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

import collections
n = int(input())
s_n = [] * n
for i in range(n):
    s = input()
    s_n.append(collections.Counter(s))

cnt = 0
for i in range(n):
    cur_same = 0
    if s_n[i] == -1:
        continue
    for j in range(i+1,n):
        if s_n[i] == s_n[j]:
            cur_same += 1
            cnt += 1*cur_same
            s_n[j] = -1

print(cnt)


### FIXED CODE ###

n = int(input())
ans = 0
used_s = {}
for _ in range(n):
    s = "".join(sorted(input()))
    if not s in used_s.keys():
        used_s[s] = 0
    else:
        used_s[s] += 1
        ans += 1 * used_s[s]

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

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
  if A[i] < (10**5)*2:
    for j in range(i+1, N):
      if (j > A[j]) and (A[i] < (10**5)*2):
        if j-i == A[i]+A[j]:
          ans += 1
      
print(ans)

### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(int)
for i in range(n):
    ap[i - a[i]] += 1

ans= 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)
### BUGGY CODE ###

from math import factorial
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
MOD = 10**9+7
ans = 0
for i in range(n):
  if n-i-1 < k-1:
    continue
  C = ( factorial(n-i-1)//factorial(k-1) ) // factorial(n-i-k)
  C %= MOD
  ans += ((a[i]-a[n-i-1]) * C) % MOD
  ans %= MOD

print(ans)
  

### FIXED CODE ###

MAX = 100000 #階乗のmodを求めたい中で最大のもの
MOD = 10**9+7

fac = [0]*MAX   #階乗のmod
inv = [0]*MAX    #その数の逆元
finv = [0]*MAX   #階乗の逆元

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = (fac[i-1] * i) % MOD
        inv[i] = MOD-(inv[MOD%i] * (MOD//i))%MOD
        finv[i] = (finv[i-1]*inv[i]) %MOD
        
    
def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return (fac[n] * (finv[k]*finv[n-k]))%MOD

#pが素数でないと使えない
COMinit()
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
MOD = 10**9+7
ans = 0
for i in range(n):
  if n-i < k:
    continue
  C = COM(n-i-1,k-1)
  ans += ((a[i]-a[n-i-1]) * C) % MOD
  ans %= MOD

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

N = int(input())

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

ans = nums[0]

for x in range(N - 1):
    ans = ans * nums[x + 1]


if ans > 1000000000000000000:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

N = int(input())

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

ans = nums[0]

for i in range(N):
    if nums[i] == 0:
        print("0")
        exit()

for x in range(N - 1):
    ans = ans * nums[x + 1]
    if ans > 1000000000000000000:
        print("-1")
        exit()
        
print(ans)
### BUGGY CODE ###

from math import factorial

N = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
x_dis = [x[i+1] - x[i] for i in range(N-1)]
ans = 0
m = N-1
fac = factorial(m)
tmp = fac
for i in range(m):
    ans += x_dis[i] * tmp
    ans %= mod
    tmp += fac//(i+2)
print(ans)


### FIXED CODE ###

from math import factorial

N = int(input())
x = list(map(int, input().split()))
mod = 10**9 + 7
x_dis = [x[i+1] - x[i] for i in range(N-1)]
ans = 0
m = N-1
fac = factorial(m) % mod
tmp = fac
for i in range(m):
    ans += x_dis[i] * tmp
    ans %= mod
    tmp += (fac*pow((i+2),(mod-2), mod))%mod
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict,deque
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

graph = defaultdict(lambda: defaultdict(int))

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v,g):
    que = deque()
    que.append([v,0])
    while len(que) > 0:
        # i,dist = que.pop()  # 深さ優先探索        
        i,dist = que.popleft() #幅優先探索
        if i == g:
            return dist
        for n, val in graph[i].items():
            que.append([n,dist+val])
    return -1

for x,y in xy:
    print(xfs(x-1,K-1) + xfs(K-1,y-1))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict,deque
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

# graph = defaultdict(lambda: defaultdict(int))
graph = [defaultdict(int) for _ in range(N)]

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v):
    dist = [-1 for _ in range(N)]
    dist[v] = 0
    que = deque()
    que.append(v)
    while len(que) > 0:
        i = que.pop()  # 深さ優先探索        
        # i = que.popleft() #幅優先探索
        for n, val in graph[i].items():
            if dist[n] == -1:
                dist[n] = dist[i] + val
                que.append(n)
    return dist

dist = xfs(K-1)

for x,y in xy:
    print(dist[x-1] + dist[y-1])
### BUGGY CODE ###

n,k = map(int,input().split())
lis = list(map(int,input().split()))

dp = [10 ** 10 for i in range(n+k+1)]

dp[0] = 0
for i in range(n):
    for j in range(1,min(n-i,k+1)):
        dp[i+j] = min(dp[i+j],dp[i]+abs(lis[i+j]-lis[i]))
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
lis = list(map(int,input().split()))

dp = [10 ** 10 for i in range(n+k+1)]

dp[0] = 0
for i in range(n):
    for j in range(1,min(n-i,k+1)):
        dp[i+j] = min(dp[i+j],dp[i]+abs(lis[i+j]-lis[i]))
print(dp[n-1])
### BUGGY CODE ###

while 1:
    n = input()
    if n == 0:
        break
    D = {x**2 % n for x in xrange(1, n)}
    C = {}
    print D
    for p in D:
        for q in D:
            if p == q:
                continue
            g = (p - q) % n
            if g > (n - 1)/2:
                g = n - g
            C[g] = C.get(g, 0) + 1
    for i in xrange(1, (n-1)/2+1):
        print C.get(i, 0)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    if N == 1:
        return True
    *S, = set(i**2 % N for i in range(1, N))
    S.sort()
    L = len(S)
    C = [0]*N
    D = [0]*((N-1)//2)
    for i in range(L):
        a = S[i]
        for b in S[:i]:
            C[a - b] += 2
    for i in range(1, N):
        D[min(i, N-i)-1] += C[i]
    write("\n".join(map(str, D)))
    write("\n")
    return True
while solve():
    ...
### BUGGY CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]


def main():
    n, m = na()
    a = na()

    c = 0
    for l in range(n):
        v = 0
        for r in range(l, n):
            v += a[r]
            if v % m == 0:
                c += 1

    print(c)
                
main()


### FIXED CODE ###

import sys
import math

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]


def main():
    n, m = na()
    a = na()

    vs = {}

    b = [0] * n
    b[0] = a[0]
    for i in range(1, n):
        b[i] = b[i-1] + a[i]

    for i in range(n):
        k = b[i] % m
        if k in vs:
            vs[k] += 1
        else:
            vs[k] = 1
            

    cnt = 0
    for k, v in vs.items():
        if v >= 2:
            cnt += math.factorial(v) // 2 // math.factorial(v-2)
        if k == 0:
            cnt += v


    print(cnt)


main()
### BUGGY CODE ###

#!/usr/bin/env python3
N, C = map(int, input().split())
table = [[0] * C for i in range(2 * 10 ** 5 + 1)]
for i in range(N):
    s, t, c = map(int, input().split())
    table[2 * s][c - 1] = 1
    table[2 * t][c - 1] = -1

ans = 0
for i in range(1, 2 * 10 ** 5 + 1):
    for j in range(C):
        if table[i - 1][j] == 1 and table[i][j] == 0:
            table[i][j] = 1
    ans = max(ans, sum(map(lambda x: abs(x), table[i])))

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
N, C = map(int, input().split())
table = [[0] * C for i in range(10 ** 5 + 1)]
for i in range(N):
    s, t, c = map(int, input().split())
    table[s - 1][c - 1] += 1
    table[t - 1][c - 1] -= 1

imos = [0] * (10 ** 5 + 1)
for i in range(10 ** 5 + 1):
    for j in range(C):
        if table[i][j] == 1:
            imos[i] += 1
        if table[i][j] == -1:
            imos[i + 1] -= 1

ans = 0
for i in range(1, 10 ** 5 + 1):
    imos[i] += imos[i - 1]
    ans = max(ans, imos[i])

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

import collections

H,W,M = map(int, input().split())
h = [0]*M
w = [0]*M
for i in range(M):
    h[i], w[i] = map(int, input().split())
ch = collections.Counter(h).most_common()
mh = []
mnh = ch[0][1]
for ch1 in ch:
    if mnh == ch1[1]:
        mh.append(ch1[0])
        continue
    else:
        break
    break
cw = collections.Counter(w).most_common()
mw = []
mnw = cw[0][1]
for cw1 in cw:
    if mnw == cw1[1]:
        mw.append(cw1[0])
        continue
    else:
        break
    break
for h1 in mh:
    for w1 in mw:
        if (h1,w1) not in zip(h,w):
            print(mnh+mnw)
            exit()
print(mnh+mnw-1)

### FIXED CODE ###

from collections import defaultdict

H, W, M = map(int, input().split())
h = [0] * M
w = [0] * M

nh = [0] * H  # number of h == i+1
nw = [0] * W  # number of w == i+1
dic = defaultdict(bool)

for i in range(M):
    h[i], w[i] = map(int, input().split())
    h[i] -= 1
    w[i] -= 1
    nh[h[i]] += 1
    nw[w[i]] += 1
    dic["{}-{}".format(h[i],w[i])] = True

mnh = max(nh)
mnw = max(nw)

mh = [i for i, nh1 in enumerate(nh) if nh1 == mnh]
mw = [i for i, nw1 in enumerate(nw) if nw1 == mnw]

for h1 in mh:
    for w1 in mw:
        if not dic["{}-{}".format(h1,w1)]:
            print(mnh + mnw)
            exit()
print(mnh + mnw - 1)
### BUGGY CODE ###

import numpy as np

N = int(input())

*A,  = map(int, input().split())
A    = np.array(A)
min = float('INF')

for i in range(N-1):
    sunek = A[0:i+1]
    araig = A[i+1:N]
    min_temp = (np.abs(np.sum(sunek)-np.sum(araig)))

    if min_temp < min:
        min = min_temp

print(min)

### FIXED CODE ###

import sys

N= int(input())

*A, = map(int, input().split())


S = [0]*(len(A)+1)

for i in range(1, len(S), 1):

    S[i] = S[i-1] + A[i-1]

x = 0
y = 0
min = float('inf')

for i in range(1, N, 1):
    x = S[i]
    y = S[len(S)-1] - S[i]

    if min > abs(x-y):
        min = abs(x-y)
print(min)
### BUGGY CODE ###

n,s=open(0)
n=int(n)
d={i:s.count(i)for i in'RGB'}
a=0
for i in range(n):
    d[s[i]]-=1
    b=d.copy()
    for j in range(i+1,n):
        b[s[j]]-=1
        if s[i]==s[j]:continue
        c,*_=set('RGB')-{s[i],s[j]}
        a+=b[c]
        k=j+j-i
        if k<n and s[k]==c:
            a-=1
print(a)

### FIXED CODE ###

n=int(input())
s=[ord(c)%3for c in input()]
d=[0]*3
for i in s:d[i]+=1
a=0
for i in range(n):
    d[s[i]]-=1
    b=d.copy()
    for j in range(i+1,n):
        b[s[j]]-=1
        if s[i]==s[j]:continue
        c=(0,2,1,0)[s[i]+s[j]]
        a+=b[c]
        k=j+j-i
        if k<n and s[k]==c:
            a-=1
print(a)
### BUGGY CODE ###

n =int(input())
# print(n)
List=list(map(int,input().split()))
count = 0
# print(List)
# print(List[1])
for i in range(n):
    # print(List[i])
    count += List.count(List[i])
    # print(count)
if count == n:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

def has_duplicates(seq):
    return len(seq) != len(set(seq))

n =int(input())
List=list(map(int,input().split()))
if has_duplicates(List) == False:
    print('YES')
else:
    print("NO")
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=sorted(a,reverse=True)
x,y=b[0],b[1]
for i in range(n):
	if i==a.index(x):
		print(y)
	else:
		print(x)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=sorted(a,reverse=True)
x,y=b[0],b[1]
z=a.index(x)
for i in range(n):
	if i==z:
		print(y)
	else:
		print(x)
### BUGGY CODE ###

from scipy.special import comb
import itertools

n, k = map(int, input().split())
x = list(map(int, input().split()))
X = []
m = 3*10**8

for v in itertools.combinations(x, k):
    X.append(list(v))

for i in range(comb(n, k, exact=True)):
    a = min(abs(min(X[i]))+abs(max(X[i])-min(X[i])), abs(max(X[i]))+abs(max(X[i])-min(X[i])))
    if m > a:
        m = a
print(m)

### FIXED CODE ###

n, k = map(int, input().split())
x = list(map(int, input().split()))
m = 3*10**8

for i in range(n-k+1):
    a = x[i]
    b = x[i+k-1]
    t= min(abs(a)+abs(b-a), abs(b)+abs(b-a))
    if m > t:
        m = t
print(m)
### BUGGY CODE ###

import bisect

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
nums = []

for a in A:
    for b in B:
        for c in C:
            n = a + b + c
            idx = bisect.bisect_right(nums, n)
            if idx == 0 and len(nums) > K:
                break
            else:
                nums.insert(idx, n)
                if len(nums) > K:
                    nums.pop(0)

for n in nums[::-1]:
    print(n)

### FIXED CODE ###

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

E = sorted([a+b for a in A for b in B], reverse=True)

E = E[:K]
nums = sorted([e+c for e in E for c in C], reverse=True)

for n in nums[:K]:
    print(n)
### BUGGY CODE ###

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

for num in A:
    if num in dic:
        dic[num] += 1
    else:
        dic[num] = 1

for num in A:
    dic[num] -= 1
    total = 0
    for value in dic.values():
        total += value * (value-1) / 2
    print(int(total))
    dic[num] += 1


### FIXED CODE ###

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

for num in A:
    if num in dic:
        dic[num] += 1
    else:
        dic[num] = 1

total = 0
for value in dic.values():
    total += value * (value-1) / 2   # 使えないボールがない場合のtotal

for num in A:
    print(int(total - dic[num] + 1))
### BUGGY CODE ###

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [10**9 for _ in range(h+1)]
dp[0] = 0
for i in range(1, h+1):
    for a, b in ab:
        if a < i:
            dp[i] = min(dp[i], dp[i-a]+b)
        else:
            dp[i] = min(dp[i], b)
print(dp[h])

### FIXED CODE ###

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [10**5 for _ in range(h+1)]
dp[0] = 0
for i in range(1,h+1):
    dp[i] = min([dp[max(0, i-pw)]+ma for pw, ma in ab])
print(dp[h])
### BUGGY CODE ###

import collections

N = int(input())
S = ['']*N

for i in range(N):
    S[i] = input()

s = collections.Counter(S)

max_list = [ml[0] for ml in s.items() if ml[1] == max(s.values())]
max_list.sort()

for i in max_list:
    print(i)

### FIXED CODE ###

import collections

N = int(input())
S = ['']*N

for i in range(N):
    S[i] = input()

s = collections.Counter(S)

max_num = max(s.values())

ans = []

for k, v in s.items():
    if v == max_num:
        ans.append(k)

ans.sort()

print('\n'.join(ans))
### BUGGY CODE ###

s = [_ for _ in input()]
qn = int(input())
rev = False

for _ in range(qn):
  q = [_ for _ in input().split()]
  if q[0] == '1':
    rev = not rev
  else:
    if (rev and q[1] == '2') or (not rev and q[1] == '1'):
      s.insert(0, q[2])
    else:
      s.append(q[2])

if rev:
  s.reverse()
print("".join(s))

### FIXED CODE ###

s = [_ for _ in input()]
qn = int(input())
rev = False
prevs = ['']*200000
nexts = ['']*200000
previ = 0
nexti = 0

for _ in range(qn):
  q = [_ for _ in input().split()]
  if q[0] == '1':
    rev = not rev
  else:
    if (rev and q[1] == '2') or (not rev and q[1] == '1'):
      prevs[previ] = q[2]
      previ += 1
    else:
      nexts[nexti] = q[2]
      nexti += 1

prevs.reverse()
s = prevs + s + nexts
if rev:
  s.reverse()
print("".join(s))
### BUGGY CODE ###

from collections import Counter
N = int(input())
B = [int(x) for x in input().split()]
A=Counter(B)
V, C = zip(*A.most_common())
count=0
for x in C:
  if x==0:
    break
  count+=x*(x-1)/2
for x in B:
  ans=count-C[V.index(x)]+1
  print(int(ans))

### FIXED CODE ###

from collections import Counter
N = int(input())
B = [int(x) for x in input().split()]
A=Counter(B)
V, C = zip(*A.most_common())
count=0
i=0
dict={}
for x in C:
  count+=x*(x-1)/2
  dict[V[i]]=x
  i+=1
for x in B:
  ans=count-dict[x]+1
  print(int(ans))
### BUGGY CODE ###

import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
#sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)
s=list(input())
k=0
kprev=-1
while(kprev!=k):
    kprev=k
    i=0
    while(i+1<len(s)):
        if(s[i]=="B" and s[i+1]=="W"):
            s[i],s[i+1]=s[i+1],s[i]
            k+=1
        i+=1
print(k)


### FIXED CODE ###

import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
#sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)
s=list(input())
A=[]
for i in range(len(s)):
    if(s[i]=="W"):
        A.append(i)
k=0
i=0
for x in A:
    k+=(x-i)
    i+=1
print(k)
### BUGGY CODE ###

import itertools
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

_w = list(range(H+W-2))

min_change = H * W

for path in itertools.combinations(_w,W-1):
    state = [0, 0]
    pathway = [0] * (H+W-2)
    path = list(path)
    change = 0
    for i in path:
        pathway[i] = 1
    # init Flag
    black_flag = True if S[0][0] == '#' else False
    
    for go in pathway:
        state[go] += 1
        if S[state[0]][state[1]] == '#':
            if state == [H-1, W-1]:
                change += 1
                break
            if black_flag:
                continue
            else:
                black_flag = True
        else:
            if black_flag:
                change += 1
            else:
                continue
    if min_change > change:
        min_change = change
print(min_change)

### FIXED CODE ###

# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

grid = [[0 for _ in range(W)] for _ in range(H)]

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])
### BUGGY CODE ###

n = int(input())

ans = 0
for i in range(1, n):
    for j in range(1, i+1):
        if (i % j) == 0:
            ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n):
  ans += (n - 1) // i
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

ans = 0

for i in range(N + 1):
    for j in range(N + 1):
        t = (N - G * i - B * j)
        if is_integer_num(t / R) and t >= 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

ans = 0

for i in range(N + 1):
    for j in range(N + 1):
        t = (N - G * i - B * j)
        if is_integer_num(t / R) and t >= 0:
            ans += 1

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

import bisect
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = [list(map(int,input().split())) for _ in range(M)]

for b,c in BC:
    for i in range(b):
        bisect.insort(A,c)    
    # print(A[-N:])
# print(A)
# print(sorted(A))
# print(sorted(A)[-N:])
print(sum(sorted(A)[-N:]))

### FIXED CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC, key=lambda x:x[1], reverse=True)
D = [0] * N
idx = 0
for b,c in BC:
    for i in range(b):
        D[idx] = c
        idx += 1
        if idx >= N:
            break
    if idx >= N:
        break
# print(D)


# print(D)
# print(sorted(A))
# print(len(D), len(A))
for i in range(N):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break
print(sum(A))
### BUGGY CODE ###

from bisect import bisect
mod = 10**9+7
N,K = map(int,input().split())

c = []
for i in range(1,int(N**0.5)+1):
    c.append(i)
    c.append(int(N/i))
c = list(set(c))
c.sort()

k = []
for i in c:
    if int(N/i) != int(N/(i+1)):
        k.append(i)

dp = [[0]*len(k) for _ in range(K)]
for i in range(len(k)):
    dp[0][i]=k[i]

def S(n,m):
    l = bisect(k,m)
    return dp[n][l-1]+(dp[n][l]-dp[n][l-1])*(m-k[l-1])*pow(k[l]-k[l-1],mod-2,mod)

    
for i in range(K-1):
    dp[i+1][0] = dp[i][-1]
    for j in range(len(k)-1):
        dp[i+1][j+1] = dp[i+1][j]+(k[j+1]-k[j])*S(i,int(N/(k[j]+1)))
        dp[i+1][j+1] %= mod

print(dp[-1][-1])

### FIXED CODE ###

from bisect import bisect
mod = 10**9+7
N,K = map(int,input().split())

c = []
for i in range(1,int(N**0.5)+1):
    c.append(i)
    c.append(int(N/i))
c = list(set(c))
c.sort()

k = []
for i in c:
    if int(N/i) != int(N/(i+1)):
        k.append(i)

dp = [[0]*len(k) for _ in range(K)]
for i in range(len(k)):
    dp[0][i]=k[i]

inv = [0]*(len(k)-1)
for i in range(len(k)-1):
    inv[i] = pow(k[i+1]-k[i],mod-2,mod)

index = [0]*len(k)
for i in range(len(k)):
    m = int(N/(k[i]+1))
    index[i] = bisect(k,m)

for i in range(K-1):
    dp[i+1][0] = dp[i][-1]
    for j in range(len(k)-1):
        m = int(N/(k[j]+1))
        l = index[j]
        S = dp[i][l-1]+(dp[i][l]-dp[i][l-1])*(m-k[l-1])*inv[l-1]
        dp[i+1][j+1] = dp[i+1][j]+(k[j+1]-k[j])*S
        dp[i+1][j+1] %= mod

print(dp[-1][-1])