题目描述
有 n 个人在进行异或游戏,其规则如下:
第 i 个人拥有一个二进制表示下(忽略前导零)不超过 m 位的 互不相同的正整数 ai,则游戏的结局为 ret=a1⊕a2⊕⋯⊕ak−1⊕ak,其中 a⊕b 表示 a 与 b 按位异或的结果。
当 ret=0 时,我们认为游戏是 nim 的。
给定 n,请你求出有多少种 {an} 使得游戏是 nim 的。
{an} 与 {bn} 不同,当且仅当,存在 1≤i≤n,满足 ∀1≤j≤n,bj=ai。
因为答案可能很大,所以只需要你输出答案模 10k 的值。
输入格式
第一行三个正整数 n,m,k。
输出格式
一个整数,表示答案。
样例 1
2 2 2
0
5 5 5
5208
数据范围与提示
对于 100% 的数据,n≤1013,m≤45,k≤min(62−m,18),保证 n<2m。