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

n = int(input())
slist = []
cnt = 0
for i in range(n):
  s = input()
  s = sorted(s)
  
  s = ''.join(s)
  
  if slist:
    for i in range(len(slist)):
      if slist[i] == s:
        cnt += 1
  slist.append(s)
print(cnt)

### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
n = int(input())
ans = 0
sum = 0
ansdic = {}
for i in range(n):
  s = input()
  slist = [i for i in s]
  slist.sort()
  smoji = ','.join(slist)
  if smoji in ansdic:
    ansdic[smoji] += 1
  else:
    ansdic[smoji] = 1
for i in ansdic:
  if ansdic[i] > 1:
    sum += cmb(ansdic[i],2)
print(sum)
### BUGGY CODE ###

N = int(input())
S = str(input())
P = 0
JI = 0
RGB = 'R'
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if S[i] != S[j]:
            JI = j-i
            if S[i] != 'R' and S[j] != 'R':
                RGB = 'R'
            elif S[i] != 'G' and S[j] != 'G':
                RGB = 'G'
            else:
                RGB = 'B'
            for k in range(j+1,N):
                if JI != k-j:
                    if S[k] == RGB:
                        P += 1
print(P)

### FIXED CODE ###

N = int(input())
S = str(input())
P = 0
R = S.count('R')
G = S.count('G')
B = S.count('B')
P = R*G*B
for i in range(1,(N//2)+1):
    for j in range(N-2*i):
            if S[j]!=S[j+i] and S[j+i]!=S[j+2*i] and S[j]!=S[j+2*i]:
                P -= 1
print(P)
### BUGGY CODE ###

def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

k = int(input())
s = input()

n = len(s)

fact = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans = (ans - fact[n + k] * inv[i] * inv[n + k - i] * modpow(25, n + k - i, MOD) % MOD + MOD) % MOD

print(ans)

### FIXED CODE ###

def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

k = int(input())
s = input()

n = len(s)

fact = [1 for _ in range(n + k + 1)]
p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD
    p25[i] = p25[i - 1] * 25 % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans -= fact[n + k] * inv[i] % MOD * inv[n + k - i] % MOD * p25[n + k - i] % MOD
    if ans < 0:
        ans += MOD

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

S = input()
Q = int(input())
reversed = False
for _ in range(Q):
    q = input().replace(" ","")
    if len(q) == 3:
        t, f, c = q[0],q[1],q[2]
    else:
        t = q[0]
    if t == "1":
        reversed = not reversed
    elif t == "2":
        if f == "1":
            #元の順のとき
            if not reversed:
                S = c + S
            #元とは逆順になっているとき
            else:
                S = S + c
        else:
            #元の順のとき
            if not reversed:
                S = S + c
            #元とは逆順になっているとき
            else:
                S = c + S
if reversed:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

S = input()
Q = int(input())
head = ""
tail = ""
reversed = False
for _ in range(Q):
    q = input().replace(" ","")
    if len(q) == 3:
        t, f, c = q[0],q[1],q[2]
    else:
        t = q[0]
    if t == "1":
        reversed = not reversed
    elif t == "2":
        if f == "1":
            #元の順のとき
            if not reversed:
                head = c + head
            #元とは逆順になっているとき
            else:
                tail = tail + c
        else:
            #元の順のとき
            if not reversed:
                tail = tail + c
            #元とは逆順になっているとき
            else:
                head = c + head
if reversed:
    print(tail[::-1],S[::-1],head[::-1],sep="")
else:
    print(head,S,tail,sep="")
### BUGGY CODE ###

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

a=list(set(A))

cnt=0
for i in range(len(a)):
  n=A.count(a[i])
  cnt+=n*(n-1)//2

for i in range(N):
  print(cnt-A.count(A[i])+1)

### FIXED CODE ###

from collections import Counter

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

a=list(set(A))
C=Counter(A)
total=0

for i in range(len(a)):
  total+=C[a[i]]*(C[a[i]]-1)//2

for i in range(N):
  print(total-C[A[i]]+1)
### BUGGY CODE ###

K,S=input().split()
L=0
for i in range(0,int(K)+1):
    X=i
    if 0<int(S)-X<int(K)*2:
        for j in range(0,int(K)+1):
            Y=j
            Z=int(S)-(X+Y)
            if 0<=Z<=int(K):
                L=L+1
            else:
                L=L
    if int(S)-X==0 or int(S)-X==int(K)*2:
        L=L+1
    else:
        L=L
print(L)        
        

### FIXED CODE ###

K,S=input().split()
k=int(K)
s=int(S)
L=0
for X in range(0,k+1):
    for Y in range(0,k+1):
        Z=s-(X+Y)
        if 0<=Z<=k:
            L+=1
        
print(L)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = {}
answer = []
for i in range(N):
    B[i+1] = A[i]
for i in range(N):
    for j in range(1, N+1):
        if B[j] == i+1:
            answer.append(j)
print(' '.join(map(str,answer)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = {}
for i in range(N):
    B[A[i]] = i+1
answer = sorted(B.items())
ac=[]
for i in range(N):
    ac.append(answer[i][1])
print(' '.join(map(str, ac)))
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
BC = []
for _ in range(M):
  bc = list(map(int, input().split()))
  BC.append(bc)
BC = sorted(BC, key=lambda x:x[1])
for bc in BC:
  A[:bc[0]][A[:bc[0]]<bc[1]] = bc[1]
  A = np.sort(A)
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x:x[1],reverse=True)  
for b, c in BC:
  A.extend([c] * b)
  if len(A)>=2*N:
    break
A = sorted(A, reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

#import math
from functools import reduce

def gcd(a,b):
    if b>a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

def gcds(nums):
    return reduce(gcd, nums)

n = int(input())
a = [int(i) for i in input().split()]

ans = 0
for i in range(len(a)):
    aa = a[:i] + a[(i+1):]
    if ans < gcds(aa):
        ans = gcds(aa)
print(ans)

### FIXED CODE ###

import sys
from functools import reduce

input = sys.stdin.readline

def gcd(a,b):
    if b>a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

n = int(input())
a = [int(i) for i in input().split()]


ans = 0
l = [0]*(n+1)
r = [0]*(n+1)
for i in range(n):
    l[i+1] = gcd(l[i], a[i])
    r[n-i-1] = gcd(r[n-i], a[n-i-1])
for i in range(n):
    ans = max(ans, gcd(l[i], r[i+1]))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def print_ans(N, sr):
    """Test Case
    >>> print_ans(3, ["acornistnt", "peanutbomb", "constraint"])
    1
    >>> print_ans(2, ["oneplustwo", "ninemodsix"])
    0
    >>> print_ans(5,["abaaaaaaaa","oneplustwo","aaaaaaaaba","twoplusone","aaaabaaaaa"]) 
    4
    """
    check_ar = []
    for s in sr:
        check_ar.append("".join(sorted(s)))
    count = 0
    for i in range(N):
        tmp = check_ar[i]
        for k in range(i + 1, N):
            if tmp == check_ar[k]:
                count +=1
    print(count)


if __name__ == '__main__':
    N = int(input().rstrip())
    sr = [ input().rstrip() for _ in range(N)]
    print_ans(N, sr)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def print_ans(N, sr):
    """Test Case
    >>> print_ans(3, ["acornistnt", "peanutbomb", "constraint"])
    1
    >>> print_ans(2, ["oneplustwo", "ninemodsix"])
    0
    >>> print_ans(5,["abaaaaaaaa","oneplustwo","aaaaaaaaba","twoplusone","aaaabaaaaa"]) 
    4
    """
    for i in range(N):
        sr[i] = "".join(sorted(sr[i]))
    C = Counter(sr)
    ans = 0
    for v in C.values():
        ans += v * (v - 1) // 2
    print(ans)

    # for i in range(N):
    #     tmp = sr[i]
    #     for k in range(i + 1, N):
    #         if tmp == sr[k]:
    #             count +=1
    # print(count)


if __name__ == '__main__':
    N = int(input().rstrip())
    sr = [ input().rstrip() for _ in range(N)]
    print_ans(N, sr)
### BUGGY CODE ###

n=int(input())
x=list(map(int,input().split(' ')))
for i in range(n):
    x1=x[:]
    x1.pop(i)
    x1.sort()
    print (x1[int(n/2)-1])


### FIXED CODE ###

import numpy as np
n=int(input())
x=list(map(int,input().split(' ')))
x1=x[:]
x.sort()
m1=x[int(n/2)-1]
m2=x[int(n/2)]
for i in range(n):
    now=x1[i]
    if x1[i]<=m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

from sys import stdin

n,m = map(int, input().split())
a = list(map(int,input().split()))
for i in range(m):
    a.sort(reverse=True)
    a[0] = a[0]//2

print(sum(a))


### FIXED CODE ###

from sys import stdin
import heapq

n,m = map(int, input().split())
a = [int(x)*(-1) for x in stdin.readline().rstrip().split()]
heapq.heapify(a)

for i in range(m):
    temp = (-1)*heapq.heappop(a)//2
    heapq.heappush(a,temp*(-1))

print(sum(a)*(-1))
### BUGGY CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    K = II()
    S = input()
    N = len(S)
    def nCr(n,r):
        res = 1
        r = min(r,n-r)
        for i in range(n-r+1,n+1):
            res = res * i % P
        for i in range(2,r+1):
            res = res * pow(i,P-2,P) % P
        return res
    ans = 0
    for t in range(K+1):
        ans += pow(26,t,P)*pow(25,K-t,P)*nCr(N-1+K-t,K-t)
        ans %= P
    print(ans)

    
main()

### FIXED CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    K = II()
    S = input()
    N = len(S)
    def gencmb(n,k):
        # N-1+K C K  ... N-1 C 0
        ans = [1]*(k+1)
        for i in range(1,k+1):
            ans[-i-1] = ans[-i] * (N+i-1) * pow(i,P-2,P) % P
        return ans
    ans = 0
    pow26 = [0] * (K+1)
    pow26[0] = 1
    for i in range(1,K+1):
        pow26[i] = pow26[i-1] * 26 % P
    pow25 = [0] * (K+1)
    pow25[0] = 1
    for i in range(1,K+1):
        pow25[i] = pow25[i-1] * 25 % P
    cmb = gencmb(N,K)
    for t in range(K+1):
        ans += pow26[t]*pow25[K-t]*cmb[t]%P
        ans %= P
    print(ans)

    
main()
### BUGGY CODE ###

n=int(input())

def f_count(j):
    count=0
    for x in range(1,j):
        for y in range(1,j):
            for z in range(1,j):
                if x**2+y**2+z**2+x*y+y*z+z*x==j:
                    count+=1
    return count
    
for i in range(1,n+1):
    print(f_count(i))
    

### FIXED CODE ###

N=int(input())

#f(N)を入れるリスト。f(1)=ans_list[0], f(N)=ans_list[N-1]
ans_list=[0]*N

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            s=x**2+y**2+z**2+x*y+y*z+z*x
            if s<=N:
                ans_list[s-1]+=1
            
   
for i in range(N):
   print(ans_list[i])
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
i = 0
j = 0
n = 0
ans = []
ans = [0] * N
for n in range(N):
    for i, j in zip(H[n::],H[n+1::]):
        if i >= j:
            ans[n] += 1
        else:
            break
print(max(ans))


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = 0
i = 0
for n in range(N-1):
    if H[n] >= H[n+1]:
        i += 1
    else:
        if ans < i:
            ans = i
        i=0
print(max(ans,i))
### BUGGY CODE ###

N = int(input())
six = [6**i for i in range(7)]
nine = [9**i for i in range(6)]
L = []
for s in six:
  L.append(s)
for s in nine[1:]:
  L.append(s)
L.sort(reverse=True)
ans = 0
for l in L:
  while N > 0:
    ans += N // l
    N %= l
print(ans)

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def get_num_draw(n, x):
    res = 0
    while n > 0:
        res += n % x
        n = n // x
    return res


def main():
    N = NI()
    ans = 10**10
    for i in range(0, N+1, 6):
        ans = min(get_num_draw(N-i, 9) + get_num_draw(i//6, 6), ans)
    print(ans)


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

import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    prev_states = [set() for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            prev_states[ns].add(ps)
            next_states[ps].add(ns)
    
    today_states = queue.Queue()
    for s in range(max_state):
        if len(prev_states[s]) == 0:
            today_states.put(s)
    
    n_days = 0
    n_states_left = max_state
    while today_states.qsize() > 0:
        n_days += 1
        n_today_states = today_states.qsize()
        if n_today_states == 0:
            break
        for _ in range(n_today_states):
            s = today_states.get()
            n_states_left -= 1
            for ns in next_states[s]:
                prev_states[ns].remove(s)
                if len(prev_states[ns]) == 0:
                    today_states.put(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = set()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.add(s)
    
    n_days = 0
    n_states_left = max_state
    while len(today_states) > 0:
        n_days += 1
        if len(today_states) == 0:
            break
        n_states_left -= len(today_states)
        nextday_states = set()
        for s in today_states:
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    nextday_states.add(ns)
        today_states = nextday_states
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


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

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

for i in range(q):
    l, r = map(int, input().split())
    sl = s[l - 1 : r]
    sl = sl.replace("AC", "-")
    ans = sl.count("-")
    print(ans)


### FIXED CODE ###

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

t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i : i + 2] == "AC" else 0)
# print(t)
for j in range(q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

h, w, m = map(int, input().split())

targets = []
rowsum = [0] * h
rowmax = 0
colsum = [0] * w
colmax = 0
for _ in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    targets.append((hi, wi))
    rowsum[hi] += 1
    rowmax = max(rowmax, rowsum[hi])
    colsum[wi] += 1
    colmax = max(colmax, colsum[wi])

rowindices = []
for i, v in enumerate(rowsum):
    if v == rowmax:
        rowindices.append(i)

colindices = []
for i, v in enumerate(colsum):
    if v == colmax:
        colindices.append(i)

ans = rowmax + colmax - 1
for ri in rowindices:
    for ci in colindices:
        if (ri, ci) not in targets:
            print(rowmax + colmax)
            exit()

print(ans)

### FIXED CODE ###

from collections import defaultdict

h, w, m = map(int, input().split())

rowsum = [0] * h
rowmax = 0
colsum = [0] * w
colmax = 0
targets = defaultdict(int)
for _ in range(m):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    rowsum[hi] += 1
    rowmax = max(rowmax, rowsum[hi])
    colsum[wi] += 1
    colmax = max(colmax, colsum[wi])
    targets[(hi, wi)] = 1

rowindices = []
for i, v in enumerate(rowsum):
    if v == rowmax:
        rowindices.append(i)

colindices = []
for i, v in enumerate(colsum):
    if v == colmax:
        colindices.append(i)

ans = rowmax + colmax - 1
for ri in rowindices:
    for ci in colindices:
        if targets[(ri, ci)]:
            continue
        print(rowmax + colmax)
        exit()

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

# Library
alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = 0
next_char = [[-1 for j in range(len(s))] for i in range(26)]
# nc[i, j]: j文字目以降(1-indexed)で'a'+i がいつ出てくるか

for i in range(26):
    ind = chr(ord('a') + i)
    for j in range(len(s)):
        next_char[i][j] = ss.find(ind, j) - (j - 1)
        # print("next " + alp[i] + " is " + str(next_char[i][j]))

for i in range(len(t)):
    tmp = next_char[ord(t[i]) - ord('a')][index % len(s)]
    if tmp <= 0:
        index = -1
        break
    else:
        index += tmp
        # print(index)

print(index)


### FIXED CODE ###

# Library
import bisect

alp = "abcdefghijklmnopqrstuvwxyz"
#

s = input()
t = input()
ss = s * 2
index = -1
cir = 0
letter = []
res = 0

for i in range(len(ss)):
    letter.append([ss[i], i])

# Sort出来る.
letter.sort()

for i in range(len(t)):
    search = [t[i], index]
    tmp_ind = bisect.bisect(letter, search)
    # print("now searching " + str(search))
    # print("find: " + str(tmp_ind))
    # print("found: " + str(letter[tmp_ind]))
    if tmp_ind == len(ss):
        res = -1
        break
    if t[i] != letter[tmp_ind][0]:
        # Not exist
        res = -1
        break
    index += (letter[tmp_ind][1] - index)
    if index >= len(s):
        cir += 1
        index -= len(s)
    # print("cir,index : " + str(cir) + " " + str(index))
    res = cir * len(s) + index + 1

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353

    dp[0][0] = pow(2, N, MOD)
    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*pow(2, MOD-2, MOD)

    print(dp[N][S]%MOD)


main()

### FIXED CODE ###

import sys
input=sys.stdin.readline


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    m = pow(2, MOD-2, MOD)
    dp[0][0] = pow(2, N, MOD)
    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*m
            dp[i][j] %= MOD

    print(dp[N][S])


main()
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
R_max = N // R + 1
G_max = N // G + 1
B_max = N // B + 1
ans = 0
for i in range(0, R_max):
    for j in range(0, G_max):
        #for k in range(0, B_max):
            #if i * R + j * G + k * B == N:
        #a, b = divmod(N - (i * R + j * G), B)
        if (N - (i * R + j * G)) % B == 0 and (N - (i * R + j * G)) >= 0:
            #print('ans', i, j)
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
R_max = N // R + 1
G_max = N // G + 1
B_max = N // B + 1
ans = 0
for i in range(0, R_max):
    for j in range(0, G_max):
        #for k in range(0, B_max):
            #if i * R + j * G + k * B == N:
        #a, b = divmod(N - (i * R + j * G), B)
        if (N - (i * R + j * G)) % B == 0 and (N - (i * R + j * G)) >= 0:
            #print('ans', i, j)
            ans += 1
print(ans)
### BUGGY CODE ###

import math
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)
def is_prime(n):
  for i in range(len(primes)):
    if n % primes[i] == 0:
      return False
  return True
for i in range(3, int(1e5)):
  if is_prime(i):
    primes.append(i)

seeds = []
for p in primes:
  while M % p == 0:
    seeds.append(p)
    M = M // p

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = comb(len(seeds)-1, N-1)
# !!! 24=(2^a1 * 3^b1) * (2^a2 * 3^b2) * ... | sum(a) = 3, sub(b) = 1, len(a) = 4
# aのパターン数は 3,0,0,0 = ooo|||, 2,1,0,0 = oo|o|| なので並び替えのパターン数で
# (sum(a) + 分ける数)! / (sum(a)! * 分ける数!) = (6!/(3!3!)) = 20
# b にも同じことをして 1,0,0,0 = o||| = (1+3)!/(1!*3!) = 4
# 24を4つに分けるパターンは 20 * 4 = 80?

# (a+b)!/(a!b!) = (a+b)Ca = (a+b)Cb

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)


### FIXED CODE ###

N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)

seeds = []
p = 2
while M > 1:
  while M % p == 0:
    seeds.append(p)
    M = M // p
  if p*p > M:
    if M != 1:
	    seeds.append(M)
    M = 0
  p += 1

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)