CodeEff/ECCO huggingface dataset:
# Original solution
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    N, T = list(map(int, input().split()))
    A = list(map(int, readline().split()))

    if N == 2:
        print((1))
        return
    
    L = SegmentTree(A, min, float('inf'))
    R = SegmentTree(A, max, 0)

    profit = 0
    for i in range(1, N + 1):
        l = L.get(0, i + 1)
        r = R.get(i, N + 1)
        profit = max(profit, r - l)
    
    cnt = 0
    for i in range(N):
        l = L.get(0, i + 1)
        r = R.get(i, N + 1)
        if r - l == profit:
            if l == A[i]:
                L.update(i, l - 1)
            else:
                R.update(i, r + 1)
            cnt += 1
    
    print(cnt)


if __name__ == "__main__":
    main()


# Optimized solution
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    N, T = list(map(int, input().split()))
    A = list(map(int, readline().split()))

    L = float('inf')
    cnt = 0
    profit = 0
    for a in A:
        if a - L > profit:
            cnt = 1
            profit = a - L
        elif a - L == profit:
            cnt += 1
        
        if a < L:
            L = a
    
    print(cnt)


if __name__ == "__main__":
    main()
# Original solution
N,T = list(map(int,input().split()))
List = list(map(int,input().split()))
dic = {}
min = List[0]
for i in range(N):
  if List[i]<min:
    min = List[i]
  if List[i]-min not in dic:
    dic[List[i]-min] = 1
  else:
    dic[List[i]-min] += 1
dic2 = sorted(list(dic.items()), reverse=True)
Answer = dic2[0][1]
print(Answer)

# Optimized solution
n, t = list(map(int, input().split()))
*a, = list(map(int, input().split()))
purchase = a[0]
profit = []
for i in range(len(a)):
  profit.append(a[i] - purchase)
  if a[i] < purchase:
    purchase = a[i]
profit.sort()
Answer = profit.count(profit[-1])
print(Answer)
# Original solution
N,T = list(map(int,input().split()))
src = list(map(int,input().split()))
minv = src[0]
maxp = ans = 0
for i in range(1,N):
    profit = src[i] - minv
    if profit == maxp:
        ans += 1
    elif profit > maxp:
        maxp = profit
        ans = 1
    minv = min(minv, src[i])

print(ans)

# Optimized solution
N,T = list(map(int,input().split()))
src = list(map(int,input().split()))

mincost = src[0]
maxgain = 0
sell = 0
buy = 1
for a in src[1:]:
    if a < mincost:
        mincost = a
        buy = 1
    elif a == mincost:
        buy += 1
    elif a > mincost + maxgain:
        maxgain = a - mincost
        sell = 1
    elif a == mincost + maxgain:
        sell += 1

print((max(sell,buy)))
# Original solution
N,T = list(map(int,input().split()))
src = list(map(int,input().split()))

mincost = src[0]
maxgain = 0
sell = 0
buy = 1
for a in src[1:]:
    if a < mincost:
        mincost = a
        buy = 1
    elif a == mincost:
        buy += 1
    elif a > mincost + maxgain:
        maxgain = a - mincost
        sell = 1
    elif a == mincost + maxgain:
        sell += 1

print((max(sell,buy)))


# Optimized solution
N,T = list(map(int,input().split()))
A = list(map(int,input().split()))
mn = A[0]
gain = 0
ans = 1
for a in A[1:]:
    if a < mn:
        mn = a
        continue
    if a-mn == gain:
        ans += 1
    elif a-mn > gain:
        gain = a-mn
        ans = 1
print(ans)
# Original solution
N, T = list(map(int, input().split()))
A = list(map(int, input().split()))

max_bef = 0
cnt = 0
A_min = A[0]

for i in range(1,N):
    tmp = A[i] - A_min
    if max_bef < tmp:
        max_bef = tmp
        cnt = 0
    if max_bef == tmp:
        cnt += 1
    A_min = min(A_min, A[i])

print(cnt)


# Optimized solution
def main():
    N, T = list(map(int, input().split()))
    A = list(map(int, input().split()))
    min_A = float('inf')
    cnt = 0
    profit = 0
    for i in range(N):
        min_A = min(min_A,A[i])
        diff_A = A[i] - min_A
        if profit == diff_A:
            cnt += 1
        elif profit < diff_A:
            cnt = 1
            profit = diff_A
    print(cnt)



if __name__ == "__main__":
    main()
# Original solution
from collections import defaultdict
n, t = list(map(int, input().split()))
A = list(map(int, input().split()))

MAX_S = []
max_tmp = 0
for a in A[::-1]:
    if max_tmp < a:
        max_tmp = a
    MAX_S.append(max_tmp)
MAX_S = MAX_S[::-1]
cnt = defaultdict(int)
for a, s in zip(A, MAX_S):
    cnt[s-a] += 1

c = [(k, v) for k, v in list(cnt.items())]
c.sort(reverse=True)
print((c[0][-1]))


# Optimized solution
from collections import defaultdict
n, _ = list(map(int, input().split()))
A = list(map(int, input().split()))

MAX_S = []
max_s = 0
for a in A[::-1]:
    if max_s < a:
        max_s = a
    MAX_S.append(max_s)
MAX_S = MAX_S[::-1]
cnt = defaultdict(int)
for a, s in zip(A, MAX_S):
    cnt[s-a] += 1

print((sorted(list(cnt.items()), reverse=True)[0][1]))
# Original solution
# -*- coding: utf-8 -*-

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

apple_price = list(map(int, input().split()))
price_diff = []

for i in range(n):
    if(i <= n-2):
        if(apple_price[i] < apple_price[i+1]):
            for j in range(i,n):
                diff = apple_price[j] - apple_price[i]
                if(diff>0):
                    price_diff.append(diff)
    else:
        for j in range(i, n):
            diff = apple_price[j] - apple_price[i]
            if (diff > 0):
                price_diff.append(diff)

if(price_diff):
    print((price_diff.count(max(price_diff))))
else:
    print((0))

# Optimized solution
# -*- coding: utf-8 -*-

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

apple_price = list(map(int, input().split()))
price_diff = []
now_min = 10**9


for i in range(n):
    if(now_min > apple_price[i]):
        now_min = apple_price[i]
    else:
        price_diff.append(apple_price[i] - now_min)

if(price_diff):
    print((price_diff.count(max(price_diff))))
else:
    print((0))
# Original solution
N,T=list(map(int,input().split()))
A=list(map(int,input().split()))


import collections
table=collections.defaultdict(set)
table2=collections.defaultdict(set)
tmp=0
for i in range(N-1):
  for j in range(i+1,N):
    table[A[j]-A[i]].add(i)
    table2[A[j]-A[i]].add(j)
    tmp=max(tmp,A[j]-A[i])
print((min(len(table[tmp]),len(table2[tmp]))))


# Optimized solution
N,T=list(map(int,input().split()))
A=list(map(int,input().split()))


import heapq
import collections
hq=[]
heapq.heapify(hq)
heapq.heappush(hq,A[0])
tmp=0
table=collections.defaultdict(int)
for i in range(1,N):
  j=heapq.heappop(hq)
  table[A[i]-j]+=1
  tmp=max(tmp,A[i]-j)
  heapq.heappush(hq,j)
  heapq.heappush(hq,A[i])
print((table[tmp]))
# Original solution
N, T = list(map(int, input().split()))
A = [int(i) for i in input().split()]

c = 0
MAX = 0
for i in range(N-1):
    a1 = min(A[:i+1])
    a2 = A[i+1]
    if MAX == a2 - a1:
        c += 1
    elif MAX < a2 - a1:
        MAX = a2 - a1
        c = 1
print(c)


# Optimized solution
N, T = list(map(int, input().split()))
A = [int(i) for i in input().split()]

c = 0
MAX = 0
a1 = A[0]
for i in range(N-1):
    if A[i] <= a1:
        a1 = A[i]
    a2 = A[i+1]
    if MAX == a2 - a1:
        c += 1
    elif MAX < a2 - a1:
        MAX = a2 - a1
        c = 1
print(c)
# Original solution
import sys
import heapq
def v():
    N,T=tuple(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))
    d=[]
    for i,a in enumerate(A[:-1]):
        b=max(A[i+1:])
        c=b-a if b>a else 0
        d.append(-c)
    heapq.heapify(d)
    res,x=1,heapq.heappop(d)
    while len(d)>0:
        y=heapq.heappop(d)
        if x==y:res+=1
    print(res)
if __name__=='__main__':v()

# Optimized solution
import sys
import heapq
def v():
    N,T=tuple(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))
    ma=0
    d=[]
    heapq.heapify(d)
    for a in reversed(A):
        if a<ma:heapq.heappush(d,a-ma)
        else:ma=a
    res,x=1,heapq.heappop(d)
    while len(d)>0:
        y=heapq.heappop(d)
        if x==y:res+=1
    print(res)
if __name__=='__main__':v()
# Original solution
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
#n = int(input())
n,t = [int(i) for i in readline().split()]
a = [10**9+1]+[int(i) for i in readline().split()]


"""
gain = 0
m = 0
maxid = []
minid = []
memo = {}
for i in range(n-1,-1,-1):
    ai = a[i]
    if ai > m:
        m = ai
        maxid = [i]
        memo.append([minid[:],maxid[:]])
    elif ai == m:
        maxid.append[i]

    m = max(ai,m)
    if gain < m-ai:
        gain = m-ai
        minid = [i]
        memo = []
    elif gain == m-ai:
        minid.append(i)
    
    print(minid,maxid,memo)
"""    

gain = 0
m = 0
for ai in reversed(a):
    m = max(ai,m)
    if gain < m-ai: gain = m-ai

m = 0
mi = ma = 0

ans = 0
for ai in reversed(a):
    if m < ai:
        ans += max(mi,ma)
        mi = ma = 0
    elif m == ai:
        ma += 1

    m = max(m,ai)
    
    if m-ai == gain:
        mi += 1


print(ans)    






# Optimized solution
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
#n = int(input())
n,t = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

m = gain = 0
ans = 0
for ai in reversed(a):
    m = max(ai,m)
    if gain < m-ai:
        ans = 1
    elif gain == m-ai:
        ans += 1
    gain = max(gain,m-ai)

print(ans)
# Original solution
iN,iT = [int(_) for _ in input().split()]
aA = [int(_) for _ in input().split()]
iL = len(aA)

aMaxD = [0]
aMin=[aA[0]]
iV = 0

def checkMax(aMaxD,aMin,iB):
    iMaxD = 0
    for iMin in aMin:
        iMaxD = max(iMaxD,iB - iMin)
    if aMaxD[0] < iMaxD:
        aMaxD = [iMaxD]
    elif aMaxD[0] == iMaxD:
        aMaxD.append(iMaxD)
    return aMaxD

for i in range(1,iL):
    iB = aA[i-1]
    iN = aA[i]
    if iB - iN > 0:
        if iV >= 0:
            aMaxD = checkMax(aMaxD,aMin,iB)
        iV = -1
    elif iB - iN < 0:
        if iV <= 0:
            aMin.append(iB)
        if i == iL -1 :
            aMaxD = checkMax(aMaxD,aMin,iN)
        iV = 1
print(( len(aMaxD) ))


# Optimized solution

iN,iT = [int(_) for _ in input().split()]
aA = [int(_) for _ in input().split()]
iL = len(aA)

aMaxD = [0]
iMin = aA[0]
iV = 0

def checkMax(aMaxD,iMaxD):
    if aMaxD[0] < iMaxD:
        aMaxD = [iMaxD]
    elif aMaxD[0] == iMaxD:
        aMaxD.append(iMaxD)
    return aMaxD

for i in range(1,iL):
    iB = aA[i-1]
    iN = aA[i]
    if iB - iN > 0:
        if iV >= 0:
            aMaxD = checkMax(aMaxD,iB-iMin)
        iV = -1
    elif iB - iN < 0:
        if iV <= 0:
            iMin = min(iB,iMin)
        iV = 1
aMaxD = checkMax(aMaxD,aA[-1] - iMin)
print(( len(aMaxD) ))
# Original solution
def 解():
    iN,iT = [int(_) for _ in input().split()]
    aA = [int(_) for _ in input().split()]
    iL = len(aA)

    aMaxD = [0]
    iMin = aA[0]
    iV = 0

    def checkMax(aMaxD,iMaxD):
        if aMaxD[0] < iMaxD:
            aMaxD = [iMaxD]
        elif aMaxD[0] == iMaxD:
            aMaxD.append(iMaxD)
        return aMaxD

    iB = aA[0]
    for iN in aA[1:]:
        if iB - iN > 0:
            if iV >= 0:
                aMaxD = checkMax(aMaxD,iB-iMin)
            iV = -1
        elif iB - iN < 0:
            if iV <= 0:
                iMin = min(iB,iMin)
            iV = 1
        iB = iN
    aMaxD = checkMax(aMaxD,aA[-1] - iMin)
    print(( len(aMaxD) ))
解()


# Optimized solution
def 解():
    iN,iT = [int(_) for _ in input().split()]
    aA = [int(_) for _ in input().split()]

    aMaxD = [0]
    iMin = aA[0]
    iV = 0

    def checkMax(aMaxD,iMaxD):
        if aMaxD[0] < iMaxD:
            aMaxD = [iMaxD]
        elif aMaxD[0] == iMaxD:
            aMaxD.append(iMaxD)
        return aMaxD

    iB = aA[0]
    for iN in aA[1:]:
        if iB - iN > 0: #山
            if iV >= 0:
                aMaxD = checkMax(aMaxD,iB-iMin)
            iV = -1
        elif iB - iN < 0: #谷
            if iV <= 0:
                if iB < iMin : iMin = iB
            iV = 1
        iB = iN
    aMaxD = checkMax(aMaxD,aA[-1] - iMin)
    print(( len(aMaxD) ))
解()
# Original solution
def main():
    N, T = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    target_list = list()
    price_buy, town_num_buy = A[N - 1], 1
    price_sell, town_num_sell = A[N - 1], 1
    for t in range(N - 2, -1, -1):
        price = A[t]
        if price < price_buy:
            price_buy = price
            town_num_buy = 1
        elif price == price_buy:
            town_num_buy += 1
        elif price == price_sell:
            town_num_sell += 1
        elif price > price_sell:
            target_list.append({
                'score': price_sell - price_buy,
                'town_num_buy': town_num_buy,
                'town_num_sell': town_num_sell
            })
            price_buy, town_num_buy = price, 1
            price_sell, town_num_sell = price, 1
    target_list.append({
        'score': price_sell - price_buy,
        'town_num_buy': town_num_buy,
        'town_num_sell': town_num_sell
    })
    max_score = max([target['score'] for target in target_list])
    ans = 0
    for target in target_list:
        if target['score'] < max_score:
            continue
        ans += min(target['town_num_buy'], target['town_num_sell'])
    print(ans)


if __name__ == '__main__':
    main()

# Optimized solution
def main():
    N, T = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    score_list = [0 for _ in range(N)]
    min_price = A[0]
    for i in range(N):
        a = A[i]
        score_list[i] = a - min_price
        min_price = min(a, min_price)
    max_score = max(score_list)
    ans = 0
    for i in range(N):
        if score_list[i] == max_score:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
N=int(input().split(" ")[0])
put=input().split(" ")
A=[]
for i in range(N):
    A.append(int(put[i]))

p=[A[0]]
for i in range(1,N-1):
    if A[i-1]<A[i] and A[i]>A[i+1]:
        p.append(A[i])
    elif A[i-1]>A[i] and A[i]<A[i+1]:
        p.append(A[i])

p.append(A[N-1])

x=0
t=1
for i in range(len(p)):
    k=i+1
    y=0
    while k<=(len(p)-1):
        if y< p[k]-p[i]:
            y=p[k]-p[i]
        k+=1
    if x<y:
        x=y
        t=1
    elif x==y:
        t=t+1

print(t)        

# Optimized solution
nt=input().split(" ")
N=int(nt[0])
T=int(nt[1])


a=input().split(" ")
int_a=[]
maxlist=[]
for i in range(N):
    int_a.append(int(a[i]))

reva=int_a
reva.reverse()
max=0
for i in range(N):
    if reva[i]>max:
        max=reva[i]
    maxlist.append(max)

maxlist.reverse()
int_a.reverse()


max=0
count=1
for i in range(N):
    if maxlist[i]-int_a[i]>max:
        count=1
        max=maxlist[i]-int_a[i]
    elif maxlist[i]-int_a[i]==max:
        count+=1

print(count)
# Original solution
n,t=list(map(int,input().split()))
a=list(map(int,input().split()))
max=0
ans=1
for i in range(len(a)-1):
  for j in range(i+1,len(a)):
    if (a[j]-a[i])>max:
      max=a[j]-a[i]
      ans=1
    elif (a[j]-a[i])==max:
      ans+=1
    else:
      pass
print(ans)
  

# Optimized solution
n,t=list(map(int,input().split()))
a=list(map(int,input().split()))
max=0
min=1000000000000000000000000000000000000
ans=1
for i in range(len(a)-1):
  if a[i]<min:
    min=a[i]
  elif min==a[i] or max==a[i]-min:
    ans+=1
  elif max<a[i]-min:
    ans=1
    max=a[i]-min
if a[len(a)-1]-min==max:
  ans+=1
print(ans)
# Original solution
n, t = list(map(int, input().split(" ")))
list_a = list(map(int, input().split(" ")))
list_profit = []
for i, a in enumerate(list_a[:-1]):
  max_price = max(list_a[(i+1):])
  if a < max_price:
    list_profit.append(max_price - a)
  else:
    list_profit.append(0)
max_profit = max(list_profit)
print((list_profit.count(max_profit)))

# Optimized solution
n, t = list(map(int, input().split(" ")))
list_a = list(map(int, input().split(" ")))
list_profit = []
min_price = list_a[0]
for a in list_a:
  if min_price < a:
    list_profit.append(a - min_price)
  else:
    list_profit.append(0)
    min_price = a
max_profit = max(list_profit)
print((list_profit.count(max_profit)))
# Original solution
class SEGTree:
    def __init__(self,n):
        self.Unit=0
        i=1
        while(i<n):
            i*=2
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]=x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=max(self.SEG[i*2+1],self.SEG[i*2+2])
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return max(c1,c2)
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)

N,T=list(map(int,input().split()))
A=list(map(int,input().split()))
SEG=SEGTree(N)
for i in range(N):
    SEG.update(i,A[i])
li=[0]*N
for i in range(N):
    li[i]=max(li[i],SEG.get(i+1,N)-A[i])
m=max(li)
ans=0
for i in range(N):
    if li[i]==m:
        ans+=1
print(ans)

# Optimized solution
N,T=list(map(int,input().split()))
A=list(map(int,input().split()))
ans=0
max_=0
B=[0]*N
for i in reversed(list(range(N))):
    B[i]=max(B[i],max_-A[i])
    max_=max(max_,A[i])
m=max(B)
print((B.count(m)))
# Original solution
# ans = 売る可能性がある場所の数 = 売って利益が最大値になる可能性がある場所
# Tは関係ない

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

# 売る場所を一つず右にずらす
# それより前の場所の最安値を持っておく
# 差分のmaxvalを満たす回数をカウント、maxvalが更新されたら回数は1に戻す

INF=10**9+1
maxval=0
minval=INF
ans=0
for i in range(1,len(A)):
  minval=min(A[i-1],minval)
  diff=A[i]-minval
  if diff>maxval:
    maxval=diff
    ans=1
  elif diff==maxval:
    ans+=1

print(ans)


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

# そこまでの最小値を記録する
# 最小値との差が最大になった時点で、その値を記録し、1を計上
# 最小値との差がこれまでの最大値と同じ場合は+1を計上
# 最小値との差の最大値が更新された場合はまた1から計上
# Tは関係ない

N,T = list(map(int,readline().split()))
A = list(map(int,readline().split()))

minval = 10 ** 9 + 1 # そこまでの最小値
maxdiff = 0 # そこまでの差の最大値
ans = 0
for a in A:
  if a < minval:
    minval = a
    continue
  diff = a - minval
  if diff > maxdiff:
    maxdiff = diff
    ans = 1
  elif diff == maxdiff:
    ans += 1

print(ans)
# Original solution
from sys import stdin, stdout
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: list(map(int, stdin.readline().split()))

INF, NINF = float('inf'), float('-inf')

def main():
	MOD = 10**9 + 7
	x = []
	for c in rll()[0]:
		x.append(int(c))
	d = int(rl())
	ans = 0

	dp = [[[0]*2 for j in range(d)] for i in range(len(x)+1)]
	dp[0][0][1] = 1
	for i in range(len(x)):
		for digsum in range(d):
			for tight in range(2):
				for dig in range(x[i]+1 if tight else 10):
					ns = (digsum + dig) % d 
					ntight = 1 if tight and dig == x[i] else 0
					dp[i+1][ns][ntight] += dp[i][digsum][tight]
					dp[i+1][ns][ntight] %= MOD

	ans = (dp[len(x)][0][0] + dp[len(x)][0][1] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

# Optimized solution
from sys import stdin, stdout
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: list(map(int, stdin.readline().split()))

INF, NINF = float('inf'), float('-inf')

def main():
	MOD = 10**9 + 7
	x = []
	for c in rll()[0]:
		x.append(int(c))
	d = int(rl())
	ans = 0

	dp = [[0]*2 for _ in range(d)]
	dp[0][1] = 1
	for i in range(len(x)):
		ndp = [[0]*2 for _ in range(d)]
		for digsum in range(d):
			for tight in range(2):
				for nd in range(x[i]+1 if tight else 10):
					ns = (digsum + nd) % d 
					ntight = 1 if tight and nd == x[i] else 0
					ndp[ns][ntight] += dp[digsum][tight]
					ndp[ns][ntight] %= MOD
		dp = ndp

	ans = (dp[0][0] + dp[0][1] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()
# Original solution


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    _ _ 

    dp[i][j][one_of_previous_number_is_lower] = count of remainder j up to i-th digit, 0 <= j < D

    dp[i][(j+digit)%D][True] += dp[i-1][j][True] + dp[i-1][j][False] digit < K[i]
    dp[i][(j+digit)%D][False] += dp[i-1][j][False]        digit == K[i]
    """
    K = list(map(int, input().strip()))
    D = read_int()
    dp = [[[0, 0] for _ in range(D)]
           for _ in range(len(K)+1)]
    dp[0][0][0] = 1
    modulo = 10**9+7
    for i in range(len(K)):
        for j in range(D):
            for digit in range(10):
                dp[i+1][(j+digit)%D][True] += dp[i][j][True]
                if digit < K[i]:
                    dp[i+1][(j+digit)%D][True] += dp[i][j][False]
                if digit == K[i]:
                    dp[i+1][(j+digit)%D][False] += dp[i][j][False]
                dp[i+1][(j+digit)%D][False] %= modulo
                dp[i+1][(j+digit)%D][True] %= modulo
    return (dp[-1][0][0]+dp[-1][0][1]-1)%modulo


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


# Optimized solution


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    _ _ 

    dp[i][j][one_of_previous_number_is_lower] = count of remainder j up to i-th digit, 0 <= j < D

    dp[i][(j+digit)%D][True] += dp[i-1][j][True] + dp[i-1][j][False] digit < K[i]
    dp[i][(j+digit)%D][False] += dp[i-1][j][False]        digit == K[i]
    """
    K = list(map(int, input().strip()))
    D = read_int()
    dp = [[0, 0] for _ in range(D)]
    dp[0][0] = 1
    modulo = 10**9+7
    for i in range(len(K)):
        new_dp = [[0, 0] for _ in range(D)]
        for j in range(D):
            for digit in range(10):
                new_dp[(j+digit)%D][True] += dp[j][True]
                if digit < K[i]:
                    new_dp[(j+digit)%D][True] += dp[j][False]
                if digit == K[i]:
                    new_dp[(j+digit)%D][False] += dp[j][False]
                new_dp[(j+digit)%D][False] %= modulo
                new_dp[(j+digit)%D][True] %= modulo
        dp = new_dp
    return (dp[0][0]+dp[0][1]-1)%modulo


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