bzoj#P4475. [Jsoi2015] 子集选取

[Jsoi2015] 子集选取

题目描述

给定 nn 个元素的集合 S={ 1,2...n}S= \left\{ \ 1,2...n \right\} 和整数k k,现在要从SS 中选出若干子集 Ai,jA_{i,j}ASA \subseteq S1jik1 \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 只关心输出答案模 109+710^9+7 的值。

对于两种选取方案 A={ A1,1,A2,1,Ak,k}A = \left\{ \ A_{1,1} , A_{2,1} , A_{k,k} \right\}B={ B1,1,B2,1,Bk,k}B = \left\{ \ B_{1,1} , B_{2,1} , B_{k,k} \right\} 只要存在 i,ji,j 满足 Ai,jBi,jA_{i,j} \neq B_{i,j},我们就认为 AABB 是不同的方案。

输入格式

输入包含一行两个整数 nnkk

输出格式

一行一个整数,表示不同方案数目模 109+710^9+7 的值。

2 2


16

数据规模与约定

对于 100%100\% 的数据,1n,k1091\le n,k\le 10^9