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


import math


li = list(map(int,input().split()))

def main():

	x = []
	for i in range(li[2]+1):
		x.append(math.floor((li[0]*i)/li[1]) - li[0]*(math.floor(i/li[1])))
	max = 0
	for l in x:
		if l>max:
			max = l
	return(print(max))

      

main()

### FIXED CODE ###

import math
 
A, B, N = map(int, input().split())
 
x = 0
if N < B:
    x = N
else:
    x = B - 1
 
print(math.floor(A * x / B) - A * math.floor(x / B))
### BUGGY CODE ###

import math

A, B, N = map(int, input().split())
max = 0
temp = 0
bk_temp = 0

if B <= N:
    max = math.floor(A * (B - 1) / B) - (A * math.floor((B - 1) / B))
else:
    for i in range(1, N + 1):
        temp = math.floor(A*i/B) - (A * math.floor(i/B))
        # print(str(i) + ' ' + str(temp))
        if bk_temp > temp:
            max = bk_temp
            break
        if max < temp:
            max = temp
        bk_temp = temp

print(max)

### FIXED CODE ###

import math

A, B, N = map(int, input().split())
max = 0
temp = 0
bk_temp = 0

if B <= N:
    max = math.floor(A * (B - 1) / B) - (A * math.floor((B - 1) / B))
else:
    # for i in range(1, N + 1):
    #     temp = math.floor(A*i/B) - (A * math.floor(i/B))
    #     print(str(i) + ' ' + str(temp))
    #     if bk_temp > temp:
    #         max = bk_temp
    #         break
    #     if max < temp:
    #         max = temp
    #     bk_temp = temp
    max = math.floor(A * N / B) - (A * math.floor((N) / B))

print(max)
### BUGGY CODE ###

n=int(input())
l=[]
ans=0
for i in range(n):
  s=str(input())
  if s not in l:
    l.append(s)
    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
  s=str(input())
  l.append(s)
print(len(set(l)))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
ch, cw = mapint()
dh, dw = mapint()
maze = [list(input()) for _ in range(H)]

dirc = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
from collections import deque
from heapq import heappop, heappush
Q = [(0, (ch-1)*(10**4)+cw-1)]

dist = [[10**18]*W for _ in range(H)]
dist[ch-1][cw-1] = 0
ans = 10**18
while Q:
    d, yx = heappop(Q)
    y, x = divmod(yx, 10**4)
    if d>dist[y][x]:
        continue
    dist[y][x] = d
    if y==dh-1 and x==dw-1:
        ans = d
        break
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if (dy, dx) in dirc:
                if dist[ny][nx]>d:
                    heappush(Q, (d, ny*(10**4)+nx))
            else:
                if dist[ny][nx]>d+1:
                    heappush(Q, (d+1, ny*(10**4)+nx))
if ans>=10**17:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def main():
    H, W = mapint()
    ch, cw = mapint()
    dh, dw = mapint()
    maze = [list(input()) for _ in range(H)]
    
    dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))
    magic = ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2))
    from collections import deque
    Q = deque([(ch-1, cw-1)])
    
    dist = [[10**18]*W for _ in range(H)]
    dist[ch-1][cw-1] = 0
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]:
                dist[ny][nx] = dist[y][x]
                Q.appendleft((ny, nx))
        
        for dy, dx in magic:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.append((ny, nx))
    if dist[dh-1][dw-1]>=10**17:
        print(-1)
    else:
        print(dist[dh-1][dw-1])
main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])

l=1
while l<2*(n+2)-1:
	l*=2
l-=1
seg=[True]*l
seg[0]=False

def update(i):
	if seg[i]:
		seg[i]=False
		update((i-1)//2)

update((l-1)//2)
update((l-1)//2+n+1)

def search_left(i,j):
	if j==1:
		if i%2==1:
			return search_left((i-1)//2,1)
		else:
			if seg[i-1]:
				return search_left((i-1)//2,1)
			else:
				return search_left(i-1,0)
	else:
		if i<l//2:
			return search_left(2*i+2-seg[2*i+2],0)
		else:
			return i

def search_right(i,j):
	if j==1:
		if i%2==0:
			return search_right((i-1)//2,1)
		else:
			if seg[i+1]:
				return search_right((i-1)//2,1)
			else:
				return search_right(i+1,0)
	else:
		if i<l//2:
			return search_right(2*i+1+seg[2*i+1],0)
		else:
			return i

ans=0
for i,j in a:
	s=(l//2+1+i)
	p=search_left(s,1)
	q=search_right(s,1)
	ans+=(s-p)*(q-s)*j
	update(s)

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])

l=1
while l<2*(n+2)-1:
	l*=2
l-=1
seg=[True]*l
seg[0]=False

def update(i):
	if seg[i]:
		seg[i]=False
		update((i-1)//2)

update((l-1)//2)
update((l-1)//2+n+1)

def search_left(i,j):
	if j==1:
		if i%2==1:
			return search_left((i-1)//2,1)
		else:
			if seg[i-1]:
				return search_left((i-1)//2,1)
			else:
				return search_left(i-1,0)
	else:
		if i<l//2:
			return search_left(2*i+2-seg[2*i+2],0)
		else:
			return i

def search_right(i,j):
	if j==1:
		if i%2==0:
			return search_right((i-1)//2,1)
		else:
			if seg[i+1]:
				return search_right((i-1)//2,1)
			else:
				return search_right(i+1,0)
	else:
		if i<l//2:
			return search_right(2*i+1+seg[2*i+1],0)
		else:
			return i

ans=0
for i,j in a:
	s=(l//2+1+i)
	p=search_left(s,1)
	q=search_right(s,1)
	ans+=(s-p)*(q-s)*j
	update(s)

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

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

def main():
  N = int(input())
  XY = [tuple(map(int,input().split())) for _ in range(N-1)]
  MOD =10**9+7
  
  E = [[] for _ in range(N)]
  for x,y in XY:
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
  
  # dp[v][c]:根がvである部分木において、vを色cで塗ったときの塗り方のパターン
  # vの子をu1,u2...unとすると、vが白ならuxは白でも黒でもいい。
  # vが黒ならuxは白でないといけない。
  # uxを根とする部分木の塗り方パターン数を掛け合わせたものが、
  # vを根とする部分木の塗り方のパターン数になる。
  dp = [[0 for _ in range(2)] for _ in range(N)]
  def dfs(v,c,s):
    dp[v][c] = 1
    for u in E[v]:
      if u != s:
        if c == 0: #vが白の場合
          dp[v][c] *= (dfs(u,0,v)+dfs(u,1,v))
        else: #vが黒の場合
          dp[v][c] *= dfs(u,0,v)
    #dp[v][c] %= MOD
    return dp[v][c]

  print((dfs(0,0,-1)+dfs(0,1,-1)) % MOD)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def main():
  N = int(input())
  XY = [tuple(map(int,input().split())) for _ in range(N-1)]
  MOD =10**9+7
  
  E = [[] for _ in range(N)]
  for x,y in XY:
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
  
  def dfs(v,s):
    b = 1
    w = 1
    for u in E[v]:
      if u != s:
        b0,w0 = dfs(u,v)
        b *= w0
        w *= (b0+w0)
    #b %= MOD
    #w %= MOD
    return b,w

  b,w = dfs(0,-1)
  print((b+w) % MOD)

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

import sys
input=sys.stdin.readline
from collections import deque
class ctmp():
    def __init__(self,ij,dis):
        self.ij=ij
        self.dis=dis
H,W=map(int,input().split())
ls=["#"*(W+2)]
for i in range(H):
    ls.append("#"+input()+"#")
ls.append("#"*(W+2))
q=deque([])
tmp=ctmp((1,1),0)
q.append(tmp)
df={}
while q:
    tmp=q.popleft()
    df[tmp.ij]=1
    if tmp.ij==(H,W):
        break
    for i in range(4):
        ntmpij=(tmp.ij[0]+(i<2)*(2*i-1),tmp.ij[1]+(i>1)*(2*i-5))
        #print(ntmpij)
        if ntmpij not in df and ls[ntmpij[0]][ntmpij[1]]==".":
            c_tmp=ctmp(ntmpij,tmp.dis+1)
            q.append(c_tmp)

if tmp.ij==(H,W):
    nw=0
    for i in range(1,H+1):
        #for j in range(1,W+1):
         #   if ls[i][j]==".":
          #      nw+=1
        nw+=ls[i].count(".")
    print(nw-tmp.dis-1)
else:
    print(-1)


### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    from collections import deque
    #class ctmp():
    #    def __init__(self,ij,dis):
    #        self.ij=ij
    #        self.dis=dis
    H,W=map(int,input().split())
    ls=["#"*(W+2)]#
    for i in range(H):
        ls.append("#"+input()+"#")
    ls.append("#"*(W+2))#
    q=deque([])
    #qd=deque([])
    #tmp=ctmp((1,1),0)
    q.append((1,1))
    #qd.append(0)
    #df={}
    lf=[[float("inf") for _ in range(W+2)] for _ in range(H+2)]#
    #これでfとdの両方の役割をこなす
    lf[1][1]=0
    while q:
        tmpij=q.popleft()
        #tmpd=qd.popleft()
        #df[tmpij]=1
        if tmpij==(H,W):
            break
        lind=[(-1,0),(1,0),(0,-1),(0,1)]#
        for i in range(4):
            #ntmpij=(tmpij[0]+(i<2)*(2*i-1),tmpij[1]+(i>1)*(2*i-5))
            ntmpij=(tmpij[0]+lind[i][0],tmpij[1]+lind[i][1])
            #print(ntmpij)
            #if ntmpij not in df and ls[ntmpij[0]][ntmpij[1]]==".":
            if lf[ntmpij[0]][ntmpij[1]]==float("inf") and ls[ntmpij[0]][ntmpij[1]]==".":
                #c_tmp=ctmp(ntmpij,tmp.dis+1)
                #q.append(c_tmp)
                q.append(ntmpij)
                #qd.append(tmpd+1)
                lf[ntmpij[0]][ntmpij[1]]=lf[tmpij[0]][tmpij[1]]+1
                #dは訪れる前に書き込んでしまう
    if tmpij==(H,W):
        nw=0
        for i in range(1,H+1):
            #for j in range(1,W+1):
             #   if ls[i][j]==".":
              #      nw+=1
            nw+=ls[i].count(".")
        #print(nw-tmpd-1)
        print(nw-lf[H][W]-1)
    else:
        print(-1)

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

N=int(input())
S=input()


cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            for k in range(j+1,N):
                if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]  and j-i!=k-j:
                    cnt+=1

print(cnt)


### FIXED CODE ###

N=int(input())
S=input()

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

cnt=0
for i in range(N):
    for j in range(i+1,N):
        k=j+j-i
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            cnt+=1

print((r*g*b)-cnt)
### BUGGY CODE ###

from collections import defaultdict

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
for i, s in enumerate(reversed(S)):
    x += int(s) * 10**i
    m = x % 2019
    mp[m] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)



### FIXED CODE ###

from collections import defaultdict
import random

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
y = 1
for i, s in enumerate(reversed(S)):
    x = (x + int(s) * y) % 2019
    y = (y * 10) % 2019
    mp[x] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

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

import sys
sys.setrecursionlimit(10 ** 7)

N = input()

# TLE (Python3 3.4.3)
# AC  (PyPy3 (2.4.0))

# DP
INF = pow(10, 8)
L = len(N)
dp = [[INF] * 2 for _ in range(L+2)]
dp[0][0] = 0

# reverse
N = N[::-1] + '0'


for i in range(L+1):
    n = int(N[i])

    # 更新後のdp
    ni = i + 1

    # 前の桁で繰り下がりなし
    # 同じだけ払う
    dp[ni][0] = min(dp[ni][0], dp[i][0] + n)

    # 繰り下がりあり
    if n > 0:
        dp[ni][1] = min(dp[ni][1], dp[i][0] + (10 - n))
    else:
        dp[ni][0] = min(dp[ni][0], dp[i][0])

    # 前の桁で繰り下がりあり
    n += 1

    # 同じだけ払う
    if n == 10:
        dp[ni][1] = min(dp[ni][1], dp[i][1])
    else:
        dp[ni][0] = min(dp[ni][0], dp[i][1] + n)

    # 繰り下がりあり
    dp[ni][1] = min(dp[ni][1], dp[i][1] + (10 - n))


ans = min(dp[L+1][0], dp[L+1][1])

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = input()

# DP
INF = pow(10, 8)
L = len(N)
dp = [[INF] * 2 for _ in range(L+2)]
dp[0][0] = 0

# reverse
N = N[::-1] + '0'


for i in range(L+1):
    for j in range(2):
        # 繰り下がりも加味
        n = int(N[i])
        n += j

        # 更新後のdp
        ni = i + 1

        # 10通りから探索
        for a in range(10):
            nj = 0
            b = a - n

            # 繰り下がりあり
            if b < 0:
                b += 10
                nj = 1

            dp[ni][nj] = min(dp[i][j] + a + b, dp[ni][nj])

ans = min(dp[L+1][0], dp[L+1][1])

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

#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
*l, = map(int,input().split())
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  s = bin(l[i])[2:]
  for j in range(len(s)):
    lone[j] += int(s[-j-1])
ans = 0
for i in range(60):
  ans += (2**i*lone[i]*(n-lone[i]))%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
l = list(map(int,input().split()))
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  s = bin(l[i])[2:]
  for j in range(len(s)):
    lone[j] += int(s[-j-1])
ans = 0
for i in range(60):
  ans += (2**i*lone[i]*(n-lone[i]))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

a = input().split()

pura = int(a[0])     #1
zero = int(a[1])     #0
mai  = int(a[2])     #-1
num  = int(a[3])     #枚数
total = 0

for i in range(num):
    if pura > 0:
        pura = pura - 1
        total = total + 1
    elif zero > 0:
        zero = zero - 1
        total = total + 0
    elif mai > 0:
        mai = mai - 1
        total = total - 1
print(total)

### FIXED CODE ###

a = input().split()

pura = int(a[0])     #1
zero = int(a[1])     #0
mai  = int(a[2])     #-1
num  = int(a[3])     #枚数
total = 0
k = num-pura-zero

if pura >= num:
    total = num
else:
    total = pura
    if zero >= num - pura:
        total = pura
    else:
        total = pura-(k)
print(total)
### BUGGY CODE ###

def add2(l):
    ys = []
    for i in range(len(l)):
        ys += [l[i] + x for x in l[i+1:]]
    return ys


def add(n, l):
    if not l:
        return []
    elif n == 1:
        return l
    elif n == 2:
        return add2(l)
    else:
        ys = [x for x in add(n, l[1:])]
        ys += [l[0] + x for x in add(n-1, l[1:])]
        return ys


def main():
    n, a = (int(x) for x in input().split())
    xs = [int(x) for x in input().split()]
    tot = sum(xs)

    if n == 1:
        count = len(list(filter(lambda x: x == a, xs)))
    else:
        count = 0
        lop = n // 2 + 1
        for i in range(1, n//2+1):
            ys = add(i, xs)
            count += len(list(filter(lambda x: x == a * i, ys)))
            if n - i > i:
                zs = [tot - x for x in ys]
                count += len(list(filter(lambda x: x == a * (n - i), zs)))
        if sum(xs) == n * a:
            count += 1

    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(n):
    for j in range(2*w+1):
        if 0<=j-x[i]<=2*w:
            dp[i+1,j]=dp[i,j]+dp[i,j-x[i]]
        else:
            dp[i+1,j]=dp[i,j]
print(dp[n,w]-1)
### BUGGY CODE ###

N = int(input())
S = input()
dp = [[0]*N for i in range(N)]
pm = 0
ans = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    if S[i]==S[j]:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1]+1, i-j)
      else:
        dp[i][j] = 1
    else:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1], i-j)
      else:
        dp[i][j] = 0
    if dp[i][j]>ans:
      ans = dp[i][j]
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*N for i in range(N)]
pm = 0
ans = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    if S[i]==S[j]:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1]+1, i-j)
      else:
        dp[i][j] = 1
    else:
      dp[i][j] = 0
    if dp[i][j]>ans:
      ans = dp[i][j]
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
diff = []
total = sum(a)
for i in range(N-1):
    diff.append(abs((sum(a[:i+1]) * 2) - total))
print(min(diff))


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
sunuke = []
diff = []
total = sum(a)
for i, x in enumerate(a[0:-1]):
    if(i==0):
        sunuke.append(x)
    else:
        sunuke.append(x + sunuke[i-1])
for i in sunuke:
    diff.append(abs((i * 2) - total))
print(min(diff))
### BUGGY CODE ###

def resolve():
    N = int(input())
    P = list(map(int, input().split()))

    n = 0
    for i in range(N):
        for j in range(i):
            if P[i] > P[j]:
                break
        else:
            n += 1
    print(n)
    
resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    P = list(map(int, input().split()))

    n = 0
    x = 10 ** 20
    for i in range(N):
        if x >= P[i]:
            x = P[i]
            n += 1
    print(n)

resolve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

#print(5 & 3)
answer = 0
for l in range(0,n):
    p = 0
    for r in range(l,n):
        if p & a[r] != 0:
            break
        else:
            p = p | a[r]
            answer += 1

print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

n =int(input())
a = [int(i) for i in input().split()]
answer = 0
asum = a[0]
xsum = a[0]
r=0
for l in range(0,n):
    while r < n-1:
        asum = asum + a[r+1]
        xsum = xsum ^ a[r+1]
#        print("sum",asum,xsum)
        if asum == xsum:
            r += 1
        else:
            asum = asum - a[r+1]
            xsum = xsum ^ a[r+1]
            break
#    print(l,r)
#    print(answer)
    answer += (r-l + 1)
    asum = asum - a[l]
    xsum = xsum - a[l]

print(answer)
### BUGGY CODE ###

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

for i in range(d):
    t = a.index(max(a))
    a[t] //= 2
    if max(a) == 0:
        break
print(sum(a))

### FIXED CODE ###

import heapq
n, d = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for _ in range(d):
    t = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-t//2))

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

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [None] * N

for i in range(N-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def solve():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        pcounter[node] = counter[node]
        if parent is not None:
            pcounter[node] += pcounter[parent]
        for c in neighbor[node]:
            if pcounter[c] is None:
                stack.append((c, node))

solve()
print(*pcounter, sep=' ')


### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [None] * N
depth = {0: 0}

for i in range(N-1):
    a, b = map(int, input().split())
    a_deper, b_deeper = False, False
    if a in depth and b not in depth:
        depth[b] = depth[a] + 1
    if b in depth and a not in depth:
        depth[a] = depth[b] + 1
    if a in depth and b in depth:
        if depth[a] < depth[b]:
            neighbor[a-1].append(b-1)
        else:
            neighbor[b-1].append(a-1)
    else:
            neighbor[a-1].append(b-1)
            neighbor[b-1].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def solve():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        pcounter[node] = counter[node]
        if parent is not None:
            pcounter[node] += pcounter[parent]
        for c in neighbor[node]:
            if pcounter[c] is None:
                stack.append((c, node))

solve()
print(*pcounter, sep=' ')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    l = list(map(int, input().split()))
    l.append(i)
    lst.append(l)
    i+=1
res=[]
lst.sort()
for i in range(1,n+1):
    j=1
    for k in lst:
        if i == k[0]:
            res.append([k[2],str(k[0]).rjust(6,'0') + str(j).rjust(6,'0')])
            j+=1
#ans
res.sort()
for ans in res:
    print(ans[1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    lst.append(list(map(int, input().split())) + [i])
    i+=1
lst = sorted(lst)
j=0
i=1
for k in lst:
    if i != k[0]:
        i=k[0]
        j=1
        k[1]=i*1000000+j
    else:
        j+=1
        k[1]=i*1000000+j

#ans
for ans in sorted(lst, key=lambda x:x[2]):
    print('{0:012d}'.format(ans[1]))
### BUGGY CODE ###


h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))

blackli = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            blackli.append((i, j))

bp = len(blackli)
dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
tmpblackli = []

while bp != h * w:
    for li in blackli:
        for dx, dy in dd:
            nx = li[1] + dx; ny = li[0] + dy
            if 0 <= nx < w and 0 <= ny < h:
                tmpblackli.append((ny, nx))
    blackli += tmpblackli
    blackli = list(set(blackli))
    ans += 1
    bp = len(blackli)
    tmpblackli = []
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))
que = deque()
dist = [[-1]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            dist[i][j] = 0
            que.append((i, j))


dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
d = 0
while que:
    y, x = que.popleft() #幅優先探索
    d = dist[y][x]
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and dist[ny][nx] == -1:
            dist[ny][nx] = 0
            que.append((ny, nx))
            dist[ny][nx] = d + 1
print(d)
### BUGGY CODE ###

from math import factorial
from operator import mul
from functools import reduce

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r

n,m=map(int,input().split())
mod = 10 ** 9 + 7

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
broken = [int(input()) for i in range(m)]
broken.sort()
broken += [0] * (n-m)
index = 0
mod = 10**9 + 7
for i in range(1,n+1):
  if i==1:
    if i != broken[index]:
      a=1
      b=1
    else:
      a=1
      b=0
      index += 1
  else:
    if i == broken[index]:
      a,b=b,0
      index += 1
    else:
      a,b=b,(a+b)%mod
print(b)
### BUGGY CODE ###

mod=1000000007
n=int(input())
x=list(map(int,input().split()))
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=(x[i]*x[j])%mod
print((ans)%mod)


### FIXED CODE ###

mod=1000000007
n=int(input())
x=list(map(int,input().split()))
cl=[1]
for i in range(1,n):
    cl.append(cl[i-1]+x[i])
sum=0
for i in range(n-1):
    sum+= x[i]*(cl[n-1]-cl[i])
    sum%=mod

print(sum)