LittleElephantAndPermutationDiv2

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. Return 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.)

Definition

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

Constraints

N will be between 1 and 10, inclusive.
K will be between 1 and 100, 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
```
When A = (1,2,3), there are 3 possibilities for B: (2,3,1), (3,1,2) and (3,2,1). For each of the other 5 values of A, it can be shown that there are 3 possibilities for B as well. Therefore the answer is 3*6 = 18.
```
10
```
```
47
```
```
Returns: 13168189440000
```

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.