AvoidingPermutations | Topcoder Archive

Problem Statement

A permutation P of length N is called (2,0,1)-avoiding if there are no indices 0 <= i < j < k < N such that P[i] > P[k] > P[j].

Farmer Bob used to remember a (2,0,1)-avoiding permutation P. However, in an unfortunate accident with his combine, he lost most of his memory. Now, he only remembers its length N and first element P[0]=F. He tried to recover it, but quickly realized that there are many possible solutions.

You're given two ints N and F. Compute and return the number of (2,0,1)-avoiding permutations that farmer Bob could've remembered originally, modulo 1,000,000,007.

Definition

Class:: AvoidingPermutations
Method:: countPermutations
Parameters:: int, int
Returns:: int
Method signature:: int countPermutations(int N, int F)
(be sure your method is public)

Notes

A permutation of length N is a sequence of numbers 0 through N-1 such that each number appears in the sequence exactly once.

Constraints

N will be between 1 and 5,000, inclusive.
F will be between 0 and N-1, inclusive.

Examples

```
3
```
```
2
```
```
Returns: 1
```
The only permutations with given length and first element are (2,0,1) and (2,1,0). Out of them, only permutation (2,1,0) is (2,0,1)-avoiding.
```
4
```
```
2
```
```
Returns: 3
```
The permutations are (2,1,0,3),(2,1,3,0),(2,3,1,0).
```
4
```
```
3
```
```
Returns: 1
```
```
6
```
```
3
```
```
Returns: 14
```
```
3
```
```
0
```
```
Returns: 2
```
```
11
```
```
5
```
```
Returns: 1638
```
```
5000
```
```
500
```
```
Returns: 442656280
```
```
5000
```
```
4200
```
```
Returns: 16369253
```

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.