4475 - [Jsoi2015]子集选取

给定 nnn 个元素的集合 S={ 1,2...n}S= \left{ \ 1,2...n \right}S={ 1,2...n} 和整数k kk，现在要从SSS 中选出若干子集 Ai,jA{i,j}Ai,j​（A⊆SA \subseteq SA⊆S，1≤j≤i≤k1 \le j \le i \le k1≤j≤i≤k）排成下面所示边长为 kkk 的三角形（因此总共选出了 12k(k+1)\frac{1}{2} k(k+1)21​k(k+1) 个子集）。 A1,1A2,1A2,2A3,1A3,2A3,3⋮⋮⋮⋱Ak,1Ak,2Ak,3⋯Ak,k\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} A1,1​A2,1​A3,1​⋮Ak,1​​A2,2​A3,2​⋮Ak,2​​A3,3​⋮Ak,3​​⋱⋯​Ak,k​​

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

对于两种选取方案 A={ A1,1,A2,1,Ak,k}A = \left{ \ A{1,1} , A{2,1} , A{k,k} \right}A={ A1,1​,A2,1​,Ak,k​} 和 B={ B1,1,B2,1,Bk,k}B = \left{ \ B{1,1} , B{2,1} , B{k,k} \right}B={ B1,1​,B2,1​,Bk,k​} 只要存在 i,ji,ji,j 满足 Ai,j≠Bi,jA{i,j} \neq B{i,j}Ai,j​=Bi,j​，我们就认为 AAA 和 BBB 是不同的方案。

输入包含一行两个整数N和K，1<=N,K<=10^9

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