Analysis

以下令 $N,M$ 表示题目中的 $w,h$。

Solution 1

考虑只有一排，不考虑是否锁死的情况，那么 $n$ 列的方案数可以通过 dp 直接计算得出，即：$f_n=f_{n-1}+f_{n-2}$。因为有 $M$ 的高度，故还要进行 $M$ 次幂。

这样，我们就计算得出了 $f_n$ 表示高度为 $m$，有 $n$ 列且不考虑锁死的方案数。

接下来令 $g_n$ 表示高度为 $m$，有 $n$ 列且考虑锁死的方案数。枚举最后一个能锁死的块的宽度为 $i$，不难发现有：

$$g_n=f_n-\sum_{i=1}^{n-1}f_{n-i}g_i$$

把 $f$ 与 $g$ 看做多项式 $F,G$，不难发现有 $G=F-F\times G$，化简有 $G=\dfrac{F}{F+1}$，直接用多项式求逆即可在 $O(n\log m+n\log n)$ 的复杂度内完成（所以数据范围不用限制 $m$）。

但是问题在于模数是 $10^9+7$，需要 MTT，常数很大，因此考虑其他做法。

Solution 2

如果暴力按照 Solution 1 的做法进行 dp，复杂度是 $O(n^2)$ 的，由于有 $n\times m\le 5\times 10^5$ 的限制，考虑用 $m$ 更高的复杂度平衡。

令 $f_{n,m}$ 表示考虑前 $n$ 列，且最后一列有 $m$ 个 $1\times 2$ 的积木向后突出的方案数。因此得出转移：

$$f_{n,m}=\sum_{i=1}^{M-1}\binom{M-i}{m}\times f_{n-1,i}$$

答案即是 $\sum f_{N-1,i}$。不难发现由于每个转移的 $m\not=0,m\not=M$，所以积木一定是锁死的。

这样 dp 的复杂度是 $O(nm^2)$ 的。

将两种 dp 的方法进行平衡：$n\le m^2$ 时，采用 $O(n^2)$ 的 dp，$n>m^2$ 时，采用 $O(nm^2)$ 的 d。

平衡后的复杂度为 $O((n\times m)^{4/3})$，可以轻松通过。

Code

const int N = 250010;

int n, m;
Z f[N], g[N], h[N], fac[N], ivf[N];

Z binom(int x, int y) {
  if (x < 0 || y < 0 || x < y) return 0;
  return fac[x] * ivf[y] * ivf[x - y];
}

int main() {
  n = read(), m = read();
  if (n <= 1ll * m * m) {
    f[0] = 1, f[1] = 1, g[0] = 1;
    rep (i, 2, n) f[i] = f[i - 1] + f[i - 2];
    rep (i, 1, n) f[i] = f[i].pow(m);
    rep (i, 1, n) {
      rep (j, 1, i - 1) h[i] += f[j] * g[i - j];
      g[i] = f[i] - h[i];
    }
    write(g[n].val());
  } else {
    fac[0] = 1;
    rep (i, 1, m) fac[i] = fac[i - 1] * i;
    ivf[m] = fac[m].inv();
    per (i, m, 1) ivf[i - 1] = ivf[i] * i;
    rep (i, 1, m) f[i] = binom(m, i);
    rep (i, 2, n - 1) {
      rep (j, 1, m - 1) rep (k, 1, m - j) g[k] += f[j] * binom(m - j, k);
      rep (j, 0, m) f[j] = g[j], g[j] = 0;
    }
    Z ans = 0;
    rep (i, 1, m) ans += f[i];
    write(ans.val());
  }
}