思路

首先，我们可以对于每一个数单独考虑，因为数之间互不影响，所以最后答案为每一个数的答案的 $n$ 次幂。现在可以把问题转化为：在边长为 $k$ 的三角形内填 $0$ 或 $1$，要求如果一个位置为 $1$，它的左边和上面也必须为 $1$。求方案数。

按列考虑。对于一列，数的分布是前面若干个 $1$ 之后全都是 $0$，要不然不满足上面必须为 $1$ 的限制了。再考虑列与列直接的关系，对于当前列，最下面的 $1$ 必须在左边列最下面 $1$ 的上面或同一行。如下图所示：

这个图中被红色笔划掉的就是 $i$ 这一列不能放的。

所以，除了第一列，每一列的 $1$ 的个数都是严格小于上一列的。

又发现，这个三角形要么全都是 $1$，要么一定会在某一列上变成全 $0$，后面也都是 $0$ 了。

先不考虑全 $1$ 的情况。设变成全 $0$ 的列为第 $i$ 列。如果设第 $0$ 列有 $k+1$ 个 $1$，则这 $k+1$ 个 $1$ 会被减 $i$ 次（每一列严格小于上一列）。现在的问题变成了一个数减 $y$ 次变成 $0$ 的方案数。这个问题等价于一个数 $x$ 被有顺序地分解成 $y$ 个数的方案数。这相当于有 $x$ 个球，分隔 $y-1$ 次把它们变成 $y$ 组。这个的方案数是在 $x-1$ 个间隔中选 $y-1$ 个间隔作为分隔点，$C_{x-1}^{y-1}$。所以这一列全变成 $0$ 的方案数是 $C_{k+1-1}^{i-1}=C_k^{i-1}$。

把所有列变成 $0$ 的方案数都加起来再加上全 $1$ 的方案便是这个问题的方案：$C_{k}^0 + C_k^1 + \cdots + C_k^{k-1} +1=C_{k}^0 + C_k^1 + \cdots C_{k}^{k-1}+C_k^k=2^k$。（每个数都有选或不选的两种情况，一共有 $k$ 个数，所以方案数是 $2^k$）

这是一个数时的方案数。有 $n$ 个数，方案数就是 $2^k$ 的 $n$ 次方。

代码

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int qpow(int a,int b)
{
	a%=mod;
	int ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
signed main()
{
	int n,k;
	cin>>n>>k;
	cout<<qpow(qpow(2,k),n);
	return 0;
}