This page is still under construction.

Parts of this page are still being built. What you see may change.

A Simple Function

Time limit1sMemory limit512 MB

Summary
Define f via a Pascal-like recurrence that resets to 0 whenever the sum is divisible by prime M, and answer up to 10^4 queries f(a, b, M) modulo 10^9+7.
Level

Hard8 of 10

Topics
Number theory, Combinatorics, Math, Dynamic programming
Solved
No attempts yet

Problem

Let NN be the set of non-negative integers. The function f:N3→Nf : N^3 \to N is defined as follows.

  • f(i,0,M)=1f(i, 0, M) = 1 for all ii and MM.
  • f(i,i,M)=1f(i, i, M) = 1 for all ii and MM.
  • f(i,x,M)=0f(i, x, M) = 0 whenever i<xi < x.
  • For 0<x<i0 < x < i, if f(i−1,x−1,M)+f(i−1,x,M)f(i - 1, x - 1, M) + f(i - 1, x, M) is not a multiple of MM, then f(i,x,M)=f(i−1,x−1,M)+f(i−1,x,M)f(i, x, M) = f(i - 1, x - 1, M) + f(i - 1, x, M).
  • For 0<x<i0 < x < i, if f(i−1,x−1,M)+f(i−1,x,M)f(i - 1, x - 1, M) + f(i - 1, x, M) is a multiple of MM, then f(i,x,M)=0f(i, x, M) = 0.

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

Input

The first line contains an integer TT, the number of test cases. Each of the next TT lines contains three space-separated integers aa, bb, and MM. For each such line, compute the value of f(a,b,M)f(a, b, M).

You may assume:

  • 1≤T≤1041 \le T \le 10^4
  • 0≤a<2310 \le a < 2^{31}
  • 0≤b<2310 \le b < 2^{31}
  • MM is a prime no greater than 10 00010\,000.

Output

For each test case, print the answer modulo 109+710^9 + 7 on its own line.

Examples4

  1. Example 1

    Input
    2
2 1 2
4 2 5
    Expected output
    0
6

  2. Example 2

    Input
    6
0 0 2
0 0 9973
5 0 7
7 7 3
3 5 2
0 1 2
    Expected output
    1
1
1
1
0
0

  3. Example 3

    Input
    8
1 1 2
2 1 2
3 1 2
4 1 2
4 2 2
5 2 2
6 3 2
8 4 2
    Expected output
    1
0
1
0
0
0
0
0

  4. Example 4

    Input
    6
9 3 3
10 5 3
26 13 3
27 1 3
80 40 3
81 27 3
    Expected output
    0
0
8
0
16
0