Problem Statement
You are given the
- The length of the array is exactly N.
- Each element in the array is an integer between 1 and N, inclusive.
- Each number occurs in the array at most K times.
- Choose two distinct integers x and y, each between 1 and N, inclusive.
- Change the values of some elements of A: All elements of A that had the value x will now have the value y and vice versa.
- Finally, swap two elements of A: the elements with the 1-based indices x and y.
- We choose x=1 and y=3.
- After changing the values in A, we have the array [3,1,1,4].
- Then, after the swap we have the final result: the array [1,1,3,4].
Note that if we morph an array that belongs into S, the result will always belong into S as well.
We are interested in a subset T of S with the property that any array in S can be produced from some array in T by a sequence of zero or more morphing operations. Find the smallest possible size of such subset T, and return its size modulo 1,000,000,007.
Definition
- Class:
- Morphling
- Method:
- findsz
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int findsz(int N, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 100, inclusive.
- K will be between 1 and min(25, N), inclusive.
Examples
1
1
Returns: 1
The only valid array is [1]. The subset T must contain this array.
2
1
Returns: 2
There are two arrays in S: [1,2] and [2,1]. The morphing operation always changes [1,2] into [1,2] and it always changes [2,1] into [2,1]. Therefore we need to include both arrays into T.
2
2
Returns: 3
There are four arrays in S: [1,2], [2,1], [1,1], [2,2]. The morphing operation allows to transform [1,1] to [2,2], so only one of this should be included into T.
3
1
Returns: 3
3
3
Returns: 7
Here the set S contains 27 different arrays. Some of these arrays can be produced from other arrays by morphing. The smallest possible subset T with the required property consists of only 7 of these arrays.
10
1
Returns: 42
48
18
Returns: 270440792
100
25
Returns: 796177038
9
9
Returns: 2615
95
19
Returns: 945044826
50
3
Returns: 606683264
69
14
Returns: 15602052
71
25
Returns: 805176177
93
22
Returns: 295332237
37
22
Returns: 387457839
96
1
Returns: 118114304
14
14
Returns: 466199
30
3
Returns: 338273764
17
17
Returns: 10884049
11
5
Returns: 19837
90
15
Returns: 498270418
75
23
Returns: 766316916
1
1
Returns: 1
12
12
Returns: 57903
40
6
Returns: 724747205
11
11
Returns: 20491
97
14
Returns: 236897474
4
4
Returns: 19
95
15
Returns: 247412499
86
25
Returns: 841853953
86
2
Returns: 848983346
8
8
Returns: 951
25
10
Returns: 58550894
17
12
Returns: 10883852
53
3
Returns: 854458216
66
1
Returns: 2323520
22
18
Returns: 152118235
3
3
Returns: 7
78
22
Returns: 605442915
35
2
Returns: 841115074
34
2
Returns: 666881155
84
2
Returns: 583498129
55
24
Returns: 63557441
75
2
Returns: 292701596
58
14
Returns: 554381834
83
24
Returns: 463595731
20
1
Returns: 627
36
24
Returns: 568758458
34
11
Returns: 634519705
20
20
Returns: 258604642
83
24
Returns: 463595731
66
19
Returns: 213563016
55
15
Returns: 971709733
22
3
Returns: 860857296
60
4
Returns: 371770711
47
24
Returns: 896415504
30
19
Returns: 682628691
26
21
Returns: 899222021
97
4
Returns: 128772105
18
18
Returns: 31241170
95
22
Returns: 192964570
96
21
Returns: 257314950
72
12
Returns: 664849350
99
17
Returns: 713749590
39
3
Returns: 445226026
100
20
Returns: 818963941
54
23
Returns: 21970194
98
22
Returns: 894664887
67
4
Returns: 444328226
97
2
Returns: 395147803
91
25
Returns: 800797358
100
19
Returns: 423633321
51
21
Returns: 493477511
100
2
Returns: 378017182
37
19
Returns: 840710360
99
2
Returns: 136563450
2
2
Returns: 3
98
1
Returns: 150198136
14
14
Returns: 466199
100
18
Returns: 262026393
64
24
Returns: 270928094
97
21
Returns: 936421701
100
23
Returns: 469719472
99
4
Returns: 224806980
18
18
Returns: 31241170
96
4
Returns: 92260582
100
1
Returns: 190569292
87
1
Returns: 38887673
100
3
Returns: 506241817
99
1
Returns: 169229875
98
2
Returns: 303096421
96
23
Returns: 823306570
25
25
Returns: 78308836