Problem Statement
You are given two
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).
2
2
Returns: 14
3
5
Returns: 21234
20
27
Returns: 88437461
Watch out for integer overflow.
50
50
Returns: 427946384
0
50
Returns: 77829876
50
1
Returns: 930402295
49
17
Returns: 986740599
25
25
Returns: 817855208
13
22
Returns: 258396166
34
39
Returns: 899558903
49
9
Returns: 597962015
15
37
Returns: 329517643
30
11
Returns: 37135753
46
39
Returns: 316806104
10
9
Returns: 278555994
0
37
Returns: 610952631
11
12
Returns: 318773240
11
42
Returns: 916998426
36
37
Returns: 749982167
20
26
Returns: 997672421
14
48
Returns: 444025966
24
33
Returns: 1025561
9
39
Returns: 45786149
21
46
Returns: 605052952
31
48
Returns: 391386112
13
29
Returns: 606458569
42
9
Returns: 375009981
12
16
Returns: 752997011
14
5
Returns: 804909504
46
50
Returns: 984930483
28
31
Returns: 673262318
13
3
Returns: 74516015
24
37
Returns: 895534910
11
20
Returns: 922263646
15
31
Returns: 110489376
49
21
Returns: 458636027
16
34
Returns: 487249080
43
44
Returns: 369811952
5
10
Returns: 166851858
24
33
Returns: 1025561
23
14
Returns: 196891069
18
37
Returns: 377740773
29
30
Returns: 329922048
33
17
Returns: 780587842
29
17
Returns: 638882845
8
36
Returns: 977378805
42
28
Returns: 175748333
28
36
Returns: 584381000
14
14
Returns: 603658263
50
20
Returns: 621479913
45
5
Returns: 727886904
21
22
Returns: 448902841
28
49
Returns: 638146078
26
14
Returns: 786050835
18
8
Returns: 550574287
8
34
Returns: 549985104
23
25
Returns: 13411071
50
37
Returns: 67128318
49
14
Returns: 42103866
5
2
Returns: 3720
34
22
Returns: 912252945
9
4
Returns: 536362852
14
10
Returns: 403920293
38
30
Returns: 408554922
40
19
Returns: 505776858
33
5
Returns: 445053785
19
28
Returns: 530873350
17
29
Returns: 679866230
12
46
Returns: 662526033
48
35
Returns: 963749168
46
16
Returns: 42613958
32
35
Returns: 540219593
36
5
Returns: 749691064
39
12
Returns: 411778963
29
44
Returns: 801226687
31
28
Returns: 927505571
42
50
Returns: 566689009
37
36
Returns: 17103005
26
45
Returns: 942769424
11
5
Returns: 285736828
43
24
Returns: 244411007
29
39
Returns: 340737674
23
18
Returns: 405744622
21
9
Returns: 868911045
20
35
Returns: 406482058
27
3
Returns: 711564780
13
16
Returns: 207162714
47
37
Returns: 449705363
36
29
Returns: 789199291
4
17
Returns: 342884667
19
31
Returns: 61788753
42
9
Returns: 375009981
30
32
Returns: 328934328
12
13
Returns: 190839933
45
48
Returns: 802599441
5
18
Returns: 9961204
49
14
Returns: 42103866
44
9
Returns: 98926489
39
41
Returns: 628516574
17
29
Returns: 679866230
18
40
Returns: 213526041
6
27
Returns: 264021687
37
32
Returns: 595865995
45
34
Returns: 42405906
28
30
Returns: 656659737
8
42
Returns: 584566549
49
28
Returns: 338823704
22
26
Returns: 268263153
37
37
Returns: 382151168
17
18
Returns: 900700485
39
45
Returns: 899439350
41
23
Returns: 186678214
37
9
Returns: 802141913
50
19
Returns: 673964288
32
29
Returns: 481577493
12
14
Returns: 179380061
49
48
Returns: 26448153
50
25
Returns: 225531341
33
45
Returns: 180049669
34
1
Returns: 71258146