CodeEff/ECCO huggingface dataset:
# Original solution
N, M = list(map(int, input().split()))
A_ = [int(eval(input())) for _ in range(M)]
A = [0] * (N+3)
for a in A_:
    A[a] = 1
dp = [0] * (N+3)
dp[0] = 1

mod = 10**9+7

for i in range(1, N+1):
    if A[i-1] == 0:
        dp[i] += dp[i-1]
    if A[i-2] == 0:
        dp[i] += dp[i-2]
    dp[i] %= mod
print((dp[N]))

# Optimized solution
n,m=list(map(int,input().split()))
dp=[0]*(n+3)
a=[int(eval(input())) for i in range(m)]
mod=10**9+7
for i in range(m):
    dp[a[i]]=-1

dp[0]=1
if dp[1]!=-1:
    dp[1]+=dp[0]

for i in range(n+1):
    if dp[i+2]==-1:
        continue
    if dp[i]!=-1:
        dp[i+2]+=dp[i]
    if dp[i+1]!=-1:
        dp[i+2]+=dp[i+1]
    dp[i+2]%=mod
print((dp[n]%mod))
# Original solution
n,m=list(map(int,input().split()))
dp=[0]*(n+3)
a=[int(eval(input())) for i in range(m)]
mod=10**9+7
for i in range(m):
    dp[a[i]]=-1

dp[0]=1
if dp[1]!=-1:
    dp[1]+=dp[0]

for i in range(n+1):
    if dp[i+2]==-1:
        continue
    if dp[i]!=-1:
        dp[i+2]+=dp[i]
    if dp[i+1]!=-1:
        dp[i+2]+=dp[i+1]
    dp[i+2]%=mod
print((dp[n]%mod))

# Optimized solution
n,m = list(map(int,input().split()))
a = []
stairs = [0]*(n+2)
for _ in range(m):
    a = int(eval(input()))
    stairs[a] = 1
mod = 10**9 + 7

dp = [0]*(n+2)
dp[0] = 1

for i in range(n):
    if i <= 1:
        if stairs[i+1] == 0:
            dp[i+1] += dp[i]
            dp[i+1] %= mod
            stairs[i+1] = 1
    if stairs[i+2] == 0:
        dp[i+2] += dp[i+1]+dp[i]
        dp[i+2] %= mod
        stairs[i+2] = 1

print((dp[n]%mod))
# Original solution
# DP
N, M = list(map(int, input().split()))
broken = [int(eval(input())) for _ in range(M)]

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

for i in reversed(list(range(N))):
    if i in broken:
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % MOD

print((dp[0]))


# Optimized solution
# DP
N, M = list(map(int, input().split()))
broken = set([int(eval(input())) for _ in range(M)])

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

for i in reversed(list(range(N))):
    if i in broken:
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % MOD

print((dp[0]))
# Original solution
# DP
N, M = list(map(int, input().split()))
broken = set([int(eval(input())) for _ in range(M)])

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

for i in reversed(list(range(N))):
    if i in broken:
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % MOD

print((dp[0]))


# Optimized solution
# DP
N, M = list(map(int, input().split()))
broken = set([int(eval(input())) for _ in range(M)])

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

for i in reversed(list(range(N))):
    if i in broken:
        continue
    dp[i] = dp[i+1] + dp[i+2]
    dp[i] %= MOD

print((dp[0]))
# Original solution
n,m=list(map(int,input().split()))
al=[int(eval(input())) for i in range(m)]
mod=1000000007
ansl=[0,1]
for i in range(1,n+1):
    if i in al:
        ansl.append(0)
    else:
        ansl.append((ansl[-2]+ansl[-1])%mod)
print((ansl[-1]%mod))

# Optimized solution
n,m=list(map(int,input().split()))
al=set([int(eval(input())) for i in range(m)])
mod=1000000007
ansl=[0,1]
for i in range(1,n+1):
    if i in al:
        ansl.append(0)
    else:
        ansl.append((ansl[-2]+ansl[-1])%mod)
print((ansl[-1]%mod))
# Original solution
MOD = 10**9 + 7

import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = []
for _ in range(m):
    a.append(int(eval(input())))

# i段目にたどり着く方法
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

for i in range(2, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if i not in a else 0

print((dp[-1]))

# Optimized solution
MOD = 10**9 + 7

import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = [0] * (n + 1)
for _ in range(m):
    a[int(eval(input()))] = 1

# i段目にたどり着く方法
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if a[1] == 0 else 0

for i in range(2, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if a[i] == 0 else 0

print((dp[-1]))
# Original solution
n, m = list(map(int, input().split()))
a = [int(eval(input())) for _ in range(m)]
dan = [0]*(n+1)
dan[0] = 1

for i in range(1,n+1):
    if i not in a:
        dan[i] += dan[i-1]
        if i >= 2:
            dan[i] += dan[i-2]

print((dan[n]%(10**9+7)))

# Optimized solution
n, m = list(map(int, input().split()))
li = [True]*(n+1)

for i in range(m):
    a = int(eval(input()))
    li[a] = False

dan = [0]*(n+1)
dan[0] = 1

for j in range(1,n+1):
    if li[j]:
        dan[j] += dan[j-1]
        if j >= 2:
            dan[j] += dan[j-2]

print((dan[n]%(10**9+7)))
# Original solution
n, m = list(map(int, input().split()))
a = [int(eval(input())) for _ in range(m)]

mod = 10**9 + 7
def nCr(n, r):
    r = min(r, n-r)
    num, den = 1, 1
    for i in range(r):
        num *= (n-i)
        den *= (i+1)
    return num // den % mod

lv = 0
a.append(n+1)
ans = 1
for v in a:
    vr = v-1 - lv
    if vr < 0:
        print((0))
        exit()
    r = 0
    for i in range(vr+(-vr//2)+1):
        r += nCr(vr-i, i)
    ans = (ans * r) % mod
    lv = v+1
print(ans)

# Optimized solution
n, m = list(map(int, input().split()))
a = [int(eval(input())) for _ in range(m)]

mod = 10**9+7
a.append(float('INF'))
a = a[::-1]
dp = [0] * (n+1)
dp[0] = 1
if a[-1] != 1:
    dp[1] = 1
else:
    a.pop()
for i in range(2, n+1):
    if i == a[-1]:
        a.pop()
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod
print((dp[n]))
# Original solution
import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = list(map(int, input().split()))
A = [int(eval(input())) for i in range(M)]

current_step, prev_step, two_prev_step = 0, 1, 0
for i in sorted(list(range(N)), reverse=True):
    if i in A:
        prev_step, two_prev_step = 0, prev_step
        continue

    current_step = prev_step + two_prev_step
    prev_step, two_prev_step = current_step, prev_step

print((current_step % max_num))

# Optimized solution
import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = list(map(int, input().split()))
A = [int(eval(input())) for i in range(M)]

stairs = [1] * (N+1)
for i in A:
    stairs[i] = 0

for i in range(1, N):
    if stairs[i+1] != 0:
        stairs[i+1] = stairs[i] + stairs[i-1]
print((stairs[N] % max_num))
# Original solution
n,m=list(map(int,input().split()))
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(eval(input())))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print((ans[n]))

# Optimized solution
n,m=list(map(int,input().split()))
a=set([int(eval(input())) for _ in range(m)])
dp=[1]+[0 for _ in range(n)]
mod=1000000007
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
print((dp[-1]))
# Original solution
import sys
N, M = list(map(int, input().split()))
A = [int(eval(input())) for _ in range(M)]
mod = 10 ** 9 + 7

if N == 1:
    print((1))
    sys.exit()

B = ['.'] * (N + 1) 
for a in A:
    B[a] = '#'
    
dp = [0] * (N + 1)
if B[1] == '.' and B[2] == '.':
    dp[1] = 1
    dp[2] = 2
elif B[1] == '#' and B[2] == '.':
    dp[2] = 1
elif B[1] == '.' and B[2] == '#':
    dp[1] = 1
    
for i in range(3, N + 1):
    if B[i] == '.':
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    
print((dp[N]))

# Optimized solution
import sys
n, m = list(map(int, input().split()))
A = [int(eval(input())) for _ in range(m)]
mod = 1000000007

if n == 1:
    print((1))
    sys.exit()

B = ['.'] * (n + 1)
for a in A:
    B[a] = '#'
    
dp = [0] * (n + 1)
if B[1] == '.' and B[2] == '.':
    dp[1] = 1
    dp[2] = 2
elif B[1] == '#' and B[2] == '.':
    dp[2] = 1
elif B[1] == '.' and B[2] == '#':
    dp[1] = 1
    
for i in range(3, n + 1):
    if B[i] == '.':
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    
print((dp[-1]))
# Original solution
# -*- coding: utf-8 -*-
def main():
    N,M = list(map(int,input().split()))
    A = [int(eval(input())) for _ in range(M)]
    MOD = 1000000007
    ans = [1]
    ans.append(0) if 1 in A else ans.append(1)
    for i in range(2,N+1):
        ans.append(0)
        if i in A:
            continue
        ans[i] += (ans[i-1] + ans[i-2])
    print((ans[N] % MOD))
if __name__ == '__main__':
    main()

# Optimized solution
# -*- coding: utf-8 -*-
def main():
    N,M = list(map(int,input().split()))
    A = set([int(eval(input())) for _ in range(M)])
    MOD = 1000000007
    ans = [1]
    ans.append(0) if 1 in A else ans.append(1)
    for i in range(2,N+1):
        ans.append(0)
        if i in A:
            continue
        ans[i] += (ans[i-1] + ans[i-2])
    print((ans[N] % MOD))
if __name__ == '__main__':
    main()
# Original solution
n, m = [int(i) for i in input().split()]
a = [-1] + [int(eval(input())) for _ in range(m)] + [n+1]

fib_l = [-1] * (n+3)

def make_fib(n):
    fib_l[0] = fib_l[1] = 1
    for i in range(2, n):
        fib_l[i] = fib_l[i-1] + fib_l[i-2]

make_fib(n+3)
ret = 1
for i in range(m+1):
    t = a[i+1] - a[i] - 2
    if t < 0:
        ret = 0
        break
    ret *= fib_l[t]
print((ret % 1000000007))

# Optimized solution
from sys import stdin

n, m = [int(i) for i in stdin.readline().rstrip().split()]
a = [-1] + [int(stdin.readline()) for _ in range(m)] + [n+1]

fib_l = [-1] * (n+3)

def make_fib(n):
    fib_l[0] = fib_l[1] = 1
    for i in range(2, n):
        fib_l[i] = fib_l[i-1] + fib_l[i-2]

make_fib(n+3)
ret = 1
for i in range(m+1):
    t = a[i+1] - a[i] - 2
    if t < 0:
        ret = 0
        break
    ret *= fib_l[t]
print((ret % 1000000007))
# Original solution
n,m = list(map(int,input().split()))
A = list()
for i in range(m):
    a = int(eval(input()))
    A.append(a)
dp = [0]*(n+1)
dp[0] = 1
if 1 not in A:
    dp[1] = 1
for i in range(2,n+1):
    if i not in A:
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] = dp[i]%1000000007
print((dp[-1]%1000000007))

# Optimized solution
n,m = list(map(int,input().split()))
A = list()
for i in range(m):
    a = int(eval(input()))
    A.append(a)
dp = [0]*(n+1)
dp[0] = 1
if 1 in A:
  del A[0]
else:
  dp[1] = 1
for i in range(2,n+1):
    if len(A) != 0:        
        if i != A[0]:
            dp[i] = dp[i-2] + dp[i-1]
            dp[i] = dp[i]%1000000007
        else:
          del A[0]
    else:
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] = dp[i]%1000000007
print((dp[-1]%1000000007))
# Original solution
Num = 10 ** 9 + 7
N, M = list(map(int, input().split()))
danger = []
for i in range(M):
  danger.append(int(eval(input())))
l = [1, 1]
for i in range(1, N):
  if i in danger:
    l[1] = 0
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N in danger:
  l[1] = 0
print((l[1] % Num))

# Optimized solution
Num = 10 ** 9 + 7
N, M = list(map(int, input().split()))
danger = -1
if M != 0:
  danger = int(eval(input()))
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(eval(input()))
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print((l[1] % Num))
# Original solution
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

if m != 0:
    lin = [int(stdin.readline().rstrip()) for _ in range(m)]
else:
    lin = [-1]

dp = [-1]*(n+1)
dp[0] = 1

if lin[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if i in lin:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

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

# Optimized solution
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

lin = [0]*(n+1)

if m != 0:
    for i in range(m):
        lin[int(stdin.readline().rstrip())] = -1

dp = [-1]*(n+1)

dp[0] = 1

if lin[1] == -1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if lin[i] == -1:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

print((dp[n]%(10**9+7)))
# Original solution
from sys import stdin
import bisect

n,m = [int(x) for x in stdin.readline().rstrip().split()]
if m == 0:
    li = [0]
else:
    li = [int(stdin.readline().rstrip()) for _ in range(m)]

dp = [-1]*(n+1)

dp[0] = 1

if li[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if li[bisect.bisect_right(li,i)-1] == i:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

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

# Optimized solution
n,m = list(map(int,input().split()))
a = [int(eval(input())) for _ in range(m)]

now = 0
point = 1
mod = 10**9+7

def fib(n,mod):
    a, b = 1, 1
    for _ in range(n):
        a, b = b %mod, (a + b)%mod
    return a%mod

for i in range(1,m):
    if a[i-1]+1 == a[i]:
        print((0))
        exit()

for i in a:
    point *= fib((i-1-now),mod)
    point %= mod
    now = i+1
    if now == n:
        break

point *= fib(n-now,mod)
point %= mod

print(point)
# Original solution
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r)*math.factorial(r))

n,m=[int(i) for i in input().split()]
a1=[int(eval(input())) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in a1:
    a3=i-1-a2
    c2=0
    for j in range(a3//2+1):
        c2+=combinations_count(a3-j,j)
    c1=(c1*c2)%(1000000007)
    a2=i+1
    if c1==0:
        break



print(c1)


# Optimized solution
#フィボナッチ数列か…
#c問題も解けないのか…
#典型問題なんだろうな
#踏めない段の分は除いて考えれば良い
n,m=input().split()
n,m=int(n),int(m)
ax=[1]*(n+1)
for i in range(m):
    ax[int(eval(input()))]=0
bx=[1,1]
for i in range(2,n+1):
    if ax[i-1]==1:
        f1=bx[i-1]
    else:
        f1=0
    if ax[i-2]==1:
        f2=bx[i-2]
    else:
        f2=0
    bx.append((f1+f2)%(10**9+7))

print((bx[n]))
# Original solution
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():
    N, M = list(map(int,input().split()))
    A = [int(eval(input())) for _ in range(M)]


    dp = [0]*(N+1)
    dp[0]=1

    for i in range(N):
        if not i+1 in A:
            dp[i + 1] = (dp[i]+dp[i+1])%(10**9+7)
        if i < N - 1 and not i+2 in A:
            dp[i + 2] = (dp[i]+dp[i+2])%(10**9+7)
    print((dp[N]%(10**9+7)))



resolve()

# Optimized solution
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():

    N,M=list(map(int,input().split()))
    A=[int(eval(input())) for i in range(M)]


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

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

    print((dp[N]))

resolve()
# Original solution
mod = 10**9 + 7
n, m = list(map(int, input().split()))
a = [int(eval(input())) for _ in range(m)]

is_broken = [1] * (n+1)
for i in range(n):
    if i in a:
        is_broken[i] = 0

step = [i for i in range(n+1)]
step[0] = 1

for i in range(n):
    if i - 1 >= 0:
        step[i+1] = step[i] * is_broken[i] + step[i-1] * is_broken[i-1]
    else:
        step[i+1] = step[i] * is_broken[i]
    step[i+1] %= mod

print((step[n]))

# Optimized solution
mod = 10**9 + 7
n, m = list(map(int, input().split()))
a = [int(eval(input())) for _ in range(m)]

is_broken = [1] * (n+1)

for i in range(m):
    is_broken[a[i]] = 0

step = [i for i in range(n+1)]
step[0] = 1

for i in range(n):
    if i - 1 >= 0:
        step[i+1] = step[i] * is_broken[i] + step[i-1] * is_broken[i-1]
    else:
        step[i+1] = step[i] * is_broken[i]
    step[i+1] %= mod

print((step[n]))
# Original solution
n,m=list(map(int,input().split()))
A=[int(eval(input())) for i in range(m)]
mod=10**9+7
flag=1
S=[0 for i in range(n+3)]
S[0]=1
SET=set(A)
for i in range(n):
    if i in SET:
        S[i]=0
        if i+1 in SET:
            flag=0
    S[i+1]+=S[i]
    S[i+2]+=S[i]
    
print((S[n]%mod if flag==1 else 0))
#配る方で解いてみた。

# Optimized solution
import sys
input=sys.stdin.buffer.readline
n,m=list(map(int,input().split()))
mod=10**9+7
dp=[0]*(n+1)
for _ in range(m):
    a=int(eval(input()))
    dp[a]=-1
dp[0]=1
for i in range(n):
    if dp[i]>=0:
        if i+1<=n:
            if dp[i+1]>=0:
                dp[i+1]+=dp[i]
                dp[i+1]%=mod
        if i+2<=n:
            if dp[i+2]>=0:
                dp[i+2]+=dp[i]
                dp[i+2]%=mod
print((dp[n] if dp[n]>0 else 0))
# Original solution
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
a = [0]*M
mod = 10**9+7

for i in range(M):
    a[i] = int(eval(input()))

DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1

for i in range(2, N+1):
    if(i not in a):
        DP[i] = (DP[i-1]+DP[i-2])%mod
        
print((DP[-1]))

# Optimized solution
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
a = [0]*M
mod = 10**9+7

for i in range(M):
    a[i] = int(eval(input()))

a = set(a)
DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1

for i in range(2, N+1):
    if(i not in a):
        DP[i] = (DP[i-1]+DP[i-2])%mod
        
print((DP[-1]))
# Original solution
mod=10**9+7
N,M=list(map(int,input().split()))
A=[int(eval(input())) for m in range(M)]
L=[1 for n in range(N+1)]
for a in A:
    L[a]=0
Block=[0,1]
for n in range(1,N+1):
    if L[n]==1:
        Block=Block[1:]+[sum(Block)%mod]
        
    else:
        Block=Block[1:]+[0]
print((Block[-1]))

# Optimized solution
mod=10**9+7
N,M=list(map(int,input().split()))
A=[int(eval(input())) for m in range(M)]
L=[1 for n in range(N+1)]
for a in A:
    L[a]=0
Block=[0,1]
for n in range(1,N+1):
    if L[n]:
        Block=Block[1:]+[sum(Block)%mod]
    else:
        Block=Block[1:]+[0]
print((Block[-1]))
# Original solution
n, m = list(map(int, input().split()))
a = [int(eval(input())) for i in range(m)]

mod = 10**9+7
dp = [0] * (n+1)
dp[0] = 1

for i in range(1,n+1):
    if i in a:
        continue
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print((dp[-1]))

# Optimized solution
n,m = list(map(int,input().split()))
mod = 10**9+7
a = set()
for i in range(m):
  s = int(eval(input()))
  a.add(s)
  
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
  if i in a:
    continue
  dp[i] = (dp[i-1] + dp[i-2]) % mod
  
print((dp[-1]))
# Original solution
import sys

S = sys.stdin.readline().strip()
T = sys.stdin.readline().strip()

ls = len(S)
lt = len(T)
match = 0
for i in range(ls - lt + 1):
    tmp = 0
    for j in range(lt):
        if S[i+j] == T[j]:
            tmp += 1
    match = max(match, tmp)

print((lt - match))

# Optimized solution
import sys

input = sys.stdin.readline
S = input().strip()
T = input().strip()

ans = float("inf")
ls = len(S)
lt = len(T)
for i in range(ls - lt + 1):
    tmp = 0
    for j in range(lt):
        if S[i+j] != T[j]:
            tmp += 1
    ans = min(ans, tmp)

print(ans)
# Original solution
import sys
import math

#https://atcoder.jp/contests/agc008/submissions/15248942
sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

S = input()
T = input()

ans = 0
for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        if (j-i) == len(T):
            match = 0
            for k,l in enumerate(range(i,j)):
                if S[l] == T[k]:
                    match += 1
            ans = max(ans,match)

print(len(T)-ans)



# Optimized solution
import sys
import math

#https://atcoder.jp/contests/agc008/submissions/15248942
sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

S = input()
T = input()
ans = 1e9

for si in range(len(S)):
    if si+len(T) > len(S):
        break
    cnt = 0
    for i in range(len(T)):
        if S[si+i] != T[i]:
            cnt += 1
    ans = min(ans,cnt)

print(ans)
# Original solution
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


S = LS2()
T = LS2()
a = len(S)
b = len(T)

ans = 10000
for i in range(a-b+1):
    x = 0
    for j in range(b):
        if S[i+j] != T[j]:
            x += 1
    ans = min(ans,x)
print(ans)


# Optimized solution
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


S,T = LS2(),LS2()
a,b = len(S),len(T)

ans = 1000
for i in range(a-b+1):
    x = 0
    for j in range(b):
        if S[i+j] != T[j]:
            x += 1
    ans = min(ans,x)
print(ans)
# Original solution
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


S = LS2()
T = LS2()
s = len(S)
t = len(T)

ans = 10**5
for i in range(s-t+1):
    count = 0
    for j in range(t):
        if T[j] != S[i+j]:
            count += 1
    ans = min(ans,count)

print(ans)


# Optimized solution
import sys
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


S = LS2()
T = LS2()
s = len(S)
t = len(T)

ans = 10**5
for i in range(s-t+1):
    count = 0
    for j in range(t):
        if T[j] != S[i+j]:
            count += 1
    ans = min(ans,count)

print(ans)
# Original solution
from sys import stdin
import re
from itertools import combinations


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S = _in[0]  # type:str
    T = _in[1]  # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    if T in S:
        ans = 0
    else:
        for i in range(len(T)):
            ans = i + 1
            index = [j for j in range(len(T))]
            comb = list(combinations(index, i+1))

            for _comb in comb:
                t = list(T)
                for _i in _comb:
                    t[_i] = r'(\w)'
                t = r''.join(t)
                if re.search(t, S):
                    break
            else:
                continue
            break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S = _in[0]  # type:str
    T = _in[1]  # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = float('inf')
    S_ = list(S)
    T_ = list(T)

    for i in range(len(S_)-len(T_)+1):
        s_ = S_[i:i+len(T_)]
        cnt = 0
        for a,b in zip(s_, T_):
            if a == b:
                pass
            else:
                cnt += 1
        ans = min(ans, cnt)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
s,t=open(0)
print((min(sum(x!=y for x,y in zip(s[i:],t[:-1]))for i in range(len(s)-len(t)+1))))

# Optimized solution
s,(*t,_)=open(0)
print((min(sum(x!=y for x,y in zip(s[i:],t))for i in range(len(s)-len(t)))))