#P6075. [JSOI2015] 子集选取

[JSOI2015] 子集选取

题目描述

给定 nn 个元素的集合 S={1,2,,n}S= \left\{1,2,\cdots,n \right\} 和整数 k k,现在要从 SS 中选出若干子集 Ai,j (ASA_{i,j}\ (A \subseteq S1jik)1 \le j \le i \le k) 排成下面所示边长为 kk 的三角形(因此总共选出了 12k(k+1)\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 对选出的子集之间还有额外的要求:选出的这些子集必须满足 Ai,jAi,j1A_{i,j} \subseteq A_{i,j-1}Ai,jAi1,jA_{i,j} \subseteq A_{i-1,j}
JYY 想知道,求有多少种不同的选取这些子集的方法。因为答案很大,JYY 只关心输出答案模 1,000,000,0071{,}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,ji,j 满足 Ai,jBi,jA_{i,j} \neq B_{i,j},我们就认为 AABB 是不同的方案。

输入格式

输入包含一行两个整数 nnkk

输出格式

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

2 2
16

提示

对于 100%100\% 的数据,1n1 \le nk109k \le 10^9