import copy
class matrix():
def __init__(self):
self.mod = 10**9+7
def multiplication(self,arr1,arr2):
'''
例
arr1
2 3 4 5
6 7 8 9
arr2
1 2
3 4
5 6
7 8
'''
H = len(arr1)
W = len(arr2[0])
arr3 = [[0]*W for i in range(H)]
for i in range(H):
for j in range(W):
val = 0
for k in range(len(arr1[0])):
val += arr1[i][k]*arr2[k][j]
arr3[i][j] = val
return arr3
def determinant(self,arr):
'''
正方行列N*Nの行列式
計算量O(N**3)
'''
arr_calc = copy.deepcopy(arr)
N = len(arr_calc)
for i in range(N-1):
d = arr_calc[i][i]
for j in range(i+1,N):
e = arr_calc[j][i]/d
for k in range(i,N):
arr_calc[j][k] -= e*arr_calc[i][k]
#arr_calc 上△行列
det = 1
for i in range(N):
det *= arr_calc[i][i]
return det
def invarr(self,arr):
'''
正方行列N*Nの逆行列
det == 0ならreturn False
計算量O(N**3)
'''
arr_calc = copy.deepcopy(arr)
if self.determinant(arr_calc) == 0:
return False
N = len(arr_calc)
for i in range(N):
v = [0]*(N)
v[i] = 1
arr_calc[i].extend(v)
for i in range(N-1):
d = arr_calc[i][i]
for j in range(i+1,N):
e = arr_calc[j][i]/d
for k in range(i,2*N):
arr_calc[j][k] -= e*arr_calc[i][k]
for i in range(N-1,-1,-1):
d = arr_calc[i][i]
for k in range(i,2*N):
arr_calc[i][k] /= d
for j in range(i-1,-1,-1):
c = arr_calc[j][i]
for k in range(i,2*N):
arr_calc[j][k] -= c*arr_calc[i][k]
inv = [[0]*(N) for i in range(N)]
for i in range(N):
for j in range(N):
inv[i][j] = arr_calc[i][j+N]
return inv
def SimultaneousE(self,arr):
'''
3x+2y+z = 4
4x+5y+6z = 3
7x+8y+9z = 2
->
3 2 1 4
4 5 6 3
7 8 9 2
'''
N = len(arr)
arr1 = [[0]*(N) for i in range(N)]
for i in range(N):
for j in range(N):
arr1[i][j] = arr[i][j]
v = [[0] for i in range(N)]
for i in range(N):
v[i][0] = arr[i][-1]
if self.determinant(arr1) == 0:
return False
inva = self.invarr(arr1)
return self.multiplication(inva,v)
def invmod(self,a):#mod逆元
if a == 0:
return 0
if a == 1:
return 1
return (-self.invmod(self.mod % a) * (self.mod // a)) % self.mod
def multiplication_mod(self,arr1,arr2):
H = len(arr1)
W = len(arr2[0])
arr3 = [[0]*W for i in range(H)]
for i in range(H):
for j in range(W):
val = 0
for k in range(len(arr1[0])):
val += arr1[i][k]*arr2[k][j]
arr3[i][j] = val%self.mod
return arr3
def determinant_mod(self,arr):
'''
正方行列N*Nの行列式
計算量O(N**3)
'''
arr_calc = copy.deepcopy(arr)
N = len(arr_calc)
for i in range(N-1):
d = arr_calc[i][i]
for j in range(i+1,N):
e = arr_calc[j][i]*self.invmod(d)
e %= self.mod
for k in range(i,N):
arr_calc[j][k] -= e*arr_calc[i][k]
arr_calc[j][k] %= self.mod
#arr_calc 上△行列
det = 1
for i in range(N):
det *= arr_calc[i][i]
det %= self.mod
return det
def invarr_mod(self,arr):
'''
正方行列N*Nの逆行列
det == 0ならreturn False
計算量O(N**3)
'''
arr_calc = copy.deepcopy(arr)
det = self.determinant_mod(arr_calc)
if det == 0:
return False
N = len(arr_calc)
for i in range(N):
v = [0]*(N)
v[i] = det
arr_calc[i].extend(v)
for i in range(N-1):
d = arr_calc[i][i]
for j in range(i+1,N):
e = arr_calc[j][i]*self.invmod(d)
for k in range(i,2*N):
arr_calc[j][k] -= e*arr_calc[i][k]
arr_calc[j][k] %= self.mod
for i in range(N-1,-1,-1):
d = arr_calc[i][i]
for k in range(i,2*N):
arr_calc[i][k] *= self.invmod(d)
for j in range(i-1,-1,-1):
c = arr_calc[j][i]
for k in range(i,2*N):
arr_calc[j][k] -= c*arr_calc[i][k]
arr_calc[j][k] %= self.mod
inv = [[0]*(N) for i in range(N)]
for i in range(N):
for j in range(N):
inv[i][j] = arr_calc[i][j+N]*self.invmod(det)%self.mod
return inv
def SimultaneousE_mod(self,arr):
'''
3x+2y+z = 4
4x+5y+6z = 3
7x+8y+9z = 2
->
3 2 1 4
4 5 6 3
7 8 9 2
'''
N = len(arr)
arr1 = [[0]*(N) for i in range(N)]
for i in range(N):
for j in range(N):
arr1[i][j] = arr[i][j]
v = [[0] for i in range(N)]
for i in range(N):
v[i][0] = arr[i][-1]
det = self.determinant_mod(arr1)
if det == 0:
return False
inva = self.invarr_mod(arr1)
v2 = self.multiplication_mod(inva,v)
for i in range(N):
v2[i][0] %= self.mod
return v2
def modPow_matrix(self,arr,n):
'''
N*Nの正方行列arrをn乗する。
'''
N = len(arr)
if n==0:
arr1 = [[0]*(N) for i in range(N)]
for i in range(N):
arr1[i][i] = 1
return arr1
if n==1:
for i in range(N):
for j in range(N):
arr[i][j] %= self.mod
return arr
if n % 2 == 1:
arr2 = self.multiplication_mod(arr,self.modPow_matrix(arr,n-1))
return arr2
arr3 = self.modPow_matrix(arr,n//2)
return self.multiplication_mod(arr3,arr3)
def Pow_matrix(self,arr,n):
'''
N*Nの正方行列arrをn乗する。
'''
N = len(arr)
if n==0:
arr1 = [[0]*(N) for i in range(N)]
for i in range(N):
arr1[i][i] = 1
return arr1
if n==1:
return arr
if n % 2 == 1:
arr2 = self.multiplication(arr,self.Pow_matrix(arr,n-1))
return arr2
arr3 = self.Pow_matrix(arr,n//2)
return self.multiplication(arr3,arr3)
A,B = map(int,input().split())
N = int(input())
mod = 10**9+7
MX = matrix()
ansls = []
arr = [[A,B,1],[1,0,0],[0,0,0]]
arr2 = [[1,0,0],[0,1,0],[A,B,1]]
ini = [[1],[1],[0]]
for i in range(N):
T = int(input())
T2 = T//2
Tr = T%2
md = MX.modPow_matrix(arr, T2)
if Tr==1:
md = MX.multiplication_mod(arr2,md)
vec = MX.multiplication_mod(md,ini)
ans = sum([vec[i][0] for i in range(3)])%mod
ansls.append(ans)
print(*ansls,sep='\n')