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

N = int(input())
A = [int(i) for i in input().split()]

maxdig = 60
mod = 10**9+7

ans = 0
for i in range(60+1):
  cnt1 = 0
  for a in A:
    if (a >> i) & 1:
      cnt1 += 1
  ans += (cnt1*(N-cnt1)*(1<<i))
  ans = ans%mod

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

maxdig = 60
mod = 10**9+7

ans = 0
for i in range(60+1):
  cnt1 = sum([1 for a in A if (a >> i) & 1])
  ans += (cnt1*(N-cnt1)*(1<<i))
  ans = ans%mod

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

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

l = ['SS', 'SW', 'WS', 'WW']

for i in range(4):
  ans = l[i]
  for j in range(1, n):
    if ans[j] == 'S' and s[j] == 'o':
      if ans[j-1] == 'S':
        ans += 'S'
      else:
        ans += 'W'
    elif ans[j] == 'S' and s[j] == 'x':
      if ans[j-1] == 'S':
        ans += 'W'
      else:
        ans += 'S'
    elif ans[j] == 'W' and s[j] == 'o':
      if ans[j-1] == 'S':
        ans += 'W'
      else:
        ans += 'S'
    else:
      if ans[j-1] == 'S':
        ans += 'S'
      else:
        ans += 'W' 
  flag = 0
  if ans[-1] == ans[0]:
    if ans[0] == 'S' and s[0] == 'o':
      if ans[-2] == ans[1]:
        flag = 1
    elif ans[0] == 'W' and s[0] == 'o':
      if ans[-2] != ans[1]:
        flag = 1
    elif ans[0] == 'S' and s[0] == 'x':
      if ans[-2] != ans[1]:
        flag = 1
    else:
      if ans[-2] == ans[1]:
        flag = 1
  if flag == 1:
    print(ans[:-1])
    exit()
else:
  print('-1')

### FIXED CODE ###

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

l = ['SS', 'SW', 'WS', 'WW']

for i in range(4):
  ans = l[i]
  for j in range(1, n):
    if ans[j] == 'S' and s[j] == 'o':
      if ans[j-1] == 'S':
        ans += 'S'
      else:
        ans += 'W'
    elif ans[j] == 'S' and s[j] == 'x':
      if ans[j-1] == 'S':
        ans += 'W'
      else:
        ans += 'S'
    elif ans[j] == 'W' and s[j] == 'o':
      if ans[j-1] == 'S':
        ans += 'W'
      else:
        ans += 'S'
    else:
      if ans[j-1] == 'S':
        ans += 'S'
      else:
        ans += 'W' 
  flag = 0
  if ans[-1] == ans[0]:
    if ans[0] == 'S' and s[0] == 'o':
      if ans[-2] == ans[1]:
        flag = 1
    elif ans[0] == 'W' and s[0] == 'o':
      if ans[-2] != ans[1]:
        flag = 1
    elif ans[0] == 'S' and s[0] == 'x':
      if ans[-2] != ans[1]:
        flag = 1
    else:
      if ans[-2] == ans[1]:
        flag = 1
  if flag == 1:
    print(ans[:-1])
    exit()
else:
  print('-1')
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ls = [0]*N
for i in range(N):
    ls[i] = A.index(i+1)
def plus(n):
    return n + 1
ls = map(plus,ls)
print(*ls)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ls = [0]*N
for i in range(N):
    ls[A[i]-1] = i+1
print(*ls)
### BUGGY CODE ###

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

trial_num = int(input())
stones = list(input())

min_turn_stones = 2*10**5

for i in range(trial_num):
    tmp_min = stones[:i].count("#") + stones[i+1:].count(".")
    if( tmp_min < min_turn_stones):
        min_turn_stones = tmp_min

print(min_turn_stones)

### FIXED CODE ###

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

trial_num = int(input())
stones = list(input())

left_black_stone = 0
right_white_stone = stones.count(".")
min_turn_stones = right_white_stone

for i in range(trial_num):
    if(stones[i] == "#"):
        left_black_stone += 1
    else:
        right_white_stone -= 1

    tmp_min = left_black_stone + right_white_stone
    if(tmp_min < min_turn_stones):
        min_turn_stones = tmp_min


print(min_turn_stones)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc136/tasks/abc136_d

s = list(str(input()))
n = len(s)
t = []
u = []
w = []
for i in range(n):
    if s[i] == 'R':
        for j in range(i, n):
            if s[j] == 'L':
                t.append(j - 1)
                u.append(j - i - 1)
                break
    else:
        for j in reversed(range(i)):
            if s[j] == 'R':
                t.append(j)
                u.append(i - j)
                break

v = [0] * n
aaa = 10 ** 100

for i in range(n):
    a = (aaa - u[i]) % 2
    v[t[i] + a] += 1

print(' '.join(map(str, v)))


### FIXED CODE ###

#https://atcoder.jp/contests/abc136/tasks/abc136_d

s = list(str(input()))
n = len(s)
t = []
u = []
v = [0] * n
for i in range(n):
    if i == 0:
        for j in range(i, n):
            if s[j] == 'L':
                t.append(j - 1)
                u.append(j - i - 1)
                break

    else:
        if s[i] == s[i-1]:
            t.append(t[i-1])
            u.append(u[i-1] + 1)
        elif s[i] == 'R':
            for j in range(i, n):
                if s[j] == 'L':
                    t.append(j - 1)
                    u.append(j - i - 1)
                    break
        else:
            
            for j in reversed(range(i)):
                if s[j] == 'R':
                    t.append(j)
                    u.append(i - j)
                    break
            '''
            t.append(i-1)
            u.append(0)
            '''
    a = u[i] % 2
    v[t[i] + a] += 1


print(' '.join(map(str, v)))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(n-k+1):
    tmp = (sum(p[i:i+k])+k)/2
    if tmp > ans:
        ans = tmp

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
kitai = [(p+1)/2 for p in P]
kitai_cum = [kitai[0]] * (n + 1)
for i in range(n):
    kitai_cum[i+1] = kitai_cum[i] + kitai[i]
ans = 0
for i in range(n-k+1):
    ans = max(ans, kitai_cum[i+k]-kitai_cum[i])
print(ans)
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = int(1e+9) + 7
def extgcd(a, b):
  if b == 0:
    return 1, 0
  else:
    x, y, u, v, k, l = 1, 0, 0, 1, a, b
    while l != 0:
      x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
      k, l = l, k % l
    return x
def inved(x):
  y = 1
  p = mod - 2
  base = x
  while p != 0:
    if p % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    p //= 2
  return y
def doubling(N, M):
  y = 1
  base = N
  while M != 0:
    if M % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    M //= 2
  return y
S = [inved(i+1) for i in range(b)]
A = doubling(2, n)
A = (A - 1) % mod
proda, prodb = 1, 1
for i in range(a):
  proda *= ((n - i) * S[i]) % mod
  proda %= mod
for i in range(b):
  prodb *= ((n - i) * S[i]) % mod
  prodb %= mod
print((A - proda - prodb) % mod)


### FIXED CODE ###

n, a, b = map(int, input().split())
mod = int(1e+9) + 7
def extgcd(a, b):
  if b == 0:
    return 1, 0
  else:
    x, y, u, v, k, l = 1, 0, 0, 1, a, b
    while l != 0:
      x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
      k, l = l, k % l
    return x
def inved(x):
  a = extgcd(x, mod)
  return a % mod
def doubling(N, M):
  y = 1
  base = N
  while M != 0:
    if M % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    M //= 2
  return y
S = [inved(i+1) for i in range(b)]
A = doubling(2, n)
A = (A - 1) % mod
proda, prodb = 1, 1
for i in range(a):
  proda *= ((n - i) * S[i]) % mod
  proda %= mod
for i in range(b):
  prodb *= ((n - i) * S[i]) % mod
  prodb %= mod
print((A - proda - prodb) % mod)
### BUGGY CODE ###

#14:50
scale = 20
#scale = 3
n = int(input())
raw = list(map(int,input().split()))
a = [[] for _ in range(scale)]
for i in range(n):
  x = raw[i]
  for d in range(scale):
    a[d].append(x%2)
    x //= 2
#print(a)
b = []
for d in range(scale):
  A = a[d]
  add = [0]
  for i in range(n):
    add.append(add[-1]+A[i])
  b.append(add)
#print(b)
import bisect
ans = 0
for l in range(n):
  now = []
  for d in range(scale):
    r = bisect.bisect_right(b[d],b[d][l]+1)
    now.append(r)
  ans += min(now) - l - 1
  #print(now,min(now)-l-1)
print(ans)

### FIXED CODE ###

#14:50
#チョイ見た
scale = 20
#scale = 3
n = int(input())
raw = list(map(int,input().split()))
a = [[] for _ in range(scale)]
for i in range(n):
  x = raw[i]
  for d in range(scale):
    a[d].append(x%2)
    x //= 2
#print(a)
c = []
for d in range(scale):
  b = []
  tmp = 0
  for i in range(n):
    if a[d][i] == 1:
      tmp += 1
      if tmp == 2:
        b.append(i)
        break
  else:
    b += [n for _ in range(n)]
    c.append(b)
    continue
  for i in range(1,n):
    if a[d][i-1] == 0:
      b.append(b[-1])
      continue
    for j in range(b[-1]+1,n):
      if a[d][j] == 1:
        b.append(j)
        break
    else:
      b += [n for _ in range(i,n)]
      break
  c.append(b)
#print(c)
ans = []
for l in range(n):
  now = []
  for d in range(scale):
    now.append(c[d][l])
  ans.append(min(now)-l)
#print(ans)
print(sum(ans))
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for i in range(Q):
    l,r=map(int,input().split())
    print(S[l-1:r].count("AC"))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
s_cnt=[]
cnt=0
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        cnt+=1
        s_cnt.append(cnt)
    else:
        s_cnt.append(cnt)
for i in range(Q):
    l,r=map(int,input().split())
    l-=2
    r-=2
    if l<0:
        print(s_cnt[r])
    else:    
        print(s_cnt[r] - s_cnt[l])
### BUGGY CODE ###

Q = int(input())

ls = [list(map(int,input().split())) for i in range(Q)]
n_max = max(ls)[1]

prime = []
data = [i for i in range(2,n_max+1)]
limit = n_max**(1/2)
while True:
    p = data[0]
    if limit<=p:
        break
    prime.append(p)
    data = [i for i in data if i%p!=0]
prime = prime +data

ans_ls = [0]*len(prime)
for i in range(len(prime)):
    if (prime[i]+1)//2 in prime:
        ans_ls[i] =1

for l,r in ls:
    ans = 0
    for i in range(len(prime)):
        if (l<=prime[i]) and (prime[i]<=r):
           ans += ans_ls[i]
    print(ans)



### FIXED CODE ###

Q = int(input())

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

n_max = 10**5

prime = []
data = [i for i in range(2,n_max+1)]
limit = n_max**(1/2)

while True:
    p = data[0]
    if limit<=p:
        break
    prime.append(p)
    data = [i for i in data if i%p!=0]

prime = prime +data

ans_ls = [0]*(1+n_max)
for i in prime:
    if (i + 1) // 2 in prime:
        ans_ls[i] = 1

ans_cs = [0]*(1+n_max)
for i in range(n_max):
    ans_cs[i+1] = ans_cs[i]+ans_ls[i+1]
    
for l,r in ls:
    print(ans_cs[r]-ans_cs[l-1])
### BUGGY CODE ###

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

count=0

for i in range(N):
    if min(P[:i+1])>=P[i]:
        count+=1
    else:
        pass
print(count)

### FIXED CODE ###

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

count=1
base=P[0]

for i in range(1,N):
    if P[i]<=base:
        base=P[i]
        count+=1
print(count)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A_arr = []
que = deque()
dist = [[-1 for i in range(W)] for i in range(H)]

for i in range(H):
    A_arr.append(list(input()))
    for j in range(W):
        if A_arr[i][j] == "#":
            que.append([i,j])
            dist[i][j] = 0

n_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while 1:
    if len(que) == 0:
        break
    
    x, y = que.popleft()
    d = dist[x][y]
    for n in range(4):
        tmp = [x + n_list[n][0], y + n_list[n][1]]
        if tmp[0] < 0 or tmp[0] >= H:
            pass
        elif tmp[1] < 0 or tmp[1] >= W:
            pass
        elif dist[tmp[0]][tmp[1]] != -1:
            pass
        else:
            dist[tmp[0]][tmp[1]] = d + 1
            que.append([tmp[0], tmp[1]])


print(d)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A_arr = []
que = deque()
dist = [[-1 for i in range(W)] for i in range(H)]

for i in range(H):
    A_arr.append(list(input()))
    for j in range(W):
        if A_arr[i][j] == "#":
            que.append([i,j])
            dist[i][j] = 0

n_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while 1:
    if len(que) == 0:
        break
    
    x, y = que.popleft()
    d = dist[x][y]
    for n in range(4):
        tmp = [x + n_list[n][0], y + n_list[n][1]]
        if tmp[0] < 0 or tmp[0] >= H:
            pass
        elif tmp[1] < 0 or tmp[1] >= W:
            pass
        elif dist[tmp[0]][tmp[1]] != -1:
            pass
        else:
            dist[tmp[0]][tmp[1]] = d + 1
            que.append([tmp[0], tmp[1]])


print(d)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
gridgraph = [list(input()) for _ in range(H)]
distance = [[float("inf")]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append([i, j])
            distance[i][j] = 0
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if distance[ny][nx] != float("inf"):
            continue
        distance[ny][nx] = distance[cy][cx] + 1
        q.append([ny, nx])
ans = 0
for d in distance:
    ans = max(ans, max(d))
print(ans)


### FIXED CODE ###

import sys
from collections import deque
H, W = map(int, input().split())
gridgraph = []
for line in sys.stdin.readlines():
    line = line.rstrip()
    gridgraph.append(list(line))
q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0

while len(q):
    cy, cx = q.popleft()

    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)
### BUGGY CODE ###

DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N = int(input())
INL = [II() for _ in range(N)]
SM = sum(INL)
HSM = SM//2

DP1 = [[0]*(SM+1) for _ in range(N+1)]
DP2 = [[0]*(SM+1) for _ in range(N+1)]
DP1[0][0] = 1
DP2[0][0] = 1

for i, value in enumerate(INL,1):
    for j in range(SM+1):
        if j-value >= 0:
            DP1[i][j] = (2*DP1[i-1][j]+DP1[i-1][j-value])%DVSR
            DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-value]
        else:
            DP1[i][j] = (2*DP1[i-1][j])%DVSR
            DP2[i][j] = DP2[i-1][j]

sub = 0
patall = POW(3, N)
for i in range(HSM+1, SM+1):
    sub += DP1[N][i]*3

if SM % 2 == 0:
    sub += 3*(DP1[N][HSM] - 2*DP2[N][HSM])
    sub += 3*DP2[N][HSM]

# print(DP2[N])
# print(SM)
print((patall - sub) % DVSR)

### FIXED CODE ###

DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N = int(input())
INL = [II() for _ in range(N)]
SM = sum(INL)
HSM = SM//2

DP1 = [[0]*(SM+1) for _ in range(N+1)]
DP2 = [[0]*(SM+1) for _ in range(N+1)]
DP1[0][0] = 1
DP2[0][0] = 1

for i in range(1,N+1):
    value = INL[i-1]
    for j in range(SM+1):
        if j-value >= 0:
            DP1[i][j] = (2*DP1[i-1][j]+DP1[i-1][j-value])%DVSR
            DP2[i][j] = (DP2[i-1][j]+DP2[i-1][j-value])%DVSR
        else:
            DP1[i][j] = (2*DP1[i-1][j])%DVSR
            DP2[i][j] = DP2[i-1][j]

sub = 0
patall = POW(3, N)
for i in range(HSM+1, SM+1):
    sub += DP1[N][i]*3

if SM % 2 == 0:
    sub += 3*(DP1[N][HSM] - 2*DP2[N][HSM])
    sub += 3*DP2[N][HSM]

# print(DP2[N])
# print(SM)
print((patall - sub) % DVSR)
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
L.sort()

def binary_s(left, right, a, b):
    result = 0
    while L[a]+L[b] > L[left]:
        if right - left <= 1:
            if L[a]+L[b] > L[right]:
                result = right - b
            else:
                result = left - b
            break
        mid = (left+right)//2
        if L[a]+L[b] > L[mid]:
            left = mid
        else:
            right = mid
    return result
counter = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        counter += binary_s(j+1, n-1, i, j)
print(counter)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split(' ')))
l.sort()
counter = 0
for i in range(n):
    s = i + 2
    for j in range(i+1,n):        
        while (s < n and l[i] + l[j] > l[s]):
            s += 1
        counter += s-j-1
print(counter)
### BUGGY CODE ###

import itertools

n = int(input())
c = list(input())

deta = list(range(n))

lis = list(itertools.combinations(deta,2))

count  = 0

for i in lis:
    if c[i[0]] != c[i[1]]:
        for j in range(i[0]+1,i[1]):
            if j-i[0] != i[1]-j and c[i[0]] != c[j] and c[j] != c[i[1]]:
                count += 1

print(count)


### FIXED CODE ###

n = int(input())
c = list(input())

r = c.count("R")
g = c.count("G")
b = c.count("B")

ans = r*g*b
count  = 0
sub1 = 0

for i in range(n):
    for j in range(i+1,n):
        if 2*j-i >= n or 2*j-i <0:
            break
        elif c[2*j-i] != c[i] and c[i] != c[j] and c[2*j-i] != c[j]:
                sub1 += 1


print(ans-sub1)
### BUGGY CODE ###

num=int(input())
line=input()
line=line.split()
count=0
count1=0
for i in range(num):
    num1=int(line[i])
    for j in range(i+1):
        if num1<=int(line[j]):
            count+=1
    if count == (i+1):
        count1+=1
    count=0
print(count1)

### FIXED CODE ###

num=int(input())
line=input()
line=line.split()
#b=list(map(int,input().split()))
count1=0
num1=200000
for i in range(num):
    if num1>=int(line[i]):
        num1=int(line[i])
        count1+=1
print(count1)
### BUGGY CODE ###

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

def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [0]*(M+1)
    for s in S:
        dp_ = dp[:]
        for i, t in enumerate(T):
            dp[i+1] = dp_[i+1] + dp[i] - dp_[i] + (dp_[i]+1 if t==s else 0)
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [1]*(M+1)
    for s in S:
        is_s = s.__eq__
        dp_ = dp[:]
        acc = 0
        for i, t in enumerate(T):
            if is_s(t):
                acc += dp_[i]
            dp[i+1] = dp_[i+1] + acc
    res = (dp[-1])%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
    
if N > 2000:
  print(0)
  
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import math

ans = 0
for i in range(1, N):
    ans += cmb(N-1, N-i, mod)*math.factorial(i-1)*math.factorial(N-i-1)*(A[N-1]-A[i-1])
    ans %= mod
    for j in range(i+1, N):
        ans += cmb(N-1, j-i+1, mod)*math.factorial(N-j+i-2)*math.factorial(j-i-1)*(A[j-1]-A[i-1])
        ans %= mod
        
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
    
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

L = [1]*N
for i in range(1, N):
    L[i] *= L[i-1]*i
    L[i] %= mod
    
ans = 0
for i in range(1, N):
    ans += cmb(N-1, N-i, mod)*L[i-1]*L[N-i-1]*(A[N-1]-A[i-1])
    ans %= mod
        
L2 = [0]*(N-1)
for i in range(N-1):
    L2[i] = A[i+1]-A[i]

S = [0]*N
for i in range(N-1):
    S[i+1] = S[i] + L2[i]
    
L3 = [0]*N
for i in range(1, N):
    if N-i-1 >= i:
        L3[i] = L3[i-1] + S[N-i-1] - S[i-1]
    else:
        L3[i] = L3[N-i-1]

for t in range(1, N-1):
    ans += cmb(N-1, t+1, mod)*L[N-t-2]*L[t-1]*L3[t]
    ans %= mod
        
print(ans)
### BUGGY CODE ###

S = input()

modList = [0] * 2019 # あまりは0～2018の2019個

ans = 0

modList[0] = 1 # 解答でいうT(n)=0 の場合

# 最大20万回ループ、時間かかるならＤＰする？
# ↓ではTLEになった
# for i in range(len(S)):
#     m = int(S[i:]) % 2019
#     modList[m] += 1
T = 0
for i in range(1,len(S)+1):
    T += int(S[-i]) * 10**i
    modList[T % 2019] += 1


#print(modList)

for j in modList:
    if j <= 1:
        continue
    else:
        ans += j*(j-1)/2

print(int(ans))


### FIXED CODE ###

S = input()

modList = [0] * 2019 # あまりは0～2018の2019個

ans = 0

modList[0] = 1 # 解答でいうT(n)=0 の場合

# 最大20万回ループ、時間かかるならＤＰする？
# ↓ではTLEになった
# for i in range(len(S)):
#     m = int(S[i:]) % 2019
#     modList[m] += 1

# ↓　これでもTLEになった
# T = 0
# for i in range(1,len(S)+1):
#     # T += int(S[-i]) * 10**i
#     T += int(S[-i]) * ((10**i) % 2019)
#     modList[T % 2019] +=1

T = 0
a = 1
for s in S[::-1]:
    T = T+int(s) * a
    modList[T%2019]+=1
    a*=10
    a%=2019
#print(modList)

for j in modList:
    if j <= 1:
        continue
    else:
        ans += j*(j-1)/2

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

N, Q = map(int, input().split())
S = input()
minians = []
for i in range(N-1):
    if S[i:i + 2] == "AC":
        minians.append(i)
# print(minians)
ans = [0]*Q
for i in range(Q):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    ans[i] = sum(left <= mini < right for mini in minians)
    """for j in range(len(minians)):
        if left <= minians[j] and minians[j] < right:
            ans[i] += 1
        elif minians[j] >= right:
            break"""
print('\n'.join(map(str, ans)))


### FIXED CODE ###

import bisect
N, Q = map(int, input().split())
S = input()
minians = []
for i in range(N-1):
    if S[i:i + 2] == "AC":
        minians.append(i)
# print(minians)
ans = [0]*Q
for i in range(Q):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    """print("\n", bisect.bisect_left(minians, right),
          bisect.bisect_left(minians, left))"""
    ans[i] = bisect.bisect_left(minians, right) - \
        bisect.bisect_left(minians, left)

    #ans[i] = sum(left <= mini < right for mini in minians)
    """for j in range(len(minians)):
        if left <= minians[j] and minians[j] < right:
            ans[i] += 1
        elif minians[j] >= right:
            break"""
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
count = 1

for i in range(1, n):
    new = p[:i]
    m = sorted(new)
    #print('{}, {}'.format(m[0],p[i]))
    if p[i] < m[0]:
        count += 1

print(count)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
min = 10 ** 100
count = 0


for i in range(n):
    if p[i] < min:
        min = p[i]
        count += 1

print(count)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
counter = Counter(a)
key = list(counter.keys())
value = list(counter.values())

s = sum(a)
q = int(input())

for i in range(q):
  b, c = map(int, input().split())
  if b in key:
    x = key.index(b)
    if c in key:
      y = key.index(c)
      s += (c - b) * value[x]
      value[y] += value[x]
      del key[x]
      del value[x]
    else:
      key[x] = c
      s += (c - b) * value[x]
  else:
    pass
  print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [i for i in range(10 ** 5 + 2)]
m = [0] * (10 ** 5 + 2)
for i in a:
  m[i] += 1
s = sum(a)
q = int(input())
for i in range(q):
  b, c = map(int, input().split())
  if m[b] != 0:
    s += (c - b) * m[b]
    m[c] += m[b]
    m[b] = 0
  print(s)