This is a template problem.
Given $T$ queries, each described by $n, a, b, c, k_1, k_2$. For each query, calculate
$$ \sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2} $$
modulo $1000000007$.
Input
The first line contains an integer $T$.
The next $T$ lines each contain six integers $n, a, b, c, k_1, k_2$.
Output
Output $T$ lines, each containing the answer for the corresponding query.
Examples
Input 1
1
2 2 0 1 1 1Output 1
10Subtasks
For $100 \%$ of the data, $T = 1000, 1 \le n, a, b, c \le {10} ^ 9, 0 \le k_1 + k_2 \le 10$.
| Test Case | $n$ | $k_1, k_2$ |
|---|---|---|
| $10\%$ | $n \le 100000$ | No special restrictions |
| $20\%$ | No special restrictions | $k_1 = 0, k_2 = 1$ |
| $20\%$ | No special restrictions | $k_1 + k_2 \le 2$ |
| $50\%$ | No special restrictions | No special restrictions |