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

n = int(input())
def total(n):
    total = 0
    for i in range(len(str(n))):
        total += int(str(n)[i])
        if i == len(str(n)):
            if len(str(total)) > 10**5:
                total(total)
    
    return total

if total(n) %9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
total = 0

for i in str(n):
    total += int(i)

if total %9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
ans = 1
primes = [2]

if C % 2 == 0:
  ans += 1
  while C % 2 == 0:
    C //= 2

p = 3
while C > 1:
  for prime in primes:
    if p % prime == 0:
      continue
  primes.append(p)
  if C % p == 0:
    ans += 1
  while C % p == 0:
    C //= p
  p += 2
print(ans)

### FIXED CODE ###

import fractions
import math

A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n == 1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

for q in get_primes2(min(C, 10**6)):
  if q ** 2 > C:
    break
  if C % q == 0:
    pfac.append(q)
    while C % q == 0:
      C //= q
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)
### BUGGY CODE ###

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

for i in range(M):
    B,C = map(int,input().split())
    A = A + [C] * B

A.sort(reverse=True)
A_max = A[0:N]

print(sum(A_max))

### FIXED CODE ###

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

A.sort()
S_BC = sorted(BC,key=lambda x:x[1],reverse=True)

index = 0
flag = 0
for Bj,Cj in S_BC:
    for k in range(Bj):
        if len(A) >= index+1:
            if A[index] < Cj:
                A[index] = Cj
                index += 1
            else:
                flag = 1
                break
        else:
            flag = 1
            break
        
    if flag == 1:
        break

print(sum(A))
### BUGGY CODE ###

#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_b
import itertools

intext = input()
[r, g, b, n] = map(int, intext.split())

rgb_list = [r, g, b]
rgb_list.sort(reverse=True)
[x, y, z] = rgb_list

cnt = 0
for x_val in range(0, n+1, x):
    for y_val in range(0, n+1, y):
        zan = n - x_val - y_val
        if zan >=0 and zan % z == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_b
import itertools

intext = input()
[r, g, b, n] = map(int, intext.split())

rgb_list = [r, g, b]
rgb_list.sort(reverse=True)
[x, y, z] = rgb_list

cnt = 0
for x_val in range(0, n+1, x):
    # for y_val in range(0, n+1, y):
    for y_val in range(0, (y*((n-x_val)//z))+1, y):
        zan = n - x_val - y_val
        if zan >=0 and zan % z == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import queue
N = int(input())
br = []
alist = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    br.append([a, b])
    alist[a].append(b)
    alist[b].append(a)

q = queue.Queue()
ans = dict()
typeNum = 0
for a in alist:
    typeNum = max(typeNum, len(a))

f = [False]*(N+1)
q.put([1, 1])
f[1] = True
while not q.empty():
    n = q.get()
    c = n[1]
    for nxt in alist[n[0]]:
        if not f[nxt]:
            ans[str(sorted([n[0], nxt]))] = c
            c = c % typeNum+1
            q.put([nxt, c])
            f[nxt] = True

print(typeNum)
for k in br:
    print(ans[str(k)])


### FIXED CODE ###

import sys
import queue
input = sys.stdin.readline

N = int(input())
alist = [[] for _ in range(N+1)]
idx = {}
for i in range(N-1):
    a, b = map(int, input().split())
    alist[a].append(b)
    alist[b].append(a)
    idx[(a, b)] = i
    idx[(b, a)] = i

q = queue.Queue()
ans = [0]*(N-1)
typeNum = 0
for a in alist:
    typeNum = max(typeNum, len(a))

f = [False]*(N+1)
q.put([1, 1])
f[1] = True
while not q.empty():
    n = q.get()
    c = n[1]
    for nxt in alist[n[0]]:
        if not f[nxt]:
            ans[idx[(n[0], nxt)]] = c
            c = c % typeNum+1
            q.put([nxt, c])
            f[nxt] = True

print(typeNum)
print(*ans, sep='\n')
### BUGGY CODE ###

n=int(input())

l=[0]*(n+1)
for i in range(1,n+1):
    for j in range(i,n+1,i):
        l[j]+=1

ans=0
for i in range(1,n+1):
    ans+=i*l[i]
print(ans)


### FIXED CODE ###

n=int(input())

l=[0]*(n+1)
for i in range(1,n+1):
    for j in range(i,n+1,i):
        l[j]+=1
# print(l)

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

#C - Traveling Plan
N = int(input())
A = list(map(int, input().split()))
DP = []
ans = []
DP.append(abs(0-A[0]))
for i in range(1,N):
    DP.append(abs(A[i]-A[i-1]))

for j in range(N):
    DP2 = DP[:]
    #DP2.pop(j)

    if j == 0:
        DP2[j+1] = abs(A[j+1])
        tmp = sum(DP2)-DP2[0]+abs(A[N - 1])
    elif j == N-1:
        tmp = sum(DP2)-DP2[N-1]+abs(A[N - 2])
    else:
        tmp = sum(DP2) + abs(A[N - 1])-DP2[j]-DP2[j+1]+abs(A[j+1]-A[j-1])
    ans.append(tmp)

for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

#C - Traveling Plan
N = int(input())
A = list(map(int, input().split()))
DP = []
ans = []
DP.append(abs(0-A[0]))
for i in range(1,N):
    DP.append(abs(A[i]-A[i-1]))

sum_DP = sum(DP)

for j in range(N):
    if j == 0:
        tmp = sum_DP-DP[0]-DP[1]+abs(A[1])+abs(A[N - 1])
    elif j == N-1:
        tmp = sum_DP-DP[N-1]+abs(A[N - 2])
    else:
        tmp = sum_DP + abs(A[N - 1])-DP[j]-DP[j+1]+abs(A[j+1]-A[j-1])
    ans.append(tmp)

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

N,X,Y=map(int,input().split())

E=[[] for i in range(N)]

for i in range(N-1):
  E[i].append(i+1)
  E[i+1].append(i)
  
E[X-1].append(Y-1)
E[Y-1].append(X-1)

INF=10**4

ans=[0 for i in range(N)]
from collections import deque
for i in range(N):
  score=[INF for i in range(N)]
  q=deque([[i,0]])
  while q:
    v,dist=q.pop()
    if score[v]>dist:
      score[v]=dist
    else:
      continue
    for child in E[v]:
      q.append([child,dist+1])
  for s in score:
    ans[s]+=1
    
for i in range(1,N):
  print(ans[i]//2)
    


### FIXED CODE ###

N,X,Y=map(int,input().split())

E=[[] for i in range(N)]

for i in range(N-1):
  E[i].append(i+1)
  E[i+1].append(i)
  
E[X-1].append(Y-1)
E[Y-1].append(X-1)

INF=10**4

ans=[0 for i in range(N)]
from collections import deque
for i in range(N):
  score=[INF for i in range(N)]
  q=deque([[i,0]])
  while q:
    v,dist=q.pop()
    if score[v]>dist:
      score[v]=dist
    else:
      continue
    for child in E[v]:
      q.append([child,dist+1])
  for s in score:
    ans[s]+=1
    
for i in range(1,N):
  print(ans[i]//2)
### BUGGY CODE ###

D=int(input())
C=list(map(int,input().split()))
S=[list(map(int,input().split())) for i in range(D)]
T=[int(input())-1 for i in range(D)]
X=[0]*26
Y=[0]*26
M=int(input())
d,q=0,0
P=0
for i in range(D):
  P+=S[i][T[i]]
  for j in range(26):
    X[j]+=C[j]
  X[T[i]]=0
  for j in range(26):
    Y[j]+=X[j]
for i in range(M):
  d,q=map(int,input().split())
  d,q=d-1,q-1
  P-=S[d][T[d]]
  P+=S[d][q]
  for j in range(26):
    X[j]=0
  Y[T[d]],Y[q]=0,0
  for j in range(D):
    if j==d:
      Z=q
    else:
      Z=T[j]
    for j in range(26):
      X[j]+=C[j]
    X[Z]=0
    Y[T[d]]+=X[T[d]]
    Y[q]+=X[q]
  T[d]=q
  print(P-sum(Y))

### FIXED CODE ###

D=int(input())
C=list(map(int,input().split()))
S=[list(map(int,input().split())) for i in range(D)]
T=[int(input())-1 for i in range(D)]
X=[0]*26
Y=[0]*26
M=int(input())
d,q=0,0
P=0
for i in range(D):
  P+=S[i][T[i]]
  for j in range(26):
    X[j]+=C[j]
  X[T[i]]=0
  for j in range(26):
    Y[j]+=X[j]
for i in range(M):
  d,q=map(int,input().split())
  d,q=d-1,q-1
  P-=S[d][T[d]]
  P+=S[d][q]
  for j in range(26):
    X[j]=0
  Y[T[d]],Y[q]=0,0
  for j in range(D):
    if j==d:
      Z=q
    else:
      Z=T[j]
    X[T[d]]+=C[T[d]]
    X[q]+=C[q]
    X[Z]=0
    Y[T[d]]+=X[T[d]]
    Y[q]+=X[q]
  T[d]=q
  print(P-sum(Y))
### BUGGY CODE ###

n=int(input())
s=input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(0,n-2):
    for j in range(0,int(n-i)):
        if i + j + j <= n-1:
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j] :
                ans = ans - 1

print(ans)

### FIXED CODE ###

n=int(input())
s=input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(0,n-2):
    for j in range(1,int((n-i)/2)+1):
        if i + j + j <= n-1:
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j] :
                ans = ans - 1

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

N = int(input())
Cx = [[] for i in range(N)]
Cy = [[] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = [[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)]
Qx.sort()
Qy = [[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)]
Qy.sort()
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
while cnt < N - 1:
  if Qx[0][0] <= Qy[0][0]:
    q = Qx[0]
    Qx = Qx[1:]
  else:
    q = Qy[0]
    Qy = Qy[1:]
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

### FIXED CODE ###

N = int(input())
Cx = [[0, 0] for i in range(N)]
Cy = [[0, 0] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)
### BUGGY CODE ###

import itertools
import sys
H, W = [int(i) for i in input().split(' ')]

cross = [[0] * (H + W -1) for _ in range(H + W - 1)]
for i, line in enumerate(sys.stdin):
    for j, c in enumerate(line.strip()):
        if c == "#":
            cross[i+j][i-j+W-1] = 1

across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]

r = 0
for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[i][j] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[i][k] == 1:
                if i - (k-j) >= 0:
                    r += across[i - (k - j)][k+1] - across[i - (k - j)][j]
                if i + (k-j) < H + W - 1:
                    r += across[i + (k - j)][k+1] - across[i + (k - j)][j]

for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[j][i] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[k][i] == 1:
                if i - (k-j) >= 0:
                    r += across2[i - (k - j)][k] - across2[i - (k - j)][j+1]
                if i + (k-j) < H + W - 1:
                    r += across2[i + (k - j)][k] - across2[i + (k - j)][j+1]

print(r)


### FIXED CODE ###

import itertools
import sys
H, W = [int(i) for i in input().split(' ')]

cross = [[0] * (H + W -1) for _ in range(H + W - 1)]
for i, line in enumerate(sys.stdin):
    for j, c in enumerate(line.strip()):
        if c == "#":
            cross[i+j][i-j+W-1] = 1

across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]

r = 0
for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[i][j] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[i][k] == 1:
                if i - (k-j) >= 0:
                    r += across[i - (k - j)][k+1] - across[i - (k - j)][j]
                if i + (k-j) < H + W - 1:
                    r += across[i + (k - j)][k+1] - across[i + (k - j)][j]

for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[j][i] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[k][i] == 1:
                if i - (k-j) >= 0:
                    r += across2[i - (k - j)][k] - across2[i - (k - j)][j+1]
                if i + (k-j) < H + W - 1:
                    r += across2[i + (k - j)][k] - across2[i + (k - j)][j+1]

print(r)
### BUGGY CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))
sum_p = []
for i in p:
    sum_p.append((1 + i) / 2)
ans = sum(sum_p[0:k])
for i in range(n - k + 1):
    if ans < sum(sum_p[i:i + k]):
        ans = sum(sum_p[i:i + k])
print(ans)

### FIXED CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))
sum_p = []
for i in p:
    sum_p.append((1 + i) / 2)

ans = sum(sum_p[0:k])
check = sum(sum_p[0:k])
p = 0
for i in range(k,n):
    check = check + sum_p[i] - sum_p[i - k]
    if check > ans:
        ans = check
print(ans)
### BUGGY CODE ###

S = input()
quantity = int(input())
L = [input().split() for i in range(quantity)]
for row in range(quantity):
    each = L[row]
    if each[0] == "1":
        S = S[::-1]
    else:
        if each[1] == "1":
            S = each[2] + S
        else:
            S = S + each[2]

print(S)

### FIXED CODE ###

S = input()
quantity = int(input())
L = [input().split() for i in range(quantity)]
hanten = -1
atama = ""
shiri = ""
for row in range(quantity):
    each = L[row]
    if each[0] == "1":
        hanten = hanten * -1
    else:
        if each[1] == "1":
            if hanten == -1:
                atama = atama + each[2]
            else:
                shiri = shiri + each[2]
        else:
            if hanten == -1:
                shiri = shiri + each[2]
            else:
                atama = atama + each[2]

atama = atama[::-1]
ans = atama + S + shiri
if hanten == 1:
    ans = ans[::-1]

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

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(n)]
    AB.sort()

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = dp[i - 1][j]
        for k in range(i, n):
            _, b = AB[k]
            res = max(res, dp[i][j - 1] + b)
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
        now = dp[i - 1][t - 1] + b
        res = max(res, now)

    print(res)


if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    H=list(map(int,input().split()))
    dp=[-1]*n #足湯iまでに着くまでに支払うコストの総和の最小値
    dp[0]=0
    for i in range(n):
        for j in range(1,k+1):
            ni=i+j
            if ni>=n:continue
            if dp[ni]==-1:
                dp[ni]=dp[i]+abs(H[ni]-H[i])
            else:
                dp[ni]=min(dp[ni],dp[i]+abs(H[ni]-H[i]))
    print(dp[n-1])
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    H=list(map(int,input().split()))
    dp=[-1]*n #足湯iまでに着くまでに支払うコストの総和の最小値
    dp[0]=0
    for i in range(n):
        for j in range(1,k+1):
            ni=i+j
            if ni>=n:continue
            if dp[ni]==-1:
                dp[ni]=dp[i]+abs(H[ni]-H[i])
            else:
                dp[ni]=min(dp[ni],dp[i]+abs(H[ni]-H[i]))
    print(dp[n-1])
if __name__=='__main__':
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
# 総和0を平均とするためKを引く
A = [a-K for a in LIST()]

# 半分全列挙
A1 = A[:N//2]
A2 = A[N//2:]

# それぞれの全組み合わせ
P1 = [0]
for S in range(1, 1<<len(A1)):
    p = 0
    for i in range(len(A1)):
        if S & 1<<i:
            p += A1[i]
    P1.append(p)
P2 = [0]
for S in range(1, 1<<len(A2)):
    p = 0
    for i in range(len(A2)):
        if S & 1<<i:
            p += A2[i]
    P2.append(p)

# 総和0になるペアの数を求める
C2 = Counter(P2)
ans = 0
for p in P1:
    ans += C2[-p]
# どちらも1つも選ばない分の1を引く
print(ans - 1)


### FIXED CODE ###

# -*- coding: utf-8 -*-

""" 3次元DP """

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

# i(=xNリストからどこまでを選べる範囲とするか)からj(=0～N)枚選んで、選んだ値の合計をkにするような選び方の総数
dp = [[[0] * (N*X+1) for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1

ans = 0
for i in range(1,N+1):
    for j in range(N+1):
        for k in range(N*X+1):
            # 求めたい合計(k)が、この周回で増えた選択肢(xN[i-1])より小さい場合、
            # 選び方の総数は増える見込みがないので前回の値をそのまま使用
            if k < xN[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            # 合計kが大きければ、増やせるかもしれないので、選んだ数と合計を減らしたところを見に行く
            # 選べる数j=0は論外だし、添え字[j-1]に良くないので条件で除外する
            elif k >= xN[i-1] and j > 0:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-xN[i-1]]
            # 選んだ数と合計から判断して、平均が条件に合うものなら答えに足す
            if i == N and j > 0 and k == j*A:
                ans += dp[i][j][k]

# ans = 0
# for k in range(1,N+1):
#     ans += dp[N][k][k*A]
        
print(ans)
### BUGGY CODE ###

n=int(input())
s=[sorted(input()) for i in range(n)]
s.sort()
cnt=0
k=0
for i in range(n-1):
  for j in range(i+1,n):
    for k in range(10):
      if s[i][k]!=s[j][k]:
        break
      elif k==9:
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
A={}
for i in range(n):
  s=str(sorted(input()))
  if s in A.keys():
    A[s]+=1
  else:
    A[s]=1
ans=0
for i in list(A.values()):
  ans+=int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())
    query = []
    for q in range(Q):
        query.append(input())

    for q in query:
        if len(q.split(' ')) > 1:
            T, F, C = q.split(' ')
            if F == '1':
                S = C + S
            elif F == '2':
                S = S + C
        elif q == '1':
            S = S[::-1]

    print(S)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    S = input()
    Q = int(input())

    t = deque(S)
    reverse = False
    for _ in range(Q):
        query = input()
        if query[0] == '1':
            reverse = not reverse
        elif query[0] == '2':
            _, F, C = query.split()
            if F == '1':
                if reverse:
                    t.append(C)
                else:
                    t.appendleft(C)
            elif F == '2':
                if reverse:
                    t.appendleft(C)
                else:
                    t.append(C)
    
    result = ''.join(t)
    if reverse:
        result = result[::-1]

    print(result)

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

n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ok=0
import bisect
for i in range(n):
    ind=bisect.bisect_right(b,a[i])
    for j in range(ind,n):
        indsec=bisect.bisect_right(c,b[j])
        ok += n-indsec
print(ok)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=list(map(int,input().split()))
c=sorted(list(map(int,input().split())))
import bisect
ans=0
for i in range(n):
    inda=bisect.bisect_left(a,b[i])
    indc=bisect.bisect_right(c,b[i])
    ans += inda*(n-indc)
print(ans)
### BUGGY CODE ###

N = int(input())
l = ["".join(sorted([c for c in input()])) for i in range(N)]
l.sort()


def fac(n):
    """階乗"""
    res = 0
    for i in range(1, n+1):
        res += i
    return res

hash_t = {}
for i in range(N-1):
    if l[i] == l[i+1]:
        if l[i] in hash_t.keys():
            hash_t[l[i]] += 1
        else:
            hash_t[l[i]] = 1

cnt = 0
for x in hash_t.values():
    cnt += fac(x)
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
l = ["".join(sorted([c for c in input()])) for i in range(N)]
l.sort()


def fac(n):
    """階乗"""
    res = 0
    for i in range(1, n+1):
        res += i
    return res


hash_l = []
for i in range(N-1):
    if l[i] == l[i+1]:
        if i == 0:
            hash_l.append(0)
        if l[i-1] == l[i]:
            hash_l[-1] += 1
        else:
            hash_l.append(1)

cnt = 0
for x in hash_l:
    cnt += fac(x)
print(cnt)
### BUGGY CODE ###

import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
na = np.array(a)
q = int(input())

for _ in range(q):
    cf, ca = map(int, input().split())
    na[na == cf] = ca
    print(na.sum())



### FIXED CODE ###

import sys
import numpy as np
import math
import collections
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
c_n = np.array([(k, v) for k, v in c.items()])
total = np.dot(c_n.T[0], c_n.T[1])
q = int(input())
for _ in range(q):
    cf, ca = map(int, input().split())
    num = c[cf]
    if ca in c:
        c[ca] += c[cf]
        c[cf] = 0
#         del sd[cf]
#         del c[cf]
    else:
#         sd[ca] = sd[cf]
        c[ca] = c[cf]
        c[cf] = 0
#         del sd[cf]
#         del c[cf]
    total += num * (ca - cf)
    print(total)
### BUGGY CODE ###

def main():
  n = int(input())
  mod = 10**9+7
  a = []
  for i in range(n):
    a.extend(list(map(int,input().split())))
  dp = [0]*(1<<n)
  dp[0] = 1
  for S in range((1<<n)-1):
    k = bin(S).count("1")*n
    t = dp[S]
    for i in range(n):
      if a[k+i]:
        dp[S|1<<i] = (dp[S|1<<i]+t)%mod
  print(dp[(1<<n)-1])
main()

### FIXED CODE ###

def main():
  n = int(input())
  mod = 10**9+7
  a = []
  for i in range(n):
    a.extend(list(map(int,input().split())))
  dp = [0]*(1<<n)
  dp[0] = 1
  for S in range((1<<n)-1):
    k = bin(S).count("1")*n
    t = dp[S]
    for i in range(n):
      if a[k+i]:
        dp[S|1<<i] = (dp[S|1<<i]+t)%mod
  print(dp[(1<<n)-1])
main()