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

N = int(input())
count = 0

for i in range(357, N+1):
 
    thr = str(i).count("3")
    fiv = str(i).count("5")
    sev = str(i).count("7")


    if thr > 0 and fiv > 0 and sev > 0 and len(str(i)) == thr + fiv + sev:
        count += 1

print(count)

### FIXED CODE ###

from itertools import product

N = int(input())
num_list = ["3", "5", "7"]
count = 0

for i in range(3, 10):
    for t in (product(num_list, repeat=i)):
        check = t.count("3")*t.count("5")*t.count("7")
        if int("".join(t)) <= N and check:
            count += 1


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

n = int(input())
s = input()

m = n

for i in range(n):
    west = s[:i]
    east = s[i+1:]

    turn = west.count('W') + east.count('E')

    m = min(turn, m)

print(m)

### FIXED CODE ###

n = int(input())
s = input()

m = n
turn = s[1:].count('E')
m = min(turn, m)
for i in range(1, n):
    if s[i-1] == 'W': turn += 1
    if s[i] == 'E': turn -= 1

    m = min(turn, m)

print(m)
### BUGGY CODE ###

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

sum=0

for m in range(M):
    A[A.index(max(A))]//=2
for a in A:
    sum+=a
print(sum)

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(int,input().split()))

sum=0
A=[-1 * i for i in A]
heapq.heapify(A)

for m in range(M):
    rep=-(-heapq.heappop(A)//2)
    heapq.heappush(A,rep)
for a in A:
    sum-=a

print(sum)
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(1, n+1):
    for j in range(i, n+1, i):
        ans+=j
print(ans)

### FIXED CODE ###

from numba import jit
@jit
def Sum_divisors():
    n,ans=int(input()),0
    for i in range(1, n+1):
        for j in range(i, n+1, i):ans+=j
    print(ans)

Sum_divisors()
### BUGGY CODE ###

N = int(input())
list_a = [int(x) for x in input().split()]

ans = 0
ansX1 = 0
ansX2 = 0

for X in range(min(list_a),max(list_a)+1) :
    ansX0 = list_a.count(X)
    ansX = ansX0 + ansX1 + ansX2
    ans = max(ans,ansX)
    ansX2 = ansX1
    ansX1 = ansX0

print(ans)


### FIXED CODE ###

N = int(input())
list_a = [int(x) for x in input().split()]

list_X = []

for X in list_a :
    list_X.append(X)
    list_X.append(X+1)
    list_X.append(X-1)

from collections import Counter
print(max(Counter(list_X).values()))
### BUGGY CODE ###

n=int(input())
alis=list(map(int,input().split()))
xlis=set()
for i in alis:
    xlis.add(i-1)
    xlis.add(i+1)
    xlis.add(i)
#print(xlis)
counter=[0 for _ in range(len(xlis))]
t=-1
for x in xlis:
    t+=1
    for i in range(n):
        if x-1<=alis[i] and alis[i]<=x+1:
            counter[t]+=1
print(max(counter))

### FIXED CODE ###

n=int(input())
alis=list(map(int,input().split()))
xlis=dict()
for i in set(alis):
    xlis[i-1]=0
    xlis[i+1]=0
    xlis[i]=0
for i in alis:
    xlis[i-1]+=1
    xlis[i+1]+=1
    xlis[i]+=1
print(max(xlis.values()))
### BUGGY CODE ###

import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
if len(c) <= k:
    print(0)
else:
    sum = 0
    for i in range(k, len(c)):
        sum += c.most_common()[i][1]
    print(sum)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
d = c.most_common()
if len(c) <= k:
    print(0)
else:
    sum = 0
    for i in range(k, len(c)):
        sum += d[i][1]
    print(sum)
### BUGGY CODE ###


import math
N=int(input())
S=[]
def eratos(n,l,r):
    count=0
    isprime=[True]*(n+1)
    isprime[0]=False
    isprime[1]=False
    for i in range(2,int(math.sqrt(n))+1):
        if isprime[i]==True:
            j=i+i
            while j<=n:
                isprime[j] =False
                j=j+i

    for i in range(l,r+1):
        if isprime[i]==True:
            if isprime[(i+1)//2]==True:
                count+=1
    
    return count
    
for k in range(N):
    l,r=map(int,input().split())

    print(eratos(110000,l,r))

### FIXED CODE ###


import math
N=int(input())
S=[0]*100010
n=110000
count=0
isprime=[True]*(n+1)
isprime[0]=False
isprime[1]=False
for i in range(2,int(math.sqrt(n))+1):
    if isprime[i]==True:
        j=i+i
        while j<=n:
            isprime[j] =False
            j=j+i

for i in range(2,100010):
    if isprime[i]==True:
        if isprime[(i+1)//2]==True:
            count+=1
    
    S[i]=count
        
                
    

    
for k in range(N):
    l,r=map(int,input().split())
    
    print(S[r]-S[l-1])
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp=[0for i in range(N)]
dp[0]= 0
if N<=K:
    dp[N-1]=abs(h[0]-h[N-1])
else:   
    for j in range(1,K+1):
        dp[j]= abs(h[0]-h[j])
    
    for i in range(K,N):
        list1 =[]
        for k in range(1,K+1):
            cost = dp[i-k]+abs(h[i-k]-h[i])
            list1.append(cost)
        dp[i]= min(list1)
            
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp=np.array([0 for i in range(N)])
dp[0]= 0
dp[1]=abs(h[1]-h[0])
if N<=K:
    dp[N-1]=abs(h[0]-h[N-1])
else:  
    for i in range(2,N):
      j=max(0,i-K)
      dp[i]=np.min(dp[j:i]+np.abs(h[i]-h[j:i]))
      #dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(k+1,i+1))])
print(int(dp[-1]))
### BUGGY CODE ###

s = input()
roop = int(input())
is_head = True
for i in range(roop):
    q_li = input().split()
    t = int(q_li[0])
    if t == 1:
        is_head = not is_head
    else:
        f = int(q_li[1])
        c = q_li[2]
        if f == 1:
            # 先頭に追加
            s = c + s if is_head else s + c
        else:
            # 末尾に追加
            s = s + c if is_head else c + s

print(s) if is_head else print(s[::-1])


### FIXED CODE ###

# TLE
s = input()
loop = int(input())
is_head = True
to_head = []
to_tail = []
for i in range(loop):
    q_li = input().split()
    t = int(q_li[0])
    if t == 1:
        is_head = not is_head
    else:
        f = int(q_li[1])
        c = q_li[2]
        if f == 1:
            # 先頭に追加
            to_head.append(c) if is_head else to_tail.append(c)
        else:
            # 末尾に追加
            to_tail.append(c) if is_head else to_head.append(c)

if is_head:
    print("".join(to_head[::-1]) + s + "".join(to_tail))
else:
    print("".join(to_tail[::-1]) + s[::-1] + "".join(to_head))
### BUGGY CODE ###

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

N, K = [int(x) for x in input().strip().split()]
highest = 0
lowest = 10 ** 9
high = [0] * N
low = [0] * N
q = deque([])
ans = 10 ** 9
pre = -1
H = sorted([int(input()) for _ in range(N)])
for n, ne in enumerate(H):
    q.append(ne)
    if len(q) > K:
        pre = q.popleft()
    if ne > highest:
        highest = ne
    if ne < lowest:
        lowest = ne
    if pre == highest:
        highest = max(q)
    if pre == lowest:
        lowest = min(q)
    if n >= K - 1:
        ans = min(ans, highest - lowest)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().strip().split()]
H = sorted([int(input()) for _ in range(N)])
ans = 10 ** 9
for n in range(N - (K - 1)):
    ans = min(ans, H[n+K-1] - H[n])

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

import sys
input = sys.stdin.readline


def calc(N, adj, ignore, dp, prevs):
    s, t = ignore
    for i in range(prevs+1):
        dp[i] = 0.0
    for i in range(prevs, -1, -1):
        n = len(adj[i])
        if i == s:
            n -= 1
            if n == 0:
                return float("Inf")
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    x = [(-1, -1)] + [None] * M
    for i in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
        x[i+1] = (s-1, t-1)
    x.sort(reverse=True)
    ans = float("Inf")
    dp = [0.0] * (N)
    prevs = N - 1
    for ignore in x:
        tmp = calc(N, adj, ignore, dp, prevs)
        ans = min(ans, tmp)
        prevs = ignore[0]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def calc(N, adj, dp, ignore):
    s, t = ignore
    for i in range(N-1, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        if i == s:
            n -= 1
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
    dp1 = [0.0] * N
    ans = calc(N, adj, dp1, (-1, -1))
    dp2 = [0.0] * N
    for i in range(N-1, -1, -1):
        if len(adj[i]) <= 1:
            continue
        j = i
        mx = -1
        for nxt in adj[i]:
            if dp1[nxt] > mx:
                j = nxt
                mx = dp1[nxt]
        tmp = calc(N, adj, dp2, (i, j))
        ans = min(ans, tmp)
    print(ans)


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

n = int(input())
k = [int(a) for a in input().split()]
k_set = set(k)
all = 0
count_dic = {}

for b in k_set:
    tmp = k.count(b)
    all += tmp * (tmp - 1) // 2
    count_dic[b] = tmp

for c in k:
    tmp = count_dic[c]
    print(all - (tmp - 1))

### FIXED CODE ###

import collections

n = int(input())
k = [int(a) for a in input().split()]
k_set = set(k)
all = 0
count_dic = collections.Counter(k)

for b in k_set:
    tmp = count_dic[b]
    all += tmp * (tmp - 1) // 2

for c in k:
    tmp = count_dic[c]
    print(all - (tmp - 1))
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
counter=0
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
else:
    list_a=[0]*P
    list_a[0]+=1
    for i in range(N):
        temp=int(S[N-i-1:])%P
        counter+=list_a[temp]
        list_a[temp]+=1
print(counter)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()

counter=0
def power_func(a,b,p):
    if b==0:
        return 1
    elif b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    elif b%2==1:
        return (a*power_func(a,b-1,p ))%p
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
else:
    list_a=[0]*P
    list_a[0]+=1
    temp=0
    for i in range(N):
        M = power_func(10,N-i,P)
        temp=(int(S[i])*M+temp)%P
        counter+=list_a[temp]
        list_a[temp]+=1
print(counter)
### BUGGY CODE ###

#C - Poll
import collections
N = int(input())
S = [str(input()) for i in range(N)]
#print(S)

A = collections.Counter(S)
maxS = [kv[0] for kv in A.items() if kv[1] == max(A.values())]
maxS = sorted(maxS)
for l in range(len(maxS)):
    print(maxS[l])

### FIXED CODE ###

#C - Poll
N = int(input())
S = [str(input()) for i in range(N)]
S = sorted(S)
count = 1
tmpcount = 1
DP = [S[0]]
for i in range(1,N):
    if S[i] == S[i-1]:
        count += 1
        if tmpcount < count:
            DP.clear()
            DP.append(S[i])
            tmpcount = count
        elif tmpcount == count:
            DP.append(S[i])
        else:
            pass
    else:
        count = 1
        if tmpcount == count:
            DP.append(S[i])
        else:
            pass

for l in range(len(DP)):
     print(DP[l])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
minians = []
for i in range(N-1):
    if S[i:i + 2] == "AC":
        minians.append(i)
# print(minians)
ans = [0]*Q
for i in range(Q):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    for j in range(len(minians)):
        if left <= minians[j] and minians[j] < right:
            ans[i] += 1
        elif minians[j] >= right:
            break
print('\n'.join(map(str, ans)))


### FIXED CODE ###

import bisect
N, Q = map(int, input().split())
S = input()
minians = []
for i in range(N-1):
    if S[i:i + 2] == "AC":
        minians.append(i)
# print(minians)
ans = [0]*Q
for i in range(Q):
    left, right = map(int, input().split())
    left -= 1
    right -= 1
    """print("\n", bisect.bisect_left(minians, right),
          bisect.bisect_left(minians, left))"""
    ans[i] = bisect.bisect_left(minians, right) - \
        bisect.bisect_left(minians, left)

    #ans[i] = sum(left <= mini < right for mini in minians)
    """for j in range(len(minians)):
        if left <= minians[j] and minians[j] < right:
            ans[i] += 1
        elif minians[j] >= right:
            break"""
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

# https://img.atcoder.jp/abc123/editorial.pdf
# 問題D: Cake 123 解法 #3 - さらに高速な解法、priority-queue を用いて O(K log K)

from heapq import heappush, nlargest

def solve(X, Y, Z, K, A, B, C):
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    Q = []
    for a in A:
        for b in B:
            heappush(Q, a+ b)
    AB = nlargest(K, Q)

    Q2 = []
    for ab in AB:
        for c in C:
            heappush(Q2, ab + c)
    ABC = nlargest(K, Q2)
    print("\n".join(map(str, ABC)))

if __name__ == "__main__":
    X, Y, Z, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    solve(X, Y, Z, K, A, B, C)

### FIXED CODE ###

from collections import defaultdict

def append(m, printed, cand_a, cand_b, cand_c):
    key = "{}-{}-{}".format(cand_a, cand_b, cand_c)
    key2 = "{}-{}-{}".format(cand_a-1, cand_b, cand_c)
    key3 = "{}-{}-{}".format(cand_a, cand_b-1, cand_c)
    key4 = "{}-{}-{}".format(cand_a, cand_b, cand_c-1)
    if not key in printed \
            and cand_a < len(A) \
            and cand_b < len(B) \
            and cand_c < len(C) \
            and not key in m \
            and not key2 in m \
            and not key3 in m \
            and not key4 in m :
#       print("Appended {}".format(key))
        m[key] = A[cand_a] + B[cand_b] + C[cand_c]
    return m

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

a = 0
b = 0
c = 0

n_print = 0
#print(A, B, C)
memo = {}
printed = defaultdict(lambda: False)
while True:
    summ = A[a] + B[b] + C[c]
    printed["{}-{}-{}".format(a, b, c)] = True

    print(summ)

#   print(memo.items())
#   print(a, b, c)
#   print("")

    n_print += 1
    if n_print == K:
        break

    memo = append(memo, printed, a+1, b, c)
    memo = append(memo, printed, a, b+1, c)
    memo = append(memo, printed, a, b, c+1)

    max_k = max(memo, key=memo.get)
    a, b, c = max_k.split("-")
    a = int(a)
    b = int(b)
    c = int(c)
        
    memo.pop(max_k)
#   print("Pop {}".format(max_k))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

input_line = list(map(int,input().split()))
input_hp = list(map(int,input().split()))

if input_line[0] <= input_line[1]:
    print('0')
else:
    [(input_hp.sort(reverse=True) ,input_hp.pop(_)) for _ in range(input_line[1])]
    print(sum(input_hp))

### FIXED CODE ###

input_line = list(map(int,input().split()))
input_hp = list(map(int,input().split()))

if input_line[0] <= input_line[1]:
    print('0')
else:
    input_hp.sort()
    result_input_hp = len(input_hp) - input_line[1]
    sum_total = sum(input_hp[:result_input_hp])
    print(sum_total)
### BUGGY CODE ###

N, P = map(int,input().split())
 
output=1
 
if P==1:
  outtput=1
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)

### FIXED CODE ###

N, P = map(int,input().split())
 
output=1
 
if P==1:
  output=1
elif N==1:
  output=P
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)
### BUGGY CODE ###

import itertools

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

cnt = 0
for a, b, c in list(itertools.combinations(L,3)):
    if a<b+c and b<a+c and c<a+b:
        cnt += 1

print(cnt)

### FIXED CODE ###

from bisect import bisect_left

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

L.sort()

cnt = 0

# 2番目に長い棒bを固定
for b in range(N):
    # bより短い棒aを一つずつ探索
    for a in range(b):
        ab = L[a] + L[b]
        # 二分探索でa+bより短い棒（c<a+bが成り立つc）の範囲を求める
        r = bisect_left(L, ab)
        # cの範囲のうちbの範囲を除外して、cの本数を求める
        cnt += r - (b + 1)

print(cnt)
### BUGGY CODE ###

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

count = 0

for i in range(a, b+1):
    if i%c != 0 and i%d != 0:
        count +=1

print(count)

### FIXED CODE ###

a, b, c,d = map(int, input().split())
import math
min = int(c*d/math.gcd(c,d))
x = b-b//c - b//d + b//min
y = a-1-(a-1)//c - (a-1)//d + (a-1)//min

print(int(x-y))
### BUGGY CODE ###

from sys import stdin

n,q=map(int,input().split())
s=input()
l = [stdin.readline().rstrip().split() for _ in range(q)]

t=[0]*(n)
for i in range(n):
    t[i]=(1 if s[i:i+2]=="AC" else 0)

for j,k in l:
    ans=0
    for x in range(int(j)-1,int(k)-1):
        ans+=t[x]
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

from collections import Counter

class Bit:
    def __init__(self, n,ls):
        self.size=n
        self.tree=[Counter() for _ in range(n+1)]
        self.ls=['']*(n+1)

    def sum(self, i, j):
        i-=1
        res1=Counter()
        res2=Counter()
        while i>0:
            res1 += self.tree[i]
            i -= i&-i
        while j>0:
            res2 += self.tree[j]
            j -= j&-j
        return len(res2-res1)
    
    def add(self, i, x):
        self.ls[i] = x
        while i <= self.size:
            self.tree[i][x]+=1
            i += i & -i

    def change(self, i, x):
        original = self.ls[i]
        self.ls[i]=x
        while i <= self.size:
            self.tree[i][original] -=1
            self.tree[i][x] +=1
            i += i & -i
        

n = int(input())
s = list(input())
bit=Bit(n,s)

for i in range(n):
    bit.add(i+1, s[i])

q = int(input())
for _ in range(q):
    query, a, b = input().split()
    if query=='1':
        bit.change(int(a),b)
    else:
        ans=bit.sum(int(a), int(b))
        print(ans)


### FIXED CODE ###

from collections import Counter
def snum(x):
    return ord(x)-ord('a')

class Bit:
    def __init__(self, n,ls):
        self.size=n
        self.tree=[[0]*26 for _ in range(n+1)]
        self.ls=['']*(n+1)

    def sum(self, i, j):
        i-=1
        res=[0]*26
        for k in range(26):
            i2=i
            j2=j
            while j2>0:
                res[k] += self.tree[j2][k]
                j2 -= j2&-j2
            while i2>0:
                res[k] -= self.tree[i2][k]
                i2 -= i2&-i2
        return 26-res.count(0)
    
    def add(self, i, x):
        self.ls[i] = x
        while i <= self.size:
            self.tree[i][snum(x)]+=1
            i += i & -i

    def change(self, i, x):
        original = self.ls[i]
        self.ls[i]=x
        while i <= self.size:
            self.tree[i][snum(original)] -= 1
            self.tree[i][snum(x)] += 1
            i += i & -i
        

n = int(input())
s = list(input())
bit=Bit(n,s)

for i in range(n):
    bit.add(i+1, s[i])

q = int(input())
for _ in range(q):
    query, a, b = input().split()
    if query=='1':
        bit.change(int(a),b)
    else:
        print(bit.sum(int(a), int(b)))
### BUGGY CODE ###

q = int(input())
for i in range(q):
    X = input()
    Y = input()

    m, n = len(X), len(Y)
    c = [[0 for i in range(n+1)] for j in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            x, y = X[i-1], Y[j-1]
            if x == y:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])

    print(c[m][n])


### FIXED CODE ###

def lcs(X, Y):
    global c
    m, n = len(X), len(Y)
    c = [[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
    return c[m][n]

def lcs_improved(X, Y):
    hist = [0] # yの文字cまでを見た時に, hist[i]以降の文字列において, 共通文字のうち, 一番小さいindexのもの
    for c in Y:
        for i in range(len(hist)-1, -1, -1):
            next_match_i = X.find(c, hist[i])+1
            if next_match_i:
                if i+1 < len(hist):
                    hist[i+1] = min(hist[i+1], next_match_i)
                else:
                    hist.append(next_match_i)
    return len(hist)-1

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs_improved(X, Y))
### BUGGY CODE ###

MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
if M>N//2+2:
  print(0)
  exit()
x = 0
y = 1
for i in range(N):
  if i+1 in a:
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)


### FIXED CODE ###

import bisect
def f(x,a):
  global M
  b = bisect.bisect_left(a,x)
  if x==a[min(b,M)]:
    return True
  else:
    return False
MOD = 10**9+7
N,M = map(int,input().split())
a = [-1]+[int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)
### BUGGY CODE ###

import math

N = int(input())
S = [0] * N
for i in range(N):
    S[i] = sorted(str(input()))

Sum = 0
hoge = 1

S.sort()

for i in range(N-1):
    if S[i] == S[i+1]:
        hoge += 1
    if (S[i] != S[i+1] or i == N-2) and hoge != 1:
        Sum += math.factorial(hoge) // (math.factorial(hoge - 2) * math.factorial(2))
        hoge = 1

print(Sum)

### FIXED CODE ###

import math

N = int(input())
S = [0] * N
for i in range(N):
    S[i] = sorted(str(input()))

Sum = 0
hoge = 1

S.sort()

for i in range(N-1):
    if S[i] == S[i+1]:
        hoge += 1
    if (S[i] != S[i+1] or i == N-2) and hoge != 1:
        #Sum += math.factorial(hoge) // (math.factorial(hoge - 2) * math.factorial(2))
        Sum += hoge*(hoge-1)//2
        hoge = 1

print(Sum)