// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define dibs reserve
#define OVER9000 1234567890
#define patkan 9
#define tisic 47
#define soclose 1e-9
#define pi 3.1415926535898
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define chocolate win
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):(x))
#define uint unsigned int
// mylittlepony
using namespace std;
long long pow(long long a, long long e, long long m) {
if(e <= 0) return 1;
int x =pow(a,e/2,m);
x =(x*x)%m;
if(e%2 != 0) x =(x*a)%m;
return x;}
int main() {
cin.sync_with_stdio(0);
int N,K,M;
cin >> N >> K >> M;
int mod =(1<<M)-1;
vector<int> A[N/2+1];
A[0].push_back(0);
for(int i =0; i < N/2; i++) {
A[i+1].dibs(A[i].size()*26);
ALL_THE(A[i],it) for(int j =1; j <= 26; j++)
A[i+1].push_back((((*it)*33)^j)&mod);
}
int n =N-N/2;
int inv =(int)pow(33LL,(1LL<<(M-1))-1LL,1LL<<M);
vector<int> B[n+1];
B[0].push_back(K);
for(int i =0; i < n; i++) {
B[i+1].dibs(B[i].size()*26);
ALL_THE(B[i],it) for(int j =1; j <= 26; j++)
B[i+1].push_back((((*it)^j)*inv)&mod);
}
vector<int> sA(1<<M,0);
ALL_THE(A[N/2],it) sA[*it]++;
long long ans =0;
ALL_THE(B[n],it) ans +=sA[*it];
cout << ans << "\n";
return 0;}
// look at my code
// my code is amazing
Ly8gaW9zdHJlYW0gaXMgdG9vIG1haW5zdHJlYW0KI2luY2x1ZGUgPGNzdGRpbz4KLy8gYml0Y2ggcGxlYXNlCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPGlvbWFuaXA+CiNkZWZpbmUgZGlicyByZXNlcnZlCiNkZWZpbmUgT1ZFUjkwMDAgMTIzNDU2Nzg5MAojZGVmaW5lIHBhdGthbiA5CiNkZWZpbmUgdGlzaWMgNDcKI2RlZmluZSBzb2Nsb3NlIDFlLTkKI2RlZmluZSBwaSAzLjE0MTU5MjY1MzU4OTgKI2RlZmluZSBBTExfVEhFKENBS0UsTElFKSBmb3IoYXV0byBMSUUgPUNBS0UuYmVnaW4oKTsgTElFICE9IENBS0UuZW5kKCk7IExJRSsrKQojZGVmaW5lIGNob2NvbGF0ZSB3aW4KI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAojZGVmaW5lIGFicyh4KSAoKHggPCAwKT8tKHgpOih4KSkKI2RlZmluZSB1aW50IHVuc2lnbmVkIGludAovLyBteWxpdHRsZXBvbnkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmxvbmcgbG9uZyBwb3cobG9uZyBsb25nIGEsIGxvbmcgbG9uZyBlLCBsb25nIGxvbmcgbSkgewogICAgaWYoZSA8PSAwKSByZXR1cm4gMTsKICAgIGludCB4ID1wb3coYSxlLzIsbSk7CiAgICB4ID0oeCp4KSVtOwogICAgaWYoZSUyICE9IDApIHggPSh4KmEpJW07CiAgICByZXR1cm4geDt9CgppbnQgbWFpbigpIHsKICAgIGNpbi5zeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBpbnQgTixLLE07CiAgICBjaW4gPj4gTiA+PiBLID4+IE07CiAgICBpbnQgbW9kID0oMTw8TSktMTsKCiAgICB2ZWN0b3I8aW50PiBBW04vMisxXTsKICAgIEFbMF0ucHVzaF9iYWNrKDApOwogICAgZm9yKGludCBpID0wOyBpIDwgTi8yOyBpKyspIHsKICAgICAgICBBW2krMV0uZGlicyhBW2ldLnNpemUoKSoyNik7CiAgICAgICAgQUxMX1RIRShBW2ldLGl0KSBmb3IoaW50IGogPTE7IGogPD0gMjY7IGorKykKICAgICAgICAgICAgQVtpKzFdLnB1c2hfYmFjaygoKCgqaXQpKjMzKV5qKSZtb2QpOwogICAgICAgIH0KCiAgICBpbnQgbiA9Ti1OLzI7CiAgICBpbnQgaW52ID0oaW50KXBvdygzM0xMLCgxTEw8PChNLTEpKS0xTEwsMUxMPDxNKTsKCiAgICB2ZWN0b3I8aW50PiBCW24rMV07CiAgICBCWzBdLnB1c2hfYmFjayhLKTsKICAgIGZvcihpbnQgaSA9MDsgaSA8IG47IGkrKykgewoJCUJbaSsxXS5kaWJzKEJbaV0uc2l6ZSgpKjI2KTsKCQlBTExfVEhFKEJbaV0saXQpIGZvcihpbnQgaiA9MTsgaiA8PSAyNjsgaisrKQoJCQlCW2krMV0ucHVzaF9iYWNrKCgoKCppdCleaikqaW52KSZtb2QpOwogICAgICAgIH0KCiAgICB2ZWN0b3I8aW50PiBzQSgxPDxNLDApOwogICAgQUxMX1RIRShBW04vMl0saXQpIHNBWyppdF0rKzsKCiAgICBsb25nIGxvbmcgYW5zID0wOwogICAgQUxMX1RIRShCW25dLGl0KSBhbnMgKz1zQVsqaXRdOwogICAgY291dCA8PCBhbnMgPDwgIlxuIjsKICAgIHJldHVybiAwO30KCi8vIGxvb2sgYXQgbXkgY29kZQovLyBteSBjb2RlIGlzIGFtYXppbmcK
prog.cpp: In function ‘int main()’:
prog.cpp:20:31: warning: ‘auto’ changes meaning in C++11; please remove it [-Wc++0x-compat]
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:46:9: note: in expansion of macro ‘ALL_THE’
ALL_THE(A[i],it) for(int j =1; j <= 26; j++)
^
prog.cpp:46:22: error: ‘it’ does not name a type
ALL_THE(A[i],it) for(int j =1; j <= 26; j++)
^
prog.cpp:20:36: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:46:22: error: expected ‘;’ before ‘it’
ALL_THE(A[i],it) for(int j =1; j <= 26; j++)
^
prog.cpp:20:55: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:46:22: error: ‘it’ was not declared in this scope
ALL_THE(A[i],it) for(int j =1; j <= 26; j++)
^
prog.cpp:20:55: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:20:31: warning: ‘auto’ changes meaning in C++11; please remove it [-Wc++0x-compat]
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:57:3: note: in expansion of macro ‘ALL_THE’
ALL_THE(B[i],it) for(int j =1; j <= 26; j++)
^
prog.cpp:57:16: error: ‘it’ does not name a type
ALL_THE(B[i],it) for(int j =1; j <= 26; j++)
^
prog.cpp:20:36: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:57:16: error: expected ‘;’ before ‘it’
ALL_THE(B[i],it) for(int j =1; j <= 26; j++)
^
prog.cpp:20:55: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:57:16: error: ‘it’ was not declared in this scope
ALL_THE(B[i],it) for(int j =1; j <= 26; j++)
^
prog.cpp:20:55: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:20:31: warning: ‘auto’ changes meaning in C++11; please remove it [-Wc++0x-compat]
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:62:5: note: in expansion of macro ‘ALL_THE’
ALL_THE(A[N/2],it) sA[*it]++;
^
prog.cpp:62:20: error: ‘it’ does not name a type
ALL_THE(A[N/2],it) sA[*it]++;
^
prog.cpp:20:36: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:62:20: error: expected ‘;’ before ‘it’
ALL_THE(A[N/2],it) sA[*it]++;
^
prog.cpp:20:55: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:62:20: error: ‘it’ was not declared in this scope
ALL_THE(A[N/2],it) sA[*it]++;
^
prog.cpp:20:55: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:20:31: warning: ‘auto’ changes meaning in C++11; please remove it [-Wc++0x-compat]
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:65:5: note: in expansion of macro ‘ALL_THE’
ALL_THE(B[n],it) ans +=sA[*it];
^
prog.cpp:65:18: error: ‘it’ does not name a type
ALL_THE(B[n],it) ans +=sA[*it];
^
prog.cpp:20:36: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:65:18: error: expected ‘;’ before ‘it’
ALL_THE(B[n],it) ans +=sA[*it];
^
prog.cpp:20:55: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^
prog.cpp:65:18: error: ‘it’ was not declared in this scope
ALL_THE(B[n],it) ans +=sA[*it];
^
prog.cpp:20:55: note: in definition of macro ‘ALL_THE’
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
^