Translated Document to Fix
Define
$$ f(n, m) = \sum_{i = 0}^m\binom n i $$
where
$$ \binom{n}{i} = \frac{n!}{i!(n-i)!} $$
Given $l, r, m$, calculate the value of $f(n, m)$ for all $l \le n \le r$.
The answer should be taken modulo $P = 10^9 + 7$.
Input
A single line containing three non-negative integers $l, r, m$, with the guarantee that $m \le l \le r$.
Output
Output a single line containing $r - l + 1$ integers, where the $i$-th integer represents the value of $f(l + i - 1, m)$.
Examples
Input 1
10 20 10
Output 1
1024 2047 4083 8100 15914 30827 58651 109294 199140 354522 616666
Note 1
The data range for this sample is the same as the 8th test case.
Subtasks
For $100\%$ of the data, $l, r, m \le 3\times 10^5$.
| Test Case | $m,l,r$ | Special Constraints |
|---|---|---|
| $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$ |
Property A: Satisfies $m=l=r$
Property B: Satisfies $l=r$