Louis loves integers. He defines the value of a sequence of non-negative integers $$$A = [a_1, a_2 ,\ldots, a_k]$$$ as the following formula ($$$\oplus$$$ means bitwise exclusive-or):
$$$$$$ \sum \limits_{i = 1}^k \sum \limits_{j = 1}^{i - 1} a_i \oplus a_j $$$$$$
He wants to know how many different sequences $$$A$$$ holds the following conditions:
Two sequences $$$[a_1, \dots, a_k]$$$, $$$[b_1, \dots, b_k]$$$ are considered different if and only if there exists an index $$$i$$$ such that $$$a_i \neq b_i$$$. Tell Louis the answer module $$$10^9 + 7$$$.
The input contains of single line containing three integers $$$n$$$, $$$m$$$, $$$k$$$, ($$$0 \leq n \leq 10^{15}$$$, $$$0 \leq m \leq 10^{12}$$$, $$$1 \leq k \leq 18$$$).
Output the answer modulo $$$10^9 + 7$$$.
6 2 3
12
30 6 5
1520
In the first example, vaild sequences are
$$$[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]$$$.
