akhauriyash/Code-Regression huggingface dataset:
// ORZ YJZ
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define rep(i,a,b) for(int (i) = (a); (i) <= (b); i++)
#define repd(i,a,b) for(int (i) = (a); (i) >= (b); i--)
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define mp make_pair
#define pb push_back
using namespace std;
#define is_digit(c) ((c) >= '0' && (c) <= '9')
#define is_upper(c) ((c) >= 'A' && (c) <= 'Z')
#define is_lower(c) ((c) >= 'a' && (c) <= 'z')
#define readchar() ((char)fgetc(stdin))
#define printchar(c) fputc((c), stdout)
void readline(char *s) {int len=0;char c;for(c=readchar(); c!='\n'; s[len++]=c, c=readchar());s[len]=0;}
void readstr(char *s) {int len=0;char c;for(c=readchar(); c!=' '&&c!='\n'; s[len++]=c, c=readchar());s[len]=0;}
void printstr(const char *s) {int len=strlen(s);rep(i,0,len-1) printchar(s[i]);}
void to_lower(char *s, int L, int R) {rep(i,L,R) if (is_upper(s[i])) s[i]=s[i]-'A'+'a';}
void to_upper(char *s, int L, int R) {rep(i,L,R) if (is_lower(s[i])) s[i]=s[i]-'a'+'A';}
ll readll() {
	char c;ll ans=0, x=1;for (c=readchar(); !is_digit(c)&&c!='-'; c=readchar());
	if (c=='-') x=-1, c=readchar();for (; is_digit(c); ans=ans*10+c-'0', c=readchar());return ans*x;
}
void printll(ll x) {
	int a[25], cnt=0;if (x==0) { printchar('0'); return; }if (x<0) printchar('-'), x=-x;
	for (; x; a[cnt++]=x-x/10*10, x/=10);repd(i,cnt-1,0) printchar(a[i]+'0');
}
#define readint() ((int)readll())
#define printint(x) printll((ll)(x))
int n, K, a[5005];
bool dp[5005];
int main() {
	n=readint();K=readint();
	rep(i,1,n) a[i]=readint();
	sort(a+1,a+1+n);
	while (a[n]>=K) n--;
	int l=0, r=n+1, m=0;
	while (l+1<r) {
		m=(l+r)>>1;
		int i=m;
		memset(dp,0,sizeof(dp));
		dp[0]=true;
		rep(j,1,n) {
			if (j==i) continue;
			repd(k,K-1,0) {
				if (k+a[j]<K) dp[k+a[j]]|=dp[k];
			}
		}
		bool f=true;
		rep(j,K-a[i],K-1) {
			if (!dp[j]) continue;
			f=false;break;
		}
		if (f) l=m; else r=m;
	}
	printint(l);
	return 0;
}

Measured memory_bytes: 384
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  a=LI()
  b=LI()
  c=LI()

  for i in range(2):
    if not (a[i+1]-a[i]==b[i+1]-b[i] and b[i+1]-b[i]==c[i+1]-c[i]):
      return 'No'

  return 'Yes'

print(main())


Measured memory_bytes: 5420
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int ans = 0;
  
  for(int i = 0; i < S.length() - 1; i++){
    
  	if(S.at(i) == 'C'){
    	for(int j = i+1; j < S.length(); j++){
        	if(S.at(j) == 'F'){
            	ans = 1;
            }
        }
    }
    
    
  }
  
  if(ans == 1){
  	cout << "Yes" << endl;
  }else{
  	cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

// aのn乗を求める。計算量はO(logn)
ll modpow(ll a, ll n) {
    if(n == 0) {
        return 1;
    }
    if(n%2 == 1) {
        return (a * modpow(a, n-1))%mod;
    }
    return (modpow(a, n/2) * modpow(a, n/2))%mod;
}

int main() {
    ll n;
    cin >> n;

    vl c(n);
    rep(i, n) {
        cin >> c[i];
    }
    sort(rall(c));

    ll ans = 0;
    rep(i, n) {
        ans += c[i]*(i+2);
        ans %= mod;
    }

    ans *= modpow(4, n-1);
    ans %= mod;

    out(ans);
    re0;
}

Measured memory_bytes: 1792
n = int(input())
s = list(input())
l = []
count = 0
r = count
for i in range(n):
  a = s.pop(0)
  if (a in s) and (a not in l):
    count += 1
    if count > r:
      r = count
  elif (a not in s) and (a in l):
    count -= 1
  l.append(a)
print(r)


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

int main() {
  ll n,k;
  ll ans = 0;
  cin >> n >> k;
  rep(b,k+1,n+1){
    ans += (b-k)*(n/b);
    if(n%b != 0) ans += max(0LL,n%b-k+1);
  }
  if(ans >= n*n) ans = n*n;
  cout << ans << endl;
}

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

#define pb push_back
#define eb emplace_back
#define mk make_pair
#define fi first
#define se second
#define mset(a, b) memset(a, b, sizeof(a))
#define DBG(x) cout << "[" << #x << "]: " << x << endl
using ll = long long;
using pii = pair<int, int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

template<class Ty> Ty randint(Ty a, Ty b) { return uniform_int_distribution<Ty>(a, b)(rng); }
template<class num> inline void rd(num& x) {
	char c, neg = 0; while(isspace(c = getchar_unlocked()));
	if(!isdigit(c)) neg = (c == '-'), x = 0;
	else x = c - '0';
	while(isdigit(c = getchar_unlocked())) x = (x << 3) + (x << 1) + c - '0';
	x = neg ? -x : x; }
template <class... Args> inline void rd(Args&... args) { (rd(args), ...); }

const int MAXN = 1e6 + 5, INF = 0x3f3f3f3f;

int cnt[MAXN];
bool comp[MAXN];

int main() {
	comp[1] = 1;
	for (int i = 2; i < MAXN; i++) {
		if (comp[i]) continue;
		for (int j = i + i; j < MAXN; j += i)
			comp[j] = 1;
	}


	int n; rd(n);

	int g = 0;
	for (int i = 1; i <= n; i++) {
		int x; rd(x);
		g = gcd(x, g);

		if (comp[x])
		for (int j = 2; j * j <= x; j++) {
			if (x%j == 0) {
				cnt[j]++;
				while(x % j == 0) x /= j;
			}
		}

		if (x > 1) cnt[x]++;
	}

	bool ans1 = true;
	for (int p = 2; p < MAXN; p++)
		if (cnt[p] > 1) ans1 = false;

	if (ans1) puts("pairwise coprime");
	else if (g == 1) puts("setwise coprime");
	else puts("not coprime");

}

Measured memory_bytes: 8528
import java.util.*;
class Main{
    public static void main(String a[]){
      Scanner s=new Scanner(System.in);
      int n = s.nextInt();
      int m = s.nextInt();
      System.out.print(m==1&&n==1?1:m==2||n==2?0:(long)(n==1?1:n-2)*(m==1?1:m-2));
  }
}


Measured memory_bytes: 21844
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    ll n; cin>>n;
    vector<vector<ll>>a(300,vector<ll>(2));
    ll cnt=0;
    vector<ll>A(n);
    rep(i,n){
        cin>>A[i];
        rep(j,A[i]){
            cin>>a[cnt][0]>>a[cnt][1];
            cnt++;
        }
    }
    a.resize(cnt);
    vector<ll>sumA(n+1);
    sumA[0]=0;
    rep(i,n){
        sumA[i+1]=sumA[i]+A[i];
    }

    ll ans=0;
    ll mx;
    bool judge;
    for(int tmp=0;tmp<(1<<n);tmp++){
        bitset<15>b(tmp);
        mx=0;
        judge=false;
        rep(i,n){
            if(b.test(i)){
                for(int k=sumA[i];k<sumA[i+1];k++){
                    if(a[k][1]==1){

                        if(!b.test(a[k][0]-1)){
                            judge =true;
                            break;
                        }
                    }
                    else{
                        if(b.test(a[k][0]-1)){
                            judge=true;
                            break;
                             }
                   
                    }
                }
                if(judge)break;
            }
    
        }
        if(!judge){
            mx=b.count();
        }

        ans=max(ans,mx);
    }
    cout<<ans<<endl;
}



























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

int main() {
  int N;
  cin >> N;
  
  vector<int> p(N);
  for(int i=0; i<N ;i++){
    cin >> p.at(i);
  }
  
  sort(p.begin(),p.end());
  
  int ans = 1;
  
  for(int i=0; i<N-1 ;i++){
    int goukei=1;
    for(int j=1; j<N-i ; j++){
      if(p.at(i)==p.at(i+j) || p.at(i)+1==p.at(i+j) || p.at(i)+2==p.at(i+j)){
        goukei++;
      }
     else if(p.at(i)+2<p.at(i+j)){
       break;
     }
    }
    if(goukei>ans){
      ans = goukei;
    }
    if(ans>N-i){
      break;
    }
  }
  
  cout << ans << endl;    
                       
  
  
  
}

Measured memory_bytes: 3700
#include <iostream>
#include <string>

int main(void){
    using namespace  std;
    string S, T;
    cin >> S >> T;
    int A, B;
    cin >> A >> B;
    string U;
    cin >> U;
    if(U==S)
        A--; else
        B--;
    cout << A << " " << B << endl;

    return 0;
}

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

struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;
using intpair = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((int)((a) + (b) - 1)/(int)(b))
//#define int long long

signed main(){
    int n, m;
    cin >> n >> m;
    rep(i,m){
        int a; cin >> a;
        n -= a;
    }
    cout << max(-1,n) << endl;
}

Measured memory_bytes: 3640
using namespace std;

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <limits>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
typedef long long ll;
typedef pair<int,int> p;

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)




int main()
{
  // input & declare
  string s;
  cin >> s;
  s[3] = '8';
  std::cout << s << '\n';


}


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

int main(){
    int N; cin>>N;
    vector<int> H(N);
    for(int i=0;i<N;i++) cin>>H[i];
    int n=H[0]-1;
    for(int i=1;i<N;i++){
        if(n<=H[i]-1) n=H[i]-1;
        else if(n<=H[i]) n=H[i];
        else{
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 640
import math

data = input().split()

loop_count = int(data[0])
moto = int(data[1])
least_donut = 100000
one = 0

for i in range(loop_count):
    gram = int(input())
    one = one + gram
    if gram < least_donut:
        least_donut = gram

nokori = moto - one
print(loop_count + math.floor(nokori / least_donut))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <time.h>
//#include <random>
//#ifndef _LOCAL
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#endif
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define pii pair <int, int>
#define pll pair <ll, ll>
#define ft first
#define sd second
#define pb push_back
#define ppb pop_back
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
#define re return
#define nins 4294967295
using namespace std;
typedef long long ll;
typedef long double ld;

//mt19937 rnd(0);

void solve() {
    ll n, sum = 0;

	cin >> n;
	for (ll i = 1; i <= n; i++)
        if (i % 3 && i % 5)
            sum += i;

    cout << sum;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef _LOCAL
//        in("input.txt");

        int t = 1;
//        cin >> t;
        for (int i = 1; i <= t; i++) {
            cout << "Test #" << i << elf;

            clock_t start_time = clock();

            solve();

            cerr.precision(4); cerr << fixed;
            cerr << elf;
            cerr << "Time :: " << ld(clock() - start_time) / CLOCKS_PER_SEC << elf;

            cout << elf;
        }
    #else
        int t = 1;
//        cin >> t;

        while (t--) {
            solve();
            cout << el;
        }
    #endif
}


Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;



int main() {
  int n;
  cin >> n;
  double sum=0;
  rep(i,n) {
        double m;
        string s;
        cin >> m >> s;
        if (s == "JPY") {
            sum += m;
        } else {
            sum += m * 380000.0;
        }
    }
  printf("%.10f\n",sum);
}

Measured memory_bytes: 256
//In the name of God:)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int INF = 1e9 + 10;
long long N , W , dp[MAXN];

int main(){
    fill(dp , dp + MAXN , INF);
    dp[0] = 0;
    scanf("%lld%lld" , &N , &W);
    for(int i = 0 ; i < N ; i++){
        int w , v;
        scanf("%d%d" , &w , &v);
        for(int j = MAXN-2 ; j >= v ; j--){
            dp[j] = min(dp[j] , dp[j - v] + w);
        }
    }
    long long ans = 0;
    for(int i = 0 ; i < MAXN ; i++){
        if(dp[i] <= W){
            ans = i;
        }
    }
    printf("%lld\n" , ans);
}


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

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;

    int count=1;
    for(int i=0;i<N-1;i++){
        if(S[i]==S[i+1]){
            continue;
        }
        count++;
    }

    cout << count << endl;
}

Measured memory_bytes: 512
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int mod = 1000000000 + 7;
	static int[][] dp;
	static ArrayList<Integer>[] edges;
	static void dfs(int node, int parent) {
		if(dp[node][0] != -1 && dp[node][1] != -1) return;
		long white = 1, black = 1;
		boolean is_leaf = true;

		for(int edge : edges[node]) {
			if(edge != parent) {
				is_leaf = false;
				if(dp[edge][0] == -1 || dp[edge][1] == -1) dfs(edge, node);
				white *= (long)(dp[edge][0] + dp[edge][1]);
	            black *= (long)dp[edge][0];
	            white %= mod;
	            black %= mod;
			}
		}

		if(is_leaf) {
			dp[node][0] = 1;
			dp[node][1] = 1;
		} else {
			dp[node][0] = (int)white;
			dp[node][1] = (int)black;
		}
	}
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		edges = new ArrayList[N];
		for(int i = 0; i < N; i++) edges[i] = new ArrayList<Integer>();
		for(int i = 0; i < N - 1; i++) {
			int x = sc.nextInt(), y = sc.nextInt();
			edges[x - 1].add(y - 1);
			edges[y - 1].add(x - 1);
		}
		dp = new int[N][2];
		for(int j = 0; j < 2; j++) for(int i = 0; i < N; i++) dp[i][j] = -1;
		dfs(0, -1);
		System.out.println((dp[0][0] + dp[0][1]) % mod);
	}
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
//const int MOD =  (int)1e9 + 7;
const int MOD = 998244353;
const double EPS = 1e-9;

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

	int N;
	cin >> N;
	vector<string> S(N);
	vector<pii> PV, ZV,NV;
	rep(i, 0, N)
	{
		cin >> S[i];
		int L = 0, R = 0;
		rep(j, 0, SZ(S[i]))
		{
			if (S[i][j] == '(')R++;
			else
			{
				if (R > 0)R--;
				else L++;
			}
		}
		if (R - L > 0)PV.push_back(mp(L, R));
		if (R - L == 0)ZV.push_back(mp(L, R));
		if (R - L < 0)NV.push_back(mp(-R, -L));
	}

	sort(all(PV));
	sort(all(NV));

	int R = 0;
	for (auto p : PV)
	{
		R -= p.first;
		if (R < 0)
		{
			cout << "No" << endl;
			return 0;
		}
		R += p.second;
	}
	for (auto p : ZV)
	{
		R -= p.first;
		if (R < 0)
		{
			cout << "No" << endl;
			return 0;
		}
		R += p.second;
	}
	for (auto p : NV)
	{
		R += p.second;
		if (R < 0)
		{
			cout << "No" << endl;
			return 0;
		}
		R -= p.first;
	}

	if (R == 0)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}


	return 0;
}

Measured memory_bytes: 50272
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		long N = sc.nextLong();
		long K = sc.nextLong();
		long A = N%K;
		long ans = 0;
		if( N%K==0 ){
			ans = 0;
		}else{
			ans = Math.min( A,K-A );
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23760
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int D,L;
  cin>>D>>L;
  cout << D / L + (D % L) << endl;
}


Measured memory_bytes: 3192
// https://atcoder.jp/contests/abc164/tasks/abc164_b

#include "algorithm"
#include "bitset"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "map"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define rep1(i, to) for (ll i = 1; i <= (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define unless(cond) if (!(cond))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;

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

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

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}

const ll INF = 1e18;

void solve();

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

void solve() {
  ll A, B, C, D;
  cin >> A >> B >> C >> D;

  ll t_ct = (C + B - 1) / B;
  ll a_ct = (A + D - 1) / D;

  if (t_ct <= a_ct) drop("Yes");
  drop("No");
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
long long MOD=1000000007;
int n,uu,vv;
vector<int> ga[200100];
vector<int> ch[200100];
long long dp1[200100],dp2[200100];
long long inv[200100],fac[200100],ifac[200100];
int zsize[200100];
long long C(int x,int y){
	return fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
long long qpow(long long a,long long b){
	long long res=1LL;
	while(b){
		if(b&1)
			res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res%MOD;
}
void dp1_solve(int u,int p){
	zsize[u]=0;
	dp1[u]=1;
	for(int v:ga[u]){
		if(v==p)
			continue;
		ch[u].push_back(v);
		dp1_solve(v,u);
		zsize[u]+=zsize[v];
		dp1[u]=dp1[u]*C(zsize[u],zsize[v])%MOD*dp1[v]%MOD;
	}
	zsize[u]++;
}
void dp2_solve(int u){
	int tmp=zsize[u];
	for(int v:ch[u]){
		dp2[v]=dp2[u]*dp1[v]%MOD*qpow(dp1[v]*C(n-1,zsize[v])%MOD,MOD-2)%MOD*C(n-1,n-zsize[v])%MOD;
		dp2_solve(v);
	}
}
int main(){
	#ifdef FILIN
		#ifndef LOCAL
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>uu>>vv;
		ga[uu].push_back(vv);
		ga[vv].push_back(uu);
	}
	inv[1]=1LL;
	for(int i=2;i<=n;i++)
		inv[i]=(MOD-((MOD/i)*inv[MOD%i])%MOD);
	fac[0]=1LL;
	ifac[0]=1LL; 
	for(int i=1;i<=n;i++){
		fac[i]=(fac[i-1]*(long long)(i))%MOD;
		ifac[i]=(ifac[i-1]*inv[i])%MOD;
	}
	dp1_solve(1,-1);
	dp2[1]=dp1[1];
	dp2_solve(1);
	for(int i=1;i<=n;i++)
		cout<<(dp2[i])<<endl;
	return 0;
}


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

const int MOD = 1000000007;

int main(){
    int n,k; cin>>n>>k;
    
    int ans = 1;
    
    rep(i,n){
        if(!i)ans *= k;
        else ans *= k-1;
    }
    
    cout << ans << endl;
    
    return 0;
}

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

int n;
long long a[N], x[N];

int main() {
#ifdef whyqx
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%lld", a + i);
    sort(a + 1, a + n + 1);

    if (a[1] >= 0) {

        long long ans = 0;
        for (int i = 2; i <= n; ++i)
            ans += a[i];
        ans -= a[1];
        cout << ans << endl;

        for (int i = 2; i < n; ++i) {
            printf("%lld %lld\n", a[1], a[i]);
            a[1] -= a[i];
        }
        printf("%lld %lld\n", a[n], a[1]);

    } else if (a[n] <= 0) {

        long long ans = 0;
        for (int i = 1; i < n; ++i) {
            ans -= a[i];
        }
        ans += a[n];
        cout << ans << endl;

        for (int i = 1; i < n; ++i) {
            printf("%lld %lld\n", a[n], a[i]);
            a[n] -= a[i];
        }

    } else {

        long long ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += a[i] < 0 ? -a[i] : a[i];
        }
        cout << ans << endl;

        int now = 1;
        while (a[now] < 0) ++now;
        for (int i = now; i < n; ++i) {
            printf("%lld %lld\n", a[1], a[i]);
            a[1] -= a[i];
        }
        for (int i = 1; i < now; ++i) {
            printf("%lld %lld\n", a[n], a[i]);
            a[n] -= a[i];
        }

    }

    return 0;
}


Measured memory_bytes: 3968
#include<stdio.h>
int main(){
	int a,b,c,d,s;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if(a*b>=c*d)
		s=a*b;
	else
		s=c*d;
	printf("%d\n",s);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)

typedef long long ll;

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

void solve(void){
    int N; ll L;
    cin >> N >> L;
    int f = -1;
    vector <ll> as(N);
    rep(N, i) {
        cin >> as[i];
    }
    rep(N-1, i) {
        if (as[i] + as[i+1] >= L) {
            f = i;
        }
    }
    if (f >= 0) {
        cout << "Possible" << endl;
        Rep(1, f, i) cout << i << endl;
        Repr(N-1, f+1, i) cout << i << endl;
    }
    else cout << "Impossible" << endl;
}

int main(void){
  solve();
  //cout << "yui(*-v・)yui" << endl;
  return 0;
}


Measured memory_bytes: 1664
S = input()
l = len(S)

ans = 0
lis = ['A', 'C', 'G', 'T']

for i in range(l):
  count = 0
  for j in range(l-i):
    if S[i+j] in lis:
      count += 1
    else:
      break
  ans = max(ans, count)
print(ans)

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

static const auto fast_io = [] {
 ios_base::sync_with_stdio(false); 
 cin.tie(nullptr); cout.tie(nullptr); 
 return nullptr;
}();

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd() {
 return uniform_int_distribution<int> (1, (int) 1e9) (rng);
}

template<class A> 
A rnd(A x, A y) {
 return uniform_int_distribution<A> (x, y) (rng);
}

string to_string(string s) {
 return '"' + s + '"';
}

string to_string(const char* ch) {
 return to_string((string)ch);
}

string to_string(char ch) {
 return (string)"'" + ch + (string)"'";
}

string to_string(bool b) {
 return (b ? "true" : "false");
}

template<class A, class B>
string to_string(pair<A, B> p) {
 return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template<class A>
string to_string(A a) {
 string res = "{";
 bool first = true;
 for(const auto& x: a) {
  if(first == false) res += ", ";
  first = false;
  res += to_string(x);
 }
 res += "}";
 return res;
}

template<class A, class B, class C>
string to_string(priority_queue<A, B, C> a) {
 vector<A> res;
 while(a.empty() == false) {
  res.push_back(a.top());
  a.pop();
 }
 reverse(res.begin(), res.end());
 return to_string(res);
}

template<class A>
string to_string(priority_queue<A> a) {
 vector<A> res;
 while(a.empty() == false) {
  res.push_back(a.top());
  a.pop();
 }
 reverse(res.begin(), res.end());
 return to_string(res);
}

template<class A>
string to_string(stack<A> a) {
 vector<A> res;
 while(a.empty() == false) {
  res.push_back(a.top());
  a.pop();
 }
 return to_string(res);
}

template<class A>
string to_string(queue<A> a) {
 vector<A> res;
 while(a.empty() == false) {
  res.push_back(a.front());
  a.pop();
 }
 return to_string(res);
}

vector<string> __vector_tuple;
template<int index, class... A>
struct print_tuple {
 auto operator() (tuple<A...> a) {
  __vector_tuple.push_back(to_string(get<index>(a)));
  print_tuple<index-1, A...>{}(a);
 }
};

template<class... A>
struct print_tuple<0, A...> {
 auto operator() (tuple<A...> a) {
  __vector_tuple.push_back(to_string(get<0>(a)));
 }
};

template<class... T>
string to_string(tuple<T...> a) {
 const int ttsz = tuple_size<decltype(a)>::value;
 print_tuple<ttsz-1, T...>{}(a);
 string __ss = to_string(__vector_tuple);
 __vector_tuple.clear();
 return __ss;
}

void debug() {cerr << "]\n";}

template<class H, class... T>
void debug(H head, T... tail) {
 cerr << to_string(head) << " ";
 debug(tail...);
}

#ifdef LOCAL
 #define debug(...) cerr << "[" << #__VA_ARGS__ << " ] = ["; debug(__VA_ARGS__);
#else 
 #define debug(...) 
#endif

typedef long long int ll;

int main()
{
 int n;
 cin >> n;
 int ans = 0;
 for(int i = 1; i <= n; i++) {
  int x;
  cin >> x;
  if(i % 2 == 1 && x % 2 == 1) ans++;
 }
 cout << ans << '\n';
 return 0;
}


Measured memory_bytes: 3656
import java.io.*;
import java.util.*;

class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastScanner s  = new FastScanner();
		
		char[] arr = s.nextString().toCharArray();
		int l = arr.length;
		char[] A = new char[l];
		char[] B = new char[l];
		int c=0,d = 0;
		for(int i = 0;i<l;i++)
		{
			A[i] = i%2==0?'0':'1';
			B[i] = i%2==0?'1':'0';
			if(A[i]!=arr[i])c++;
			if(B[i]!=arr[i])d++;
		}System.out.println(Math.min(c,d));
		
	}
static   class FastScanner {
		
	    private InputStream mIs;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner() {
			this(System.in);
		}

		public FastScanner(InputStream is) {
			mIs = is;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = mIs.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		
		}	

	}

	
}


Measured memory_bytes: 23380
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N,M,re=0;
  cin>>N>>M;
  vector<int> K(N);
  vector<int> res(M+1);
  int A[N][M];
  for(int i=0;i<N;i++){
    cin>>K.at(i);
    for(int j=0;j<K.at(i);j++){
      cin>>A[i][j];
    }
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<K.at(i);j++){
      for(int k=1;k<=M;k++){
        if(A[i][j]==k)res.at(k)++;
      }
    }
  }
  for(int g=1;g<=M;g++){
    if(res.at(g)==N)re++;
  }
  cout<<re<<endl;
}


Measured memory_bytes: 256
import sys
import collections
from math import ceil

ma = lambda : map(int,input().split())
ni = lambda : int(input())
s = input()
n = len(s)
l = [0]*(n+1)
d = 1
mod = 2019
for i in range(1,n+1):
    l[i] = (l[i-1] + int(s[-i])*d)%mod
    d = d*10%mod

co = collections.Counter(l)
ans = 0
for cnt in co.values():
    ans+=cnt*(cnt-1)//2
print(ans)


Measured memory_bytes: 16812
# https://atcoder.jp/contests/agc032/tasks/agc032_a
import sys

n = int(input())
nums = [int(i) - 1 for i in input().split()]
ans = []
for i in range(n):
    for j in range(len(nums) - 1, -1, -1):
        if nums[j] == j:
            ans.append(j + 1)
            del nums[j]
            break
    else:
        print(-1)
        sys.exit()
for a in ans[::-1]:
    print(a)


Measured memory_bytes: 63452
import math


class Solution:
    def solve(self, A: int, B: int) -> int:

        for i in range((B+1)*10):
            if int(math.floor(i * 0.08)) == A and int(math.floor(i * 0.10)) == B:
                return i

        return -1


if __name__ == '__main__':

    # standard input
    A, B = map(int, input().split())

    # solve
    solution = Solution()
    print(solution.solve(A, B))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back
#define Cout(s) cout << s << endl
string Yes(bool b) {if(b){return "Yes";} else {return "No";}}
string YES(bool b) {if(b){return "YES";} else {return "NO";}}

struct coor{
	int y, x;
	coor(int a = 0, int b = 0){
		y = a;
		x = b;
	}
};

int main(){
	int H, W;
	cin >> H >> W;

	vector<vector<char>> S(H, vector<char>(W));
	rep(i, H) rep(j, W) cin >> S[i][j];

	vector<vector<int>> dist(H, vector<int>(W, 10000));
	//vector<vector<bool>> visited(H, )

	queue<pair<coor, char>> que;
	que.push({coor(0, 0), S[0][0]});
	dist[0][0] = 0;
	const int d[2] = {1, 0};
	while(!que.empty()){
		coor now;
		char col;
		tie(now, col) = que.front();
		que.pop();
		
		for(int i = 0; i < 2; i++){
			int ny = now.y + d[i];
			int nx = now.x + d[i ^ 1];
			if(ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
			
			int step = (S[ny][nx] == col ? 0 : 1);
			if(dist[ny][nx] > dist[now.y][now.x] + step){
				dist[ny][nx] = dist[now.y][now.x] + step;
				que.push({coor(ny, nx), S[ny][nx]});
			}
		}
	}
	int p = 1 + (S[0][0] == '#');
	cout << (dist[H-1][W-1] + p) / 2 << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Array;
using static AtCoder.Tool;

namespace AtCoder
{
    class AC
    {
        const int mod = 1000000007;
        const int INF = int.MaxValue / 2;
        const long SINF = long.MaxValue / 2;

        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            var cin = new Scanner();
            int Q = int.Parse(Console.ReadLine());
            int[] l = new int[Q];
            int[] r = new int[Q];
            for(var i = 0; i < Q; i++)
            {
                var input = cin.SplitRead();
                l[i] = input[0];
                r[i] = input[1];
            }


            var p = new PrimeList((int)10e5 + 1);
            int[] ans = new int[(int)10e5 + 1];
            ans[0] = 0;
            for(var i = 1; i < ans.Length; i++)
            {
                if (i % 2 == 0) { ans[i] = ans[i - 1]; }
                else
                {
                    if (p.prime[i] && p.prime[(i + 1) / 2])
                    {
                        ans[i] = ans[i - 1] + 1;
                    }
                    else
                    {
                        ans[i] = ans[i - 1];
                    }
                }
            }

            for(var i = 0; i < Q; i++)
            {
                Console.WriteLine(ans[r[i]] - ans[l[i] - 1]);
            }

            Console.Out.Flush();
        }

    }
    public class Scanner
    {
        public int[] SplitRead()
        {
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return array;
        }
        public long[] SplitReadL()
        {
            long[] array = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return array;
        }
    }

    public static class Tool
    {
        static public void Initialize<T>(ref T[] array, T initialvalue)
        {
            for (var i = 0; i < array.Length; i++)
            {
                array[i] = initialvalue;
            }
        }
        static public long ModuloP(long value, long mod)
        {
            long r = value % mod;

            if (r * mod < 0)
            {
                r += mod;
            }
            return r;
        }
    }

    public class PrimeList
    {
        public bool[] prime;
        public List<int> primelist;

        public PrimeList(int n)
        {
            if (n < 2) { return; }
            primelist = new List<int>();
            prime = new bool[n + 1];
            for(var i = 0; i <= n; i++)
            {
                prime[i] = i != 0 && i != 1;
            }

            for (var i = 2; i <= Sqrt(n); i++)
            {
                if (!prime[i]) { continue; }
                primelist.Add(i);

                int c = i;
                while (c + i <= n)
                {
                    c += i;
                    prime[c] = false;
                }
            }
        }
    }

}






Measured memory_bytes: 23228
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a, f;
ll n, k;

bool chk(ll x){
    ll sum=0;
    vector<ll> t(n);
        for(int i=0; i<n; i++)
            t.at(i) = x/f.at(i);
        for(int i=0; i<n; i++)
            sum += max(0LL, a.at(i)-t.at(i));
    return sum <= k;
}



int main(){
    cin >> n >> k;
    a.resize(n); f.resize(n);

    for(int i=0; i<n; i++)  cin >> a.at(i);
    for(int i=0; i<n; i++)  cin >> f.at(i);
    sort(a.begin(), a.end(), greater<ll>());
    sort(f.begin(), f.end());

    ll l=-1, r=1e+15;
    while(l+1<r){
        ll mid = (l+r)/2;
        if(chk(mid)) r = mid;
        else l = mid;
    }
    
    
    cout << l+1 << endl; 
}


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

using namespace std;

int main(void){
    int N,T,A,answer=1001,H;
    double temp,propT;
    cin >> N >> T >> A;
    cin >> H;
    propT=abs(A-(T-H*0.006));
    //cout << propT << endl;
    answer=1;
    for(int i=1;i<N;i++){
        cin >> H;
        temp=abs(A-(T-H*0.006));
        if(propT>temp){
            propT=min(propT,temp);
            answer=i+1;
        }


    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
int n;
bool f[10];
int ok(int x){
	int i=1;
	while(x){
		if(f[x%10]) return i;
		x/=10;
		i++;
	}
	return 0;
}
int main(){
	int k,x;
	for (scanf("%d%d",&n,&k); k--;)
	{
		scanf("%d",&x);
		f[x]=true;
	}
	int bi;
	while(bi=ok(n)>0) n+= pow(10,bi)/10;
	printf("%d\n",n);
	return 0;
}

Measured memory_bytes: 128
#if defined(LOCAL)
#define PROBLEM_NAME "b"
const double _max_double_error = 1e-9;
#include "testutils.h"
#define L(x...) (debug(x, #x))
#define C(x...) CHECK(x)
#else
#define L(x, ...) (x)
#define C(x, ...) ;
#include <bits/stdc++.h>
#endif

using namespace std;
using vi = vector<int>; using vvi = vector<vi>;
using ii = pair<int,int>; using vii = vector<ii>;
using l = long long; using vl = vector<l>; using vvl = vector<vl>;
using ll = pair<l,l>; using vll = vector<ll>; using vvll = vector<vll>;
using lu = unsigned long long;
using vb = vector<bool>; using vvb = vector<vb>;
using vd = vector<double>; using vvd = vector<vd>;
using mll = unordered_map<l, l>;
const l INF = numeric_limits<l>::max();
const double EPS = 1e-10; static constexpr auto PI = acos(-1);
const l e0=1, e3=1000, e5=100000, e6=10*e5, e7=10*e6, e8=10*e7, e9=10*e8;
const char lf = '\n';
#define all(x) begin(x), end(x)
#define F(a,b,c) for (l a = l(b); a < l(c); a++)
#define B(a,b,c) for (l a = l(c) - 1; a >= l(b); a--)
#define MAX(a,b)({__typeof__(a)__x=(a);__typeof__(b)__y=(b);__x<__y?__y:__x;})
#define MIN(a,b)({__typeof__(a)__x=(a);__typeof__(b)__y=(b);__x<__y?__x:__y;})

void solve(istream& cin, ostream& cout) {
  l n; cin >> n;
  l a = 1, b = 1;
  F(i, 0, n) {
    l x; cin >> x;
    a *= 3;
    b *= (x % 2) ? 1 : 2;
  }
  cout << a - b << endl;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(15);
#if defined(LOCAL)
  // _generate_random_test = generate_random;
  // _solve_brute = solve_brute;
  // _player_b = player_b;
  // _custom_solution_checker = solution_checker;
  maybe_run_tests(cin, cout);
#else
  solve(cin, cout);
#endif
}


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

void solve()
{
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll ans = a*c;
	ans = max(ans,a*d);
	ans = max(ans,b*c);
	ans = max(ans,b*d);
	cout<<ans<<endl;
}

int main()
{
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
}

Measured memory_bytes: 3616
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
p = p_dash = 1

def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

n,m=map(int,input().split())
A=list(map(int,input().split()))
a=A[0]
while a%2==0:
    count+=1; a//=2
for ai in A:
    p=lcm(p,ai)
    p_dash=lcm(p_dash,ai//2)
    tmp=0
    while ai%2==0:
        tmp+=1; ai//=2
    if tmp!=count:
        # print(213243)
        print(0)
        exit()

if p_dash>m:
    print(0)
else:
    print((m-p_dash)//p+1)
# print(p,p_dash)



Measured memory_bytes: 71152
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
const int MOD = 1000000007;

int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	int a[n+1], dp[n+1];
	memset(a, 0, sizeof(a));
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	for(int i=0; i<m; i++){
		int tmp;
		scanf("%d", &tmp);
		a[tmp] = 1;
	}
	for(int i=1; i<=n; i++){
		if(a[i]) continue;
		if(i>1) dp[i] += (dp[i-1] + dp[i-2]) % MOD;
		else dp[i] += dp[i-1];
		dp[i] %= MOD;
	}
	printf("%d\n", dp[n]);
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);
        int n;
        cin>>n;
        vector <int> st(n);
        for(int i =0;i<n;i++)
                cin>>st[i];
        sort(st.begin(),st.end());
        int c=0;
        for(int i =0;i<n-2;i++)
        {
                for(int j =i+1;j<n-1;j++)
                {
                        for(int k =j+1;k<n;k++)
                        {
                                if(st[i]!=st[j] && st[j] != st[k])
                                {
                                        if(st[i]+st[j] > st[k])
                                                c++;
                                }
                        }
                }

        }
        cout<<c;

return 0;
}



Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 200000;
int N,D[MAX_N] = {};vector<int> v[MAX_N];
bool Visit[MAX_N] = {};
void dfs(int s){
  Visit[s] = 1;
  for(int i=0;i<v[s].size();i++){
    if(!Visit[v[s][i]]){
      D[v[s][i]] += D[s];
      dfs(v[s][i]);
    }
  }
}
int main(){
  int Q,i,a,b,p,x;scanf("%d%d",&N,&Q);
  for(i=0;i<N-1;i++){
    scanf("%d%d",&a,&b);a--;b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for(i=0;i<Q;i++){
    scanf("%d%d",&p,&x);p--;
    D[p] += x;
  }
  dfs(0);
  for(i=0;i<N;i++) printf("%d ",D[i]);
  printf("\n");
}

Measured memory_bytes: 25128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N) cin >> a[i];
  sort(all(a), greater<int>());
  int sum = 0;
  rep(i, N) sum += a[i] * pow(-1, i);
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
const long long INF = 1LL << 60;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N,K;
  cin >> N >> K;
  vector<double> p(N);
  rep(i,N) cin >> p[i];
  rep(i,N)
  {
    p[i] *= 0.5;
    p[i] += 0.5;
  }
  vector<double> rsum(N);
  rsum[0] = p[0];
  rep(i,N-1)
  {
    rsum[i+1] += p[i+1] + rsum[i];
  }
  double M = rsum[K-1];
  double X = M;
  rep(i,N-K)
  {
    X -= p[i];
    X += p[K+i];
    M = max(M,X);
  }
  cout << M << endl;
  return 0;
}

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

#define REP(i,num) for(ll i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=ll>
T in(){T x; cin >> x; return (x);}
template<typename T=ll,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	ll N=in();
	auto A=vecin(N);
	vector<ll> Z(60,0),O(60,0);

	REP(i,N){
		auto V=A[i];
		REP(index,60){
			if(V&1LL) O[index]++;
			else Z[index]++;
			V/=2LL;
		}
	}
	ll S=0,K=1;
	REP(i,60){
		auto X=O[i]*Z[i];
		X %= atcoder_mod;
		S += (X*K)%atcoder_mod;
		S %= atcoder_mod;
		K *= 2LL;
		K %= atcoder_mod;
	}

	out(S);
	return 0;
}


Measured memory_bytes: 2560
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner seer = new Scanner(System.in);
		char[] s = seer.next().toCharArray();
		int res = 0;
		for(char c: s){
			if(c == '+') res++;
			else res--;
		}
		System.out.println(res);
	}

}


Measured memory_bytes: 21844
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,s;
int main(){
	cin>>n;
	int k=n;
	while(k!=0){
		s+=k%10;
		k/=10;
	}
	if(n%s==0)cout<<"Yes";else cout<<"No";
	return 0;
}

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

int main(){
    long long int X;
    cin >> X;
    long long int i=0,j=0;
    i = X / 500;
    j = (X % 500) / 5;
    long long int result;
    result = 1000 * i + j * 5;
    cout << result;

}

Measured memory_bytes: 256
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)

int main()
{
	vector<int> str1(50);
	vector<int> str2(50);
	vector<int> count(50);
	int n, m;

	cin >> n >> m;

	rep(i, m) {
		cin >> str1.at(i) >> str2.at(i);
	}

	for (int k = 1; k < n + 1; k++) {
		rep(i, m) {
			if ((k == str1.at(i)) || (k == str2.at(i))) {
				count.at(k - 1)++;
			}
		}
	}

	rep(i, n) {
		cout << count.at(i) << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int		main()
{
	int		M1, D1;
	int		M2, D2;
	int		ans = 0;

	scanf("%d %d\n", &M1, &D1);
	scanf("%d %d\n", &M2, &D2);
	if (M1 != M2)
		ans = 1;
	printf("%d\n", ans);
	return (0);
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <map>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main() {
    int n; cin >> n;
    vector<int> a(n);
    vector<vector<int> > xs;
    vector<vector<int> > ys;
    vector<int> tmpv;
    int tmpx, tmpy;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        xs.push_back(tmpv);
        ys.push_back(tmpv);
        for(int j = 0; j < a[i];j++) {
            cin >> tmpx;
            cin >> tmpy;
            xs[i].push_back(tmpx);
            ys[i].push_back(tmpy);
        }
    }
    long long ans = 0;
    for(long long bit = 0; bit < pow(2,n); bit++) {
        long long i = bit;
        long long ii = bit;
        long long digits = 0;
        bool isOK = true;
        long long count = 0;

        while(ii != 0) {
            if(ii & 1 == 1)
                count++;
            ii >>= 1;
        }
        while(digits != n) {
            if(i & 1 == 1) {
                for(int j = 0; j < xs[digits].size(); j++) {
                    long long a = pow(2, xs[digits][j]-1);
                    if (((a & bit) >> (xs[digits][j]-1)) != ys[digits][j]) {
                        isOK = false;
                    }
                }
            }
            i >>= 1;
            digits++;
        }
        if(isOK) {
            if(ans < count)
                ans = count;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 512