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

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in map(int, input().split()):
        # accumulate dp
        S = [0] * (k + 2)
        for i in range(k + 1):
            S[i + 1] = S[i] + dp[i]
            if S[i + 1] >= MOD:
                S[i + 1] -= MOD
        # ndp[i] = dp[i - a] + ... + dp[i]
        dp = [S[i + 1] - S[max(0, i - a)] for i in range(k + 1)]

    print(dp[k])
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    dp=[0]*(k+1)
    dp[k]=1
    for i in range(n):
        ndp=[0]*(k+1)
        # dpの累積和を取っておく
        S=[0]*(k+2)
        for j in range(k+1):
            S[j+1]=S[j]+dp[j]
            S[j+1]%=MOD
        # iterete
        for j in range(k+1):
            ndp[j]=S[min(j+A[i]+1,k+1)]-S[j]
            ndp[j]%=MOD
        dp=ndp
    print(dp[0])
resolve()
### BUGGY CODE ###

import numpy as np
I=list(map(int,open(0).read().split()))
n,k,q=I[:3]
a=I[3:]
p=np.array([k]*n)
for i in a:
    p-=1
    p[i-1]+=1
for i in p:
    if i<=0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

I=list(map(int,open(0).read().split()))
n,k,q=I[:3]
a=I[3:]
p=[0]*n
for i in a:
    p[i-1]+=1
for i in p:
    if i<=q-k:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import numpy as np
N, K = list(map(int, input().split()))
p = list(map(int, input().split()))

max_sum_val = 0
sum_list = []
for j in range(len(p) - K + 1):
    max_sum_val = max(sum(p[j:K+j]), max_sum_val)
print((max_sum_val + K)/2)

### FIXED CODE ###

import numpy as np
N, K = list(map(int, input().split()))
p = list(map(int, input().split()))
p_sum=[0]
for i in p:p_sum.append(p_sum[-1]+i)
max_sum_val = 0
for j in range(len(p_sum) - K):
    max_sum_val = max(p_sum[K+j]-p_sum[j], max_sum_val)
print((max_sum_val + K)/2)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
s = [input() for _ in range(n)]
parity = [-1 for _ in range(n)]

def dfs(x):
	for i in range(n):
		if s[x][i] == "1":
			if parity[i] == parity[x]:
				print(-1)
				sys.exit()
			elif parity[i] == -1:
				parity[i] = parity[x]^1
				dfs(i)
	return

parity[0] = 0
dfs(0)

dist = [[10**30 if s[i][j] == "0" else 1 for j in range(n)] for i in range(n)]
for i in range(n):
	dist[i][i] = 0

for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

#print(*dist, sep="\n")
diam = 0
for i in range(n):
	for j in range(n):
		if dist[i][j] < 10**30:
			diam = max(diam, dist[i][j])

print(diam+1)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
s = [input() for _ in range(n)]
parity = [-1 for _ in range(n)]

def dfs(x):
	for i in range(n):
		if s[x][i] == "1":
			if parity[i] == parity[x]:
				print(-1)
				sys.exit()
			elif parity[i] == -1:
				parity[i] = parity[x]^1
				dfs(i)
	return

parity[0] = 0
dfs(0)

dist = [[10**30 if s[i][j] == "0" else 1 for j in range(n)] for i in range(n)]
for i in range(n):
	dist[i][i] = 0

for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

#print(*dist, sep="\n")
diam = 0
for i in range(n):
	for j in range(n):
		if dist[i][j] < 10**30:
			diam = max(diam, dist[i][j])

print(diam+1)
### BUGGY CODE ###

import sys

data=input().split(' ')
data_1=int(data[0])
data_1sub=data_1+1
data_2=int(data[1])
d=0
e=0
for i in range(data_1sub):	
	for j in range(data_1sub):
         for k in range(data_1sub):
         	d=i+j+k
         	if d == data_2:
         		e=e+1
         	else:
         		pass
print(e)

### FIXED CODE ###

import sys

data=input().split(' ')
k=int(data[0])
data_1sub=k+1
s=int(data[1])
d=0
e=0
for i in range(data_1sub):
    for j in range(data_1sub):
        d=s-i-j
        if (0 <= d) and (d <= k):
            e=e+1
        else:
            pass
print(e)
### BUGGY CODE ###

ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]


n = int(input())
a = ai()
mod = 10**9+7

from collections import Counter
dup = list(Counter(sorted(a)).values()).index(2)+1
ant = a.index(dup)
post = a[::-1].index(dup)


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


def inv(x):
    return pow(x, mod - 2, mod)


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCb(n+1,k)
        if ant+post+1 >= k:
            ans -= nCb(ant+post,k-1)
        print(ans)


### FIXED CODE ###

ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())
a = ai()

dup = sum(a)-n*(n+1)//2
ant = a.index(dup)
post = a[::-1].index(dup)

mod = 10**9+7
factorial = [1]
for i in range(1,n+2):
    factorial.append(factorial[i-1]*i %mod)

inverse = [0]*(n+2)
inverse[n+2-1] = pow(factorial[n+2-1], mod-2,mod)
for i in range(n+2-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n,r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % mod


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCr(n+1,k) - nCr(ant+post,k-1)
        if ans < 0:
            ans += mod
        print(ans)
### BUGGY CODE ###

import re

N, Q = map(int, input().split())
S = input()
L = [list(map(int, input().split())) for i in range(Q)]

array = []

for m in re.finditer(r'AC', S):
    array.append(m.start())


for i in range(Q) :
    count = 0
    for j in range(len(array)) :
        if L[i][0] - 1 <= array[j] and L[i][1] - 2 >= array[j] :
            count += 1
    print(count)


### FIXED CODE ###

import re

N, Q = map(int, input().split())
S = input()
L = [list(map(int, input().split())) for i in range(Q)]

array = [0 for i in range(N + 1)]
for i in range(N) :
    array[i + 1] = array[i] + (1 if S[i: i + 2] == 'AC' else 0)

for i in range(Q) :
    print(array[L[i][1] - 1] - array[L[i][0] - 1])
### BUGGY CODE ###

N = int(input())
a_list = list(map(int,input().split()))


from collections import Counter
a_dict = Counter(a_list)

start = a_list[0]
# 数を減らさない。
# a_dict[a] -= 1

a_keys = a_dict.keys()

def check():
    for a1 in a_keys:
#         print("for1",start,a1)
        a0 = start
        tmp_dict = a_dict.copy()
#         tmp_dict[a1] -= 1
        for i in range(N):
#             print(" for2",i,a0,a1)
#             print(tmp_dict)
            next_a = int(bin(a0^a1), 0)
            if not next_a in tmp_dict:
#                 print(next_a," not in dict")
                break
            if tmp_dict[next_a] <= 0:
#                 print(next_a," dict 0")
                break
            a0 = a1
            a1 = next_a
            tmp_dict[next_a] -= 1
            if tmp_dict[next_a] == 0:
                tmp_dict.pop(next_a)
            if i == N-1:
                return True
    return False

if check():
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import Counter
N = int(input())
a_list = list(map(int,input().split()))

l = len(set(a_list))

def check():
    counter = Counter(a_list)
    if l == 1:
        if a_list[0] == 0:
            return True
        return False
    if l == 2:
        if counter[0] == N/3:
            return True
        return False
    if l == 3:
        x,y,z = set(a_list)
        if int(bin(x^y^z), 0) == 0 and set(list(counter.values()))==set([N/3]):
            return True
        return False
    return False

if check():
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

S = list(input())
Q = int(input())

for i in range(Q):
    X = list(input().split(" "))
    if int(X[0]) == 1:
        S.reverse()
    elif int(X[0]) == 2 and int(X[1]) == 1:
        S.insert(0, X[2])
    elif int(X[0]) == 2 and int(X[1]) == 2:
        S.append(X[2])

print(*S, sep="")



### FIXED CODE ###

S = list(input())
Q = int(input())
rev = False
F = []

for i in range(Q):
    X = list(input().split(" "))

    if X[0] == "1" and rev is False:
        rev = True
    elif X[0] == "1" and rev is True:
        rev = False
    elif X[0] == "2" and X[1] == "1" and rev is False:
        F.append(X[2])
    elif X[0] == "2" and X[1] == "1" and rev is True:
        S.append(X[2])
    elif X[0] == "2" and X[1] == "2" and rev is False:
        S.append(X[2])
    elif X[0] == "2" and X[1] == "2" and rev is True:
        F.append(X[2])

F.reverse()
F.extend(S)

if rev is True:
    F.reverse()

print(*F, sep="")
### BUGGY CODE ###

n, W = map(int, input().split())
w, v = [], []
for _ in range(n):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

dp = [[0]*(W+1) for _ in range(n+1)]

for i in range(n):
    for j in range(W+1):
        dp[i+1][j] = dp[i][j]
        if w[i] <= j:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j])

print(dp[n][W])


### FIXED CODE ###

n, W = map(int, input().split())
w, v = [], []
for _ in range(n):
    _w, _v = map(int, input().split())
    w.append(_w)
    v.append(_v)

dp = [[0]*(W+1) for _ in range(n+1)]

for i in range(n):
    for j in range(W+1):
        dp[i+1][j] = dp[i][j]
        if w[i] <= j:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j])

print(dp[n][W])
### BUGGY CODE ###

import re
s = input()
words = ['dream', 'dreamer', 'erase', 'eraser']

while s != '':
    tmp = s
    for word in words:
        s = re.sub(r'dream$', '', s)
        s = re.sub(r'dreamer$', '', s)
        s = re.sub(r'erase$', '', s)
        s = re.sub(r'eraser$', '', s)
    if s == '':
        print('YES')
    if tmp == s:
        print('NO')
        break

### FIXED CODE ###

s = input()
while s != '':
    tmp = s
    s = s.replace('eraser', '')
    s = s.replace('erase', '')
    s = s.replace('dreamer', '')
    s = s.replace('dream', '')
    if s == '':
        print('YES')
    if tmp == s:
        print('NO')
        break
### BUGGY CODE ###

N,K=map(int,input().split())
S=input()

#連続する0or1の数をリスト化
L=[]
c=1
for i in range(1,N):
    if S[i]==S[i-1]:
        c+=1
        continue
    if c>0:
        L.append(c)
    c=1
if c>0:
    L.append(c)

#1で始まる2K+1個の塊を連続させることができる
#最大値を求める
ans=0
start=0
if S[0]=='0':
    #0から始まっている場合はそこから2K個をつなげる
    ans=sum(L[0:2*K])
    start=1
for i in range(start,len(L),2):
    ans=max(ans,sum(L[i:i+2*K+1]))
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
S=input()

ans=0
history=[0]*(2*K+1)
sum_recent=0
idx=0
c=1
for i in range(1,N+1):
    #print(ans,sum_recent,history,idx,c)
    if i<N and S[i]==S[i-1]:
        c+=1
        continue
    sum_recent=sum_recent+c-history[idx]
    history[idx]=c
    idx=(idx+1)%(2*K+1)
    c=1
    if S[i-1]=='1':
        ans=max(ans,sum_recent)
    elif i==N:
        sum_recent-=history[idx]
        ans=max(ans,sum_recent)

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

import sys
sys.setrecursionlimit(4100000)

n, m, k = map(int, input().split())
F = [[] for i in range(n)] #Friend
BinG = [[] for i in range(n)] #Block in Group
#友達関係
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
GS = []   #Group Size
gid = 0 #group id

#DFSを行うための関数
def using_DFS(p):
    if G[p] == 0:
        G[p] = gid
        for j in F[p]:
            if G[j-1] == 0:
                using_DFS(j-1)
            else:   #すでに登場
                pass
    else:
        pass

for i in range(n):
    if G[i] == 0:
        gid += 1
        t = 0
        using_DFS(i)
        GS.append(G.count(gid))
    else:
        pass
#print('G=',G)
#print('S=',S)

#ブロック関係
for i in range(k):
    c, d = map(int, input().split())
    if G[c-1] == G[d-1]:
        BinG[c-1].append(d)
        BinG[d-1].append(c)
    else:
        pass
#print('F=',F)
#print('B=',B)

for i in range(n):
    ans = GS[G[i]-1] - 1 - len(F[i]) - len(BinG[i])
    print(ans)

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    # r: どの連結成分に存在するかをメモするid
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter

N = int(input())
As = list(map(int, input().split()))
count = sorted(Counter(As).items(), key = lambda x: x[0])
divider = set()


ans = 0
for numi, c in count:
  if c > 1:
    divider.add(numi)
    continue
  flag = True
  for numj in divider:
    if numj ** (0.5) > numi:
      divider.add(numi)
      ans += 1
      break
    if numi % numj == 0:
      break
  else:
    divider.add(numi)
    ans += 1
  
print(ans)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
M = max(A_list)+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Here your code !
import math
  
def is_prime_num(in_num):
    cnt = 0
    if in_num == 2:
        return True
    elif in_num <= 1:
        return False
    elif in_num % 2 == 0:
        return False
    else:
        if pow(2, in_num-1, in_num) == 1:
            return True
        else:
            return False
 
while True:
    try:
        n = int(input())
        prime_cnt = 0
        if n >= 2:
            #?????????2???????????????
            prime_cnt = prime_cnt + 1
 
        for i in range(3, n+1, 2):
            if is_prime_num(i):
                prime_cnt = prime_cnt + 1
                  
  
        print(str(prime_cnt))
    except:
        break
    

### FIXED CODE ###

#init
max_num = 1000000
is_prime_num = [True for i in range (max_num+1)]

#0, 1 --- not prime number
is_prime_num[0] = False
is_prime_num[1] = False
end = int(max_num ** .5)

for i in range(2, end+1):
    if is_prime_num[i]:
        for j in range(i*i, max_num+1, i):
            is_prime_num[j] = False


while True:
    try:
        n = int(input())
        prime_cnt = 0
        for i in range(1, n+1):
            if is_prime_num[i]:
                prime_cnt = prime_cnt + 1
                   
   
        print(str(prime_cnt))
    except:
        break
### BUGGY CODE ###

K = 1000000007
S = input()
l = len(S)
li = [1] + [0] * 12
for i in range(l):
    s = S[l - i - 1]
    if s == "?":
        work_li = [0] * 13
        next_li = [0] * 13
        for x in range(10):
            work_li[x * (10 ** i) % 13] = 1
        next_li = [sum([work_li[j] * li[(k - j) % 13] for j in range(13)]) for k in range(13)]
    else:
        n = int(s)
        r = (n * (10 ** i)) % 13
        next_li = [li[(j - r) % 13] for j in range(13)]
    li = [j % K for j in next_li]
print(li[5])


### FIXED CODE ###

K = 1000000007
S = input()
l = len(S)
li = [1] + [0] * 12
work_lists = [[0] * 13 for i in range(6)]
for i in range(6):
    for x in range(10):
        work_lists[i][(x * (10 ** i)) % 13] = 1
for i in range(l):
    s = S[l - i - 1]
    if s == "?":
        work_li = work_lists[i % 6]
        next_li = [sum([work_li[j] * li[(k - j) % 13] for j in range(13)]) % K for k in range(13)]
    else:
        n = int(s)
        r = (n * (10 ** (i % 6))) % 13
        next_li = [li[(j - r) % 13] for j in range(13)]
    li = next_li
print(li[5])
### BUGGY CODE ###

while True:
    try:
        n = int(raw_input())
    except EOFError:
        break
    count = 0
    for i in range(2, n + 1):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            count += 1
    print count

### FIXED CODE ###

N = 10 ** 6
sieve = map(lambda x:False, range(2, N + 1))
for i in range(2, N + 1):
    if sieve[i - 2]:
        continue
    for j in range(i * 2, N + 1, i):
        sieve[j - 2] = True
while True:
    try:
        n = int(raw_input())
    except EOFError:
        break
    print sieve[:n - 1].count(False)
### BUGGY CODE ###

N, X, Y= map(int, input().split())
List=[]
for i in range(1,N+1,1):
	for j in range(i,N+1,1):
		saitan = min(abs(i-j), abs(i-X)+abs(Y-j)+1, abs(i-Y)+abs(X-j)+1)
		List.append(saitan)

for i in range(1,N):
    	print(List.count(i))


### FIXED CODE ###

N, X, Y= map(int, input().split())
List=N*[0]

for i in range(1,N+1,1):
	for j in range(i,N+1,1):
		saitan = min(abs(i-j), abs(i-X)+abs(Y-j)+1, abs(i-Y)+abs(X-j)+1)
		List[saitan] += 1


for i in range(1,N):
    	print(List[i])
### BUGGY CODE ###

R, C, K = map(int, input().split())

I = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(K): 
  r, c, v = map(int, input().split())
  I[r][c] = v 
  
DP1 = [0 for _ in range(C+1)] #c列目までとったとき、最新の行で1個以下とったという条件のもとの最大
DP2 = [0 for _ in range(C+1)] #c列目までとったとき、最新の行で2個以下とったという条件のもとの最大
DP3 = [0 for _ in range(C+1)] #c列目までとったとき、最新の行で3個以下とったという条件のもとの最大
#print(I)

for r in range(1,R+1):
  for c in range(1,C+1): 
    #更新の順番に注意
    #mid = max(DP1[c], DP2[c], DP3[c]) + I[r][c]
    mid = DP3[c] + I[r][c] 
    DP3[c] = max(DP3[c-1], mid, DP2[c-1] + I[r][c]) #3個
    DP2[c] = max(DP2[c-1], mid, DP1[c-1] + I[r][c]) #2個
    DP1[c] = max(DP1[c-1], mid) #1個
  #print(DP3)
    
print(DP3[C])
    
    
    

### FIXED CODE ###

R, C, K = map(int, input().split())

I = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(K): 
  r, c, v = map(int, input().split())
  I[r][c] = v 
  
DP1 = [0 for _ in range(C+1)] #c行目までとったとき、c行目で1個以下とったときの最大
DP2 = [0 for _ in range(C+1)] #c行目までとったとき、c行目で2個以下とったときの最大
DP3 = [0 for _ in range(C+1)] #c行目までとったとき、c行目で3個以下とったときの最大
#print(I)

for r in range(1,R+1):
  for c in range(1,C+1): 
    #更新の順番に注意
    #mid = max(DP1[c], DP2[c], DP3[c]) + I[r][c]
    mid = DP3[c] + I[r][c] 
    DP3[c] = max(DP3[c-1], mid, DP2[c-1] + I[r][c]) #3個
    DP2[c] = max(DP2[c-1], mid, DP1[c-1] + I[r][c]) #2個
    DP1[c] = max(DP1[c-1], mid) #1個
  #print(DP3)
    
print(DP3[C])
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(2000000)

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


ans = a*n//b - a*(n//b)

for i in range(n, int(math.sqrt(n))-1, -1):
    if ans < a*i//b - a*(i//b):
        ans = a*i//b - a*(i//b)
    #print(ans, end=" ")
    #print(a*i//b - a*(i//b))

print(ans)


### FIXED CODE ###

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

x = min(b-1, n)
ans = a*x//b - a*(x//b)

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


def cal_comb(n,r):
    ret = 1
    for i in range(1,n+1):
        ret *= i
    for i in range(1,n-r+1):
        ret //= i
    for i in range(1,r+1):
        ret //= i
    return ret


N,M = map(int,input().split())
L = list(map(int,input().split()))

from itertools import accumulate
accumulated =  [0]+list(accumulate(L))
accumulated = map(lambda x:x%M,accumulated)
def counter(array):
    from collections import Counter
    return list(Counter(array).most_common())
c = counter(accumulated)
ans = 0
for x in c:
    ans += cal_comb(x[1],2)

print(ans)



### FIXED CODE ###




N,M = map(int,input().split())
L = list(map(int,input().split()))

from itertools import accumulate
accumulated =  [0]+list(accumulate(L))
accumulated = map(lambda x:x%M,accumulated)
def counter(array):
    from collections import Counter
    return list(Counter(array).most_common())
c = counter(accumulated)
ans = 0
for x in c:
    ans += x[1] * (x[1]-1) //2

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

def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        s=list(reversed(bin(a[i])[2:]))
        for j in range(len(s)):
            if s[j]=='1':
                hist[j]+=1
        bs.append(s)
    #print(bs)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)


### FIXED CODE ###

def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)
        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1

    #print(bs)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)
### BUGGY CODE ###


N,Q = map(int,input().split())
S = input()

A=[[] for _ in range(26)]
for i in range(len(S)):
    A[int(ord(S[i]))-65].append(i)
#print(A)
g = [1]*(N)
#print(g)
for i in range(Q):
    t,d = input().split()
    for h in A[ord(t)-65]:
        if h == 0 and d=='L':
            g[0] = 0
        if h == N-1 and d=='R':
            g[N-1] = 0
        if h<N-1 and d=='R':
            tmp = g[h]
            g[h] = 0
            g[h+1] += tmp
        if h>0 and d=='L':
            tmp = g[h]
            g[h] = 0
            g[h-1] += tmp
sum = 0
for i in range(N):
    sum += g[i]
print(sum)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
td = [input().split() for _ in range(Q)]
def solve(i):
    cur = i
    for t,d in td:
        if S[cur] == t:
            cur += 1 if d=='R' else -1
        if cur < 0 or cur >= N:
            return False
    return True
 
def binary_search(ok,ng):
    while abs(ok-ng) >1:
        mid = (ok+ng)//2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(max(0,binary_search(-1,N)-binary_search(N,-1)+1))