UpDownNess | Topcoder Archive

Problem Statement

Given a permutation P, a lo-hi-lo triple is any triple (i,j,k) of valid indices into P such that i < j < k and P[i] < P[j] > P[k]. Note that there is no requirement on the comparison between P[i] and P[k].

You are given the ints N and K. Among all N! permutations of the numbers 1 through N, consider those that contain exactly K lo-hi-lo triples. Let X be the number of such permutations. Compute and return the value (X modulo 1,000,000,007).

Definition

Class:: UpDownNess
Method:: count
Parameters:: int, int
Returns:: int
Method signature:: int count(int N, int K)
(be sure your method is public)

Constraints

N is between 1 and 50, inclusive.
K is between 0 and 5000, inclusive.

Examples

```
3
```
```
1
```
```
Returns: 2
```
{1,3,2} and {2,3,1} meet the condition.
```
3
```
```
0
```
```
Returns: 4
```
{1,2,3},{2,1,3},{3,1,2} and {3,2,1} meet the conditon.
```
4
```
```
3
```
```
Returns: 4
```
Here, the four good permutations are {1,3,4,2}, {1,4,3,2}, {2,3,4,1}, and {2,4,3,1}. For the permutation P={1,3,4,2} the three lo-hi-lo triples of indices are the following ones: (0,1,3), because we have 1 < 3 > 2. (0,2,3), because we have 1 < 4 > 2. (1,2,3), because we have 3 < 4 > 2. (Note that all the indices used above are 0-based: P[0]=1, P[1]=3, P[2]=4, and P[3]=2.)
```
19
```
```
19
```
```
Returns: 24969216
```
```
50
```
```
2000
```
```
Returns: 116596757
```

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.