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


def main():
    s = input()
    cnt = 0
    for i in range(len(s) - 3):
        for j in range(i + 3, len(s)):
            if int(s[i:j + 1]) % 2019 == 0:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter


def main():
    MOD = 2019
    s = input()
    n = len(s)
    t = [0] * (n + 1)
    # n-1,n-2,...,0
    for i in range(n - 1, -1, -1):
        t[i] = t[i + 1] + pow(10, n - i - 1, MOD) * int(s[i])
        t[i] %= MOD
    c = Counter(t)
    cnt = 0
    for v in c.values():
        cnt += v * (v - 1) // 2
    print(cnt)


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

N = int(input())
A = [int(input()) for _ in range(N)]

done_list = [1]
ans = 0
tmp = 1
while True:
    if A[tmp-1] in done_list:
        print(-1)
        exit(0)
    done_list.append(A[tmp-1])
    tmp = A[tmp-1]
    ans += 1
    if tmp == 2:
        print(ans)
        exit(0)

### FIXED CODE ###

N = int(input())
A = [0] + [int(input()) for _ in range(N)]

done = {}
ans = 0
now = A[1]
while True:
    ans += 1
    if now == 2:
        print(ans)
        exit(0)
    if done.get(now) == None:
        done[now] = True
        now = A[now]
    else:
        break
print(-1)
### BUGGY CODE ###

n = int(input())
tl = input().split()

l = [int(i) for i in tl]

mn = n

count = 0
for i in range(len(l)):
    if l[i] > mn:
        continue

    sl = l[0:i+1]
    mn = min(sl)
    count += 1

print(count)


### FIXED CODE ###

n = int(input())
tl = input().split()

l = [int(i) for i in tl]

mn = n

count = 0
mn_i = 0
for i in range(len(l)):
    if l[i] > mn:
        continue

    sl = l[mn_i:i+1]
    mn = min(sl)
    mn_i = i
    count += 1

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

n, q = map(int, input().split())
a = list(map(int, input().split()))
x = [int(input()) for _ in range(q)]
sort_x = sorted(x)
ans = {}
if n%2== 1:
    small_position = 0
    border_position = int((n-1)/2)
    sum_all = sum(a[border_position:])
    a.append(1000000000)
    a.append(1000000000)
    for x_i in sort_x:
        for compare in a[border_position:]:
            if x_i - a[small_position] > compare-x_i:
                sum_all = sum_all + a[small_position] - compare
                small_position += 2
                border_position += 1
                ans[x_i] = sum_all
            else:
                ans[x_i] = sum_all
                break

else:
    small_position = 1
    border_position = int(n/2)
    sum_all = sum(a[border_position:])
    a.append(1000000000)
    a.append(1000000000)
    for x_i in sort_x:
        for compare in a[border_position:]:
            if x_i - a[small_position] > compare-x_i:
                sum_all = sum_all + a[small_position] - compare
                small_position += 2
                border_position += 1
                ans[x_i] = sum_all
            else:
                ans[x_i] = sum_all
                break

for x_i in x:
    print(ans[x_i])


### FIXED CODE ###

n, q = map(int, input().split())
a = list(map(int, input().split()))
x = [int(input()) for _ in range(q)]
sort_x = sorted(x)
ans = {}
if n%2== 1:
    small_position = 0
    border_position = int((n-1)/2)
else:
    small_position = 1
    border_position = int(n/2)
sum_all = sum(a[border_position:])
a.append(10000000000)
a.append(10000000000)
x_index = 0
flag = False
for compare in a[border_position:]:
    compare_x = sort_x[x_index]
    small_a = a[small_position]
    while 2*sort_x[x_index] - small_a <= compare:
        ans[sort_x[x_index]] = sum_all
        x_index += 1
        if x_index == q:
            flag = True
            break
    sum_all = sum_all + small_a - compare
    small_position += 2
    if flag:
        break

for x_i in x:
    print(ans[x_i])
### BUGGY CODE ###

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

kotae = 1
for i in range(n):
    kotae *= a[i]

if(kotae > 10 ** 18):
    kotae = -1

print(kotae)

### FIXED CODE ###

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

kotae = 1
for i in range(n):
    if(kotae == -1):
        if(a[i] == 0):
            kotae = 0
    else:
        kotae *= a[i]
    if(kotae > 10 ** 18):
        kotae = -1

print(kotae)
### BUGGY CODE ###

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

import math

n = int(input())
seg = SegmentTree(n, math.gcd)

A = list(map(int,input().split()))
for i in range(n):
    seg.update(i, A[i])

ans = 1
for i in range(n):
    tmp = A[i]
    seg.update(i, A[i-1])
    ans = max(ans, seg.query(0,n))
    seg.update(i, tmp)
    
print(ans)

### FIXED CODE ###

from math import gcd as gcd
import numpy as np
N = int(input())
A = list(map(int,input().split()))

A = [0] + A + [0]

fromleft = np.array([0]*N)
fromright = np.array([0]*N)

for i in range(1,N):
    fromleft[i] = gcd(A[i],fromleft[i-1])
    fromright[-(i+1)] = gcd(A[-(i+1)],fromright[-i])

#print(fromleft)
#print(fromright)

ansgcd = [0]*N

for i in range(N):
    ansgcd[i] = gcd(fromright[i], fromleft[i])

print(max(ansgcd))
### BUGGY CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

d = []

for e1 in a:
  for e2 in b:
    d.append(e1+e2)

d.sort(reverse=True)
d = d[:k]
e = []

for e1 in d:
  for e2 in c:
    e.append(e1+e2)
    
e.sort(reverse=True)

for i in range(k):
  print(e[i])

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []

for e1 in a:
  for e2 in b:
    d.append(e1+e2)

d.sort(reverse=True)
d = d[:k]
e = []

for e1 in d:
  for e2 in c:
    e.append(e1+e2)
    
e.sort(reverse=True)

for i in range(k):
  print(e[i])
### BUGGY CODE ###

N = int(input())
a = []
for _ in range(N):
    a.append(int(input()))
tmp = 0
idx = 0
while idx < N:
    tmp, a[idx] = a[idx], tmp
    print(max(a))
    tmp, a[idx] = a[idx], tmp
    idx += 1


### FIXED CODE ###

N = int(input())
a = []
for _ in range(N):
    a.append(int(input()))
a_sorted = sorted(a)
max_a = a_sorted.pop()
second_a = a_sorted.pop()
if max_a == second_a:
    for _ in range(N):
        print(max_a)
else:
    idx = 0
    while idx < N:
        if a[idx] == max_a:
            print(second_a)
        else:
            print(max_a)
        idx += 1
### BUGGY CODE ###

import itertools

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    for x in range(N):
        tmp = [y for idx, y in enumerate(A) if idx != x]
        result = tuple(filter(lambda t: t[0] == t[1], itertools.combinations(tmp, 2)))
        print(len(result))


### FIXED CODE ###

import sys
import itertools
from collections import Counter
sys.setrecursionlimit(10**8)
if __name__ == "__main__":
    N = int(input())
    A = input().split()
    counter = Counter(A)
    result = 0
    for c in counter.values():
        result += c*(c-1)//2
    for a in A:
        k = counter[a]
        print(result - k*(k-1)//2 + (k-1)*(k-2)//2)
### BUGGY CODE ###

import copy

n = int(input())
A = []
for _ in range(n):
    a = list(map(int, input().split()))
    A.append(a)

Check = copy.deepcopy(A)

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

Graph_exist = True
for i in range(n):
    for j in range(n):
        if A[i][j] != Check[i][j]:
            Graph_exist = False

Road_exist = [[True for _ in range(n)] for _ in range(n)]
for i in range(n):
    Road_exist[i][i] = False

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j or i==k or j==k:
                continue
            if A[i][j] == (A[i][k] + A[k][j]):
                Road_exist[i][j] = False

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if Road_exist[i][j] == True:
            ans += A[i][j]

if Graph_exist == False:
    ans = -1
print(ans)

### FIXED CODE ###

import copy

n = int(input())
A = []
for _ in range(n):
    a = list(map(int, input().split()))
    A.append(a)

Check = copy.deepcopy(A)

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

Graph_exist = True
for i in range(n):
    for j in range(n):
        if A[i][j] != Check[i][j]:
            Graph_exist = False

Road_exist = [[True for _ in range(n)] for _ in range(n)]
for i in range(n):
    Road_exist[i][i] = False

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j or i==k or j==k:
                continue
            if A[i][j] == (A[i][k] + A[k][j]):
                Road_exist[i][j] = False

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if Road_exist[i][j] == True:
            ans += A[i][j]

if Graph_exist == False:
    ans = -1
print(ans)
### BUGGY CODE ###

def gcd(a, b):
  if a > b:
    min1, min2 = a, b
  else:
    min1, min2 = b, a
  if min2 == 0:
    return min1
  else:
    return gcd(min2, min1%min2)
N = int(input())
monster = list(map(int, input().split()))
monster.sort()
while len(monster) > 1:
  monster = [gcd(monster[i], monster[i+1]) for i in range(len(monster)-1)]
print(monster[0])

### FIXED CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
monster = list(map(int, input().split()))
print(reduce(gcd, monster))
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float('inf')] * n
    cost[0] = 0
    for i in range(1, n):
        for j in range(1, k + 1):
            if i - j < 0:
                break
            else:
                cost[i] = min(cost[i], cost[i - j] + abs(h[i] - h[i - j]))
    print(cost[n - 1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float('inf')] * n
    cost[0] = 0
    for i in range(1, n):
        for j in range(1, k + 1):
            if i - j < 0:
                break
            else:
                cost[i] = min(cost[i], cost[i - j] + abs(h[i] - h[i - j]))
    print(cost[n - 1])


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

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e+9 + 7)
a = sorted(a)

kai = [1]*(n+1)
gyaku = [1]*(n+1)

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

answer = 0
for i in range(n-k+1):
    for j in range(i+k-1,n):
        answer = (answer + ((a[j] - a[i])%mod * kai[j-i-1] *gyaku[j-i-1-(k-2)])%mod * gyaku[k-2])%mod

if k == 1:
    print(0)
else:
    print(answer)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e+9 + 7)
a = sorted(a)

kai = [1]*(n+1)
gyaku = [1]*(n+1)

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

answer = 0
for i in range(k-1,n):
    answer = (answer + a[i] * kai[i] * gyaku[(i)-(k-1)] * gyaku[k-1]) % mod

answer2 = 0
for i in range(n-k+1):
    answer2 = (answer2 + a[i] * kai[n-i-1] * gyaku[(n-i)-k] * gyaku[k-1]) % mod


if k == 1:
    print(0)
else:
    print((answer - answer2)%mod)
### BUGGY CODE ###

n, h = map(int, input().split())
a = []
b = []
for _ in range(n):
    a_i, b_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
b.sort()
ap = h - sum(b)
ans = ap // max(a)
h -= ans * max(a)

if h > sum(b):
    h -= max(a)
    ans += 1

while h > 0:
    attack = b.pop()
    if attack > max(a):
        h -= attack
        ans += 1
    else:
        b.append(attack)
        h -= max(a)
        ans += 1
print(ans)

### FIXED CODE ###

n, h = map(int, input().split())
a = []
b = []
for _ in range(n):
    a_i, b_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)

r = max(a)
key_b = 10**10

attack = []
for i in range(n):
    if a[i] == r:
        if b[i] < key_b:
            if key_b != 10**10:
                attack.append(key_b)
            key_b = b[i]
        else:
            attack.append(b[i])
    elif r < b[i]:
        attack.append(b[i])

ans = 0
attack.sort(reverse=True)
for bi in attack:
    if bi > key_b:
        h -= bi
        ans += 1
    elif h <= key_b:
        h -= key_b
        ans += 1
    else:
        h -= bi
        ans += 1

    if h <= 0:
        break

if 0 < h <= key_b:
    ans += 1
elif key_b < h:
    h -= key_b
    ans += 1

    if h % r == 0:
        ans += h // r
    else:
        ans += 1 + h // r

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

N = int(input())
ans = 0
for i in range(1, N + 1):
    a = i * (N // i) * (N // i + 1) / 2
    ans += round(a)
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N + 1):
    b = N // i
    ans += i * b * (b + 1) // 2
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]

c = Counter(s)
ans_number = c.most_common()[0][1]
    
s_max = []
for i in range(n):
  if s.count(s[i]) == ans_number:
    s_max.append(s[i])
    
s_max = list(set(s_max))
s_max.sort()
for i in range(len(s_max)):
  print(s_max[i])


### FIXED CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]

c = Counter(s)
c = c.most_common()
ans_number = c[0][1]
c.sort()

for i in range(len(c)):
  if c[i][1] == ans_number:
    print(c[i][0])
### BUGGY CODE ###

MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


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

if A < B:
    A, B = B, A

# n = 2 * min(K // A + 2, N + 1) + 3
n = min((K + A - 1) // A, N) + 1

lst = Factorial(N + 1, MOD) #O(N)
N_factrorial = lst.factorial(N)

def calc(a, b):
    tmp = 0
    G = min(a, b) #緑色の最大値
    # print ('G=', G)
    for green in range(G, -1, -1):
        red = a - green
        blue = b - green
        none_color = N - red - green - blue
        # print (red, green, blue, none_color)
        if none_color < 0:
            break
        tmp += ((((N_factrorial * lst.ifactorial(red) % MOD) * lst.ifactorial(green) % MOD) * lst.ifactorial(blue) % MOD) * lst.ifactorial(none_color) % MOD)
        tmp %= MOD
    # print ('tmp=', tmp)
    return tmp

def count(a, b):
    if a + b > 2 * N:
        return 0
    # print ('to calc')
    return calc(a, b)

ans = 0
for a in range(n): #Aの数
    if A * a > K:
        break
    if (K - A * a) % B != 0:
        continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

print (ans)

### FIXED CODE ###

import numpy as np
MOD = 998244353

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

def gcd(a, b):
    if a > b:
        a, b = b, a
    if b % a == 0:
        return a
    return gcd(b % a, a)

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

if A < B:
    A, B = B, A

# n = 2 * min(K // A + 2, N + 1) + 3
n = min((K + A - 1) // A, N) + 1
lcm = A * B // gcd(A, B)
step = lcm // A

c = Factorial(N + 1, MOD).comb #O(N)

def calc(a, b):
    if a > b:
        a, b = b, a #必ずaのほうが小さくなる
    return (c(N, a) * c(N, b)) % MOD


def count(a, b):
    if a <= N and b <= N:
        return calc(a, b)
    return 0

def maike_satrt(step):
    for i in range(step):
        if (K - A * i) % B == 0:
            return i

start = maike_satrt(step)
# print (start, n)
ans = 0
for a in range(start, n, step): #Aの数
    if A * a > K:
        break
    # if (K - A * a) % B != 0:
    #     continue
    b = (K - A * a) // B
    # print ('a=', a, 'b=', b)
    ans += count(a, b)
    ans %= MOD

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

import sys
import bisect
import heapq

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

### FIXED CODE ###

from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)
### BUGGY CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

member = [A, B, C, D, E]
people = [N, 0, 0, 0, 0, 0]
count = 0
while people[5] < N:
    for i in reversed(range(5)):
        if people[i] >= member[i]:
            people[i+1] += member[i]
            people[i] -= member[i]
        elif people[i] > 0:
            people[i+1] += people[i]
            people[i] = 0
    count += 1
    
print(count)
        

### FIXED CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

member = [A, B, C, D, E]
if N % min(member) == 0:
    answer = N // min(member) + 4
else:
    answer = N // min(member) + 5
print(answer)
### BUGGY CODE ###

def unite(x, y, s_list):
    x_list = None
    y_list = None
    for s in s_list:
        if x in s and y in s:
            x_list = s.copy()
            y_list = s.copy()
            del s
        elif x in s:
            x_list = s.copy()
            del s
        elif y in s:
            y_list = s.copy()
            del s
    if x_list != None and y_list != None:
        s_list.append(list(set(x_list + y_list)))
    elif x_list != None and y_list == None:
        x_list.append(y)
        s_list.append(x_list)
    elif x_list == None and y_list != None:
        y_list.append(x)
        s_list.append(y_list)
    else:
        s_list.append([x, y])

def same(x, y, s_list):
    x_list = None
    y_list = None
    for s in s_list:
        if x in s and y in s:
            return 1
    return 0


n, q = list(map(int, input().split()))
com_list = list()
x_list = list()
y_list = list()
s_list = list()

for _ in range(q):
    com, x, y = list(map(int, input().split()))
    com_list.append(com)
    x_list.append(x)
    y_list.append(y)

for i in range(q):
    com = com_list[i]
    x = x_list[i]
    y = y_list[i]
    if com == 0:
        unite(x, y, s_list)
    else:
        result = same(x, y, s_list)
        print(result)

    

### FIXED CODE ###

def make_set(x, disjoint):
    disjoint[x] = x

def find_set(x, disjoint):
    if x not in disjoint.keys():
        make_set(x, disjoint)
    if x != disjoint[x]:
        disjoint[x] = find_set(disjoint[x], disjoint)
    return disjoint[x]

def link(x, y, disjoint):
    disjoint[y] = x

def unite(x, y, disjoint):
    link(find_set(x, disjoint), find_set(y, disjoint), disjoint)

def same(x, y, disjoint):
    if find_set(x, disjoint) == find_set(y, disjoint):
        return 1
    return 0

n, q = list(map(int, input().split()))
com_list = list()
x_list = list()
y_list = list()

for _ in range(q):
    com, x, y = list(map(int, input().split()))
    com_list.append(com)
    x_list.append(x)
    y_list.append(y)

disjoint = dict()

for i in range(q):
    com = com_list[i]
    x = x_list[i]
    y = y_list[i]

    if com == 0:
        unite(x, y, disjoint)
    else:
        print(same(x, y, disjoint))
### BUGGY CODE ###

import sys

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

  
n = int(input())
if n == 1:
  print(0)
  sys.exit()

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 )

pow8 = [0]*(n+1)
pow8[0] = 1
for i in range(1,n+1):
  pow8[i] = (pow8[i-1]*8) % mod


ans = (10**n) % mod - pow8[n]
for i in range(1,n+1):
  ans = (ans - pow8[n-i]*2*cmb(n,i,mod)) % mod
               
print(ans)

### FIXED CODE ###

import sys

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

n = int(input())
if n == 1:
  print(0)
  sys.exit()

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

pow10=10

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 )
    pow8[i] = (pow8[i-1]*8) % mod  
    pow10 =(pow10*10) % mod
ans = pow10 - pow8[n]
for i in range(1,n+1):
  ans = (ans - pow8[n-i]*2*cmb(n,i,mod)) % mod
               
print(ans)
### BUGGY CODE ###

# coding: utf-8
s = input()
q = int(input())
f = 0
for _ in range(q):
    li = list(input().split())
    if len(li) == 1:
        f = ~f
    else:
        if li[1] == '1':
            if f == 0:
                s = li[2] + s
            else:
                s = s + li[2]
        else:
            if f == 0:
                s = s + li[2]
            else:
                s = li[2] + s
if f == -1:
    s = s[::-1]
    
print(s)

### FIXED CODE ###

# coding: utf-8
s = list(input())
q = int(input())

first = []
end = []
f = 0
for _ in range(q):
    li = list(input().split())
    if len(li) == 1:
        f = ~f
    else:
        if li[1] == '1':
            if f == 0:
                first.append(li[2])
            else:
                end.append(li[2])
        else:
            if f == 0:
                end.append(li[2])
            else:
                first.append(li[2])
s = first[::-1] + s + end
if f == -1:
    s = s[::-1]
    
print(''.join(s))