Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = int(S(), 2)
D = []
for i in range(1, n + 1):
    if n % i == 0 and n // i % 2:
        D += [i]

D.sort()
cnt = [0] * len(D)
ans = 0
for k in range(len(D)):
    bit = x >> (n - D[k])
    cnt[k] = (cnt[k] + bit) % mod
    m = 0
    for i in range(n // D[k]):
        m <<= D[k]
        if i % 2:
            m |= (2 ** D[k] - 1) ^ bit
        else:
            m |= bit
    if m <= x:
        cnt[k] += 1
    ans += cnt[k] * D[k] * 2
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
    ans %= mod

print(ans % mod)





### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
x = S()
rx=x.replace("1","2").replace("0","1").replace("2","0")
D = []
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if n // i % 2:
            D += [i]
        if i != n // i and i % 2:
            D += [n // i]

D.sort()
bx=int(x,2)
cnt = [0] * len(D)
ans = 0
for k in range(len(D)):
    t=x[:D[k]]
    rt=rx[:D[k]]
    f=(t+rt)*(n//D[k]//2)+t
    cnt[k]=cnt[k]+int(int(f,2)<=bx)+int(t,2)
    cnt[k]%=mod
    ans += cnt[k]*D[k]*2
    for kk in range(k + 1, len(D)):
        if D[kk] % D[k] == 0:
            cnt[kk] -= cnt[k]
            cnt[kk]%=mod
    ans %= mod

print(ans % mod)
### BUGGY CODE ###

n, k = map(int, input().split())
tds = [list(map(int, input().split())) for _ in range(n)]

tds.sort(key=lambda x:x[1])

arr = [0] * (n + 1)

for idx, td in enumerate(tds):
    t, d = td
    arr[t] = [d, n - idx - 1]

tds = [y for x, y in tds[::-1]]

base = 0
res = 0
kind = 0

new_arr = []
for xy in arr:
    if not xy:
        continue
    new_arr.append(xy)

new_arr.sort(reverse=True)

for x, y in new_arr:
    kind += 1
    base += x
    if y < k:
        tds[y] = 0
    else:
        while tds[k - 1] == 0:
            k -= 1
            if k == 0:
                break
        k -= 1
        if k <= 0:
            break
    res = max(res, kind ** 2 + base + sum(tds[:k]))

print(res)


### FIXED CODE ###

n, k = map(int, input().split())
tds = [list(map(int, input().split())) for _ in range(n)]

tds.sort(key=lambda x:x[1])

arr = {}
for idx, td in enumerate(tds):
    t, d = td
    arr[t] = [d, n - idx - 1]

tds = [y for x, y in tds[::-1]]

base = 0
rest = sum(tds[:k])
res = 0
kind = 0
new_arr = sorted(arr.values(), reverse=True)

for x, y in new_arr:
    kind += 1
    base += x
    if y < k:
        rest -= x
        tds[y] = 0
    else:
        while k >= 1 and tds[k - 1] == 0:
            k -= 1
        rest -= tds[k - 1]
        k -= 1
        if k <= 0:
            break
    res = max(res, kind ** 2 + base + rest)

if k >= 0:
    res = max(res, kind ** 2 + base + rest)

print(res)
### BUGGY CODE ###

import itertools

n = int(input())
a = list(map(int,input().split()))

mod = 10**9 + 7

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += (a[i]*a[j])%mod

print(ans%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))

mod = 10**9 + 7

sum_a = sum(a)%mod
ans = 0
for i in range(n-1):
    sum_a -= a[i]
    ans += (a[i]*sum_a)%mod

print(ans%mod)
### BUGGY CODE ###


s = input()
q = int(input())
t = []
 
def F(f,ans,c):
  if f == '1':
     return c + ans
  if f == '2':
    return ans + c
 
def R(r):
  if r == '1':return '2'
  if r == '2':return '1'
 
ans = s
r = '1'
for n in range(q):
  t = input().split()
  if t[0] == '1':
    r = R(r)
  else:
    if r =='2':
      t[1] = R(t[1])
    ans = F(t[1],ans,t[2])
 
    
if r == '1': 
   print(ans)
else:
  print(ans[::-1])

### FIXED CODE ###


s = input()
q = int(input())
t = []
 
def F(f,fr,ba,c):
  if f == '1':
     return c + fr, ba
  if f == '2':
    return fr,ba + c

def R(r):
  if r == '1':return '2'
  if r == '2':return '1'

ans = s
fr = ''
ba = ''
r = '1'
for n in range(q):
  t = input().split()
  if t[0] == '1':
    r = R(r)
  else:
    if r =='2':
      t[1] = R(t[1])
    fr, ba = F(t[1],fr,ba,t[2])
 
    
if r == '1': 
   print(fr + ans + ba)
else:
  print(ba[::-1] + ans[::-1]+ fr[::-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0

l = {}
r = {}
for i in range(1,n+1):
    if i-a[i-1] in l:
        l[i-a[i-1]]+=1
    else:
        l[i-a[i-1]]=1

    
    
    if i+a[i-1] in r:
        r[i+a[i-1]]+=1
    else:
        r[i+a[i-1]]=1
    

for i,v in l.items():
    for j,w in r.items():
        if i==j:
            ans+=v*w


print(ans)





### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0

l = {}
r = {}
for i in range(1,n+1):
    if i-a[i-1] in l:
        l[i-a[i-1]]+=1
    else:
        l[i-a[i-1]]=1

    
    
    if i+a[i-1] in r:
        r[i+a[i-1]]+=1
    else:
        r[i+a[i-1]]=1
    

for i in l:
    if i in r:
        ans += l[i]*r[i]
    


print(ans)
### BUGGY CODE ###

splited = input().split(" ")

k = int(splited[0])
s = int(splited[1])

result = 0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x + y + z == s:
        result = result + 1

print(result)

### FIXED CODE ###

splited = input().split(" ")

k = int(splited[0])
s = int(splited[1])

result = 0
for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z and z <= k:
      result = result + 1

print(result)
### BUGGY CODE ###

def comb(n, r, p):
    return fac[n] * facinv[r] * facinv[n - r] % p


def comb_pre(N_UNTIL, p):
    for i in range(2, N_UNTIL + 1):
        fac.append(fac[i - 1] * i % p)
        inv.append(-inv[p % i] * (p // i) % p)
        facinv.append(facinv[-1] * inv[-1] % p)


fac = [1, 1]
facinv = [1, 1]
inv = [0, 1]

K = int(input())
S = input()
N = len(S)
MOD = 1_000_000_007
comb_pre(N + K - 1, MOD)
ans = 0
for i in range(K + 1):
    tmp = pow(25, K - i, MOD)
    tmp *= comb(N + K - i - 1, K - i, MOD)
    tmp %= MOD
    tmp *= pow(26, i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)


### FIXED CODE ###

def comb(n, r, p):
    return fac[n] * facinv[r] * facinv[n - r] % p


def comb_pre(N_UNTIL, p):
    for i in range(2, N_UNTIL + 1):
        fac.append(fac[i - 1] * i % p)
        inv.append(-inv[p % i] * (p // i) % p)
        facinv.append(facinv[-1] * inv[-1] % p)


fac = [1, 1]
facinv = [1, 1]
inv = [0, 1]

K = int(input())
S = input()
N = len(S)
MOD = 1_000_000_007
comb_pre(N + K - 1, MOD)
ans = 0
for i in range(K + 1):
    tmp = pow(25, K - i, MOD)
    tmp *= comb(N + K - i - 1, K - i, MOD)
    tmp %= MOD
    tmp *= pow(26, i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)
### BUGGY CODE ###

from math import gcd

k = int(input())
d = {}

ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            if (a, b, c) in d:
                ans += d[(a, b, c)]
            else:
                d[(a, b, c)] = gcd(a, gcd(b, c))
                ans += d[(a, b, c)]

print(ans)


### FIXED CODE ###

def GCD(a, b):
    return a if b == 0 else GCD(b, a % b)


k = int(input())

ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        ab = GCD(a, b)
        if ab == 1:
            ans += k
            continue
        for c in range(1, k + 1):
            ans += GCD(ab, c)

print(ans)
### BUGGY CODE ###

n=int(input())
l=[]
for i in range(n):
    x=int(input())
    l.append(x)
for i in range(n):
    x=l[i]
    l.pop(i)
    y=max(l)
    l.insert(i,x)
    print(y)

### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
    x=int(input())
    l.append(x)
x=sorted(l)
for i in range(n):
    if l[i]==x[-1]:
        print(x[-2])
    else:
        print(x[-1])
### BUGGY CODE ###

import random
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
a=[0 for i in range(N+1)]
b=[0 for i in range(N+1)]
for i in range(N):
    a[A[i]]+=1
    b[B[i]]+=1
if max([a[i]+b[i] for i in range(1,N+1)])<=N:
    print("Yes")
else:
    print("No")
    exit()
point=0
for i in range(N):
    if A[i]==B[i]:
        point+=1
while(point>0):
    x=random.randrange(N)
    y=random.randrange(N)
    if x==y:
        continue
    before=0
    after=0
    if A[x]==B[x]:
        before+=1
    if A[y]==B[y]:
        before+=1
    if A[x]==B[y]:
        after+=1
    if A[y]==B[x]:
        after+=1
    if before>after:
        B[x],B[y]=B[y],B[x]
        point=point+after-before
print(*B)


### FIXED CODE ###

import random
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
a=[0 for i in range(N+1)]
b=[0 for i in range(N+1)]
for i in range(N):
    a[A[i]]+=1
    b[B[i]]+=1
if max([a[i]+b[i] for i in range(1,N+1)])<=N:
    print("Yes")
else:
    print("No")
    exit()
B=B[::-1]
point=0
for i in range(N):
    if A[i]==B[i]:
        point+=1
while(point>0):
    x=random.randrange(N)
    y=random.randrange(N)
    if x==y:
        continue
    before=0
    after=0
    if A[x]==B[x]:
        before+=1
    if A[y]==B[y]:
        before+=1
    if A[x]==B[y]:
        after+=1
    if A[y]==B[x]:
        after+=1
    if before>after:
        B[x],B[y]=B[y],B[x]
        point=point+after-before
print(*B)
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
b = Counter(a)
c = b.most_common()
values, counts = zip(*b.most_common())
d = (counts)
ans = 0

for j in range(len(d)):
    f = d[j]
    if f > 1:
        ans = ans + (f*(f - 1)/2)

for i in range(n):
    g = a[i]
    gc = a.count(g)
    tem = ans - gc + 1
    print(int(tem))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n
ans = 0

for i in range(n):
    b[a[i] - 1] += 1

for i in range(n):
    ans += b[i]*(b[i] - 1)//2

for i in range(n):
    print(ans - b[a[i] -1] + 1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))

a0b=[0]*n
c=[0]*30
for i in range(n):
    a0b[i]=bin(a[i])
    st=str(a0b[i])
    for j in range(len(st)-2):
        z=a0b[i][-1-j]
        z=int(z)
        c[j]+=z

c_al=[0]*30
al=0
for i in range(len(c)):
    if c[i]%2==1:
        al+=2**i

#c_alは全体の排他的論理和
ans=[0]*n
for i in range(n):
    ans[i]=al^a[i]
L=[str(a) for a in ans]
L=" ".join(L)
print(L)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))

c=a[0]
for i in range(n-1):
    c=c^a[i+1]

ans=[0]*n
for i in range(n):
    ans[i]=c^a[i]
L=[str(a) for a in ans]
L=" ".join(L)
print(L)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n,k = list(map(int, list(input().split())))
scores = list(map(int, list(input().split())))

for i in range(k + 1, n + 1):
    _s_k = 1
    s_k = 1
    for j in range(k):
        _s_k *= scores[i - j - 2]
        s_k *= scores[i - j - 1]

    if _s_k < s_k:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# -*- coding: utf-8 -*-

n,k = list(map(int, list(input().split())))
scores = list(map(int, list(input().split())))

for i in range(k + 1, n + 1):
    remove = scores[i - k - 1]
    add    = scores[i - 1]

    if remove < add:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
N=int(input())
print(0)
s=input()
a=s
if s=='Vacant':
  sys.exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    sys.exit()
  if n%2!=0:
    if s==a:
      right=n
    else:
      left=n
  else:
    if s!=x:
      right=n
    else:
      left=n
      

### FIXED CODE ###

import sys
N=int(input())
print(0)
s=input()
a=s
if s=='Vacant':
  sys.exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    sys.exit()
  if n%2!=0:
    if s==a:
      right=n
    else:
      left=n
  else:
    if s!=a:
      right=n
    else:
      left=n
### BUGGY CODE ###

N=int(input())
josi = list(map(int,input().split()))
count=[0]*N
n=0
while n<N-1:
  count[josi[n]] =count[josi[n]]+1
  n=n+1
n=0
while n<N:
  print(count[n])

      

### FIXED CODE ###

N=int(input())
josi = list(map(int,input().split()))
count=[0]*N
n=0
while n<N-1:
  count[josi[n]-1] =count[josi[n]-1]+1
  n=n+1
n=0
while n<N:
  print(count[n])
  n=n+1
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    n,s=map(int,input().split())
    MOD=998244353
    import numpy as np
    A=list(map(int,input().split()))
    dp=[np.array([0]*(n+1)) for _ in range(s)]
    dp=[np.array([1]+[0]*n)]+dp 
    for i in range(n):
        u=A[i]
        for j in range(s,-1,-1):
            if j+u<=s:
                dp[j+u][1:]+=dp[j][:-1]
                dp[j+u]%=MOD
    #print(dp)

    w=dp[s]
    q=[2**(n-i) for i in range(n+1)]
    ans=w*q%MOD
    print(ans.sum()%MOD)
#print(w)
if __name__=="__main__":
    main()


### FIXED CODE ###

mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        if j + A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
        dp[i+1][j] %= mod

print(dp[N][S])
### BUGGY CODE ###

s = input()
q=int(input())

count = 1
for i in range(q):
#     print(s)
    q_y_i = input().split()
#     print(q_y_i)
#     print(count)
    if q_y_i[0] == '1':
        count +=1
    else:
        if count % 2 == 1:
            if q_y_i[1] == '1':
                s = q_y_i[2] + s
#                 print('p1')
            elif q_y_i[1] == '2':
                s = s + q_y_i[2]
#                 print('p2')
        elif count % 2 == 0:
            if q_y_i[1] == '1':
                s = s + q_y_i[2]
#                 print('p3')
            elif q_y_i[1] == '2':
                s = q_y_i[2] + s
#                 print('p4')

if count % 2 == 0:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

s = input()
q=int(input())

from collections import deque
d = deque()
d.append(s)

count = 1
for i in range(q):
#     print(s)
    q_y_i = input().split()
#     print(q_y_i)
#     print(count)
#     print(d)
    if q_y_i[0] == '1':
        count +=1
    else:
        if count % 2 == 1:
            if q_y_i[1] == '1':
                d.appendleft(q_y_i[2])
#                 print('p1')
#                 print(d)
            elif q_y_i[1] == '2':
                d.append(q_y_i[2])
#                 print('p2')
        elif count % 2 == 0:
            if q_y_i[1] == '1':
                d.append(q_y_i[2])
#                 print('p3')
            elif q_y_i[1] == '2':
                d.appendleft(q_y_i[2])
#                 print('p4')

ans = ''
for v in d:
    ans = ans + v
if count % 2 == 0:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
l = [str(input()) for _ in range(n)]
# l = set(l)

m = [-1]*n
ans = 0

for i in range(n-1):
  if m[i] >= 0:
    continue
  else:
    si = l[i]
    m[i] = i
    temp  = 0
    for j in range(i+1, n):
      if m[j] >= 0:
        continue
      else:
        sj = l[j]
        for k in range(10):
          sj = sj.replace(si[k], '', 1)
        if sj == '':
          temp += 1
          m[j] = i
          #print(i, temp)
  ans += (temp+1)*temp/2

print(int(ans))




### FIXED CODE ###

n = int(input())
l = [str(sorted(str(input()))) for _ in range(n)]

d = {}

for i in range(n):
  s = l[i]
  # print(s)
  if s in d:
    d[s] += 1
  else:
    d[s] = 1

ans = 0
for x in d.values():
  ans += x*(x-1)/2
print(int(ans))
### BUGGY CODE ###

l,l2 = map(int,input().split())
x = list(map(int,input().split()))

dp = [0]
for i in range(1,l):
    dp.append(dp[i-1]+abs(x[i-1]-x[i]))
    
for i in range(l-1):
    for k in range(1,l2+1):
        if i + k >= l:
            break
        if dp[i+k] !=0:
            dp[i+k] = min(dp[i] + abs(x[i]-x[i+k]),dp[i+k])
        
print(dp[-1])

### FIXED CODE ###

import numpy as np

l,l2 = map(int,input().split())
x = np.array(list(map(int,input().split())))

dp = np.zeros(l,dtype=int)
dp[1] = abs(x[0]-x[1])

for i in range(2,l):
    y = max(i - l2,0)
    dp[i] = np.min(dp[y:i] + abs(x[y:i] - x[i]))
    
print(dp[-1])
### BUGGY CODE ###

import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, S = [int(sys.stdin.readline()) for _ in range(2)]


@lru_cache(maxsize=None)
def f(b, n):
    if n < b:
        return n
    return f(b, int(n // b)) + n % b


def bisect_left_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


if S > N:
    print(-1)
    exit()
if S == N:
    print(N + 1)
    exit()

# #########
# b = 2
# ans = -1
# prev = 0
# while b <= N:
#     if f(b, N) > prev:
#         print(b, N, f(b, N))
#     prev = f(b, N)
#     b += 1
# ##########

b = 2
ans = -1
while b <= math.sqrt(N) + 1:
    if f(b, N) == S:
        ans = b
        break
    b += 1
if ans >= 0:
    print(ans)
    exit()

for i in range(1, int(math.sqrt(N)) + 1):
    hi = N // i + 1
    lo = N // (i + 1) + 1
    b = bisect_left_callable(lambda x: -f(x, N), -S, lo, hi)
    if f(b, N) == S:
        ans = b
print(ans)


### FIXED CODE ###

import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, S = [int(sys.stdin.readline()) for _ in range(2)]


@lru_cache(maxsize=None)
def f(b, n):
    if n < b:
        return n
    return f(b, int(n // b)) + n % b


if S > N:
    print(-1)
    exit()
if S == N:
    print(N + 1)
    exit()

# #########
# b = 2
# ans = -1
# prev = 0
# while b <= N:
#     if f(b, N) > prev:
#         print(b, N, f(b, N))
#     prev = f(b, N)
#     b += 1
# ##########

b = 2
ans = -1
while b <= math.sqrt(N) + 1:
    if f(b, N) == S:
        ans = b
        break
    b += 1
if ans >= 0:
    print(ans)
    exit()

ans = INF
# b > sqrt(N) のとき 2 桁になるので上位桁を全探索する
for d2 in range(1, int(math.sqrt(N)) + 1):
    if (N - S) % d2 == 0:
        b = int(1 + (N - S) // d2)
        if b >= 2 and f(b, N) == S:
            ans = min(ans, b)
if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

n = int(input())
a = [int(x) for x in input().split()]

a.insert(0, 0)
b = [1 + a[1]]
cnt = 0

for x in range(2, n + 1):
    cnt += b.count(x - a[x])
    b.append(a[x] + x)

print(cnt)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

n = int(input())
a = [int(x) for x in input().split()]

a.insert(0, 0)
c = dict()
c[1 + a[1]] = 1
cnt = 0

for x in range(2, n + 1):
    if x - a[x] in c.keys():
        cnt += c[x - a[x]]

    if x + a[x] < 0:
        continue

    if x + a[x] in c.keys():
        c[x + a[x]] += 1
    else:
        c[x + a[x]] = 1

print(cnt)
### BUGGY CODE ###

n = int(input())
s = list(str(input()))
q = int(input())

def segfunc(x,y):
    return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=set(init_val[i])
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = set(y)
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
q = int(input())

s = [ord(c)-ord('a') for c in s]

#def segfunc(x,y):
    #return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]={init_val[i]}
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1] | seg[2*i+2]

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = (res | seg[p]) | seg[q]
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, sys.stdin.readline().split())
    if t == '2':
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))
    else:
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
### BUGGY CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
MOD = 10 ** 9 + 7
sum = 0
for i in range(1, N):
    for j in range(1, M):
        sum += (X[i] - X[i-1]) * (Y[j] - Y[j-1]) * i * (N - i) * j * (M - j)
        sum %= MOD

print(sum)


### FIXED CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
MOD = 10 ** 9 + 7

xsum, ysum = 0, 0
for i in range(1, N):
    xsum += (X[i] - X[i-1]) * i * (N - i)
    xsum %= MOD
for j in range(1, M):
    ysum += (Y[j] - Y[j-1]) * j * (M - j)
    ysum %= MOD

print((xsum * ysum) % MOD)