#include <stdio.h>
#include "gmp.h"
/// dlfcn.h ///
#if defined(WIN32) || (!defined(__GNUC__) && !defined(__clang__))
void* LoadLibraryA(const char *x);
void* GetProcAddress(void *x,const char *y);
int FreeLibrary(void *x);
#elif defined(__APPLE__)
void* dlopen(const char *x,int y);
void* dlsym(void *x,const char *y);
int dlclose(void *x);
#define LoadLibraryA(s) dlopen(s,2)
#define GetProcAddress dlsym
#define FreeLibrary dlclose
#else
void* __libc_dlopen_mode(const char *x,int y);
void* __libc_dlsym(void *x,const char *y);
int __libc_dlclose(void *x);
#define LoadLibraryA(s) __libc_dlopen_mode(s,2)
#define GetProcAddress __libc_dlsym
#define FreeLibrary __libc_dlclose
#endif
typedef void (*type_mpz_init)(mpz_t);
typedef void (*type_mpz_clear)(mpz_t);
typedef void (*type_mpz_out_str)(FILE*,int,mpz_t);
typedef void (*type_mpz_set)(mpz_t,mpz_t);
typedef void (*type_mpz_set_ui)(mpz_t,unsigned long);
typedef void (*type_mpz_cmp_ui)(mpz_t,unsigned long);
typedef void (*type_mpz_add)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_sub)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_mul)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_tdiv_q)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_tdiv_r)(mpz_t,mpz_t,mpz_t);
type_mpz_init mympz_init;
type_mpz_clear mympz_clear;
type_mpz_out_str mympz_out_str;
type_mpz_set mympz_set;
type_mpz_set_ui mympz_set_ui;
type_mpz_cmp_ui mympz_cmp_ui;
type_mpz_add mympz_add;
type_mpz_sub mympz_sub;
type_mpz_mul mympz_mul;
type_mpz_tdiv_q mympz_tdiv_q;
type_mpz_tdiv_r mympz_tdiv_r;
void mul(mpz_t a1,mpz_t b1,mpz_t c1,mpz_t d1,mpz_t a2,mpz_t b2,mpz_t c2,mpz_t d2){
mpz_t a0,b0,c0,d0,t,u;
mympz_init(a0);
mympz_init(b0);
mympz_init(c0);
mympz_init(d0);
mympz_init(t);
mympz_init(u);
mympz_mul(t,a1,a2);
mympz_mul(u,b1,c2);
mympz_add(a0,t,u);
mympz_mul(t,a1,b2);
mympz_mul(u,b1,d2);
mympz_add(b0,t,u);
mympz_mul(t,c1,a2);
mympz_mul(u,d1,c2);
mympz_add(c0,t,u);
mympz_mul(t,c1,b2);
mympz_mul(u,d1,d2);
mympz_add(d0,t,u);
mympz_set(a1,a0);
mympz_set(b1,b0);
mympz_set(c1,c0);
mympz_set(d1,d0);
mympz_clear(a0);
mympz_clear(b0);
mympz_clear(c0);
mympz_clear(d0);
mympz_clear(t);
mympz_clear(u);
}
int main(){
//void *h=LoadLibraryA("/opt/local/lib/libgmp.dylib"); //MacPorts
//void *h=LoadLibraryA("/usr/lib/i386-linux-gnu/libgmp.so.10.0.5"); //ideone-codeiq
void *h=LoadLibraryA("/usr/lib/i386-linux-gnu/libgmp.so.10"); //ideone
//void *h=LoadLibraryA("/usr/lib64/libgmp.so.10.0.2"); //wandbox
//void *h=LoadLibraryA("/usr/lib64/libgmp.so.10"); //yukicoder
mympz_init=(type_mpz_init)GetProcAddress(h,"__gmpz_init");
mympz_clear=(type_mpz_clear)GetProcAddress(h,"__gmpz_clear");
mympz_out_str=(type_mpz_out_str)GetProcAddress(h,"__gmpz_out_str");
mympz_set=(type_mpz_set)GetProcAddress(h,"__gmpz_set");
mympz_set_ui=(type_mpz_set_ui)GetProcAddress(h,"__gmpz_set_ui");
mympz_cmp_ui=(type_mpz_cmp_ui)GetProcAddress(h,"__gmpz_cmp_ui");
mympz_add=(type_mpz_add)GetProcAddress(h,"__gmpz_add");
mympz_sub=(type_mpz_sub)GetProcAddress(h,"__gmpz_sub");
mympz_mul=(type_mpz_mul)GetProcAddress(h,"__gmpz_mul");
mympz_tdiv_q=(type_mpz_tdiv_q)GetProcAddress(h,"__gmpz_tdiv_q");
mympz_tdiv_r=(type_mpz_tdiv_r)GetProcAddress(h,"__gmpz_tdiv_r");
mpz_t a1,b1,c1,d1,a2,b2,c2,d2;
mympz_init(a1);
mympz_init(b1);
mympz_init(c1);
mympz_init(d1);
mympz_init(a2);
mympz_init(b2);
mympz_init(c2);
mympz_init(d2);
mympz_set_ui(a1,1);
mympz_set_ui(b1,0);
mympz_set_ui(c1,0);
mympz_set_ui(d1,1);
mympz_set_ui(a2,1);
mympz_set_ui(b2,1);
mympz_set_ui(c2,1);
mympz_set_ui(d2,0);
int N;
N=(N+3)/2*2;
for(;N;N>>=1){
if(N&1)mul(a1,b1,c1,d1,a2,b2,c2,d2);
mul(a2,b2,c2,d2,a2,b2,c2,d2);
}
mympz_set_ui(a2,1);
mympz_sub(c1,c1,a2);
mympz_out_str(stdout,10,c1);
mympz_clear(a1);
mympz_clear(b1);
mympz_clear(c1);
mympz_clear(d1);
mympz_clear(a2);
mympz_clear(b2);
mympz_clear(c2);
mympz_clear(d2);
FreeLibrary(h);
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlICJnbXAuaCIKCi8vLyBkbGZjbi5oIC8vLwojaWYgZGVmaW5lZChXSU4zMikgfHwgKCFkZWZpbmVkKF9fR05VQ19fKSAmJiAhZGVmaW5lZChfX2NsYW5nX18pKQoJdm9pZCogTG9hZExpYnJhcnlBKGNvbnN0IGNoYXIgKngpOwoJdm9pZCogR2V0UHJvY0FkZHJlc3Modm9pZCAqeCxjb25zdCBjaGFyICp5KTsKCWludCAgIEZyZWVMaWJyYXJ5KHZvaWQgKngpOwojZWxpZiBkZWZpbmVkKF9fQVBQTEVfXykKCXZvaWQqIGRsb3Blbihjb25zdCBjaGFyICp4LGludCB5KTsKCXZvaWQqIGRsc3ltKHZvaWQgKngsY29uc3QgY2hhciAqeSk7CglpbnQgICBkbGNsb3NlKHZvaWQgKngpOwoJI2RlZmluZSBMb2FkTGlicmFyeUEocykgZGxvcGVuKHMsMikKCSNkZWZpbmUgR2V0UHJvY0FkZHJlc3MgZGxzeW0KCSNkZWZpbmUgRnJlZUxpYnJhcnkgZGxjbG9zZQojZWxzZQoJdm9pZCogX19saWJjX2Rsb3Blbl9tb2RlKGNvbnN0IGNoYXIgKngsaW50IHkpOwoJdm9pZCogX19saWJjX2Rsc3ltKHZvaWQgKngsY29uc3QgY2hhciAqeSk7CglpbnQgICBfX2xpYmNfZGxjbG9zZSh2b2lkICp4KTsKCSNkZWZpbmUgTG9hZExpYnJhcnlBKHMpIF9fbGliY19kbG9wZW5fbW9kZShzLDIpCgkjZGVmaW5lIEdldFByb2NBZGRyZXNzIF9fbGliY19kbHN5bQoJI2RlZmluZSBGcmVlTGlicmFyeSBfX2xpYmNfZGxjbG9zZQojZW5kaWYKCnR5cGVkZWYgdm9pZCAoKnR5cGVfbXB6X2luaXQpKG1wel90KTsKdHlwZWRlZiB2b2lkICgqdHlwZV9tcHpfY2xlYXIpKG1wel90KTsKdHlwZWRlZiB2b2lkICgqdHlwZV9tcHpfb3V0X3N0cikoRklMRSosaW50LG1wel90KTsKdHlwZWRlZiB2b2lkICgqdHlwZV9tcHpfc2V0KShtcHpfdCxtcHpfdCk7CnR5cGVkZWYgdm9pZCAoKnR5cGVfbXB6X3NldF91aSkobXB6X3QsdW5zaWduZWQgbG9uZyk7CnR5cGVkZWYgdm9pZCAoKnR5cGVfbXB6X2NtcF91aSkobXB6X3QsdW5zaWduZWQgbG9uZyk7Cgp0eXBlZGVmIHZvaWQgKCp0eXBlX21wel9hZGQpKG1wel90LG1wel90LG1wel90KTsKdHlwZWRlZiB2b2lkICgqdHlwZV9tcHpfc3ViKShtcHpfdCxtcHpfdCxtcHpfdCk7CnR5cGVkZWYgdm9pZCAoKnR5cGVfbXB6X211bCkobXB6X3QsbXB6X3QsbXB6X3QpOwp0eXBlZGVmIHZvaWQgKCp0eXBlX21wel90ZGl2X3EpKG1wel90LG1wel90LG1wel90KTsKdHlwZWRlZiB2b2lkICgqdHlwZV9tcHpfdGRpdl9yKShtcHpfdCxtcHpfdCxtcHpfdCk7Cgp0eXBlX21wel9pbml0IG15bXB6X2luaXQ7CnR5cGVfbXB6X2NsZWFyIG15bXB6X2NsZWFyOwp0eXBlX21wel9vdXRfc3RyIG15bXB6X291dF9zdHI7CnR5cGVfbXB6X3NldCBteW1wel9zZXQ7CnR5cGVfbXB6X3NldF91aSBteW1wel9zZXRfdWk7CnR5cGVfbXB6X2NtcF91aSBteW1wel9jbXBfdWk7Cgp0eXBlX21wel9hZGQgbXltcHpfYWRkOwp0eXBlX21wel9zdWIgbXltcHpfc3ViOwp0eXBlX21wel9tdWwgbXltcHpfbXVsOwp0eXBlX21wel90ZGl2X3EgbXltcHpfdGRpdl9xOwp0eXBlX21wel90ZGl2X3IgbXltcHpfdGRpdl9yOwoKdm9pZCBtdWwobXB6X3QgYTEsbXB6X3QgYjEsbXB6X3QgYzEsbXB6X3QgZDEsbXB6X3QgYTIsbXB6X3QgYjIsbXB6X3QgYzIsbXB6X3QgZDIpewoJbXB6X3QgYTAsYjAsYzAsZDAsdCx1OwoJbXltcHpfaW5pdChhMCk7CglteW1wel9pbml0KGIwKTsKCW15bXB6X2luaXQoYzApOwoJbXltcHpfaW5pdChkMCk7CglteW1wel9pbml0KHQpOwoJbXltcHpfaW5pdCh1KTsKCglteW1wel9tdWwodCxhMSxhMik7CglteW1wel9tdWwodSxiMSxjMik7CglteW1wel9hZGQoYTAsdCx1KTsKCW15bXB6X211bCh0LGExLGIyKTsKCW15bXB6X211bCh1LGIxLGQyKTsKCW15bXB6X2FkZChiMCx0LHUpOwoJbXltcHpfbXVsKHQsYzEsYTIpOwoJbXltcHpfbXVsKHUsZDEsYzIpOwoJbXltcHpfYWRkKGMwLHQsdSk7CglteW1wel9tdWwodCxjMSxiMik7CglteW1wel9tdWwodSxkMSxkMik7CglteW1wel9hZGQoZDAsdCx1KTsKCglteW1wel9zZXQoYTEsYTApOwoJbXltcHpfc2V0KGIxLGIwKTsKCW15bXB6X3NldChjMSxjMCk7CglteW1wel9zZXQoZDEsZDApOwoKCW15bXB6X2NsZWFyKGEwKTsKCW15bXB6X2NsZWFyKGIwKTsKCW15bXB6X2NsZWFyKGMwKTsKCW15bXB6X2NsZWFyKGQwKTsKCW15bXB6X2NsZWFyKHQpOwoJbXltcHpfY2xlYXIodSk7Cn0KCmludCBtYWluKCl7CgkvL3ZvaWQgKmg9TG9hZExpYnJhcnlBKCIvb3B0L2xvY2FsL2xpYi9saWJnbXAuZHlsaWIiKTsgLy9NYWNQb3J0cwoJLy92b2lkICpoPUxvYWRMaWJyYXJ5QSgiL3Vzci9saWIvaTM4Ni1saW51eC1nbnUvbGliZ21wLnNvLjEwLjAuNSIpOyAvL2lkZW9uZS1jb2RlaXEKCXZvaWQgKmg9TG9hZExpYnJhcnlBKCIvdXNyL2xpYi9pMzg2LWxpbnV4LWdudS9saWJnbXAuc28uMTAiKTsgLy9pZGVvbmUKCS8vdm9pZCAqaD1Mb2FkTGlicmFyeUEoIi91c3IvbGliNjQvbGliZ21wLnNvLjEwLjAuMiIpOyAvL3dhbmRib3gKCS8vdm9pZCAqaD1Mb2FkTGlicmFyeUEoIi91c3IvbGliNjQvbGliZ21wLnNvLjEwIik7IC8veXVraWNvZGVyCgoJbXltcHpfaW5pdD0odHlwZV9tcHpfaW5pdClHZXRQcm9jQWRkcmVzcyhoLCJfX2dtcHpfaW5pdCIpOwoJbXltcHpfY2xlYXI9KHR5cGVfbXB6X2NsZWFyKUdldFByb2NBZGRyZXNzKGgsIl9fZ21wel9jbGVhciIpOwoJbXltcHpfb3V0X3N0cj0odHlwZV9tcHpfb3V0X3N0cilHZXRQcm9jQWRkcmVzcyhoLCJfX2dtcHpfb3V0X3N0ciIpOwoJbXltcHpfc2V0PSh0eXBlX21wel9zZXQpR2V0UHJvY0FkZHJlc3MoaCwiX19nbXB6X3NldCIpOwoJbXltcHpfc2V0X3VpPSh0eXBlX21wel9zZXRfdWkpR2V0UHJvY0FkZHJlc3MoaCwiX19nbXB6X3NldF91aSIpOwoJbXltcHpfY21wX3VpPSh0eXBlX21wel9jbXBfdWkpR2V0UHJvY0FkZHJlc3MoaCwiX19nbXB6X2NtcF91aSIpOwoKCW15bXB6X2FkZD0odHlwZV9tcHpfYWRkKUdldFByb2NBZGRyZXNzKGgsIl9fZ21wel9hZGQiKTsKCW15bXB6X3N1Yj0odHlwZV9tcHpfc3ViKUdldFByb2NBZGRyZXNzKGgsIl9fZ21wel9zdWIiKTsKCW15bXB6X211bD0odHlwZV9tcHpfbXVsKUdldFByb2NBZGRyZXNzKGgsIl9fZ21wel9tdWwiKTsKCW15bXB6X3RkaXZfcT0odHlwZV9tcHpfdGRpdl9xKUdldFByb2NBZGRyZXNzKGgsIl9fZ21wel90ZGl2X3EiKTsKCW15bXB6X3RkaXZfcj0odHlwZV9tcHpfdGRpdl9yKUdldFByb2NBZGRyZXNzKGgsIl9fZ21wel90ZGl2X3IiKTsKCgltcHpfdCBhMSxiMSxjMSxkMSxhMixiMixjMixkMjsKCW15bXB6X2luaXQoYTEpOwoJbXltcHpfaW5pdChiMSk7CglteW1wel9pbml0KGMxKTsKCW15bXB6X2luaXQoZDEpOwoJbXltcHpfaW5pdChhMik7CglteW1wel9pbml0KGIyKTsKCW15bXB6X2luaXQoYzIpOwoJbXltcHpfaW5pdChkMik7CgoJbXltcHpfc2V0X3VpKGExLDEpOwoJbXltcHpfc2V0X3VpKGIxLDApOwoJbXltcHpfc2V0X3VpKGMxLDApOwoJbXltcHpfc2V0X3VpKGQxLDEpOwoJbXltcHpfc2V0X3VpKGEyLDEpOwoJbXltcHpfc2V0X3VpKGIyLDEpOwoJbXltcHpfc2V0X3VpKGMyLDEpOwoJbXltcHpfc2V0X3VpKGQyLDApOwoJCglpbnQgTjsKCXNjYW5mKCIlZCIsJk4pOwoJTj0oTiszKS8yKjI7Cglmb3IoO047Tj4+PTEpewoJCWlmKE4mMSltdWwoYTEsYjEsYzEsZDEsYTIsYjIsYzIsZDIpOwoJCW11bChhMixiMixjMixkMixhMixiMixjMixkMik7Cgl9CglteW1wel9zZXRfdWkoYTIsMSk7CglteW1wel9zdWIoYzEsYzEsYTIpOwoJbXltcHpfb3V0X3N0cihzdGRvdXQsMTAsYzEpOwoJcHV0cygiIik7CgoJbXltcHpfY2xlYXIoYTEpOwoJbXltcHpfY2xlYXIoYjEpOwoJbXltcHpfY2xlYXIoYzEpOwoJbXltcHpfY2xlYXIoZDEpOwoJbXltcHpfY2xlYXIoYTIpOwoJbXltcHpfY2xlYXIoYjIpOwoJbXltcHpfY2xlYXIoYzIpOwoJbXltcHpfY2xlYXIoZDIpOwoKCUZyZWVMaWJyYXJ5KGgpOwp9