题目描述

有 $n$ 个人在进行异或游戏，其规则如下：
第 $i$ 个人拥有一个二进制表示下（忽略前导零）不超过 $m$ 位的 互不相同的正整数 $a_i$，则游戏的结局为 $ret=a_1\oplus a_2\oplus \dots\oplus a_{k-1}\oplus a_k$，其中 $a\oplus b$ 表示 $a$ 与 $b$ 按位异或的结果。
当 $ret=0$ 时，我们认为游戏是 $nim$ 的。
给定 $n$，请你求出有多少种 $\{a_n\}$ 使得游戏是 $nim$ 的。
$\{a_n\}$ 与 $\{b_n\}$ 不同，当且仅当，存在 $1\leq i\leq n$，满足 $\forall 1\leq j\leq n, b_j\neq a_i$。
因为答案可能很大，所以只需要你输出答案模 $10^k$ 的值。

输入格式

第一行三个正整数 $n,m,k$。

输出格式

一个整数，表示答案。

2 2 2

0

5 5 5

5208

数据范围与提示

对于 $100\%$ 的数据，$n\leq 10^{13}, m\leq 45, k\leq \min(62-m,18)$，保证 $n<2^m$。