#include "iostream"#include "cstdio"using namespace std;class matrix{public: int a[2][2]; matrix() { a[0][0]=a[1][0]=a[0][1]=1; a[1][1]=0; }};matrix multi(matrix a,matrix b){ matrix temp; int i,j,k; for(i=0;i<2;i++) for(j=0;j<2;j++) { temp.a[i][j]=0; for(k=0;k<2;k++) temp.a[i][j]+=(a.a[i][k]*b.a[k][j]); temp.a[i][j]%=10000; } return temp;}matrix power(int n){ matrix temp,s; temp.a[0][1]=temp.a[1][0]=0; temp.a[0][0]=temp.a[1][1]=1; while(n!=0) { if(n%2!=0) temp=multi(temp,s); s=multi(s,s); n=n/2; } return temp;}int main(){ int n; while(~scanf("%d",&n)&&(n!=-1)) { matrix t=power(n); cout< <
#include "iostream"#include "cstdio"using namespace std;#define MOD 1000000009#define LL long longclass matrix{public: LL a[2][2]; matrix() { a[0][0]=a[1][0]=a[0][1]=1; a[1][1]=0; }};matrix multi(matrix a,matrix b){ matrix temp; LL i,j,k; for(i=0;i<2;i++) for(j=0;j<2;j++) { temp.a[i][j]=0; for(k=0;k<2;k++) temp.a[i][j]+=(a.a[i][k]*b.a[k][j]); temp.a[i][j]%=MOD; } return temp;}matrix power(LL n){ matrix temp,s; temp.a[0][1]=temp.a[1][0]=0; temp.a[0][0]=temp.a[1][1]=1; while(n!=0) { if(n%2!=0) temp=multi(temp,s); s=multi(s,s); n=n/2; } return temp;}int main(){ LL n; while(~scanf("%lld",&n)&&(n!=-1)) { matrix t=power(n); cout< <