수열의 비밀 (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 자료형을 사용하는 것을 추천한다.