子集选取

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

给定含有 $n$ 个元素的集合 $S=\{1,2,\ldots,n\}$ 和整数 $k$。现在要从 $S$ 中选出若干子集 $A_{i,j}$（$A_{i,j}\subseteq S$，$1\le j\le i\le k$），并将它们排成如下所示、边长为 $k$ 的三角形。因此一共选出了 $\frac{1}{2}k(k+1)$ 个子集。

$$\begin{matrix} A_{1,1}\\ A_{2,1}&A_{2,2}\\ A_{3,1}&A_{3,2}&A_{3,3}\\ \vdots&\vdots&\vdots&\ddots\\ A_{k,1}&A_{k,2}&A_{k,3}&\cdots&A_{k,k} \end{matrix}$$

选出的这些子集还必须满足下列包含关系（仅当等式右侧的相邻下标存在时要求）：

$$A_{i,j}\subseteq A_{i,j-1},\qquad A_{i,j}\subseteq A_{i-1,j}.$$

求有多少种不同的子集选取方案。答案很大，请输出答案对 $1{,}000{,}000{,}007$ 取模后的值。

对于两种选取方案 $A=\{A_{1,1},A_{2,1},\ldots,A_{k,k}\}$ 和 $B=\{B_{1,1},B_{2,1},\ldots,B_{k,k}\}$，只要存在一对 $i,j$ 满足 $A_{i,j}\ne B_{i,j}$，就认为它们是不同的方案。

输入格式

输入一行，包含两个整数 $n,k$。

输出格式

输出一行一个整数，表示不同方案数对 $1{,}000{,}000{,}007$ 取模后的值。

样例输入 1

2 2

样例输出 1

16

数据范围

对于全部数据，保证 $1\le n,k\le 10^9$。

子任务编号	分值	特殊限制
1	20	$k\le 2000$
2	40	$k\le 10^7$
3		无特殊限制

上述两条非满分限制是本次 OI 改编合成的规模约束。