Определим
$$ f(n, m) = \sum_{i = 0}^m\binom n i $$
где
$$ \binom{n}{i} = \frac{n!}{i!(n-i)!} $$
Даны $l, r, m$. Для каждого $n$ в диапазоне $l \le n \le r$ вычислите значение $f(n, m)$.
Ответ выведите по модулю $P = 10^9 + 7$.
Входные данные
В одной строке заданы три неотрицательных целых числа $l, r, m$, при этом гарантируется, что $m \le l \le r$.
Выходные данные
Выведите в одну строку $r - l + 1$ целое число, где $i$-е число представляет собой значение $f(l + i - 1, m)$.
Примеры
Пример 1
Входные данные
10 20 10
Выходные данные
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$