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

s = input()
invs = s[::-1]

MOD = 10 ** 9 + 7
 
dp = [[0]*13 for _ in range(len(s))]

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * 10**order)%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * 10**order)%13 ]  += dp[order-1][j]%MOD
 
print(dp[-1][5]%MOD)

### FIXED CODE ###

s = input()
invs = s[::-1]

MOD = 10 ** 9 + 7
 
dp = [[0]*13 for _ in range(len(s))]

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

mul = 10
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)
### BUGGY CODE ###

import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = list(zip(*xy))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)

### FIXED CODE ###

import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
input = sys.stdin.readline
from collections import defaultdict
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
dcy = defaultdict(int)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yls = list(yls)
for i in range(n):
  dcy[yls[i]] = i
yls.sort()
yind = [0 for i in range(n)]
for i in range(n):
  ind = dcy[yls[i]]
  yind[ind] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)
### BUGGY CODE ###

import time

N, M = [int(i) for i in input().split()]
A = [s for s in input().split()]
numDict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}

def strNumSort(strNum, addStrNum):
    addIntNum = int(addStrNum)
    for i in range(len(strNum)):
        if addIntNum >= int(strNum[i]):
            return int("{0}{1}{2}".format(strNum[:i], addIntNum, strNum[i:]))
    return int(strNum + addStrNum)

start = time.time()

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

for i in range(N + 1):
    for strNum in A:
        if i - numDict[strNum] == 0:
            dp[i] = max(dp[i], int(strNum))
            continue
        if i - numDict[strNum] > 0 and dp[i - numDict[strNum]] != 0:
            dp[i] = max(dp[i], strNumSort(str(dp[i - numDict[strNum]]), strNum))

print(dp[N])

#elapsed_time = time.time() - start
#print(elapsed_time)


### FIXED CODE ###

N, M = [int(i) for i in input().split()]
A = sorted([s for s in input().split()], reverse=True)
numDict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}
dp = ["" for _ in range(N + 1)]

for i in range(N + 1):
    for strNum in A:
        if i - numDict[strNum] < 0:
            continue
        if i - numDict[strNum] == 0 and dp[i] == "":
            dp[i] = strNum
        preStrNum = dp[i - numDict[strNum]]
        if preStrNum != "":
            if len(preStrNum) + 1 > len(dp[i]):
                dp[i] = preStrNum + strNum

print("".join(sorted(dp[N], reverse=True)))
### BUGGY CODE ###

# 明らかにdp、あるマスに乗っているときそれまでの履歴とかが全く意味をなさないから
# dp[i]: マス目iにいるときのそこまでの移動方法の合計
# dp[i+1] = dp[i]
# 最悪N*K掛かりそうな気がするけどnumpyなら早いんかなぁ？だとしたら簡単すぎる問題な気もするけど。。。？

N,K = map(int,input().split())
L = 998244353
LR = [0] * K
for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]
import numpy as np
dp = np.array([0] * (N+1))

dp[1] = 1
for i in range(1,N+1):
    for l,r in LR:
        dp[i+l:i+r+1] += dp[i]
        dp[i+l:i+r+1] %= L

print(dp[N])





### FIXED CODE ###

N,K = map(int,input().split())
L = 998244353
LR = [0] * K
# 累積和をとっていく。累積和の表を予め作っておき、どんどん足しておく
for i in range(K):
    l,r = map(int,input().split())
    LR[i] = [l,r]

AS = [0] * (N+2)
#for l,r in LR:
#    AS[l] += 1
#    AS[r+1] -= 1

A = [0] * (N+2)
A[1] = 1
A[2] = -1
for i in range(1,N+1):
    AS[i] = (AS[i-1] + A[i])%L
    rest = AS[i]
    for l,r in LR:
        if i+l>N:
            continue
        right = min(N+1,i+r+1)
        A[i+l] += rest
        A[right] += -rest

print(sum(A[1:N+1])%L)
### BUGGY CODE ###

s = input()
counter = 0
for i in range(3, len(s)+1):
    snum = 0
    for m in range(i):
        snum += int(s[m])
    num = int(s[0:i])
    if num % 2019 == 0:
        counter += 1
    for j in range(1, len(s)-i+1):
        snum -= int(s[j-1])
        snum += int(s[j+i-1])
        if snum % 3 != 0:
            continue
        num = int(s[j:j + i])
        if num % 673 == 0:
            counter += 1
print(counter)


### FIXED CODE ###

import collections


def comb(n):
    return n * (n-1)/2


s = input()
ans = 0
lst_mod = [0]*2019  # O(N)で回した連続値のmod(2019)の値
lst_mod[0] += 1
num, dim = 0, 1
for char in reversed(s):
    num += int(char)*dim
    num %= 2019
    dim *= 10
    dim %= 2019  # サイズを大きくしたくないからmod(2019)を使う
    lst_mod[num] += 1

for mod in lst_mod:
    ans += comb(mod)
print(int(ans))
### BUGGY CODE ###

def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = [[[0, 0] for i in range(LT + 1)] for j in range(LS + 1)]
  
  for i in range(LS):
    for j in range(LT):
      a = DP[i+1][j][0]
      b = DP[i][j+1][0]
      if s[i] == t[j]:
        c = DP[i][j][0] + 1
        if max(a, b, c) == c:
          DP[i+1][j+1] = [c, 3]
        elif max(a, b) == b:
          DP[i+1][j+1] = [b, 2]
        else:
          DP[i+1][j+1] = [a, 1]
      else:
        if max(a, b) == b:
          DP[i+1][j+1] = [b, 2]
        else:
          DP[i+1][j+1] = [a, 1]
        
  Ans = ""
  j = LS
  k = LT
  for i in range(DP[j][k][0], 0, -1):
    while True:
      if DP[j][k][1] == 3:
        Ans += t[k-1]
        j -= 1
        k -= 1
        break
      elif DP[j][k][1] == 2:
        j -= 1
      else:
        k -= 1
  print(Ans[::-1])
main()


### FIXED CODE ###

def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = [[0 for i in range(LT + 1)] for j in range(LS + 1)]
  L = [[0 for i in range(LT)] for j in range(LS)]
  for i in range(LS):
    for j in range(LT):
      a = DP[i+1][j]
      b = DP[i][j+1]
      if max(a, b) == a:
        DP[i+1][j+1] = a
        L[i][j] = 1
      else:
        DP[i+1][j+1] = b
        L[i][j] = 2
        a = b
      if s[i] == t[j]:
        c = DP[i][j] + 1
        if max(a, c) == c:
          DP[i+1][j+1] = c
          L[i][j] = 3       
        
  Ans = ""
  j = LS - 1
  k = LT - 1
  x = DP[LS][LT]
  for i in range(x, 0, -1):
    while True:
      if L[j][k] == 3:
        Ans += t[k]
        j -= 1
        k -= 1
        break
      elif L[j][k] == 2:
        j -= 1
      else:
        k -= 1
  print(Ans[::-1])
main()
### BUGGY CODE ###

n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
ans=0
for i in range(1<<q):
  A=[1]*n
  arrj=[]
  sumd=0
  hantei=True
  for j in range(q):
    if ((i>>j)&1):
      a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
      if A[a-1]!=1 and A[b-1]!=1:
        if A[b-1]-A[a-1]!=c:
          hantei=False
          break
      elif A[a-1]==1 and A[b-1]!=1:
        A[a-1]=A[b-1]-c
        if A[a-1]<1:
          hantei=False
          break
      else:
        A[b-1]=A[a-1]+c
        if A[b-1]>m:
          hantei=False
          break
      sumd+=d
      arrj.append(j)
  if hantei:
    for j in arrj:
      a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
      if A[b-1]-A[a-1]!=c:
        hantei=False
        break
  if hantei:
    for j in range(n-1):
      if A[j]>A[j+1]:
        hantei=False
        break
  if hantei and sumd>ans:
    ans=sumd
print(ans)

### FIXED CODE ###

n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
ans=0

def calc(arr):
  score=0
  for a,b,c,d in abcd:
    if arr[b-1]-arr[a-1]==c:
      score+=d
  return score

def dfs(arr, i):
  global ans
  if len(arr)==n:
    ans=max(ans,calc(arr))
    return
  for j in range(i,m+1):
    arr.append(j)
    dfs(arr, j)
    arr.pop()
dfs([], 1)
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush

N, Q = map(int, input().split())

event = []
for _ in range(N) :
    s, t, x = map(int, input().split())
    event.append([s - x, t - x, x])

D = [int(input()) for _ in range(Q)]

event.sort()

closed = []
ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while closed and closed[0][1] <= d :
        heappop(closed)
    
    if closed :
        print(closed[0][0])
    else :
        print(-1)

### FIXED CODE ###

import sys, heapq
input = sys.stdin.readline

N, Q = map(int, input().split())

event = []
for _ in range(N) :
    s, t, x = map(int, input().split())
    event.append([s - x, t - x, x])

D = [int(input()) for _ in range(Q)]

event.sort()

closed = []
ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heapq.heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while closed and closed[0][1] <= d :
        heapq.heappop(closed)
    
    if closed :
        print(closed[0][0])
    else :
        print(-1)
### BUGGY CODE ###

mod1,mod2=10**9+7,998244353
mod=mod2
n,s=map(int,input().split())
dp=[0]*(s+1)
dp[0]=1
for a in map(int,input().split()):
    for i in range(s,a-1,-1):
        dp[i]=(dp[i]*2%mod+dp[i-a])%mod
    for i in range(min(s,a-1),-1,-1):
        dp[i]=2*dp[i]%mod
        
print(dp[-1])


### FIXED CODE ###

n,s=map(int,input().split())
dp=[0]*(s+1)
dp[0]=1
ne=[0]*(s+1)
mod=998244353
for i in list(map(int,input().split())):

    for k in range(0,s+1):
        if k+i<=s:
            ne[k+i]=(ne[k+i]+dp[k])%mod
        ne[k]=(ne[k]+2*dp[k])%mod
        dp[k]=0
    dp,ne=ne,dp
print(dp[-1])
### BUGGY CODE ###

N, K = map(int, input().split())

list0 = []
list1 = []
set1 = set()

td = []
for i in range(N):
    t, d = map(int, input().split())
    td.append((t, d))

td.sort(key=lambda x: (x[0], -x[1]))

for t, d in td:
    if t in set1:
        list0.append(d)
    else:
        set1.add(t)
        list1.append(d)

list0.sort(reverse=True)
list1.sort(reverse=True)

various = min(K, len(list1))
selected0 = []
selected1 = []
for i in range(various):
    selected1.append(list1.pop(0))
if K > various:
    for i in range(K - various):
        selected0.append(list0.pop(0))


ans = sum(selected0) + sum(selected1) + various ** 2

while list0 and list0[0] > selected1[-1]:
    selected1.pop(-1)
    selected0.append(list0.pop(0))
    various -= 1
    tmp = sum(selected0) + sum(selected1) + various ** 2
    if tmp <= ans:
        break
    ans = tmp

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())

list0 = []
list1 = []
set1 = set()

td = []
for i in range(N):
    t, d = map(int, input().split())
    td.append((t, d))

td.sort(key=lambda x: (x[0], -x[1]))

for t, d in td:
    if t in set1:
        list0.append(d)
    else:
        set1.add(t)
        list1.append(d)

list0.sort(reverse=True)
list1.sort(reverse=True)

various = min(K, len(list1))
selected0 = []
selected1 = []
for i in range(various):
    selected1.append(list1.pop(0))
if K > various:
    for i in range(K - various):
        selected0.append(list0.pop(0))


ans = sum(selected0) + sum(selected1) + various ** 2

mn = selected1[-1]
sum0 = sum(selected0)
sum1 = sum(selected1)
while list0 and list0[0] > mn:
    sum0 += list0.pop(0)
    sum1 -= selected1.pop(-1)
    various -= 1
    tmp = sum0 + sum1 + various ** 2
    if tmp <= ans:
        break
    ans = tmp

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

n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True]*(a[n-1])
for val in set(a):
    temp=2
    while val*temp<=a[n-1]:
        dp[val*temp-1]=False
        temp+=1
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
dp=[True]*a[-1]
def hantei(i):
    ans = True
    if i!=n-1:
        if a[i]==a[i+1]: ans = False
    if i!=0:
        if a[i]==a[i-1]: ans=False
    return ans
for val in set(a):
    for i in range(2*val,a[-1]+1,val): dp[i-1]=False
ans=0
for i in range(n):
    if dp[a[i]-1] and hantei(i)==1: ans+=1
print(ans)
### BUGGY CODE ###

import itertools

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

RGB = {"R":[0]*N, "G":[0]*N, "B":[0]*N}
for i in range(N):
    if S[i] == "R":
        RGB["R"][i] = 1
    elif S[i] == "G":
        RGB["G"][i] = 1
    else:
        RGB["B"][i] = 1

for k in RGB.keys():
    RGB[k] = list(itertools.accumulate(RGB[k]))

ans = 0
for i in range(N-2):
    l_i = S[i]
    for j in range(i+1, N-1):
        l_j = S[j]
        d = {"R", "G", "B"}
        if l_i != l_j:
            d.remove(l_i)
            d.remove(l_j)
            l_k = d.pop()
            ans += RGB[l_k][N-1] - RGB[l_k][j]
            if j*2 - i <= N-1:
                if S[j*2 - i] == l_k:
                    ans -= 1

print(ans)




### FIXED CODE ###

import itertools

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

RGB = {"R":[0]*N, "G":[0]*N, "B":[0]*N}
for i in range(N):
    if S[i] == "R":
        RGB["R"][i] = 1
    elif S[i] == "G":
        RGB["G"][i] = 1
    else:
        RGB["B"][i] = 1

for k in RGB.keys():
    RGB[k] = list(itertools.accumulate(RGB[k]))

ans = 0
for i in range(N-2):
    l_i = S[i]
    for j in range(i+1, N-1):
        l_j = S[j]
        d = {"R", "G", "B"}
        if l_i != l_j:
            d.remove(l_i)
            d.remove(l_j)
            l_k = d.pop()
            ans += RGB[l_k][N-1] - RGB[l_k][j]
            if j*2 - i <= N-1:
                if S[j*2 - i] == l_k:
                    ans -= 1

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

from collections import deque
n=int(input())
edge=list(set(map(int,input().split())) for _ in range(n-1))
color=[0]*(n-1)
d=deque()


s=1
d.append(s)
while d:
  c=1
  s=d.popleft()
  check=set()
  seen=set()
  for i in range(n-1):
    if s in edge[i] :
      for k in edge[i]:
        if k!=s:
          e=k
      if color[i]==0:
        d.append(e)
        check.add(i)
      else:
        seen.add(color[i])
  for j in check:
    if c not in seen:
      color[j]=c
      c+=1
    else:
      while c in seen:
        c+=1
      color[j]=c
      c+=1
print(int(max(color)))
print(" ".join(list(map(lambda x: str(int(x)), color))))        
    


### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
k=0
used=[-1]*n
seen=[-1]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
    k=max(k,len(node[pair[0]]),len(node[pair[1]]))
print(k)
ans={}
d=deque()
d.append(0)
while d:
    i=d.pop()
    seen[i]=1
    res=1
    for j in node[i]:
        if seen[j]==1:
            continue
        d.appendleft(j)
        if res!=used[i]:
            ans[(i,j)]=res
        else:
            res+=1
            ans[(i,j)]=res
        used[j]=res
        res+=1
for pair in v:
    a,b=pair
    if (a,b) in ans:
        print(ans[(a,b)])
    else:
        print(ans[(b,a)])
### BUGGY CODE ###

h,w = map(int,input().split())
L = []
for i in range(h):
  L.append(list(input()))
B = []
W = []
for i in range(h):
  for j in range(w):
    if L[i][j] == '.':
      W.append([i,j])
    else:
      B.append([i,j])
anslist = []
for i in range(len(W)):
  ans = float('inf')
  for j in range(len(B)):
    if ans >= abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1]):
      ans = abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1])
  anslist.append(ans)
if len(anslist) != 0:
  print(max(anslist))
else:
  print(0)

### FIXED CODE ###

import collections
h,w = map(int,input().split())
q = collections.deque()
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        if s[j] == '.':
            L.append(s[j])
        else:
            L.append(0)
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = A[cur[0]][cur[1]]+1
                q.append([y,x])
ans = 0
for i in range(h):
    for j in range(w):
        if ans < A[i][j]:
            ans = A[i][j]
print(ans)
### BUGGY CODE ###

import itertools
def aCb(a,b):return len(list(itertools.combinations([0]*a,b)))
def ex(X):
  b=X[:]
  b.append("null")
  a=[]
  for i in range(len(X)):
    if b[i]!=b[i+1]:a.append(b[i])
  return a
n,a=int(input()),list(map(int,input().split()));b=[0]
for i in a:b.append(b[-1]+i)
b.sort();d=ex(b);c=0;ans=0
for i in d:
  x=b.count(i)
  if x>=2:ans+=aCb(x,2)
print(ans)

### FIXED CODE ###

n,a=int(input()),list(map(int,input().split()));b=[0]
for i in range(n):b.append(b[i]+a[i])
b.sort();c=1;ans=0
for i in range(n):
  if b[i]==b[i+1]:c+=1
  else:
    if c>=2:ans+=(c*(c-1))//2
    c=1
if c>=2:ans+=(c*(c-1))//2
print(ans)
### BUGGY CODE ###

n=input()
m=0
MOD = 10 ** 9 + 7
from itertools import combinations
b=combinations
a=b(map(int,input().split()),2)
for i,j in a:
    k=i*j
    m+=k%MOD
    m%=MOD
print(m)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
MOD = 10 ** 9 + 7

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

ans = 0
for i in range(N):
    ans += (A[i] * (cumsum[-1] - cumsum[i])) % MOD
    ans %= MOD

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

N = int(input())
L = [int(i) for i in input().split()]

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i] < L[j] + L[k] and L[j] < L[i] + L[k] and L[k] < L[i] + L[j]:
                ans += 1
print(ans)

### FIXED CODE ###

import collections

N = int(input())
L = [int(i) for i in input().split()]
M = max(L)
c = collections.Counter(L)
li = [c[i] for i in range(M+1)]

ans = 0
for i in range(1,M+1):
    for j in range(i,M+1):
        if i == j:
            ans += int(li[i] * (li[i] - 1) * (li[i] - 2) / 6)
            ans += int(sum(li[j+1:min(M+1, i+j)]) * li[i] * (li[i] - 1) / 2)
        else:
            ans += int(li[i] * li[j] * (li[j] - 1) / 2)
            ans += li[i] * li[j] * sum(li[j+1:min(M+1, i+j)])
print(int(ans))
### BUGGY CODE ###

from bisect import *

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    ans = 0
    pos = [0] * n
    for i, a in enumerate(aa):
        pos[a - 1] = i
    #print(pos)
    fin = [-1, -1, n, n]
    for a in range(n - 1, -1, -1):
        i = pos[a]
        j = bisect_left(fin, i)
        fin.insert(j, i)
        ans += (a + 1) * ((fin[j - 1] - fin[j - 2]) * (fin[j + 1] - fin[j])
                          + (fin[j] - fin[j - 1]) * (fin[j + 2] - fin[j + 1]))
        # print(a, ans, fin)
    print(ans)

main()


### FIXED CODE ###

# 参考 https://atcoder.jp/contests/abc140/submissions/7411285
import sys
input = sys.stdin.readline

def main():
    n = int(input()[:-1])
    aa = list(map(int, input().split()))
    ans = 0
    pos = [0] * (n + 1)
    for i, a in enumerate(aa):
        pos[a] = i + 2
    Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
    Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
    for a in range(1,n + 1):
        i = pos[a]
        l0 = Lnext[i]
        l1 = Lnext[l0]
        r0 = Rnext[i]
        r1 = Rnext[r0]
        ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
        Lnext[r0] = l0
        Rnext[l0] = r0
    print(ans)

main()
### BUGGY CODE ###

import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
    for i in range(len(b)):
        counter= 0
        for num2 in range(b[i]//2+1):
            counter += math.factorial(num2+(b[i]-2*num2))//math.factorial(num2)//math.factorial(b[i]-2*num2)
    c.append(counter%1000000007)
ans = 1
for i in range(len(c)):
    ans *= c[i]
print(ans%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
a = [ int(input()) for _ in range(m)]
M=10**9+7
lis = [1] + [0]*n

for i in a:
  lis[i]=-1
lis[1] += 1
for i in range(n-1):
  if lis[i+2]<0:
    lis[i+2]= 0
  else:
    lis[i+2] = (lis[i+1] + lis[i])%M
print(lis[n])
### BUGGY CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


n,m=mdata()
dp=[0]*n
g=[set() for i in range(n)]
par=[i for i in range(n)]
for i in range(m):
    x,y=mdata()
    g[x-1].add(y-1)
for i in range(n):
    if par[i]==i:
        s1=set()
        s1.add(i)
        while s1:
            s2=set()
            for i in s1:
                for j in g[i]:
                    s2.add(j)
                    dp[j]=max(dp[j],dp[i]+1)
            s1=s2.copy()
print(max(dp))





### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


n,m=mdata()
dp=[0]*n
g=[set() for i in range(n)]
par=[i for i in range(n)]
chl=[0]*n
for i in range(m):
    x,y=mdata()
    g[x-1].add(y-1)
    chl[y-1]=1
vis=[0]*n
for i in range(n):
    if chl[i]==0:
        s1=deque()
        s1.append(i)
        while s1:
            a=s1[-1]
            if vis[a]==1:
                if a!=i:
                    dp[par[a]]=max(dp[par[a]],dp[a]+1)
                s1.pop()
                continue
            vis[a]=1
            for j in g[a]:
                if vis[j]==0:
                    s1.append(j)
                    par[j]=a
                else:
                    dp[a]=max(dp[a],dp[j]+1)
print(max(dp))