1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 unsigned long long N = 0;
 9 struct Mat
10 {
11     unsigned long long mat[2][2];
12     Mat operator * (Mat &b)
13     {
14         Mat tmp;
15         memset(tmp.mat,0,sizeof(tmp.mat));
16         for(int i = 0; i < 2; ++i)
17         {
18             for(int j = 0; j < 2; ++j)
19             {
20                 for(int k = 0; k < 2; ++k)
21                 {
22                     tmp.mat[i][j] += mat[i][k] * b.mat[k][j];
23                 }
24                 if(tmp.mat[i][j] > N) tmp.mat[i][j] %= N;
25             }
26         }
27         return tmp;
28     }
29     Mat pow(int k)
30     {
31         if(k == 0)
32         {
33             mat[0][0] = mat[1][1] = 1;
34             mat[0][1] = mat[1][0] = 0;
35             return *this;
36         }
37         else if(k == 1) return *this;
38         else
39         {
40             Mat tmp;
41             tmp = *this * (*this);
42             if(k & 1) return tmp.pow(k/2) * (*this);
43             else return tmp.pow(k/2);
44         }
45     }
46 };
47 unsigned long long n,m;
48 int main()
49 {
50     while(cin >> n >> m)
51     {
52         if(n == 0) cout << "0" << endl;
53         else
54         {
55             N = 1<<m;
56             Mat f;
57             f.mat[0][0] = f.mat[0][1] = f.mat[1][0] = 1;
58             f.mat[1][1] = 0;
59             f = f.pow(n-1);
60             cout << f.mat[0][0]%N << endl;
61         }
62     }
63     return 0;
64 }

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 long long f[2000000];
 5 int main()
 6 {
 7     int n , m;
 8     while(cin >> n >> m)
 9     {
10         f[0] = 0; f[1] = 1;
11         long long  N = 1<<m;
12         int i;
13         for(i = 2; i <= n; ++i)
14         {
15             f[i] = (f[i-1] % N + f[i-2] % N) % N;
16             if(f[i] == 1 && f[i-1] == 0) break;
17         }
18         if(i > n) cout << f[n] << endl;
19         else cout << f[n % (i - 1)] << endl;
20     }
21     return 0;
22 }
23 

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 typedef long long ll;
 7 ll dp[1000];
 8 
 9 ll hash(ll t,ll n)
10 {
11     return t*4+n%4;
12 }
13 
14 ll f(ll n,ll m,ll cur)
15 {
16     if(n<3)
17     return 1%m;
18     ll u=hash(cur,n);
19     if(dp[u]>-1)
20     return dp[u];
21     ll i=n/2;
22     ll f1=f(i,m,cur+1);
23     ll f2=f(n-i-1,m,cur+1);
24     ll f3=f(i+1,m,cur+1);
25     ll f4=f(n-i,m,cur+1);
26     return dp[u]=((f1*f2)%m+(f3*f4)%m)%m;
27 }
28 
29 int main()
30 {
31     ll m,n;
32     while(scanf("%lld%lld",&n,&m)!=EOF)
33     {
34         memset(dp,-1,sizeof(dp));
35         printf("%lld\n",n?f(n,1<<m,0):0);
36     }
37     return 0;
38 }