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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

import copy
ans = 0

for i in range(N-1):
    B = copy.copy(A)
    del B[:i+1]
    B = list(map(lambda x: x % MOD, B))
    B = sum(B) % MOD
    ans += A[i] * B
    ans = ans % MOD
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

import copy
B = copy.copy(A)
C = sum(B)
ans = 0

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

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush
import numpy as np


def small_dp(N,k,X):
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        dp = np.zeros((3, N+1), dtype=int)
        M = np.arange(N+1)
        dp[0] = X[0][1]*(M//X[0][0]) + M%X[0][0]
        for i,w in product(range(1,3), range(1,N+1)):
            dp[i,w] = max(dp[i-1,w], dp[i,w-X[i][0]]+X[i][1] if w >= X[i][0] else 0)
        N = dp[-1][N]
        return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    for C in ((A,B), (B,A)):
        *X, = filter(lambda c: int.__sub__(*c)<0, zip(*C))
        N = small_dp(N, len(X), X)
    res = N

    return str(res)

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


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

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

S = input()[::-1]
Surpus = [0] * 2019
Surpus[0] = 1

sum = 0
x = 1
for i in S:
    sum += int(i) * x
    Surpus[sum % 2019] += 1
    x *= 10

ans = 0
for i in Surpus:
    ans += i * (i - 1) // 2

print(ans)

### FIXED CODE ###

S = input()[::-1]
Surpus = [0] * 2019
Surpus[0] = 1

sum = 0
x = 1
for i in S:
    sum += int(i) * x
    Surpus[sum % 2019] += 1
    x *= 10
    x %= 2019

ans = 0
for i in Surpus:
    ans += i * (i - 1) // 2

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

a, b = map(int, input().split())
ans = []
c = 0
for i in range(a,b+1):
    ans.append(i)
    if i < 0:
        c += 1

if ans.count(0) == 1:
    print("Zero")
elif c % 2 != 0:
    print("Negative")
else:
    print("Positive")


### FIXED CODE ###

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


if a < 0 and b > 0:
    print("Zero")

elif a > 0:
    print("Positive")

elif b < 0 and a < 0:
    if (b - a + 1) % 2 != 0:
        print("Negative")
    else:
        print("Positive")
### BUGGY CODE ###

def solve():
    N, K, Q = map(int, input().split())
    point = [K for _ in range(N)]
    
    for _ in range(Q):
        answer = int(input()) - 1
        for i in range(N):
            if answer == i:
                continue
            else:
                point[i] -= 1
    
    for i in range(N):
        if point[i] > 0:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N, K, Q = map(int, input().split())
    point = [K for _ in range(N)]
    
    for _ in range(Q):
        answer = int(input()) - 1
        point[answer] += 1
    
    for i in range(N):
        if point[i] > Q:
            print('Yes')
        else:
            print('No')


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

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

for a in A:
    ans *= a

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
ans = 1

for a in sorted(input().split()):
    ans *= int(a)
    if ans > 10**18:
        print(-1)
        exit()

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


N = int(input())
uvw = []
colors = [-1,]

for i in range(N-1):
    kari = list(map(int,input().split()))
    uvw.append(kari)
    colors.append(-1)


now_color = 0

uvw.sort()

colors[0] = 0
nokori = N-1

#print (uvw)
#print (colors)

while nokori>0:

    for i in range(len(uvw)):

        if colors[uvw[i][0]-1] != -1 :
            if uvw[i][2] % 2 == 0:
                colors[uvw[i][1]-1] = colors[uvw[i][0]-1]
                

            elif colors[uvw[i][0]-1]==0:
                colors[uvw[i][1]-1] = 1
               
            else:
                colors[uvw[i][1]-1] = 0

            del uvw[i]
            nokori -= 1
            break

        if colors[uvw[i][1]-1] != -1 :
            if uvw[i][2] % 2 == 0:
                colors[uvw[i][0]-1] = colors[uvw[i][1]-1]

            elif colors[uvw[i][1]-1]==0:
                colors[uvw[i][0]-1] = 1

            else:
                colors[uvw[i][0]-1] = 0

            del uvw[i]
            nokori -= 1
            break


for i in colors:
    print (i)
       
    




### FIXED CODE ###


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Q_cnt = 0
Nlis[0] = 0

while len(Q) > Q_cnt and N != 1:

    now = Q[Q_cnt]
    Q_cnt += 1

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

            #Ndic[nw[0]].remove([now,nw[1]])

for i in Nlis:
    print(i)
### BUGGY CODE ###

from itertools import*
n,k,*L=map(int,open(0).read().split())
p=[(x,y) for x,y in zip(*[iter(L)]*2)]
X=sorted(x for x,y in p)+[0]
Y=sorted(y for x,y in p)
ans=float("inf")
for i,mx in enumerate(X[:-k]):
	for Mx in X[i+k-1:-1]:
		for my,My in combinations(Y,2):
			if sum(mx<=x<=Mx and my<=y<=My for x,y in p)>=k:
				ans=min(ans,(Mx-mx)*(My-my))
print(ans)

### FIXED CODE ###

n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)
### BUGGY CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict,deque
n = inn()
pr = [[ [] for i in range(n+1) ] for j in range(n+1)]
ch = [[ [] for i in range(n+1) ] for j in range(n+1)]
for i in range(1,n+1):
    a = inl()
    for j in range(n-2):
        x1 = x2 = i
        y1 = a[j]
        y2 = a[j+1]
        if x1>y1:
            x1,y1 = y1,x1
        if x2>y2:
            x2,y2 = y2,x2
        ch[x1][y1].append((x2,y2))
        pr[x2][y2].append((x1,y1))
g = {}
q = []
for i in range(1,n):
    for j in range(i+1,n+1):
        if len(pr[i][j])==0:
            q.append((i,j))
            g[(i,j)] = 1
        else:
            g[(i,j)] = 0
ddprint(ch)
ddprint("pr")
ddprint(pr)
ddprint(g)
while len(q)>0:
    z = q.pop()
    i,j = z
    for y in ch[i][j]:
        g[y] = max(g[y], g[z]+1)
        #ddprint("y {} z {}".format(y,z))
        pr[y[0]][y[1]].remove(z)
        if len(pr[y[0]][y[1]])==0:
            #del pr[y]
            q.append(y)
if min(g.values())==0:
    print(-1)
else:
    print(max(g.values()))


### FIXED CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict,deque
n = inn()
pr = [[ [] for i in range(n+1) ] for j in range(n+1)]
ch = [[ [] for i in range(n+1) ] for j in range(n+1)]
for i in range(1,n+1):
    a = inl()
    for j in range(n-2):
        x1 = x2 = i
        y1 = a[j]
        y2 = a[j+1]
        if x1>y1:
            x1,y1 = y1,x1
        if x2>y2:
            x2,y2 = y2,x2
        ch[x1][y1].append((x2,y2))
        pr[x2][y2].append((x1,y1))
g = [ [0]*(n+1) for i in range(n+1) ]
q = []
for i in range(1,n):
    for j in range(i+1,n+1):
        if len(pr[i][j])==0:
            q.append((i,j))
            g[i][j] = 1
        else:
            g[i][j] = 0
ddprint(ch)
ddprint("pr")
ddprint(pr)
ddprint(g)
while len(q)>0:
    z = q.pop()
    i,j = z
    for u,v in ch[i][j]:
        g[u][v] = max(g[u][v], g[i][j]+1)
        #ddprint("y {} z {}".format(y,z))
        pr[u][v].remove(z)
        if len(pr[u][v])==0:
            #del pr[y]
            q.append((u,v))
ddprint("newg")
ddprint(g)
#gmn = [min(r[1:]) for r in g[1:]]
gmn = BIG
for i in range(1,n):
    for j in range(i+1,n+1):
        gmn = min(gmn,g[i][j])
if gmn==0:
    print(-1)
else:
    print(max([max(r) for r in g]))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N = int(input())
A = []
for i in range(N):
    num = input()
    if num in A:
        A.remove(num)
    else:
        A.append(num)
print(len(A))


### FIXED CODE ###

# coding: utf-8
# Your code here!
N = int(input())
A = set()
for i in range(N):
    num = input()
    if num in A:
        A.remove(num)
    else:
        A.add(num)
print(len(A))
### BUGGY CODE ###

#ABC 142C
n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(1, n+1):
   ans.append(a.index(i)+1)
print(*ans)

### FIXED CODE ###

#ABC 142C
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for idx,i in enumerate(a, 1):
   ans[i-1] = idx
print(*ans)
### BUGGY CODE ###

import sys
# from sympy import divisors
from collections import Counter


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a_list = list(map(int, input().split()))
    # キーに要素、値に出現回数を持つカウンタ
    a_counter = Counter(a_list)
    ans = 0
    for a in a_list:
        # aの約数の集合
        divs = make_divisors(a)
        for divisor in divs:
            if a_counter[divisor] > 0:
                if divisor == a and a_counter[divisor] == 1:
                    continue
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    _ = input()
    a_list = list(map(int, input().split()))
    res_set = set(a_list)
    # キーに要素、値に出現回数を持つカウンタ
    a_counter = Counter(a_list)
    for e in a_counter.items():  # e:(整数，出現回数)
        if e[1] == 1:
            for i in range(e[0] * 2, 10**6 + 1, e[0]):  # その整数を含まない倍数
                res_set.discard(i)
        else:
            for i in range(e[0], 2 * 10**6 + 1, e[0]):  # その整数を含む倍数
                res_set.discard(i)
    print(len(res_set))


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

# coding: utf-8
import itertools
N=int(input())
L=list(map(int,input().split()))
ans=0
l=list(itertools.combinations(L,3))
#print(max(l[0]))
kumi=len(l)
for i in range(kumi):
    l[i]=list(l[i])
    a=max(l[i])
    l[i].remove(a)
    if a<sum(l[i]):
        ans+=1
print(ans)

### FIXED CODE ###

from bisect import bisect_right
 
N = int(input())
L = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(1, N-1):
    for j in range(i+1, N):
        ans += max(0, i - bisect_right(L, L[j] - L[i]))
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
ans = 0
L = list(map(int,input().split()))
L = sorted(L)
for i in range(N-1):
    for j in range(i+1,N):
        a = bisect.bisect(L,L[i]+L[j])
        if L[i]+L[j] in L:
            a -= 1
        ans += a-j-1
     
print(ans)        
        

### FIXED CODE ###

import bisect
N = int(input())
ans = 0
L = list(map(int,input().split()))
L = sorted(L)
for i in range(N-1):
    for j in range(i+1,N):
        a = bisect.bisect(L,L[i]+L[j]-1)
       
        ans += a-j-1

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

Q = 998244353
def main():
    N, S = map( int, input().split())
    A = list( map( int, input().split()))
    invtwo = pow(2, Q-2, Q)
    # Invtwo = [1]
    # now = 1
    dp = [pow(2, N, Q)]+[0]*S
    for i in range(N):
        a = A[i]
        for i in range(S, a-1,-1):
            # print(i, a, i-a, dp[i-a])
            if dp[i-a] > 0:
                dp[i] += dp[i-a]*invtwo%Q
                dp[i] %= Q
        # print(dp)
    print(dp[S])
                
if __name__ == '__main__':
    main()


### FIXED CODE ###

Q = 998244353
def main():
    N, S = map( int, input().split())
    A = list( map( int, input().split()))
    invtwo = pow(2, Q-2, Q)
    # Invtwo = [1]
    # now = 1
    dp = [pow(2, N, Q)]+[0]*S
    for i in range(N):
        a = A[i]
        for i in range(S, a-1,-1):
            # print(i, a, i-a, dp[i-a])
            if dp[i-a] > 0:
                dp[i] += dp[i-a]*invtwo%Q
                dp[i] %= Q
        # print(dp)
    print(dp[S])
                
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

input = sys.stdin.readline
n,m = map(int, input().split())
A = list(map(int,input().split()))
d = {}
for i in range(m):
    b,c = map(int, input().split())
    if d.get(c) == None:
        d[c] = b
    else:
        d[c] = d[c] + b

for c, b in sorted(d.items()):
    A.sort()
    if b > n:
        b = n

    if A[0] < c:
        if A[b-1] > c:
            for i in range(b):
                if i // c == 0:
                    f = i
                break
            A[:f]=[c]*f
        else:
            A[:b]=[c]*b


print(sum(A))


### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline
n,m = map(int, input().split())
A = list(map(int,input().split()))
d = [list(map(int,input().split())) for _ in range(m)]

d.sort(key=lambda x:-x[1])
total = sum(A)
heapq.heapify(A)

for i in range(m):
    for j in range(d[i][0]):
        tmp = heapq.heappushpop(A, d[i][1])
        if tmp < d[i][1]:
                total += (d[i][1] - tmp)
        else:
            break

print(total)
### BUGGY CODE ###

N, C, K = map(int, input().split())

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

T.sort()

num_track = 0
i = 0
while i < N:
	L = T[i]
	if i + C + 1 < N:
		kouho = T[i:i+C] # T[i],...,T[i+C-1]
	else:
		kouho = T[i:]
	# <= L + K
	num = 0
	for j in range(len(kouho)):
		if kouho[j] - L <= K:
			num += 1
	num_track += 1
	i += num

print(num_track)



### FIXED CODE ###

N, C, K = map(int, input().split())

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

T.sort()

res = 0
i = 0
while i < N:
	res += 1
	Left = i
	while (i < N and T[i] - T[Left] <= K and i - Left + 1 <= C):
		i += 1

print(res)
### BUGGY CODE ###

N = list(map(int, input().split()))[-1]
A = sorted(list(map(int, input().split())))[::-1]
B = sorted(list(map(int, input().split())))[::-1]
C = sorted(list(map(int, input().split())))[::-1]

result = [A[i]+B[j]+C[k] 
          for i in range(len(A)) 
          for j in range(len(B)) 
          for k in range(len(C))
          if i+j+k <= N
         ]
  
result = sorted(result)[::-1]
[print(result[i]) for i in range(N)]

### FIXED CODE ###

N = list(map(int, input().split()))[-1]
A = sorted(list(map(int, input().split())), reverse=True)[:N]
B = sorted(list(map(int, input().split())), reverse=True)[:N]
C = sorted(list(map(int, input().split())), reverse=True)[:N]

first = [i+j for i in A for j in B]
first = sorted(first, reverse=True)[:N]
second = [i+j for i in first for j in C]
result = sorted(second, reverse=True)[:N]

[print(i) for i in result]
### BUGGY CODE ###

def main():
  n = int(input())
  a = []
  for n in range(n):
    a.append(int(input())-1)
  sw = [0]
  while True:
    nextsw = a[sw[-1]]
    if nextsw == 1:
      print(len(sw))
      return
    if nextsw in sw:
      print(-1)
      return
    sw.append(nextsw)
                                
main()

### FIXED CODE ###

import sys


def main():
    n = int(input())
    a = [0] * n
    for i in range(n):
        a[i] = int(sys.stdin.readline()) - 1
    sw = [False for _ in range(n)]
    nextsw = 0
    while True:
        if nextsw == 1:
            print(sw.count(True))
            return
        if sw[nextsw]:
            print(-1)
            return
        sw[nextsw] = True
        nextsw = a[nextsw]


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

N = int(input())
a = [int(i) for i in input().split()] #横にNこ
num = 0
j = 0
while j < N:
    c = 0
    k = j 
    while k < N:
        c = c + a[k]
        if c == 0:
            num = num+1
        k = k+1
    j = j + 1
print(num)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()] 
b =[0]*(N+1)
for i in range(N):
    b[i+1]= b[i] + a[i]
b.sort()
j = 0
num = 0
v = 0
while j < N:
    if b[j+1] == b[j]:
        v = v+1
    else:
        num = num + (v*(v+1))//2
        v = 0
    j = j +1
num = num + (v*(v+1))//2
print(num)
### BUGGY CODE ###

import numpy as np

K = int(input())
gcd = 0

gcd1 = np.sum(np.arange(1,K+1))
gcd2 = 0
gcd3 = 0
for a in np.arange(1,K-1):
    for b in np.arange(a+1,K):
        for c in np.arange(b+1,K+1):
            gcd_bc = np.gcd(b, c)
            gcd3 += np.gcd(a, gcd_bc)

for a in np.arange(1,K):
    for b in np.arange(a+1,K+1):
        gcd2 += np.gcd(a, b)

print(gcd1 + gcd2 * 6 + gcd3 * 6)

### FIXED CODE ###

from math import gcd
K = int(input())
sum_gcd = [0]*201
ans = 0
 
for i in range(1,K+1):
  for j in range(1,K+1):
    sum_gcd[gcd(i,j)] += 1
for i in range(1,K+1):
  for k in range(1,K+1):
    ans += sum_gcd[i]*gcd(i,k)
 
print(ans)
### BUGGY CODE ###

from collections import deque

N, M, L = map(int, input().split())
routes = [[] for i in range(N+1)]

for i in range(M):
    a, b, c = map(int, input().split())
    routes[a].append([b, c])
    routes[b].append([a, c])


def bfs(start, goal, full_energy):
    todo = deque([])
    for to, cost in routes[start]:
        if full_energy - cost >= 0:
            todo.append([to, full_energy-cost, 0])

    while todo:
        now, power, charge = todo.popleft()
        if now == goal:
            return charge

        for nex, cost in routes[now]:
            if power - cost >= 0:
                todo.appendleft([nex, power-cost, charge])
            todo.append([nex, full_energy-cost, charge+1])
    return -1


Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    print(bfs(s, t, L))



### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

n, m, energy = map(int, input().split())
edges = [[float('INF')]*n for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c

G = csgraph_from_dense(edges, null_value=float('INF'))
dist = floyd_warshall(G)

L_edges = [[float('INF')]*n for _ in range(n)]
for i in range(n-1):
    for j in range(i, n):
        if dist[i][j] <= energy:
            L_edges[i][j] = 1
            L_edges[j][i] = 1

G = csgraph_from_dense(L_edges, null_value=float('INF'))
answers = floyd_warshall(G)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    ans = answers[s-1][t-1] - 1
    if ans == float('INF'):
        ans = -1
    print(int(ans))
### BUGGY CODE ###

S=list(input())

dp=[(i,0) for i in range(13)]
dp=dict(dp)
dp[0]=1

i=0
for k in reversed(S):
    dpcopy=dp.copy()
    dp=dict([(i,0) for i in range(13)])
    if k=='?':
        for s in range(10):
            p=(s * 10**(i))%13
            for j in range(13):               
                dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    else:
        k=int(k)
        p=(k * 10**(i))%13
        for j in range(13):
            dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    i += 1


print(dp[5]%(10**9+7))


### FIXED CODE ###

S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

dp = [[0]*13 for i in range(le+1)]
dp[0][0] = 1

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
K = int(input())

def factorize(target_number):
    factor_list = []
    while target_number % 2 == 0:
        factor_list.append(2)
        target_number //= 2
    factor = 3
    while factor * factor <= target_number:
        while target_number % factor == 0:
            target_number //= factor
            factor_list.append(factor)
        factor += 2
    if target_number > 1:
        factor_list.append(target_number)
    return factor_list

fact_list = factorize(K)
if fact_list.count(2) > 0 or fact_list.count(5) > 0:
    print(-1)
else:
    num = 7
    for i in range(10 ** 6):
        if num % K == 0:
            print(i + 1)
            break
        num = num * 10 + 7
    

### FIXED CODE ###

# C TLE
# -*- coding: utf-8 -*-
K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    num = 7
    for i in range(10 ** 6):
        mod_num = num % K
        if mod_num == 0:
            print(i + 1)
            break
        num = mod_num * 10 + 7
### BUGGY CODE ###

#from collections import defaultdict
from sys import stdin
input = stdin.readline

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

ans = "IMPOSSIBLE"

ls_a,ls_b = [],[]
af,bf = [False]*M,[False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    if a-1 == 0:
        af[m] = True
        ls_a.append(b-1)
    if b-1 == N-1:
        bf[m] = True
        ls_b.append(a-1)
    if af[m] and bf[m]:
        ans = "POSSIBLE"
        break
    
for a in ls_a:
    if ans == "POSSIBLE":
        break
    if a in ls_b:
        ans = "POSSIBLE"
        break

print(ans)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

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

ans = "IMPOSSIBLE"

seta,setb = set(),set()
af,bf = [False]*M,[False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    if a-1 == 0:
        af[m] = True
        seta.add(b-1)
    if b-1 == N-1:
        bf[m] = True
        setb.add(a-1)
    if af[m] and bf[m]:
        ans = "POSSIBLE"
        break
    
for a in seta:
    if ans == "POSSIBLE":
        break
    if a in setb:
        ans = "POSSIBLE"
        break

print(ans)