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

a,b=map(int,input().split())
ans=0
for i in range(a+1):
    for j in range(a+1):
        for k in range(a+1):
            if i+j+k==b:
                ans+=1
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
c=0
for i in range(a+1):
  for j in range(a+1):
    z=b-(i+j)
    if 0<=z<=a:
      c+=1
print(c)
### BUGGY CODE ###

import math
n = int(input())

rtn = math.floor(math.sqrt(n))

for i in range(rtn,n+1):
    if n % i == 0:
        print(len(str(i)))
        exit()

### FIXED CODE ###

import math
n = int(input())

# def is_prime(n):
#     if n == 1:
#         return False
#     for i in range(2,int(n**0.5)+1):
#         if n % i == 0:
#             return False
#     return True

# if is_prime(n):
#     print(len(str(n)))
#     exit()

# rtn = math.floor(math.sqrt(n))

# for i in range(rtn,n+1):
#     if n % i == 0:
#         print(len(str(i)))
#         exit()

# n = a * b = b * aでなのでa<=bのaの方を求めてその時のbの桁数出力すれば間に合う。
# 上記のようにbの方から求めるとぎり間に合わない。

rtn = math.ceil(math.sqrt(n))
for i in reversed(range(1, rtn + 1)):
    if n % i == 0:
        b = n // i #求めるのはa(=i)ではなくbの方
        print(len(str(b)))
        exit()
### BUGGY CODE ###

from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = [[] for n in range(vertice)]
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i].append(j)
    weight[i].update({j:w})
#print(weight,link)
for v in range(vertice):
    goal = v
    queue = []
    heapq.heappush(queue,[0,source])
    went = set()

    while queue != []:
        #print(queue)
        now_cost,here = heapq.heappop(queue)
        #print(now_cost,here,queue)
        if here == goal:
            print(now_cost)
            break

        can_go = link[here]
        not_went = set(can_go) - went
        #print(v,here,now_cost,not_went,queue)
        for nw in not_went:
            next_cost = now_cost + weight[here][nw]
            heapq.heappush(queue,(next_cost,nw))
        went = went | {here}
    else:
        print("INF")

### FIXED CODE ###

import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
from collections import defaultdict
vertices, edges, start = map(int, readline().split())
connect = defaultdict(list)
cost = defaultdict(dict)
answer = ["INF" for n in range(vertices)]
for _ in range(edges):
    s, t, w = map(int, readline().split())
    connect[s].append(t)
    cost[s].update({t:w})
 
 
now = start
weight = 0
p_queue = []
heappush(p_queue, (0, now))
visited = set()
while p_queue:
    weight, now = heappop(p_queue)
    if now in visited:
        continue
    visited |= {now}
    answer[now] = weight
    for c in connect[now]:
        if c not in visited:
            heappush(p_queue, (weight + cost[now][c], c))
for a in answer:
    print(a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

dp=dict()
dp[0]=[0]*(W+1)
for i in range(1,N+1):
    w,v=map(int,input().split())
    tmp=dp[i-1][:w]
    for j in range(w,W+1):
        tmp.append(max(dp[i-1][j],dp[i-1][j-w]+v))
    dp[i]=tmp
   
print(max(dp[N]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * 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.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

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

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


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

tk=UnionFind(n)

kk=[[False] * n for _ in range(n)]

ans=[n-1]*n
for _ in range(m):
    a,b=map(int, input().split())
    kk[a-1][b-1]=True
    kk[b-1][a-1]=True
    tk.union(a-1, b-1)

for _ in range(k):
    c,d=map(int, input().split())
    kk[c-1][d-1]=True
    kk[d-1][c-1]=True

for i in range(n):
    tmp=tk.members(i)
    ans=-1
    for val in tmp:
        if not kk[i][val]:
            ans+=1
    print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

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

tk=UnionFind(n)

stk=[0 for _ in range(n)]
blk=[[] for _ in range(n)]

for _ in range(m):
    a,b=map(int, input().split())
    stk[a-1]+=1
    stk[b-1]+=1
    tk.union(a-1, b-1)

for _ in range(k):
    c,d=map(int, input().split())
    blk[c-1].append(d-1)
    blk[d-1].append(c-1)

for i in range(n):
    ans=tk.get_size(i)-1-stk[i]
    for j in blk[i]:
        if tk.is_same(i, j):
            ans-=1
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
q = int(input())
ql = []
R = 0
for _ in range(q):
    l,r = map(int, input().split())
    ql.append((l,r))
    R = max(R,r)
R += 1

primes = [2]
for n in range(3,R+1,2):
    flag = True

    for p in primes:
        if n%p==0:
            flag = False
            break
        if n<p*p:
            break

    if flag:
        primes.append(n)

like2017 = [0]*(R+1)
for i in range(R):
    if i%2==1 and (i in primes) and ((i+1)//2 in primes):
        like2017[i+1] = like2017[i] + 1
    else:
        like2017[i+1] = like2017[i]

for (l,r) in ql:
    print(like2017[r+1] - like2017[l])


### FIXED CODE ###

def sieve(n):
    res = list(range(n+10)) # nが小さい時よう
    res[0] = -1
    res[1] = -1
    i = 2
    while i*i<n:
        if res[i]<i:
            i += 1
            continue
        j = i*i
        while j<n:
            if res[j]==j:
                res[j] = i
            j += i
        i += 1
    return res

s = sieve(10**5+10)
acc = [0]*(10**5+10)
for i in range(2,10**5+9):
    if i%2==1 and s[i]==i and s[(i+1)//2]==(i+1)//2:
        acc[i+1] = acc[i]+1
    else:
        acc[i+1] = acc[i]

q = int(input())
res = [0]*q
for i in range(q):
    l,r = map(int, input().split())
    res[i] = acc[r+1]-acc[l]

for r in res:
    print(r)
### BUGGY CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n
tmp = 0

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid


### FIXED CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid

print(high)
sys.stdout.flush()
s = input()
if s[0] == "V":
    exit()
else:
    print(low)
    sys.stdout.flush()
    s = input()
    exit()
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A_dic = defaultdict(int)
B_dic = defaultdict(int)
C_dic = defaultdict(int)

for i in A:
  A_dic[i] += 1
  B_dic[i] = 1

for i in range(N):
  if B_dic[A[i]] == 1:
    B_dic[A[i]] -= 1
    A_dic[A[i]] -= 1
    C_dic[A[i]] += sum([(i*(i-1))//2 for i in list(A_dic.values()) if i >= 2])
    print(C_dic[A[i]])
    A_dic[A[i]] += 1
  else:
    print(C_dic[A[i]])

### FIXED CODE ###

from collections import defaultdict

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

for i in A:
  A_dic[i] += 1

S = sum([(i*(i-1))//2 for i in list(A_dic.values()) if i >= 2])

for i in range(N):
  print(S - A_dic[A[i]] + 1)
### BUGGY CODE ###

n = int(input())
i=0
while True:
  n = n//2
  i += 1
  if n == 1:
    break

ans = 0
for j in range(i+1):
  ans += 2**j

print(ans)

### FIXED CODE ###

n = int(input())

# i = format(n, 'b')[::-1].find('1')
ans = 0
k = 1
while True:
  n //=2
  ans += k
  k *= 2
  if n == 1:
    print(ans+k)
    break
  elif n < 1:
    print(ans)
    break
### BUGGY CODE ###

import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
used=set()
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))
    used.add(L-1)
    used.add(R-1)

q=queue.Queue()
dist=[-1]*N
dist[0]=0

while used!=set():
    q.put(used.pop())
    while not q.empty():
        From=q.get()
        if From in used:
            used.remove(From)
        for l in s[From]:
            To,w=l
            if dist[To]==-1:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")

### FIXED CODE ###

import queue
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))

q=queue.Queue()
dist=[None]*N

for i in range(N):
    if dist[i]==None:
        dist[i]=0
        q.put(i)
    while not q.empty():
        From=q.get()
        for l in s[From]:
            To,w=l
            if dist[To]==None:
                dist[To]=dist[From]+w
                q.put(To)
            else:
                if dist[To]!=dist[From]+w:
                    print("No")
                    exit()
print("Yes")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


H, N = zz()
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = zz()
# dp = [0]*(H+max(A)+1)  # dp[i]: HPをi減らすのに必要な最低の魔力
dp = np.zeros(H+max(A)+1, np.int32)
arg_min = np.argmin(A)
dp[:min(A)+1] = B[arg_min]

for i in range(min(A)+1, H + max(A)):
    dp[i] = min(dp[i - a] + b for a, b in zip(A, B))

print(min(dp[H:H+max(A)]))
# print((dp[H:H+max(A)]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
from itertools import accumulate
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


H, N = zz()
A, B = [], []
for i in range(N):
    a, b = zz()
    A.append(a)
    B.append(b)
# B, A = zip(*sorted(zip(B, A)))

max_a = max(A)
dp = [[100000000]*(H + max_a + 1)] * (N+1)  # dp[i][j]: 魔法i種類で、HPをj減らすのに必要な魔力
#  初期化
for j in range(H):
    if (j % A[0] == 0):
        dp[0][j] = (j//A[0])*B[0]
    else:
        dp[0][j] = (j//A[0]+1)*B[0]
# print(dp)
# print()

for j in range(1, H + max_a + 1):
    for i in range(0, N):

        if(j < A[i]):
            dp[i][j] = min(dp[i-1][j], B[i])
        else:
            # if (j > 8):
            #     print(dp[i - 1][j],
            #           dp[i][j - A[i]] + B[i],
            #           dp[i-1][j-A[i]] + B[i])

            dp[i][j] = min(dp[i - 1][j],
                           dp[i][j - A[i]] + B[i],
                           dp[i-1][j-A[i]] + B[i])


# print(dp)
print(dp[N-1][H])
### BUGGY CODE ###

N = int(input())
from collections import Counter
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
h = []
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    heappush(h,(-ca[i]-cb[i],i))
lis = [[] for _ in range(N+1)]
while len(h):
  cnt, n = heappop(h)
  cnt2, n2 = heappop(h)
  if ca[n]>0:
    ca[n] -= 1
    cnt += 1
    lists = []
    while cb[n2]==0:
      lists.append((cnt2,n2))
      cnt2, n2 = heappop(h)
    for cnt3, n3 in lists:
      heappush(h,(cnt3,n3))
    cb[n2] -= 1
    cnt2 += 1
    lis[n].append(n2)
    if cnt<0:
      heappush(h,(cnt,n))
    if cnt2<0:
      heappush(h,(cnt2,n2))
  else:
    cb[n] -= 1
    cnt += 1
    lists = []
    while ca[n2]==0:
      lists.append((cnt2,n2))
      cnt2, n2 = heappop(h)
    for cnt3, n3 in lists:
      heappush(h,(cnt3,n3))
    ca[n2] -= 1
    cnt2 += 1
    lis[n2].append(n)
    if cnt<0:
      heappush(h,(cnt,n))
    if cnt2<0:
      heappush(h,(cnt2,n2))
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)

### FIXED CODE ###

N = int(input())
from collections import Counter
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [set() for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].add(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

def update_cnt(cnt_,r):
  cnt_[r] -= 1
  if cnt_[r]==0:
    del cnt_[r]

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      update_cnt(cb,q)
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      update_cnt(ca,q)
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    update_cnt(ca,p)
    update_cnt(cb,q)
    cnts[ca[p]+cb[p]].add(p)
    cnts[ca[q]+cb[q]].add(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)
### BUGGY CODE ###

#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 100, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        i1 = i * nn
        S1[i] = set(S[j] for j in range(i1, min(N, i1+nn)))

    ans = []
    rebuild = set()
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            i1 = i // nn
            S[i] = j
            rebuild.add(i1)
        elif cmd == "2":
            j = int(j)

            for i1 in rebuild:
                i2 = i1 * nn
                S1[i1] = set(S[k] for k in range(i2, min(N, i2+nn)))

            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set()
                ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

    print(*ans, sep="\n")

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

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

from decimal import Decimal

def get_primes(n):
	divs = defaultdict(int)
	if n == 0: return divs
	for i in [2,5]:
		c = 0
		while n % i == 0:
			n = n // i
			c += 1
		if c > 0:
			divs[i] = c
	return divs

L = 10**9
N = ri()
A = []
for i in range(N):
	d = Decimal(rs())
	A.append(int(d*L))
#print(A)

R = [0] * N
for i, a in enumerate(A):
	R[i] = A[i] % L
#print(R)

M = 18
K = 0
C = []
D = []
for i in range(N):
	r = R[i]
	a = A[i]
	if r > 0:
		ps = get_primes(a)
		C.append([min(ps[2], M), min(ps[5], M)])
	else:
		ps = get_primes(a)
		D.append([min(ps[2], M), min(ps[5], M)])
#print('C',C)
#print('D',D)

h = defaultdict(int)
ans0 = 0
for c in C:
	d = [M-c[0], M-c[1]]
	i, j = d[0], d[1]
	for i in range(d[0], M+1):
		for j in range(d[1], M+1):
			if (i, j) in h:
				ans0 += h[(i,j)] - (c == (i,j))
	h[tuple(c)] += 1

ans1 = len(D)*(len(D)-1)//2

ans2 = 0
for c in D:
	d = [M-c[0], M-c[1]]
	for i in range(d[0], M+1):
		for j in range(d[1], M+1):
			if (i, j) in h:
				ans2 += h[(i,j)] - (c == (i,j))
#print(ans0, ans1, ans2)
ans = ans0 + ans1 + ans2
print(ans)


### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

from decimal import Decimal

def gcd(a, b):
	return gcd(b, a%b) if b else a

L = 10**9
LL = 10**18
N = ri()
A = []
for i in range(N):
	d = Decimal(rs())
	A.append(int(d*L))

h = defaultdict(int)
for i in range(N):
	g = gcd(A[i], LL)
	h[g] += 1

ans = 0
for g, c in h.items():
	for g2, c2 in h.items():
		if g == g2:
			if g*g % LL == 0:
				ans += c*(c-1)//2
		elif g < g2:
			if g*g2 % LL == 0:
				ans += c * c2
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
mod=10**9+7
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
root=-1
l=-1
for i in range(n):
    if len(edges[i])>l:
        root=i
        l=len(edges[i])
C=[[] for _ in range(n)]

def fill_C(v,par):
    for c in edges[v]:
        if c==par:
            continue
        C[v].append(c)
        fill_C(c,v)
fill_C(root,-1)

DP=[[-1,-1] for _ in range(n)]

def white(v):
    if DP[v][0]!=-1:
        return DP[v][0]
    res=1
    for c in C[v]:
        res*=white(c)+black(c)
        res%=mod
    DP[v][0]=res
    return res
def black(v):
    if DP[v][1]!=-1:
        return DP[v][1]
    res=1
    for c in C[v]:
        res*=white(c)
        res%=mod
    DP[v][1]=res
    return res

print((black(root)+white(root))%mod)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
mod=10**9+7
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
root=-1
l=-1
for i in range(n):
    if len(edges[i])>l:
        root=i
        l=len(edges[i])
C=[[] for _ in range(n)]

def fill_C(v,par):
    for c in edges[v]:
        if c==par:
            continue
        C[v].append(c)
        fill_C(c,v)
fill_C(root,-1)

DP=[[-1,-1] for _ in range(n)]

def white(v):
    if DP[v][0]!=-1:
        return DP[v][0]
    res=1
    for c in C[v]:
        res*=white(c)+black(c)
        res%=mod
    DP[v][0]=res
    return res
def black(v):
    if DP[v][1]!=-1:
        return DP[v][1]
    res=1
    for c in C[v]:
        res*=white(c)
        res%=mod
    DP[v][1]=res
    return res

print((black(root)+white(root))%mod)
### BUGGY CODE ###

import numpy as np
n, k = map(int,input().split())
p = [(int(a) * (int(a)+1) / 2 / int(a)) for a in input().split()]
s = np.array(p)
max_index = 0
max_sum = 0
for i in range(n-k+1):
  t = np.sum(s[i:i+k])
  if max_sum < t:
    max_sum = t
    max_index = i

print(max_sum)


### FIXED CODE ###

n, k = map(int,input().split())
i = 0
kitaichi = [0] * n
kitaichi_sum = [0] * n
ans = 0
for p in input().split():
  kitaichi[i] = int(p) * (int(p)+1) / 2 / int(p)
  if i == 0:
    kitaichi_sum[i] = kitaichi[i]
  elif i >= k:
    kitaichi_sum[i] = kitaichi_sum[i-1] + kitaichi[i] - kitaichi[i-k]
    if kitaichi_sum[i] > ans:
      ans = kitaichi_sum[i]
  else:
    kitaichi_sum[i] = kitaichi_sum[i-1] + kitaichi[i]
  if kitaichi_sum[i] > ans:
    ans = kitaichi_sum[i]
  i += 1
print(ans)