Harryxun/stf_run huggingface dataset:
def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2:
            ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    # print(a_cnt,ab_cnt,ans)
print(ans)

### FIXED CODE ###

def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u

s=input()
all_hatena = s.count('?')

a_cnt = 0
ab_cnt = 0
hatena_cnt = 0
ans = 0

MOD = 10**9+7
for si in s:
    if si == 'A':
        a_cnt += 1
    elif si == 'B':
        ab_cnt += a_cnt*pow(3,all_hatena,MOD)
        if all_hatena >= 1:
            ab_cnt += hatena_cnt*pow(3,all_hatena-1,MOD)
    elif si == 'C':
        ans += ab_cnt
    else:
        ans += ab_cnt*modinv(3,MOD)
        ab_cnt += a_cnt*pow(3,all_hatena-1,MOD)
        if all_hatena >= 2:
            ab_cnt += hatena_cnt*pow(3,all_hatena-2,MOD)
        hatena_cnt += 1
    ab_cnt%=MOD
    ans%=MOD
    # print(a_cnt,ab_cnt,ans)
print(ans)
a, b, c, d = map(int, input().split())
    if abs(a-c) <= d or (abs(a-b) <= d && abs(b-c) <= d):
    	print('Yes')
    else:
       	print('No')

### FIXED CODE ###

a, b, c, d = map(int, input().split())
if abs(a-c) <= d or (abs(a-b) <= d and abs(b-c) <= d):
    print('Yes')
else:
    print('No')
n,m=map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == 1:
    a_list.append(X[i][0])
  elif X[i][0] == n:
    b_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_dic = {a_list}&{b_list}
if len(c_dic) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

### FIXED CODE ###

n,m = map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_set = set(a_list) & set(b_list)
if len(c_set) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")
K, S = map(int, input().split())
count = 0
for X in range(K+1):
  for Y in range(K+1):
    for Z in range(K+1):
      if X + Y + Z = S:
        count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z and z <= k:
      count += 1
print(count)
numpy as np

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

A = np.empty(N)
B = np.empty(N)

for i in range(N):
    INPUT_AB = input()
    A[i] = int(INPUT_AB.split(" ")[0])
    B[i] = int(INPUT_AB.split(" ")[1])

num_drink = 0
drink_price = 0

while num_drink < M:
    price = np.amin(A)
    store_index = np.argmin(A)
    num_drink += B[store_index]
    print(num_drink)
    if num_drink >= M:
        num_drink -= B[store_index]
        while num_drink < M:
            num_drink += 1
            drink_price += price
        
    else:
        drink_price += price * B[store_index]
        A = np.delete(A, store_index)
        B = np.delete(B, store_index)

print(drink_price)

### FIXED CODE ###

# 2150 start

import numpy

N,M=map(int, input().split())
price = numpy.empty((N,3))
sumcan = 0
sumprice = 0
lastshop = 0

for i in range(N):
    shop_data = input().split()
    A = int(shop_data[0])
    B = int(shop_data[1])
    price[i,0]= A * B
    price[i,1] = A
    price[i,2] = B

price = price[price[:,1].argsort(),:]

for j in range(M):
    sumcan = sumcan + price[j,2]
    if sumcan < M:
        sumprice = sumprice + price[j,0]
    elif sumcan >= M:
        sumcan = sumcan - price[j,2]
        lastshop = j
        break

sumprice = sumprice + (M - sumcan)*price[lastshop,1]

print(int(sumprice))
N, K = map(int, input().split())
S = input()

arr = []
cnt = 0
comp = S[0]
for s in S:
    if s==comp:
        cnt += 1
    else:
        if comp=='0':
            arr.append(-cnt)
        else:
            arr.append(cnt)
        cnt = 1
        comp = s
if comp=='0':
    arr.append(-cnt)
else:
    arr.append(cnt)

def iter(A, cnt):
    if cnt>=K or len(A)<2:
        return max(A)
    elif len(A)==2:
        return abs(A[0]) + abs(A[1])
    m = -A[0]+A[1]
    args = [-1]
    for i in range(len(A)-2):
        s3 = A[i] - A[i+1] + A[i+2]
        if m<s3:
            m = s3
            args = [i]
        elif m==s3:
            args.append(i)
    s3 = A[-2]-A[-1]
    if m<s3:
        m = s3
        args = [len(A)-1]
    elif m==s3:
        args.append(len(A)-1)
    arg = args[0]
    if arg==-1:
        B = [-A[0]+A[1]] + A[2:]
    elif arg==len(A)-1:
        B = A[:-2] + [A[-2]-A[-1]]
    else:
        B = A[:arg] + [A[arg] - A[arg+1] + A[arg+2]] + A[arg+3:]
    return iter(B, cnt+1)


print(iter(arr, 0))

### FIXED CODE ###

N, K = map(int, input().split())
S = input()

arr = []
cnt = 0
comp = S[0]
for s in S:
    if s==comp:
        cnt += 1
    else:
        arr.append(cnt)
        cnt = 1
        comp = s
arr.append(cnt)

if len(arr)<3:
    print(sum(arr))
else:
    if S[0]=='1':
        L = (len(arr)+1)//2 - K +1
        l = 0
        tmp = sum(arr[2*l:2*(l+K)+1])
        ans = tmp
        for l in range(1, L):
            tmp = tmp - (arr[2*(l-1)]+arr[2*l-1]) + sum(arr[2*(l-1+K)+1 : min(2*(l+K)+1, len(arr))])
            ans = max(tmp, ans)
    else:
        L = (len(arr)+1)//2 - K + 1
        l = 0
        tmp = sum(arr[2*l:2*(l+K)])
        ans = tmp
        for l in range(1, L):
            tmp = tmp - sum(arr[max(0,2*l-3) : 2*l-1]) + sum(arr[2*(l+K-1): min(2*(l+K), len(arr))])
            ans = max(tmp, ans)
            
    print(ans)
sample = input()
sample_list = sample.split(" ")
count = 0
flag = 0
for i in range(len(sample_list)):
  for j in range(1, i):
    if sample_list[i] == sample_list[j]:
      flag = 1
    if flag == 0:
      count += 1
    flag = 0
  return count


### FIXED CODE ###

sample = input()
sample_list = sample.split(" ")
count = 0
flag = 0
i = 0
j = 1
for i in range(len(sample_list)):
  for j in range(i):
    if sample_list[i] == sample_list[j]:
      flag = 1
  if flag == 0:
    count += 1
  flag = 0
print(count)
a,b = map(int,input().split())

def f(x):
    if x==0:
        return [0]
    k=2
    l = []
    while True:
        mul = k>>1
        if mul>x:
            fin = mul>>1
            l[-1]=x-fin+1
            break
        fin = mul>>1
        l.append(x//k*mul+max(x%k+1-k//2,0))
        k = k<<1
    l = l[::-1]
    return l
l1 = f(b)
l2 = f(a-1)
k=1
ans=0
while not l1==[]:
    if l2==[]:
        t = l1.pop()
        if t%2==1:
            ans+=k
    else:
        t = l1.pop()-l2.pop()
        if t%2==1:
            ans+=k
    k = k<<1
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())

def f(x):
    if x<=0:
        return [0]
    k=2
    l = []
    while True:
        mul = k>>1
        if mul>x:
            fin = mul>>1
            l[-1]=x-fin+1
            break
        fin = mul>>1
        l.append(x//k*mul+max(x%k+1-k//2,0))
        k = k<<1
    l = l[::-1]
    return l
l1 = f(b)
l2 = f(a-1)
k=1
ans=0
while not l1==[]:
    if l2==[]:
        t = l1.pop()
        if t%2==1:
            ans+=k
    else:
        t = l1.pop()-l2.pop()
        if t%2==1:
            ans+=k
    k = k<<1
print(ans)
from collections import defaultdict

class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[x] += self.__size[y]
            self.__size[y] = self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

def solve():
    uf = UnionFind()
    N, M = map(int, input().split())
    bridges = [[int(i) for i in input().split()] for i in range(M)]
    ans = [N * (N - 1) // 2]
    for A, B in reversed(bridges):
        if uf.same(A, B):
            ans.append(ans[-1])
        else:
            try:
                sa, sb = uf.size(A), uf.size(B)
                uf.union(A, B)
            except:
                sa, sb = 1, 0
            ans.append(ans[-1] - uf.size(A) * uf.size(B))
    ans.pop()
    return '\n'.join(map(str, reversed(ans)))

print(solve())


### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

def solve():
    N, M = map(int, input().split())
    bridges = [[int(i) - 1 for i in input().split()] for i in range(M)]
    ans = [N * (N - 1) // 2]

    uf = UnionFind(N)
    for bridge in reversed(bridges):
        A, B = bridge
        if uf.issame(A, B):
            ans.append(ans[-1])
        else:
            ans.append(ans[-1] - uf.size(A) * uf.size(B))
            uf.merge(A, B)
    ans.pop(-1)
    return '\n'.join(map(str, reversed(ans)))

print(solve())
import sys
sys.setrecursionlimit(20000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
nodes = [[] for _ in range(N+1)]
for w in W:
    nodes[w[0]].append((w[1], w[2]))
    nodes[w[1]].append((w[0], w[2]))
ans = [-1] * (N+1)
ans[1] = 0
def search(num, root, dis):
    for node in nodes[num]:
        sum_d = dis
        if node[0] != root:
            idx = node[0]
            sum_d += node[1]%2
            if sum_d%2 != 0:
                ans[idx] = 1
            else:
                ans[idx] = 0
            search(idx, num, sum_d)

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
nodes = [[] for _ in range(N+1)]
for w in W:
    nodes[w[0]].append((w[1], w[2]))
    nodes[w[1]].append((w[0], w[2]))
ans = [-1] * (N+1)
ans[1] = 0
def search(num, root, dis):
    for node in nodes[num]:
        sum_d = dis
        if node[0] != root:
            idx = node[0]
            sum_d += node[1]%2
            if sum_d%2 != 0:
                ans[idx] = 1
            else:
                ans[idx] = 0
            search(idx, num, sum_d)

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)
#include<iostream>
using namespace std;
int main(){
  int n,a,b;
  cin>>n>>a>>b;
  int ans=0;
  ans=(n/(a+b))*a+min(a,n%(a+b));
  cout<<ans<<endl;
  return 0;
}

### FIXED CODE ###

n,a,b = map(int,input().split())
cnt = n//(a+b)
if n%(a+b) - a >=0:
  cnt2 = a
else:
  cnt2 = n%(a+b)
print(a*cnt+cnt2)
n = int(input())
a = {i+1:int(input()) for i in range(n)}

def find(a, nexti, cnt, s):
    global n
    if cnt > n:
        return -1
    cnt += 1
    s.add(nexti)
    if a[nexti] == 2:
        return cnt
    elif a[nexti] in s:
        return -1
    else:
        return find(a, a[nexti], cnt, s)

print(find(a, 1, 0, set()))


### FIXED CODE ###

n = int(input())
a = {i+1:int(input()) for i in range(n)}
nexti = 1
for i in range(n):
    if a[nexti] == 2:
        print(i+1)
        exit()
    nexti = a[nexti]
print(-1)
a = list(map(int,input().split()))
b = list(map(int,input().split()))

b.sort(reverse=True)
for i in  range(a[1]):
    del b[0]
print(sum(b))


### FIXED CODE ###

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

if len(b) <= a[1]:
    print("0")
elif a[1]==0:
    print(sum(b))
else:
    b.sort(reverse=True)
    print(sum(b[a[1]:]))
N=int(input())
S = []
for j in range(N):
    S.append(input())
from collections import Counter
S2=collections.Counter(S)
S1=S2.most_common()

S3=[]
S3.append(S1[0][0])
for i in range(1,len(S1)):
    if S1[i][1]==S1[0][1]:
        S3.append(S1[i][0])
    else:
        break
S3=' '.join(sorted(S3))
print(S3)

### FIXED CODE ###

a, b,c = map(int, input().split())
if a==b and a!=c:
    print("Yes")
elif a==c and a!=b:
    print("Yes")
elif b==c and a!=b:
    print("Yes")
else:
    print("No")
n = int(input())
sum = 0
while (n != 0): 
  
    sum = sum + int(n % 10) 
    n = int(n/10) 

    
if (sum%9) == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
ans = 0
for i in range(len(s)):
    ans += int(s[i])
    
if ans%9 == 0:
    print("Yes")
else:
    print("No")
v\A,B  = input().split()
Flag = 1:

if A=='0' || B=='0':
    Flag = 0

if Flag 
    if B[0] == 0:
        BH =      B[2]+B[3]
    else:
        BH = B[0]+B[2]+B[3]

    ABH = str(int(A)*int(BH))
    print(int(ABH[:-2]))
else:
    print(0)

### FIXED CODE ###

A,B  = input().split()

if B[0] == 0:
    BH =      B[2]+B[3]
else:
    BH = B[0]+B[2]+B[3]

ABH = str(int(A)*int(BH))
if len(ABH) <= 2:
    print('0')
else:
    print(ABH[:-2])
N = int(input())
Inputs = [tuple(map(int, input().split())) for _ in range(N)]
H = 0
f = 0
for cx in range(101):
    for cy in range(101):
        n = 0
        while(n < N-1):
            x1, y1, h1 = Inputs[n]
            H1 = h1 + abs(x1-cx) + abs(y1-cy)
            x2, y2, h2 = Inputs[n+1]
            H2 = h2 + abs(x2-cx) + abs(y2-cy)
            n += 1
            if h1 == 0:
                continue
            if H1 != H2:
                f = 0
                break
            else:
                f = 1
        if f:
            Cx = cx
            Cy = cy
            H = H1
            
                
print(Cx, Cy, H)

### FIXED CODE ###

N = int(input())
coordinate = []
ans = -1
for _ in range(N):
    x, y, h = map(int, input().split())
    if h == 0:
        continue
    coordinate.append([x, y, h])
N = len(coordinate)
for cx in range(101):
    for cy in range(101):
        x1, y1, h1 = coordinate[0]
        H1 = h1 + abs(cx-x1) + abs(cy-y1)
        f = 1
        if N == 1:
            f = 2
            Cx = x1
            Cy = y1
            ans = h1
            break
        for n in range(1, N):
            x, y, h = coordinate[n]
            H = h + abs(cx-x) + abs(cy-y)
            if H == H1:
                f *= 1
            else:
                f *= 0
            if f and n == N-1:
                break
        if f == 1:
            Cx = cx
            Cy = cy
            ans = H1
            break
    if f:
        break
        
print(Cx, Cy, ans)
N,A,B = map(int,input().split())
color = []
if(A==0):
    print(0)
else:
    while len(color)<N:
        color.extend([1]*A)
        color.extend([0]*B)
    print(color[:N].count(1))

### FIXED CODE ###

N,A,B = map(int,input().split())
count=N//(A+B)
plus = N%(A+B)
print(A*count+min(A,plus))
import math
r = float(input())
v = math.pi*r^2
s = math.pi*r*2

print('%.7f %.7f'%(v,s))


### FIXED CODE ###

import math
r = float(input())
v = math.pi*r*r
s = math.pi*r*2

print('%.7f %.7f'%(v,s))
#https://atcoder.jp/contests/abc124
# -*- coding: utf-8 -*-

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

current=0
cnt=0
for i in h:
    if i >= current:
        current = i
        cunt += 1

print(cnt)

### FIXED CODE ###

#https://atcoder.jp/contests/abc124
# -*- coding: utf-8 -*-

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

current=0
cnt=0
for i in h:
    if i >= current:
        current = i
        cnt += 1

print(cnt)
N=int(input())

n=len(str(N))//2
full=0
for i in range(n):
    full+=int('9'+'0'*i*2)

if len(str(N))%2==0:
    b=0
else:
    nines=int('9'*(len(str(N))-1))
    b=N-nines
ans=full+b
print(ans)

### FIXED CODE ###

N=int(input())

n=len(str(N))//2
full=0
for i in range(n):
    full+=int('9'+'0'*i*2)

if len(str(N))%2==0:
    b=0
else:
    times=len(str(N))-1
    if times==0:
        nines=0
    else:
        nines=int('9'*times)
    b=N-nines
ans=full+b
print(ans)
defB():
    n = int(input())
    s = [list(map(str,input().split())) for i in range(n)]
    import collections
    c = collections.Counter(s)
    ret_l = ["AC","WA","TLE","RE"]
    for t in ret_l:
        print(t +  " x " + str(c[t]))
B()

### FIXED CODE ###

def B():
    n = int(input())
    s = []
    for _ in range(n):
        s.append(input())
    import collections
    c = collections.Counter(s)
    ret_l = ["AC","WA","TLE","RE"]
    for t in ret_l:
        print(t +  " x " + str(c[t]))
B()
s, t = input().split()
a, b = int(input().split())
u = input()
if s == u:
  print(s-1,t)
else:
  print(s,t-1)

### FIXED CODE ###

s, t = input().split(' ')
a, b = map(int, input().split(' '))
u = input()

if u == s:
  print(a-1,b)
else:
  print(a,b-1)
N, M = map(int, input().split())

def find_root(components, n):
    print(components, n)
    if components[n] == n:
        return n
    else:
        components[n] = find_root(components, components[n])
        return components[n]

bridges = []
for i in range(M):
    bridges.append([int(s) - 1 for s in input().split()])

components = [i for i in range(N)]
components_len = [1] * N
inconv = [int(N * (N-1) / 2)]

print(bridges)
for i in range(M-1, -1, -1):
    a, b = bridges[i]
    a_root, b_root = find_root(components, a), find_root(components, b)
    print(a_root, b_root)
    if a_root != b_root:
        inconv.append(inconv[-1] - components_len[a_root] * components_len[b_root])
        if components_len[a_root] < components_len[b_root]:
            a_root, b_root = b_root, a_root
        components_len[a_root] += components_len[b_root]
        components_len[b_root] = a_root
    else:
        inconv.append(inconv[-1])



### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]

    def root(self, x):
        """要素xの根の番号を返す"""
        if self.parent[x] < 0:
            return x
        self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

    def size(self, x):
        """所属するグループの頂点数を調べる"""
        return -self.parent[self.root(x)]

    def marge(self, x, y):
        """xとyを結合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size(x) < self.size(y):
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x  # 親を更新
        return True

n, m = map(int, input().split())
bridges = []
for i in range(m):
    bridges.append([int(s) - 1 for s in input().split()])

ans = [n * (n-1) // 2]
uf = UnionFind(n)
for i in range(m-1, 0, -1):
    a, b = bridges[i]
    if uf.root(a) == uf.root(b):
        ans.append(ans[-1])
    else:
        size_a = uf.size(a)
        size_b = uf.size(b)
        ans.append(ans[-1] - size_a * size_b)
        uf.marge(a, b)
ans.reverse()
print('\n'.join(map(str, ans)))
a, b = map(int, input().split())
c = a + b
d = a - b
e = a * b
print(max([c, d. e]))

### FIXED CODE ###

a, b = map(int, input().split())
print(max(a+b,a-b,a*b))
import math

a = int(raw_input())

b = (pow(a, 2) * math.pi)
c = 2 * a * math.pi
print format(b,"0.6f"), format(c, ".6f")

### FIXED CODE ###

import math
a = float(raw_input())

b = (pow(a, 2) * math.pi)
c = 2 * a * math.pi
print format(b,".6f"), format(c, ".6f")
MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
RGB = [0]*3
ans = 1
for i in A:
    count = 0
    for j in RGB:
        if i == j:
            count += 1
    RGB[RGB.index(i)] += 1
    ans = (ans * count)% MOD

print(ans)


### FIXED CODE ###

MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
RGB = [0]*3
ans = 1
for i in A:
    count = 0
    for j in RGB:
        if i == j:
            count += 1
    if count == 0:
        print(0)
        exit()
    RGB[RGB.index(i)] += 1
    ans = (ans * count)% MOD

print(ans)
def insertionSort(arr, g):
    cnt = 0
    for i in range(g, len(arr)):
        tmp = arr[i]
        j = i - g
        while(j >= 0 and arr[j] > tmp):
            arr[j + g] = arr[j]
            j -= g
            cnt += 1
        arr[j + 1] = tmp
    return cnt


def shellSort(arr):
    cnt = 0
    g = []
    h = 0
    while h <= len(arr) / 9:
        h = 3 * h + 1
        g.append(h)

    for i in range(0, m):
        cnt += insertionSort(a, g[i]):
    return (cnt, g)


N = int(input())
arr = [int(input()) for i in range(N)]

cnt, g = shellSort(arr)
print(len(g))
print(' '.join(map(str, g)))
print(cnt)
print('\n'.join(map(str, arr)))



### FIXED CODE ###

def insertionSort(arr, N, g):
    cnt = 0
    for i in range(g, N):
        tmp = arr[i]
        j = i - g
        while(j >= 0 and arr[j] > tmp):
            arr[j + g] = arr[j]
            j -= g
            cnt += 1
        arr[j + g] = tmp
    return cnt


def shellSort(arr, N):
    G = []
    h = 0
    m = 0
    while h <= N / 9:
        h = 3 * h + 1
        G.append(h)
        m += 1
    G = G[::-1]

    cnt = sum([insertionSort(arr, N, g) for g in G])
    return (cnt, G)


N = int(input())
arr = [int(input()) for i in range(N)]

(cnt, G) = shellSort(arr, N)
print(len(G))
print(' '.join(map(str, G)))
print(cnt)
print('\n'.join(map(str, arr)))
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})
def BFS(i,depth,K):  
    depth+=1
    tmp=[list(j.keys())[0] for j in i]


    if depth==1:
        calc=K-1
        diff=0
    else:
        calc=K-2
        diff=1
    seki=1
    if (len(tmp))>1 or depth<2:
        for i in range(calc,max(1,calc-(len(tmp)-diff)),-1):
            seki*=i
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            
            seki*=BFS(node[each].next,depth,K)
    return seki


N,K=list(map(int,input().split()))
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(com%1000000007)

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


N,K=list(map(int,input().split()))

if K>2:
    cache=[0 for i in range(K-2)]
    cache[0]=1
    for i in range(1,K-2):
        cache[i]=cache[i-1]*(K-1-i)%mod
    cache.append(cache[-1])
else:
    cache=[1,1]
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)