Louis 喜欢整数。他定义一个非负整数序列 $A = [a_1, a_2, \dots, a_k]$ 的值为以下公式（$\oplus$ 表示按位异或）：

$$\sum_{i=1}^{k} \sum_{j=1}^{i-1} a_i \oplus a_j$$

他想知道有多少个不同的序列 $A$ 满足以下条件：

• $A$ 的长度为 $k$。
• $A$ 的值为 $n$。
• $0 \le a_i \le m$ ($1 \le i \le k$)。

两个序列 $[a_1, \dots, a_k]$ 和 $[b_1, \dots, b_k]$ 被视为不同，当且仅当存在一个下标 $i$ 使得 $a_i \neq b_i$。请告诉 Louis 答案对 $10^9 + 7$ 取模的结果。

输入格式

输入包含一行，包含三个整数 $n, m, k$ ($0 \le n \le 10^{15}, 0 \le m \le 10^{12}, 1 \le k \le 18$)。

输出格式

输出答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

6 2 3

样例输出 1

12

样例输入 2

30 6 5

样例输出 2

1520

说明

在第一个样例中，合法的序列为： $[0, 1, 2], [0, 2, 1], [1, 0, 2], [2, 0, 1], [1, 2, 0], [2, 1, 0], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], [1, 2, 2]$。