Given a set S of first N non-negative integers i.e. S = {0, 1, 2, ..., N}. Find number of ways of choosing a K size subset of S with the property that the XOR-sum of all chosen integers has exactly B set bits in its binary representation (i.e. the bits that are equal to 1). Since the answer can be large, output it modulo (10⁹ + 7). Please refer to notes section for formal definition of XOR-sum.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The only line of each test case contains three space-separated integers N, K and B.

Output

For each test case, output a single line containing the answer to the corresponding test case.

Constraints

• 1 = T = 5
• 1 = N = 10⁹
• 1 = K = 7
• 0 = B = 30

Example

Input: 3 2 2 0 2 2 1 2 2 2 Output: 0 2 1

Notes

XOR-sum of n integers A[1], , , A[n] will be A[1] xor A[2] xor .. A[n]. By xor, we mean bit-wise xor.

Explanation

Example case 1. There is no way to choose a subset of 2 integers from {0, 1, 2} such that the XOR-sum contains 0 set bits.

Example case 2. The two possible subsets in this case are {0, 1} and {0, 2}. In both cases the XOR-sum (1 and 2 respectively) contains exactly one set bit.

Example case 3. The only possible subset is {1, 2}.