题目描述

有 $n$ 个人在进行异或游戏，其规则如下：

第 $i$ 个人拥有一个二进制表示下（忽略前导零）不超过 $m$ 位的互不相同的正整数 $a_i$，则游戏的结局为 $\text{ret} = a_1 \oplus a_2 \oplus \dots \oplus a_{n-1} \oplus a_n$，其中 $a \oplus b$ 表示 $a$ 与 $b$ 按位异或的结果。

当 $\text{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$。