De Prezer loves functions. He has invented a new function f named Troynacci .
f(1) and f(2) are given to you. If i > 2, f(i) = af(i - 2) + bf(i - 1) .
De Prezer also has got a sequence x1, x2, ..., xn .
De Prezer also loves query. So he gives you q queries. In each query, he gives you numbers l and r (l ≤ r) and for each i that l ≤ i ≤ r, you should increase xi by f(i - l + 1) .
At last, you should print the final sequence. Of course, members of sequence could be very large, so you should print them modulo 109 + 7 .
The first line of input contains two integers n and q.
The second line contains two integers f(1) and f(2) .
The third line of input contains two integers a and b .
The forth line of input contains n space separated integers x1, x2, ..., xn .
The next q lines, each line contains two integers l and r .
1 ≤ n, q ≤ 105
1 ≤ f(1), f(2), a, b ≤ 109
0 ≤ xi ≤ 109 (for each 1 ≤ i ≤ n)
Print the final sequence in a single line.
## Input
The first line of input contains two integers n and q.The second line contains two integers f(1) and f(2) .The third line of input contains two integers a and b .The forth line of input contains n space separated integers x1, x2, ..., xn .The next q lines, each line contains two integers l and r .1 ≤ n, q ≤ 1051 ≤ f(1), f(2), a, b ≤ 1090 ≤ xi ≤ 109 (for each 1 ≤ i ≤ n)
## Output
Print the final sequence in a single line.
[samples]
**Definitions**
Let $ s \in \{[, ]\}^* $ be a valid parentheses string representing a rooted forest, where each matching pair $[ \ ]$ corresponds to a node, and nested pairs represent ancestor-descendant relationships.
**Constraints**
1. $ 1 \leq |s| \leq 1000 $
2. $ s $ is a well-formed sequence of balanced brackets.
**Objective**
Compute the number of connected components in the forest, which equals the number of top-level (non-nested) bracket pairs in $ s $.
That is, count the number of times a matching pair $[ \ ]$ occurs at depth 0.
Equivalently:
Let $ d = 0 $.
Initialize $ \text{components} = 0 $.
For each character $ c $ in $ s $:
- If $ c = '[' $: increment $ d $. If $ d = 1 $, increment $ \text{components} $.
- If $ c = ']' $: decrement $ d $.
Output $ \text{components} $.