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

def g(r, c):
    ret = 0
    for i in range(1, r + 2):
        ret += fact[i + c] * fact_inv[i] * fact_inv[c]
        ret %= mod

    return ret


r1, c1, r2, c2 = map(int, input().split())

mod = 10 ** 9 + 7
MAX = 2 * 10 ** 6 + 10

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
print(ans)


### FIXED CODE ###

def g(r, c):
    ret = 0
    for i in range(1, r + 2):
        ret += fact[i + c] * fact_inv[i] * fact_inv[c]
        ret %= mod

    return ret


r1, c1, r2, c2 = map(int, input().split())

mod = 10 ** 9 + 7
MAX = 2 * 10 ** 6 + 10

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
ans %= mod
print(ans)
### BUGGY CODE ###

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

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

res = [0]
tmp = 0

tf = [-1 for i in range(n)]
tf[0] = 0

for i in range(n):
    tmp = a[tmp] - 1
    if tf[tmp] != -1:
        start = tmp
        break
    else:
        res = res + [tmp]
        tf[tmp] = i+1

lenret = i+1
stridx = tf[start]

cycle = lenret - stridx

if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx

    tmp = k % cycle

    print(res[stridx+tmp]+1)


### FIXED CODE ###

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

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

res = [0]
tmp = 0

tf = [-1 for i in range(n)]
tf[0] = 0

for i in range(n):
    tmp = a[tmp] - 1
    if tf[tmp] != -1:
        start = tmp
        break
    else:
        res.append(tmp)
        tf[tmp] = i+1

lenret = i+1
stridx = tf[start]

cycle = lenret - stridx

if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx

    tmp = k % cycle

    print(res[stridx+tmp]+1)
### BUGGY CODE ###

from fractions import gcd
from sys import exit

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

l_gcd_list = [0]
r_gcd_list = [0]
for i in range(N):
    l_gcd_list.append(gcd(l_gcd_list[i], A[i]))
    r_gcd_list.insert(0, gcd(r_gcd_list[0], A[-(i+1)]))
# print(l_gcd_list)
# print(r_gcd_list)

result = 0
for i in range(N):
    result = max(result, gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(result)


### FIXED CODE ###

from fractions import gcd
from sys import exit

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

l_gcd_list = [0]
r_gcd_list = [0]
for i in range(N):
    l_gcd_list.append(gcd(l_gcd_list[i], A[i]))
    r_gcd_list.append(gcd(r_gcd_list[i], A[-(i+1)]))
r_gcd_list = r_gcd_list[::-1]
# print(l_gcd_list)
# print(r_gcd_list)

results = []
for i in range(N):
    results.append(gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(max(results))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

for i in range(n):
    temp = a[i]
    a[i] = 0
    print(max(a))
    a[i] = temp


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

aa = sorted(a)
first = aa[-1]
second = aa[-2]

for i in range(n):
    if a[i] != first:
        print(first)
    else:
        print(second)
### BUGGY CODE ###

n=int(input())
dic={}
for i in range(n):
  a=input()
  if a not in dic.keys():dic[a]=1
  else:dic[a]+=1
dic_max=[k for k, v in dic.items() if v==max(dic.values())]
dic_s=sorted(dic_max)
[print(i) for i in dic_s]

### FIXED CODE ###

n=int(input())
dic={}
for i in range(n):
  a=input()
  if a not in dic.keys():dic[a]=1
  else:dic[a]+=1
max_value=max(dic.values())
dic_max=[k for k, v in dic.items() if v==max_value]
dic_s=sorted(dic_max)
[print(i) for i in dic_s]
### BUGGY CODE ###

import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 10**7+9
inf = 10**20

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

reverse = False
for i in range(q):
    l = input().split()
    if l[0]=="1":
        reverse = not(reverse)
    else:
        if l[1]=="1":
            if reverse:
                s += l[2][::-1]
            else:
                s = l[2] + s
        else:
            if reverse:
                s = l[2][::-1] + s
            else:
                s += l[2]

if reverse:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###

import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 10**7+9
inf = 10**20

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


sentou = ""
matubi = ""
reverse = False
for i in range(q):
    l = input().split()
    if l[0]=="1":
        reverse = not(reverse)
    else:
        if l[1]=="1":
            if reverse:
                matubi += l[2][::-1]
            else:
                sentou = l[2] + sentou
        else:
            if reverse:
                sentou = l[2][::-1] + sentou
            else:
                matubi += l[2]
    #print(sentou,s,matubi)

if reverse:
    print(matubi[::-1] + s[::-1] + sentou[::-1])
else:
    print(sentou + s + matubi)
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    F = list(map(int, input().split()))
    F.sort(reverse=True)
    H = []
    for i in range(N):
        heapq.heappush(H, [-A[i] * F[i], A[i], F[i]])

    while K > 0:
        m1 = heapq.heappop(H)
        m2 = heapq.heappop(H)
        if m1[0] == 0:
            break
        while m1[1] * m1[2] >= m2[1] * m2[2]:
            m1[1] -= 1
            K -= 1
            if K == 0:
                break
        heapq.heappush(H, [-m1[1] * m1[2], m1[1], m1[2]])
        heapq.heappush(H, m2)

    print(-min(H)[0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


# 解説AC
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)


def check(mid):
    k = K
    # 全員が目標値 mid を下回るまで修行できるか？
    for i in range(N):
        if A[i] * F[i] > mid:
            # x: 必要な修行回数
            x = A[i] - mid // F[i]
            k -= x
            # 誰かが修行できなかった ⇒ その目標値は達成不可能
            if k < 0:
                return False
    return True


def main():
    H = []
    for i in range(N):
        H.append(A[i]*F[i])
    # lb := 条件を満たさない最大, ub := 条件を満たす最小
    lb, ub = -1, max(H)
    while ub - lb > 1:
        mid = (lb + ub)//2
        if check(mid):
            ub = mid
        else:
            lb = mid
    print(ub)


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

N, K = map(int, input().split())
h = [i for i in map(int, input().split())]

dp = [0]*N
for i in range(1,N):
    start = max(0,i-K)
    dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(start,i)])
print(dp[-1])

### FIXED CODE ###

def calc_dp():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0]*N
    for i in range(1,N):
        start = max(0,i-K)
        dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(start,i)])
    print(dp[-1])

if __name__ == "__main__":
    calc_dp()
### BUGGY CODE ###


n = int(input())
 
dx =[-1, 0, 1]
 
l = [0]
i = 0
 
while(n not in l):
    i += 1
    l = list(set(l))
    for j in range(len(l)):
        a = l[0]
        l.remove(l[0])
        for k in range(3):
            l.append(a + dx[k]*i)
 
 
print(i)


### FIXED CODE ###

import math
n = int(input())
print(math.ceil((-1+(1+8*n)**(1/2))/2))
### BUGGY CODE ###

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

for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

from collections import Counter


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



c=Counter(a)
ck=set(Counter(a).keys())
for i in range(1,n+1):
    if i in ck:
        print(c[i])
    else:
        print(0)
### BUGGY CODE ###

h, w, n = map(int, input().split())
a = [None] * n
s = set()
for i in range(n):
    y, x = map(int, input().split())
    a[i] = (y - 1, x - 1)
    s.add((y -1 , x - 1))
t = set()
e = [0] * 10
c = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
d = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
for i in range(n):
    y, x = a[i]
    for j in range(9):
        y2 = y + c[j]
        x2 = x + d[j]
        if y2 <= 0 or x2 <= 0 or y2 >= h - 1 or x2 >= w - 1: continue
        z = 0
        if (y2, x2) in t: continue
        t.add((y2, x2))
        for k in range(9):
            y3 = y2 + c[k]
            x3 = x2 + d[k]
            if (y3, x3) in s: z += 1
        e[z] += 1
print(((h - 2) * (w - 2)) - sum(e))
for i in range(1, 10): print(e[i])


### FIXED CODE ###

h, w, n = map(int, input().split())
a = [None] * n
s = set()
for i in range(n):
    y, x = map(int, input().split())
    a[i] = (y - 1, x - 1)
    s.add((y -1 , x - 1))
t = set()
e = [0] * 10
c = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
d = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
for i in range(n):
    y, x = a[i]
    for j in range(9):
        y2 = y + c[j]
        x2 = x + d[j]
        if y2 <= 0 or x2 <= 0 or y2 >= h - 1 or x2 >= w - 1: continue
        z = 0
        if (y2, x2) in t: continue
        t.add((y2, x2))
        for k in range(9):
            y3 = y2 + c[k]
            x3 = x2 + d[k]
            if (y3, x3) in s: z += 1
        e[z] += 1
print(((h - 2) * (w - 2)) - sum(e))
for i in range(1, 10): print(e[i])
### BUGGY CODE ###

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

dp = [float('inf') for _ in range(n)]
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i + j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h_ls[i+j] - h_ls[i]))
print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf') for _ in range(n)]
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i + j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h_ls[i+j] - h_ls[i]))
print(dp[-1])
### BUGGY CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
#print(a)

ans_a = a[n-1]
maxi = 0
idx = 0
for i in enumerate(a):
    val = max(maxi, combinations_count(ans_a, i[1]))
    if maxi < val:
        idx = i[0]
        maxi = val
    #print(idx, maxi)

ans_b = a[idx]
print(ans_a, ans_b)


### FIXED CODE ###

import math
import numpy

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def get_nearest(li, num):
    index = numpy.abs(numpy.asarray(li) - num).argmin()
    return li[index]

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

if n == 2:
    print(max(a), 0)
    exit()

ans_a = max(a)
ans_b = get_nearest(a, ans_a/2)

print(ans_a, ans_b)
### BUGGY CODE ###

def main():
    N,W=map(int,input().split())
    dp=[0]*(W+1)
    for _ in range(1,N+1):
        w,v=map(int,input().split())
        for i in range(W+1)[::-1]:
            if w<=i:
                can1=max(dp[j] for j in range(i-w+1))
                can2=max(dp[j] for j in range(i-w+1,i+1))
                dp[i]=max(can1+v,can2)
            else:
                break
    print(dp[-1])
main()

### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
dp=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
limit = 100000
mod = 10**9+7
lpow = [False] * (limit+1)
lpow[0] = 1
def pow(n,p):
    if p<0:return 0
    if lpow[p]:
        return lpow[p]
    else:
        if p % 2 == 0:
            return pow(n,p//2)**2
        else:
            return (pow(n,p//2)**2)*n

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()

### FIXED CODE ###

mod = 10**9+7
def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def main():
    s=input()
    res = 0
    ca = 0
    cc = s.count("C")
    cw = 0
    aw = s.count("?")
    for c in s:
        if c == "A":
            ca += 1
        elif c == "C":
            cc -= 1
        elif c == "B":
            res += ca*cc*pow(3,aw)+ca*(aw-cw)*pow(3,aw-1)+cw*cc*pow(3,aw-1)+cw*(aw-cw)*pow(3,aw-2)
            res %= mod
        elif c == "?":
            res += ca*cc*pow(3,aw-1)+ca*(aw-cw-1)*pow(3,aw-2)+cw*cc*pow(3,aw-2)+cw*(aw-cw-1)*pow(3,aw-3)
            res %= mod
            cw += 1

    print(res)

main()
### BUGGY CODE ###

def main():
    s = input()
    n = len(s)
    ans = [0 for i in range(n)]
    for i in range(n):
        p = i
        if s[i]=='R':
            while s[p]=='R':
                p += 1
            if (p-i)%2==0:
                ans[p] += 1
            else:
                ans[p-1] += 1
        else:
            while s[p]=='L':
                p -= 1
            if (i-p)%2==0:
                ans[p] += 1
            else:
                ans[p+1] += 1
    print(' '.join(list(map(str,ans))))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import bisect
    s = input()
    n = len(s)
    ans = [0 for i in range(n)]
    R = []
    L = []
    E = []
    for i in range(n):
        if s[i]=='R' and s[i+1]=='L':
            R.append(i)
        elif s[i]=='L' and s[i-1]=='R':
            L.append(i)
        else:
            E.append(i)
    for i in range(len(E)):
        if s[E[i]]=="R":
            p = bisect.bisect_left(L,E[i])
            if (L[p]-E[i])%2==0:
                ans[L[p]]+=1
            else:
                ans[L[p]-1]+=1
        else:
            p = bisect.bisect_right(R,E[i])
            if (E[i]-R[p-1])%2==0:
                ans[R[p-1]]+=1
            else:
                ans[R[p-1]+1]+=1
    for r in R:
        ans[r]+=1
    for l in L:
        ans[l]+=1
    print(' '.join(list(map(str,ans))))

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

import numpy as np
n = int(input())
a = np.array([int(c) for c in input().split()], dtype=int)
c = np.zeros((n,), dtype=int)
for i in range(a.shape[0]):
    c[a[i]-1]+=1
count = (c * (c-1) / 2).sum()
for i in range(a.shape[0]):
    pp = c[a[i]-1]
    print(int(count - pp * (pp - 1) / 2 + (pp-1) * (pp-2) / 2))

### FIXED CODE ###

n = int(input())
a = [int(c) for c in input().split()]
c = [0 for _ in range(n)]
for i in range(n):
    c[a[i]-1]+=1
count = sum(c[i] * (c[i]-1) / 2 for i in range(n))
for i in range(n):
    pp = c[a[i]-1]
    print(int(count - pp * (pp - 1) / 2 + (pp-1) * (pp-2) / 2))
### BUGGY CODE ###

def CalAbs(a, b):
    sol=a-b
    if sol<0:
        sol=sol*(-1)
    return sol

input_line = input().split(" ")
N=int(input_line[0])
K=int(input_line[1])

rec=10**18+1
i=0

while i<10**19:
    if rec>N:
        rec=N
    N=CalAbs(N,K)
    i=i+1
print(rec)


### FIXED CODE ###

#絶対値を求める関数
def CalAbs(a, b):
    sol=a-b
    if sol<0:
        sol=sol*(-1)
    return sol
    
#桁数を求める関数    
def CalDigi(a):    
    digi=1
    flag=0
    while flag==0:
        a=a/10
        if a>=1:
            digi=digi+1
        else:
            flag=1
    return digi
    
#標準入力
input_line = input().split(" ")
N=int(input_line[0])
K=int(input_line[1])

rec=10**18+1

#Nが大きすぎる時、Kの倍数でそぎ落とす
N=N%K+K


i=0
times=100
count=0
while i<=times:
    if rec>N:
        rec=N
    N=CalAbs(N,K)
    if i==times:
     lastN=N
    i=i+1
if rec>N:
    rec=N
    

    

print(rec)
### BUGGY CODE ###

n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    for i, c in enumerate(map(int, s)):
        k = (c * (10**i) + k) % p
        cnt[k] += 1

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)


### FIXED CODE ###

n, p = map(int, input().rstrip().split())
s = input().rstrip()

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    w = 1
    for i, c in enumerate(map(int, s)):
        k = c * w + k
        w *= 10
        while k >= p:
            k -= p
        while w >= p:
            w -= p
        cnt[k] += 1

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())

ans = 0
for _ in range(K):
    if A > 0:
        ans += 1
        A -= 1
    elif B > 0:
        B -= 1
    elif C > 0:
        ans -= 1
        C -= 1

print(ans)

### FIXED CODE ###

A, B, C, K = map(int, input().split())

ans = 0
if K >= A:
    ans += A
    K -= A
else:
    ans += K
    K = 0

if K > 0 and B > 0:
    if K >= B:
        K -= B
    else:
        K = 0

if K > 0 and C > 0:
    if K >= C:
        K -= C
        ans -= C
    else:
        ans -= K
        K = 0

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

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

import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W, M = map(int, input().split())
h = [] * M
w = [] * M
dic_combi = defaultdict(int)

for _ in range(M):
    h_, w_ = map(int, input().split())
    h.append(h_)
    w.append(w_)
    dic_combi[h_ * (10**6) +  w_]=1

dic_h = Counter(h)
dic_w = Counter(w)
# print(dic_h, dic_w)
max_h_key = max(dic_h.items(), key=lambda x:x[1])[0]
max_w_key = max(dic_w.items(), key=lambda x:x[1])[0]

max_h = dic_h[max_h_key]
max_w = dic_w[max_w_key]

keys_h = [k for k, v in dic_h.items() if v == max_h]
keys_w = [k for k, v in dic_w.items() if v == max_w]


def get_num(ind_h, ind_w):
    ret = 0
    for i in range(M):
        if h[i] == ind_h or w[i] == ind_w:
           ret += 1
    return ret


ans = 0
for ind_h in keys_h:
    for ind_w in keys_w:
        # ret = get_num(ind_h, ind_w)
        ret = max_h + max_w
        if dic_combi[ind_h*(10**6) + ind_w] == 1:
            ret -= 1
        ans = max(ans, ret)

print(ans)






### FIXED CODE ###

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

import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W, M = map(int, input().split())
h = [] * M
w = [] * M
dic_combi = defaultdict(int)

for _ in range(M):
    h_, w_ = map(int, input().split())
    h.append(h_)
    w.append(w_)
    dic_combi[h_ * (10**6) +  w_]=1

dic_h = Counter(h)
dic_w = Counter(w)
# print(dic_h, dic_w)
max_h_key = max(dic_h.items(), key=lambda x:x[1])[0]
max_w_key = max(dic_w.items(), key=lambda x:x[1])[0]

max_h = dic_h[max_h_key]
max_w = dic_w[max_w_key]

keys_h = [k for k, v in dic_h.items() if v == max_h]
keys_w = [k for k, v in dic_w.items() if v == max_w]


ans = 0
for ind_h in keys_h:
    for ind_w in keys_w:
        ret = max_h + max_w
        if dic_combi[ind_h*(10**6) + ind_w] == 1:
            ret -= 1
        else:
            print(ret)
            sys.exit()
        ans = max(ans, ret)

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

S = input().strip()
Q = int(input())
for i in range(Q):
  query = [j for j in input().strip().split()]
  T = int(query[0])
  if T == 1:
    S = S[::-1]
  else:
    F, C = int(query[1]), query[2]
    if F == 1:
      S = C + S
    else:
      S = S + C
print(S)


### FIXED CODE ###

S = input().strip()
Q = int(input())
is_reverse = False
A = ""
B = ""
for i in range(Q):
  query = [j for j in input().strip().split()]
  T = int(query[0])
  if T == 1:
    is_reverse = not is_reverse
  else:
    F, C = int(query[1]), query[2]
    if F == 1:
      if not is_reverse:
        A = C + A
      else:
        B = B + C
    else:
      if not is_reverse:
        B = B + C
      else:
        A = C + A

res = A + S + B
if not is_reverse:
  print(res)
else:
  print(res[::-1])
### BUGGY CODE ###

N,K=map(int,input().split())
mod=10**9+7

import math
SQ=int(math.sqrt(N))

DP1=[1]*(SQ+1)
DP1[0]=0


DP2=[]

k=SQ

for i in range(SQ,0,-1):
    DP2.append(N//i-k)
    k=N//i


KOSUU2=[v for v in DP2]

#print(DP1)
#print(DP2)
#print()

for j in range(K-1):
    NDP1=[0]*(SQ+2)
    NDP2=[0]*(SQ+1)

    for j in range(1,SQ+1):
        NDP2[-j]-=DP1[j]
        NDP1[1]+=DP1[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(-1,-SQ-1,-1):
        NDP1[-j+1]-=DP2[j]
        NDP1[1]+=DP2[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(1,SQ+2):
        NDP1[j]+=NDP1[j-1]

    NDP2[0]+=NDP1[-1]

    for j in range(1,SQ+1):
        NDP2[j]+=NDP2[j-1]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(SQ):
        NDP2[j]=NDP2[j]*KOSUU2[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    DP1=[n%mod for n in NDP1[:SQ+1]]
    DP2=[n%mod for n in NDP2[:SQ]]

    
print((sum(DP1)+sum(DP2))%mod)


### FIXED CODE ###

N,K=map(int,input().split())
mod=10**9+7

import math
SQ=int(math.sqrt(N))

DP1=[1]*(SQ+1)
DP1[0]=0


DP2=[]

k=SQ

for i in range(SQ,0,-1):
    DP2.append(N//i-k)
    k=N//i


KOSUU2=[v for v in DP2]

#print(DP1)
#print(DP2)
#print()

for j in range(K-1):
    NDP1=[0]*(SQ+2)
    NDP2=[0]*(SQ+1)

    for j in range(1,SQ+1):
        NDP2[-j]-=DP1[j]
        NDP1[1]+=DP1[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(-1,-SQ-1,-1):
        NDP1[-j+1]-=DP2[j]
        NDP1[1]+=DP2[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(1,SQ+2):
        NDP1[j]+=NDP1[j-1]

    NDP2[0]+=NDP1[-1]

    for j in range(1,SQ+1):
        NDP2[j]+=NDP2[j-1]

    #print(NDP1)
    #print(NDP2)
    #print()

    for j in range(SQ):
        NDP2[j]=NDP2[j]*KOSUU2[j]

    #print(NDP1)
    #print(NDP2)
    #print()

    DP1=[n%mod for n in NDP1[:SQ+1]]
    DP2=[n%mod for n in NDP2[:SQ]]

    
print((sum(DP1)+sum(DP2))%mod)