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

N = int(input())


def lukas(n):
	if n == 1:
		return 2
	if n == 2:
		return 1
	else:
		return lukas(n-1) + lukas(n-2)
		
print(lukas(N+1))	
	
		

### FIXED CODE ###

n = int(input())

lucas = []
lucas.append(2)
lucas.append(1)

if n >= 2:
	for i in range(2,n+1):
		lucas.append(lucas[i-1] + lucas[i-2])
	print(lucas[n])
else:
	print(lucas[n])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
l = collections.Counter(a)
for i in range(n):
    print(l[i+1])
### BUGGY CODE ###

# https://atcoder.jp/contests/abc133/tasks/abc133_e

# あー解説あたまいい
# そのノードで塗れる色の候補を持つのではなくて、
# そのノードの子で塗れる通りの数を持っておく
# あるノードの子で塗れる通りの数は、親とそのノードで塗る色の通りも確定してると考えると、(K-2)P(子の数)となる。(自身が根のときは自身の色の通りも考慮して、(K)P(子の数+1)となる)
# これをdfsで実装すれば良い

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


MOD = 10**9 + 7

N, K = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a, b = mina(a, b)
    tree[a].append(b)
    tree[b].append(a)


def perm_mod(n, r, mod=MOD):
    # assert n >= r
    ret = 1
    for _ in range(r):
        ret *= n
        ret %= mod
        n -= 1
    return ret


def dfs(u, p):  # 現在のuと親のp
    if len(tree[u]) == 1 and tree[u][0] == p:
        # 葉なので終了
        return 1
    ret = 1  # その地点までの通りの数
    for to in tree[u]:
        if to == p:
            continue
        ret *= dfs(to, u)
        ret %= MOD
    if p == -1:
        ret *= perm_mod(K, len(tree[u]) + 1)
    else:
        ret *= perm_mod(K - 2, len(tree[u]) - 1)

    return ret % MOD


print(dfs(0, -1))


### FIXED CODE ###

# https://atcoder.jp/contests/abc133/tasks/abc133_e

# あー解説あたまいい
# そのノードで塗れる色の候補を持つのではなくて、
# そのノードの子で塗れる通りの数を持っておく
# あるノードの子で塗れる通りの数は、親とそのノードで塗る色の通りも確定してると考えると、(K-2)P(子の数)となる。(自身が根のときは自身の色の通りも考慮して、(K)P(子の数+1)となる)
# これをdfsで実装すれば良い

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


MOD = 10**9 + 7

N, K = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a, b = mina(a, b)
    tree[a].append(b)
    tree[b].append(a)


def perm_mod(n, r, mod=MOD):
    # assert n >= r
    ret = 1
    for _ in range(r):
        ret *= n
        ret %= mod
        n -= 1
    return ret


def dfs(u, p):  # 現在のuと親のp
    if len(tree[u]) == 1 and tree[u][0] == p:
        # 葉なので終了
        return 1
    ret = 1  # その地点までの通りの数
    for to in tree[u]:
        if to == p:
            continue
        ret *= dfs(to, u)
        ret %= MOD
    if p == -1:
        ret *= perm_mod(K, len(tree[u]) + 1)
    else:
        ret *= perm_mod(K - 2, len(tree[u]) - 1)

    return ret % MOD


print(dfs(0, -1))
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
K = list(map(int,input().split()))

for ii in range(q):
    D = [[0] * 3 for i in range(n)]
    ans = 0
    k = K[ii]
    for i in range(n):
        for j in range(3):
            D[i][j] = D[i-1][j]
        
        if i-k >= 0:
            if s[i-k] == "D":
                D[i][0] -= 1
                D[i][2] -= D[i][1]
            if s[i-k] == "M":
                D[i][1] -= 1
        
        if s[i] == "D":
            D[i][0] += 1
        if s[i] == "M":
            D[i][1] += 1
            D[i][2] += D[i][0]
        if s[i] == "C":
            ans += D[i][2]
    print(ans)
    # print(D)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()
    q = int(input())
    K = list(map(int,input().split()))
    # print(s)

    for i in range(q):
        ans = 0
        d = 0
        m = 0
        dm = 0
        k = K[i]
        for j in range(n):

            if j-k >= 0:
                if s[j-k] == "D":
                    d -= 1
                    dm -= m
                elif s[j-k] == "M":
                    m -= 1

            if s[j] == "D":
                d += 1
            elif s[j] == "M":
                m += 1
                dm += d
            elif s[j] == "C":
                ans += dm
        print(ans)

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


s = input()
q = int(input())
#query = []
#for i in range(q):
 #   query.append(input())

def rev(s):
    return "".join(list(reversed(s)))



for i in range(q):
    inp = input().split()
    if inp[0] == "1":
        s = rev(s)
    elif inp[1] == "1":
        s = inp[2] + s
    else:
        s = s + inp[2]


print(s)

### FIXED CODE ###

from collections import deque

#inp = list(map(lambda x: int(x), input().split()))
#n,k = map(lambda x: int(x), input().split())
#p_n = list(map(lambda x:int(x),input().split()))


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


cnt = 0
for i in range(q):
    inp = input().split()
    if inp[0] == "1":
        cnt += 1
    else:
        if inp[1] == "1":
            if cnt % 2 == 0:
                s.appendleft(inp[2])
            else:
                s.append(inp[2])
        else:
            if cnt % 2 == 0:
                s.append(inp[2])
            else:
                s.appendleft(inp[2])

ans = list(s)

if cnt % 2 == 1:
    ans = ans[::-1]

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

import heapq
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    cnt = 0   
    for i in range(N):
        S = 0
        for j in range(i, N):
            S += A[j]
            if S%M == 0:
                cnt += 1
    
    print(cnt)


if __name__ == '__main__':
    main()

### FIXED CODE ###

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


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    S = [0]*(N+1)           # S[i] means sum(A[0:i])%M
    for i in range(N):
        S[i+1] = (S[i] + A[i]) % M
    
    d = defaultdict(int)
    ans = 0
    for i in range(N+1):
        ans += d[S[i]]
        d[S[i]] += 1
        # print([S[i], ans])
        # print(d)
    
    print(ans)


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

n = int(input())
l = list(map(int, input().split()))
s = 0
for i in range(n-2):
  a = l[i]
  for j in range(i+1,n-1):
      b = l[j]
      for k in range(j+1,n):
        c = l[k]
        if a<b+c and b<c+a and c<a+b:
          s += 1
print(s)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
s = 0
for i in range(0,n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    s += bisect.bisect_left(l,a+b,j+1)-j-1
print(s)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline().rstrip('\n')


def calc(N, A):
    result = 0
    for i in range(N):
        a = A[i]
        for j in range(i + 1, N):
            if a == j - i - A[j]:
                result += 1
    return result
    

N = int(input())
A = [int(s) for s in input().split()]
print(calc(N, A))

### FIXED CODE ###

import math
import sys
def input():
    return sys.stdin.readline().rstrip('\n')


def calc(N, A):
    result = 0
    diff = [i - A[i] for i in range(N)]
    d1 = {}
    for x in diff:
        d1[x] = (d1[x] if x in d1 else 0) + 1 
    plus = [i + A[i] for i in range(N)]
    d2 = {}
    for x in plus:
        d2[x] = (d2[x] if x in d2 else 0) + 1
    for x in d1:
        y = d2[x] if x in d2 else 0
        result += d1[x] * y
    return result
    

N = int(input())
A = [int(s) for s in input().split()]
print(calc(N, A))
### BUGGY CODE ###

import numpy as np
in1=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(in1[0]):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
test=[]
out=[]
for k in range(Q):
    ans=0
    start,end=list(map(int,input().split(" ")))
    #place=np.where(arr==start)
    place=d[start]
    #print(start,end)
    while start != end:
        #print("ans",ans)
        #nextplace=np.where(arr==start+in1[2])#[1][0]
        nextplace=d[start+in1[2]]
        ans+=abs(int(nextplace[0])-int(place[0]))
        ans+=abs(int(nextplace[1])-int(place[1]))
        start+=in1[2]
        place=nextplace

    print(ans)
    #out.append(ans)
#for i in out:
    #print(i)


### FIXED CODE ###

import numpy as np
H, W, D=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(H):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
out=[]

cost={}

for i in range(1,D+1):
    now = i + D
    cost[i]=0
    #cost[i]=abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
    while now <= H * W:
        cost[now] = cost[now - D] + abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
        now += D


out=[]
for k in range(Q):
    start,end=list(map(int,input().split(" ")))
    out.append(cost[end]-cost[start])

for i in out:
    print(int(i))
### BUGGY CODE ###

from collections import Counter

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

cnt = Counter(As)
As.sort(reverse=True)

Ps = [2]
for i in range(58):
    Ps.append(Ps[-1] * 2)
Ps = Ps[::-1]

ans = 0
for A in As:
    if cnt[A] <= 0: continue
    cnt[A] -= 1
    for P in Ps:
        if cnt[P - A] > 0:
            ans += 1
            cnt[P - A] -= 1
            break
print(ans)


### FIXED CODE ###

from collections import Counter

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

cnt = Counter(As)
As.sort(reverse=True)

Ps = [2]
for i in range(58):
    Ps.append(Ps[-1] * 2)
Ps = Ps[::-1]

ans = 0
for A in As:
    if cnt[A] <= 0: continue
    cnt[A] -= 1
    for P in Ps:
        if cnt[P - A] > 0:
            ans += 1
            cnt[P - A] -= 1
            break
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [[] for _ in [0]*N]
Eb = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    Eb[b-1].append(a-1)

r = 0
while Eb[r]: r=Eb[r][0]

d = [-1]*N
d[r] = 0
q = [r]
while q:
    qq = []
    for i in q:
        di = d[i]
        for j in E[i]:
            if d[j]>=di+1:continue
            d[j] = di+1
            q.append(j)
    q = qq

p=[0]*N
for i in range(N):
    di = d[i]
    for j in Eb[i]:
        if d[j]==di-1:
            p[i] = j+1

print(*p,sep="\n")

### FIXED CODE ###

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [set() for _ in [0]*N]
E2 = [set() for _ in [0]*N]
Eb = [set() for _ in [0]*N]
for a,b in AB:
    E[a-1].add(b-1)
    E2[a-1].add(b-1)
    Eb[b-1].add(a-1)

p = [0]*N
q = []
for i in range(N):
    if not E[i]:
        q.append(i)
while q:
    qq = set()
    for i in q:
        for j in Eb[i]:
            E[j].remove(i)
    for i in q:
        while Eb[i]:
            j = Eb[i].pop()
            if not E[j]:
                for k in E2[j]:
                    if p[k] == 0 : p[k] = j+1
                qq.add(j)
    q = qq

print(*p,sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

MOD = 1000000007

n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
steps = [0] * (n + 1)
steps[0] = 1

for now in range(n):
    for next_ in range(now + 1, min(now + 2, n) + 1):
        if next_ not in a:
            steps[next_] += steps[now]
            steps[next_] %= MOD
print(steps[-1])



### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = 1000000007


def main():
    n, m = [int(i) for i in input().split()]
    a = {int(input()) for _ in range(m)}
    steps = [0] * (n + 1)
    steps[0] = 1

    for now in range(n):
        for next_ in range(now + 1, min(now + 2, n) + 1):
            if next_ not in a:
                steps[next_] += steps[now] % MOD
                steps[next_] %= MOD
    print(steps[-1])


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

mod = 10**9 + 7
N = int(input())
array = [int(i) for i in input().split()]

output = 0
for i in range(N):
    for j in range(i+1, N):
        output += (array[i]%mod) * (array[j]%mod)
        
print(output%mod)

### FIXED CODE ###

mod = 10**9 + 7
N = int(input())
array = [int(i) for i in input().split()]
array_2 = [0]

for a in array:
    array_2.append(array_2[-1]+a)
    
output = 0
for i in range(len(array)-1):
    output += array[i] * (array_2[-1] - array_2[i+1])
    
print(output%mod)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
C = III()
C.sort()

ans = 0
for i in range(N):
    ans += 4**(N-1)*C[i]*(N-i+1)
    ans %= mod

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
C = III()
C.sort()

ans = 0
for i in range(N):
    ans += pow(4,N-1,mod)*C[i]*(N-i+1)
    ans %= mod

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

import sys
N=int(input())
if N>10**5 or N<2:
    sys.exit()
a=input().split(' ')
if N<len(a):
    sys.exit()
s=1
for i in range(N):
    s*=int(a[i])
if s<=10**18:
    print(s)
else:
    print("-1")

### FIXED CODE ###

import sys
N=int(input())
a=list(map(int, input().split()))
s=1
# aに0がある場合を省く
if 0 in a:
    print(0)
    sys.exit()
else:
# sが10^18になったら打ち切る
    for i in a:
        if s<10**18:
            s*=i
    if s>10**18:
        print(-1)
        sys.exit()
    print(s)
### BUGGY CODE ###

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

dp = [[[ 0 for _ in range(50*N + 5)] for _ in range(N+1) ] for _ in range(N+1)]

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(N+1):
        for k in range(50*N+1):
            dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

ans = 0
for i in range(1, N+1):
    ans += dp[N][i][A * i]
print(ans)


### FIXED CODE ###

N, A = map(int,input().split())
X = list(map(int,input().split()))
dp = [[[0 for _ in range(50*50 + 1)] for _ in range(N+1)] for _ in range(N+1)]

dp[0][0][0] = 1
for i in range(1, N+1):
    for j in range(i+1):
        for k in range(50*j+1):
            dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

ans = 0
for i in range(1, N+1):
    ans += dp[N][i][A * i]
print(ans)
### BUGGY CODE ###

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

dp[0][0] = 1
for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i + 1][j] = dp[i][j] * 3
        else:
            dp[i + 1][j] = dp[i][j]
            
    if S[i] == 'A' or S[i] == '?':
        dp[i + 1][1] += dp[i][0]
    if S[i] == 'B' or S[i] == '?':
        dp[i + 1][2] += dp[i][1]
    if S[i] == 'C' or S[i] == '?':
        dp[i + 1][3] += dp[i][2]
        
print(dp[len(S)][3] % mod)

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
abc = 0
bc = 0
c = 0
q = 0

for i in S[::-1]:
    if i == 'A':
        abc = (bc + abc) % mod
    if i == 'B':
        bc = (c + bc) % mod
    if i == 'C':
        c = (pow(3, q, mod) + c ) % mod
    if i == '?':
        abc = (abc * 3 + bc) % mod
        bc = (bc * 3 + c) % mod
        c = (pow(3, q, mod) + c * 3) % mod
        q += 1
        
print(int(abc))
### BUGGY CODE ###

# D
import numpy as np
S = input()
N = len(S)
dp = [[0 for i in range(13)] for j in range(N+5)]
mod = 10**9+7

dp[N][0] = 1
# DP = np.array(dp)
# print(DP)
mul = 1
for i in reversed(range(N)):
    if(S[i]=='?'):
        c = -1
    else:
        c = int(S[i])

    for j in range(10):
        if(c != -1 and c != j):
            continue
        for k in range(13):
            dp[i][(j*mul+k)%13] += dp[i+1][k]
            dp[i][(j*mul+k)%13] %= mod
    mul *=10
    mul %=13
# DP = np.array(dp)
result = dp[0][5]
# print(DP)
print(result)


### FIXED CODE ###

S = input()
N = len(S)
dp = [[0 for i in range(13)] for j in range(N+5)]
mod = 10**9+7

dp[N][0] = 1
# DP = np.array(dp)
# print(DP)
mul = 1
for i in reversed(range(N)):
    if(S[i]=='?'):
        c = -1
    else:
        c = int(S[i])

    for j in range(10):
        if(c != -1 and c != j):
            continue
        for k in range(13):
            dp[i][(j*mul+k)%13] += dp[i+1][k]
            dp[i][(j*mul+k)%13] %= mod
    mul *=10
    mul %=13

# DP = np.array(dp)
result = dp[0][5]
# print(DP)
print(result)
### BUGGY CODE ###

S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7

if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD

print(dp[-1][5])

### FIXED CODE ###

S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7

if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD

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

import numpy
import itertools
import math
n = int(input())
town_list = []
for i in range(n):
	x, y = map(int, input().split())
	town_list.append(numpy.array([x, y]))

pattern_list = list(itertools.permutations(town_list, n))

sum = 0
for j in range(math.factorial(n)):
	for k in range(n-1):
		sum += numpy.linalg.norm(pattern_list[j][k+1] - pattern_list[j][k])

print(sum/math.factorial(n))

### FIXED CODE ###

import numpy
import itertools
import math

n = int(input())
town_list = []
for i in range(n):
	x, y = map(int, input().split())
	town_list.append([x, y])

pattern_list = list(itertools.permutations(town_list, n))

a = int(math.factorial(n))

sum = 0
for j in range(a):
	for k in range(n-1):
		# sum += numpy.linalg.norm(pattern_list[j][k+1] - pattern_list[j][k])
		x1 = pattern_list[j][k][0]
		x2 = pattern_list[j][k+1][0]
		y1 = pattern_list[j][k][1]
		y2 = pattern_list[j][k+1][1]
		sum += math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

print(sum/a)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=[0]*k
ans=0
for i in range(k):
    a[i]=p[i]
ans=sum(a)
for i in range(n):
    a.remove(a[0])
    a.append(p[i])
    if ans<sum(a):
        ans=sum(a)
print((ans+k)*0.5)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
for i in range(k):
    ans+=p[i]
pre=ans
for i in range(k,n,1):
    pre=(pre+p[i]-p[i-k])
    if ans<pre:
        ans=pre
print((ans+k)*0.5)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(200000)

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

def sum(a, b):
    if b == 0:
        return a[b]
    else:
        return a[b] + sum(a, b-1)
sumA = []
for i in range(N):
    sumA.append(sum(A, i))

ans = 0

for i in range(N):
    if sumA[-1] // 2 > sumA[i]:
        continue
    else:
        if i == 0:
            ans = abs(sumA[i] * 2 - sumA[-1])
            break
        else:
            ans = min(abs(sumA[i] * 2 - sumA[-1]), abs(sumA[i-1] * 2 - sumA[-1]))
            break

print(ans)

### FIXED CODE ###

import sys
    
sys.setrecursionlimit(200000)
    
N = int(input())
A = list(map(int, input().split(' ')))
    

sumA = []
for i in range(N):
    if i == 0:
        sumA.append(A[i])
    else:
        sumA.append(sumA[-1] + A[i])
    
ans = 0
    
for i in range(N):
    if sumA[-1] // 2 > sumA[i]:
        continue
    else:
        if i == 0:
            ans = abs(sumA[i] * 2 - sumA[-1])
            break
        else:
            ans = min(abs(sumA[i] * 2 - sumA[-1]), abs(sumA[i-1] * 2 - sumA[-1]))
            break
    
print(ans)
### BUGGY CODE ###

import math
numbers =input().rstrip().split(" ")
N =int(numbers[0])
a =int(numbers[1])
b =int(numbers[2])
Ya=math.factorial(a)
Yb=math.factorial(b)
Xa=1
Xb=1
for i in range(a):
    Xa=Xa*(N-i)
for i in range(b):
    Xb=Xb*(N-i)

d=1000000007
#answer is 2**N-nca-ncb-1 mod d
A=pow(2,N)
B=Xa*pow(Ya,d-2)
C=Xb*pow(Yb,d-2)
answer=(A+B+C-1)%d
print(answer)

### FIXED CODE ###

def cmod(n, r, p):
    x,y  = 1, 1
    for i in range(r):
        x = x * (n - i) % p
        y = y * (r - i) % p
    return (x * pow(y, p - 2, p)) % p


n, a, b = map(int, (input().split()))
p = 10 ** 9 + 7
print((pow(2, n, p) - 1 - cmod(n, a, p) - cmod(n, b, p)) % p)
### BUGGY CODE ###

from math import ceil,floor
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
first =1

for i in range(P,N):
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
        
    if b<=0:
        if A[P-1]<=target:
            ans+=1
    else:
        if target<A[P-1]:
            break
        if first==1:
            Q = A[P-1:i]
            Q_sum=sum(Q)
            len_Q =len(Q)
        else:
            Q_sum+=A[i-1]
            len_Q+=1
        if target*len_Q-Q_sum>=b*M:
            ans+=1
        else:
            break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
           
right = P-1
left = N

while left - right !=1:
    
    i = (left+right)//2
    b = (V-((P-1)+(N-i)))
    target = A[i]+M

        
    if b<0:
        if A[P-1]<=target:
            right = i
        else:
            left = i
    else:
        if target<A[P-1]:
            left = i
        else:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
            if target*len_Q-Q_sum>=b*M:
                right = i
            else:
                left =i


print(right+1)
### BUGGY CODE ###

num = int(input())

s = 7
c = 0
a = []


def prime_factorize(n):
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if num % 2 == 0:
    print(-1)

else:
    while True:
        c += 1
        prime_factorize(s)
        if num in a:
            print(c)
            break
        else:
            s = s * 10 + 7
        


### FIXED CODE ###

k = int(input())
m = 7%k

for i in range(1, 10**6+1):
    if m == 0:
        print(i)
        exit()
    else:
        m = (10 * m + 7) % k

print(-1)