「JSOI2015」子集选取
看到这个数据范围，就知道肯定是要找规律。
如果把集合看成一个长度为 (n) 的 (01) 串， (0) 表示没有这个元素， (1) 表示有这个元素，
那么我们可以发现对于题中的约束关系，不同位上的 (01) 之间不会互相影响。
那么我们只需要对于只有一位也就是 (n = 1) 的情况计算出方案（记为 (x)）那么最后的答案就是 (x ^ n) 。
现在考虑如何计算 (x) 。
根据题目的限制，不难发现每一行都是一个全是 (1) 的前缀，而且第 (i - 1) 行的前缀要比第 (i) 行的不短。
那么我们设 (f_{i, j}) 表示选到第 (i) 行其中第 (i) 行选了一个长度为 (j) 的前缀的方案。
转移很简单：
[f_{i, j} = sumlimits_{k = j}^{i - 1} f_{i - 1, k}
]
不难发现这个东西和杨辉三角有点像。
因为在杨辉三角中，一个数等于它右上方那个数往左上方的前缀的和。
所以我们可以进一步发现 (f_{i, j} = f_{i, j + 1} + f_{i - 1, j})
那么和杨辉三角类似的，第 (k) 行的和也就是 (sum_{j = 1}^k f_{k, j} = 2^k - 1)
然后再加上全是零的一种情况总共就是 (2^k) 种方案。
综上所述，最后的答案就是 (2^{nk}) 。
参考代码：
#include <cstdio>
#define rg register
#define int long long
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template < class T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while ('0' > c || c > '9') f |= c == '-', c = getchar();
while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
s = f ? -s : s;
}
const int p = 1e9 + 7;
int n, k;
inline int power(int x, int k) {
int res = 1;
for (; k; k >>= 1, x = 1ll * x * x % p)
if (k & 1) res = 1ll * res * x % p;
return res % p;
}
signed main() {
#ifndef ONLINE_JUDGE
file("cpp");
#endif
read(n), read(k);
printf("%lld
", power(2, 1ll * n * k));
return 0;
}