시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

## 문제

A function f : N3 → N where N stands for the set of non-negative integers, is defined as follows.

• f(i, 0, M) = 1, for all i and M.
• f(i, i, M) = 1, for all i and M.
• f(i, x, M) = 0, for all i < x.
• f(i, x, M) = f(i − 1, x − 1, M) + f(i − 1, x, M), if f(i − 1, x − 1, M) + f(i − 1, x, M) is NOT a multiple of M, for all 0 < x < i.
• f(i, x, M) = 0, if f(i − 1, x − 1, M) + f(i − 1, x, M) is a multiple of M, for all 0 < x < i.

For example, f(2, 1, 2) = 0 and f(4, 2, 5) = 6.

## 입력

The first line of the input contains an integer T, the number of test cases. T lines follow, one line per test case consisting of three space-separated integers a, b and M indicating that the value of f(a, b, M) is to be computed.

You may assume:

• 1 ≤ T ≤ 104
• 0 ≤ a < 231
• 0 ≤ b < 231
• M ≤ 10000 is a prime

## 출력

For each test case, output a single integer which denotes your answer modulo 109 + 7 in a line.

## 예제 입력 1

2
2 1 2
4 2 5


## 예제 출력 1

0
6