A Simple Function

英文題目敘述

A function $f:\mathbb{N}^{3} \to \mathbb{N}$ where $\mathbb{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 \le T \le 10^4$
$0 \leq a < 2^{31}$
$0 \leq b < 2^{31}$
$M \leq 10000$ is a prime

英文輸出說明

For each test case, output a single integer which denotes your answer modulo $10^{9}+7$ in a line.

範例輸入

2
2 1 2
4 2 5

範例輸出

0
6

中文題目敘述

定義一個函數 $f:\mathbb{N}^{3} \to \mathbb{N}$，其中 $\mathbb{N}$ 代表非負整數集合，$f$ 的定義如下：

對於所有的 $i$ 和 $M$，$f(i, 0, M)=1$
對於所有的 $i$ 和 $M$，$f(i, i, M)=1$
對於所有的 $i < x$，$f(i, x, M)=0$
對於所有的 $0 < x < i$，若 $f(i-1, x-1, M)+f(i-1, x, M)$ 不是 $M$ 的倍數，則 $f(i, x, M)=f(i-1, x-1, M)+f(i-1, x, M)$
對於所有的 $0 < x < i$，若 $f(i-1, x-1, M)+f(i-1, x, M)$ 是 $M$ 的倍數，則 $f(i, x, M)=0$

例如 $f(2, 1, 2) = 0$，$f(4, 2, 5) = 6$.

中文輸入說明

第一行有一個整數 $T$ 代表測試資料組數。每組測試資料由三個整數 $a$, $b$ 和 $M$ 組成，請計算 $f(a, b, M)$ 的值。

可假設：

$1 \le T \le 10^4$
$0 \leq a < 2^{31}$
$0 \leq b < 2^{31}$
$M \leq 10000$ 且是個質數

中文輸出說明

對於每組測試資料，請輸出一個整數，代表計算得到的答案除以 $10^{9}+7$ 的餘數。

Judge Setting

run-time limit: 1000 ms
memory limit: 65536000 byte
測資數量: 0