Submit: 0 Solved: 0

[Submit] [Status] [Web Board] [Creator:]

Bob has a set {1, 2, ..., N}, and he want to choose a subset with exactly M numbers. For a subset S, if it contains both x and Kx, then S is bad, otherwise S is good, where K is a given number.

Given N, M and K, Bob wants to know how many good subsets with exact M numbers he can choose.

Given N, M and K, Bob wants to know how many good subsets with exact M numbers he can choose.

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is only one line contain three integers N, M and K (1 <= N <= 10^9, 1 <= M, K <= 100).

There is only one line contain three integers N, M and K (1 <= N <= 10^9, 1 <= M, K <= 100).

For each test case, output the number of ways to choose a good subset with exact M numbers. The number may be too large, output it modulo 12347.

```
3
3 2 3
6 3 2
10 2 3
```

```
2
9
42
```

For sample 1, only {2, 3} and {1, 2} are good subset.

For sample 2, those 9 subsets are good: {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {1, 4, 6}, {1, 5, 6}, {2, 3, 5}, {2, 5, 6}, {3, 4, 5} and {4, 5, 6}.

For sample 3, except {1, 3}, {3, 9} and {2, 6}, all the other 42 subset are good.

For sample 2, those 9 subsets are good: {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {1, 4, 6}, {1, 5, 6}, {2, 3, 5}, {2, 5, 6}, {3, 4, 5} and {4, 5, 6}.

For sample 3, except {1, 3}, {3, 9} and {2, 6}, all the other 42 subset are good.