아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

간단한 함수

시간 제한1초메모리 제한512 MB

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

어려움10점 중 8점

유형
정수론, 조합론, 수학, 동적 계획법
정답자
아직 제출이 없습니다

문제

음이 아닌 정수의 집합을 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로 나눈 나머지를 한 줄에 하나씩 출력한다.

예제4

  1. 예제 1

    입력
    2
2 1 2
4 2 5
    예상 출력
    0
6

  2. 예제 2

    입력
    6
0 0 2
0 0 9973
5 0 7
7 7 3
3 5 2
0 1 2
    예상 출력
    1
1
1
1
0
0

  3. 예제 3

    입력
    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
    예상 출력
    1
0
1
0
0
0
0
0

  4. 예제 4

    입력
    6
9 3 3
10 5 3
26 13 3
27 1 3
80 40 3
81 27 3
    예상 출력
    0
0
8
0
16
0