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

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

# dp[i][j]: i人目までに合計j個渡したときの場合の数
# i人目に配れるアメは0~A[i-1]個
# 例えばA[i-1]個をi人目に配っていたらi-1人目まではj-A[i-1]個を合計で配っている
# dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-A[i-1]]
# 数列をずらして工夫すると
# dp[i][j-1] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-A[i-1]-1]
# となるので、
# dp[i][j] - dp[i][j-1] = dp[i-1][j] - dp[i-1][j-A[i-1]-1]
# 最終的に
# dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-A[i-1]-1]


dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
# i人目までに0個配る方法は1通り
for i in range(N + 1):
    dp[i][0] = 1

for i in range(1, N+1):
    for j in range(1, K + 1):
        dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        # i-1人目までに渡すアメの数は0以上でなければならない
        if (j - A[i - 1] - 1) >= 0:
            dp[i][j] = dp[i][j] - dp[i - 1][j - A[i - 1] - 1]
            
print(dp[N][K]%1000000007)

### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
m = 1000000007
# dp[i][j]: i人目までに合計j個渡したときの場合の数
# i人目に配れるアメは0~A[i-1]個
# 例えばA[i-1]個をi人目に配っていたらi-1人目まではj-A[i-1]個を合計で配っている
# dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-A[i-1]]
# 数列をずらして工夫すると
# dp[i][j-1] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-A[i-1]-1]
# となるので、
# dp[i][j] - dp[i][j-1] = dp[i-1][j] - dp[i-1][j-A[i-1]-1]
# 最終的に
# dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-A[i-1]-1]


dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
# i人目までに0個配る方法は1通り
for i in range(N + 1):
    dp[i][0] = 1

for i in range(1, N+1):
    for j in range(1, K + 1):
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % m
        # i-1人目までに渡すアメの数は0以上でなければならない
        if (j - A[i - 1] - 1) >= 0:
            dp[i][j] = (dp[i][j] + m - dp[i - 1][j - A[i - 1] - 1]) % m
            
print(dp[N][K])
### BUGGY CODE ###

n,m = map(int,input().split())
L = []
R = []
for i in range(m):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
ans = 0
for i in range(1,n+1):
    if max(L) <= i and min(R) >= i:
        ans += 1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
L = []
R = []
for i in range(m):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
ans = 0
L = max(L)
R = min(R)
for i in range(1,n+1):
    if L <= i and R >= i:
        ans += 1
print(ans)
### BUGGY CODE ###

# C - Cat Snuke and a Voyage
N,M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
goal = []
for i in range(M):
    if A[i][1] == N:
        goal.append(A[i][0])
    else:
        pass

for i in range(len(goal)):
    for j in range(M):
        if A[j][1] == goal[i]:
            if A[j][0] == 1:
                print("POSSIBLE")
                exit()
print("IMPOSSIBLE")


### FIXED CODE ###

# C - Cat Snuke and a Voyage
N,M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
goal2 = []
goal1 = []
for i in range(M):
    if A[i][1] == N:
        goal2.append(A[i][0])
    elif A[i][0] == 1:
        goal1.append(A[i][1])
    else:
        pass

if len(set(goal1)&set(goal2)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

N,K,Q =map(int,input().split())
FP = [K]*N
S = []
for i in range(Q):
    S.append(int(input()))
S.sort()
for i in range(N):
    FP[i] -= Q - S.count(i+1)
for i in FP :
    if i >= 1 :
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q=map(int,input().split())
L=[K]*N
for i in range(Q):
    A=int(input())
    L[A-1] += 1

for i in L:
    if i - Q > 0 :
        print("Yes")
    else :
        print("No")
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
visit=[1]
pos=0
while True:
    visit.append(a[pos])
    pos=a[pos]-1
    if a[pos] in visit:
        break
loop=[]
looppos=visit[-1]-1
while True:
    loop.append(a[looppos])
    looppos=a[looppos]-1
    if a[looppos] in loop:
        break
if len(visit)>k:
    print(visit[k])
else:
    t=(k-len(visit)+len(loop))%len(loop)
    print(loop[t])

### FIXED CODE ###

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

num = 1
li = [1]
flag = [True] * n
flag[0] = False

for i in range(k):
    num = a[num-1]
    if flag[num-1]:
        li.append(num)
        flag[num-1] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d

print(li[ans])
### BUGGY CODE ###

N = int(input())
A = [0] * N
A = list(map(int,input().split()))

ans = 0
mod = 10**9+7
for i in range(N):
    for j in range(i+1,N):
        ans += (A[i]%mod) * (A[j]%mod)
        ans %= mod
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0] * (N+1)

# 累積和を使う
for i in range(1,N+1):
    B[i] = A[i-1]+B[i-1]
# 累積和の配列完成
# print(B) 

ans = 0
MOD = 10**9+7
for i in range(N):
    ans += A[i] * (B[N] - B[i+1])
    ans %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
lst = [x for x in input().split()]
a = ''

for i in range(N):
    a = lst.pop()
    if a in lst:
        print('NO')
        break
    else:
        continue

if len(lst) == 0:
    print('YES')

### FIXED CODE ###

N = int(input())
U = set()
for i in input().split():
    U.add(i)
print('YES' if len(U) == N else 'NO')
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


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


def C(F, a, b, mod):
    return F[a] * inv(F[a - b], mod) * inv(F[b], mod) % mod 


def main():
    N, K = read_values()
    mod = 10 ** 9 + 7
    F = functional(5 * 10 ** 5, mod)
    res = 0
    if N <= K:
        res = C(F, 2 * N - 1, N - 1, mod)
    else:
        for k in range(K + 1):
            res += C(F, N, k, mod) * C(F, N - 1 , k, mod) % mod
    
    print(res % mod)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


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


def C(F, a, b, mod):
    return F[a] * inv(F[a - b], mod) * inv(F[b], mod) % mod 


def main():
    N, K = read_values()
    mod = 10 ** 9 + 7
    F = functional(5 * 10 ** 5, mod)
    res = 0
    if N <= K:
        res = C(F, 2 * N - 1, N - 1, mod)
    else:
        c = C(F, N - 1, 0, mod)
        for k in range(K + 1):
            res += pow(c, 2, mod) * N * inv(N - k, mod) % mod
            c *= ((N - k - 1) * inv(k + 1, mod)) % mod
            c %= mod
    
    print(res % mod)

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

import sys
from collections import defaultdict
input = sys.stdin.readline
H, W, N = map(int, input().split())

board = defaultdict(int)
black = []
for _ in range(N):
    a, b = map(int, input().split())
    black.append((a - 1, b - 1))
    board[(a-1) * 10 ** 10 + (b - 1)] = 1

num = [0] * 10
for p in black:
    for ch in range(max(p[0] - 1, 1), min(p[0] + 2, H - 1)):
        for cw in range(max(p[1] - 1, 1), min(p[1] + 2, W - 1)):
            count = 0
            for h in range(ch - 1, ch + 2):
                for w in range(cw - 1, cw + 2):
                    if board[h * 10 ** 10 + w] == 1:
                        count += 1
            num[count] += 1
for i in range(1, 10):
    num[i] //= i
print((H - 2) * (W - 2) - sum(num))
for i in range(1, 10):
    print(num[i])


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
H, W, N = map(int, input().split())

board = defaultdict(int)
black = []
for _ in range(N):
    a, b = map(int, input().split())
    black.append((a - 1, b - 1))
    board[(a-1) * W + (b - 1)] = 1

num = [0] * 10
for p in black:
    for ch in range(max(p[0] - 1, 1), min(p[0] + 2, H - 1)):
        for cw in range(max(p[1] - 1, 1), min(p[1] + 2, W - 1)):
            count = 0
            for h in range(ch - 1, ch + 2):
                for w in range(cw - 1, cw + 2):
                    if board[h * W + w] == 1:
                        count += 1
            num[count] += 1
for i in range(1, 10):
    num[i] //= i
print((H - 2) * (W - 2) - sum(num))
for i in range(1, 10):
    print(num[i])
### BUGGY CODE ###

R, G, B ,N = map(int, input().split())

cnt = 0
for r in range(N//R + 1):
  for g in range(N//G + 1):
    if (N - (r*R + g*G)) % B == 0 and  (N - (r*R + g*G)) >= 0:
      cnt += 1
print(cnt)


### FIXED CODE ###

R, G, B ,N = map(int, input().split())

if R==1 and G==1 and B==1:
  print(int((N+2)*(N+1)*(1/2)))
else:
  RGB = [R, G, B]
  RGB.sort(reverse=True)

  R = RGB[0]
  G = RGB[1]
  B = RGB[2]

  cnt = 0
  NR = N//R
  NG = N//G
  for r in range(NR + 1):
    for g in range(NG + 1):
      NrRgG = N - (r*R + g*G)
      if NrRgG < 0:
        break
      elif NrRgG >= 0:
        if NrRgG % B == 0:
          cnt += 1
  print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G_fix_3
# CreatedDate:  2020-07-28 22:54:01 +0900
# LastModified: 2020-07-28 23:09:02 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import deque


class Graph():
    def __init__(self, vertex):
        self.V = vertex
        self.path = [[] for _ in range(self.V+1)]
        self.Q = deque()
        self.distance = [0] * (self.V+1)

    def addedge(self, s, t):
        self.path[s].append(t)

    def bfs(self, init):
        self.Q.append(init)
        while self.Q:
            u = self.Q.popleft()
            for v in self.path[u]:
                if self.distance[v] < self.distance[u]+1:
                    self.distance[v] = self.distance[u]+1
                    self.Q.append(v)
        return max(self.distance)

    def clear(self):
        self.distance = [0] * (self.V+1)


def main():
    N, M = map(int, input().split())
    graph = Graph(N)
    for _ in range(M):
        s, t = map(int, input().split())
        graph.addedge(s, t)
    ans = 0
    for init in range(1, N+1):
        ans = max(ans, graph.bfs(init))
        graph.clear()
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import collections

# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    return b

def main():
    # 入力
    N, M = map(int, input().split())
    # 隣接関係は隣接リストで管理する
    lst_edge = [[] for _ in range(N)]
    # 各頂点の入力辺の本数
    deg = [0] * N
    for _ in range(M):
        x, y = map(int, input().split())
        # 最初のindexをゼロにする
        lst_edge[x-1].append(y-1)
        deg[y-1] += 1

    # 入力辺を持たない頂点をqueueに入れる
    que = collections.deque()
    for v in range(N):
        if deg[v] == 0:
            que.append(v)

    # 各頂点の最初に入力辺を持たなかった点からの距離
    dp = [0] * N

    # For sequences, (strings, lists, tuples), use the fact that empty sequences are false.
    # https://www.python.org/dev/peps/pep-0008/#programming-recommendations
    while que:
        v = que.popleft()
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            # エッジ(v, nv)をグラフから削除する
            deg[nv] -= 1
            if deg[nv] == 0:
                # エッジがなくなったことで、入力辺がなくなったらqueueに入れる
                que.append(nv)
                # 最初に入力辺を持たなかった点からの距離
                dp[nv] = chmax(dp[nv], dp[v] + 1)

    print(max(dp))

main()
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse = True)
q = sorted(list(map(int, input().split())), reverse = True)
r = sorted(list(map(int, input().split())), reverse = True)
s = p[:X] + q[:Y] + r[:X+Y]
S = sorted(s, reverse = True)
i = 0
j = 0
ans = 0
a = 0
b = 0
c = 0
while i < (X + Y):
  if S[j] in r:
    c += 1
    r.remove(S[j])
    ans += S[j]
    i += 1
  elif S[j] in p and a < X:
    a += 1
    p.remove(S[j])
    ans += S[j]
    i += 1
  elif S[j] in q and b < Y:
    b += 1
    q.remove(S[j])
    ans += S[j]
    i += 1
  j += 1
print(ans)

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse = True)
q = sorted(list(map(int, input().split())), reverse = True)
r = sorted(list(map(int, input().split())), reverse = True)
S = sorted(p[:X] + q[:Y] + r[:X+Y], reverse = True)
print(sum(S[:X+Y]))
### BUGGY CODE ###

K = int(input())

from itertools import product
kumi = product(range(1, K+1), repeat=3)

from fractions import gcd

memo = [[None for i in range(K+1)] for i in range(K+1)]
# memo2 = {}

ans = 0
for a, b, c in kumi:
    a, b, c = sorted([a, b, c])
    if memo[a][b] is not None:
        v = memo[a][b]
    else:
        v = gcd(a, b)
        memo[a][b] = v
        memo[b][a] = v
    d = gcd(v, c)
    ans += d

print(ans)

### FIXED CODE ###

K = int(input())

import math

ans = 0
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            if i == j and j == k and k == i:
                ans += i
            elif i == j or j == k or k == i:
                x = math.gcd(i, j)
                ans += math.gcd(x, k) * 3
            else:
                x = math.gcd(i, j)
                ans += math.gcd(x, k) * 6
print(ans)
### BUGGY CODE ###

x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]
S = S[::-1]

dp = [[0 for j in range(13)] for i in range(len(S) + 1)]

dp[0][0] = 1

for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

        digit_r = ((10 ** i) * j) % 13

        for k in range(13):
            r = (digit_r + k) % 13
            dp[i + 1][r] += dp[i][k] % x

print(int(dp[-1][5] % x))


### FIXED CODE ###

x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]

dp = [[0 for j in range(13)] for i in range(len(S) + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

        for k in range(13):
            dp[i + 1][(10 * k + j) % 13] += dp[i][k] % x

print(int(dp[-1][5] % x))
### BUGGY CODE ###

n=int(input())
l1=[]
l=[int(i) for i in input().split()]
for i in l:
    l1.append(i)
    l1=l1[::-1]
print(*l1)

### FIXED CODE ###

n=int(input())
l1=[]
l=[int(i) for i in input().split()]
from collections import deque 
l1=deque()
if n%2==0:
   # l1=[]
    p=0 
    for i in l:
        if p==0:
            l1.append(i)
        else:
            l1.appendleft(i)
        p=1-p 
    print(*l1)
else:
   # l1=[]
    p=0 
    for i in l:
        if p==0:
            l1.appendleft(i)
        else:
            l1.append(i)
        p=1-p 
    print(*l1)
### BUGGY CODE ###

st = input()
list_s = []
for s in st:
    list_s.append(s)

delcount = 0
while True:
    if len(list_s) < 2:
        break
    pre = list_s[0]
    count = 0
    for s in list_s:        
        if (pre == '0' and s == '1') or (pre == '1' and s == '0'):
            del list_s[count]
            del list_s[count-1]
            delcount += 1
            break
        count += 1
    if list_s.count('0') == 0 or list_s.count('1') == 0:
        break
print(delcount * 2)


### FIXED CODE ###

st = input()
list_s = list(st)

delcount = 0
count_0 = list_s.count('0')
count_1 = list_s.count('1')
if count_0 < count_1:
    print(count_0 * 2)
else:
    print(count_1 * 2)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        self.ans=""
dp = [[node() for j in range(m+1)] for i in range(n+1)]
# for i in range(1,n + 1):
#     dp[i][0].angle = Angle.UP
# for j in range(1,m + 1):
#     dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1].value = dp[i][j].value + 1
            dp[i + 1][j + 1].ans = "".join([dp[i][j].ans, s[i]])
        elif dp[i][j + 1].value > dp[i + 1][j].value: #UP
            dp[i + 1][j + 1].ans = dp[i][j + 1].ans
            dp[i + 1][j + 1].value = dp[i][j + 1].value
        else:  # LEFT
            dp[i + 1][j + 1].ans = dp[i + 1][j].ans
            dp[i + 1][j + 1].value = dp[i + 1][j].value

            
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].ans,end="")
#     print("")
print(dp[n][m].ans)

        

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

from itertools import accumulate

n, m = map(int, input().split())
A = list(map(int, input().split()))
dp = [ [0]*(n+1) for _ in range(n+1) ]
L = [0] + list(accumulate(A))
ans = 0
for i in range(1, n+1):
  for j in range(i):
    if (L[i]-L[j])%m == 0:
      ans += 1
print(ans)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
L = [ i%m for i in L ]
C = Counter(L)
ans = 0
for i in C.values():
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

s = input()
t = input()
num = set()

for i in range(len(s)):
    if s[i] != t[i]:
        if not i in num:
            a, b = s[i], t[i]
            s = s.replace(a, '-')
            s = s.replace(b, a)
            s = s.replace('-', b)
            num.add(s[i])

if s == t:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys
s = list(input())
t = list(input())
a = [-1 for _ in range(26)]
b = [-1 for _ in range(26)]

for i in range(len(s)):
    num0, num1 = a[ord(s[i])-97], b[ord(t[i])-97]
    if num0 >= 0:
        if chr(num0+97) != t[i]:
            print('No')
            sys.exit()
    else:
        a[ord(s[i])-97] = ord(t[i])-97
        
    if num1 >= 0:
        if chr(num1+97) != s[i]:
            print('No')
            sys.exit()
    else:
        b[ord(t[i])-97] = ord(s[i])-97
            
print('Yes')
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque
import sys
sys.setrecursionlimit(700000)

NIL = -1
N, M, K = map(int, input().split())
friends = [deque() for i in range(N)]
block = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A].append(B)
    friends[B].append(A)

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    block[C].append(D)
    block[D].append(C)


def dfs(x, y):
    for i in friends[y]:
        if check[i] == None:
            #print(i)
            prefriends[x].append(i)
            #print(set(prefriends[x]))
            check[i] = x
            dfs(x, i)
ans = [0]*N
#print(prefriends)
j = 0
check = [None]*N
while j < N:
    if check[j] == None:
        #print(prefriends[j])
        prefriends[j].append(j)
        check[j] = j
        dfs(j, j)
        #print(check)
    j += 1
    #print(set(prefriends[j]))
    #print(set(friends[j]))
    #print(set(block[j]))
    #print((set(prefriends[j]) - set(friends[j])) - set(block[j]))
for j in range(N):
    ans[j] = (set(prefriends[check[j]]) - set(friends[j])) - (set(block[j]) | set([j]))
    #print(ans[j])
    #print()
ans = [len(ans[i]) for i in range(N)]
print(*ans)



### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque
import sys
sys.setrecursionlimit(700000)

NIL = -1
N, M, K = map(int, input().split())
relation = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    relation[A].append(B)
    relation[B].append(A)

def dfs(x, y):
    for i in relation[y]:
        if check[i] == None:
            #print(i)
            prefriends[x].append(i)
            #print(set(prefriends[x]))
            check[i] = x
            dfs(x, i)

#print(prefriends)
j = 0
check = [None]*N
while j < N:
    if check[j] == None:
        #print(prefriends[j])
        prefriends[j].append(j)
        check[j] = j
        dfs(j, j)
        #print(check)
    j += 1
    #print(set(prefriends[j]))
    #print(set(friends[j]))
    #print(set(block[j]))
    #print((set(prefriends[j]) - set(friends[j])) - set(block[j]))

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if check[C] == check[D]:
        relation[C].append(D)
        relation[D].append(C)
ans = [0]*N
for j in range(N):
    ans[j] = len(prefriends[check[j]]) - len(relation[j]) - 1
    #print(ans[j])
    #print()
print(*ans)
### BUGGY CODE ###

mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
    return power(x, mod-2)

def binomial_coefficients(n, k):
    numera = 1  # 分子
    denomi = 1  # 分母

    for i in range(k):
        numera *= n-i
        numera %= mod
        denomi *= i+1
        denomi %= mod
    return numera * modinv(denomi) % mod

def mypow(x, n):
    res = 1
    while n > 0:
        if n & 1 == 1:
            res *= x
        x *= x
        n >>= 1
    return res

ans = 0
N = int(input())
for i in range(1,N):
    for j in range(1,N-i+1):
        ans = ans + ((binomial_coefficients(N, i)%mod)*(binomial_coefficients(N-i, j)%mod)*(mypow(8,N-i-j)%mod))%mod

print(ans)


### FIXED CODE ###

mod = 10**9 + 7

def modpow(x, n):
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res*x%mod
        x = x*x%mod
        n >>= 1
    return res

N = int(input())
ans = (modpow(10,N)-2*modpow(9,N)+modpow(8,N))%mod

print(ans)