Given an array $A$ of length $N$, we can define rotation as follows. If we rotate $A$ to the right, all elements move to the right one unit, and the last element moves to the beginning. That is, it becomes $[A_{N}, A_{1},A_{2},\ldots,A_{N-1}]$. Similarly if we rotate $A$ to the left, it becomes $[A_{2},A_{3},\ldots,A_{N}, A_{1}]$.

Given an array $A$ and an integer $x$, define $f(A,x)$ to be the array $A$ rotated by the amount $x$. If $x≥ 0$, this means we rotate it right $x$ times. If $x<0$, this means we rotate it left $|x|$ times.

You are given an array $A$ of length $N$. Then $Q$ queries follow. In each query, an integer $x$ is given. To answer the query, you should replace $A$ with $A+f(A,x)$ where $+$ denotes concatenation. After this operation, you must output the sum of all elements of $A$. Since this number can be large, output it modulo $10^{9} + 7$.

Note that the queries are cumulative. When you modify $A$ to answer one query, it starts that way for the next query.

------ Input ------

The first line contains an integer $N$ - the size of the initial array. 
The second line contains $N$ integers $A_{1},\ldots, A_{N}$ - the elements of the initial array.
The third line contains an integer $Q$ - the number of queries.
The fourth line contains $Q$ space-separated integers $x_{1},\ldots, x_{Q}$, where $x_{i}$ is the parameter of the $i$-th query.

------ Output ------
After each query, output in a single line the the sum of all elements of the current array modulo $10^{9}+7$.

------ Constraints  ------
$ 1≤ N≤ 10^{5}$
$ 1≤ Q≤ 10^{5}$
$ -10^{9}≤ A_{i}≤ 10^{9}$ 
$ -10^{5} ≤ x_{i}≤ 10^{5}$ 

------ Subtasks ------

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2
1 2
2
1 1
----- Sample Output 1 ------ 
6
12
----- explanation 1 ------ 
Initially, the array is $[1,2]$.
After the first query, the array becomes $[1, 2] + f([1, 2], 1) = [1, 2] + [2, 1] = [1, 2, 2, 1]$. The total sum is $6$.
After the second query, the array becomes $[1, 2, 2, 1] + f([1, 2, 2, 1], 1) = [1, 2, 2, 1] + [1, 1, 2, 2] = [1, 2, 2, 1, 1, 1, 2, 2]$. The total sum is $12$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
l = list(map(int, input().split()))
nq = int(input())
q = list(map(int, input().split()))
sum = 0
for i in l:
	sum += i
for p in q:
	sum *= 2
	print(sum % 1000000007)


import sys
import copy
import math
import heapq
import bisect
import statistics
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from heapq import heapify, heappush, heappop
from itertools import permutations, combinations
from collections import Counter, OrderedDict, deque
from bisect import bisect_left as bl, bisect_right as br
from functools import lru_cache, reduce
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strr = lambda : input().strip()
jl = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
muli = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
m = 1000000007
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
s = sum(arr) % m
for i in range(q):
	print(pow(2, i + 1, m) * s % m)


n = int(input())
list1 = [int(x) for x in input().split()]
q = int(input())
q_list = [int(x) for x in input().split()]
prod = sum(list1)
for elem in q_list:
	prod *= 2
	print(prod % 1000000007)


t = 1

def f(a, x):
	if x == 0:
		return a
	if x < 0:
		x = -x
		p1 = a[:x]
		p2 = a[x:]
		fp = p1[::-1] + p2[::-1]
		return fp[::-1]
	p1 = a[:n - x]
	p2 = a[n - x:]
	fp = p1[::-1] + p2[::-1]
	return fp
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	x = list(map(int, input().split()))
	s = sum(a)
	for _ in range(q):
		s = s * 2 % 1000000007
		print(s)
	t -= 1


n = int(input())
a = list(map(int, input().split()))
k = int(input())
q = list(map(int, input().split()))
summ = sum(a)
for i in range(k):
	summ = summ * 2 % 1000000007
	print(summ)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
x = list(map(int, input().split()))
s = sum(a)
for i in range(q):
	s = s * 2
	print(s % (10 ** 9 + 7))


n = int(input())
l = list(map(int, input().split()))
n1 = int(input())
l1 = list(map(int, input().split()))
sum1 = sum(l)
mod = 10 ** 9 + 7
for i in range(n1):
	sum1 = sum1 * 2
	print(sum1 % mod)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
x = list(map(int, input().split()))
add = sum(a)
x = pow(10, 9) + 7
for i in range(q):
	add += add
	print(add % x)


n = int(input())
arr = list(map(int, input().split()))
s = sum(arr)
q = int(input())
trash = list(map(int, input().split()))
for i in range(q):
	s *= 2
	print(s % (10 ** 9 + 7))


modulo = 10 ** 9 + 7
input()
a = map(int, input().split())
q = int(input())
s = sum(a) % modulo
for i in range(1, q + 1):
	s = s * 2 % modulo
	print(s)


modulo = 10 ** 9 + 7
input()
arr = map(int, input().split(' '))
query_count = int(input())
s = sum(arr)
for i in range(1, query_count + 1):
	s *= 2
	print(s % modulo)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
x = list(map(int, input().split()))
modulo = 1000000007
sum1 = sum(a)
for i in range(q):
	sum1 = sum1 * 2 % modulo
	print(sum1)


n = int(input())
l = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
s = sum(l)
for i in range(q):
	s = s * 2
	print(s % 1000000007)


n = int(input())
l = list(map(int, input().split()))
q = int(input())
x = list(map(int, input().split()))
s = sum(l)
while q > 0:
	s = s * 2
	c = 10 ** 9 + 7
	print(s % c)
	q = q - 1


import math
n = int(input())
l = list(map(int, input().split()))
q = int(input())
x = list(map(int, input().split()))
s = sum(l)
for j in range(q):
	s = s * 2
	print(s % (10 ** 9 + 7))


n = int(input())
l = list(map(int, input().split()))
q = int(input())
q_e = list(map(int, input().split()))
s = sum(l)
for i in range(q):
	s = s * 2
	print(s % (10 ** 9 + 7))


n = int(input())
a = list(map(int, input().split()))
k = int(input())
l = list(map(int, input().split()))
s = sum(a)
while k > 0:
	s = s * 2
	c = 10 ** 9 + 7
	print(s % c)
	k -= 1


mod = 1000000007
n = int(input())
a = list(map(int, input().split()))
q = int(input())
qx = list(map(int, input().split()))
s = sum(a)
for _ in range(q):
	s *= 2
	s = s % mod
	print(s)


n = int(input())
l1 = list(map(int, input().split()))
u = int(input())
l2 = list(map(int, input().split()))
su = sum(l1)
s = su
for i in range(u):
	s = s * 2
	print(s % (pow(10, 9) + 7))


n1 = int(input())
list1 = list(map(int, input().split()))
n2 = int(input())
list2 = list(map(int, input().split()))
sum1 = sum(list1)
mod = 1000000007
for i in range(n2):
	sum1 += sum1
	sum1 = (sum1 % mod + mod) % mod
	print(sum1)


n = int(input())
l1 = list(map(int, input().split()))
t = int(input())
l2 = list(map(int, input().split()))
s = sum(l1)
m = 10 ** 9 + 7
for i in range(t):
	s = s * 2 % m
	print(s)


T = int(input())
N = list(map(int, input().split()))
a = int(input())
v = list(map(int, input().split()))
su = sum(N)
M = 10 ** 9 + 7
for i in range(a):
	su = su * 2 % M
	print(su)


n = int(input())
l = list(map(int, input().split()))
m = int(input())
n = list(map(int, input().split()))
s = sum(l)
x = 10 ** 9 + 7
for i in range(m):
	s = s * 2 % x
	print(s)


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
m = 1000000007
s = sum(arr) % m
for i in range(q):
	print(pow(2, i + 1, m) * s % m)


n = int(input())
l = list(map(int, input().split()))
count = 0
le = int(input())
a = list(map(int, input().split()))
s = sum(l)
for i in range(len(a)):
	s = s * 2
	print(s % (10 ** 9 + 7))


a = int(input())
l = list(map(int, input().split()))
b = int(input())
m = list(map(int, input().split()))
s = sum(l)
for i in range(b):
	s *= 2
	print(s % (10 ** 9 + 7))


n = int(input())
arr = [int(i) for i in input().split()]
q = int(input())
x = [int(i) for i in input().split()]
s = sum(arr)
for i in range(q):
	s = s * 2
	print(s % (10 ** 9 + 7))


x = int(input())
l1 = list(map(int, input().split()))
q = int(input())
l2 = list(map(int, input().split()))
su = sum(l1)
a = len(l2)
s = su
for i in range(a):
	s = s * 2
	print(s % (pow(10, 9) + 7))


n = int(input())
l1 = list(map(int, input().split()))
k = int(input())
l2 = list(map(int, input().split()))
s = sum(l1)
x = 10 ** 9 + 7
for i in range(k):
	s = s * 2 % x
	print(s)


n = int(input())
lis = list(map(int, input().split()))
q = int(input())
que = list(map(int, input().split()))
s = sum(lis)
m = 10 ** 9 + 7
for i in que:
	s = (s + s) % m
	print(s % m)


t = int(input())
c = 0
p = 1000000007
l = list(map(int, input().split()))
for i in l:
	c = (c % p + i) % p
q = int(input())
a = list(map(int, input().split()))
for q1 in range(q):
	c *= 2
	c %= p
	print(c)


n = int(input())
m = list(map(int, input().split()))
p = int(input())
q = list(map(int, input().split()))
c = 10 ** 9 + 7
t = sum(m)
for i in range(p):
	t = t * 2 % c
	print(t)


N = int(input())
A = list(map(int, input().split()))
m = int(input())
Q = list(map(int, input().split()))
s = sum(A)
x = 10 ** 9 + 7
for i in range(m):
	s = s * 2 % x
	print(s)


n = int(input())
a = list(map(int, input().split()))
b = int(input())
m = list(map(int, input().split()))
mod = 1000000007
sum1 = sum(a)
for i in range(b):
	sum1 = sum1 * 2 % mod
	print(sum1)


N = int(input())
l = list(map(int, input().split()))
N2 = int(input())
l2 = list(map(int, input().split()))
s = sum(l)
x = 10 ** 9 + 7
for i in range(N2):
	s = s * 2 % x
	print(s)