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


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1

    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                if MEMO[t] != -1:
                    tmp += MEMO[t] + 1
                else:
                    tmp += dfs(t) + 1

            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    MEMO = [-1]*N
    MEMO[-1] = 0
    dfs(0)
    koho = [-1]*N
    for s in range(N):
        x = -1
        for t in lines[s]:
            if x < MEMO[t]:
                x = MEMO[t]
                koho[s] = t

    ans = 10**10
    for s in range(N-1):
        for t in lines[s]:
            if LL[s] == 1:
                continue
            MEMO = [-1]*N
            MEMO[-1] = 0
            lines[s].remove(t)
            LL[s] -= 1
            ans = min(ans,dfs(0))
            lines[s].add(t)
            LL[s] += 1
    print(ans)


### FIXED CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1

    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                if MEMO[t] != -1:
                    tmp += MEMO[t] + 1
                else:
                    tmp += dfs(t) + 1
            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    MEMO = [-1]*N
    MEMO[-1] = 0
    dfs(0)
    koho = [-1]*N
    for s in range(N):
        x = -1
        for t in lines[s]:
            if x < MEMO[t]:
                x = MEMO[t]
                koho[s] = t

    ans = 10**10
    for s in range(N-1):
        t = koho[s]
        if LL[s] == 1 or t == -1:
            continue
        MEMO = [-1]*N
        MEMO[-1] = 0
        lines[s].remove(t)
        LL[s] -= 1
        ans = min(ans,dfs(0))
        lines[s].add(t)
        LL[s] += 1
    print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split(' ')))

res = 1

for i in l:
    res *= i

if res > 10**18:
    print('-1')
else:
    print(res)


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split(' ')))

res = 1

l.sort()

for i in l:
    res *= i
    if res > 10**18:
        res = -1
        break

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

s,_,*q=open(0)
a=s[:-1]
p=1
for q in q:p^=q<'2';c=q[-2]*(q>'2');f=(q<'2 2')^p;a=(f^1)*c+a+c*f
print(a[::p or-1])

### FIXED CODE ###

from collections import*
s,_,*q=open(0)
d=deque(s[:-1])
p=1
for q in q:
  try:
    q,f,c=q.split()
    if(f<'2')^p:d+=c,
    else:d.appendleft(c)
  except:p^=1
print(''.join(d)[::p or-1])
### BUGGY CODE ###

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

p = []

for i in range(m):
    p.append(list(map(int, input().split())))

for i in range(m):
    pref = "{:0>6}".format(p[i][0])

    y = 1
    for j in range(m):
        if p[i][0] == p[j][0] and p[i][1] > p[j][1]:
            y += 1

    year = "{:0>6}".format(y)
    print(pref + year)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
p = [list(map(int, input().split()+[i])) for i in range(m)]

p.sort()
cnt = 0
pre = -1

for city in p:
    if city[0] == pre:
        cnt = cnt + 1
    else:
        pre = city[0]
        cnt = 1

    city.append("{:0>6}{:0>6}".format(city[0], cnt))

p.sort(key = lambda x: x[2])

for city in p:
    print(city[3])
### BUGGY CODE ###

if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

    def check_val(H, W, A, target):
        for i in range(H):
            for j in range(W):
                if target == A[i][j]:
                    x = i
                    y = j
                    return x, y
        return 0, 0

    for i in range(Q):
        mp = 0
        stat_LR = LR[i]
        if stat_LR[0] == stat_LR[1]:
            print(mp)
            continue
        stat_x, stat_y = check_val(H, W, A, stat_LR[0])
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
            x, y = check_val(H, W, A, next)
            mp += abs(x - stat_x) + abs(y - stat_y)
            stat_x = x
            stat_y = y
        print(mp)

### FIXED CODE ###

if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

#    def check_val(H, W, A, target):
#        for i in range(H):
#            for j in range(W):
#                if target == A[i][j]:
#                    x = i
#                    y = j
#                    return x, y
#        return -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    d = {}
    for i in range(1, D+1):
        d[str(i)] = 0
    for i in range(D+1, H*W+1):
        d[str(i)] = d[str(i-D)] + \
                    abs(dict_buf[str(i)][0] - dict_buf[str(i-D)][0]) + \
                    abs(dict_buf[str(i)][1] - dict_buf[str(i-D)][1])

    for i in range(Q):
#        mp = 0
#        stat_LR = LR[i]
#        if stat_LR[0] == stat_LR[1]:
#            print(mp)
#            continue
#        stat_x, stat_y = dict_buf[str(stat_LR[0])]
#        next = stat_LR[0]
#        while next != stat_LR[1]:
#            next += D
#            x, y = dict_buf[str(next)]
#            mp += abs(x - stat_x) + abs(y - stat_y)
#            stat_x = x
#            stat_y = y
#        print(mp)
        print(d[str(LR[i][1])] - d[str(LR[i][0])])
### BUGGY CODE ###

#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    asf = set(factrial(e))
    if judge & asf != set():
        pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    judge = judge | asf
# for i in a:
#     if not pc:
#         break
#     asf = set(factrial(i))

#     if judge & asf != set():
#         pc = False
#     judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)
 
        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i
 
    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num
 
    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret
 
sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])
 
for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

def main():
  n,q,*t=map(int,open(0).read().split())
  for v,w in zip(t[::2],t[1::2]):
    if n<2:
      print(min(v,w))
      continue
    s,t,v,w=[],[],[v],[w]
    for i in v:
      s.append(i)
      a=(i+n-2)//n
      if a:v.append(a)
    for j in w:
      t.append(j)
      b=(j+n-2)//n
      if b:w.append(b)
    print(max(set(s)&set(t)))
if __name__=='__main__':
  main()

### FIXED CODE ###

n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
  if n<2:
    print(min(v,w))
    continue
  s,t=set(),set()
  while v:
    s|={v}
    v=(v+n-2)//n
  while w:
    t|={w}
    w=(w+n-2)//n
  print(max(s&t))
### BUGGY CODE ###

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

for i in range(len(a)):
    x = x*a[i]
    
if x > 10**18:
    print('-1')

else:
    print(x)

### FIXED CODE ###

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

a = sorted(a)

if a[0]==0:
    print(0)

else:
    for i in range(n):
        x = x*a[i]
    
        if x > 10**18:
            print('-1')
            break
        if i == n-1:
            print(x)
            break
### BUGGY CODE ###

import sys
input = sys.stdin.readline

W,H=map(int,input().split())
p=[int(input()) for _ in range(W)]
q=[int(input()) for _ in range(H)]
ans=sum(p)*(H+1)+sum(q)*(W+1)
for i in range(W):
  for j in range(H):
    ans-=max(p[i],q[j])
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)
for i in range(W+H):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()
### BUGGY CODE ###

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

ans = 0
for i in range(len(b)):
    if a.count(b[i]) > b[i]:
        ans += a.count(b[i]) - b[i]
    elif a.count(b[i]) < b[i]:
        ans += a.count(b[i])
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
n = len(a)
a.sort()
a.append(-1)
ans = 0
i = 0
while i < n:
    cnt = 1
    while a[i] == a[i+1]:
        cnt += 1
        i += 1
        if i == len(a)-1:
            break
    if cnt > a[i]:
        ans += cnt - a[i]
    elif cnt < a[i]:
        ans += cnt
    i += 1
print(ans)
### BUGGY CODE ###

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

position = 2**(n+2)-3
result = 0
while x > 0:
    position = (position-1)//2
    if x > position:
        x -= position
        result += position//2+1
    x -= 1
    position -= 1
print(result)

### FIXED CODE ###

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

position = 2**(n+2)-3
result = 0
while x > 0:
    position = (position-1)//2
    if x == position*2+1:
        result += position + 1
        x = 0
    elif x == position+1:
        result += position//2 + 1
        x = 0
    elif x > position:
        x -= position
        result += position//2+1
    x -= 1
    position -= 1
print(result)
### BUGGY CODE ###

n = int(input())
print(sum(x for x in range(1,n)))

### FIXED CODE ###

n = int(input())
print((n*(n-1))//2)
### BUGGY CODE ###

import itertools as it

def rain_volume(A, N):
    A_citer = it.cycle(A)
    X = [0]*N
    for i in range(N):
        if i%2 == 0:
            A_p = [next(A_citer) for i in range(N)]
            X = [sum(t) for t in zip(X, A_p)] 
            next(A_citer)
        if i%2 != 0:
            A_m = [-next(A_citer) for i in range(N)]
            X = [sum(t) for t in zip(X, A_m)]
            next(A_citer)
    return X

if __name__ == '__main__':
    N = int(input())
    A = [t for t in map(int, input().split(' '))]
    print(' '.join(map(str, rain_volume(A, N))))

### FIXED CODE ###

def rain_volume(A, N):
    X = [0]*N
    X[0] = sum(A)
    for i, a in enumerate(A):
        if i%2 != 0:
            X[0] -= 2*a
    for i in range(1, N):
        if i != 0:
            X[i] = 2*A[i-1] - X[i-1]
    return X

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split(' ')))

    print(' '.join(map(str, rain_volume(A, N))))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    lh = []
    for i, b in enumerate(B):
        heapq.heappush(lh, [-b, i])

    count = 0
    while len(lh) > 0:
        b, i = heapq.heappop(lh)
        a, b = A[i], B[i]
        c = B[i-1]+B[(i+1) % N]
        if b > a and b >= c:
            d, m = divmod(b-a, c)
            count += d
            B[i] = a+m
            if m != 0:
                heapq.heappush(lh, [-B[i], i])
    # print(*A)
    # print(*B)
    for a, b in zip(A, B):
        if a != b:
            print(-1)
            return

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N):
            a, b, c = B[i-1], B[i], B[(i+1) % N]
            if b > A[i] and b > a+c:
                d, m = divmod(b-A[i], a+c)
                if m == 0:
                    B[i] = A[i]
                    count += d
                else:
                    d, m = divmod(b, a+c)
                    count += d
                    B[i] = m
                flag = True
    # print(*A)
    # print(*B)
    if A != B:
        count = -1

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


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

def main():
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  
  dp=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag[0][0][0]=1
  
  def sushi(c1,c2,c3):    
    if flag[c1][c2][c3]:
      return dp[c1][c2][c3]
    else:
      flag[c1][c2][c3]=1
      tmp=c1+c2+c3
      ans=n/tmp
      if c1>0:
        ans+=c1*sushi(c1-1,c2,c3)/tmp
      if c2>0:
        ans+=c2*sushi(c1+1,c2-1,c3)/tmp
      if c3>0:
        ans+=c3*sushi(c1,c2+1,c3-1)/tmp
      dp[c1][c2][c3]=ans  
      return ans

  #print(dp) 
  print(sushi(c1,c2,c3))      
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  a=c1+c2+c3+1
  b=c2+c3+1
  c=c3+1
  
  dp=[[[0]*a for _ in range(b)] for _ in  range(c)]
  
  for i in range(c):
    for j in range(b-i):
      for k in range(a-i-j):
        tmp=i+j+k
        if tmp==0:
          continue
        else:
          dp[i][j][k]=n/tmp
          if i>0:
            dp[i][j][k]+=i*dp[i-1][j+1][k]/tmp
          if j>0:
            dp[i][j][k]+=j*dp[i][j-1][k+1]/tmp
          if k>0:
            dp[i][j][k]+=k*dp[i][j][k-1]/tmp
  print(dp[c3][c2][c1])
             
if __name__=='__main__':
  main()
### BUGGY CODE ###

import itertools

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
for i in range(n + 1):
    for j in itertools.combinations(range(n), i):
        x = 0
        y = 0
        for z in j:
            x += v[z]
            y += c[z]
        ans = max(ans, x - y)
print(ans)

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
vc = sorted([(v[i] - c[i]) for i in range(n)], reverse=True)
ans = 0
for i in vc:
    if i > 0:
        ans += i
print(ans)
### BUGGY CODE ###

import sys,os,io
input = sys.stdin.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i
A.sort()
ans = [0]*N
from bisect import *
lis = []
cum_max = N

for x,y in A:
  insort(lis,y)
  lis_max,lis_min = lis[-1],lis[0]
  if lis_max==cum_max and len(lis)==lis_max-lis_min+1:
    for y1 in lis:
      ans[y_to_i[y1]] = len(lis)
    cum_max = lis_min-1
    lis = []
print(*ans, sep='\n')


### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
    self.min_y = [N]*n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.min_y[x] = min(self.min_y[x],self.min_y[y])
    self.parents[y] = x

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
uf = UnionFind(N)
uf.min_y = [y for x,y,i in A]
ans = [1]*N
A.sort()
Y = [(i,y) for x,y,i in A]
from heapq import *
heap = []
for u,y in Y:
  atode = []
  for _ in range(len(heap)):
    y1,v = heappop(heap)
    if y<y1:
      heappush(heap,(y1,v))
      break
    uf.union(u,v)
    if uf.parents[v]<0:
      atode.append((uf.min_y[v],v))
  if uf.parents[u]<0:
    heappush(heap,(uf.min_y[u],u))
  for y1,v in atode:
    heappush(heap,(y1,v))
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
import math

n,h = map(int,input().split())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n) :
  a[i],b[i] = map(int,input().split())
  
b.sort(reverse=True)

c = 0
for i in range(n) :
  if b[i] < max(a) :
    break
  h -= b[i]
  c += 1

print(c + math.ceil(h/max(a)))

### FIXED CODE ###

import sys
import math
import bisect

n,h = map(int,input().split())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n) :
  a[i],b[i] = map(int,input().split())
  
b.sort(reverse=True)

c = 0
bs = [b[0]]
am = max(a)
bs_append = bs.append
for i in range(1,n) :
  if b[i] < am :
    break
  bs_append(bs[i-1]+b[i])
  
if b[0] < am :
  print(math.ceil(h/am))
  sys.exit()

if bs[-1] <= h :
  print(len(bs) + math.ceil((h-bs[-1])/am))
else :
  print(bisect.bisect_left(bs,h)+1)
### BUGGY CODE ###

import math
n, m, k = map(int, input().split())

mod = 10**9 + 7


def choose(n,k):
  return (math.factorial(n) // (math.factorial(n - k) * math.factorial(k))) % mod

sum = 0
for i in range(1, n+1):
  for j in range(1, m+1):
    score = i-1 + j-1
    cnt = (n-i+1) * (m-j+1)
    sum += (score * cnt) % mod
    #print((i,j), score, cnt)

for i in range(2, n+1):
  for j in range(1, m):
    score = i-1 + m-j
    cnt = (n-i+1) * j
    sum += (score * cnt) % mod
    #print((i,j), score, cnt)

sum = sum * choose(m*n-2,k-2)
sum = sum % mod
print(sum)



### FIXED CODE ###

import math
n, m, k = map(int, input().split())

mod = 10**9 + 7

def mpow(x, n):
  ans = 1
  while n != 0:
    if n&1:
      ans = ans * x % mod
    x = x * x % mod
    n = n // 2
  return ans

fac = [0] * (n*m+2)
finv = [0] * (n*m+2)
inv = [0] * (n*m+2)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1

for i in range(2, n*m+1):
  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 choose(n,k):
  if n == 0 and k == 0:
    return 1
  if n < 0:
    return 0
  if n < k:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod


sum = 0
for i in range(1, n+1):
  for j in range(1, m+1):
    score = i-1 + j-1
    cnt = (n-i+1) * (m-j+1)
    sum += (score * cnt) % mod
    #print((i,j), score, cnt)

for i in range(2, n+1):
  for j in range(1, m):
    score = i-1 + m-j
    cnt = (n-i+1) * j
    sum += (score * cnt) % mod
    #print((i,j), score, cnt)

sum = sum * choose(m*n-2,k-2)
sum = sum % mod
print(sum)
### BUGGY CODE ###

def main():
    T = input()
    ans = ''
    for t in T:
        if t == '?':
            ans += 'D'
        else:
            ans += t
    print(ans)




if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    T = input()
    print(T.replace('?','D'))



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

import sys
input = sys.stdin.readline
N,Y = map(int,input().split())
flag = 0
for a in range(0,N+1):
    if flag == 1:break
    for b in range(0,N+1):
        if flag == 1:break
        for c in range(0,N+1):
            if flag == 1:break
            if a+b+c == N and a*10000+b*5000+c*1000 == Y:
                print(a,b,c)
                flag = 1
                break
if flag == 0:
    print(-1,-1,-1)

### FIXED CODE ###

N,Y = map(int,input().split())
flag = 0
for a in range(N+1):
    for b in range(N+1):
        if a+b > N:
            break
        elif (N-(a+b))*1000 == Y-(10000*a+5000*b):
            A,B,C = a,b,N-(a+b)
            flag = 1
if flag == 0:print(-1,-1,-1)
else:print(A,B,C)