Harryxun/stf_run huggingface dataset:
LARGE = 1000000007


def step(a, i):
    if i == len(a):
        return 1
    elif i > len(a):
        return 0

    elif a[i] == 0:
        return 0

    return step(a, i + 1) + step(a, i + 2)


def solve():
    n, m = [int(x) for x in input().split()]
    a = [1] * n
    for _ in range(m):
        a[int(input()) - 1] = 0

    # print(n, m)
    # print(a)
    # ans = step(a, 0)

    f = [0] * n
    if a[0] == 0:
        f[0] = 0
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 1
    else:
        a[0] = 1
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 2

    if a[1] == 0:
        f[1] = 0

    # print(f)
    for i in range(2, n):
        # print(i)
        if a[i]:
            f[i] = (f[i-1] + f[i-2])
    # print(f)
    print(f[n-1] % LARGE)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# inputs
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

# solve
dp = [1] * (n+1)

for i in a:
    dp[i] = 0

for i in range(2, n+1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)

print(dp[n])
h, w, d = [int(i) for i in input().split()]
a = [[int(j)-1 for j in input().split()] for i in range(h)]

q = int(input())#moving num
l = [0 for i in range(q)]#start number
r = [0 for i in range(q)]#finish number

for i in range(q):
    tmp = input().split()
    l[i]=int(tmp[0])-1
    r[i]=int(tmp[1])-1
loc = [[0, 0] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        loc[a[i][j]][0] = i
        loc[a[i][j]][1] = j
#print(loc)
cost = [0 for i in range(int((h*w)/d))]
#print(cost)
for i in range(1, len(cost)):
    cost[i] += abs(loc[(i+1)*d-1][0]-loc[i*d-1][0])
    cost[i] += abs(loc[(i+1)*d-1][1]-loc[i*d-1][1])
#print(cost)
for i in range(1, len(cost)):
    cost[i] += cost[i-1]
#print(cost)

for i in range(q):
    print(cost[int(r[i]/d)]-cost[int(l[i]/d)])


### FIXED CODE ###

import math
def func(h, w, d, a, query):
    imos = [0 for _ in range(h*w)]
    pos = [[0, 0] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            pos[a[i][j]] = [i, j]
    for i in range(d):
        for j in range(math.ceil((h*w-i)/d)):
            if j == 0:
                continue
            else:
                imos[i + d * j] = imos[i + d * (j-1)]\
                                  + abs(pos[i + d * j][0] - pos[i + d * (j-1)][0])\
                                  + abs(pos[i + d * j][1] - pos[i + d * (j-1)][1])
    for i in range(len(query)):
        print(imos[query[i][1]] - imos[query[i][0]])
    return
h, w, d = [int(i) for i in input().split()]
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    a[i] = [int(i) - 1 for i in input().split()]
q = int(input())
query = [[0, 0] for _ in range(q)]
for i in range(q):
    query[i] = [int(i) - 1 for i in input().split()]
func(h, w, d, a, query)
"""
func(3, 3, 2, [[0, 3, 2], [1, 4, 6], [7, 8, 5]], [[3, 7]])
print("ans: 5\n")
func(4, 2, 3, [[2, 6], [0, 3], [4, 1], [5, 7]], [[1, 1], [1, 1]])
print("ans: 0, 0\n")
func(5, 5, 4, [[12, 24, 6, 14, 16], [15, 21, 19, 1, 8], [13, 10, 11, 0, 18], [9, 5, 22, 7, 17], [2, 20, 4, 23, 3]], [[12, 12], [1, 9], [12, 12]])
print("ans: 0, 5, 0")
"""
# print("func({}, {}, {}, {}, {})".format(h, w, d, a, query))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

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

ticket_sum = [0]*(N*N)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*(N+1)
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (not filled[i-1]) else left[i-1]
        r = i if (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
	        if i<N-1:
                ticket_sum[(i+1)*N+r+1]+=x

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

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

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)
N = int(input())
A = tuple(int(input()) for i in range(N)

B = list(A)

for j in range(N):
    B.pop(j)
    print(max(B))
    B = list(A)

### FIXED CODE ###

N = int(input())
A = list(int(input()) for i in range(N))

max_value = max(A)
number = A.count(max_value)

if number > 1:
    for j in range(N):
        print(max_value)
else:
    position = A.index(max_value)
    A.remove(max_value)
    for j in range(N):
        if j == position:
            print(max(A))
        else:
            print(max_value)
def solve(n, k, aaa):
    buf = []
    prev_last = -1

    for t in range(k + 1):
        ma, mi = min((a, i + 1) for i, a in enumerate(aaa) if i + 1 != prev_last)
        others = set(range(1, n + 1)) - {prev_last, mi}
        buf.extend(others)
        if t == k:
            aaa[mi] += 1
        else:
            buf.append(mi)

        for i in range(n):
            if i + 1 != prev_last:
                aaa[i] -= 1
                if aaa[i] < 0:
                    print(-1)
                    return

        prev_last = mi

    print(len(buf))
    print(*buf)


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


### FIXED CODE ###

def solve(n, k, aaa):
    buf = []
    prev_last = -1

    for t in range(k + 1):
        ma, mi = min((a, i + 1) for i, a in enumerate(aaa) if i + 1 != prev_last)
        others = set(range(1, n + 1)) - {prev_last, mi}
        buf.extend(others)
        buf.append(mi)
        # print(buf)

        for i in range(n):
            if i + 1 != prev_last:
                aaa[i] -= 1
                if aaa[i] < 0:
                    print(-1)
                    return

        prev_last = mi

    print(len(buf))
    print(*buf)


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
solve(n, k, aaa)
s = input()
l = len(s)
if s[0] !="A":
    print("WA")
    break
else:
    s = s.replace(s[0],"a")
    index1 = s.find("C")
    index2 = s.find("C", 2)
    if index2 != -1 or (index1 < 2 or index1 > l-3):
        print("WA")
    else:
        s = s.replace("A","a")
        s_lower = s.lower()
        if s != s_lower:
            print("WA")
        else:
            print("AC")

### FIXED CODE ###

#104
s = input()
if(s[0]=='A' and s[2:-1].count('C')==1):
    s1 = s.replace('A', "").replace("C","")
    if(s1==s1.lower()):
        print("AC")
    else:
        print("WA")
else:
    print("WA")
#ABC138D
def main():
    import sys
    N, Q = map(int, sys.stdin.readline().split())
    ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N-1)]
    px = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    
    edge = [[] for _ in range(N)]
    #有向グラフ
    for row in ab:
        edge[row[0]-1].append(row[1]-1)
    #print(edge)
    point_list = [0 for i in range(N)]
    for row in px:
        point_list[row[0]-1] += row[1]
    #print(point_list)
    
    sys.setrecursionlimit(100000)
    visited = [-1 for _ in range(N)]
    visited[0] = 0
    def dfs(p):
        for c in edge[p]:
            if visited[c]==-1:
                visited[c]=0
                point_list[c] +=point_list[p]
                dfs(c)
            
    
    dfs(0)
    #print(visited)
    print(*point_list)
        



if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(1000000)

n,q = map(int, input().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

v = [deque([]) for i in range(n)]
for e in a_b:
    v[e[0]-1]+=[e[1]-1]
    v[e[1]-1]+=[e[0]-1]
score = [0 for i in range(n)]
for e in p_x:
    score[e[0]-1]+=e[1]
def dfs(p, bp=-1):
    while v[p]:
        c =v[p].popleft()
        if c ==bp:
            continue
        #print(p, c, bp)
        score[c]+=score[p]
        dfs(c, bp=p)
visited = [0]                
dfs(0)
print(*score)
import math

a,b = map(lambda x:int(x), input().split())


print(math.ceil(a*b/math.gcd(a,b)))





### FIXED CODE ###

import fractions
import math

a,b = map(lambda x:int(x), input().split())


print(math.ceil(a*b/fractions.gcd(a,b)))
N = int(input())
S = input()
s_list = list(S)
count_1 = 0
count_2 = 0
for i in range(N-1):
    if s_list[i] == "#" and s_list[i+1] == ".":
        temp_start = i
        break

for i in range(N)[::-1]:
    if s_list[i] != "#":
        temp_end = i
        break

for i in range(temp_start,temp_end + 1):
    if s_list[i] == "#":
        count_1 += 1
    else :
        count_2 += 1
print(min(count_1,count_2))

### FIXED CODE ###

import fractions,math,sys
from collections import Counter
n = int(input())
s = list(input())
cnt = Counter(s)
white_l = 0
black_l = 0
min = cnt['.']
for i in range(n):
    if s[i] == '#':
        black_l += 1
        cnt['#'] -= 1
    else:
        white_l += 1
        cnt['.'] -= 1
    if black_l + cnt['.'] < min:
        min = black_l + cnt['.']
print(min)
from collections import deque
INFTY = 10**10
N,M = map(int,input().split())
if N==1:
    ind = 0
else:
    G = {}
    for _ in range(M):
        L,R,D = map(int,input().split())
        if L not in G:
            G[L]=[]
        G[L].append((R,D))
        if R not in G:
            G[R] = []
        G[R].append((L,-D))
    dist = [INFTY for _ in range(N+1)]
    hist = [0 for _ in range(N+1)]
    for i in G:
        heap = deque([i])
        ind = 2
        while heap:
            cur = heap.popleft()
            if hist[cur]==0:
                dist[cur] = 0
                hist[cur]=1
                ind = 0
            elif hist[cur]==1 and ind==2:
                break
            for x in G[cur]:
                v,w = x[0],x[1]
                if hist[v]==0:
                    dist[v] = dist[cur]+w
                    heap.append(v)
                    hist[v]=1
                else:
                    if dist[v]!=dist[cur]+w:
                        ind = 1
                        break
            if ind==1:break
        if ind==1:break
if ind!=1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from collections import deque
INFTY = 10**10
N,M = map(int,input().split())
ind = 2
if N==1:
    ind = 0
else:
    G = {}
    for _ in range(M):
        L,R,D = map(int,input().split())
        if L not in G:
            G[L]=[]
        G[L].append((R,D))
        if R not in G:
            G[R] = []
        G[R].append((L,-D))
    dist = [INFTY for _ in range(N+1)]
    hist = [0 for _ in range(N+1)]
    for i in G:
        ind = 2
        heap = deque([i])
        while heap:
            cur = heap.popleft()
            if hist[cur]==0:
                dist[cur] = 0
                hist[cur]=1
                ind = 0
            elif hist[cur]==1 and ind==2:
                break
            for x in G[cur]:
                v,w = x[0],x[1]
                if hist[v]==0:
                    dist[v] = dist[cur]+w
                    heap.append(v)
                    hist[v]=1
                else:
                    if dist[v]!=dist[cur]+w:
                        ind = 1
                        break
            if ind==1:break
        if ind==1:break
if ind!=1:
    print("Yes")
else:
    print("No")
from math import gcd
N = int(input())
A = list(map(int,input().split()))
# N=3
# A=[12 ,15 ,18]
l=[0]*N
r=[0]*N
l[0]=A[0]
r[0]=A[N-1]
for i in range(1,N-1):
    l[i]=gcd(l[i-1],A[i])
    r[i]=gcd(r[i-1],A[i])    
gcdlist = [l[N-2],r[N-2]]
for i in range(N-2):
    gcdlist.append(gcd(l[i],r[N-3-i]))
print(gcdlist)
print(max(gcdlist))

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
# N=3
# A=[12 ,15 ,18]
l=[0]*N
r=[0]*N
l[0]=A[0]
r[0]=A[N-1]
for i in range(1,N-1):
    l[i]=gcd(l[i-1],A[i])
    r[i]=gcd(r[i-1],A[N-1-i])    
gcdlist = [1,l[N-2],r[N-2]]
for i in range(N-2):
    gcdlist.append(gcd(l[i],r[N-3-i]))
#print(gcdlist)
print(max(gcdlist))
import math

def factorization(n):
    arr = []
    tmp = n
    for div in range(2, int(-(-n**0.5//1))+1):
        if tmp % div == 0:
            cnt = 0
            while tmp % div == 0:
                cnt += 1
                tmp //= div
            arr.append([div, cnt])

    if tmp != 1:
        arr.append([tmp, 1])

    if len(arr) == 0:
        arr.append([n, 1])

    return arr

if __name__ == '__main__':
    A, B = map(int, input().split())
    gcd = math.gcd(A, B)
    if gcd == 1:
        print(1)
        exit()
    facts = factorization(gcd)
    print(len(facts) + 1)

### FIXED CODE ###

import math
import fractions
gcd = math.gcd if hasattr(math, "gcd") else fractions.gcd

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

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

g = gcd(A, B)

print(len(set(factorize(g)))+1)
import sys

lines = sys.stdin.readlines()

H, M = list(map(int, lines[0].split()))
AB = []

max_at = 0
min_mg = 999999
at_min_mg = 0
for i in range(M):
  t = tuple(map(int, lines[i+1].split()))
  AB.append(t)
  if t[0]>max_at:
    max_at = t[0]
  if t[1]<min_mg:
    min_mg = t[1]
    at_min_mg = t[0]

ABlen = len(AB)

DP = [0]
for i in range(1, at_min_mg+1):
  DP.append(min_mg)
  
for i in range(at_min_mg+1,H+max_at):
  mm = 99999999
  for j in range(ABlen):
    if i-AB[j][0]<0:
      continue
    if mm > DP[i-AB[j][0]]+AB[j][1]:
      mm = DP[i-AB[j][0]]+AB[j][1]
  DP.append(mm)
print(min(DP[H:H+max_at-1]))

### FIXED CODE ###

import sys

lines = sys.stdin.readlines()

H, M = list(map(int, lines[0].split()))
AB = []

max_at = 0
min_mg = sys.maxsize
at_min_mg = 0
for i in range(M):
  t = tuple(map(int, lines[i+1].split()))
  AB.append(t)
  if t[0]>=max_at:
    max_at = t[0]
  if t[1]<=min_mg:
    min_mg = t[1]
    at_min_mg = t[0]

ABlen = len(AB)

DP = [0]
for i in range(1, at_min_mg+1):
  DP.append(min_mg)
  
for i in range(at_min_mg+1,H+max_at+1):
  mm = sys.maxsize
  for j in range(ABlen):
    if i-AB[j][0]<0:
      continue
    if mm > DP[i-AB[j][0]]+AB[j][1]:
      mm = DP[i-AB[j][0]]+AB[j][1]
  DP.append(mm)
print(min(DP[H:H+max_at]))
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(S: str):
    N = len(S)
    s1 = S[:(N-1)//2]
    s1r = s1[::-1]
    s2 = S[(N+3)//2]
    s2r = s2[::-1]
    if S == S[::-1] and s1 == s1r and s2 == s2r:
        print(YES)
    else:
        print(NO)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(S: str):
    N = len(S)

    if N == 3:
        if S == S[::-1]:
            print(YES)
            exit()
        else:
            print(NO)
            exit()

    s1 = S[:(N-1)//2]
    s1r = s1[::-1]
    s2 = S[(N+3)//2]
    s2r = s2[::-1]
    # print(s1, s1r, s2, s2r)
    if S == S[::-1] and s1 == s1r and s2 == s2r:
        print(YES)
    else:
        print(NO)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()
ef S(): return input().rstrip()

def main():
    s = S()

    if 'A' in s and 'B' in s:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()


### FIXED CODE ###

def S(): return input().rstrip()

def main():
    s = S()

    if 'A' in s and 'B' in s:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()
n = int(input())
v = list(map(int , input().split()))

n = len(v)
from collections import defaultdict
c0 = defaultdict(int)
for vi in v[0::2]:
    c0[vi] += 1
c1 = defaultdict(int)
for vi in v[1::2]:
    c1[vi] += 1

sc0 = sorted(c0.items(), key=lambda x: x[1])
sc1 = sorted(c1.items(), key=lambda x: x[1])

print(sc0)
print('-----------')
print(sc1)
if sc0[-1][0] != sc1[-1][0]:
    #print('--1')
    print(n//2 - sc0[-1][1] + n//2 - sc1[-1][1])
    exit()
if len(sc0) == 1 and len(sc1) == 1:
    #print('--2')
    print(n//2)
    exit()
if sc0[-1][1] == sc1[-1][1]:
    if sc0[-2][1] > sc1[-2][1]:
        print(n//2 - sc0[-1][1] + n//2 - sc1[-2][1])
    else:
        print(n//2 - sc0[-2][1] + n//2 - sc1[-1][1])
    exit()
if sc0[-1][1] > sc1[-1][1]:
    #print('--3')
    print(n//2 - sc0[-1][1] + n//2 - sc1[-2][1])
    exit()
else:
    #print('--4')
    print(n//2 - sc0[-2][1] + n//2 - sc1[-1][1])
    exit()
 (2054, 12394), (27775, 12395)
(50652, 12393), (27775, 12395)


### FIXED CODE ###

n = int(input())
v = list(map(int , input().split()))

n = len(v)
from collections import defaultdict
c0 = defaultdict(int)
for vi in v[0::2]:
    c0[vi] += 1
c1 = defaultdict(int)
for vi in v[1::2]:
    c1[vi] += 1

sc0 = sorted(c0.items(), key=lambda x: x[1])
sc1 = sorted(c1.items(), key=lambda x: x[1])
#print(n)
#print(sc0)
#print('------------------')
#print(sc1)
if sc0[-1][0] != sc1[-1][0]:
    #print('--1')
    print(n//2 - sc0[-1][1] + n//2 - sc1[-1][1])
    exit()
if len(sc0) == 1 and len(sc1) == 1:
    #print('--2')
    print(n//2)
    exit()
if sc0[-1][1] > sc1[-1][1]:
    #print('--3')
    print(n//2 - sc0[-1][1] + n//2 - sc1[-2][1])
    exit()
if sc0[-1][1] < sc1[-1][1]:
    #print('--4')
    print(n//2 - sc0[-2][1] + n//2 - sc1[-1][1])
    exit()
if sc0[-1][1] == sc1[-1][1]:
    if sc0[-2][1] < sc1[-2][1]:
        #print('--1',sc0[-1][1],sc1[-1][1], sc0[-2][1],sc1[-2][1])
        print(n//2 - sc0[-1][1] + n//2 - sc1[-2][1])
    else:
        #print('--1',sc0[-1][1],sc1[-1][1], sc0[-2][1],sc1[-2][1])
        print(n//2 - sc0[-2][1] + n//2 - sc1[-1][1])
    exit()

#(92753, 12393), (2054, 12394), (27775, 12395)
#(55530, 10),    (50652, 12393),   (27775, 12395)
n = int(input())
a = [input() for i in range(n+1)]
m = int(input())
b = [input() for i in range(m+1)]
min = 0
for i in range(n+1):
    max = a.count(a[i])-b.count(a[i])
    if max >= min:
        min = max
    else:
        pass
print(max)
        

### FIXED CODE ###

n = int(input())
a = [input() for i in range(n)]
m = int(input())
b = [input() for i in range(m)]
min = 0
for i in range(n):
    max = a.count(a[i])-b.count(a[i])
    if max >= min:
        min = max
    else:
        pass
print(min)
print(fAIR, LATER, OCCASIONALLY CLOUDY.swapcase())

### FIXED CODE ###

s = input()
print(s.swapcase())
N = int(input())
Tlist = [int(N) for N in input().split()]
M = int(input())
PXlist = [[int(i) for i in input().split()]for j in range(M)]
def time_sum():
    s = 0
    for i in range(0,N):
        s = s+Tlist[i]
    return s
def time_cal():
    empty = []
    for i in range(0,M):
        empty.append(time_sum() - Tlist[PXlist[i][0]-1] + PXlist[i][1])
    return empty
print(time_sum)
for i in time_cal():
    print(i)

### FIXED CODE ###

A, op, B = input().split()
if op is '+':
  print(int(A)+int(B))
if op is '-':
  print(int(A)-int(B))
n,a,b=map(int,input().split
mod = 10**9+7
MAX_N = 10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod



x=mod_comb_k(n,a,mod)+mod_comb_k(n,b,mod)
y=((pow(2,n)-1)%(10**9+7))
ans=(y-x%(10**9+7))
while ans<0:
          ans+=10**9+7
print(ans)



### FIXED CODE ###

n,a,b=map(int,input().split())
def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

x=pow(2,n,10**9+7)-1
y=comb(n,a)+comb(n,b)
ans=x-y





while ans<0:
          ans+=10**9+7
print(ans)
import sys
input = sys.stdin.readline

N = int(input())
P = list(map(int, input().split()))
cnt = 0
for i, p in enumerate(P):
    num = i + 1
    if num != p:
        continue
    else:
        next = P[i+1]
        tmp = P[i]
        P[i] = P[i+1]
        P[i+1] = tmp
        cnt += 1
print(cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
P = list(map(int, input().split()))
cnt = 0
for i, p in enumerate(P):
    num = i + 1
    if num != p:
        continue
    else:
        if(i+1 < N):
            next = P[i+1]
            tmp = P[i]
            P[i] = P[i+1]
            P[i+1] = tmp
            cnt += 1
        else:
            cnt += 1
print(cnt)
N = input()
 
a = 0
for i in range(3):
  if N[i] == '7':
    a = 1
    
if a = 1:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N = input()

a = 0
for i in range(3):
  if N[i] == '7':
    a = 1
    
if a == 1:
  print('Yes')
else:
  print('No')
N, Y = map(int, input().split())
for i1 in range(N)
	for i2 in range(N)
  		for i3 in range(N)
    		if Y==10000*i1+5000*i2+1000*i3:
        		print(i1,i2,i3)
          		break
            else:
              
      
      	

### FIXED CODE ###

N, Y = map(int, input().split())
 
for x in range(N+1):
  for y in range(N-x+1):
    z = N - x - y
    if 10000 * x + 5000 * y + 1000 * z == Y:
      print(x,y,z)
      exit()
print(-1,-1,-1)
n = int(input())
res = n % 26

A = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s',
     't','u','v','w','x','y','z']

ans = []
while n//26 > 0 :
  res = n % 26
  if res % 26 != 0:
    ans.append(A[res-1])
  elif res % 26 == 0:
    ans .append(A[25])
  n = n // 26

if res != 0:
  ans.append(A[res-1])
elif res == 0:
  ans.append(A[25])
print(*ans[::-1], sep='')

### FIXED CODE ###

a = input()

if a.islower() == True:
  print('a')
else:
  print('A')