akhauriyash/Code-Regression huggingface dataset:
integer::n,k,s,t
real(8)::ans=0.d0
read*, n,k
do i= 1, n
  s=i
  t=0
  do while(S<K)
    s = s*2
    t=t+1
  end do
  ans=ans+0.5d0**t/real(n,8)
end do
 
print'(f12.10)',ans

end

Measured memory_bytes: 256
function main(input){
    const args = input.split("\n");
    const balls = args[1].split(" ");
    console.log(balls.reduce((acc, cur, idx, arr) => {
        let tempValue = 0
       let count = -1
       for(let val of arr){
           count = count + 1
           if(count === idx) continue
           tempValue = val * cur + tempValue
       }
    return acc + tempValue
    }, 0) / 2)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(true){
            int m = sc.nextInt();
            int f = sc.nextInt();
            int r = sc.nextInt();

            if (m == -1 && f == -1 && r == -1) {
                break;
            }else if(m == -1 || f == -1){
                System.out.println("F");
            } else if (m + f >= 80) {
                System.out.println("A");
            } else if (m + f >= 65) {
                System.out.println("B");
            } else if (m + f >= 50) {
                System.out.println("C");

            } else if (m + f >= 30) {
                if (r >= 50) {
                    System.out.println("C");
                } else {
                    System.out.println("D");
                }
            } else {
                System.out.println("F");
            }
        }
    }
}

Measured memory_bytes: 26420
import sys
import math
from fractions import gcd
# import queue
from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


N , K =  map(int, sys.stdin.readline().split())
L =  list(map(int, sys.stdin.readline().split()))

C = Counter(L)
X = [x for x in C.items()]

X.sort(key=lambda x : x[1])

kind = len(X)
cnt = 0
idx = 0
while True:
    if kind <= K:
        print(cnt)
        exit()
    kind -= 1
    cnt += X[idx][1]
    idx += 1

Measured memory_bytes: 123972
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int n = sc.nextInt();
		int sum = 0;
		for (int i = 0; i < n; i++) {
			sum += sc.nextInt();
		}
		sc.close();

		if (sum >= h) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 47952
#include <bits/stdc++.h>
using namespace std;
#define LEN 100005

typedef struct pp {
  char name[100];
  int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x) {
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}

P dequeue(){
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}

int min(int a, int b) { return a < b ? a : b; }

int main() {
  int elaps = 0, c, q;
  P u;
  //scanf("%d %d", &n, &q);
  cin >> n >> q;
  for (int i = 1; i <=n; i++) {
    //scanf("%s", Q[i].name);
    //scanf("%d", &Q[i].t);
    cin >> Q[i].name >> Q[i].t;
  }
  head = 1;
  tail = n + 1;

  while ( head != tail ) {
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    elaps += c;
    if ( u.t > 0 ) {
      enqueue(u);
    } else {
      //printf("%s %d\n", u.name, elaps);
      cout << u.name << " " << elaps << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 13232
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    // start
    int n;
    cin >> n;
    cout << (n >= 1000 ? "ABD" : "ABC") << endl;
    // end

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <map>

using namespace std;

struct UnionFind {
    vector<long long> par; // 親ノード
    vector<long long> rank; // ランク
    vector<long long> root_size; //ノードが根のときに、何個の子要素を持っているのか。(自分を含む)
                            //親じゃない場合は-1を出力

    UnionFind(long long n = 1) {
        init(n);
    }

    void init(long long n = 1) {
        par.resize(n); rank.resize(n); root_size.resize(n);
        for (long long i = 0; i < n; ++i) par[i] = i, rank[i] = 0, root_size[i] = 1;
    }

    long long root(long long x) {
        if (par[x] == x) {
            return x;
        }
        else {
            long long r = root(par[x]);
            return par[x] = r;
        }
    }

    bool issame(long long x, long long y) {
        return root(x) == root(y);
    }

    //yをxにマージ
    bool merge(long long x, long long y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        root_size[x] += root_size[y];
        root_size[y] = -1;
        return true;
    }

    long long size(long long x){
        x = root(x);
        return root_size[x];
    }
};

int main(){
    long long N;
    cin >> N;
    UnionFind UF(N);

    long long M; cin >> M;
    long long K; cin >> K;

    vector<long long> path_num(N);

    for(long long i=0; i<M; ++i){
        long long a, b; cin >> a >> b;
        a--; b--;
        path_num[a]++;
        path_num[b]++;
        UF.merge(a, b);    
    }

    for(long long i=0; i<N; ++i){
        UF.root(i);
    }

    vector<long long> node_edges(N);
    for(long long i=0; i<N; ++i){
        node_edges[i] = UF.size(i) -1;
    }

    //delete block
    for(long long i=0; i<K; ++i){
        long long c, d; cin >> c >> d;
        c--; d--;
        if(UF.issame(c, d)){
            path_num[c]++;
            path_num[d]++;
        }
    }

    for(long long i=0; i<N; ++i){
        cout << node_edges[i] - path_num[i] << endl;
    }

}

Measured memory_bytes: 7196
MAX_SUM = 4000
MAX_I = 1000
K = 4

### global variables

$sn_cache = (0..K).map{[]}

### subroutines

def check_sum(k, n)
  if $sn_cache[k][n].nil?
    count = 0
    max_i = [MAX_I, n].min

    for i in (0..max_i)
      count += check_sum(k - 1, n - i)
    end

    $sn_cache[k][n] = count
  end

  #puts "(#{k}, #{n}) = #{$sn_cache[k][n]}"
  return $sn_cache[k][n]
end

### main

$sn_cache[1] = (0..MAX_I).map{1} + ((MAX_I + 1)..MAX_SUM).map{0}
#p $sn_cache[1]

while (line = gets)
  n = line.chomp.to_i

  puts check_sum(K, n)
end

Measured memory_bytes: 6300
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

#define rep(i,n) for(int i=0;i<n;i++)
const long long MOD = 1000000007;
typedef pair<int,int> P;
typedef long long ll;
ll n,m,k,ans;
string s;

int main(){
  cin >> n >> m;
  int fragS[m][n] = {};
  rep(i,m){
    cin >> k;
    rep(j,k){
      int t; cin >> t;
      fragS[i][t-1] = 1;
    }
  }
  int p[m]; rep(i,m) cin >> p[i];
  ans = 0;
  rep(i, pow(2,n)){
    bool frag = true;
    rep(j,m){
      int on = 0;
      rep(l,n){
        if( ((i>>l)&1) && (fragS[j][l]==1) ) on++;
      }
      if((on%2)!=p[j]) frag = false;
    }
    if(frag) ans++;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define INF 1e9
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int> p;

int d[121][121],obs[121][121],dx[]={1,0,-1,0,1,-1},dy[]={0,1,0,-1,1,-1},t,n;

void bfs(int x,int y){
	queue<p> q;
	rep(i,121)rep(j,121)d[i][j]=INF;
	q.push(p(x,y));
	d[x][y]=0;
	while(!q.empty()){
		p c=q.front();q.pop();
		if(d[c.first][c.second]==t)return;
		rep(i,6){
			int nx=c.first+dx[i],ny=c.second+dy[i];
			if(nx>=0&&nx<121&&ny>=0&&ny<121&&!obs[nx][ny]&&d[nx][ny]==INF){
				q.push(p(nx,ny));
				d[nx][ny]=d[c.first][c.second]+1;
			}
		}
	}
}

int main(){
	while(cin>>t>>n&&(t||n)){
		rep(i,121)fill(obs[i],obs[i]+121,0);
		int x,y,ans=0;
		rep(i,n){
			cin>>x>>y;
			obs[x+60][y+60]=1;
		}
		cin>>x>>y;
		bfs(x+60,y+60);
		rep(i,121)rep(j,121)ans+=d[i][j]<=t;
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1032
#include<bits/stdc++.h>
using namespace std;



int main() {
  int k,n;
  cin >> k >> n;
  int a[n];
  for(int i=0;i<n;i++) cin >> a[i];
  int MAX = 0,index;
  for(int i=0;i<n;i++){
      int before = i-1;
      if(before < 0) before += n;
      int sa = a[i] - a[before];
      if(sa < 0) sa+=k;
      if(sa > MAX){
          MAX = sa;
          index = i;
      }
  }
  int sum = 0;
  for(int i = 0;i<n-1;i++){
      index++;
      sum += a[index%n] - a[(index-1)%n];
      if(index%n == 0) sum +=k;
  }

  cout << sum << endl;
  return 0;


}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;

long long d, n, ans;

int main() {
cin >> d >> n;
if(d == 0) ans = 1;
else if(d == 1) ans = 100;
else ans = 10000;
if(n == 100) ++n;
ans *= n;
cout << ans << endl;
return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;

ll n;
ll ans;
ll P[25];
int main(){
	cin >> n;
	REP(i,0,n){
		cin>>P[i];
	}
	REP(i,0,n-2){
		if(P[i] < P[i+1] && P[i+1] < P[i+2]){
			ans++;
		}else if(P[i] > P[i+1] && P[i+1] > P[i+2]){
			ans++;
		}
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
x = gets.split.map(&:to_i)
min,max = 100,1
x.each do |i|
  i < min ? (min = i) : max < i ? (max = i) : next
end
ans = Float::INFINITY
(min..max).each do |i|
  sum = 0
  x.each do |j|
    sum += (i-j)**2
  end
  ans = [ans,sum].min
end
puts ans


Measured memory_bytes: 14256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int UF_SIZE = 128;
int UF[UF_SIZE];

void UF_init() {
	for(int i = 0; i < UF_SIZE; i++) {
		UF[i] = i;
	}
}

int UF_indx(int a) {
	if(a == UF[a])
		return a;
	else
		return UF_indx(UF[a]);
}

int UF_merge(int a, int b) {
	UF[UF_indx(a)] = UF_indx(b);
}

struct bridge {
	int a, b;
	int cost;
	bridge(int a_, int b_, int cost_) {
		a = a_; b = b_;
		cost = cost_;
	}

	bool operator<(const bridge obj) const {
		return cost < obj.cost;
	}
};

int main() {
	int n, m;
	while(1) {
		cin >> n >> m;
		if(n == 0 && m == 0)
			break;
		vector<bridge> v;
		UF_init();
		for(int i = 0; i < m; i++) {
			int a, b;
			int cost;
			cin >> a >> b >> cost;
			v.push_back(bridge(a, b, cost));
		}

		sort(v.begin(), v.end());
		int ans = 0;
		for(int i = 0; i < v.size(); i++) {
			if(UF_indx(v[i].a) != UF_indx(v[i].b)) {
				UF_merge(v[i].a, v[i].b);
				ans += v[i].cost;
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1204
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    string s;
    cin >> s;
    if (s[0] != s[1] && s[1] != s[2] && s[2] != s[3]) {
        cout << "Good" << endl;
    }
    else {
        cout << "Bad" << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int a, b, c;
	scanf("%d %d %d",&a ,&b ,&c);
	if(a<b && b<c)
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 580
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappush,heappop,heapify
def resolve():
    n,m=map(int,input().split())
    A=list(map(lambda x:-int(x),input().split()))
    heapify(A)
    for _ in range(m):
        x=-heappop(A)
        x//=2
        heappush(A,-x)

    print(-sum(A))
resolve()

Measured memory_bytes: 68224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;

int main()
{
    ll n;
    while(~scanf("%lld",&n)){
        ll ans=0;
        while(n){
            ans=ans+ans+1;
            n/=2;
        }
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import numpy as np

N,M = map(int, raw_input().split())
image = np.zeros((N,N),dtype='int8')
template = np.zeros((M,M),dtype='int8')
YesFlag = 0

for i in range(N):
    S = raw_input()
    for j in range(len(S)):
        if(S[j]=='#'):
            image[i][j] = 0
        elif(S[j]=='.'):
            image[i][j] = 1
for i in range(M):
    S = raw_input()
    for j in range(len(S)):
        if(S[j]=='#'):
            template[i][j] = 0
        elif(S[j]=='.'):
            template[i][j] = 1

#print(image)
#print(template)

for i in range(N-M+1):
    for j in range(N-M+1):
        #print(image[i:M+i,j:M+j])
        if(np.all(image[i:M+i,j:M+j]==template) == True):
            YesFlag = 1
            break
    if(YesFlag == 1):
        break

if(YesFlag == 1):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 11752
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()

int main() {
    int a,b,c;
    cin>>a>>b>>c;
    cout<<a+b+c-max(max(a,b),c);
	return 0;
}


Measured memory_bytes: 3552
/*

*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
#include <stack>
#include <deque>
 
#define ll long long
#define cint const int
#define ld long double
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
 
using namespace std;
 
typedef vector <long long> vll;
typedef vector <string> vs;
typedef vector <char> vc;
typedef set <int> si;
typedef set <string> ss;
typedef pair <int, int> pi;
typedef pair <long long, long long> pll;
typedef pair <int, long long> pil;
typedef pair <int, string> pis;
typedef pair <int, char> pic;
typedef pair <long long, int> pli;
typedef pair <long long, string> pls;
typedef pair <long long, char> plc;
typedef pair <string, int> psi;
typedef pair <string, long long> psl;
typedef pair <string, char> psc;
typedef pair <char, int> pci;
typedef pair <char, long long> pcl;
typedef pair <char, string> pcs;

ll n, a[100005], m;
ll s = 0;

int main () {
	cin >> n;
	ll c = 1;
	while (n > 0) {
	    if (n == 1) {
	        c *= 2;
	        s += c;
	        break;
	    }
	    n /= 2;
	    s += c;
	    c *= 2;
	}
	cout << c - 1;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
using Graph = vector<vector<int>>;

int main(){
	int a, b, c; cin >> a >> b >> c;
	if(a + b + c > 21) cout << "bust" << endl;
	else cout << "win" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	
	while(cin >> n){
	int ans = 0;
		for(int a = 0; a <= 9; a++){
			for(int b = 0; b <= 9; b++){
				for(int c = 0; c <= 9; c++){
					for(int d = 0; d <= 9; d++){
						if(a+b+c+d==n){
							ans++;
						}
					}
				}
			}
		}
	cout << ans << endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h> 
 
using namespace std;
 
 template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
const double EPS=0.00001;


int main(){
    int A,B,C,D,E,F;
    cin>>A>>B>>C>>D>>E>>F;
    A*=100;B*=100;
    int n=100;
    double res=0.0;
    PII pi=MP(A,0);
    for(int n=100;n<=F;n+=100){
        bool flag=false;
        for(int nA=0;nA<=n;nA+=A)for(int nB=0;nB<=n-nA;nB+=B){
            if(nA+nB==n){
                flag=true;break;
            }
        }
        if(!flag)continue;
        int maxi=n/100*E;

        for(int nC=0;nC<=maxi;nC+=C)for(int nD=0;nD<=maxi-nC;nD+=D){
            int tmp=nC+nD;
            if(tmp+n<=F&&res<(double)tmp/(double)(n+tmp)){
                res=(double)tmp/(double)(n+tmp);
                pi=MP(n+tmp,tmp);
            }
        }
    }
    cout<<pi.first<<" "<<pi.second<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define M 1000000007 
#define MM 998244353
#define PI 3.14159265 
using namespace std;
 
int main()
{
	long long int sum = 0, num = 9;
	string s;

	cin >> s;

	for (long long int i = 0; i < s.size(); i++)
	{
		sum = sum + s[i] - 48;
	}

	

	if (sum%num == 0)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}

  	return 0;
}

Measured memory_bytes: 3744
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <deque>
#include <numeric>
#include <map>
#define rep(i,n) for (int i = 0; i < (n); ++i)
 
using namespace std;
 
typedef pair<int,int> P;
typedef long long ll;

const int  SIZE = 200005;
const ll INF = 1e18 + 10;

int N;
string S;
int dp[5005][5005];

int main() {
    cin >> N >> S;
    for (int i = N-1; i >= 0; --i) {
      for (int j = N-1; j>=0; --j) {
        if (S[i]!=S[j]) dp[i][j] = 0;
        else dp[i][j] = dp[i+1][j+1] + 1;
      }
    }
    int ans = 0;
    rep(i,N) rep(j,N) {
      if (i>=j) continue;
      int now = min(dp[i][j], j -i );
      ans = max(ans, now);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 100832
#include "bits/stdc++.h"

using namespace std;

int n, m, cnt = 0, res = 0;
vector<int> v;
int main(){
    cin >> n >> m;
    v.assign(n, 0);
    for(int i = 0; i < n; ++i){
        cin >> v[i];
        cnt += v[i];
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n; ++i){
        if(v[i] >= cnt/(4.0 * m)){
            res++;
        }
    }
    cout << (res >= m ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define pp pop_back
#define mp make_pair
#define pb push_back
#define rep(x, a, b) for(int x=a; x<=b; x++)
#define drp(x, a, b) for(int x=a; x>=b; x--)
typedef long long ll;
const int mod=924844033;
const int N=200200;
const int G=5;
int ans[N], n, m, l, rev[N<<2], fac[N], inv[N], f[N<<2], u[N], v[N], g[N<<2], head[N], cnt, siz[N], c[N];
ll read(){
	ll x=0; char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
	return x;
}
void write(ll x){
	if(x<10)
	{
		putchar(x+'0');
		return;
	}
	write(x/10);
	putchar(x%10+'0');
}
struct Edge{
	int to, next;
}edge[N<<1];
void AddEdge(int u, int v){
	edge[++cnt]=(Edge){ v, head[u] }, head[u]=cnt;
	edge[++cnt]=(Edge){ u, head[v] }, head[v]=cnt;
}
void dfs(int u, int fa){
	siz[u]=1;
	for(int i=head[u]; i; i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v, u);
		c[n-siz[v]]--;
		siz[u]+=siz[v];
	}
	c[siz[u]]--;
}
int power(int a, int k){
	int ret=1;
	while(k)
	{
		if(k&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod; k>>=1;
	}
	return ret;
}
void DFT(int *a, int n, int f){
	rep(i, 0, n-1) if(i<rev[i]) swap(a[i], a[rev[i]]);
	for(int i=1, t=1; i<n; i<<=1, t++)
	{
		int wn=power(G, f?(mod-1-((mod-1)>>t)):((mod-1)>>t));
		for(int j=0; j<n; j+=i<<1)
		{
			int w=1;
			for(int k=0; k<i; k++, w=1ll*w*wn%mod)
			{
				int u=a[j+k], v=1ll*w*a[j+k+i]%mod;
				a[j+k]=(u+v)%mod; a[j+k+i]=(u+mod-v)%mod;
			}
		}
	}
	if(f)
	{
		int v=power(n, mod-2);
		rep(i, 0, n-1) a[i]=1ll*a[i]*v%mod;
	}
}
int main(){
	n=read();
	fac[0]=1;
	rep(i, 1, n) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=power(fac[n], mod-2);
	drp(i, n, 1) inv[i-1]=1ll*inv[i]*i%mod;
	rep(i, 1, n-1){ u[i]=read(), v[i]=read(); AddEdge(u[i], v[i]); }
	rep(i, 1, n-1) c[i]=mod;
	dfs(1, 0);
	c[n]=n;
	rep(i, 1, n) f[i]=1ll*c[i]*fac[i]%mod;
	rep(i, 0, n) g[n-i+1]=inv[i];
	for(m=1; m<=((n<<1)|1); m<<=1) l++;
	rep(i, 0, m-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	DFT(f, m, 0); DFT(g, m, 0);
	rep(i, 0, m-1) f[i]=1ll*f[i]*g[i]%mod;
	DFT(f, m, 1);
	rep(k, 1, n) ans[k]=1ll*inv[k]*f[n+k+1]%mod;
	rep(i, 1, n) write(ans[i]), puts("");
}

Measured memory_bytes: 28928
//encoding:utf-8
//#include <iostream> //c++
//#include<stack> //スタックに関して　最新のデータから捨てる
//#include<queue> //キューに関して　最古のデータから捨てる
//#include<math.h>
//#include<vector>
//#include<algorithm> //sort とかにいる
#include<bits/stdc++.h>//vector,algorithm,que
#include<time.h> //時間にかんして

#define ll long long
#define MOD 1000000007
#define INF (1<<29)
using namespace std;
int main(){
  ll R,G,B,N;
  cin>>R>>G>>B>>N;
  ll ans = 0;
  for(int i=0;i<(int)3000/R+1;i++){
    if(N-i*R<0){
      break;
    }
    for(int j=0;j<(int)3000/G+1;j++){
      if(N-i*R-j*G<0){
        break;
      }
      if((N-i*R-j*G)%B == 0){
        ans += 1;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<string,int>> vpsi;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;

int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////

int a,b;
cin >> a;
cin >> b;
if(1!=a&&1!=b)fin(1);
if(2!=a&&2!=b)fin(2);
if(3!=a&&3!=b)fin(3);

//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int q;
    cin >> q;
    set<int> s;
    while (q--) {
        int c, x;
        cin >> c >> x;
        if (c == 0) {
            s.emplace(x);
            cout << sz(s) << endl;
        } else if (c == 1) {
            cout << s.count(x) << endl;
        } else if (c == 2) {
            s.erase(x);
        } else if (c == 3) {
            int y;
            cin >> y;
            auto st = s.lower_bound(x);
            auto ed = s.upper_bound(y);
            for (;st != ed; st++) cout << *st << endl;
        }
    } 
}



Measured memory_bytes: 12516
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) &= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

int N;
vec a;
int sum[410], dp[410][410];

int rec(int l, int r) {
  if (l == r) return 0;
  if (l + 1 == r) return sum[r] - sum[l - 1];
  if (dp[l][r] > 0) return dp[l][r];

  int res = INF;
  for (int i = l; i < r; i++) {
    chmin(res, rec(l, i) + rec(i + 1, r));
  }

  return dp[l][r] = res + (sum[r] - sum[l - 1]);
}

signed main() {
  cin >> N;
  a.resize(N);
  for (int i = 0; i < N; i++) cin >> a[i];

  sum[0] = 0;
  for (int i = 1; i <= N; i++) {
    sum[i] = sum[i - 1] + a[i - 1];
  }

  cout << rec(1, N) << endl;
  return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

int main(){
	
	long long a;
	string b;
	cin >> a >> b;
	
	int bn = 0;
	for(int i = 0; i < b.size(); i++){
		if(b[i] == '.')continue;
		bn += b[i] - '0';
		bn *= 10;
	}
	bn /= 10;
	long long ans = a*bn;
	ans /= 100;
	cout << ans << endl;
	
	return 0;
}
 

Measured memory_bytes: 3596
/* Tuan Kkura */
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define base 31
#define MOD 1e9+7
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORs(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, a, b) for(int i = a; i < b; i++)
#define __FOR(i, a, b, k) for(int i = a; i <= b; i+= k)
#define __REP(i, a, b, k) for(int i = a; i < b; i+= k)
#define pb push_back
#define _io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

typedef pair <int, int> ii;
typedef vector <ii> vii;
#define fi first
#define se second
#define mp make_pair
#define PROB "text"
#define MAXN 200005

int ans[MAXN];
vii DSK[MAXN];

void DFS(int u, int pre, int color)
{
    int val = 1;
    if(val == color) val++;
    for(ii v : DSK[u])
        if(v.fi != pre)
        {
            ans[v.se] = val;
            DFS(v.fi, u, val);
            val++;
            if(val == color) val++;
        }
}

int main()
{
    _io
    int n; cin >> n;
    FOR(i, 1, n-1)
    {
        int u, v; cin >> u >> v;
        DSK[u].pb(mp(v, i));
        DSK[v].pb(mp(u, i));
    }
    int res = 0;
    FOR(i, 1, n)
        res = max(res, (int)DSK[i].size());
    DFS(1, 0, 0);
    cout << res << '\n';
    FOR(i, 1, n-1)
        cout << ans[i] << '\n';
}


Measured memory_bytes: 10752
n=int(input())
s1=input()
s1_=list(s1)
s2=input()
for i in range(len(s1)-1):
  if s1[i]==s1[i+1]:
    idx=s1_.index(s1[i])
    s1_[idx+1]='1'
    del s1_[idx]
mod=10**9+7
if s1_[0]=='1':
  ans=6
else:
  ans=3
#print(s1_)
for i in range(1,len(s1_)):
  if s1_[i]=='1':
    if s1_[i-1]!='1':
      ans*=2
      ans%=mod
    else:
      ans*=3
      ans%=mod
  else:
    if s1_[i-1]!='1':
      ans*=2
      ans%=mod
print(ans%mod)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159265359
#define int long long
#define pii pair<int,int>
const int mod=1e9+7;

int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};






int32_t  main()
{ 
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
 



 string s;
 cin>>s;
 if(s[2]==s[3]&&s[4]==s[5])
 {
     cout<<"Yes\n";
 }
 else cout<<"No\n";

}




Measured memory_bytes: 256
// AOJ GRL_3_A Articulation Points
// 2018.5.7 bal4u
// https://everysick.hatenablog.com/entry/2016/06/13/120033 を参考にした
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAX_V 100002
#define MAX_E 100002

int  hi[MAX_V], *to[MAX_V];
int  low[MAX_V], ord[MAX_V];
int  cnt;
int  ap[MAX_V], sz;      // Articulation Point 関節点
char mk[MAX_V];

void dfs(int cur, int from)
{
	int i, e, t, ct;
	int is_ap;
	
	mk[cur] = 1;
	low[cur] = ord[cur] = cnt++;
	is_ap = 0;
	ct = 0;

	for (i = 0; i < hi[cur]; i++) {
		e = to[cur][i];
		if (!mk[e]) {
			ct++;
			dfs(e, cur);
			t = low[e];
			if (t < low[cur]) low[cur] = t;
			if (~from && ord[cur] <= low[e]) is_ap = 1;
		} else if (from != e) {
			t = ord[e];
			if (t < low[cur]) low[cur] = t;
		}
	}
	if (from == -1 && ct > 1) is_ap = 1;
	if (is_ap) ap[sz++] = cur;
} 

void check_ap(int V)
{
	int i;
	cnt = 0;
	for (i = 0; i < V; i++) {
		if (!mk[i]) dfs(i, -1);
	}
}

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

int cmp(int *a, int *b) { return *a - *b; }

int main()
{
    int E, V, s, t, i, j;
    int *memo;
 
    V = in(), E = in();
    memo = malloc(E<<3);
    j = 0; for (i = 0; i < E; i++) {
        memo[j++] = s = in(), memo[j++] = t = in();
        hi[s]++, hi[t]++;
     }
    for (i = 0; i < V; i++) {
        if (hi[i]) to[i] = malloc(hi[i]<<2);
    }
    memset(hi, 0, V<<2);
 
    j = 0; while (E--) {
        s = memo[j++], t = memo[j++];
		to[s][hi[s]++] = t, to[t][hi[t]++] = s;
    }
 
    check_ap(V);
 	qsort(ap, sz, sizeof(int), cmp);

	for (i = 0; i < sz; i++) printf("%d\n", ap[i]);
    return 0;
}


Measured memory_bytes: 3384
//int a = s - '0'; 文字から数字
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//stack<ll> s;
//s.push(要素);s.top();s.pop();
//queue<ll> q;
//q.push(要素);q.front();q.pop();
//同じ作業繰り返す系の問題：収束先を見つける
//過半数：N/2.0で判定
//優先度付きキュー
//priority_queue<
//ll,
//vector<ll>
//> q;
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
#define PI 3.14159265358979323846264338327950L
using namespace std;

//割るやつ
const ll MOD = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

//a,bの最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1));
}

//Nのd桁目の数
ll dignum(ll N, ll d) {
	ll x = pow(10, d);
	N %= x;
	ll y = pow(10, d - 1);
	N /= y;
	return N;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

ll RS(ll N, ll P, ll M) {
	if (P == 0) return 1;
	if (P % 2 == 0) {
		ll t = RS(N, P / 2, M);
		return t * t % M;
	}
	return N * RS(N, P - 1, M);
}

vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            S.push_back(i);
        }
    }
    return S;
}

int main() {
	int N, K, X, Y;cin >> N >> K >> X >> Y;

	cout << X * min(N,K) + Y * max(N - K, 0) << endl;
}	

Measured memory_bytes: 11020
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		int K = Integer.parseInt(sc.next());
		sc.close();

		int num = 1;
		for(int i = 1; i <= N; i++) {
			if(num <= K) {
				num *= 2;
			}else {
				num += K;
			}
		}
		System.out.println(num);
	}
}

Measured memory_bytes: 21588
import sys

s = int(input())

res = [s]
c = 0
while True:
    if(res[c]%2 == 0):
        tmp = res[c]//2
    if(res[c]%2 == 1):
        tmp = res[c]*3+1
    res.append(tmp)
    if(len(set(res)) != len(res)):
        print(c+2)
        sys.exit()
    c+=1

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int t[58],n,f,ans,d;
int main(){
    cin>>n>>d;
    for(int i=0;i<n;i++){
        cin>>f;
        t[f]++;
    }
    for(int i=50;i>=0;i--){
        while(t[i]!=0&&d!=0){
            t[i]--;
            ans+=i;
            d--;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
h,n = gets.chomp.split(" ").map(&:to_i)
arr = n.times.map{gets.chomp.split(" ").map(&:to_i)}

# 体力iのモンスターを倒すための最小魔力
dp = Array.new(h+1, 10 ** 8)
dp[0] = 0

arr.each do |(a, b)|
  1.upto(h) do |i|
    tmp = 0
    # 前回までの攻撃
    tmp += dp[i - a] if i - a >= 0
    # 今回の攻撃
    tmp += b
    dp[i] = [dp[i], tmp].min
  end
end

puts dp[-1]


Measured memory_bytes: 14192
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
		//文字列から10進数に変換するときはparseIntを使います
	var n = parseInt(input[0], 10);
		
	s = input[1].trim().split("");///////  trim  文字
   
	//console.log(s);
	var cnt = 0;
	var i = 0;
    for(i=0;i<n;i++){
     if (s[i] == s[i+1]){//console.log(i);
                      }else{cnt =cnt +1;}
                     // console.log (cnt);
    }
	console.log(cnt);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21960
//
//  main.cpp
//  CoderTest
//
//  Created by yuya on 2019/07/25.
//  Copyright © 2019 yuya. All rights reserved.
//

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;



int main(){
    
    ll N;
    cin >> N;
    deque<int> S;
    ll v;
    int i=0;
    while(N!=0){
        v = pow(-2,i);
        if(abs(N) % (2 * abs(v)) != 0){
            S.push_front(1);
            N -= v;
        } else {
            S.push_front(0);
        }
        i++;
    }
    if(S.empty()) {
        cout << 0 << endl;
        return 0;
    }
    while(!S.empty()){
        cout << S.front();
        S.pop_front();
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
const ll MAX_N=1e5,MOD=1e9+7,MAX_K=1e5;
ll N,K;
vector<ll> G[MAX_N];
ll fact[MAX_K+1],ifact[MAX_K+1];
ll mpw(ll n,ll m){
    ll ret=1;
    while(m){
        if(m&1){
            ret*=n;
            ret%=MOD;
        }
        m>>=1;
        n*=n;
        n%=MOD;
    }
    return ret;
}
ll minv(ll n){
    return mpw(n,MOD-2);
}
ll per(ll n, ll m){
    if(n<m){
//        cout<<"debug"<<endl;
        return 0;
    }
    return fact[n]*ifact[n-m]%MOD;
}
ll dfs(ll v,ll x,ll p){
    ll y=0;
    if(p!=-1)y=1;
    ll ret=per(K-x,(ll)G[v].size()-y);
    if(ret==0){
//        cout<<K-x<<','<<(ll)G[v].size()-y<<endl;
    }
    for(auto e:G[v]){
        if(e!=p){
            ret*=dfs(e,2,v);
            ret%=MOD;
        }
    }
    
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>K;
    fact[0]=1;
    REP(i,K){
        fact[i+1]=fact[i]*(i+1)%MOD;
    }
    ifact[K]=minv(fact[K]);
    for(ll i=K-1;i>=0;i--){
        ifact[i]=ifact[i+1]*(i+1)%MOD;
    }
    REP(i,N-1){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    if(K==1){
        cout<<(N==1 ? 1 : 0)<<endl;
    }else{
        cout<<K*dfs(0,1,-1)%MOD<<endl;
    }
//    cout<<ifact[0]<<endl;
//    cout<<fact[21]<<endl;
}


Measured memory_bytes: 62720
#include<bits/stdc++.h>
#include<vector>
#define int long long
#include<string>
#define float long double
using namespace std;
   signed main()
 {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin>>n;
  int a[n],s=1,h=1;
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<n-1;i++)
  {
      if(a[i]>=a[i+1])
        s++;
      if(a[i]<a[i+1]||i==n-2)
      {
         if(s>h)
            h=s;
         s=1;
      }
  }
  cout<<h-1;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 2);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end(), greater<int>());
    for(int i = 1; i <= n; i++) {
        if(a[i + 1] < i + 1) {
            int j = i + 1;
            for(; a[j] == i; j++);
            int tmp1 = a[i] - i + 1;
            int tmp2 = j - i;
            if((tmp1 & 1) && (tmp2 & 1)) {
                cout << "Second" << endl;
            }
            else {
                cout << "First" << endl;
            }
            break;
        }
    }
    
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long

using namespace std;

char s[15];
int h,use;

void dfs(int n,int len)
{
    if (n==len)
    {
        printf("%s\n",s);
        return;
    }
    for (int i=0;i<use+1;i++)
    {
        if (i==use)
        {
            use++;
            s[n]='a'+i;
            dfs(n+1,len);
            s[n]='\0';
            use--;
        }
        else
        {
            s[n]='a'+i;
            dfs(n+1,len);
            s[n]='\0';
        }
    }
}


int main()
{
    use=0; int n;
    scanf("%d",&n);
    dfs(0,n);

    return 0;
}


Measured memory_bytes: 1536
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define mp make_pair
#define pi pair<int,int>
#define pl pair<long long int,long long int>
#define pb push_back
#define fi first
#define se second
#define len(a) (int)(a).length()
#define sz(a) (int)(a).size()

typedef long long int ll;
typedef long double ld;

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

// order_of_key (k) : Number of items strictly smaller than k, basically 0-based index of k
// find_by_order(k) : K-th element in a set (counting from zero)

typedef struct $
{
	int m[51][51];
}matrix;

int n;
const int M = 1e9 + 7;

matrix matmul(matrix a, matrix b) {
	matrix res;
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			res.m[i][j] = 0;
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j) {
			for (int k=1; k<=n; ++k) {
				res.m[i][j] = (res.m[i][j] + 1LL * a.m[i][k] * b.m[k][j]) % M;
			}
		}
	return res;
}

matrix matpow(matrix base, ll y) {
	matrix res;
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			res.m[i][j] = (i == j);
	while (y > 0LL) {
		if (y & 1LL) res = matmul(res, base);
		base = matmul(base, base);
		y >>= 1;
	}
	return res;
}

int main ()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll k;
	cin >> n >> k;
	matrix inp;
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			cin >> inp.m[i][j];
	matrix p = matpow(inp, k);
	int ans = 0;
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			ans = (ans + p.m[i][j]) % M;
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 384
n = gets.to_i

d = 10 ** 9 + 7
m10 = 1
m9 = 1
m8 = 1
n.times do |i|
  m10 = (10 * m10) % d
  m9 = (9 * m9) % d
  m8 = (8 * m8) % d
end

puts (m10 - 2 * m9 + m8) % d


Measured memory_bytes: 14320
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

def fact(n):
    #階乗を求める
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

a = 0
#aについて
f = [False] * N
for i in range(N):
    a += (P[i]-1-f[:P[i]-1].count(True)) * fact(N-i-1) + 1
    f[P[i]-1] = True

b = 0
#bについて
f = [False] * N
for i in range(N):
    b += (Q[i]-1-f[:Q[i]-1].count(True)) * fact(N-i-1) + 1
    f[Q[i]-1] = True

print(abs(a-b))

Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }

int main(){
    ll A, B;
    cin >> A >> B;
    if (A<=8 && B<=8) cout << "Yay!\n";
    else cout << ":(\n";
}


Measured memory_bytes: 256
object Main extends App {
  override def main(args: Array[String]): Unit = {
    Iterator.continually(new DataFactory(io.StdIn.readLine.toInt))
      .takeWhile(_.continue)
      .map(_.read.sigma).foreach(println)
  }

  class DataFactory(n: Int) {
    val continue = n != 0;
    def read(): Data = {
      val list = io.StdIn.readLine.split(' ').toList.map(_.toInt)
      new Data(n,list)
    }
  }
  class Data(n:Int , list : List[Int]) {
    val sum = list.sum.toDouble
    val mean:Double = sum/n.toDouble
    
    val sigma = Math.sqrt( list.map( si =>  (si.toDouble - mean)*(si.toDouble-mean) ).sum /n.toDouble )
    
  }
}

Measured memory_bytes: 44672
n = int(input())
s = []
a = 0
for i in range(n):
  sk = int(input())
  s.append(sk)
s.append(0)
s.sort()
a = sum(s)
for i in s:
  a -= i
  if a % 10 != 0:
    break
  else:
    a += i
if a % 10 == 0: 
  a = 0
print(a)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void shortestPath(const Matrix &g,
    Matrix &dist, vector< vector<int> > &inter) {
  int n = g.size();
  dist = g;
  inter.assign(n, vector<int>(n,-1));
  REP(k, n) REP(i, n) REP(j, n) {
    if (dist[i][j] > dist[i][k] + dist[k][j]) {
      dist[i][j] = dist[i][k] + dist[k][j];
      inter[i][j] = k;
    }
  }
}
void buildPath(const vector< vector<int> > &inter,
    int s, int t, vector<int> &path) {
  int u = inter[s][t];
  if (u < 0) path.push_back(s);
  else buildPath(inter, s, u, path), buildPath(inter, u, s, path);
}
vector<int> buildPath(
    const vector< vector<int> > &inter, int s, int t) {
  vector<int> path;
  buildPath(inter, s, t, path);
  path.push_back(t);
  return path;
}

void solve(long long N, long long M, vector<long long> a, vector<long long> b, vector<long long> c){
  Matrix mat;
  int edges[100][100] = {0};
  for ( int i = 0; i < N; i++ ) {
    for ( int j = 0; j < N; j++ ) {
      if ( i == j ) { continue; }
      edges[i][j] = 100000000;
    }
  }
  for ( int i = 0; i < M; i++ ) {
    edges[a[i]-1][b[i]-1] = c[i];
    edges[b[i]-1][a[i]-1] = c[i];
  }
  for ( int i = 0; i < N; i++ ) {
    Array ws;
    for ( int j = 0; j < N; j++ ) {
      Weight w = edges[i][j];
      ws.push_back(w);
    }
    mat.push_back(ws);
  }

  Matrix dist;
  vector<vector<int>> inter;
  shortestPath(mat, dist, inter);

  int ans = 0;
  for ( int i = 0; i < M; i++ ) {
    if (dist[a[i]-1][b[i]-1] < c[i]) {
      ans ++;
    }
  }

  cout << ans << endl;
}

int main(){
	long long N;
	long long M;
	scanf("%lld",&N);
	scanf("%lld",&M);
	vector<long long> c(M-1+1);
	vector<long long> b(M-1+1);
	vector<long long> a(M-1+1);
	for(int i = 0 ; i <= M-1 ; i++){
		scanf("%lld",&a[i]);
		scanf("%lld",&b[i]);
		scanf("%lld",&c[i]);
	}
	solve(N, M, a, b, c);
	return 0;
}



Measured memory_bytes: 512