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

from collections import defaultdict

s = input().split('T')
dx = list(map(len, s[0::2]))
dy = list(map(len, s[1::2]))
lx = sum(dx)
ly = sum(dy)
x, y = map(int, input().split())

dp = [defaultdict(bool) for _ in range(len(dx))]
dp[0][dx[0]] = True
for i in range(1, len(dx)):
    for j in range(-lx, lx + 1):
        dp[i][j] = dp[i - 1][j - dx[i]] or dp[i - 1][j + dx[i]]

x_ok = dp[len(dx) - 1][x]

if len(dy) > 0:
    dp = [defaultdict(bool) for _ in range(len(dy))]
    dp[0][dy[0]] = True
    dp[0][-dy[0]] = True
    for i in range(1, len(dy)):
        for j in range(-ly, ly + 1):
            dp[i][j] = dp[i - 1][j - dy[i]] or dp[i - 1][j + dy[i]]
    y_ok = dp[len(dy) - 1][y]
else:
    y_ok = y == 0

print('Yes' if x_ok and y_ok else 'No')


### FIXED CODE ###

s = input().split('T')
dx = list(map(len, s[0::2]))
dy = list(map(len, s[1::2]))
x, y = map(int, input().split())

def check(start, ds, goal):
    cands = {start}
    for d in ds:
        new_cands = set()
        for c in cands:
            new_cands.add(c - d)
            new_cands.add(c + d)
        cands = new_cands
    return goal in cands

x_ok = check(dx[0], dx[1:], x)
y_ok = check(0, dy, y)

print('Yes' if x_ok and y_ok else 'No')
### BUGGY CODE ###

a, b, k = map(int, input().split())
l = [i for i in range(a, b+1)]

c = a
while c < a + k and c <= b:
    print(c)
    c += 1
c = max(b-k+1, c)
while c <= b:
    print(c)
    c += 1


### FIXED CODE ###

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

c = a
while c < a + k and c <= b:
    print(c)
    c += 1
c = max(b-k+1, c)
while c <= b:
    print(c)
    c += 1
### BUGGY CODE ###

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

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

Group=[i for i in range(N+1)]

Swap=[None]*M
for i in range(M):
    Swap[i]=tuple(map(int,input().split()))

for i in range(M):
    if (Group[Swap[i][1]],Group[Swap[i][0]])!=(min(Group[Swap[i][0]], Group[Swap[i][1]]),min(Group[Swap[i][0]], Group[Swap[i][1]])):
        Group=[min(Group[Swap[i][0]], Group[Swap[i][1]])  if (j==Group[Swap[i][0]] or j==Group[Swap[i][1]]) else j for j in Group]

count=0

for i in range(N):
    if Group[P[i]]==Group[i+1]:
        count+=1


print(count)

### FIXED CODE ###

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

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


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

from collections import Counter
import bisect

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

a_raw=Counter(A)
b_raw=Counter(B)
c_raw=Counter(C)

a=sorted(a_raw.items(), key=lambda x: x[0])
c=sorted(c_raw.items(), key=lambda x: x[0])

ans=0
for i in b_raw:
    insert_index_a = bisect.bisect_left([a[x][0] for x in range(len(a))],i)
    insert_index_c = bisect.bisect_right([c[y][0] for y in range(len(c))],i)
    if insert_index_a>0 and insert_index_c !=len(c):
        sum_a=sum(a[m][1] for m in range(insert_index_a))
        sum_c=sum(c[n][1] for n in range(insert_index_c,len(c)))
        ans+=sum_a * b_raw[i] * sum_c

print(ans)



### FIXED CODE ###

import bisect

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

A.sort()
B.sort()
C.sort()

ans = 0
for i in B:
    ins_a = bisect.bisect_left(A,i)
    ins_c = bisect.bisect_right(C,i)
    ans+=ins_a*(N-ins_c)

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

def main():
    S = input()
    K = int(input())
    ans = ''
    for s in S:
        if 123 - ord(s) <= K and s != 'a':
            ans += 'a'
            K -= 123-ord(s)
        else:
            ans += s
    if K > 0:
        ans = ans[:-1] + chr((ord(ans[-1])+K-97) % 26+97)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    S = input()
    K = int(input())
    ans = ''
    for s in S:
        if 123 - ord(s) <= K and s != 'a':
            ans += 'a'
            K -= 123-ord(s)
        else:
            ans += s
    if K > 0:
        ans = ans[:-1] + chr((ord(ans[-1])+K-97) % 26+97)
    print(ans)


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

import sys 

readline = sys.stdin.readline 

N = int(input())
X_str= input()
X = list(X_str)
bit_count = X_str.count('1')

def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0:
        bit_con = bit_counter if counter == 0 else bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

for i in range(N):
    # ビットの反転
    x_copy = X.copy()
    bit_count_n = bit_count
    if x_copy[i] == '0':
        x_copy[i] = '1'
        bit_count_n += 1
    else:
        x_copy[i] = '0'
        bit_count_n -= 1

    bit_int = int("".join(x_copy), 2)

    print(popcount(bit_int, bit_count_n))






### FIXED CODE ###

def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1) if (bit_count - 1) != 0 else 0

    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)
### BUGGY CODE ###

import numpy as np

n = int(input())
a = list(map(int,input().split()))
a = np.array(a,dtype=np.int64)
b = [((a>>i)&1).sum() for i in range(31)]
li = []
for i in a:
    c = np.array([((i>>j)&1) for j in range(31)],dtype=np.int64)
    d = b-c
    point = 0
    for i in range(31):
        if d[i]%2 == 1:
            point += 2**(i)
    li.append(point)

print(*li)

### FIXED CODE ###

import numpy as np

n = int(input())
a = list(map(int,input().split()))
now = 0
for i in a:
    now ^= i
li = []
for i in a:
    li.append(i^now)

print(*li)
### BUGGY CODE ###

import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N - 1, 0, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A, comp, 0, i - 1)
        while True:
            if A[j] == comp:
                if used[j] == 0:
                    ans += 1
                    used[j] = 1
                    break
                else:
                    if j + 1 < i:
                        j += 1
                    else:
                        break
            else:
                break

print(ans)


### FIXED CODE ###

import bisect
import math
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set = []
num = []
a_cur = float('inf')
for a in A:
    if a != a_cur:
        A_set.append(a)
        num.append(1)
        a_cur = a
    else:
        num[-1] += 1

ans = 0
for i in range(len(A_set) - 1, -1, -1):
    if num[i] > 0:
        A_i = A_set[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A_set, comp, 0, i)
        while True:
            if A_set[j] == comp:
                if num[j] > 0:
                    if i != j:
                        ans += min(num[j], num[i])
                        num[j] = max(num[j] - num[i], 0)
                        break
                    elif num[j] >= 2:
                        add = num[j] // 2
                        ans += add
                        num[j] = num[j] % 2
                        break
                    else:
                        break
                else:
                    break
            else:
                break

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

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

INF = -1
H, W = map(int,input().split())
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = [[1,0], [-1,0], [0,1], [0,-1]]

def dfs():
    q = deque([])
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                q.append([h,w])
                Dist[h][w]=0
    while len(q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                q.append([hs,ws])
                Dist[hs][ws] = Dist[h][w] + 1

def main():
    dfs()
    print(max([max(Dist[h]) for h in range(H)]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())

INF = -1
Gmap = [list(input()) for _ in range(H)]
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Gmap[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        lv=Gmap[h][w]+1
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

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

import itertools
n = int(input())
a = list(map(int,input().split()))
a.sort()
#print(a)[1, 2, 7, 20, 30, 40]
A = list(itertools.accumulate(a))
#print(A)
cnt = 1
for i in range(n-1):
  s = A[i]
  #print(s)
  for j in range(i+1,n):
    if s*2 >= a[j] :
      s += a[j]
      #print(s)
    else:
      break
  if s == A[-1]:
    cnt += 1
print(cnt)    
      
    
    


### FIXED CODE ###

import itertools
n = int(input())
a = list(map(int,input().split()))
a.sort()
#print(a)[1, 2, 7, 20, 30, 40]
A = list(itertools.accumulate(a))
#print(A)[1, 3, 10, 30, 60, 100]
cnt = 0
for i in range(n-1):
  s = A[i]
  #この条件を満たしていないとそれ以上他のスライムを取り込めない
  if s*2 < a[i+1] :
    cnt = i+1

print(n-cnt)
### BUGGY CODE ###

from collections import deque

n = int(input())

q = deque()
for i in range(n):
    cmd = input().strip()
    if cmd == 'deleteFirst':
        q.popleft()
        continue
    if cmd == 'deleteLast':
        q.pop()
        continue
    cmd, x = cmd.split()
    x = int(x)
    if cmd == 'insert':
        q.appendleft(x)
        continue
    if cmd == 'delete':
        try:
            q.remove(x)
        except:
            pass
        continue

print(' '.join(map(str, q)))

### FIXED CODE ###

import sys
from collections import deque

n = int(sys.stdin.readline())
q = deque()
for i in range(n):
    cmd = sys.stdin.readline()[:-1]
    if cmd[0] == 'i':
        q.appendleft(cmd[7:])
    elif cmd[6] == ' ':
        try:
            q.remove(cmd[7:])
        except:
            pass
    elif cmd[6] == 'F':
        q.popleft()
    else:
        q.pop()

print(' '.join(q))
### BUGGY CODE ###

n = int(input())
a_list = [int(input()) for _ in range(n)]
for i in range(n):
    cp_list = a_list.copy()
    cp_list[i] = 0
    print(max(cp_list))
    

### FIXED CODE ###

n = int(input())
a_list = [int(input()) for _ in range(n)]
cp_list = a_list.copy()
cp_list.sort()
second_ans = cp_list[-2]
ans = cp_list[-1]
for i in range(n):
    if a_list[i] == ans:
        print(second_ans)
    else:
        print(ans)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
A = sorted([int(x) for x in input().split()])
card = np.zeros(N*2)
for i in range(N):
    card[i] = A[i]

for j in range(M):
    B, C = map(int, input().split())
    for k in range(B):
        if card[N+k] < C:
            card[N+k] = C
        else:
            break
    card = sorted(card, reverse=True)

ans = 0
for h in range(N):
    ans += card[h]
print("{}".format(int(ans)))


### FIXED CODE ###

# 未完成　要素と個数を別にしてソートすればいける？
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
cardnumberlist = []
card_dict = {}
for i in range(N):
    if A[i] in card_dict:
        card_dict[A[i]] += 1
    else:
        card_dict[A[i]] = 1
        cardnumberlist.append(A[i])

for j in range(M):
    B, C = map(int, input().split())
    if C in card_dict:
        card_dict[C] += B
    else:
        card_dict[C] = B
        cardnumberlist.append(C)
ans = 0
cardnumberlist = sorted(cardnumberlist, reverse=True)
# print(cardnumberlist)
# print(card_dict)
numofcard = 0
for h in range(N):
    #print(h)
    if numofcard + card_dict[cardnumberlist[h]] > N:
        ans += cardnumberlist[h] * (N - numofcard)
        break
    else:
        ans += cardnumberlist[h] * card_dict[cardnumberlist[h]]
        numofcard += card_dict[cardnumberlist[h]]
print(ans)
### BUGGY CODE ###

def _integral(A):
    result = []
    sum_value = 0
    result.append(sum_value)
    for i in range(len(A)):
        sum_value += A[i]
        result.append(sum_value)
    return result


def _main(N, M, K, A, B):
    integral_a = _integral(A)
    integral_b = _integral(B)
    top_count = 0
    for a_index in range(len(A) + 1)[::-1]:
        a_value = integral_a[a_index]
        if K < a_value:
            continue
        for b_index in range(len(B) + 1)[::-1]:
            if a_value + integral_b[b_index] <= K:
                if top_count < a_index + b_index:
                    top_count = a_index + b_index
                break
    print(top_count)
    #
    #
    # sum_k = 0.0
    # a_index = 0
    # a_len = len(A)
    # b_index = 0
    # b_len = len(B)
    # while sum_k < K:
    #     current_a = A[a_index] if a_index < a_len else None
    #     current_b = B[b_index] if b_index < b_len else None
    #     if current_a is None and current_b is None:
    #         break
    #
    #     if current_a is not None and current_b is None:
    #         if K < sum_k + current_a:
    #             break
    #         sum_k += current_a
    #         a_index += 1
    #     elif current_a is None and current_b is not None:
    #         if K < sum_k + current_b:
    #             break
    #         sum_k += current_b
    #         b_index += 1
    #     elif current_a < current_b:
    #         if K < sum_k + current_a:
    #             break
    #         sum_k += current_a
    #         a_index += 1
    #     else:
    #         if K < sum_k + current_b:
    #             break
    #         sum_k += current_b
    #         b_index += 1
    #
    # print(a_index + b_index)


if __name__ == "__main__":
    Na, Ma, Ka = map(int, input().split())
    Aa = list(map(float, input().split()))
    Ba = list(map(float, input().split()))
    _main(Na, Ma, Ka, Aa, Ba)


### FIXED CODE ###

def _integral(A):
    result = []
    sum_value = 0
    result.append(sum_value)
    for i in range(len(A)):
        sum_value += A[i]
        result.append(sum_value)
    return result


def _main(N, M, K, A, B):
    integral_a = _integral(A)
    integral_b = _integral(B)
    top_count = 0
    b_max = len(B)
    for a_index in range(len(A) + 1):
        a_value = integral_a[a_index]
        if K < a_value:
            break
        for b_index in range(0, min(len(B) + 1, b_max + 1))[::-1]:
            if a_value + integral_b[b_index] <= K:
                if top_count < a_index + b_index:
                    top_count = a_index + b_index
                b_max = b_index
                break
    print(top_count)


if __name__ == "__main__":
    Na, Ma, Ka = map(int, input().split())
    Aa = list(map(float, input().split()))
    Ba = list(map(float, input().split()))
    _main(Na, Ma, Ka, Aa, Ba)
### BUGGY CODE ###

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    P = []
    input_raw = read_func().strip().split()
    for i in range(N):
        P.append(float(input_raw[i]))

    dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
    dp[0][0] = 1
    for i in range(0, N):
        for j in range(0, i + 1):
            dp[i + 1][j] += (1.0 - P[i]) * dp[i][j]
            dp[i + 1][j + 1] += P[i] * dp[i][j]

            #dp[i][j] += p[i] * dp[i - 1][j - 1] + (1 - p[i])

    count = 0L
    for j in range(N/2 + N%2, N + 1):
        count += dp[N][j]
    print count
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    P = []
    input_raw = read_func().strip().split()
    for i in range(N):
        P.append(float(input_raw[i]))

    dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
    dp[0][0] = 1
    for i in range(0, N):
        for j in range(0, i + 1):
            dp[i + 1][j] += (1.0 - P[i]) * dp[i][j]
            dp[i + 1][j + 1] += P[i] * dp[i][j]

            #dp[i][j] += p[i] * dp[i - 1][j - 1] + (1 - p[i])

    count = 0L
    for j in range(N/2 + N%2, N + 1):
        count += dp[N][j]
    print count
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [""]*(N+1)
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(2, N+1):
        cur = (int(dp[i]) if dp[i] else 0)
        for a in A:
            if match[a] == i or (i - match[a] >= 0 and dp[i - match[a]]):
                ne = int(dp[i - match[a]] + str(a))
                if cur < ne:
                    dp[i] = str(ne)
                    cur = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    dp = ["-"]*(N+10)
    dp[0] = ""
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(N+1):
        if dp[i] == "-":
            continue
        for a in A:
            cur = dp[i+match[a]]
            ne = dp[i] + str(a)
            if len(cur) < len(ne) or cur < ne:
                dp[i+match[a]] = ne
    # print(dp)
    print(dp[N])


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

s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 4 for i in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    if s[i] == "A":
        dp[i + 1][1] = dp[i + 1][1] + dp[i][0]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    elif s[i] == "B":
        dp[i + 1][2] = dp[i + 1][2] + dp[i][1]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    elif s[i] == "C":
        dp[i + 1][3] = dp[i + 1][3] + dp[i][2]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    else:
        for j in range(4):
            dp[i + 1][j] += 3 * dp[i][j]
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][3] += dp[i][2]

print(dp[n][3] % mod)


### FIXED CODE ###

s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 4 for i in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    if s[i] == "A":
        dp[i + 1][1] = dp[i + 1][1] + dp[i][0]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    elif s[i] == "B":
        dp[i + 1][2] = dp[i + 1][2] + dp[i][1]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    elif s[i] == "C":
        dp[i + 1][3] = dp[i + 1][3] + dp[i][2]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    else:
        for j in range(4):
            dp[i + 1][j] += 3 * dp[i][j]
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][3] += dp[i][2]
    for j in range(4):
        dp[i + 1][0] %= mod
        dp[i + 1][1] %= mod
        dp[i + 1][2] %= mod
        dp[i + 1][3] %= mod

print(dp[n][3] % mod)
### BUGGY CODE ###

K= int(input())

if K%2==0:
    print('-1')
else:
    t=True
    n=1
    a=7
    while t:
        if a%K!=0:
            a=(10*a+7)%K
            n+=1
        else:
            t=False
            print(n)

### FIXED CODE ###

K= int(input())

if K%2==0:
    print('-1')
else:
    t=True
    n=1
    a=7
    
    while t:
        if n>K:
            t=False
            print('-1')
        if a%K!=0:
            a=(10*a+7)%K
            n+=1
        else:
            t=False
            print(n)