Definiujemy
$$ f(n, m) = \sum_{i = 0}^m\binom n i $$
gdzie
$$ \binom{n}{i} = \frac{n!}{i!(n-i)!} $$
Dla danych $l, r, m$ oblicz wartości $f(n, m)$ dla wszystkich $l \le n \le r$.
Wynik należy podać modulo $P = 10^9 + 7$.
Wejście
W jednym wierszu znajdują się trzy nieujemne liczby całkowite $l, r, m$, przy czym spełniony jest warunek $m \le l \le r$.
Wyjście
Wypisz w jednym wierszu $r - l + 1$ liczb całkowitych, gdzie $i$-ta liczba oznacza wartość $f(l + i - 1, m)$.
Przykład
Przykład 1
Wejście
10 20 10
Wyjście
1024 2047 4083 8100 15914 30827 58651 109294 199140 354522 616666
Uwagi
Zakres danych w tym przykładzie jest zgodny z ósmym punktem testowym.
Podzadania
Dla $100\%$ danych $l, r, m \le 3\times 10^5$.
| Punkt testowy | $m,l,r$ | Specjalne ograniczenia |
|---|---|---|
| $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$ | .h=2 |
| $10$ | $\leq 3\times 10^5$ |
Własność A: spełnione $m=l=r$
Własność B: spełnione $l=r$