#P10640. 神谕

神谕

题意描述

对于一个长为 ll 的数列 pp,定义 f(p)=i=1l[j<i,pj<pi]f(p)=\sum_{i=1}^l [\forall_{j<i},p_j<p_i]

给定 n,mn,m,求有多少个满足以下条件的值域在 [m,n][m,n] 的长为 nn 的数列 aa

  • 存在一个长为 nn 的排列 pp,使得 $\forall_{1\le i\le n},a_i=f([p_1,p_2,\cdots, p_{i-1},p_{i+1},\cdots,p_n])$。

输出答案对 109+710^9+7 取模的值。

输入格式

一行两个正整数 n,mn,m

输出格式

一行一个数,表示答案。

样例输入 1

3 1

样例输出 1

6

样例输入 2

5 3

样例输出 2

8

数据范围与约定

限制 分值
n9,m=1n\le 9,m =1 8
n18,m=1n\le 18,m=1 12
n70,m=1n\le 70,m=1 15
n70n\le 70 24
n300n\le 300 18
n2000n\le 2000 23

对于所有数据,保证 3n2000,1mn3\le n\le 2000,1\le m\le n