GreaterThanAll | Topcoder Archive

Problem Statement

Given a sequence A = (a₁, a₂, ..., a_n) (where a[i] >= 1 are integers), of length n, we define the Peak_Set as
Peak_Set(A) = { a[i] : a[i] > a[j] for all j < i }

For example, for the sequence A = {2, 1, 5, 6, 3, 3, 2, 8, 10, 4}, Peak_Set(A) = {2, 5, 6, 8, 10}.

For a given integers N and K, you need to count the number of Sequences 'X' of length N with Peak_Set(X) = {1, 2, 3,..., K}, modulo (10⁹ + 7).

Definition

Class:: GreaterThanAll
Method:: count
Parameters:: int, int
Returns:: int
Method signature:: int count(int n, int k)
(be sure your method is public)

Constraints

The number of elements of the sequence, N ranges from 1 to 106, inclusive.
The value of K is between 1 and N.

Examples

```
3
```
```
2
```
```
Returns: 3
```
The only possible sequences are "112", "121" and "122" whose Peak_Set is {1, 2}.
```
762476
```
```
157929
```
```
Returns: 441862509
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.