Now the scientist wants you to count the number of ways each student can pick a candy,  but this time he ordered the candies by deliciousness decreasingly.

The candies are sorted by deliciousness decreasingly. The candies from $1$ till $k$ have deliciousness of $10^{18}$, the candies from $k + 1$ till $2*k$ have deliciousness of $10^{18} - 1$, the candies from $2*k + 1$ till $3*k$ have deliciousness of $10^{18} - 2$ ,..... the candies from $x*k + 1$ till $n$ have deliciousness of $10^{18} - x$.

Each student $i$ chooses one candy from the candies that lie in the range $[max(1,i - e),min(n,i + e)]$,borders included.

Going from left to right, each student will pick the candy with the highest deliciousness if there are multiple ones with the same value the student picks any candy.

When a student picks a candy it disappears and its place becomes empty.

The scientist needs to know the number of ways each student can pick a candy such that each student takes exactly one candy.

You need to answer $q$ queries.

All queries have the same value of k while only the value of n changes per query.

print the answer for each query $\mod 10^9 + 7$. 

The first line of the input is made up of $3$ integers $k,e,q(1\leq k\leq10^{18},1\leq e\leq4,1\leq q\leq2000)$, the size of a single group of candies, the value that defines the range the student can see, and the number of queries, respectively.

The next $q$ lines each contain a single integer $n(1\leq n \leq 10^{18})$ the number of students and candies in the query. 

Output $q$ lines.

The integer in $i_{th}$ line represents the answer for the $i_{th}$ query.