수열의 비밀 (Hard)

다음 조건을 만족하는 길이가 $n$인 수열 $a\_1, a\_2, a\_3, \ldots, a\_n$이 있다.

• $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)$

$S\_n=a\_1+a\_2+\ldots +a\_{n}$으로 정의할 때 $S\_n$을 ${10^9+7}$로 나눈 나머지를 출력하라.

첫 번째 줄에 양의 정수 $k$가 주어진다. $(n=2^k-1)$

두 번째 줄에 양의 정수 $p,q,r,s$가 공백으로 구분되어 주어진다.

세 번째 줄에 양의 정수 $a\_1$이 주어진다.

첫 번째 줄에 $S\_n$을 ${10^9 + 7}$로 나눈 나머지를 출력한다.

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

연산 과정에서 C/C++의 int 범위를 넘을 수 있으므로 long long 자료형을 사용하는 것을 추천한다.