시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 0 0 0.000%

## 문제

Pesho is crypting a sequence of N numbers where each integer from 1 to N appears exactly once. He is using the following algorithm:

1. Replace each initial number X with the Xth prime number.
2. Choose a random positive integer K, not greater than N.
3. Consider all subsequences with consecutive elements. For each subsequence with at least K elements write down the product of the smallest K numbers.
4. Let P be the number of unique products written in the previous step.
5. The code is “N K P”.

Let us see how Pesho should crypt the sequence {4, 1, 3, 2}:

1. The first 4 prime numbers are 2, 3, 5 and 7. In the initial sequence he replaces
• 4 with the fourth prime number which is 7;
• 1 with the first prime number which is 2;
• 3 with the third prime number which is 5;
• 2 with the second prime number which is 3.

Pesho obtains the new sequence {7, 2, 5, 3}.

1. He chooses a random number K. Say K=2.
2. All contiguous subsequences are:

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

Pesho removes all subsequences with less than K=2 elements and for each of the rest he computes the product of the smallest K=2 elements.

• {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

He writes the numbers {14, 10, 15, 10, 6, 6}

1. There are four unique numbers {6, 10, 14, 15}, thus P = 4.
2. The code is “4 2 4”.

Pesho quickly figured out that the algorithm is much better than he expected. He cannot always decrypt the code unambiguously.

Write a program crypto, which given a code calculates the number of possible initial sequences. Find the answer modulo 1 000 000 007.

## 입력

The first line contains the positive integers N, K and P.

## 출력

Print the number of possible initial sequences with code “N K P”. Print the answer modulo 1 000 000 007.

## 제한

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

## 예제 입력 1

3 2 3


## 예제 출력 1

2


The sequences {1, 3, 2} and {2, 3, 1} will be crypted as “3 2 3”.

## 예제 입력 2

4 2 4


## 예제 출력 2

12


The sequences are {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 4, 2, 3}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 1, 3, 2}, {4, 2, 3, 1}.