akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

long long bin_pow(long long a, long long n, long long m)
{
    if(n == 0)
        return 1;
    long long p = bin_pow(a, n / 2, m);
    if(n % 2 == 0)
        return (p * p) % m;
    else
        return (((p * p) % m) * a) % m;
}

long long c(long long n, long long k)
{
    long long x = 1;
    for(long long i = n - k + 1; i <= n; i++)
    {
        x *= i;
        x %= MOD;
    }
    long long y = 1;
    for(long long i = 1; i <= k; i++)
    {
        y *= i;
        y %= MOD;
    }
    y = bin_pow(y, MOD - 2, MOD);
    long long ans = (x * y) % MOD;
    return ans;
}

int main()
{
    long long n, a, b;
    cin >> n >> a >> b;
    long long all = bin_pow(2, n, MOD);
    all--;
    long long cna = c(n, a);
    long long cnb = c(n, b);
    cna %= MOD;
    cnb %= MOD;
    cout << ((all - (cna + cnb) % MOD) + MOD) % MOD;
    return 0;
}


Measured memory_bytes: 256
from functools import reduce

s = list(input().split())
#numA = None
#numB = None
temp = []
#ans = []
#ans = None

for i in range(len(s)):
    if s[i] == '+':
        temp.append(temp.pop() + temp.pop())
    elif s[i] == '-':
        temp.append(-(temp.pop() - temp.pop()))
    elif s[i] == '*':
        temp.append(temp.pop() * temp.pop())
    else:
        temp.append(int(s[i]))

#    print("\ns[i]: " + s[i])


print(temp.pop())


Measured memory_bytes: 6280
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
using namespace std;
using ll = long long;
int main(){
  int a,b,c;
  cin >> a >> b >>c;
  if(a>b+c) cout << 0 << endl;
  else cout << c-(a-b) << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
string s1,s2;
int main(){
    cin>>s1>>s2;
    for(int i=0;i<s1.size();++i){
        cout<<s1[i];
        if(i<s2.size())
            cout<<s2[i];
    }
    cout<<endl;
    return 0;
}

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

using namespace std;

#define ALL(x) x.begin(), x.end()

typedef long long int lld;
typedef pair<int, int> pii;

const int maxn = 1e5+5;

int num[maxn];
int dp[maxn];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(15);
	cout << fixed;

	int n = 0;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}

	for (int i = 1; i < n; i++) {
		if (i == 1)
			dp[i] = abs(num[i] - num[i - 1]);
		else
			dp[i] = min(dp[i - 1] + abs(num[i] - num[i - 1]), dp[i - 2] + abs(num[i] - num[i - 2]));
	}
	
	cout << dp[n - 1] << endl;

	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int w = sc.nextInt();
		int n = sc.nextInt();
		int x;
		int[] values = new int[w];
		for (int i = 0; i < values.length; i++) {
			values[i] = i + 1;
		}
		for (int i = 0; i < n; i++) {
			String str = sc.next();
			String[] ab = str.split(",");
			int a = Integer.parseInt(ab[0]) - 1;
			int b = Integer.parseInt(ab[1]) - 1;
			x = values[a];
			values[a] = values[b];
			values[b] = x;
		}
		for (int i = 0; i < w; i++) {
			System.out.println(values[i]);
		}
	}
}

Measured memory_bytes: 25948
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n, m, dp[100001], x, y, in[100001], ans; bool vis[100001];
vector<int> adj[100001];
queue<int> q;
int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> x >> y;
        adj[x].pb(y); in[y]++;
    }
    for (int i = 1; i <= n; i++){
        if (!in[i]){
            q.push(i);
            in[i]--;
        }
    }
    while(!q.empty()){
        int p = q.front(); q.pop();
        ans = max(ans, dp[p]);
        for (int v : adj[p]){
            dp[v] = max(dp[v], dp[p] + 1);
            if (--in[v] == 0) q.push(v);
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 6528
#include<iostream>
using namespace std;
int main(){
    int h,w;
    cin >> h >> w;
    while(h!=0){
        int i,j;
       
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                    if((j+i)%2==0){
                        cout << "#";
                    }else{
                        cout << ".";
                    }
                }
            cout << endl;
            }
         cout << endl;
         cin >> h >> w;
    }
    return 0;
}



Measured memory_bytes: 3088
let m = 1000000007
let ( +^ ) x y = (x + y) mod m
let ( -^ ) x y = x +^ (m - y)
let ( *^ ) x y = (x * y) mod m

let rec power ( * ) e m n =
  if n <= 0 then e
  else power ( * ) (if n land 1 = 0 then e else m * e) (m * m) (n lsr 1)

let perm n k =
  Array.fold_left ( *^ ) 1 @@
  Array.init k @@ fun i -> (i + n - k + 1) mod m
let comb n k = power ( *^ ) (perm n k) (perm k k) (m - 2)

let () = Scanf.scanf "%d %d" @@ fun n k ->
  let perm_n = Array.make (min n k + 1) 1 in
  let perm_n1 = Array.make (min n k + 1) 1 in
  let perm_kk = Array.make (min n k + 1) 1 in
  for i = 0 to min n k - 1 do
    perm_n.(i + 1) <- (n - i) mod m *^ perm_n.(i);
    perm_n1.(i + 1) <- (n - i - 1) mod m *^ perm_n1.(i);
    perm_kk.(i + 1) <- (i + 1) *^ perm_kk.(i)
  done;
  let combn k = power ( *^ ) perm_n.(k) perm_kk.(k) (m - 2) in
  let combn1 k = power ( *^ ) perm_n1.(k) perm_kk.(k) (m - 2) in
  Printf.printf "%d\n" @@
  Array.fold_left ( +^ ) 0 @@
  Array.init (min n k + 1) @@ fun i -> combn i *^ combn1 i

Measured memory_bytes: 8192
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication51
{
    class Program
    {
        static void Main(string[] args)
        {
            string line;
            while ((line = Console.ReadLine()) != null)
            {
                double a = double.Parse(line);
                double b = a / 9.8;
                double c = b * b * 4.9;
                int d = 1;
                while (true)
                {
                    if (5 * d >= c)
                        break;
                    d++;
                }
                Console.WriteLine(d + 1);
            }
        }
    }
}

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

int ans(int a, int b) {
    for (int i = 1; i <= 3; i++) {
        if (i == a || i == b) {
            continue;
        }

        return i;
    }
}

int main() {
    int a, b;
    cin >> a >> b;

    cout << ans(a, b) << endl;

    return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<((a-c)*(b-d))<<endl;
  return 0;
}


Measured memory_bytes: 256
// ABC177A - Don't be late

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;

int main() {
	int D, T, S;
	cin >> D >> T >> S;

	if (T * S >= D) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 3616
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		StringBuilder sb=new StringBuilder();
		for(int i = 0;i<n;i++) {
			var e=sc.Ia;
			sb.Append(((e[0]-1)*127+((e[0]&1)==1?e[1]:(e[1]^127)))+"\n");
		}
		Console.Write(sb);
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 11188
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int color[100005];
vector<vector<int>> g;
bool dfs(int u,int c){
    color[u] = c;
    for(int i=0;i<g[u].size();i++){
        int v = g[u][i];
        if(color[v] == c){
            return false;
        }
        if(color[v] == 0 && !dfs(v,-c) ){
            return false;
        }
    }
    return true;
}
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll n,m;
    cin >> n >> m;
    g.resize(n);
    rep(i,m){
        int x,y;
        cin >> x >> y;
        x--;y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    ll B = 0 , W = 0;
    if(dfs(0,1)){
        for(int i=0;i<n;i++){
            if(color[i]==1){
                B++;
            }else if(color[i]==-1){
                W++;
            }
        }
        cout << B*W - m << endl;
    }else{
        cout << (n*(n-1))/2 - m << endl;
    }
}

Measured memory_bytes: 6528
#include<cstdio>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(void) {
	long long X, K, D;
	scanf("%lld %lld %lld", &X, &K, &D);
	if (X >= 0) {
		if (K <= X / D + 1) {
			printf("%lld\n", abs(X - K * D));
		} else {
			int rest = K - X / D;
			if (rest % 2 == 0) printf("%lld\n", X % D);
			else printf("%lld\n", abs(X % D - D));
		}
	} else {
		if (K <= abs(X) / D + 1) {
			printf("%lld\n", abs(X + K * D));
		} else {
			int rest = K - abs(X) / D;
			if (rest % 2 == 0) printf("%lld\n", abs(X) % D);
			else printf("%lld\n", -1 * (abs(X) % D) + D);
		}
	}
	return 0;
}


Measured memory_bytes: 3824
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String date = sc.next();
		Scanner a = new Scanner(date).useDelimiter("/");
		int i = 0;
		String[] list = new String[3];
		while(a.hasNext()) {
			list[i] = a.next();
			i++;
		}
		if(!list[0].equals("2018"))
			list[0] = "2018";
		System.out.println(list[0] + "/"+list[1] +"/"+list[2]);
		
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <limits>
#include <unordered_map>

using namespace std;
using str = string;

#define rep(a,l,r) for(int a=(l);a<(r);a++)
#define get cin>>
#define put cout<<

void run() {

	int k; get k;
	int ans{0};

	if (k%2==1){
		ans = (k / 2) * (k / 2 + 1);
	} else {
		ans = (k / 2) * (k / 2);
	}

	put ans;
}

int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);run();return 0;}


Measured memory_bytes: 256
#!/usr/bin/python
# -*- coding: utf-8 -*-
n = int(raw_input())
s = []
for _ in xrange(n):
    s.append(raw_input())

ss = set()
last = None
ret = 'Yes'
for w in s:
    if w in ss:
        ret = 'No'
        break
    if last is None:
        ss.add(w)
        last = w
        continue
    if last[-1] != w[0]:
        ret = 'No'
        break
    ss.add(w)
    last = w

print ret

Measured memory_bytes: 2696
// Problem : C - management
// Contest : AtCoder - AtCoder Beginner Contest 163
// URL : https://atcoder.jp/contests/abc163/tasks/abc163_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/coder3101/cp-editor)

// Mere bas ka nahi hai
// still i'm trying
// apna time aayega
//
//        .--------------.  
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |  
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'                          		  
//
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll power(ll x,ll y,ll m){if(y==0)return 1;ll p=power(x,y/2,m)%m;p=(p*p)%m;return (y%2==0)?p:(x*p)%m;}
ll nCr(ll n,ll r,ll m){if(r>n)return 0;ll a=1,b=1,i;for(i=0;i<r;i++){a=(a*n)%m;--n;}while(r){b=(b*r)%m;--r;}return (a*power(b,m-2,m))%m;}
#define Test int t;cin>>t;while(t--)
#define endl '\n'
void solve()
{
	int n;
	cin >> n;
	vector<int> v(n+1);
	for(int i=0;i<n-1;++i)
	{
		int temp;
		cin >> temp;
		v[temp]++;
	}
	for(int i=1;i<=n;++i)
	cout << v[i] << endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//Test
	solve();
	return 0;
}


Measured memory_bytes: 3988
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
double Pi = 3.1415926535897932384626;
 
//vector<ll> G[550010];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
ll mod = 1000000007;
/*
2000000011 is prime
2000000033 is prime
*/

ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}

/*
ll fact[800005],rfact[800005];

void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=800000; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[800000] = rui(fact[800000],mod - 2);
    for(ll i=800000; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod) * rfact[n-r]) % mod;}
*/
 
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r,l;
ll k,ans;
ll x[500005],y[500005],z[500005];
char s[50],t[50];
bool dp[500005];

int main(){
    cin >> n;
    if(n == 1){
        p(0);
    }else if(n == 2){
        p(1);
    }else{
        p(n * (n - 1) / 2);
    }
    return 0;
}






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

using namespace std;
int N;
vector<long long> a;

int gcd(long long a, long long b){
  if (a == 0) return b;
  else gcd(b % a, a);
}

int gcd_vec(vector<long long> a){
  int ans = a[0];
  for(int i =1; i< a.size(); i++){
    ans = gcd(ans, a[i]);
  }
  return ans;
}

int main(){
  cin >> N;
  a.resize(N);
  for(int i =0; i< N;i++){
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  cout << gcd_vec(a);
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<typeinfo>
#include<complex>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)
const long double PI = (acos(-1));

int main() {

	int n;
	cin >> n;

	int maxi = 0, cnt = 0;

	vector<int> h(n);
	rep(i, 0, n) {
		cin >> h[i];
		if (h[i] >= maxi) {
			cnt++;
			maxi = h[i];
		}
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;

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

  long long n;
  cin >> n;
  for(int i = 1; i < 10; i++){
    if(n%i == 0 and n/i < 10){
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
char c[100005];
int s;
int main(){
	scanf("%s",c);
	for(int i=0;i<strlen(c);++i){
		if(c[i]=='g'&&i%2)++s;
		if(c[i]=='p'&&i%2==0)--s;
	}
	printf("%d\n",s);
    return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())

A = [[a for a in input()] for _ in range(H)]
flag = True
while flag:
    flag = False
    # 行方向
    rm = []
    for i, a in enumerate(A):
        if '#' not in a:
            rm.append(i)
    if len(rm) > 0:
        flag = True
        A = [a for i, a in enumerate(A) if i not in rm]
    # 列方向
    rm = []
    A = list(zip(*A))
    for i, a in enumerate(A):
        if '#' not in a:
            rm.append(i)
    if len(rm) > 0:
        flag = True
        A = [a for i, a in enumerate(A) if i not in rm]
    A = list(zip(*A))

for a in A:
    print(''.join(a))


Measured memory_bytes: 38768
import sys
import collections
# import math
# import string
import bisect
# import re
# import itertools
# import statistics

def main():
    n, k, *a = (int(x) for x in sys.stdin.read().split())

    c = collections.Counter(a)
    diffs = len(c)
    if diffs <= k: print(0); exit()
    remainder = diffs - k
    count = 0
    l = sorted(c.values())
    for i in range(1, n+1):
        b = bisect.bisect_right(l, i) - bisect.bisect_left(l, i)
        if remainder - b >= 0:
            count += b * i
            remainder -= b
        else:
            count += remainder * i
            break
    
    print(count)

if __name__ == "__main__":
    # execute only if run as a script
    main()


Measured memory_bytes: 33556
#include<bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
using namespace std;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

int main() {
	int n, k; cin >> n >> k;
	string s; cin >> s;
	vector<ll> sum;
	sum.push_back(0);
	rep(i, n) {
		int c = 0;
		char prev = s[i];
		while (s[i] == prev) {
			c++;
			i++;
		}
		i--;
		sum.push_back(c);
	}
	int sz = sum.size();
	rep(i, sz - 1) sum[i + 1] += sum[i];
	ll ans = 0;
	if (s[0] == '1') {
		rep(i, sz) {
			if (i % 2) chmax(ans, sum[min(sz - 1, i + k * 2)] - sum[i]);
			else chmax(ans, sum[min(sz - 1, i + k * 2 + 1)] - sum[i]);
		}
	}
	else {
		rep(i, sz) {
			if (i % 2) chmax(ans, sum[min(sz - 1, i + k * 2 + 1)] - sum[i]);
			else chmax(ans, sum[min(sz - 1, i + k * 2)] - sum[i]);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4424
N, K = gets.chomp.split(" ").map(&:to_i)
P = N.times.map{ gets.chomp.split(" ").map(&:to_i)}.sort_by{|x| x[0]}

ans = []
(0..(N-K)).each{|i|
  ((i+K-1)...N).each{|j|
    wdt = P[j][0] - P[i][0]
    ext = P[i..j].sort_by{|x| x[1]}
    (0..(ext.size-K)).each{|k|
      hgt = ext[k+K-1][1] - ext[k][1]
      ans << (wdt * hgt)
    }
  }
}

puts ans.min


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

int main(void){
    int n,k,i,p_summax,p_sum,j;
    double exp,exp_sum0,exp_sum1,exp_summax,exp_sum;

    exp = 0;
    exp_sum0 = 0;
    exp_sum1 = 0;
    exp_summax = 0;


    cin >> n >> k;
    vector<int>  p(n);
    for(i=0; i<n; i++){
        cin >> p.at(i);
    }


    for(i=0; i<k; i++){
        exp_sum0 += 1 + 0.5*(p.at(i) - 1);
    }
    exp_summax = exp_sum0;


    for(i=k; i < n; i++){
        exp_sum1 = exp_sum0 - (1 + 0.5*p.at(i-k)) + (1 + 0.5 * p.at(i));
        exp_summax = max(exp_summax,exp_sum1);
        exp_sum0 = exp_sum1;
    }

    cout << fixed;
    cout << setprecision(7) << exp_summax << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define less Less
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define KK 500
#define MXN 200005
double cal(int n,double d,double x){
 //   printf("%d %lf %lf\n",n,d,x);
    if(n==0)return 0;
    double res=(d+d+(2*n-1)*x)/2;
    return res+cal(n-1,((2*n+2)*d+5*x)/(2*n),(2*n+4)*x/(2*n));
}
int main(){
    int n,d,x;
    scanf("%d %d %d",&n,&d,&x);
    printf("%.12lf\n",cal(n,d,x));
}
/*

b[i]*K!/(i)!*(K-i)!
*/

Measured memory_bytes: 6528
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Logic logic = new Logic1();
        long start = System.nanoTime();
        logic.solve(sc);
        long end = System.nanoTime();
//        System.out.println(((end - start)/1_000_000) + "ms");
    }
}


interface Logic {
    void solve(Scanner sc);
}

class Logic1 implements Logic {

    @Override
    public void solve(Scanner sc) {
        int X = sc.nextInt();
        int Y = sc.nextInt();
        int Z = sc.nextInt();
        int K = sc.nextInt();

        long[] a = new long[X];
        long[] b = new long[Y];
        long[] c = new long[Z];

        for (int i=0; i<X; i++) {
            a[i] = sc.nextLong();
        }
        for (int i=0; i<Y; i++) {
            b[i] = sc.nextLong();
        }
        for (int i=0; i<Z; i++) {
            c[i] = sc.nextLong();
        }
        PriorityQueue<Long> queue1 = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i=0; i<X; i++) {
            for (int j=0; j<Y; j++) {
                queue1.add(a[i]+b[j]);
            }
        }
        PriorityQueue<Long> queue2 = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i=0; i<K; i++) {
            long e;
            if (queue1.size() > 0) {
                e = queue1.poll();
            } else {
                break;
            }
            for (int j=0; j<Z; j++) {
                queue2.add(e+c[j]);
            }
        }
        for (int i=0; i<K; i++) {
            System.out.println(queue2.poll());
        }
    }
}


class Logic2 implements Logic {

    @Override
    public void solve(Scanner sc) {

    }
}


Measured memory_bytes: 194020
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
suti = 0

for i in range(n):
    suti += b[a[i]-1]
    if i != 0 and a[i]-a[i-1] == 1:
        suti += c[a[i]-2]

print(suti)


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

int main()
{
	int a[5],b,c=0;
	for (int i = 0; i < 5; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < 4; i++)
	{
		if (a[i] % 10 < a[i + 1] % 10&&a[i]%10!=0||a[i+1]%10==0)
		{
			b = a[i];
			a[i] = a[i + 1];
			a[i + 1] = b;
		}
		if(a[i]%10!=0)
		a[i] = a[i] + (10 - a[i] % 10);
		c += a[i];
	}
	cout << c+a[4];
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long int ff(long long int n) {
	if (n == 0) {
		return 0;
	}
	else {
		return ff(n / 10) + n % 10;
	}
}

int main() {

	long long int n;
	cin >> n;

	if (n % ff(n) == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
h, w = list(map(int, input().split()))
c_list = [list(input()) for _ in range(h)]

for i in range(len(c_list) * 2):
    for j in range(len(c_list[0])):
        print(c_list[min((i) // 2, h - 1)][j], end="")
    print()


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

int main(){

    int N;
    string S;
    int bNum = 0;
    int wNum = 0;

    vector <int> ans;

    cin >> N;
    cin >> S;

    for(int i = 0; i < N; i++){
        if(S[i] == '#') bNum ++;
        else wNum ++;
    }

    if(bNum == 0 || wNum == 0){
        cout << "0" << endl;
        return 0;
    }

    int BtoW = 0;
    for(int i = 0; i < N ; i++){
        if(S[i] == '#'){
            ans.push_back(min(wNum, bNum) + BtoW);
            BtoW += 1;
            bNum -= 1;
        }
        else{
            wNum -= 1;
        }
    }

    int minAns = *min_element(ans.begin(), ans.end());
    cout << minAns << endl;
}

Measured memory_bytes: 1024
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
l = r = lv = rv = 0
for i in range(n):
    if s[i]=='(':
        l += 1
    elif l>0:
        l -= 1
    else:
        rv += 1
for i in range(n-1,-1,-1):
    if s[i]==')':
        r += 1
    elif r>0:
        r -= 1
    else:
        lv += 1
print('('*rv+s+')'*lv)


Measured memory_bytes: 38384
/* generated by esotope-bfc */
#include <stdio.h>
#include <stdint.h>
#define GETC() (fflush(stdout), fgetc(stdin))
#define PUTC(c) fputc(c, stdout)
static uint8_t m[30000], *p = m;
int main(void) {
        p[1] = GETC();
        p[2] = 0;
        p[1] -= 32;
        p[3] = 0;
        while (p[1]) {
                p[2] += 4;
                p[1] += 8*p[2];
                p[2] = GETC();
                p[3] += 4;
                p[2] -= 8*p[3];
                p[3] = 0;
                ++p;
        }
        while (p[0] != 0) --p;
        p[0] = GETC();
        p[0] -= 10;
        while (p[0]) {
                p[0] += 10;
                PUTC(p[0]);
                p[0] = GETC();
                p[0] -= 10;
        }
        while (p[1]) {
                PUTC(p[1]);
                ++p;
        }
        return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;


int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    REP(i, n){ cin >> a.at(i); }

    vector<ll> cs(n, 0), cs2(n, 0);
    REP(i, n){
        cs.at(i) = a.at(i);
        cs2.at(i) = max(a.at(i), 0LL);
        if(i > 0){
            cs.at(i) += cs.at(i - 1);
            cs2.at(i) += cs2.at(i - 1);
        }
    }
    const auto rngsum = [](const vector<ll>& cs, ll l, ll r) -> ll {
        if(l >= r || cs.size() == 0){ return 0; }
        r = min((ll)cs.size(), r);
        ll ret = cs.at(r - 1);
        if(l > 0){
            ret -= cs.at(l - 1);
        }
        return ret;
    };

    ll ans = numeric_limits<ll>::min();
    REP(i, n - k + 1){
        ll tmp = rngsum(cs2, 0, i) + rngsum(cs2, i + k, n);
        ans = max(ans, tmp);
        ans = max(ans, tmp + rngsum(cs, i, i + k));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5636
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P>IP;
typedef vector<ll> V;
typedef vector<V> V2;
typedef vector<vector<P> > G;
void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}
void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}
const ll INF = 1145141919;
const ll MOD = 1000000007;
const ll NUM = 101010;

int main(){

    ll N, D, A;
    cin >> N >> D >> A;
    vector<P>v;
    rep(i, N){
        ll x, h;
        cin >> x >> h;
        v.push_back(P(x, h));
    }
    sort(v.begin(), v.end());
    priority_queue<P, vector<P>, greater<P> >Q;
    Q.push(P(1145141919810LL, 0));
    ll ans = 0, sum = 0;
    rep(i, N){
        ll x = v[i].first;
        ll h = v[i].second;
        while(x > Q.top().first){
            sum -= Q.top().second;
            Q.pop();
        }
        if(sum >= h)continue;
        ll tmp = 1 + (h - sum) / A;
        if((h - sum) % A == 0)tmp--;
        sum += tmp * A;
        ans += tmp;
        Q.push(P(x + 2 * D, tmp * A));
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 7020
n = int(input())
k = int(input())

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

distance = []

for i in range(n):
  if abs(x[i] - 0) < abs(x[i] - k):
    distance.append(abs((x[i] - 0) * 2))
  else:
    distance.append(abs((x[i] - k) * 2))

print(sum(distance))

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
long p[10000]={2,3,5,7,11,13,17,19,23},s,n,i,j=8;
while(cin>>n){
if(n==0)break;
while(n>j+1){
s=p[j];
for(;;){
s+=2;
for(i=1;p[i]*p[i]<=s;i++)if(s/p[i]*p[i]==s)break;
if(p[i]*p[i]>s){p[j+1]=s;break;}
}
j++;
}
for(s=i=0;i<n;i++)s+=p[i];
cout<<s<<endl;
}
return 0;
}

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

int main(){
  int n, m, l;
  cin >> n >> m >> l;

  int a[n][m];
  int b[m][l];
  long long c[n][l];

  //??????A??\???
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin >> a[i][j];
    }
  }

  //??????B??\???
  for(int i=0; i<m; i++){
    for(int j=0; j<l; j++){
      cin >> b[i][j];
    }
  }

  //??????C?????????
  for(int i=0; i<n; i++){
    for(int j=0; j<l; j++){
      c[i][j] = 0;
    }
  }

  //?¨??????????
  for(int i=0; i<n; i++){
    for(int j=0; j<l; j++){
      for(int k=0; k<m; k++){
        c[i][j] += a[i][k]*b[k][j];
      }
    }
  }

  //????????????
  for(int i=0; i<n; i++){
    for(int j=0; j<l; j++){
      if(j==l-1){
        cout << c[i][j] << endl;
      }else{
        cout << c[i][j] << " ";
      }
    }
  }

}

Measured memory_bytes: 3224
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;


int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	cout << s[0] <<  s[1]  << s[2];












	return 0;
}


Measured memory_bytes: 3604
S = input()
T = input()

max_num = 0
count = 0

for i in range(len(S)-len(T)+1):
  count = 0
  for j in range(len(T)):
    if S[i+j] == T[j]:
      count += 1
  if max_num < count:
    max_num = count
    
#print(max_num)
print(len(T)-max_num)

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

long X, Y;

int main() {
    cin >> X >> Y;
    int ans = 0;
    long nowA = X;
    while (nowA <= Y) {
        nowA *= 2;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {

    public static void main(String args[]) throws IOException {
        FastReader in = new FastReader();
        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);
        Task.solve(in, out);
        out.close();
    }

    static class Task {

        public static void solve(FastReader in, PrintWriter out) {
            int a = in.nextInt();
            int b = in.nextInt();
            if(a<=8&&b<=8){
                System.out.println("Yay!");
            }else{
                System.out.println(":(");
            }
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 21588
#include<bits/stdc++.h>
#define mod 1000000007
#define MOD(x) ((x)%mod)
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
int n;
char c[3005];
long long dp[3005][3005];
long long up[3005][3005];
long long low[3005][3005];
long long ans;
int main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
		scanf(" %c",&c[i]);
	dp[1][1]=1;
	up[1][1]=1;
	low[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		if(c[i]=='<')
		{
			for(int j=2;j<=i;j++)
				dp[i][j]=MOD(dp[i][j]+low[i-1][j-1]);
		}
		else
		{
			for(int j=1;j<i;j++)
				dp[i][j]=MOD(dp[i][j]+up[i-1][j]);
		}
		for(int j=1;j<=i;j++)
			low[i][j]=MOD(low[i][j-1]+dp[i][j]);
		for(int j=i;j>=1;j--)
			up[i][j]=MOD(up[i][j+1]+dp[i][j]);
	}
	for(int i=1;i<=n;i++)
		ans=MOD(ans+dp[n][i]);
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 210176
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long

int N;
ll cnt_A[100005]={0}, cnt_C[100005]={0}, ans=0;
vector<int> A, B ,C;

void solve(){
    for(int i = 0; i < N; i++){
        auto itrA = lower_bound(A.begin(), A.begin()+N, B[i]);
        cnt_A[i] = itrA - A.begin(); 
        
        auto itrC = upper_bound(C.begin(), C.begin()+N, B[i]);
        cnt_C[i] = N - (itrC - C.begin());
        
        ans += cnt_A[i] * cnt_C[i];
    }

    cout << ans << endl;
}

int main(){
    cin >> N;

    int buff;
    for(int i = 1; i <= N; i++){
        cin >> buff;
        A.push_back(buff);
    } 
    for(int i = 1; i <= N; i++){
        cin >> buff;
        B.push_back(buff);
    }
    for(int i = 1; i <= N; i++){
        cin >> buff;
        C.push_back(buff);
    }
 
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    sort(C.begin(),C.end());
    
    solve();
}


Measured memory_bytes: 3064
#import <stdio.h>
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)

int main() {
    char a[] = "CODEFESTIVAL2016";
    char b[17];
    scanf("%s", b);
    int ans = 0;
    rep(i, 17) if (a[i] != b[i]) ans++;
    printf("%d\n", ans);
}



Measured memory_bytes: 2164
#include<bits/stdc++.h>
#define pb push_back
#define rint register int
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=1e5+10;
const int inf=0x3f3f3f3f;

struct Edge{
	int vv,next,ww;
}e[2*maxn];

int n,u,v,w,tot;
int head[maxn],clr[maxn];

void add(int u,int v,int w){
	e[++tot].vv=v;
	e[tot].ww=w;
	e[tot].next=head[u];
	head[u]=tot;
}

void dfs(int x,int fa){
	for(rint i=head[x];i;i=e[i].next){
		int kx=e[i].vv;
		if(fa==kx) continue;
		clr[kx]=clr[x]^(e[i].ww%2);
		dfs(kx,x);
	}
}

int main(){
	scanf("%d",&n);
	for(rint i=1;i<n;++i) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	clr[1]=1;
	dfs(1,0);
	for(rint i=1;i<=n;++i) printf("%d\n",clr[i]);
	return 0;
}

Measured memory_bytes: 5632
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  in(a),in(b)
#define in3(a,b,c)  in2(a,b),in(c)
#define in4(a,b,c,d)  in2(a,b),in2(c,d)
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x,y) memset(x,y,sizeof(x))
ll read(){
    ll f=1,x=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 100010
#define inf 0x7fffffff
/*------------------------------------------------------------*/
bool check(int x){
	FOR(i,2,sqrt(x))
		if(x%i==0)return 0;
	return 1;
}
char c[100][100];
ll pow(ll a,ll b){
	FOR(i,1,b)a*=2;
	return a;
}
int main(){
	ll a,b,c,k;
	in4(a,b,c,k);
	ll f=max(max(a,b),c);
	ll ans=a+b+c-f+pow(f,k);
	outl(ans);
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

vector<vector<int>> v(111111);
ll n, m, ans;

void dfs(int now, int pre, ll num){
	ll cou = num;
	REP(i, v[now].size()){
		if(v[now][i] == pre)continue;
		ans *= max(0LL, (m - cou));
		ans %= MOD;
		cou++;
		dfs(v[now][i], now, min(2LL, num+1));
	}
}

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

	cin >> n >> m;
	REP(i, n-1){
		int a, b;cin >> a >> b;
		a--;b--;
		v[a].PB(b);
		v[b].PB(a);
	}

	ans = m;

	dfs(0, -1, 1);
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 10624
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int alphabet[2][30];

vector<string>ans;

string tostr(int a);

int main() {

	int n;

	scanf("%d",&n);

	string S;

	int i,j;

	for (i = 0; i < n; i++) {
		cin >> S;
		memset(alphabet[1],0,sizeof(alphabet[1]));
		for (j = 0; j < S.size(); j++) {
			alphabet[1][S[j] - 'a']++;
		}
		if (i == 0) {
			for (j = 0; j < S.size(); j++) {
				alphabet[0][S[j] - 'a']++;
			}
		}
		else {
			for (j = 0; j < 30; j++) {
				alphabet[0][j] = min(alphabet[0][j], alphabet[1][j]);
			}
		}
	}


	for (i = 0; i < 26; i++) {
		for (j = 0; j < alphabet[0][i]; j++) {
			if (i == 0) {
				ans.push_back("a");
			}
			else if (i == 1) {
				ans.push_back("b");
			}
			else if (i == 2) {
				ans.push_back("c");
			}
			else if (i == 3) {
				ans.push_back("d");
			}
			else if (i == 4) {
				ans.push_back("e");
			}
			else if (i == 5) {
				ans.push_back("f");
			}
			else if (i == 6) {
				ans.push_back("g");
			}
			else if (i == 7) {
				ans.push_back("h");
			}
			else if (i == 8) {
				ans.push_back("i");
			}
			else if (i == 9) {
				ans.push_back("j");
			}
			else if (i == 10) {
				ans.push_back("k");
			}
			else if (i == 11) {
				ans.push_back("l");
			}
			else if (i == 12) {
				ans.push_back("m");
			}
			else if (i == 13) {
				ans.push_back("n");
			}
			else if (i == 14) {
				ans.push_back("o");
			}
			else if (i == 15) {
				ans.push_back("p");
			}
			else if (i == 16) {
				ans.push_back("q");
			}
			else if (i == 17) {
				ans.push_back("r");
			}
			else if (i == 18) {
				ans.push_back("s");
			}
			else if (i == 19) {
				ans.push_back("t");
			}
			else if (i == 20) {
				ans.push_back("u");
			}
			else if (i == 21) {
				ans.push_back("v");
			}
			else if (i == 22) {
				ans.push_back("w");
			}
			else if (i == 23) {
				ans.push_back("x");
			}
			else if (i == 24) {
				ans.push_back("y");
			}
			else {
				ans.push_back("z");
			}

		}
	}

	sort(ans.begin(),ans.end());

	string s = "";

	for (i = 0; i < ans.size(); i++) {
		s += ans[i];
	}
	cout << s << endl;

	return 0;
}

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

using ll = long long;

constexpr ll MOD = 1e9+7;
constexpr ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

struct UnionFind
{
	vector<ll> par;

	void init(ll n) {par.assign(n, -1);}

	ll root(ll x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool merge(ll x, ll y)
	{
		x = root(x);
		y = root(y);
		if(x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

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

	ll size(ll x)
	{
		return -par[root(x)];
	}
};

int main(int argc, char **argv)
{
	ll N, M, K; cin >> N >> M >> K;
	vector<set<ll>> no(N);
	UnionFind uf;
	uf.init(N);

	REP(i, M)
	{
		ll a, b; cin >> a >> b;
		--a, --b;
		no[a].insert(b);
		no[b].insert(a);


		uf.merge(a, b);
	}

	REP(i, K)
	{
		ll c, d; cin >> c >> d;
		--c, --d;
		if (uf.issame(c, d))
		{
			no[c].insert(d);
			no[d].insert(c);
		}
	}

	REP(i, N)
		std::cout << (i?" ":"")<<uf.size(i) - no[i].size() - 1;
	std::cout << std::endl;
}


Measured memory_bytes: 25088
#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <cstdlib>
#include <iomanip>
#include <stdio.h>

using namespace std;

int main(){

  int n,score_a=0,score_b=0;
  char a[101],b[101];

  scanf("%d\n",&n);

  for(int i=0;i<n;i++){
     scanf("%s %s\n",a,b);
     int cmp = strcmp(a,b);
     if(cmp>0)
      score_a+=3;
     else if(cmp<0)
      score_b+=3;
     else {
      score_a++;
      score_b++;
     }
  }
  printf("%d %d\n",score_a,score_b);


}


Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F(i,a,b) for(int i=a;i<=b;i++)
ll n,m;
ll v[1000];
ll w[1000];
ll d[101][100000];
int main()
{
    cin>>n>>m;
    F(i,1,n)cin>>w[i]>>v[i];
    F(i,1,n)F(j,1,m)
    {
        if(w[i]<=j)d[i][j]=max(d[i-1][j],d[i-1][j-w[i]]+v[i]);
        else d[i][j]=d[i-1][j];
    }
    cout<<d[n][m];
}


Measured memory_bytes: 78336
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
typedef long long ll;

using namespace std;

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int ans=min(b,d)-max(a,c);
    if(ans<=0){
        cout<<0<<endl;
    }else{
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vout(v) VOUT(v,z);
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) { a = b; return true; }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) { a = b; return true; }
    return false;
}

const string YES = "Yes";
const string NO = "No";
#define judge(f) cout<<(f?YES:NO)<<"\n";

void solve(std::vector<std::vector<long long>> A, long long N, std::vector<long long> b){
    vector<vector<bool>> bingo(3,vector<bool>(3));
    for (long long i = 0; i < N; i++) {
        for(int j = 0 ; j < 3 ; j++){
            for(int k = 0 ; k < 3 ; k++){
                if(b[i]==A[j][k]) bingo[j][k]=true;
            }
        }
    }
    // mout(bingo);
    bool f=false;
    if(    (bingo[0][0] && bingo[0][1] && bingo[0][2])
        || (bingo[1][0] && bingo[1][1] && bingo[1][2])
        || (bingo[2][0] && bingo[2][1] && bingo[2][2])
        || (bingo[0][0] && bingo[1][0] && bingo[2][0])
        || (bingo[0][1] && bingo[1][1] && bingo[2][1])
        || (bingo[0][2] && bingo[1][2] && bingo[2][2])
        || (bingo[0][0] && bingo[1][1] && bingo[2][2])
        || (bingo[2][0] && bingo[1][1] && bingo[0][2])){
            f=true;
        }
    judge(f);
}

int main(){
    std::vector<std::vector<long long>> A(3, std::vector<long long>(3));
    for(int i = 0 ; i < 3 ; i++){
        for(int j = 0 ; j < 3 ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    long long N;
    scanf("%lld",&N);
    std::vector<long long> b(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&b[i]);
    }
    solve(std::move(A), N, std::move(b));
    return 0;
}


Measured memory_bytes: 256