DerangementsDiv2 | Topcoder Archive

Problem Statement

You are given two ints: n and m.

Let D be the number of permutations of the set {1,2,...,n+m} such that the first m values are not fixed points of the permutation. Formally, we are interested in permutations p such that for each j between 1 and m, inclusive, we have p(j) != j.

Compute and return D modulo 1,000,000,007.

Definition

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

Constraints

n will be between 0 and 50, inclusive.
m will be between 1 and 50, inclusive.

Examples

```
0
```
```
2
```
```
Returns: 1
```
Here we are looking for permutations of {1, 2} such that p(1) != 1 and p(2) != 2. There is only one such permutation: the permutation (2, 1). In other words, the permutation p such that p(1) = 2 and p(2) = 1.
```
2
```
```
1
```
```
Returns: 4
```
Here we are counting permutations of {1, 2, 3} such that p(1) != 1. There are four such permutations: (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Here, (a, b, c) denotes a permutation p for which p(1) = a, p(2) = b, and p(3) = c.
```
1
```
```
2
```
```
Returns: 3
```
This time we want permutations of {1, 2, 3} such that p(1) != 1 and p(2) != 2. The three such permutations are (2, 1, 3), (2, 3, 1), and (3, 1, 2).
```
3
```
```
5
```
```
Returns: 21234
```
```
20
```
```
27
```
```
Returns: 88437461
```
Watch out for integer overflow.

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.