cho.sh

간단한 함수

합이 소수 M의 배수가 되면 0으로 초기화되는 파스칼식 점화식으로 정의된 f에 대해 최대 10^4개의 f(a, b, M) 값을 10^9+7로 나눈 나머지로 구한다.

어려움8정수론조합론수학동적 계획법아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

음이 아닌 정수의 집합을 NN이라 하자. 함수 f:N3→Nf : N^3 \to N을 다음과 같이 정의한다.

  • 모든 ii와 MM에 대해 f(i,0,M)=1f(i, 0, M) = 1이다.
  • 모든 ii와 MM에 대해 f(i,i,M)=1f(i, i, M) = 1이다.
  • i<xi < x이면 f(i,x,M)=0f(i, x, M) = 0이다.
  • 0<x<i0 < x < i이고 f(i−1,x−1,M)+f(i−1,x,M)f(i - 1, x - 1, M) + f(i - 1, x, M)이 MM의 배수가 아니면, 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)이다.
  • 0<x<i0 < x < i이고 f(i−1,x−1,M)+f(i−1,x,M)f(i - 1, x - 1, M) + f(i - 1, x, M)이 MM의 배수이면, f(i,x,M)=0f(i, x, M) = 0이다.

예를 들어 f(2,1,2)=0f(2, 1, 2) = 0이고 f(4,2,5)=6f(4, 2, 5) = 6이다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 이어지는 TT개의 줄에 각각 세 정수 aa, bb, MM이 공백으로 구분되어 주어진다. 각 줄마다 f(a,b,M)f(a, b, M)의 값을 구해야 한다.

다음을 가정해도 된다.

  • 1≤T≤1041 \le T \le 10^4
  • 0≤a<2310 \le a < 2^{31}
  • 0≤b<2310 \le b < 2^{31}
  • MM은 10 00010\,000 이하의 소수이다.

출력

각 테스트 케이스마다 답을 109+710^9 + 7로 나눈 나머지를 한 줄에 하나씩 출력한다.