定義
$$ f(n, m) = \sum_{i = 0}^m\binom n i $$
ここで
$$ \binom{n}{i} = \frac{n!}{i!(n-i)!} $$
$l, r, m$ が与えられたとき、$l \le n \le r$ について $f(n, m)$ の値を計算してください。
答えは $P = 10^9 + 7$ で割った余りを出力してください。
入力
一行に3つの非負整数 $l, r, m$ が与えられる。$m \le l \le r$ であることが保証される。
出力
一行に $r - l + 1$ 個の整数を出力する。$i$ 番目の整数は $f(l + i - 1, m)$ の値を表す。
入出力例
入力 1
10 20 10
出力 1
1024 2047 4083 8100 15914 30827 58651 109294 199140 354522 616666
注記 1
このサンプルケースのデータ範囲は第 8 テストケースと同じである。
小課題
$100\%$ のデータに対して、$l, r, m \le 3\times 10^5$ を満たす。
| テストケース | $m,l,r$ | 特殊な制約 |
|---|---|---|
| $1$ | $\leq 1$ | A |
| $2,3,4$ | $\leq 100$ | A |
| $5,6$ | $\leq 2000$ | B |
| $7$ | $\leq 3\times 10^5$ | B |
| $8,9$ | $\leq 2000$ | |
| $10$ | $\leq 3\times 10^5$ |
性質 A：$m=l=r$ を満たす
性質 B：$l=r$ を満たす