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

import copy
N,M = map(int,(input().split()))
x = [0]*M
y = [0]*M
z = [0]*M
line = [[] for _ in range(N+1)]
dot = []
for i in range(M):
    x[i],y[i],z[i] = map(int,(input().split()))
    line[x[i]].append(y[i])
    line[y[i]].append(x[i])
    dot.append(x[i])
    dot.append(y[i])

f = [0]*N
nohint = 0
hint = [0]*(N+1)
for i in range(1,N+1):
    f[i-1] = dot.count(i)
    if f[i-1] == 0:
        nohint += 1
    else:
        hint[i] = 1

not_visit = [False]*(N+1)
for i in range(len(hint)):
    if hint[i] == 1:
        not_visit[i] = True

ans = 0
stack = []
while sum(hint):
    stack.append(hint.index(1))
    while stack:
        now = stack.pop()
        if not_visit[now]:
            hint[now] = 0
            for i in line[now]:
                stack.append(i)
                hint[i] = 0
        not_visit[now] = False
    ans += 1
print(ans + nohint)

### FIXED CODE ###

import copy
N,M = map(int,(input().split()))
x = [0]*M
y = [0]*M
z = [0]*M
line = [[] for _ in range(N+1)]
dot = []

for i in range(M):
    x[i],y[i],z[i] = map(int,(input().split()))
    line[x[i]].append(y[i])
    dot.append(x[i])
    dot.append(y[i])

class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

        if x == y:
            return
        else:
            if self.rank[x] <self.rank[y]:
                self.par[y] += self.par[x] # 負+負でsize管理 
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]: # 負+負でsize管理 
                    self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.par[self.root(x)]

Tree = UnionFind(N)

for i in range(N):
    for j in line[i]:
        Tree.union(i-1,j-1)

nohint = 0
hint = []
for i in range(N):
    if Tree.size(i) == 1:
        nohint += 1
    else:
        hint.append(Tree.root(i))

print(nohint + len(set(hint)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
tmp = []
flag = [0]*N
for i in range(N):
    f = 0
    for j in range(N):
        if i == j:
            continue
        else:
            if A[i]%A[j]==0:
                f=1
    if f == 0:
        ans += 1
    

print(ans)
# print(tmp)
# print(flag)

### FIXED CODE ###

# エラトステネスの篩を使う！O(nloglogn)
N = int(input())
A = list(map(int,input().split()))

listA = [0] * (10**6+10)
ans = 0
for i in A:
    if listA[i] != 0:
            listA[i] = 2
            continue
    for j in range(i,10**6+10,i):
        listA[j] += 1

for i in A:
    if listA[i] == 1:
        ans += 1

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

import sys
N,K=map(int, input().split())
a=list(map(int, input().split()))
sum=0
for i in range(0,N):
  sum+=a[i]
if sum<K:#全部不必要
  print(N)
  sys.exit()
if sum==K:#全部必要
  print(0)
  sys.exit()
a.sort()
a.reverse()

#K未満の最大の数字のラベルはどこ？
l=N
for i in range(N-1,-1,-1):
  if a[i]<K:
    l=i
  else:
    break

if l==N:
  print(0)
  sys.exit()

count=N
#lまでの要素が必要か不要かチェック(使いまわし可能)
sum=0
for j in range(l,N):
  if sum+a[j]<K:
    sum+=a[j]
for i in range(0,l):  
  if sum+a[i]>=K:#必要ってことだ
    count-=1
#lからの要素は自分のことを抜かないといけないことに注意
for i in range(l,N):
  sum=0
  b=a[:]
  C=b.pop(i)
  for j in range(l-1,N-1):
    if sum+b[j]<K:
      sum+=b[j]
  if sum+C>=K:#必要ってことだ
    count-=1
print(count)

### FIXED CODE ###

import sys
N,K=map(int, input().split())
a=list(map(int, input().split()))
sum=0
for i in range(0,N):
  sum+=a[i]
if sum<K:#全部不必要
  print(N)
  sys.exit()
if sum==K:#全部必要
  print(0)
  sys.exit()
a.sort()
a.reverse()
 
#K未満の最大の数字のラベルはどこ？
l=N
for i in range(N-1,-1,-1):
  if a[i]<K:
    l=i
  else:
    break
 
if l==N:
  print(0)
  sys.exit()
 
count=N
#lまでの要素が必要か不要かチェック(使いまわし可能)
sum=0
l_list=[]
for j in range(l,N):
  if sum+a[j]<K:
    sum+=a[j]
    l_list.append(a[j])
for i in range(0,l):  
  if sum+a[i]>=K:#必要ってことだ
    count-=1
#lからの要素は自分のことを抜かないといけないことに注意
for i in range(l,N):
  if a[i] in l_list:
    sum=0
    b=a[:]
    C=b.pop(i)
    for j in range(l-1,N-1):
      if sum+b[j]<K:
        sum+=b[j]
    if sum+C>=K:#必要ってことだ
      count-=1
  else:
    count-=1
print(count)
### BUGGY CODE ###

import sys
x = int(input())
ans = 2
while(True):
    if x*ans == 360:
        print(ans)
        sys.exit()
    ans +=1

### FIXED CODE ###

import sys
x = int(input())
ans = 2
while(True):
    if x*ans % 360 == 0:
        print(ans)
        sys.exit()
    ans +=1
### BUGGY CODE ###

#ABC137_C
N=int(input())
ans=[]
cnt=0
for _ in range(N):
    str_list=input()
    dic={}
    for i in range(10):
        if str_list[i] in dic:
            dic[str_list[i]]+=1
        else:
            dic[str_list[i]]=1
    ans.append(dic)
while len(ans)>1: 
    cnt+=ans.count(ans.pop(0))
print(cnt) 

### FIXED CODE ###

#ABC137_C
from collections import Counter
N=int(input())
S=[input() for i in range(N)]

ctr=Counter()
ans=0

for s in S:
    a=''.join(sorted(list(s)))
    if a in ctr:
        ans+=ctr[a]
    ctr[a]+=1
print(ans)
### BUGGY CODE ###

def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline

    s = readline()
    t = readline()

    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])

    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))


resolve()


### FIXED CODE ###

def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
 
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]
 
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])
 
    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))
 
 
resolve()
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC137 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,num_v, start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-float('inf') for _ in range(num_v)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    flg = 0
    for _ in range(100000):
        update = False
        for i in range(num_v):
            for edge in edges:
                e_from, e_to, e_cost = edge
                if e_from != -float('inf') and dist[e_to] < dist[e_from] + e_cost:
                    dist[e_to] = dist[e_from] + e_cost
                    update = True
        if not update:
            flg = 1
            break
    return dist, flg

n,m,p = LI()
edge = []
for _ in range(m):
    a,b,c = LI()
    edge.append([a-1,b-1,c-p])
d,f = Bellman_Ford(edge,n,0)
if d[-1] < 0:
    print(0)
elif not f:
    print(-1)
else:
    print(d[-1])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC137 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,num_v, start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-float('inf') for _ in range(num_v)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    flg = 0
    for i in range(num_v):
        update = False
        for edge in edges:
            e_from, e_to, e_cost = edge
            if e_from != -float('inf') and visited[e_to] and dist[e_to] < dist[e_from] + e_cost:
                dist[e_to] = dist[e_from] + e_cost
                update = True
        if not update:
            flg = 1
            break
    return dist, flg

n,m,p = LI()
edge = []
f = defaultdict(dict)
for _ in range(m):
    a,b,c = LI()
    edge.append([a-1,b-1,c-p])
    f[b-1][a-1] = 1
visited = [False]*n
def dfs(x):
    visited[x] = True
    for t in f[x].keys():
        if not visited[t]:
            dfs(t)
dfs(n-1)
d,f = Bellman_Ford(edge,n,0)
if not f:
    print(-1)
else:
    print(max(0,d[-1]))
### BUGGY CODE ###

from collections import defaultdict as ddict

n=int(input())
a=[]
dict={}
for i in range(n):
    d=ddict(int)
    s=input()
    for x in s:
        d[x]+=1
    a.append(sorted(d.items()))
#print(a)

count=0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]==a[j]:
            count+=1

print(count)


### FIXED CODE ###

from collections import Counter
n=int(input())
d=Counter()
ans=0
for i in range(n):
    t=str("".join(sorted(input())))
    if t in d:
        ans+=d[t]
    d[t]+=1
print(ans)
### BUGGY CODE ###

N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))

### FIXED CODE ###

N, M, P = map(int, input().split())
E = [[] for _ in range(M)]
for i in range(M):
  a, b, c = map(int, input().split())
  E[i] = [a - 1, b - 1, c]
D = [None] * N
D[0] = 0
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
_D = D[-1]
for _ in range(N):
  for a, b, c in E:
    if D[a] == None:
      continue
    if D[b] == None:
      D[b] = D[a] + c - P
    else:
      D[b] = max(D[b], D[a] + c - P)
if D[-1] > _D:
  print(-1)
else:
  print(max(D[-1], 0))
### BUGGY CODE ###

# coding: utf-8
import numpy as np

n, m = map(int, input().split())
l = [int(n) for n in input().split()]
arr = np.asarray(l)

for j in range(m):
    i = np.argmax(l)
    l[i] = int(l[i]/2)
    if l[i] <= 0:
        l.remove(l[i])
        if len(l) == 0:
            break

print(sum(l))



### FIXED CODE ###

# coding: utf-8
import heapq

n, m = map(int, input().split())
l = [ -1 * int(n) for n in input().split()]

heapq.heapify(l)

for i in range(m):
    a = heapq.heappop(l) * (-1)
    a = int(a/2)
    if a != 0:
        heapq.heappush(l, a * (-1))
    if len(l) == 0:
        break
    
    
print(sum(l) * (-1))
### BUGGY CODE ###

X, K, D = list(map(int, input().split()))

for i in range(K):
    if (abs(X) > D):
        X = abs(X) - D
    else:
        if ((K - i) % 2 == 0):
            break
        else:
            X = X - D
            break

print(abs(X))


### FIXED CODE ###

X, K, D = list(map(int, input().split()))

syou = abs(X) // D


if (K > syou):
    K = K - syou
    if ((K % 2) == 0):
        print(abs(abs(X) - D * syou))
    else:
        print(abs(abs(X)-D*(syou+1)))
else:
    print(abs(abs(X)-D*K))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
L = [(a, i+1) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*(n+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n+1):
  for j in range(n+1-i):
    a, idx = L[i+j-1]
    if i:
      dp[i][j] = max(dp[i][j], dp[i-1][j]+a*(idx-i))
    if j:
      dp[i][j] = max(dp[i][j], dp[i][j-1]+a*(n+1-j-idx))
ans = 0
for i in range(n+1):
  ans = max(ans, dp[i][n-i])
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import collections
N=int(input())
A=list(map(int,input().split()))
c = collections.Counter(A)
ans=0
n=len(set(A))
for i in range(n):
    a=int(c.most_common()[i][0])
    b=c.most_common()[i][1]
    if a <= b:
        ans+=b-a
    else:
        ans+=b
print(ans)

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
c = collections.Counter(A)
ans=0
n=len(set(A))
c_=c.most_common()
for i in range(n):
    a=int(c_[i][0])
    b=c_[i][1]
    if a <= b:
        ans+=b-a
    else:
        ans+=b
print(ans)
### BUGGY CODE ###

n=int(input())
a=input().split()
l0=[]
sums=[1 for i in range(30)]
for i in range(n):
  newl=[]
  k=int(a[i])
  for j in range(30):
    if k%2==0:
      newl.append(0)
      k/=2
    else:
      newl.append(1)
      sums[j]*=-1
      k=(k-1)/2
  l0.append(newl)
      
for i in range(n):
  ans=0
  for j in range(30):
    if sums[j]==1:
      if l0[i][j]==1:
        ans+=2**j
    else:
      if l0[i][j]==0:
        ans+=2**j
  print(ans,end=" ")
print("")

### FIXED CODE ###

n=int(input())
a=input().split()
nl=[]
jo=0
for i in range(n):
  nl.append(int(a[i]))
  jo=jo^int(a[i])

for i in range(n):
  ans=nl[i]^jo
  print(ans,end=" ")
print("")
### BUGGY CODE ###

n = int(input())

if n == 1:
  print(0)
elif n == 2:
  print(2)
else:
  sn = n*"9"
  count = 0
  for i in range(1,int(sn)+1):
    check = str(i).zfill(n)
    if "0" in check and "9" in check:
      count += 1
  print(count%(10**9+7))

### FIXED CODE ###

n = int(input())
count = 10**n - 9**n - 9**n +8**n
print(count%(10**9+7))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(200001)


def dfs1(v, p):
    global parent, subtree_count, links
    parent[v] = p
    stc = subtree_count[v]
    cnt = 1
    for u in links[v]:
        if u == p:
            continue
        result = dfs1(u, v)
        stc[u] = result
        cnt += result
    return cnt


def dfs2(v, pc):
    # pc: vを根とした時の、parent方面の部分木のノード数
    global ans, parent, subtree_count

    if len(subtree_count[v]) == 0:
        return

    p = parent[v]
    children, st_counts = map(list, zip(*subtree_count[v].items()))
    children.append(p)
    st_counts.append(pc)
    cl = len(st_counts)
    ct = sum(st_counts)

    for u, stc in subtree_count[v].items():
        dfs2(u, ct - stc + 1)

    if cl == 1:
        return

    tmp = 0
    for stc in st_counts:
        tmp = (tmp + d2s[ct - stc]) % MOD
    tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
    ans = (ans + (1 - tmp) * d2) % MOD


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
parent = [-1] * n
subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
MOD = 10 ** 9 + 7
d2 = 500000004  # 2^-1 mod 10**9+7
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
ans = 0
dfs1(root, -1)
# print(parent)
# print(subtree_count)
dfs2(root, 0)
print(ans)


### FIXED CODE ###

import sys


def dfs1(root, links):
    parent = [0] * n
    subtree_count = [{} for _ in range(n)]
    q = [(root, -1, 0)]  # 2番目:親  3番目:0=初, 1=全ての子巡回後
    while q:
        v, p, t = q.pop()
        if t == 0:
            parent[v] = p
            q.append((v, p, 1))
            for u in links[v]:
                if u == p:
                    continue
                q.append((u, v, 0))
        elif p != -1:
            subtree_count[p][v] = sum(subtree_count[v].values()) + 1
    return parent, subtree_count


def dfs2(root, parent, subtree_count, d2, d2s):
    ans = 0
    q = [(root, 0)]
    while q:
        v, pc = q.pop()

        if len(subtree_count[v]) == 0:
            continue

        p = parent[v]
        children, st_counts = map(list, zip(*subtree_count[v].items()))
        children.append(p)
        st_counts.append(pc)
        cl = len(st_counts)
        ct = sum(st_counts)

        for u, stc in subtree_count[v].items():
            q.append((u, ct - stc + 1))

        if cl == 1:
            continue

        tmp = 0
        for stc in st_counts:
            tmp = (tmp + d2s[ct - stc]) % MOD
        tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
        ans = (ans + (1 - tmp) * d2) % MOD
    return ans


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
MOD = 10 ** 9 + 7
d2 = 500000004  # 2^-1 mod 10**9+7
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
parent, subtree_count = dfs1(root, links)
# print(parent)
# print(subtree_count)
ans = dfs2(root, parent, subtree_count, d2, d2s)
print(ans)
### BUGGY CODE ###

S=input()
ans=0
N=len(S)
for i in range(N-2):
  for j in range(i+4,N+1):
    if int(S[i:j])%2019==0:
      ans+=1
print(ans)

### FIXED CODE ###

S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)
### BUGGY CODE ###

inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def rmod(i,qb,qw):
    numer = (two2i[i] - qb + qw) % R
    denom = two2i[i+1]
    iden = modinv(denom, R)
    ddprint("num {} den {} idn {}".format(numer, denom, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))
two2i = [1] * (b+w+2)
for i in range(1,b+w+2):
    x = (2*two2i[i-1])
    two2i[i] = x if x < R else x-R
cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb) % R
    qw = 0 if i<w else 1 if i==w else (2*qw+cw) % R
    cb = 1 if i<b else ((cb*i) * modinv(i-b+1, R)) % R
    cw = 1 if i<w else ((cw*i) * modinv(i-w+1, R)) % R
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw))


### FIXED CODE ###

inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9 + 7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def pw(x,e):
    if e==0:
        return 1
    elif e%2==0:
        return (pw(x,e//2)**2)%R
    else:
        return (x * pw(x,e//2)**2)%R

def rmod(i,qb,qw):
    global two2i, itwo2i
    numer = (two2i[i] - qb + qw)
    iden = itwo2i[i+1]
    ddprint("num {} idn {}".format(numer, iden))
    return (numer*iden)%R

b,w = inm()
ddprint("b {} w {}".format(b,w))

inv2 = modinv(2,R)
fact = [1] * (b+w+2)
for i in range(2,b+w+1):
    fact[i] = (i*fact[i-1])%R
ifact = [1] * (b+w+2)
ifact[b+w] = modinv(fact[b+w],R)
for i in range(b+w-1,0,-1):
    ifact[i] = ((i+1)*ifact[i+1])%R
two2i = [1] * (b+w+2)
itwo2i = [1] * (b+w+2)
itwo2i[1] = inv2
for i in range(1,b+w+1):
    x = (2*two2i[i-1])
    two2i[i] = x if x < R else x-R
    itwo2i[i] = (inv2*itwo2i[i-1]) % R
ddprint(fact[0:5])
ddprint(ifact[0:5])

cb = cw = 1
qb = qw = 0
print(500000004)
for i in range(1,b+w):
    qb = 0 if i<b else 1 if i==b else (2*qb+cb) % R
    qw = 0 if i<w else 1 if i==w else (2*qw+cw) % R
    cb = 1 if i<b else (fact[i]*ifact[b-1]*ifact[i-b+1]) % R
    cw = 1 if i<w else (fact[i]*ifact[w-1]*ifact[i-w+1]) % R
    ddprint("i {} cb {} cw {} qb {} qw {}".format(i,cb,cw,qb,qw))
    print(rmod(i,qb,qw))
### BUGGY CODE ###

n,m,k=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
A=n*m
v=cmb(A-2,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m
for i in range(1,m):
  y+=i*(m-i)*n*n

ans=v*(t+y)
print(ans%mod)

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=10**9+7
A=n*m-2
from math import factorial
def Comb(N, K):
    a = factorial(N) % mod
    b = factorial(K) % mod
    c = factorial(N-K) % mod
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
v=Comb(A,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m%mod
for i in range(1,m):
  y+=i*(m-i)*n*n%mod

ans=v*(t+y)
print(ans%mod)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
A = []
B = []
ans = 0
for _ in range(N):
    i = list(map(int,input().split()))
    A.append(i[0])
    B.append(i[1])
while M != 0:
    if M - B[A.index(min(A))] >= 0:
        M -= B[A.index(min(A))]
        ans = ans + A[A.index(min(A))]*B[A.index(min(A))]
        B[A.index(min(A))] -= B[A.index(min(A))]
    else:
        ans = ans + A[A.index(min(A))]*M
        M = 0
        B[A.index(min(A))] = 0
    if B[A.index(min(A))] <= 0:
        B.pop(A.index(min(A)))
        A.pop(A.index(min(A)))
print(ans)

### FIXED CODE ###

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

AB = [list(map(int,input().split())) for i in range(N)]
AB.sort()
ans = 0
for _ in range(N):
    if AB[_][1] >= M:
        ans += AB[_][0]*M
        break
    else:
        ans += AB[_][0]*AB[_][1]
        M -= AB[_][1]
print(ans)