March Break Contest '22 Problem 5 - Good Arrays

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M
PyPy 2 128M
PyPy 3 128M

Problem type

We define a good array as an array of length N with all elements ranging from 1 to K inclusive, the first element of the array is equal to 1, and the last element of the array is equal to X, and consecutive elements must be different from each other.

Given N, K, and X, how many good arrays can you form, mod 1000000007?

Input Specification

One line containing N, K, X, the constraints of a good array.

Subtask 1 [30%]

1 \leq K \leq N \leq 10^3

1 \leq X \leq K

Subtask 2 [70%]

1 \leq K \leq N \leq 10^5

1 \leq X \leq K

Output Specification

One integer, the number of good arrays that you can form, mod 1000000007.

Sample Input 1

4 3 2

Sample Output 1


Sample Explanation 1

The good arrays you can form are 1212, 1312 and 1232.

Sample Input 2

77 73 37

Sample Output 2



There are no comments at the moment.