Namid[A]me 好听呢。可惜了。
今天 DP 专题感觉 laofu 选的题有点经典，导致我有一半时间在摸鱼，不过还是写了点题的。
怎么西工大附中有糖醋茄子这种神秘菜啊。
ICPC 2020 Macau B Boring Problem
其实不一定懂完了，试着说一说。
显然询问没什么用，问题本质是要求解一个 AC 自动机上游走问题。
直接高斯消元显然寄飞了，考虑优化。
考虑原本的高斯消元是什么样的，是：\(f_u=\sum_{i=1}^k p_i f_{tr(u,k)}+1\)。
考虑主元法，发现这样一件事：如果在原 Trie 上某个节点只有一个儿子，这个点在 AC 自动机上的其余转移全部会指向向上的节点，于是可以用父亲的方程推出儿子用主元表示的结果。
于是令根节点与儿子个数大于二的节点的儿子们作为主元，这样就只有 \(O(n)\) 个主元，可以使用 BFS 推出所有元用主元表示的结果，以结束点答案为 \(0\) 和「儿子个数大于二的节点」存在两种表示：「用儿子们」「从父亲推」来构造方程，于是就做到 \(O(n^3)\)，Code。
昨天模拟赛 T3 就这个东西加后半的普及组答辩，不写了。
IOI2005 River
令 \(f_{u,j,k}\) 表示对于点 \(u\) 钦定祖先 \(j\) 作为最近的伐木场，子树内选了 \(k\) 个伐木场，\(g_{u,j,k}\) 同上，但是 \(u\) 是一个伐木场，同时这个也没算进 \(k\) 里面。
于是暴力 DP 复杂度就是 \(O(n^2k^2)\)，对了，Code。
TC12909 Seat Friends
令 \(f_{i,j}\) 表示当前 \(i\) 个人 \(j\) 段，于是可以列出转移柿子：
\[\begin{aligned} 2jf_{i,j}&\to f_{i+1,j}\\ jf_{i,j}&\to f_{i+1,j-1}\\ jf_{i,j}&\to f_{i+1,j+1} \end{aligned} \]最后计算答案需要上一个组合数，还得记得考虑圆是可以转圈的，\(O(n^2)\)，Code。
CS Academy Round #32 Sum of Powers
需要知道 \(f_{i,j}\) 表 \(i\) 个数凑出 \(j\) 这样的 DP。
于是就会发现求 \(f_{i-k,j-k*l}k^m\) 的总和就是答案了，证明很好证。
/*
Author: cnyz
世界があたしを拒んでも今 愛の唄 歌わせてくれないかな
*/
#include<bits/stdc++.h>
using namespace std;
using db=double;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
using ull=unsigned long long;
#define fi first
#define se second
#define gc getchar
#define pb emplace_back
#define mkp make_pair
#define push emplace
#define sz(a) (int)a.size()
#define all(p) p.begin(),p.end()
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
bool Mbe;
void chkmax(int &x,int y) {if(x<y) x=y;}
void chkmin(int &x,int y) {if(x>y) x=y;}
void chkmax(ll &x,ll y) {if(x<y) x=y;}
void chkmin(ll &x,ll y) {if(x>y) x=y;}
int read() { int x; cin>>x; return x; }
const int mod=1e9+7;
struct modint {
int x;
modint(int o=0) { x=(0ll+mod+o)%mod; }
modint &operator = (int o) { return x=o,*this; }
modint &operator += (modint o) { return x=(x+o.x)%mod,*this; }
modint &operator -= (modint o) { return x=(mod+x-o.x)%mod,*this; }
modint &operator *= (modint o) { return x=1ull*x*o.x%mod,*this; }
modint &operator ^= (int b) {
modint a=*this,c=1;
for(;b;b>>=1) { if(b&1) c*=a; a*=a; }
return x=c.x,*this;
}
modint &operator /= (modint o) { return *this*=(o^=mod-2); }
friend modint operator + (modint a,modint b) { return a+=b; }
friend modint operator - (modint a,modint b) { return a-=b; }
friend modint operator * (modint a,modint b) { return a*=b; }
friend modint operator / (modint a,modint b) { return a/=b; }
friend modint operator ^ (modint a,int b) { return a^=b; }
friend bool operator == (modint a,int b) { return a.x==b; }
friend bool operator != (modint a,int b) { return a.x!=b; }
bool operator ! () { return !x; }
modint operator - () { return x?mod-x:0; }
bool operator < (const modint &b) const { return x<b.x; }
};
const int N=5005;
modint f[N][N],g[N];
void solve() {
int n=read(),K=read(),m=read();
f[0][0]=1;
FOR(i,0,K-1) FOR(j,0,n) {
f[i+1][j+1]+=f[i][j];
if(i&&j+i<=n) f[i][j+i]+=f[i][j];
}
modint o=0;
FOR(i,1,n) FOR(j,1,K) if(i*j<=n) {
modint pm=i; pm^=m;
o+=f[K-j][n-i*j]*pm;
}
cout<<o.x<<"\n";
}
bool Med;
int main() {
ios::sync_with_stdio(false),cin.tie(0);
// fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
int T=1;
while(T--) solve();
// fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
}