Secret of the Sequence (Hard)

There is a sequence $a\_1, a\_2, a\_3, \ldots, a\_n$ of length $n$ that satisfies the following conditions.

• $a\_{2i} = p \cdot a\_i + q$ $(2 \leq 2i \leq n)$
• $a\_{2i+1} = r \cdot a\_{i} + s$ $(3 \leq 2i+1 \leq n)$

Let $S\_n=a\_1+a\_2+\ldots +a\_{n}$. Print the remainder of $S\_n$ divided by ${10^9+7}$.

The first line contains a positive integer $k$. $(n=2^k-1)$

The second line contains positive integers $p,q,r,s$, separated by spaces.

The third line contains a positive integer $a\_1$.

Print the remainder of $S\_n$ divided by ${10^9 + 7}$ on the first line.

• $1\leq k\leq 50$
• $1\leq p,q,r,s\leq 100$
• $1\leq a\_1\leq 10$

Intermediate values can exceed the range of the C/C++ int type, so using long long is recommended.