LittleElephantAndPermutationDiv1

Problem Statement

This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

Little Elephant from the Zoo of Lviv likes permutations. A permutation of size N is a sequence (a₁, ..., a_N) that contains each of the numbers from 1 to N exactly once. For example, (3,1,4,5,2) is a permutation of size 5.

Given two permutations A = (a₁, ..., a_N) and B = (b₁, ..., b_N), the value magic(A,B) is defined as follows: magic(A,B) = max(a₁,b₁) + max(a₂,b₂) + ... + max(a_N,b_N).

You are given the int N. You are also given another int K. Let X be the number of pairs (A,B) such that both A and B are permutations of size N, and magic(A,B) is greater than or equal to K. (Note that A and B are not required to be distinct.) Return the value (X modulo 1,000,000,007).

Definition

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

Constraints

N will be between 1 and 50, inclusive.
K will be between 1 and 2500, inclusive.

Examples

```
1
```
```
1
```
```
Returns: 1
```
For N=1 the only pair of permutations is ( (1), (1) ). The magic of this pair of permutations is 1, so we count it.
```
2
```
```
1
```
```
Returns: 4
```
Now there are four possible pairs of permutations. They are shown below, along with their magic value. magic( (1,2), (1,2) ) = 1+2 = 3 magic( (1,2), (2,1) ) = 2+2 = 4 magic( (2,1), (1,2) ) = 2+2 = 4 magic( (2,1), (2,1) ) = 2+1 = 3 In all four cases the magic value is greater than or equal to K.
```
3
```
```
8
```
```
Returns: 18
```
```
10
```
```
74
```
```
Returns: 484682624
```
```
50
```
```
1000
```
```
Returns: 539792695
```

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.