Crypto

Pesho는 1부터 N까지의 정수가 정확히 한 번씩 나타나는 수열을 암호화한다. 그는 다음 알고리즘을 사용한다:

1. 각 초기 수 X를 X번째 소수로 바꾼다.
2. N 이하의 양의 정수 K를 무작위로 고른다.
3. 연속한 원소로 이루어진 모든 부분수열을 고려한다. 원소가 K개 이상인 각 부분수열마다 가장 작은 K개의 수의 곱을 적는다.
4. P를 이전 단계에서 적은 서로 다른 곱의 개수로 둔다.
5. 코드는 “N K P”이다.

Pesho가 수열 {4, 1, 3, 2}를 어떻게 암호화해야 하는지 보자:

1. 처음 4개의 소수는 2, 3, 5, 7이다. 초기 수열에서 그는

• 4를 네 번째 소수 7로 바꾼다;
• 1을 첫 번째 소수 2로 바꾼다;
• 3을 세 번째 소수 5로 바꾼다;
• 2를 두 번째 소수 3으로 바꾼다.

Pesho는 새 수열 {7, 2, 5, 3}을 얻는다.

1. 그는 무작위 수 K를 고른다. K=2라고 하자.
2. 모든 연속 부분수열은 다음과 같다:

{7}, {2}, {5}, {3}, {7, 2}, {2, 5}, {5, 3}, {7, 2, 5}, {2, 5, 3}, {7, 2, 5 ,3}

Pesho는 원소가 K=2개보다 적은 모든 부분수열을 제거하고, 나머지 각각에 대해 가장 작은 K=2개의 수의 곱을 계산한다.

• {7, 2} 2.7 = 14
• {2, 5} 2.5 = 10
• {5, 3} 3.5 = 15
• {7, 2, 5} 2.5 = 10
• {2, 5, 3} 2.3 = 6
• {7, 2, 5 ,3} 2.3 = 6

그는 수 {14, 10, 15, 10, 6, 6}을 적는다

1. 서로 다른 수는 {6, 10, 14, 15}로 네 개이므로 P = 4이다.
2. 코드는 “4 2 4”이다.

Pesho는 이 알고리즘이 자신이 기대한 것보다 훨씬 낫다는 것을 금방 알아냈다. 그는 코드를 항상 명확하게 복호화할 수 없다.

코드가 주어졌을 때 가능한 초기 수열의 개수를 구하는 프로그램 crypto를 작성하라. 답을 1 000 000 007로 나눈 나머지를 구한다.

첫째 줄에 양의 정수 N, K, P가 주어진다.

코드 “N K P”를 가지는 가능한 초기 수열의 개수를 출력한다. 답을 1 000 000 007로 나눈 나머지를 출력한다.

• 1 ≤ K ≤ N ≤ 400
• 1 ≤ P ≤ 1 000 000 000

예제 1

입력:

3 2 3

출력:

2

예제 2

입력:

4 2 4

출력:

12