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

def f(point):
    k = K
    for i in range(N):
        a = A[i]
        f = F[i]
        if a*f > point:
            k -= a - point//f
        if k < 0:
            return False
    # print(point, k)
    return True

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
l = -1
r = 10**18+1
while (r-l) > 1:
    mid = (r+l)//2
    if f(mid):
        r = mid
    else:
        l = mid
print(r)


### FIXED CODE ###

def f(point):
    k = K
    for i in range(N):
        a = A[i]
        f = F[i]
        if a*f > point:
            k -= a - point//f
        if k < 0:
            return False
    # print(point, k)
    return True

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
l = -1
r = 10**18+1
while (r-l) > 1:
    mid = (r+l)//2
    if f(mid):
        r = mid
    else:
        l = mid
print(r)
### BUGGY CODE ###

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

ypi = []
ipy = []
for i in range(M):
    p, y = map(int,input().split())
    ypi.append([y, p, i])
    ipy.append([i, p, y])

ypi.sort()

rank = [[] for i in range(N)]

for count in range(M):
    y, p, i = ypi[count]
    rank[p-1].append([i, p, y])

for count in range(M):
    i, p, y = ipy[count]
    ansp = p
    ansy = rank[p-1].index([i, p, y]) + 1

    print('{:06}'.format(ansp)+'{:06}'.format(ansy))

### FIXED CODE ###

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

ypi = []

for i in range(M):
    p, y = map(int,input().split())
    ypi.append([y, p, i])

ypi.sort()

rank = [0] * N

ans = [''] * M
for count in range(M):
    y, p, i = ypi[count]
    rank[p-1] += 1
    ans[i] = '{:06}'.format(p)+'{:06}'.format(rank[p-1])

for s in ans:
    print(s)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1000
for ii in range(2 ** n):
    for jj in range(2 ** n):
        tmp = 1000
        kab = 0
        for i in range(n):
            if (ii >> i) & 1:  # buy
                if tmp < A[i]:
                    break
                kab += tmp // A[i]
                tmp = tmp % A[i]

            if (jj >> i) & 1:  # sell
                if kab == 0:
                    break
                tmp += kab * A[i]
                kab = 0
        else:
            ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1000
for i in range(n - 1):
    if A[i] < A[i + 1]:
        ans += ans // A[i] * (A[i + 1] - A[i])
print(ans)
### BUGGY CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys
import bisect
from operator import itemgetter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    a = tuple(_ia())
    l = {}
    for i, ai in enumerate(a):
        aip = ai + i + 1
        l[aip] = l.get(aip, 0) + 1
    r = tuple(sorted(i+1-ai for i, ai in enumerate(a)))
    li = 0
    ans = 0
    for k, v in sorted(l.items(), key=itemgetter(0)):
        r = r[li:]
        li = bisect.bisect_right(r, k)
        ans += v * (li - bisect.bisect_left(r, k))
        if li >= n:
            break
    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
from collections import Counter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = sys.stdin.readline()
    a = list(_ia())
    l = Counter(ai+i+1 for i, ai in enumerate(a))
    r = Counter(i+1-ai for i, ai in enumerate(a))
    return sum(v*r.get(k, 0) for k, v in l.items())


if __name__ == "__main__":
    print(main())
### BUGGY CODE ###

def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    ans=sum(a)
    q=int(input())
    a_dict = {}
    for i in set(a):
        a_dict[str(i)] = 0
    for j in a:
        a_dict[str(j)] += 1
    ch=list(a_dict.keys())
    for _ in range(q):
        b,c = map(str, input().split())
        if b in ch:
            d = a_dict[b]
            a_dict[b]=0
            if c in ch:
                a_dict[c] += d
            else:
                a_dict[c] = d
                ch.append(c)
            ans=ans-d*(int(b)-int(c))
            print(ans)
        else:
            print(ans)
resolve()

### FIXED CODE ###

def resolve():
    n=int(input())
    ac = list(map(int, input().split()))
    ans=sum(ac)
    q=int(input())
    a=[0]*(10**5+1)
    for i in ac:
        a[i]+=1
    for _ in range(q):
        b,c = map(int, input().split())
        g=a[b]
        a[b]=0
        a[c]+=g

        ans=ans-g*(b-c)
        print(ans)
resolve()
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    c = 1
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
            c = c * (cnt + 1)

    if temp != 1:
        arr.append([temp, 1])
        c = c * (1 + 1)

    if arr == []:
        arr.append([n, 1])
        c = c * (1 + 1)

    return c


n = int(input())
ans = 0
for i in range(1, n):
    ans += factorization(n - i)
print(ans - 1)


### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
    ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

from collections import defaultdict
H, W, M = map(int, input().split())
tate = defaultdict(int)
yoko = defaultdict(int)
T = {}
for i in range(M):
    h, w = map(int, input().split())
    tate[h-1] += 1
    yoko[w-1]+= 1
    T[(h-1, w-1)] = 1

tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_m = tate[0][1]
yoko_m = yoko[0][1]
ans = 0
for i in range(len(tate)):
    if tate[i][1] == tate_m:
        for j in range(len(yoko)):
            if yoko[j][1] == yoko_m:
                if (tate[i][0], yoko[j][0]) in T:
                    ans = max(ans, tate_m + yoko_m - 1)
                else:
                    ans = max(ans, tate_m + yoko_m)
            elif yoko[j][1] == yoko_m - 1:
                if (tate[i][0], yoko[j][0]) in T:
                    ans = max(ans, tate_m + yoko_m - 2)
                else:
                    ans = max(ans, tate_m + yoko_m - 1)
            else:
                break
    elif tate[i][1] == tate_m - 1:
        for j in range(len(yoko)):
            if yoko[j][1] == yoko_m:
                if (tate[i][0], yoko[j][0]) in T:
                    ans = max(ans, tate_m + yoko_m - 2)
                else:
                    ans = max(ans, tate_m + yoko_m - 1)
            else:
                break
    else:
        break
print(ans)

### FIXED CODE ###

from collections import defaultdict
H, W, M = map(int, input().split())
tate = defaultdict(int)
yoko = defaultdict(int)
T = {}
for i in range(M):
    h, w = map(int, input().split())
    tate[h-1] += 1
    yoko[w-1]+= 1
    T[(h-1, w-1)] = 1

tate = sorted(tate.items(), key=lambda x:x[1], reverse=True)
yoko = sorted(yoko.items(), key=lambda x:x[1], reverse=True)
tate_m = tate[0][1]
yoko_m = yoko[0][1]
ans = 0
for i in range(len(tate)):
    if ans == tate_m + yoko_m:
        break
    if tate[i][1] == tate_m:
        for j in range(len(yoko)):
            if yoko[j][1] == yoko_m:
                if (tate[i][0], yoko[j][0]) in T:
                    ans = max(ans, tate_m + yoko_m - 1)
                else:
                    ans = max(ans, tate_m + yoko_m)
            else:
                break
    else:
        break
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
p = [0] * m
y = [0] * m

d = {}

for i in range(m):
    p[i], y[i] = map(int, input().split())

    if not p[i] in d:
        d[p[i]] = []

    d[p[i]].append(y[i])

for v in d.values():
    v.sort()

for i in range(m):
    print("{:06}{:06}".format(p[i], d[p[i]].index(y[i]) + 1))


### FIXED CODE ###

from operator import itemgetter


n, m = map(int, input().split())
p = [0] * m
y = [0] * m

d = {}

for i in range(m):
    p[i], y[i] = map(int, input().split())

    if not p[i] in d:
        d[p[i]] = []

    d[p[i]].append([y[i], i])

for v in d.values():
    v.sort(key=itemgetter(0))

ans = [None] * m

for k, v in d.items():
    for i, vv in enumerate(v):
        ans[vv[1]] = str(k).zfill(6) + str(i + 1).zfill(6)

print("\n".join(ans))
### BUGGY CODE ###

import heapq
import copy
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
heapq.heapify(AB)

work = [0 for i in range(M)]
for i in range(1,M+1):
    AB2 = copy.deepcopy(AB)
    heapq.heapify(AB2)
    while AB2:
        b,a = heapq.heappop(AB2)
        b = -b
        if a <= i:
            work[i-1] = b
            AB.remove([-b,a])
            break
print(sum(work))

### FIXED CODE ###

import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
heapq.heapify(AB2)
for i in range(1,M+1):
    for j in AB[i]:
        heapq.heappush(AB2,j)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)
### BUGGY CODE ###

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

l = [0] * 1000 # 000 to 999
for i in range(n - 2): # i桁目 を残す
  for j in range(i + 1, n - 1):
    for k in range(j + 1, n):
      password = s[i] + s[j] + s[k]
      l[int(password)] = 1

print(l.count(1))



### FIXED CODE ###

n = int(input())
S = input()

result = 0
for i in range(10):
  if str(i) in S:
    T = S[S.index(str(i))+1:]

    for j in range(10):
      if str(j) in T:
        U = T[T.index(str(j))+1:]

        for k in range(10):
          if str(k) in U:
            result += 1

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

a,b,k = map(int, input().split())

count = 0

for _ in range(k):
  if a>=1:
    a -= 1
  elif a==0 and b >= 1:
      b -= 1

print(a, b)


### FIXED CODE ###

a,b,k=map(int,input().split())
print(max(a-k,0),max(0,b-max(k-a,0)) )
### BUGGY CODE ###

K = int(input())
S = input()
S = len(S)


mod = 10**9 + 7

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

from collections import deque

kaijou = 1
fact = [1]
for k in range(1, K + S+1):
  kaijou = kaijou * k % mod
  fact.append(kaijou)

fact_k = deque(fact[:K+1])
fact_ks = deque(fact[S-1:])


list26 = deque([1])
list25 = deque([1])
now26 = 26
now25 = 25
for k in range(K):
  list25.append(now25)
  list26.append(now26)
  now25 = now25*25%mod
  now26 = now26*26%mod


ans = 0
for k in range(K+1):
  now = list26.pop()
  now = now * list25.popleft() % mod
  now = now * fact_ks.popleft() % mod
  now = now * modinv(fact_k.popleft()) %mod
  ans += now
  ans %= mod


ans *= modinv(fact[S-1])
ans %= mod
print(ans)


### FIXED CODE ###

K = int(input())
S = input()
S = len(S)


mod = 10**9 + 7

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

from collections import deque

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, K + S + 1):
  fact.append((fact[-1] * i) % mod)
  if i < K+2:
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

factinv_k = deque(factinv[:K+1])
fact_ks = deque(fact[S-1:])


list26 = deque([1])
list25 = deque([1])
now26 = 26
now25 = 25
for k in range(K):
  list25.append(now25)
  list26.append(now26)
  now25 = now25*25%mod
  now26 = now26*26%mod


ans = 0
for k in range(K+1):
  now = list26.pop()
  now = now * list25.popleft() % mod
  now = now * fact_ks.popleft() % mod
  now = now * factinv_k.popleft() %mod
  ans += now
  ans %= mod


ans *= modinv(fact[S-1])
ans %= mod
print(ans)
### BUGGY CODE ###

while True:
    n = input()
    if n == 0: break
    ans = [0,0,0,0,0,0,0]
    for i in range(n):
        age = input()
        if age <= 9:
            ans[0] = ans[0]+1
        elif age <= 19:
            ans[1] = ans[1]+1
        elif age <= 29:
            ans[2] = ans[2]+1
        elif age <= 39:
            ans[3] = ans[3]+1
        elif age <= 49:
            ans[4] = ans[4]+1
        elif age <= 59:
            ans[5] = ans[5]+1
        else:
            ans[6] = ans[6]+1
    else:
        for c in ans:
            print c

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break
    ans = [0 for i in range(7)]
    for i in xrange(n):
        age = int(raw_input())
        if age <= 9:
            ans[0] += 1
        elif age <= 19:
            ans[1] += 1
        elif age <= 29:
            ans[2] += 1
        elif age <= 39:
            ans[3] += 1
        elif age <= 49:
            ans[4] += 1
        elif age <= 59:
            ans[5] += 1
        else:
            ans[6] += 1
    for c in ans:
        print c
### BUGGY CODE ###

import re

i = int(input().split()[1])
s = input()
k = 0
result = []

while k < i:
    ft, et = [int(n) for n in input().split()]
    result.append(len(re.findall("AC", s[ft - 1:et])))
    k += 1

for kekka in result:
    print(kekka)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
s = input()

count = [0]
for i in range(1, n):
    count.append(count[i-1])
    if(s[i-1:i+1] == "AC"):
        count[i] += 1

# print(count)

for _ in range(q):
    l, r = map(int, input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

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

for i in range(n):
    nums[i] -= (i + 1)
    if i == 0:
        x = y =  nums[i]
    else:
        if nums[i] < x:
            x = nums[i]
        elif y < nums[i]:
            y = nums[i]

d = 0
for i in range(x, y):
    c = 0
    for j in range(n):
        c += abs(nums[j] - i)
    else:
        if d != 0 and d < c:
            print(d)
            break
        elif d == 0 and c == 0:
            print(d)
            break
        else:
            d = c
else:
    print(d)
            
    


### FIXED CODE ###

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

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

nums.sort()
        
if (n-1) % 2 != 0:
    m = n//2 - 1
else:
    m = (n-1)//2
    
a = sum(nums[m+1:]) - (n-m-1)*nums[m]
b = - sum(nums[0:m+1]) + (m+1)*nums[m]

print(a+b)
### BUGGY CODE ###

from functools import lru_cache
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(amari, keta):
    if keta == lens - 1:
        if S[keta] == "?":
            cnt = 0
            for i in range(9, -1, -1):
                if (amari + i) % 13 == 5:
                    cnt += 1
            return cnt
        else:
            if (amari + int(S[keta])) % 13 == 5:
                return 1
            else:
                return 0
    else:
        if S[keta] == "?":
            x = 0
            for i in range(9, -1, -1):
                x += solve(amari + (i * pow(10, (lens - 1 - keta), 13)) % 13, keta + 1)
                x %= MOD
            return x
        else:
            return solve(amari + (int(S[keta]) * pow(10, (lens - 1 - keta), 13)) % 13, keta + 1) % MOD


print(solve(0, 0) % MOD)


### FIXED CODE ###


S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = ord(S[i - 1]) - ord('0')

    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD


print(dp[S_len][5] % MOD)
### BUGGY CODE ###

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

for i in range(1,a):
  switch = 0
  for j in range(i-1,-1,-1):
    if b[i] > b[j]:
      switch = 1
      break
  if switch != 1:
    c += 1
print(c)
      
      
  

### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
c = 1
k = b[0]
for i in range(1,a):
  if k>b[i]:
  	
  	k = b[i]
  	c+=1
print(c)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
num = [0 for i in range(N)]
zu = []
ans = []
for i in A:
    num[i-1]+=1
for i in range(N):
    temp = 1/2*num[i]*(num[i]-1)
    zu.append(int(temp))
for i in A:
    num[i-1]-=1
    temp = zu[i-1]
    zu[i-1] = 1/2*num[i-1]*(num[i-1]-1)
    print(int(sum(zu)))
    zu[i-1] = temp
    num[i-1]+=1


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
num = [0 for i in range(N)]
zu = 0
ans = []
for i in A:
    num[i-1]+=1
for i in range(N):
    temp = 1/2*num[i]*(num[i]-1)
    zu += temp
for i in A:
    kawari =zu
    temp1 = 1/2*num[i-1]*(num[i-1]-1)
    num[i-1] -= 1
    temp2 = 1/2*num[i-1]*(num[i-1]-1)
    kawari += -temp1+temp2
    num[i-1] += 1
    print(int(kawari))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

ans = 0
# 文字列 s2 の末尾までを走査して、
# s1 にまだ表れていない文字があれば連結して、
# 連結後の s1 と、s2 から走査済みの文字を除いたものを返す
def func(s1, s2):
    global ans
    if s2 == "":
        return None
    for i,c in enumerate(s2):
        if c not in s1:
            ans += 1
            t1 = s1 + c
            t2 = s2[i+1:]
#            print(t1, t2, ans)
            func(t1, t2)

N = int(input())
S = input().strip()

func("", S)
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline

N = int(input())
S = input().strip()
h = {}
for c in S:
    if c in h:
        h[c] += 1
    else:
        h[c] = 1

ans = 1
for v in h.values():
    ans *= v+1
ans -= 1

print(ans%(10**9+7))
### BUGGY CODE ###

# 必要なライブラリのインポート
import queue


def f(x,y):
    if x < 0 or y < 0 or x >= r or y >= c:
        return False
    if m[x][y] == "#":
        return False
    elif not (x,y) in done:
        if (x,y) == (gx,gy):
            return True
        else:
            done.add((x,y))
            q.put((x,y))
            return False
    else:
        return False          

# FIFOキューの作成
q = queue.Queue()

r,c = map(int,input().split())
sx,sy = 1,1
gx,gy = r,c

sx -= 1
sy -= 1
gx -= 1
gy -= 1


m = ["" for _ in range(r)] 
sharp_counter = 0
for i in range(r):
    m[i] = input()
    sharp_counter += m[i].count("#")
    
    
q.put((sx,sy))
done = set()
counter = 1
while True:
    q_list = []
    for _ in range(q.qsize()):
        tx,ty = q.get()
        q_list.append((tx,ty))
        
    for one in q_list:
        tx,ty = one
        flags = [f(tx,ty-1),f(tx,ty+1),f(tx-1,ty),f(tx+1,ty)]
        if sum(flags) == 1:
            print(r*c -sharp_counter -(counter-1)-2)
            break
            
    if sum(flags) == 1:
        break
    else:
        counter += 1
        

### FIXED CODE ###

# 必要なライブラリのインポート
import queue


def f(x,y):
    if x < 0 or y < 0 or x >= r or y >= c:
        return False
    if m[x][y] == "#":
        return False
    elif not (x,y) in done:
        if (x,y) == (gx,gy):
            return True
        else:
            done.add((x,y))
            q.put((x,y))
            return False
    else:
        return False          

# FIFOキューの作成
q = queue.Queue()

r,c = map(int,input().split())
sx,sy = 1,1
gx,gy = r,c

sx -= 1
sy -= 1
gx -= 1
gy -= 1


m = ["" for _ in range(r)] 
sharp_counter = 0
for i in range(r):
    m[i] = input()
    sharp_counter += m[i].count("#")
    
    
q.put((sx,sy))
done = set()
counter = 1
while True:
    q_list = []
    for _ in range(q.qsize()):
        tx,ty = q.get()
        q_list.append((tx,ty))
        
    for one in q_list:
        tx,ty = one
        flags = [f(tx,ty-1),f(tx,ty+1),f(tx-1,ty),f(tx+1,ty)]
        if sum(flags) == 1:
            print(r*c -sharp_counter -(counter-1)-2)
            break
            
    if sum(flags) == 1:
        break
    if q_list == []:
        print(-1)
        break
    else:
        counter += 1
### BUGGY CODE ###

m,n=map(int,raw_input().split())
N=n
M=10**9+7

ans=m
c=1
while n>1:
	ans=ans**2
	ans%=M
	n/=2
	c*=2

print ( ans*(m**(N-c)) )%M


### FIXED CODE ###

m,n=map(int,raw_input().split())
M=10**9+7

def a(m,n):
	N=n
	ans=m
	c=1
	while n>1:
		ans=ans**2
		ans%=M
		n/=2
		c*=2

	N=N-c
	return ans,N


x=m; y=n

ans=1
while y>1:
	x,y=a(m,y)
	ans=(ans*x)%M

if y==1:
	print (ans*m)%M
else:
	print ans
### BUGGY CODE ###

# https://drken1215.hatenablog.com/entry/2019/06/21/230200

def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *s, = map(int, input().split())
    *t, = map(int, input().split())

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N + 1):
        for j in range(M + 1):
            if j > 0:
                dp[i][j] += dp[i][j - 1]
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            if i > 0 and j > 0 and s[i - 1] != t[j - 1]:
                dp[i][j] -= dp[i - 1][j - 1]
            dp[i][j] %= MOD
    print(dp[N][M])


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://hiramekun.hatenablog.com/entry/2019/06/18/184256

def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *s, = map(int, input().split())
    *t, = map(int, input().split())

    dp = [[0] * (M + 1) for _ in range(N + 1)]  # (i,j)で丁度終わる文字列数
    dp[0][0] = 0
    dp[0][1] = 0
    dp[1][0] = 0

    acc = [[0] * (M + 1) for _ in range(N + 1)]
    acc[0][0] = 0
    acc[0][1] = 0
    acc[1][0] = 0

    for i, si in enumerate(s, 1):
        for j, ti in enumerate(t, 1):
            if si == ti:
                dp[i][j] = acc[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
            acc[i][j] = (acc[i - 1][j] + acc[i][j - 1] + dp[i][j] - acc[i - 1][j - 1]) % MOD

    ans = acc[N][M] + 1  # ("","")のケース

    print(ans)


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

n=int(input())
a=list(map(int,input().split()))
flag=0
cnt=0
for i in range(n):
    for j in range(n):
        if(i==j):
            continue
        if(a[i]%a[j]==0):
            cnt=cnt+1
            break
print(n-cnt)
    

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
set(a)
ans=[0]*1000005
x=1
for i in a:
    if(ans[i]!=0):
        ans[i]=2
        continue
    for j in range(i,1000005,i):
        ans[j]=ans[j]+1
cnt=0
for i in range(0,n):
    if(ans[a[i]]==1):
        cnt=cnt+1
print(cnt)
### BUGGY CODE ###

n, q = map(int, input().split())
processes = []
for i in range(n):
    name, time =  input().split()
    processes += [[name, int(time)]]

progress = 0

while len(processes):
    target = processes[0]
    if target[1] > q:
        target[1] -= q
        progress += q
        processes = processes[1:] + [target]
    else:
        progress += target[1]
        processes = processes[1:]
        print(target[0], progress)     

### FIXED CODE ###

import sys
n, q = map(int, sys.stdin.readline().split())
processes = []
for i in range(n):
    name, time =sys.stdin.readline().split()
    processes += [[name, int(time)]]

progress = 0

while len(processes):
    new_processes = []
    for target in processes:
        if target[1] > q:
            target[1] -= q
            progress += q
            new_processes += [target]
        else:
            progress += target[1]
            print(target[0], progress)
    processes = new_processes