给定 $n$ 个元素的集合 $S={1,2,...,n}$ 和整数 $k$，现在要从 $S$ 中选出若干子集 $A_{i,j}（A_{i,j}\subseteq S, 1 \le j \le i \le k）$排成下图所示边长为 $k$ 的三角形（因此总共选出了 $k(k+1)/2$ 个子集）：
$\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 只关心输出答案模 $1000000007$ 的值。
对于两种选取方案 $A={ A_{1,1},A_{2,1},\dots ,A_{k,k} }$ 和$B={ B_{1,1},B_{2,1},\dots ,B_{k,k}}$。只要存在 $i,j$ 满足 $A_{i,j} \ne B_{i,j}$，我们就认为 $A$ 和 $B$ 是不同的方案。
Comet OJ