题目描述

给定 $n$ 个元素的集合 $S= \left\{1,2,\cdots,n \right\}$ 和整数 $k$，现在要从 $S$ 中选出若干子集 $A_{i,j}\ (A \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} $$

此外，JYY 对选出的子集之间还有额外的要求：选出的这些子集必须满足 $A_{i,j} \subseteq A_{i,j-1}$ 且 $A_{i,j} \subseteq A_{i-1,j}$。
JYY 想知道，求有多少种不同的选取这些子集的方法。因为答案很大，JYY 只关心输出答案模 $1{,}000{,}000{,}007$ 的值。

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

输入格式

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

输出格式

一行一个整数，表示不同方案数目模 $1,000,000,007$ 的值。

2 2

16

提示

对于 $100\%$ 的数据，$1 \le n$，$k \le 10^9$。