P6075 [JSOI2015] Subset Selection

Given a set $S = \left\{1,2,\cdots,n \right\}$ with $n$ elements and an integer $k$, we want to choose some subsets $A_{i,j}\ (A \subseteq S,\ 1 \le j \le i \le k)$ from $S$ and arrange them into a triangle with side length $k$ as shown below (so in total, $\frac{1}{2} k(k+1)$ subsets are chosen). $$\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} $$ In addition, JYY has extra requirements on the chosen subsets: these subsets must satisfy $A_{i,j} \subseteq A_{i,j-1}$ and $A_{i,j} \subseteq A_{i-1,j}$. JYY wants to know how many different ways there are to choose these subsets. Since the answer is very large, you only need to output the answer modulo $1{,}000{,}000{,}007$. For two selection plans $A = \left\{ A_{1,1} , A_{2,1} ,\cdots, A_{k,k} \right\}$ and $B = \left\{ B_{1,1} , B_{2,1} ,\cdots, B_{k,k} \right\}$, as long as there exists some $i,j$ such that $A_{i,j} \neq B_{i,j}$, we consider $A$ and $B$ to be different plans.

The input contains one line with two integers $n$ and $k$.

Output one line with one integer, representing the number of different plans modulo $1,000,000,007$.

For $100\%$ of the testdata, $1 \le n, k \le 10^9$. Translated by ChatGPT 5