n integers, each between 1 and m. Scan it from left to right and mark the **records**: elements strictly greater than every element before them. The first element is always a record.
For example, the array [2, 1, 3, 3, 5] has three records: 2, 3 (the first 3) and 5.
Count the arrays of length n with values from 1 to m that have exactly k records. The answer can be large, so return it modulo 10⁹ + 7.n=3, m=2, k=2 → 3
The arrays [1, 2, 1], [1, 2, 2] and [1, 1, 2] work: in each one the records are the first element and the first 2.
n=2, m=4, k=1 → 10
The second element must not exceed the first: 1 + 2 + 3 + 4 = 10 arrays.
n=4, m=3, k=4 → 0
Four records need four strictly increasing values, and only three are available.
n ≤ 50m ≤ 100k ≤ nn=3, m=2, k=2
3
Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.