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

s = input()[::-1]
MOD = 10**9 + 7

dp = [[0] * 13 for _ in range(len(s))]

for i, x in enumerate(s):
    # 1, 10, 100, 1000...の剰余を順に計算し、各桁までの剰余を計算
    if i == 0:
        tmp = 1
    else:
        tmp = tmp * 10 % 13
    if x != "?":
        move = int(x) * tmp
        if i == 0:
            dp[i][move] = 1
        else:
            for j in range(13):
                dp[i][j] += dp[i - 1][(j - move + 13) % 13]
                dp[i][j] %= MOD
    else:
        for coef in range(10):
            move = coef * tmp
            if i == 0:
                dp[i][move] = 1
            else:
                for j in range(13):
                    dp[i][j] += dp[i - 1][(j - move + 13) % 13]
                    dp[i][j] %= MOD

print(dp[-1][5])

### FIXED CODE ###

s = input()[::-1]
MOD = 10**9 + 7

dp = [[0] * 13 for _ in range(len(s))]

for i, x in enumerate(s):
    # 1, 10, 100, 1000...の剰余を順に計算し、各桁までの剰余を計算
    if i == 0:
        tmp = 1
    else:
        tmp = tmp * 10 % 13
    if x != "?":
        move = int(x) * tmp
        if i == 0:
            dp[i][move] = 1
        else:
            for j in range(13):
                dp[i][j] += dp[i - 1][(j - move + 13) % 13]
                dp[i][j] %= MOD
    else:
        for coef in range(10):
            move = coef * tmp
            if i == 0:
                dp[i][move] = 1
            else:
                for j in range(13):
                    dp[i][j] += dp[i - 1][(j - move + 13) % 13]
                    dp[i][j] %= MOD

print(dp[-1][5])
### BUGGY CODE ###

N, M = map(int, input().split())
lst1 = []
lst2 = []

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        lst1.append(b)
    if b == N:
        lst2.append(a)

for x in lst1:
    if lst2.count(x) >= 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, input().split())
s1 = set()
s2 = set()

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        s1.add(b)
    if b == N:
        s2.add(a)

if len(s1.intersection(s2)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

def main():
    # 入力
    n = int(input())

    min_l = 10

    # ccc = 0
    for i in range(1, n+1):
        # ccc += 1
        if n % i != 0:
            continue
        il = len(str(i))
        if il > min_l:
            break
        j = int(n / i)

        jl = len(str(j))
        f = max(il, jl)
        if f < min_l:
            min_l = f
        if il == jl or il > jl:
            break


    # print(ccc)
    print(min_l)


main()


### FIXED CODE ###

def main():
    # 入力
    s = input()

    x = len(s)
    limit = int(x/2)+1 if x % 2 == 0 else int(x/2)+2
    limit2 = int(x/2) if x % 2 == 0 else int(x/2)+1

    n = int(s)

    min_l = 11

    # ccc = 0
    for i in range(1, n+1):
        # ccc += 1
        il = len(str(i))
        if il == limit:
            break
        if n % i != 0:
            continue
        if il == min_l:
            break
        j = int(n / i)

        jl = len(str(j))
        f = max(il, jl)
        if f < min_l:
            min_l = f
        if jl == limit2 or il == jl or il > jl:
            break


    # print(ccc)
    print(min_l)


main()
### BUGGY CODE ###

import collections

N = int(input())
l = [s for s in input().split()]

c = collections.Counter(l)
hoge = list(c.values())

for i in l:
    ans = 0
    for ix,k in enumerate(c):# key
        
        if int(k) == int(i) and hoge[ix]-1 >= 2:
            tmp = hoge[ix] - 1
            ans += (tmp * (tmp-1)) / 2
            
        elif int(k) != int(i) and hoge[ix] >= 2:
            tmp = hoge[ix]
            ans += (tmp * (tmp-1)) / 2
            
        else:
            pass
    print(int(ans))

### FIXED CODE ###

import collections

N = int(input())
l = [s for s in input().split()]

c = collections.Counter(l)
ans_dict = {}

hoge = list(c.values())
full_fuga = [(i*(i-1))/2 if i >= 2 else 0 for i in hoge]
full_ans = sum(full_fuga)

for i in l:
    v = c[str(i)]
    if v < 2:
        print(int(full_ans))
    elif v == 2:
        print(int(full_ans - 1))
    elif v > 2:
        print(int(full_ans - ((v*(v-1))/2) + (((v-1) *(v-2))/2)))
### BUGGY CODE ###



n,k = map(int,input().split())
a = [0 for _ in range(n)]
b = [0 for _ in range(n)]
c = [[] for _ in range(n)]

for i in range(n - 1):
	A,B = map(int,input().split())
	a[i] = A
	b[i] = B
	c[A - 1].append(B - 1)
	c[B - 1].append(A - 1)

pat = k
pat_arr = [0 for _ in range(n)]
pat_arr[0] = k
queue = [0]



while(queue):
	pos = queue.pop(0)
	num = k-2
	if(pos == 0):num += 1
	
	for i in c[pos]:
		if(pat_arr[i] != 0):continue
		queue.append(i)
		pat_arr[i] = num
		pat *= num
		pat %= 1000000007
		num -= 1
		
		
print(pat % 1000000007)


### FIXED CODE ###

n,k = map(int,input().split())
#a = [0 for _ in range(n)]
#b = [0 for _ in range(n)]
c = [[] for _ in range(n)]

for i in range(n - 1):
	A,B = map(int,input().split())
	#a[i] = A
	#b[i] = B
	c[A - 1].append(B - 1)
	c[B - 1].append(A - 1)

pat = k
pat_arr = [0 for _ in range(n)]
pat_arr[0] = k
queue = [0]



while(queue):
	pos = queue.pop(0)
	num = k-2
	if(pos == 0):num += 1
	
	for i in c[pos]:
		if(pat_arr[i] != 0):continue
		queue.append(i)
		pat_arr[i] = num
		pat *= num
		pat %= 1000000007
		num -= 1
		
		
print(pat % 1000000007)
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[N,M,R]=i2()
r=i2()
f=2**20
d=[[f for j in range(N)]for i in range(N)]
for i in range(N):d[i][i]=0
for i in range(M):
    a=i2()
    d[a[0]-1][a[1]-1]=a[2]
    d[a[1]-1][a[0]-1]=a[2]
for i in range(N):
    for j in range(N):
        for k in range(N):
            d[j][k]=min(d[j][k],d[j][i]+d[i][k])
a=[]
c=2**20
dd=[[f for j in range(N)]for i in range(N)]
for i in r:
    for j in r:
        if i<j:
            dd[i-1][j-1]=d[i-1][j-1]
            dd[j-1][i-1]=d[i-1][j-1]
import itertools
for i in list(itertools.permutations(r)):
    ddd=0
    for j in range(len(i)-1):
       ddd+=dd[i[j]-1][i[j+1]-1]
    c=min(c,ddd)
print(c)

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[N,M,R]=i2()
r=i2()
f=float("inf")
d=[[f for j in range(N)]for i in range(N)]
for i in range(N):d[i][i]=0
for i in range(M):
    a=i2()
    d[a[0]-1][a[1]-1]=a[2]
    d[a[1]-1][a[0]-1]=a[2]
for i in range(N):
    for j in range(N):
        for k in range(N):
            d[j][k]=min(d[j][k],d[j][i]+d[i][k])
c=float("inf")

import itertools
for i in list(itertools.permutations(r)):
    ddd=0
    for j in range(len(i)-1):
       ddd+=d[i[j]-1][i[j+1]-1]
    c=min(c,ddd)

print(c)
### BUGGY CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
A = ints()

w = 1000000007

s = 0
for k in range(60):
  n = [0, 0]
  for i in range(N):
    n[A[i]%2] += 1
    A[i] //= 2

  s += (n[0]*n[1] << k) % w

print(s%w)


### FIXED CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
A = ints()

w = 1000000007

s = 0
for k in range(60):
  n = [0, 0]
  for i in range(N):
    n[A[i]%2] += 1
    A[i] >>= 1

  s += (n[0]*n[1] << k) % w

print(s%w)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    DI = [(int(input()), i) for i in range(Q)]
    DI.sort(key=itemgetter(0))
    D = [0] * Q
    revD = [0] * Q
    for i in range(Q):
        D[i], revD[i] = DI[i]
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        for i in range(l, r):
            idx = revD[i]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


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

from itertools import combinations, product
n=int(input())
s=[["a" for _ in range(n)] for _ in range(n)]
for i in range(n):
  s[i]=list(input())

res=0
for a,b in product(range(n),range(n)):
  for i,j in combinations(range(n),2):
    if(s[(i+a)%n][(j+b)%n]!=s[(j+a)%n][(i+b)%n]):
      break
  else:
    res+=1

print(res)


### FIXED CODE ###

from itertools import combinations, product
n=int(input())
s=[["a" for _ in range(n)] for _ in range(n)]
for i in range(n):
  s[i]=list(input())

res=0
for a in range(n):
  for i,j in combinations(range(n),2):
    if(s[(i+a)%n][j%n]!=s[(j+a)%n][i%n]):
      break
  else:
    res+=1

print(res*n)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [ai + bi for bi in b[:k] for ai in a[:k]]
ab.sort(reverse=True)

s = [ci + abi for abi in ab[:k] for ci in c[:k]]
s.sort(reverse=True)

for si in s[:k]:
    print(si)

### FIXED CODE ###

import sys
input = sys.stdin.readline

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [ai + bi for bi in b[:k] for ai in a[:k]]
ab.sort(reverse=True)

s = [ci + abi for abi in ab[:k] for ci in c[:k]]
s.sort(reverse=True)

for si in s[:k]:
    print(si)
### BUGGY CODE ###

n, m = [int(x) for x in input().split()]
g = [[]*n for _ in range(n)]
visited = set()
for _ in range(m):
    x, y = [int(x) for x in input().split()]
    g[x - 1].append(y - 1)
dp = [0] * n
from collections import deque
def dfs(u):
    queue = deque([u])
    d = [None]*n
    max_d = 0
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                max_d = max(max_d, d[i])
                queue.append(i)
                visited.add(i)
            elif d[v] + 1 >= d[i]:
                d[i] = max(d[i], d[v] + 1)
                max_d = max(max_d, d[i])
                queue.append(i)
    return max_d

for i in range(n):
    if i in visited:
        continue
    dp[i] = dfs(i)

print(max(dp))




### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
    x, y = [int(x) for x in input().split()]
    g[x - 1].append(y - 1)
from functools import lru_cache
sys.setrecursionlimit(10**7)
@lru_cache(maxsize=None)
def dp(v):
    res = 0
    for u in g[v]:
        res = max(res, dp(u) + 1)
    return res
ans = -1
for i in range(n):
    ans = max(ans, dp(i))
print(ans)
### BUGGY CODE ###

n = int(input())
pow = 1
for i in range(n):
  pow *= i+1
print(pow%(10**9+7))

### FIXED CODE ###

n = int(input())
pow = 1
for i in range(n):
  pow *= i+1
  pow = pow%(10**9+7)
print(pow)
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
 
def how_two(n):
    a = 0
    while n %2 ==0:
        a+=1
        n//=2
    return a
 
log2 = how_two(A[0])
for i in A:
    tmplog2 = how_two(i)
    if log2!=tmplog2:
        log2 =0
        break
        
        
if log2==0:
    print(0)
else:
    def p_prime(n): 
        prime = [2]
        for i in range(3,n+1):
            flag = 0
            for j in prime:
                if i%j == 0:
                    flag = 1
                    break
                if i**0.5 < j:
                    break
            if flag == 0:
                prime.append(i)
        return prime
 
    mod = 10**9+7
    prime = p_prime(int(mod**0.5+1))
    def soinsuu(M):
        a = {}
        for p in prime:
            count = 0
            while M%p ==0:
                count += 1
                M //= p
            if count > 0:
                a[p] = count
        if M != 1:
            a[M] = 1
        return a
 
    def LCM(A):
        from collections import defaultdict
        AA = defaultdict(int)
    
        for i in range(len(A)):
            tmp = soinsuu(A[i])
            for j in tmp:
                AA[j] = max(AA[j], tmp[j])
                
        L = 1
        for i in AA:
            L *= pow(i,AA[i])
        return L
 
    B = []
    twotwo = pow(2,log2)
    for i in A:
        B.append(i//twotwo)
    l = LCM(B)
    l *= pow(2,log2-1)
    ans =(M+l)//(2*l)
    
    print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
AA = max(A)
 
def how_two(n):
    a = 0
    while n %2 ==0:
        a+=1
        n//=2
    return a
 
log2 = how_two(A[0])
for i in A:
    tmplog2 = how_two(i)
    if log2!=tmplog2:
        log2 =0
        break
        
        
if log2==0:
    print(0)
else:
    from fractions import gcd
    l = 1
    dame = 0
    for i in A:
        l = (l*i)//gcd(l,i)
        if l//2 >= 10**9:
            dame = 1
            break
    l //= 2
    
    MAX = (M+l)//(2*l)
    MIN = max(1,-(-(AA+2*l)//(4*l)))
    ans = MAX-MIN +1
    #print(MIN)
    
    if dame==1:
        print(0)
    else:
        print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())

ans = 2019
for i in range(L,R):
    for j in range(i+1,R+1) :
        pro = (i*j) %2019
        ans = min(ans,pro)
        if ans == 0 :
            break

print(ans)

### FIXED CODE ###

import sys

L,R = map(int,input().split())

ans = 2019
for i in range(L,R):
    for j in range(i+1,R+1) :
        pro = (i*j) %2019
        ans = min(ans,pro)
        if ans == 0 :
            print(0)
            sys.exit()

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

n = int(input())

dams = list(map(int, input().split()))

ans = sum([dams[x]*(-1)**x for x in range(n)])
out = str(ans)

for i in range(1, n):
  ans = -1 * ans + 2 * dams[i - 1]
  out += " " + str(ans)
  
print(out)
  

### FIXED CODE ###

n = int(input())

dams = list(map(int, input().split()))
ans_list = [0 for x in range(n)]

ans_list[0] = sum([dams[x]*(-1)**x for x in range(n)])

for i in range(1, n):
  ans_list[i] = -ans_list[i-1] + 2 * dams[i - 1]

print(" ".join(list(map(str, ans_list))))

#print(*ans_list)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split( )))
ans = 0
mod = 10**9+7
Bit = [[0]*2 for j in range(60)]# for i in range(n+1)

for i in range(1,n):##1から
    for j in range(60):
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j][0] += 1
        else:#ｊビット目1
            Bit[j][1] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j][0]<<j
            ans %=mod
        else:
            ans += Bit[j][1]<<j
            ans %= mod
    #print(Bit[:6])
"""
for i in range(1,n):##1から
    for j in range(60):

    #ans += a[i]
    #ans %=mod
    #自身の分
        #print(ans)
"""
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split( )))
ans = 0
mod = 10**9+7
Bit = [0 for j in range(60)]# for i in range(n+1)
for j in range(60):#ループ交換
    for i in range(1,n):##1から
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j]<<j
            ans %=mod
        else:
            ans += (i-Bit[j])<<j
            ans %= mod
    
print(ans)
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10**100
N, M = map(int, input().split())
G = [[]for i in range(N)]
for i in range(1, N):
    G[i].append([i-1, 0])

for i in range(M):
    L, R, C = map(int, input().split())
    G[L-1].append([R-1, C])

S = 0

def dijkstra(N, S):
    d = [INF for i in range(N)]

    que = []
    d[S] = 0
    heapq.heappush(que, [0, S])

    while not(len(que) == 0):
        q = heapq.heappop(que)
        ver = q[1] # ノード
        dis = q[0] # 過去に更新された最短距離

        # vまで2番目に短い距離（最新）　＜　過去最短距離　の時、
        # キューから取り出した過去のものを無視する
        if d[ver] < dis:
            continue

        # 隣接リストに対してループ
        for i in range(len(G[ver])):
            e = G[ver][i]
            if d[e[0]] > d[ver] + e[1]:
                d[e[0]] = d[ver] + e[1]
                heapq.heappush(que, [d[e[0]], e[0]])

    return d[N-1]

ans = dijkstra(N, S)
if ans == INF:
    print(-1)
else:
    print(dijkstra(N, S))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
E = []
for i in range(M):
    L, R, C = map(int, input().split())
    E.append([L-1, R-1, C])

E = sorted(E, key=lambda X: X[1])

# N_はN以上の2べき数
N_ = 2**(len(bin(N))-2)
INF = 10**15 # 10**10 
seg = [INF] * (2*N_-1)

# k番目(0index)をaに更新
def update(k, a):
    k += N_-1
    seg[k] = a

    while k > 0:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1], seg[k*2+2])

# 開区間！！！[a, b)の最小値を求める
def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INF
    if a <= l and r <= b:
        return seg[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return min(vl, vr)



# 初期化
update(0, 0)

for i in range(M):
    new = query(E[i][0], E[i][1], 0, 0, N_) + E[i][2]
    if new < seg[E[i][1] + N_-1]:
        update(E[i][1], new)

if seg[N-1+N_-1] == INF:
    print(-1)
else:
    print(seg[N-1+N_-1])
### BUGGY CODE ###

import math

n,k = list(map(int, input().split(" ")))
nums  = list(map(int, input().split(" ")))
nums.sort()

mod = 10**9 + 7
f = [1]
for i in range(1,10**5+1):
    f.append(f[-1] * i)

def nCr(n,r):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

minSum = 0
maxSum = 0

for i in range(n-k+1):
    minSum += nums[i] * nCr(n-1-i, k-1)
    maxSum += nums[-i-1] * nCr(n-1-i,k-1)

print((maxSum - minSum + mod) % mod)

### FIXED CODE ###

import math

n,k = list(map(int, input().split(" ")))
nums  = list(map(int, input().split(" ")))
nums.sort()

mod = 10**9 + 7
f = [1]
for i in range(1,10**5+1):
    f.append(f[-1] * i % mod)

def nCr(n,r):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

minSum = 0
maxSum = 0

for i in range(n-k+1):
    minSum += nums[i] * nCr(n-1-i, k-1)
    maxSum += nums[-i-1] * nCr(n-1-i,k-1)

print((maxSum - minSum + mod) % mod)
### BUGGY CODE ###

s = input()
num = int(input())
t = "X"
reverse = False

for _ in range(num):
    row = input().split()
    if len(row) == 1:
        if reverse == False:
            reverse = True
        else:
            reverse = False
    else:
        x = row[1]
        y = row[2]
        if x == "1" and reverse:
            t += y
        elif x == "1" and not reverse:
            t = y + t
        elif x == "2" and reverse:
            t = y + t
        else:
            t += y

if reverse:
    t = t.replace("X", s)
    print(t[::-1])
else:
    t = t.replace("X", s)
    print(t)

### FIXED CODE ###

s = input()
num = int(input())
t = "X"
reverse = False

for _ in range(num):
    row = input().split()
    if len(row) == 1:
        if reverse == False:
            reverse = True
        else:
            reverse = False
    else:
        x = row[1]
        y = row[2]
        if x == "1" and reverse:
            t += y
        elif x == "1" and not reverse:
            t = y + t
        elif x == "2" and reverse:
            t = y + t
        else:
            t += y

if reverse:
    t = t.replace("X", s)
    print(t[::-1])
else:
    t = t.replace("X", s)
    print(t)
### BUGGY CODE ###

import numpy as np

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

col_lis = [0 if c == "R" else 1 if c == "G" else 2 for c in S]
col_lis = np.asarray(col_lis)

ans = 0

r_count = 0
g_count = 0
b_count = 0

color_table = []

for color in col_lis:
    if color == 0:
        r_count += 1
    elif color == 1:
        g_count += 1
    else:
        b_count += 1
    color_table.append([r_count, g_count, b_count])

ans = 0

for center in range(1, N - 1):
    for right in range(center + 1, N):
        if col_lis[right] == col_lis[center]:
            continue
        left = 3 - col_lis[right] - col_lis[center]
        ans += color_table[center - 1][left]
        if center * 2 - right >= 0 and col_lis[center * 2 - right] == left:
            ans -= 1


print(ans)

### FIXED CODE ###

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

col_lis = [0 if c == "R" else 1 if c == "G" else 2 for c in S]

ans = 0

r_count = 0
g_count = 0
b_count = 0

color_table = []

for color in col_lis:
    if color == 0:
        r_count += 1
    elif color == 1:
        g_count += 1
    else:
        b_count += 1
    color_table.append([r_count, g_count, b_count])

ans = 0

for center in range(1, N - 1):
    for right in range(center + 1, N):
        if col_lis[right] == col_lis[center]:
            continue
        left = 3 - col_lis[right] - col_lis[center]
        ans += color_table[center - 1][left]
        if center * 2 - right >= 0 and col_lis[center * 2 - right] == left:
            ans -= 1


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

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

Sum = 0

A.sort()
sosuu = []

for i in range(N):

    if i > 0:
        if A[i] == A[i-1]:
            continue

    flag = True

    for j in range(len(sosuu)):
        if A[i] % sosuu[j] == 0:
            flag = False
            break

    if flag:
        if A.count(A[i]) == 1:
            Sum += 1
        sosuu.append(A[i])

print(Sum)


### FIXED CODE ###

from collections import defaultdict

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

d = defaultdict(int)
for key in A:
    d[key] += 1

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if d[A[i]] == 1:
            Sum += 1
print(Sum)
### BUGGY CODE ###

import sys
from bisect import insort_left
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()
    for _ in range(m):
        b = a.pop()//2
        insort_left(a, b)
    print(sum(a))


main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

import numpy as np

def main():
    n, m = map(int, input().split())
    a = np.array([int(i) for i in input().split()])
    a.sort()

    while True:
        temp = a[-1]//2
        a[-1] //= 2
        a.sort()
        ind = np.where(a==temp)[0][0]
        m -= 1
        if m == 0:
            print(np.sum(a))
            break
        elif n - ind < m:
            a[ind:] = a[ind:]//2
            a.sort()
            m = m - (n-ind)
        else:
            a[-m:] = a[-m:]//2
            print(np.sum(a))
            break

main()
### BUGGY CODE ###

N, A = map(int, input().split())
X = list(map(int, input().split()))
X = [0] + X

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

dp[0][0][0] = 1
for limit in range(1,N+1):
    for num in range(limit+1):
        for summ in range(50*N+1):
            if summ-X[limit] < 0:
                dp[limit][num][summ] = dp[limit-1][num][summ]
            else:
                dp[limit][num][summ] = dp[limit-1][num][summ] + \
                                       dp[limit-1][num-1][summ-X[limit]]
         
ans = 0                           
for i in range(1,N+1):
    ans += dp[N][i][A*i]

print(ans)      

### FIXED CODE ###

import collections

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

for i in range(N):
    X[i] -= A

sums = collections.Counter([0,X[0]])

for i in X[1:]:
    c = collections.Counter()
    for p,q in sums.items():
        c[i+p] = q
    sums += c

print(sums[0]-1)