Максимумы

시간 제한2초메모리 제한1024 MB

요약

1부터 n까지의 순열 중 정확히 k개의 극댓값(봉우리)을 갖는 순열의 개수를 239로 나눈 나머지를 구합니다. n은 10^15까지 커질 수 있습니다.

난이도: 어려움10점 중 8점
유형: 조합론, 동적 계획법, 정수론
정답자: 아직 제출이 없습니다

문제

Говорят, что перестановка $\langle a\_1, a\_2, \ldots, a\_n\rangle$ целых чисел от 1 до $n$ имеет $k$ максимумов, если неравенство $a\_{i-1} < a\_i > a\_{i+1}$ выполняется ровно для $k$ различных позиций $i$ (будем считать, что $a\_0=a\_{n+1}=0$ ).

Например, у перестановки $\langle 3, 1, 4, 5, 2 \rangle$ два максимума: $i = 1$ и $i = 4$ .

По заданным $n$ и $k$ найдите количество перестановок чисел от 1 до $n$ ровно с $k$ максимумами. Верните это число по модулю 239.

입력

Входной файл содержит два целых числа: $n$ и $k$ ( $1 \le n \le 10^{15}$ , $1 \le k \le 30$ ).

출력

Выведите одно целое число --- количество перестановок чисел от 1 до $n$ ровно с $k$ максимумами, взятое по модулю 239.

예제2

예제 1
입력
```
3 1
```
예상 출력
```
4
```
예제 2
입력
```
10 3
```
예상 출력
```
131
```