410579: GYM104053 M XOR Sum

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:

• The length of $$$A$$$ is $$$k$$$.
• The value of $$$A$$$ is $$$n$$$.
• $$$0\le a_i\le m$$$ ($$$1\le i\le k$$$).

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]$$$.