4499: M. XOR Sum

Louis loves integers. He defines the value of a sequence of non-negative integers A = [a₁, a₂ ,…, a_k] as the following formula (⊕ means bitwise exclusive-or):

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 ≤ a_i ≤ m (1 ≤ i ≤ k).

Two sequences [a₁, ..., a_k], [b₁, ..., b_k] are considered different if and only if there exists an index i such that a_i ≠ b_i. Tell Louis the answer module 10⁹ + 7.

The input contains of single line containing three integers n, m, k, (0 <= n <= 10¹⁵, 0 <= m <= 10¹², 1 <= k <= 18).

Output the answer modulo 10⁹ + 7.

6 2 3

12

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


input

30 6 5

output

1520