Maxima

Time limit2sMemory limit1024 MB

Summary

Count permutations of 1 to n with exactly k maxima, where n is up to 10^15 and the answer is taken modulo 239.

Level: Hard8 of 10
Topics: Combinatorics, Matrix, Dynamic programming
Solved: No attempts yet

Problem

A permutation $\langle a\_1, a\_2, \ldots, a\_n\rangle$ of the integers from 1 to $n$ is said to have $k$ maxima if the inequality $a\_{i-1} < a\_i > a\_{i+1}$ holds for exactly $k$ positions $i$ . Here $a\_0 = a\_{n+1} = 0$ .

For example, the permutation $\langle 3, 1, 4, 5, 2 \rangle$ has two maxima: $i = 1$ and $i = 4$ .

Input

The input file contains two integers $n$ and $k$ ( $1 \le n \le 10^{15}$ , $1 \le k \le 30$ ).

Output

Print one integer: the number of permutations of the integers from 1 to $n$ with exactly $k$ maxima, taken modulo 239.

Examples2

Example 1
Input
```
3 1
```
Expected output
```
4
```
Example 2
Input
```
10 3
```
Expected output
```
131
```