#P16477. [NEERC2005Western]Increasing Subsequences递增子序列

[NEERC2005Western]Increasing Subsequences递增子序列

题目描述

一个由 1,2,…,N1,2,\ldots,N 组成的序列

p(1),p(2),…,p(N)p(1),p(2),\ldots,p(N)

称为一个排列,当且仅当序列中的所有元素两两不同。

如果存在下标

1≤i1<i2<⋯<ik≤N,1\le i_1<i_2<\cdots<i_k\le N,

并且满足

p(i1)<p(i2)<⋯<p(ik),p(i_1)<p(i_2)<\cdots<p(i_k),

则称排列 pp 包含一个长度为 kk 的递增子序列。

若排列 pp 中存在长度为 BB 的递增子序列,但不存在长度为 B+1B+1 的递增子序列,则称这个排列的递增度为 BB。换句话说,排列的递增度就是其最长递增子序列的长度。

给定 NN 和 BB,求递增度恰好为 BB 的排列数量。

由于答案可能很大,请输出答案对 1 000 000 0001\,000\,000\,000 取模后的结果。

输入格式

一行包含两个整数 NN 和 BB。

输出格式

输出一个整数,表示递增度恰好为 BB 的排列数量对 1 000 000 0001\,000\,000\,000 取模后的结果。

数据范围

1≤N≤40,1\le N\le 40, 1≤B≤5.1\le B\le 5.

样例

输入

3 2

输出

4

难度参考:CF 2400。