与（and）

给定 $n,k$ ，一个长度为 $k$ 的序列 $a$ 合法当且仅当：

• $\sum a_i=n$。
• 任意 $1\le i<k$， $a_i\text{ AND }a_{i+1}=a_{i+1}$ 。

求合法序列个数。对 $10^9+7$ 。

考虑拆位贡献，则对于某一个二进制位，设 $A_i$ 为 $i$ 的这个二进制位，则必然存在一个 $j$ 使得 $i\in[1,j]$ 满足 $A_i=1$ 且其余为 $0$ 。因此只要 $\sum A_i$ 确定了，则这一二进制位的所有数均确定。

不妨设 $b_i$ 表示第 $i$ 个二进制位的 $1$ 的个数，则限制变为：

$$\sum2^ib_i=n(b_i\le k)$$

这是一个多重背包问题，看似是 $\mathcal{O}(n^2\log n)$ 的复杂度，但是注意到复杂度是：

$$\begin{aligned} \sum n\lfloor\frac{n}{2^i}\rfloor&=n\sum \lfloor\frac{n}{2^i}\rfloor\\&=\mathcal{O}(n^2) \end{aligned}$$

于是直接写一个多重背包就能通过。