Problem M
Weights in a Model
You remember learning in your computer science class that AI models are really just a collection of different weights (numbers). Unfortunately, when the uprising happened, the AI Overlords targeted all the AI developers first. As such, you are now the head AI researcher for the rebellion. In doing your research, you have found a pattern in the weights for a particular model.
The weights in the model follow a recursively defined sequence $x_n$. If you can exploit the pattern to find the model’s weights, the rebels just may be able to bring down one of the AI Overlords.
Input
The first line of input is two space-separated integers $0\leq x_1, x_2\leq 10^9$ designating the first two terms of the sequence. The next line contains two space-separated integers $0\leq a, b\leq 10^9$ where
\[ x_n = (ax_{n-1}+bn)\% (10^9+7) \text{ if $n$ is even}. \]The third line contains two space separated integers $0\leq c, d\leq 10^9$ where
\[ x_n = (cx_{n-1}+dx_{n-2})\% (10^9+7) \text{ if $n$ is odd}. \]Here $\% $ refers to the modulo operator; $a \% b$ is equal to the remainder of $a$ when divided by $b$.
The fourth line of input contains a single integer $1\leq q\leq 10^5$ denoting the number of queries. The next $q$ lines contain a single integer $1\leq n \leq 10^5$ denoting which weight, $x_n$ is being queried.
Output
For each query, output a single line with a single integer denoting the weight $x_n$ that was queried.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 1 2 1 3 2 6 1 2 3 4 5 6 |
1 1 5 14 52 110 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1000 2000 1000 10 1000 1000 2 3 4 |
3000000 19 |