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

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) % MOD * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - sum(i for i in range(1, n + 1))

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n - 1, k)
    ans += 2 * comb(n - 1, k - 1)
    if ans >= MOD:
        ans -= MOD
    if ans >= MOD:
        ans -= MOD

    if k >= 2:
        ans += comb(n - 1, k - 2)
        if ans >= MOD:
            ans -= MOD

    ans -= comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)


### FIXED CODE ###

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x


fact = [1] * 100100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)
### BUGGY CODE ###

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

res = [0] * (N)

for i in range(N):
    for j in range(i+1, N):
        dist = min(abs(i - j), abs(i - X + 1) + 1 + abs(j - Y + 1), abs(i-Y+1) + 1 + abs(j-X+1))
        res[dist] += 1

for i in range(1, N):
    print(res[i])


### FIXED CODE ###

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

res = [0] * (N)

for i in range(N):
    for j in range(i+1, N):
        dist = min(abs(i - j), abs(i - X + 1) + 1 + abs(j - Y + 1))
        res[dist] += 1

for i in range(1, N):
    print(res[i])
### BUGGY CODE ###

import sys
import numpy as np
input=sys.stdin.readline
n,k=map(int,input().split())
ni=n-1
h=[int(i) for i in input().split()]
h=np.array(h)
dp=[0]*n
fores=float('inf')
res=0
j=0
for base in range(1,n):
    if base<=k:
        j=0
    else:
        j=base-k
    for inter in range(j,base):
        if fores>(abs(h[base]-h[inter])+dp[inter]):
            fores=(abs(h[base]-h[inter])+dp[inter])
    dp[base]=fores
    fores=float('inf')
res=dp[ni]
print(res)

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

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


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

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

for i in A:
    sum+=i

for i in BC:
    A=sorted(A)
    for j in range(i[0]):
        #print(i[0],A[:i[0]],j,i[1])
        if i[1]>A[j]:
            sum+=i[1]-A[j]
            A[j]=i[1]
        else:
            break

print(sum)

### FIXED CODE ###


from operator import itemgetter
N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(M)]
A=sorted(A)
sum=0
BC.sort(key=itemgetter(1),reverse=True)

for a in A:
    sum+=a

i=0
#print(BC)

for j in range(M):
    #print(j)
    for k in range(BC[j][0]):
        if i<=N-1 and BC[j][1]>A[i]:
            sum+=BC[j][1]-A[i]
            i+=1
        else:
            break


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

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        B, C = map(int,input().split())
        for j in range(B):
            tmp = heapq.heappushpop(q, C)

            if tmp == C:
                break
            else:
                total += (C - tmp)

    print(total)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    X = [list(map(int,input().split())) for _ in range(M)]
    X.sort(key=lambda x:-x[1])
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        for j in range(X[i][0]):
            tmp = heapq.heappushpop(q, X[i][1])
            if tmp < X[i][1]:
                total += (X[i][1] - tmp)
            else:
                break

    print(total)

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

count = int(input())
numbers = map(int, input().split(' '))

tmp = 0
counter = 0
while True:
  for item in numbers:
    if item > 0:
      tmp += item % 2
    else:
      break
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]

print(counter)

### FIXED CODE ###

count = int(input())
numbers = [int(num) for num in input().split()]

counter = 0
while True:
  tmp = 0
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]
print(counter)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for t in range(q):
	l, r = map(int, input().split())
	u = s[l-1:r]
	counter = 0
	for i in range(len(u)-1):
		if u[i] == "A" and u[i+1] == "C":
			counter += 1
	print(counter)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
b = [0]
for t in range(1, n):
	if s[t-1] == "A" and s[t] == "C":
		b.append(b[t-1] + 1)
	else:
		b.append(b[t-1])
for u in range(q):
	l, r = map(int, input().split())
	print(b[r-1] - b[l-1])
### BUGGY CODE ###

#coding:utf-8

n = int(input())
l = []

for i in range(n):
    s = str(input())
    if s not in l:
        l.append(s)

ans = len(l)

print("{}".format(ans))

### FIXED CODE ###

#coding:utf-8

n = int(input())
l = []
count = 0

for i in range(n):
    s = str(input())
    l.append(s)

l = set(l)
count = len(l)
print("{}".format(count))
### BUGGY CODE ###

n = int(input())
*P, = map(float, input().split())
DP = [[0.0 for j in range(n+1)] for i in range(n+1)]
DP[0][0] = 1.0
for i in range(1, n+1):
    DP[i][0] = DP[i-1][0]*(1-P[i-1])
    for j in range(1, n+1):
        DP[i][j] = DP[i-1][j]*(1-P[i-1])+DP[i-1][j-1]*P[i-1]
print(sum(DP[n][(n+1)//2:]))


### FIXED CODE ###

n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n, q = list(map(int, input().split()))

trees =  [ [] for i in range(n+1) ]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    trees[a].append(b)
    trees[b].append(a)

values = [ 0 for i in range(n+1) ]
for i in range(q):
    p, x = list(map(int, input().split()))
    values[p] += x
#print(values)

def dfs2(i, parent):
    for j in trees[i]:
        if j == parent: continue
        values[j] += values[i]
        dfs2(j, i)

dfs2(1, -1)
print(*values[1:])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
 
ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)
 
cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x
 
 
# print(cnt)
 
 
def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)
 
 
d(1, -1)
print(*cnt[1:])
### BUGGY CODE ###

n = int(input())

member = list(map(int, input().split()))
ans = []

for i in range(n):
    ans.append((member.index(i+1))+1)

print(' '.join(map(str, ans)))    


### FIXED CODE ###

n = int(input())

member = list(map(int, input().split()))
ans = [0]*n

for i,num in enumerate(member):
    ans[num-1] = i+1

# print(' '.join(map(str, ans)))    
print(*ans)
### BUGGY CODE ###

n = int(input())
A = list()
for i in range(0, n):
    A.append(int(input()))
m = 0
cnt = 0
G = [1]

# G[i] = 3*Gi-1 + 1
for i in range(1, 101):
    h = 3 * G[0] + 1
    if h > n:  # h???n?¶???????????????§?????????4n+3*2n-1+1
        m = i
        break
    else:
        G.insert(0, h)


for g in G:
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            cnt += 1
        A[j+g] = v


print(m)
print(" ".join(str(x) for x in G))
print(cnt)

print("\n".join(str(x) for x in A))

### FIXED CODE ###

n = int(input())
A = list()
G = [1]
cnt = 0

for i in range(0, n):
    A.append(int(input()))


def insertion_sort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            cnt += 1
        A[j+g] = v


# G[i] = 3*Gi-1 + 1
def shell_sort():
    for i in range(1, 101):
        h = 3 * G[0] + 1
        if h > n:  # h???n?¶???????????????§?????????4n+3*2n-1+1
            break
        else:
            G.insert(0, h)
    for g in G:
        insertion_sort(A, n, g)

shell_sort()
print(len(G))
print(" ".join(str(x) for x in G))
print(cnt)
print("\n".join(str(x) for x in A))
### BUGGY CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    num = int(p ** (1 / n))
    for i in range(num + 1, 0, -1):
        if p % (i ** n) == 0:
            print(i)
            break

### FIXED CODE ###

n,p = map(int,input().split())
dum = round(p**(1/n))
for i in range(dum,-1,-1):
    if p%(i**n) == 0:
        print(i)
        break
### BUGGY CODE ###

count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    L=[i for i in range(n1+1)]
    R=[i for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = 10000000000
    R[n2] = 10000000000
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
            count+=1
        else:
            A[k] = R[j]
            j = j + 1
            count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    for i,j in enumerate(A):
        if i == n-1:
            print(j)
        else:
            print(j,end=" ")
    print(count)


### FIXED CODE ###

count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)
### BUGGY CODE ###

# B - Training Camp
def main():
    n = int(input())
    ans = 1

    for i in range(1, n+1):
        ans *= i
    else:
        print(ans%(10**9+7))

  
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

# B - Training Camp
def main():
    import math
    n = int(input())
    
    
    print(math.factorial(n)%(10**9+7))

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

p=int(input())
A=tuple(map(int,input().split()))

Fact=[1]
for i in range(1,p):
    Fact.append(Fact[i-1]*i%p)
Finv=[0]*p
Finv[-1]=pow(Fact[-1],p-2,p)
for i in range(p-2,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%p
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%p

B=[0]*p
B[0]=sum(A)
for i,a in enumerate(A):
    if a:
        for j in range(p):
            B[j]+=-comb(p-1,j)*pow(-i,p-1-j,p)
            B[j]%=p
print(*B)

### FIXED CODE ###

p=int(input())
A=tuple(map(int,input().split()))

Fact=[1] #階乗
for i in range(1,p):
    Fact.append(Fact[i-1]*i%p)
Finv=[0]*p #階乗の逆元
Finv[-1]=pow(Fact[-1],p-2,p)
for i in range(p-2,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%p
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%p

B=[0]*p
B[0]=sum(A)
for i,a in enumerate(A):
    if a:
        k=1
        for j in reversed(range(p)):
            B[j]+=-comb(p-1,j)*k
            B[j]%=p
            k*=-i
            k%=p
print(*B)
### BUGGY CODE ###

import itertools

def main():
    k,s=map(int,input().split())
    count = 0
    for x,y,z in itertools.product(range(k+1), repeat=3):
        if x + y + z == s:
            count += 1
    print(count)
        
if __name__ == "__main__":
    main()

### FIXED CODE ###

import itertools

def main():
    k,s=map(int,input().split())
    count = 0
    for x,y in itertools.product(range(k+1), repeat=2):
        if 0 <= s-(x+y) <= k:
            count += 1
    print(count)
        
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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


for i in range(n):
    ss=input()
    if len(ss)==1:
        s=s[::-1]
    else:
        a=list(ss.split())
        if a[1]=="1":
            s=a[2]+s
        else:
            s=s+a[2]
print(s)

### FIXED CODE ###

s=input()
n=int(input())
isreverse=False
top=''

for i in range(n):
    ss=input().split()
    if len(ss)==1:
        isreverse=not isreverse
    else:
        if ss[1]=="1":
            if isreverse: s+=ss[2]
            else: top+=ss[2]
        else:
            if isreverse: top+=ss[2]
            else: s+=ss[2]
if isreverse:
    s=s[::-1]+top
else:
    s=top[::-1]+s


print(s)
### BUGGY CODE ###

N = int(input())
X = input()

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

a = X.count("1")
ap, am = a+1, a-1
Flag = True

if am == 0:
  Flag = False
  am += 1

Ap = []
Am = []
temp = 1

for i in range(N):
  if i == 0:
    Ap.append(temp%ap)
    Am.append(temp%am)
  else:
    temp *= 2
    Ap.append(temp%ap)
    Am.append(temp%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am 

for i in range(N):
  cnt = 1
  if X[i] == "1":
    if Flag:
      p = Ams - Am[-1-i]
      p %= am
    else:
      cnt -= 1
      p = 0
  else:
    p = Aps + Ap[-1-i]
    p %= ap
  temp = p
  while temp > 0:
    temp %= popcount(temp)
    cnt += 1
  print(cnt)


### FIXED CODE ###

N = int(input())
X = input()

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x = x + (x >> 8) 
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

a = X.count("1")
ap, am = a+1, a-1
Flag = True

if am == 0:
  Flag = False
  am += 1

Ap = [1]
Am = [1]

for i in range(N-1):
  Ap.append(Ap[-1]*2%ap)
  Am.append(Am[-1]*2%am)

Aps = 0
Ams = 0

for i in range(N):
  if X[-1-i] == "1":
    Aps += Ap[i]
    Aps %= ap
    Ams += Am[i]
    Ams %= am 

for i in range(N):
  cnt = 1
  if X[i] == "1":
    if Flag:
      p = Ams - Am[-1-i]
      p %= am
    else:
      cnt -= 1
      p = 0
  else:
    p = Aps + Ap[-1-i]
    p %= ap
  temp = p
  while temp > 0:
    temp %= popcount(temp)
    cnt += 1
  print(cnt)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))

cnt = 0
while all([i%2!=0 for i in a])!=True:
    for i in range(n):
        if a[i]%2==0:
            a[i]//=2
            cnt+=1
            break
print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))

def cnt_div2(n):
    cnt=0
    while n%2==0:
        n//=2
        cnt+=1
    return cnt

#各要素に対して，2で割ることのできる回数をカウント
lis = [cnt_div2(i) for i in a]
print(sum(lis))
### BUGGY CODE ###

import math

n,p = map(int,input().split())

tmp = math.sqrt(p)

if n == 1:
    print(p)
else:
    for i in range(1,int(tmp)+1):
        if p % (i ** n) == 0:
            ans = i
    print(ans)

### FIXED CODE ###

import math

n,p = map(int,input().split())

tmp = math.sqrt(p)

if n == 1:
    print(p)
elif n >=100:
    print(1)
else:
    for i in range(1,int(tmp)+1):
        if p % (i ** n) == 0:
            ans = i
    print(ans)
### BUGGY CODE ###

population = int(input())
a2b = int(input())
b2c = int(input())
c2d = int(input())
d2e = int(input())
e2f = int(input())
city = [population,0,0,0,0,0]
vehicle = [a2b,b2c,c2d,d2e,e2f]
time = 0
while(city[5]!=population):
    for i in range(5):
        if city[4-i] >= vehicle[4-i]:
            city[5-i] += vehicle[4-i]
            city[4-i] -= vehicle[4-i]
        else:
            city[5-i] += city[4-i]
            city[4-i] = 0
    time += 1

print(time)

### FIXED CODE ###

import math
population = int(input())
a2b = int(input())
b2c = int(input())
c2d = int(input())
d2e = int(input())
e2f = int(input())
city = [population,0,0,0,0,0]
vehicle = [a2b,b2c,c2d,d2e,e2f]
print(math.ceil(population/min(vehicle)) + 4)
### BUGGY CODE ###

N,K=(int(x) for x in input().split())
P=list(map(int, input().split()))
S=sum(P[0:K])
ans=[S]
for i in range(N):
    S=sum(P[i:i+K])
    ans.append(S)
S=max(ans)
print((S+K)/2)

### FIXED CODE ###

N,K=(int(x) for x in input().split())
P=list(map(int, input().split()))
s=sum(P[0:K])
ans=[s]

for i in range(K,N):
    s=s+P[i]-P[i-K]
    ans.append(s)

S=max(ans)
print((S+K)/2)
### BUGGY CODE ###

import itertools

n  = int(input())

if n < 357:
  print(0)
  exit()

max_m = len(str(n))

ans = 0

for m in range(3,max_m+1):
  for i in range(1, m):
    for j in range(1, m-i):
      k = m-i-j
      ls = ['7']*i+['5']*j+['3']*k
      for l in set(itertools.permutations(ls)):
        s = ''.join(l)
        s = int(s)
        if s <= n:
          ans += 1
          #print(s)
print(ans)

### FIXED CODE ###

n = int(input())

def dfs(s):
  ret = 0
  if int(s) > n:
    return 0
  if all(s.count(c) > 0 for c in '753'):
    ret = 1
  for c in '753':
    ret += dfs(s+c)
  return ret

print(dfs('0'))
### BUGGY CODE ###

n, a = map(int, input().split())
xlist = list(map(int, input().split()))

j = n
k = n
t = n * a



dp = [[[0 for t in range(t + 1)] for k in range(k + 1)] for j in range(j + 1)]

dp[1][0][0] = 1
dp[0][0][0] = 1

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(0, j + 1):
    for ki in range(0, k + 1):
        for ti in range(0, t + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            else:
                # print('branch 4')
                dp[ji][ki][ti] = 0
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)

### FIXED CODE ###

n, a = map(int, input().split())
xlist = list(map(int, input().split()))

j = n
k = n
t = n * a
maxv = max(a, max(xlist))


dp = [[[0 for t in range(n*maxv + 1)] for k in range(k + 1)] for j in range(j + 1)]

dp[1][0][0] = 1
dp[0][0][0] = 1

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(0, j + 1):
    for ki in range(0, ji + 1):
        for ti in range(0, ki * maxv + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)
### BUGGY CODE ###

T=input()

ans=""
buff="D"
for i in range(len(T)):
    if T[i]=="?":
        if (i+1 < len(T)) and T[i+1] in ["?", "D"]:
            if i!=0 and ans[-1] == "P":
                ans=ans+"D"
            else:
                ans=ans+"P"
        else:
            ans=ans+"D"
    else:
        ans=ans+T[i]

print(ans)

### FIXED CODE ###

T=list(input())


ans=[]
buff="D"

leng=len(T)

for i in range(leng):
    now=T[i]
    if now=="?":
        if (i+1 < leng) and T[i+1] in ["?", "D"]:
            if buff == "P":
                buff="D"
            else:
                buff="P"
        else:
            buff="D"
    else:
        buff=now
    ans.append(buff)


print("".join(ans))
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1
	a = 1
	for i in range(1,length):
		a = 10 * a % 13
		if s[-i-1] != '?':
			num = int(s[-i-1])
			for j in range(13):
				dp[i][(a*num+j)%13] += dp[i-1][j]
				dp[i][(a*num+j)%13] %= MOD
		else:
			num = (10**i) % 13
			#a = 0
			for j in range(10):
				for k in range(13):
					dp[i][(a*j+k)%13] += dp[i-1][k]
					dp[i][k] %= MOD
				#a += num

	print(dp[-1][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

#gather input
input_ = str(input())
input_ = input_.lower()
list_ = []
length = len(input_)


#get length of input to bound i and j

#list to store unique strs
found = []
found.append(input_)
#iterating through possibles and storing uniques
unique = list_
for i in range(0,length):
    for j in range(i, length):
        #pull out
        unique = []
        for i_ in range(length):
            unique.append(input_[i_])
        unique[i] = input_[j]
        unique[j] = input_[i]

        test =''.join(unique)
        if test not in found:
            found.append(test)
        
print(len(found))

### FIXED CODE ###

def conbi(n):
	return int(n*(n-1)/2)

A = input("")
num = 1 + conbi(len(A)) #l_C_2
uniq = list(set(A))
for i in uniq:
	num -= conbi(A.count(i))
print(num)