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

s = input()
n = len(s)
mod = 10**9+7
dp = [0]*13
dp[0] = 1
for i,d in enumerate(s):
	_dp=[0]*13
	if d=="?":
		for x in range(10):
			for y in range(13):
				_dp[(y*10+x)%13] += dp[y]
	else:
		d = int(d)
		for y in range(13):
			_dp[(y*10+d)%13] += dp[y]
	for j in range(13):
		_dp[j] %= mod
	dp=_dp
print(dp[5])

### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i,d in enumerate(s):
	if d=="?":
		for x in range(10):
			for y in range(13):
				dp[i+1][(y*10+x)%13] += dp[i][y]
	else:
		d = int(d)
		for y in range(13):
			dp[i+1][(y*10+d)%13] += dp[i][y]
	for j in range(13):
		dp[i+1][j] %= mod
print(dp[n][5])
### BUGGY CODE ###

import functools
import fractions
MOD = 10**9+7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(numbers):
    return functools.reduce(lcm_base, numbers, 1)


def main():
    n = int(input())
    x = list(map(int, input().split()))

    l = lcm(x)
    ans = 0
    for i in range(n):
        ans += l // x[i]
        ans %= MOD

    print(ans)


main()


### FIXED CODE ###

import functools
import fractions
MOD = 10**9+7


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(numbers):
    return functools.reduce(lcm_base, numbers, 1)


def main():
    n = int(input())
    x = list(map(int, input().split()))

    l = lcm(x)
    ans = 0
    for i in range(n):
        ans += l // x[i]

    print(ans % MOD)


main()
### BUGGY CODE ###

n = int(raw_input())
S = map(int,raw_input().split())
q = int(raw_input())
T = map(int,raw_input().split())

r = 0

for c in T:
    if c in S:
	r += 1
print r

### FIXED CODE ###

n = input()
S = set(raw_input().split())
q = input()
T = set(raw_input().split())

print (len(S&T))
### BUGGY CODE ###

N=int(input())
D=[]
x=[]
D = [[0 for i in range(2)] for j in range(N)]#N×"2"の行列Dを作る
for i in range(0,N):
    x=input().split(" ")
    for j in range(0,2):#i行目の成分を入力
        D[i][j]=int(x[j])

D.sort(key=lambda p:p[1])#2列目の成分でソート

x=0
for i in range(0,N):
    x=x+D[i][0]#経過時間
    y=D[i][1]#締め切り時刻
    if x>y:
        n=1
        break
    else:
        z=0
        for j in range(0,N):
            z=z+D[j][0]
            if z<=D[N-1][1]:
                n=0
if n==1:
    print('No')
else:
    print('Yes')


### FIXED CODE ###

N=int(input())
D=[]
x=[]
D = [[0 for i in range(2)] for j in range(N)]#N×"2"の行列Dを作る
for i in range(0,N):
    x=input().split(" ")
    for j in range(0,2):#i行目の成分を入力
        D[i][j]=int(x[j])

D.sort(key=lambda p:p[1])#2列目の成分でソート

x=0
for i in range(0,N):
    x=x+D[i][0]#経過時間
    y=D[i][1]#締め切り時刻
    if x>y:
        n=1
        break
    else:
        n=0
if n==1:
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n=int(input())
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    cost[x][y] = 1
    cost[y][x] = 1
l=dijkstra(0,n,n-1,cost)
ll=dijkstra(n-1,n,n-1,cost)
s,f=0,0
for i in range(n):
    if l[i]<=ll[i]:
        f+=1
    else:
        s+=1
if f<=s:
    print("Snuke")
else:
    print("Fennec")




### FIXED CODE ###

n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    l[x].append(y)
    l[y].append(x)
from collections import deque
q=deque([0])
lf=[10**100 for i in range(n)]
lf[0]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if lf[p]+1<lf[i]:
            lf[i]=lf[p]+1
            q.append(i)
q=deque([n-1])
ls=[10**100 for i in range(n)]
ls[n-1]=0
while q:
    p=q.popleft()
    for i in l[p]:
        if ls[p]+1<ls[i]:
            ls[i]=ls[p]+1
            q.append(i)
s,f=0,0
for i in range(n):
    if lf[i]<=ls[i]:
        f+=1
    else:
        s+=1
if f<=s:
    print("Snuke")
else:
    print("Fennec")
### BUGGY CODE ###

import sys
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid, flush=True)
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        if mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
            
print(0, flush=True)
start=input()
if start=='Vacant':exit()
bin(start)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
sys.stdout.flush()
start=input()
if start=='Vacant':exit()
bin(start)
### BUGGY CODE ###

def main():
    S = [int(i) if i != '?' else -1 for i in input()]
    s = len(S)
    mod = 10 ** 9 + 7

    dp = [[0] * 13 for _ in range(s)]
    table = [[0] * 10 for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table[i][j] = (i * 10 + j) % 13

    if S[0] == -1:
        for i in range(10):
            dp[0][i] += 1
    else:
        dp[0][S[0] % 13] += 1

    for i in range(1, s):
        if S[i] == -1:
            for j in range(13):
                for k in range(10):
                    dp[i][table[j][k]] = (dp[i][table[j][k]] + dp[i - 1][j]) % mod
        else:
            for j in range(13):
                dp[i][table[j][S[i]]] = dp[i - 1][j]

    print(dp[-1][5] % mod)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = [int(i) if i != '?' else -1 for i in input()]
    s = len(S)
    mod = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(s)]

    table = [[0] * 10 for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table[i][j] = (i * 10 + j) % 13

    table2 = [[] for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table2[table[i][j]].append(i)
    t = set(range(13))
    table2 = [t - set(i) for i in table2]

    if S[0] == -1:
        for i in range(10):
            dp[0][i] += 1
    else:
        dp[0][S[0] % 13] += 1

    for i in range(1, s):
        if S[i] == -1:
            temp = sum(dp[i - 1])
            for j in range(13):
                dp[i][j] = temp
                for k in table2[j]:
                    dp[i][j] -= dp[i - 1][k]
                dp[i][j] %= mod
        else:
            for j in range(13):
                dp[i][table[j][S[i]]] = dp[i - 1][j]

    print(dp[-1][5] % mod)


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

H,W,K=map(int,input().split())
g=[input() for _ in range(H)]
ans=1<<100
for i in range(1<<H-1):
	need=bin(i).count("1")
	sz=need+1
	cnt=[0]*sz
	f=1
	for j in range(W):
		c=0
		for k in range(H):
			cnt[c]+=g[k][j]=="1"
			if cnt[c]>K:
				break
			c+=(i>>k)&1
		else:
			continue
		cnt=[0]*sz
		need+=1
		c=0
		for k in range(H):
			cnt[c]+=g[k][j]=="1"
			if cnt[c]>K:
				break
			c+=(i>>k)&1
		else:
			continue
		f=0
		break
	if f:
		ans=min(ans,need)
print(ans)



### FIXED CODE ###

h,w,k=map(int,input().split())
Cho=[list(map(int,list(input()))) for _ in range(h)]
ans=10000000
for i in range(2**(h-1)):
	need=0
	seq=[]
	t=[]
	for j in range(h-1):
		t.append(j)
		if i&(1<<j):
			need+=1
			seq.append(t)
			t=[]
	seq.append(t+[h-1])
	f=1
	q=need+1
	cnt=[0]*q
	for x in range(w):
		cntp=[0]*q
		for i,g in enumerate(seq):
			cntg=0
			for y in g:
				cntg+=Cho[y][x]
				if cntg>k:
					f=0
					break
				cntp[i]+=Cho[y][x]
			if not f:
				break
		if not f:
			break
		for xx in range(q):
			cnt[xx]+=cntp[xx]
		if any(xxx>k for xxx in cnt):
			need+=1
			if need>ans:
				f=0
				break
			cnt=cntp
	if f:
		ans=min(ans,need)
print(ans)
### BUGGY CODE ###

S = input()
#S = "?" * (10 ** 5)
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S))]
if S[0] == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(S[0])] = 1
#print(dp)
for i in range(len(S) - 1):
  if S[i + 1] == "?":
    for j in range(13):
      for k in range(10):
        dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % mod
        dp[i + 1][(j * 10 + k) % 13] %= mod
  else:
    for j in range(13):
      dp[i + 1][(j * 10 + int(S[i + 1])) % 13] += dp[i][j] % mod
      dp[i + 1][(j * 10 + int(S[i + 1])) % 13] %= mod
#print(dp)
print(dp[len(S) - 1][5] % (10 ** 9 + 7))

### FIXED CODE ###

S = input()
#S = "19?04??????451??" * (10 ** 5 // 5)
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S))]
if S[0] == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(S[0])] = 1
#print(dp)
for i in range(len(S) - 1):
  if S[i + 1] == "?":
    for j in range(13):
      for k in range(10):
        dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % mod
  else:
    for j in range(13):
      dp[i + 1][(j * 10 + int(S[i + 1])) % 13] += dp[i][j] % mod
#print(dp)
print(dp[len(S) - 1][5] % (10 ** 9 + 7))
### BUGGY CODE ###

L, R = map(int, input().split())
if R - L >= 2019:
    print(0)
result = float('inf')
for i in range(L, R):
    for j in range(i + 1, R + 1):
        mod = (i * j) % 2019
        if mod == 0:
            result = 0
            break
        elif mod < result:
            result = mod
print(result)

### FIXED CODE ###

L, R = map(int, input().split())
if R - L >= 2019:
    print(0)
else:
    result = float('inf')
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            mod = (i * j) % 2019
            if mod == 0:
                result = 0
                break
            elif mod < result:
                result = mod
    print(result)
### BUGGY CODE ###

N = int(input())
a = []
a = list(map(int,input().split()))
index = 0
count = 0
searchNum = 1
for j in range(N):
    if not 1 in a:
        count = -1
        break
    if a[j] ==searchNum:
        searchNum += 1
        continue
    else:
        count +=1
print(count)



### FIXED CODE ###

N = int(input())
a = []
a = list(map(int,input().split()))
index = 0
count = 0
searchNum = 1
if not 1 in a:
    count = -1
else:
    for j in range(N):

        if a[j] ==searchNum:
            searchNum += 1
            continue
        else:
            count +=1
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
for i in range(q):
    b,c = list(map(int,input().split()))
    a = [i if i!=b else c for i in a]
    print(sum(a))

### FIXED CODE ###

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

import collections
ans = sum(a)
a = collections.Counter(a)

for i in range(q):
    b,c = list(map(int,input().split()))
    d = a[b]
    ans -= d*b
    a[b] = 0
    ans += d*c
    a[c] += d
    print(ans)
### BUGGY CODE ###

import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        q = deque()
        q.append([i, j, 0])
        if s[i][j] == '#': continue
        visited = np.zeros((h + 5, w + 5))
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)
### BUGGY CODE ###

n,m=[int(x) for x in input().rstrip().split()]
l=[[]*n for x in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

done=[False for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True or i in stack:
        continue
      ans[i]=now+1
      done[i]=True
      stack.append(i)

bfs()
print("Yes")
for i in range(1,n):
  print(ans[i])

### FIXED CODE ###

n,m=[int(x) for x in input().rstrip().split()]
l=[[] for x in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

done=[False for i in range(n)]
ans=[0 for i in range(n)]
def bfs():
  stack=[0]
  done[0]=True
  while(stack):
    now=stack.pop(0)
    done[now]=True
  
    for i in l[now]:
      if done[i]==True:
        continue
      ans[i]=now+1
      done[i]=True
      stack.append(i)

bfs()
print("Yes")
print(*ans[1:])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h1(self, key):
        return key % self.length

    def h2(self, key):
        return 1 + (key % (self.length - 1))

    def h(self, key, i):
        return (self.h1(key) + i*self.h2(key)) % self.length

    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    #C = map(lambda x:(x[0], getNum(x[1])), C)
    
    for command, char in C:
        num = getNum(char)
        if command == "insert":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")



### FIXED CODE ###

# -*- coding: utf-8 -*-

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h(self, key, i):
        h1 = key % self.length
        h2 = 1 + (key % (self.length - 1))
        return (h1 + i*h2) % self.length

    def insert(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")
### BUGGY CODE ###

import itertools

N = int(input())
S = str(input())

c = list(itertools.combinations_with_replacement(list(range(1,N+1)), 3))

ans = 0
for i in range(len(c)):
    if S[c[i][0]-1] != S[c[i][1]-1] and S[c[i][0]-1] != S[c[i][2]-1] and S[c[i][1]-1] != S[c[i][2]-1] and c[i][1]-c[i][0] != c[i][2]-c[i][1]:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())

r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = S.count('B')

ans = r_cnt*g_cnt*b_cnt

for i in range(N):
    for d in range(1, N):
        j = i + d
        k = j + d
        if k >= N:break
        if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
            ans -= 1

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

A, B = [int(x) for x in input().split(" ")]

for k in range(0,10**9):
  if abs(A-k) == abs(B-k):
    print(k)
  else:
    print("IMPOSSIBLE")


### FIXED CODE ###

A, B = [int(x) for x in input().split(" ")]

if (A+B)%2 == 0:
  print(int((A+B)/2))
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
c=0
for i in range(n):
    if p[i]==min(p[:i+1]):
        c+=1
print(c)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
c=0
m=n+1
for i in p:
    if i<m:
        m=i
        c+=1
print(c)
### BUGGY CODE ###

import math
def main():

    N = int(input())

    d = [0 for _ in range(N+1)]

    v = int(math.sqrt(N))
    for i in range(1, v+1):
        p = i
        while p <= N:
            d[p] += 1
            if p//i > v and p//i > i:
                d[p] += 1
            p += i
    ans = 0
    for i in range(1, N+1):
        ans += i * d[i]
    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def fib_1(n):
    if not n or n == 1:
        return 1
    return fib_1(n - 2) + fib_1(n - 1)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    index = int(_input[0])
    print(fib_1(index))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


# def fib_bad(n):
#     if not n or n == 1:
#         return 1
#     return fib_bad(n - 2) + fib_bad(n - 1)


def fib_dp(n):
    fib_list[:1] = [1, 1]
    for i in range(2, n + 1):
        fib_list[i] = fib_list[i - 2] + fib_list[i - 1]
    return fib_list[n]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    index = int(_input[0])
    fib_list = [None] * index
    print(fib_dp(index))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())
s = input()


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in range(m, 0, -1):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    print(*solve(s))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())
s = input()


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    if m == 1:
        ans = [1] * n
    else:
        ans = solve(s)
    print(*ans)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    num_max = 3 * 10 ** 5 + 1
    numbers = np.zeros(num_max, dtype=np.int64)
    for _ in range(N):
        a = int(input())
        numbers[a] += 1

    ans = 0
    for index, num in enumerate(numbers):
        if num == 0:
            continue
        ans = max(numbers[index - K:index + K].sum(), ans)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
class segtree:
    """
    segment tree
    value store as object type and get update function(merge_func) from outside

    Attributes
    ----------
    n : int
        Number of elements
    initialize_func : func
        function for initialization
    merge_func : func
        function for merge x and y to x(this merge is distruction update)

    Methods
    -------
    update(i, x)
        update tree[i] value to x
    get(a, b)
        get value from [a, b)
        include a but not include b, return a merged value
    """
    def __init__(self, n, initialize_func, merge_func):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of elements
        initialize_func : func
            function for initialization
        merge_func : func
            function for merge x and y to x(this merge is distruction update)
        """
        self.n = n
        self.initialize = initialize_func
        self.merge = merge_func
        n2 = 1  # n2はnより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [initialize_func() for _ in range(n2 << 1)]

    def update(self, index, x):
        index += self.n2
        self.tree[index] = self.merge(self.tree[index], x)
        while index > 1:
            # (index ^ 1) はiと1の排他的論理和(XOR)
            x = self.merge(x, self.tree[index ^ 1])
            index >>= 1  # 右ビットシフトで親ノードのインデックスへ移動
            self.tree[index] = self.merge(self.tree[index], x)

    def get(self, a, b):
        result = self.initialize()
        q = [(1, 0, self.n2)]
        while q:
            k, left, right = q.pop()
            if a <= left and right <= b:
                result = self.merge(result, self.tree[k])
                continue
            m = (left + right) // 2
            k <<= 1
            if a < m and left < b:
                q.append((k, left, m))
            if a < right and left < m:
                q.append((k + 1, m, right))
        return result


def main():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    max_A = 3 * 10 ** 5 + 1

    seg = segtree(max_A, lambda: 0, max)
    for a in A:
        next = seg.get(max(0, a - K), min(a + K + 1, max_A))
        seg.update(a, next + 1)
    print(seg.get(0, max_A))


if __name__ == '__main__':
    main()