3178: 子集选取 [subset]（day1 -1）
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
【故事背景】
集合是计算机科学中非常基础的概念。一个大集合的所有子集和这些子集之间的包含关系能构成偏序（下图是 4 元素集合子集包含关系的Hasse Diagram）。但这并不是展示集合的唯一方式。
JYY 这次打算把子集排成其他形状。很快，JYY发现排列字集的方式千变万化，所以邀请你写一个程序帮他计算排列方案的总数。
【问题描述】
给定n个元素的集合S= {1,2,…n}和整数k，现在要从s中选出若干子集Ai,j（Ai,j⊆ S，1 ≤ j ≤ i ≤ k）排成下图所示边长为k的三角形（因此总共选出了k(k+1)/2 个子集）：
此外，JYY 对选出的子集之间还有额外的要求：选出的这些子集必须满足Ai,j⊆Ai,j-1且Ai,j⊆Ai-1,j。JYY 想知道，求有多少种不同的选取这些子集的方法。因为答案很大，JYY 只关心输出答案模1,000,000,007的值。
对于两种选取方案A = {A1,1,A2,1 ,…,Ak,k }和B = {B 1,1 ,B2,1,…,Bk,k}。只要存在i,j满足Ai,j ≠Bi,j ，我们就认为A和B是不同的方案。
集合是计算机科学中非常基础的概念。一个大集合的所有子集和这些子集之间的包含关系能构成偏序（下图是 4 元素集合子集包含关系的Hasse Diagram）。但这并不是展示集合的唯一方式。
JYY 这次打算把子集排成其他形状。很快，JYY发现排列字集的方式千变万化，所以邀请你写一个程序帮他计算排列方案的总数。
【问题描述】
给定n个元素的集合S= {1,2,…n}和整数k，现在要从s中选出若干子集Ai,j（Ai,j⊆ S，1 ≤ j ≤ i ≤ k）排成下图所示边长为k的三角形（因此总共选出了k(k+1)/2 个子集）：
此外，JYY 对选出的子集之间还有额外的要求：选出的这些子集必须满足Ai,j⊆Ai,j-1且Ai,j⊆Ai-1,j。JYY 想知道，求有多少种不同的选取这些子集的方法。因为答案很大，JYY 只关心输出答案模1,000,000,007的值。
对于两种选取方案A = {A1,1,A2,1 ,…,Ak,k }和B = {B 1,1 ,B2,1,…,Bk,k}。只要存在i,j满足Ai,j ≠Bi,j ，我们就认为A和B是不同的方案。
Input
输入包含一行两个整数n和k。
Output
一行一个整数，表示不同方案数目模1,000,000,007的值。
Sample Input Copy
2 2
Sample Output Copy
16
HINT
【数据规模与约定】
对于 30%的数据满足1 ≤ n,k ≤ 10；
对于 60%的数据满足1 ≤ n ≤ 10^9，1 ≤ k ≤ 10；
对于 100%的数据满足1 ≤ n,k ≤ 10^9。
对于 30%的数据满足1 ≤ n,k ≤ 10；
对于 60%的数据满足1 ≤ n ≤ 10^9，1 ≤ k ≤ 10；
对于 100%的数据满足1 ≤ n,k ≤ 10^9。