15471번 - A Simple Function 다국어

문제

A function f : N³ → 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 ≤ 10⁴
• 0 ≤ a < 2³¹
• 0 ≤ b < 2³¹
• M ≤ 10000 is a prime

출력

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

제한

힌트