No.389

$H_1 = 0$ のときは $1$ 通りである.

$\sum H_k + k - 1 \gt M$ のときは NA である.

その他の場合は, 詰めて塗った場合の余りの空白の数 $N = M - \sum H_k - (k-1)$ を左右の端かヒントの間の $k+1$ 個の非負整数に分割する組み合わせの数となる.

これは, $N$ 個の玉と $k$ 個の仕切りを順番に並べる組み合わせの数と等しいので, ${}_{N+k}C_k$ を計算すればいい.

$10^9+7$ は素数なので割り算は逆元が使える.