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

using namespace std;

const int maxN = 50;
const int maxA = 50;

int N, A;
int x[maxN];
long long f[maxN + 1][maxA * maxN + 1];

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

	cin >> N >> A;
	for (int i = 0; i < N; i++)
		cin >> x[i];

	f[0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = i; j >= 0; j--) {
			for (int k = A * N; k >= x[i]; k--)
				f[j + 1][k] += f[j][k - x[i]];
		}
	}

	long long ans = 0;
	for (int i = 1; i <= N; i++)
		ans += f[i][A * i];

	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 1280
N = int(input())

dic = {}
for _ in range(N):
    s = ''.join(sorted(input()))

    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

ans = 0
for v in dic.values():
    if v >= 2:
        ans += (v*(v-1))//2
print(ans)


Measured memory_bytes: 22012
# coding:utf-8

S = input()
n = S.count('N')
s = S.count('S')
e = S.count('E')
w = S.count('W')
# print(n, s, e, w)

if (n == 0 and s != 0) or (n != 0 and s == 0):
    print('No')
elif (e == 0 and w != 0) or (e != 0 and w == 0):
    print('No')
else:
    print('Yes')


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

#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;

ll counter(int b, int s, int n, int keta){
    ll cnt = 0;
    if (b==s and b <= n) cnt++;

    int nd = n / 10; int ns = n % 10;
    for (int i=1;i<keta;i++){
        int v = (s * pow(10, i)) + b;
        if (v <= n){
            if (v+pow(10, i) <= n){
                cnt += pow(10, i-1);
            }else{
                if (b <= ns){
                    cnt += nd - (v / 10)+1;
                }else{
                    cnt += nd - (v / 10);
                }
            }
        }
    }
    return cnt;
}

int cnt_keta(int n){
    int cnt=0;
    while(n!=0){
        cnt++;
        n /= 10;
    }
    return cnt;
}

int main() {
    int n;
    cin >> n;
    
    int keta = cnt_keta(n);
    ll ans = 0;

    for (int b=1;b<10;b++){
        for (int s=1;s<10;s++){
            ans += counter(b, s, n, keta) * counter(s, b, n, keta);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int a,b,c;
	
	
	scanf("%d%d%d", &a,&b,&c);
	
	if(a < b && b < c){
		printf("Yes\n");
		
	}else{
		printf("No\n");
	}
	
	return 0;
}


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

int main(void){
    int n;
    cin >> n;
    vector<int> d(n);
    for(int i=0;i<n;i++){
        cin >> d[i];
    }
    int sum=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            sum+=d[i]*d[j];
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    dp = [0] * 100
    dp[0] = 1
    dp[1] = 1
    for i in range(2, len(dp)):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n])


if __name__ == '__main__':
    main()

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

int main(){
  int N, K;
  long int H[210000];
  cin >> N >> K ;
  for (int i = 0; i < N; i++){
   cin >> H[i];
  }
  sort(H, H + N, greater<int>());

  for (int i = 0; i < K; i++) {
    H[i] = 0;
  }
  long int res = 0;
  for (int i = K; i < N; i++) {
    res += H[i];
  }
  cout << res << endl;
 }


Measured memory_bytes: 1920
// E.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const LL MOD = 1000000007;
static const size_t MAX_N = 200050;

struct modll {
	long long x;
	modll() { }
	modll(long long _x) : x(_x) { }
	operator int() const { return (int)x; }
	modll operator+(const modll& r) { return (x + r.x) % MOD; }
	modll operator+=(const modll & r) { return x = (x + r.x) % MOD; }
	modll operator-(const modll & r) { return (x + MOD - r.x) % MOD; }
	modll operator-=(const modll & r) { return x = (x + MOD - r.x) % MOD; }
	modll operator*(const modll & r) { return (x * r.x) % MOD; }
	modll operator*(int r) { return (x * r) % MOD; }
	modll operator*=(const modll & r) { return x = (x * r.x) % MOD; }
	static modll modinv(int a) { return modpow(a, MOD - 2); }
	static modll modpow(int a, int b) {
		modll x = a, r = 1;
		for (; b; b >>= 1, x *= x) if (b & 1) r *= x;
		return r;
	}
};

int main(int argc, char *argv[]) {
	int n, m;
	cin >> n >> m;
	vector<LL> s(n), t(m);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> t[i];
	}
	vector<modll> dp(2002, 0);
	for (int i = 0; i < n; ++i) {
		modll sum = 0;
		vector<modll> next = dp;
		LL x = s[i];
		for (int j = 0; j < m; ++j) {
			if (t[j] == x) {
				next[j] += 1;
				next[j] += sum;
			}
			sum += dp[j];
		}
		dp = next;
	}
	modll ans = 1;
	for (int i = 0; i <= 2000; ++i) {
		ans += dp[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
from itertools import accumulate
import sys
def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())

    C = [0] + list(accumulate(A))
    D = [0] + list(accumulate([a if a > 0 else 0 for a in A]))
    ans = -10 ** 10
    for i in range(1, N + 1 - K + 1):
        s = D[i - 1] + D[N] - D[i + K - 1]
        t = C[i + K - 1] - C[i - 1]
        s += t if t > 0 else 0
        ans = max(ans, s)
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 76704
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

ll stair(ll N)
{
  ll res = 1;
  while (N != 0) {
    res *= N;
    N -= 1;
  }
  return res;
}

int main()
{
  ll N;
  cin >> N;
  vector<pll> xy(N);
  for (ll i = 0; i < N; ++i) {
    cin >> xy.at(i).first >> xy.at(i).second;
  }
  ll all = stair(N);
  ll below = stair(N - 1) * 2;
  double sum = 0;
  for (ll i = 0; i < N - 1; ++i) {
    for (ll j = i + 1; j < N; ++j) {
      sum += sqrt(pow(xy.at(i).first - xy.at(j).first, 2) + pow(xy.at(i).second - xy.at(j).second, 2));
    }
  }
  double ans = sum;
  ans *= below;
  ans /= all;
  cout << setprecision(20) << ans << endl;
}


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

int main(void){
    int N;
    cin >> N;
    int w[N];
    for(int i=0;i<N;i++){
        cin >> w[i];
    }
    int min=10000;
    for(int i=0;i<N-1;i++){
        int left=0,right=0;
        for(int j=0;j<=i;j++){
            left += w[j];
        }
        for(int j=i+1;j<N;j++){
            right += w[j];
        }
        if(min>=abs(left-right)){
            min = abs(left-right);
        }
    }
    cout << min << endl;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        k: i128,
        a: [i128; n as usize],
        b: [i128; m as usize],
    }

    solve(n, m, k, &a, &b);
}

fn solve(n: usize, m: usize, k: i128, a: &[i128], b: &[i128]) {
    let mut x: Vec<i128> = vec![0; n + 1];
    for i in 0..n {
        x[i + 1] = x[i] + a[i];
    }

    let mut y: Vec<i128> = vec![0; m + 1];
    for i in 0..m {
        y[i + 1] = y[i] + b[i];
    }

    let mut ans = 0;
    let mut j = m;
    for i in 0..(n + 1) {
        if x[i] > k {
            break;
        }
        while x[i] + y[j] > k {
            j -= 1;
        }
        if ans < i + j {
            ans = i + j;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 18752
n, t = gets.chomp.split(" ").map(&:to_i)

a = []
n.times do
  a << gets.chomp.split(" ").map(&:to_i)
end

a.sort_by!{|x| x[0]}

a.each do |x|
  if x[1] <= t
    puts x[0]
    exit
  end
end

puts "TLE"

Measured memory_bytes: 1788
#include<iostream>
#include<stdio.h>
#include<string>
#include<cctype>
using namespace std;

int main(){
    int i,num,alpha[26]={};
    char ch,a='a';

    while(cin >> ch){
        if(isalpha(ch)){
            if(islower(ch)){
                num = ch - 'a';
                alpha[num]++;
            }else{
                num = ch - 'A';
                alpha[num]++;
            }
        }
    }
    for(i=0;i<26;i++){
        cout << a << " : " << alpha[i] << endl;
        a += 1;
    }

    return 0;
}



Measured memory_bytes: 3084
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

//# include <ext/pb_ds/assoc_container.hpp>
//# include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;
 
//template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;
//	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//	shuffle(permutation.begin(), permutation.end(), rng);



int main () {
	scanf("%d%d", &n, &m);
	if (n > m) swap(n, m);
	if (n == 1) {
		cout << 1;
		exit(0);
	}

	cout << ((n + 1) / 2) * (ll)((m + 1) / 2) + (n / 2) * (ll)(m / 2);
	return Accepted;
}

// B...a

Measured memory_bytes: 18688
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef set<int> si;
typedef map<int, int> mii;
#define INF (1<<29)


int main() {
    int n;
    cin>>n;
    vector<int> number(4);

    for(int i=0; i<4; i++){
        number[3-i]=n%10;
        n /= 10;
    }

    vector<int> op(2);
    op[0] = 1;
    op[1] = -1;
    string a,b,c;

    for (int i = 0; i < 1; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 2; l++) {
                    if((number[0]*op[i])+(number[1]*op[j])+(number[2]*op[k])+(number[3]*op[l]) == 7){
                        if(op[j]==1)a='+'; else a='-';
                        if(op[k]==1)b='+'; else b='-';
                        if(op[l]==1)c='+'; else c='-';
                        cout<<number[0]<<a<<number[1]<<b<<number[2]<<c<<number[3]<<"=7"<<endl;
                        return 0;
                    }
                }
            }
        }
    }
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>


using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
const  int INF=1001001001;
int N;
int a[102];
vector<int> D;

int main(){
	scanf("%d",&N);
	rep(i,N)scanf("%d",&a[i]);
	sort(a,a+N);
	int ans=INF;
		for(int j=a[0];j<=a[N-1];j++){
		int sans=0;
			rep(i,N)sans+=(int)(pow((double)(a[i]-j),2.0) );
			ans=min(ans,sans);
		}
		
	
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int count = 0, ncount = 0;
    	String str = sc.nextLine();

    	for(char x: str.toCharArray()){
    		if(x == 'o'){
    			count++;
    		}else {
    			ncount++;
    		}
    	}
    	
    	int nokori = 15 - str.length();
    	
      	if(nokori+count >= 8) System.out.println("YES");
      	else System.out.println("NO");
    }
}


Measured memory_bytes: 21204
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
s = [LIST() for i in range(m)]
p = LIST()
ans = 0

for i in range(2**n):
    sw = []
    for j in range(n):
        sw.append(( i >> j ) & 1)
    for j in range(m):
        reg = 0    
        for k in range(1, s[j][0]+1):
            reg += sw[s[j][k]-1]
        if reg % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)

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

#define fi first
#define se second
#define sc scanf
#define pr printf
#define pb push_back
#define ll long long
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 300100;
const long long MX = sqrt(N);
const long long H = 17;
const long long MAGIC = 1000;
const long long mod = 1e9 + 7;

using namespace std;

ll n;
ll a[N];
ll l[N];
ll r[N];

void solve()
{
        cin >> n;
        for(int i = 1; i <= 3 * n; i++){
                cin >> a[i];
        }
        ll f = 0;
        set < pair < ll, int > > s;
        for(int i = 1; i <= 3 * n; i++){
                s.insert({a[i], i});
                f += a[i];
                if(s.size() > n){
                        f -= s.begin()->fi;
                        s.erase(s.begin());
                }
                l[i] = f;
        }
        s.clear();
        f = 0;
        for(int i = 3 * n; i >= 1; i--){
                s.insert({a[i], i});
                f += a[i];
                if(s.size() > n){
                        f -= (--s.end())->fi;
                        s.erase(--s.end());
                }
                r[i] = f;
        }
        ll ans = -1e18;
        for(int i = n; i <= n + n; i++){
                ans = max(ans, l[i] - r[i + 1]);
        }
        cout << ans << endl;
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("landscape.in");
        //fout("landscape.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}


Measured memory_bytes: 13568
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main () {
	int R, G, B;
	cin >> R >> G >> B;

	int ret = R * 100 + G * 10 + B;
	if (ret % 4 == 0) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int N,M;
  cin>>N>>M;
  int cnt[M]={};
  
  for(int i=0;i<N;i++){
    int a;
    cin>>a;
    for(int i=0;i<a;i++){
      int b;
      cin>>b;
      cnt[b-1]++;
    }
  }
  
  int ans=0;
  for(int i=0;i<M;i++){
    if(cnt[i]==N) ans++;
  }
  cout<<ans;
  
}

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

int n,maxn;
int wei[3][3]={{0,0,0},{0,1,0},{0,0,1}};
int a[3][101];
bool bol[3][101];

bool ok(int c,int d){
	if(c>0&&c<=2&&d>0&&d<=n)
		return true;
	else
		return false;
}

void dfs(int x,int y,int sum){
	if(x==2&&y==n){
		maxn=max(maxn,sum);
	}
	else{
		for(int i=1;i<=2;i++){
			int xxx,yyy;
			xxx=x+wei[i][1];
			yyy=y+wei[i][2];
			if(ok(xxx,yyy)&&bol[xxx][yyy]){
				bol[xxx][yyy]=false;
				dfs(xxx,yyy,sum+a[xxx][yyy]);
				bol[xxx][yyy]=true;
			}
		}
	}
}

int main(){
	memset(bol,true,sizeof(bol));
	cin>>n;
	for(int i=1;i<=2;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	dfs(1,1,a[1][1]);
	cout<<maxn;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 5;
typedef long long ll;
int N, A[MAX];
ll psum[MAX];

int main(){
	scanf("%d", &N);
	for(int i = 1; i <= N; i++){
		scanf("%d", A + i);
		psum[i] += psum[i - 1] + A[i];
	}
	ll ans = N, xsum = 0;
	ll l, r, len = 0;
	for(l = 1, r = 1; r <= N; r++){
		xsum ^= A[r];
		if((psum[r] - psum[l - 1]) == xsum){
			len = r - l + 1;
		}
		else{
			ans += len * (len - 1) / 2;
			while(l <= r && psum[r] - psum[l - 1] != xsum){
				xsum ^= A[l++];
			}
			len = r - l;
			if(l != r){
				ans -= len * (len - 1) / 2;
			}
			len++;
		}
	}
	ans += len * (len - 1) / 2;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2560
//============================================================================
// Name        : abc057_D.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main() {
	int n;
	string s;

	cin >> n;
	cin >> s;

	int max = 0;
	int x = 0;
	for (int var = 0; var < n; ++var) {
		x += s.at(var) == 'I' ? 1 : -1;

		if(max < x) {
			max = x;
		}
	}
	cout << max;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
	int  A[4];
	for(int i=0;i<4;i++)
		cin >> A[i];
	sort(A,A+4);
	if(A[0]==1 && A[1]==4 && A[2]==7 && A[3]==9)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <ctime>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define fs first
#define sc second
#define INF 1000000000
#define MOD 1000000007
#define EPS 0.00000001

int main() {
    int N; cin >> N;
    vector<PII> V(N);
    for(int i=0; i<N; i++){
        int a; cin >> a;
        V[i] = {a, i};
    }
    
    sort(V.begin(), V.end());
    
    for(int i=0; i<N; i++){
        cout << V[i].sc + 1 << endl;
    }
    
    return 0;
}



Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> vec(33);
  vec = {0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    for(int i = 0; i < 33; i++){
      cin >> vec.at(i);
    }
  cout << vec.at(N) << endl;
    
}

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

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const long long MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


//grobal variable
//------------------------------------------

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    long long N, M; cin>>N>>M;
    vector<long long> A(M); 
    if (M!=0) REP(i, M) cin>>A.at(i);

    vector<long long> dp(N+1, -1);
    dp.at(0) = 1;

    if (M!=0) {
        if (A.at(0)!=1) dp.at(1) = 1;
    }
    else dp.at(1) = 1;

    if (M!=0)
    {

    for (long long a : A)
    {
        dp.at(a) = 0;
    }
    }

    FOR(i, 2, N+1)
    {
        if (dp.at(i) != 0) dp.at(i) = (dp.at(i-1)+dp.at(i-2))%MOD;
    }
    
    cout << dp.at(N) << endl;
    return 0;
}




Measured memory_bytes: 1792
/**
 *    Author:   Jay Sabale
 *	       
**/

#include<bits/stdc++.h>

using namespace std;
 
// Competetive Template:
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;
typedef vector <lli> vl;
typedef vector <string> vs;
typedef vector < pair <long, long> > vll;

// Debugging :
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ba  back
#define si size()
#define be begin()
#define en end()
#define le length()
#define mp make_pair 
#define mt make_tuple
#define fi first
#define se second
#define gcd __gcd
#define maxe *max_element
#define mine *min_element
#define deb debug
 
#define forz(i,n) for(lli i=0; i<n; i++)
#define rep(i,k,n) for (lli i = k; i < n; i++)
#define deci(n)  fixed<<setprecision(n)
#define high(n) __builtin_popcount(n)
#define parity(n) __builtin_parity(n)
#define ctz(n)  __builtin_ctz(n)
#define mod 1000000007
#define mod2 998244353
#define kira ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)

// Printing Data :
#define pvec(v) forz(i,v.si) cout<<v[i]<<" "; cout<<endl;
#define parr(arr, n) forz(i,n) cout<<arr[i]<<" "; cout<<endl;
#define p1(i) cout<<i<<endl;
#define p2(i, j) cout<<i<<" "<<j<<endl;
#define p3(i, j, k) cout<<i<<" "<<j<<" "<<k<<endl;
#define p4(i, j, k, l) cout<<i<<" "<<j<<" "<<k<<" "<<l<<endl;

typedef pair <lli,lli> pll;
 
// CODE BEGINS :

int main()
{
    kira; 

    lli s, w; cin>>s>>w;

    cout << (s<=w ? "unsafe" : "safe") <<endl;

    return 0;
}




















































Measured memory_bytes: 3656
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W; cin >> H >> W;
    string A[510], R[510], B[510];
    rep(i, H) cin >> A[i];
    rep(i, H) R[i] = B[i] = A[i];
    for(int i = 1; i < H; i++) {
        for(int j = 0; j < W; j += 1 + (i != H - 1)) {
            R[i][j] = '#';
        }
    }
    for(int i = 0; i < H - 1; i++) {
        for(int j = 1 - (i == 0); j < W; j += 1 + (i != 0)) {
            B[i][j] = '#';
        }
    }
    rep(i, H) cout << R[i] << endl;
    cout << endl;
    rep(i, H) cout << B[i] << endl;
    cout << endl;
    /*
    rep(i, H) {
        rep(j, W) {
            if (R[i][j] == B[i][j] && R[i][j] == '#') cout << '#';
            else cout << '.'; 
        }
        cout << endl;
    }
    */


    return 0;
}


Measured memory_bytes: 1536
import sys
sys.setrecursionlimit(10 ** 6)

n, m = [int(i) for i in input().split()]
fibo_l = [1] + [None] * n
a = set([int(input()) for i in range(m)])

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x-1) % 1000000007 + fibo(x-2) % 1000000007
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)


Measured memory_bytes: 84068
#include<iostream>
#include<string>
using namespace std;
int main() {
	int a[5], k, n = 0, x = 0, y = 0;
	cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> k;
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++){
			if (a[j] - a[i] > k) {
				x++;
			}
		}
	}
	if (x == 0) {
		cout << "Yay!" << endl;
	}
	else {
		cout << ":(" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        string str = to_string(i);
        if(str.size() % 2 == 1){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma region Header
#ifdef DEBUG
#include "debug.hpp"
#else
#define NDEBUG
#define debug(...)
#define IFD(...)
#endif
#include <utility>
#include <cstdint>
#include <cmath>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stdexcept>
#include <iostream>
#include <iomanip>
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
#define rep(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define repd(i, n) for (int i = static_cast<int>(n) - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = static_cast<int>(a); i <= static_cast<int>(b); ++i)
#define FORD(i, a, b) for (int i = static_cast<int>(b); i >= static_cast<int>(a); --i)
template <typename T>
int SZ(T const &x)
{
    return static_cast<int>(x.size());
}
template <class T>
bool chmax(T &a, T const &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, T const &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}
#pragma endregion

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

    int t1, t2;
    cin >> t1 >> t2;
    i64 v1, v2;
    {
        i64 a1, a2;
        cin >> a1 >> a2;
        i64 b1, b2;
        cin >> b1 >> b2;
        v1 = b1 - a1;
        v2 = b2 - a2;
    }

    if (v1 < 0)
    {
        v1 = -v1;
        v2 = -v2;
    }
    i64 x1 = v1 * t1, x2 = x1 + v2 * t2;
    if (x2 == 0)
    {
        cout << "infinity" << endl;
        return 0;
    }
    if (x2 > 0)
    {
        cout << 0 << endl;
        return 0;
    }
    // x1 > 0 and x2 < 0
    auto ans = 2 * (x1 / (-x2));
    if (x1 % (-x2) != 0)
    {
        ++ans;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ll mod=1e9+7;
const ll MAXN = 1e7+10;


  
int spf[MAXN];

void solve(){
    
   
    int L,R,d,ans=0;
    cin>>L>>R>>d;
    for (int i = L; i <=R; i++) {
        if(i%d==0) ans++;
    }
    cout<<ans<<"\n";
    
    
}
  
        

int main(){
   
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    #endif */
        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int T=1;
        //cin>>T;
        while(T--){
            solve();
        }
            
            
        return 0;
}
 

Measured memory_bytes: 3608
#include <stdio.h>
#include <iostream>
using namespace std;

int main(void){
  int h,w;
  while(1){
    cin >> h >> w;
    if(h==0 && w==0) break;
    for(int y=0; y<h; y++){
      for(int x=0; x<w; x++){
        printf("#");
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
long double pi=3.14159265358979323846L;
double eps=1e-12;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(int i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll gya[1000010];
ll kai[1000010];
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}

void nckinit(ll n,ll md){
  kai[0]=1;
  kai[1]=1;
  for(int i=2;i<=n;i++){
    kai[i]=kai[i-1]*i;
    kai[i]%=md;
  }
  gya[n]=gyaku(kai[n],md);
  for(int i=n-1;i>=1;i--){
    gya[i]=gya[i+1]*(i+1);
    gya[i]%=md;
  }
  gya[0]=1;
}
ll nck(ll n,ll k,ll md){
  if(k<0)return 0;
  if(k==0||n==k)return 1;
  ll ret=kai[n];
  ret*=gya[n-k];
  ret%=md;
  ret*=gya[k];
  ret%=md;
  return ret;
}
ll npk(ll n,ll k,ll md){
  if(k<0)return 0;
  if(k==0)return 1;
  ll ret=kai[n];
  ret*=gya[n-k];
  ret%=md;
  return ret;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int a,b;cin>>a>>b;
    if(a<b){
        rep(i,0,b)cout<<a;
        cout<<endl;
    }
    else{
        rep(i,0,a)cout<<b;
        cout<<endl;
    }
}


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

#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)

ll C[101010],B[101010];

vector<int> makeBitPrimes(int n) {
    vector<int> v(n + 1, 1);v[0] = v[1] = 0;
    rep(i, 2, sqrt(n)) if (v[i]) for (int j = 0; i * (j + 2) < n; j++) v[i * (j + 2)] = 0;return v;
}

int main (){
   auto A=makeBitPrimes(101010);
   rep(i, 1, 101010) if(A[i]&&A[(i+1)/2])B[i]=1;
   rep(i, 1, 101010) C[i]=C[i-1]+B[i];
   
   ll x;
   cin>>x;
   ll a,b;  
   while(x--){
      cin>>a>>b;
      cout<< (C[b]-C[a-1]) <<"\n";
   }
  return 0;                  
} 


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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll A, B; cin >> A >> B;
  if (A == 1) A = 14;
  if (B == 1) B = 14;
  cout << (A < B ? "Bob" : A > B ? "Alice" : "Draw") << endl;

  return 0;
}



Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int a, b, ans[300], i, z;
	z = 0;
	while (cin >> a >> b) {
		z++;
		a = a + b;
		b = 0;
		while (a != 0) {
			a = a / 10;
			b++;
		}
		ans[z] = b;
	}
	for (i = 1; i <= z; i++) {
		cout << ans[i] << endl;
	}
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

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

const llong inf = 1'000'000'000'000'007ll;
const llong mod = 1e9+7;

llong N, M;
vector<llong> money;
vector<llong> key;

vector<vector<llong>> dp;

llong solve(llong now, llong opened) {
	if (opened == (1<<N) - 1) return 0;
	if (now == M) return inf-1;
	if (dp[now][opened] != inf) return dp[now][opened];

	llong ret = min(solve(now+1, opened), solve(now+1, key[now]|opened) + money[now]);

	return dp[now][opened] = ret;
}

int main() {

	cin >> N >> M;
	money.resize(M);
	key.resize(M, 0);
	for (int i = 0; i < M; ++i) {
		llong b, in;
		cin >> money[i] >> b;
		for (int j = 0; j < b; ++j) {
			cin >> in;
			key[i] += 1<<(in-1);
		}
	}

	dp.resize(M, vector<llong>(1<<N, inf));
	llong ans = solve(0, 0);
	if (ans == inf-1) ans = -1;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 32384
using System;
using System.Collections.Generic;
using System.Linq;

namespace IroIroTest
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] a = Console.ReadLine().Split(' ');
            int go=0;
            int siti=0;
            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] == "5") go++;
                if (a[i] == "7") siti++;
            }
            if (go == 2 && siti == 1) Console.WriteLine("YES");
            else Console.WriteLine("NO");
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int MAX = 101010;
LL P[MAX], Q[MAX], PCUM[MAX], QCUM[MAX];

int main(){
    
    // 1. 入力情報.
    int W, H;
    scanf("%d %d", &W, &H);
    rep(i, W) scanf("%lld", &P[i]);
    rep(i, H) scanf("%lld", &Q[i]);
    
    // 2. sort.
    sort(P, P + W);
    sort(Q, Q + H);
    
    // 3. 累積和.
    rep(i, W) PCUM[i + 1] = PCUM[i] + P[i];
    rep(i, H) QCUM[i + 1] = QCUM[i] + Q[i];
    
    // 4. 横方向に見ていき, コストの総和(最小値)を計算.
    // ※縦方向でも同じ結果となるはず.
    LL ans = QCUM[H]; // 0列目を保存.
    // 1列目以降(i列目)は, Q[0], Q[1], ... , Q[H - 1] と (H + 1)個 の P[i - 1] を 併せた集まりから,
    // 小さい方から順に, (H + 1)個 取ってきたものを, 道路として舗装すると見る.
    rep(i, W){
        int at = lower_bound(Q, Q + H, P[i]) - Q;
        LL cost = QCUM[at] + (H + 1 - at) * P[i];
        ans += cost;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
#define all(i) i.begin(),i.end()
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  ll N;
  cin>>N;
  vl a(N);
  ll ma=0;
  rep(i,N){
    cin>>a[i];
    ma=max(a[i],ma);
  }
  sort(all(a));
  ll ans=0;
  vector<bool> judge(1000010,false);
  for(int i=0;i<N-1;i++){
    if(judge[a[i]]) continue;
    
    if(a[i]!=a[i+1]){
      ans++;
    }
    for(int j=a[i];j<=ma;j+=a[i]){
        judge[j]=true;
    }
  }
  if(!judge[a[N-1]]) ans++;
  cout<<ans<<endl;
}


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

#define X first
#define Y second
#define LL long long
#define ULL unsigned long long
#define PB push_back
#define MP make_pair
#define VI vector<int>
#define PII pair<int,int>
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define IN freopen("in", "r", stdin);
#define OUT freopen("out", "w", stdout);

const int maxn=200010;

int fa1[maxn],fa2[maxn];
int ans[maxn];
VI v[maxn];

int find1(int x)
{
	if (fa1[x]!=x) fa1[x]=find1(fa1[x]);
	return fa1[x];
}

int find2(int x)
{
	if (fa2[x]!=x) fa2[x]=find2(fa2[x]);
	return fa2[x];
}

bool cmp(int a,int b)
{
	return find1(a)<find1(b);
}

int main()
{
	IOS;
	int n,m1,m2;
	cin>>n>>m1>>m2;
	for (int j=1;j<=n;++j)
	{
		fa1[j]=j;
		fa2[j]=j;
	}
	for (int j=1;j<=m1;++j)
	{
		int x,y;
		cin>>x>>y;
		int fx=find1(x);
		int fy=find1(y);
		if (fx!=fy) fa1[fx]=fy;
	}
	for (int j=1;j<=m2;++j)
	{
		int x,y;
		cin>>x>>y;
		int fx=find2(x);
		int fy=find2(y);
		if (fx!=fy) fa2[fx]=fy;
	}
	for (int j=1;j<=n;++j)
	{
		int fj=find2(j);
		v[fj].PB(j);
	}
	for (int j=1;j<=n;++j)
	{
		if (find2(j)!=j) continue;
		sort(v[j].begin(),v[j].end(),cmp);
		for (int k=0;k<v[j].size();++k)
		{
			int p=k;
			while (p<v[j].size()-1&&find1(v[j][p+1])==find1(v[j][k])) ++p;
			int add=p-k+1;
			for (int l=k;l<=p;++l)
				ans[v[j][l]]+=add;
			k=p;
		}
	}
	for (int j=1;j<=n;++j)
		cout<<ans[j]<<" ";
	cout<<endl;
	return 0;
}


Measured memory_bytes: 13312
import sys
sys.setrecursionlimit(10 ** 7)
mod = p = 10**9+7
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

n, a, b = map(int, input().split())
nCa= 1
nCb= 1
for i in range(b):
    nCb = (nCb%p * (n-i)%p)%p
    nCb = nCb * mod_inv(i+1, p)
    if i+1 == a:
        nCa = nCb

ans = 2**n - 1- nCa%p - nCb%p
if ans < 0:
    print(0)
else:
    print(int(ans%p))


Measured memory_bytes: 284960
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define ll long long

int arr[10001];

int main(void)
{
	int x, y, z, k, n, temp;
	scanf("%d", &n);
	k = sqrt(n);
	for(x = 1; x <= k; x++)
		for(y = 1; y <= k; y++)
			for (z = 1; z <= k; z++)
			{
				temp = x * x + y * y + z * z + x * y + y * z + z * x;
				if (temp <= n)
					arr[temp]++;
			}
	for (int i = 1; i <= n; i++)
		printf("%d\n", arr[i]);
	return 0;
}

Measured memory_bytes: 2180
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;

#define assert_range(x,a,b) assert((a) <= (x) and (x) <= (b))
using ll = long long;
const int INF = 1e9;

const int MOD = 1e9+7;

using t_graph = vector<vector<int>>;

struct Colorings {
    ll white;
    ll black;
};

Colorings dfs(int v, int p, const t_graph& g) {
    Colorings res = {1, 1};
    for (auto u : g[v]) {
        if (u == p) continue;
        auto subres = dfs(u, v, g);
        res.white = (res.white * (subres.white + subres.black)) % MOD;
        res.black = (res.black * subres.white) % MOD;
    }
    return res;
}

ll count_independent_sets(const t_graph& g) {
    const int ROOT = 0;
    auto res = dfs(ROOT, -1, g);
    return (res.white + res.black) % MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    t_graph g(n);
    for (int i = 0; i < n-1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    auto res = count_independent_sets(g);
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 12672
#include <bits/stdc++.h>
 
#define forn(i, n) for (llong i = 0ll; i < (llong) n; ++i)
#define fornn(i, l, r) for (llong i = (llong) l; i < (llong) r; ++i)
#define size(x) ((int) (x.size()))
 
using namespace std;
 
typedef long long llong;
const llong inf = (llong) 1e+9 + 7ll;
const llong linf = (llong) 1e+18 + 7ll;
const long double eps = (long double) 1e-9;
const long double pi = acosl((long double) -1.0);
const int alph = 26;
 
mt19937 mrand(random_device{} ()); 
 
template<typename T, typename U> inline llong umin(const T& a, const U& b) { return a < b ? a : b; }
template<typename T, typename U> inline llong umax(const T& a, const U& b) { return a > b ? a : b; }
 
static char buff[(int) 2e6 + 17]; // reads std::string
const int maxn = (int) 3e6 + 17;
 
struct pt
{
	int x, y;
	pt() { }
};
 
struct fenwick
{
	int n;
	unordered_map<int, int> F;
 
	fenwick()
	{
		n = inf;
		F.rehash(200000 * 17);
		//F.max_load_factor();
	}
 
	void upd(int i, int x)
	{
		for (; i < n; i |= i + 1)
			F[i] = max(F[i], x);
	}
 
	int get(int i)
	{
		int res = 0;
 
		for (; i >= 0; i &= i + 1, --i)
			res = max(res, F[i]);
 
		return res;
	}
};
 
int n;
pt s, f;
pt p[maxn];
 
bool read()
{
	if (scanf("%d %d %d %d %d", &s.x, &s.y, &f.x, &f.y, &n) != 5)
		return false;
 
	forn (i, n)
		scanf("%d %d", &p[i].x, &p[i].y);
 
	return true;
}
 
bool cmp(pt a, pt b) { return make_pair(a.x, a.y) < make_pair(b.x, b.y); }
 
void solve()
{
	if (s.x > f.x)
		swap(s, f);
 
	if (s.y > f.y)
	{
		f.y = 2 * s.y - f.y;
 
		forn (i, n)
			p[i].y = 2 * s.y - p[i].y;
	}
 
	vector<pt> pp;
 
	forn (i, n)
		if (s.x <= p[i].x && p[i].x <= f.x && s.y <= p[i].y && p[i].y <= f.y)
			pp.push_back(p[i]);
 
	sort(pp.begin(), pp.end(), cmp);
	fenwick dp;
 
	forn (i, size(pp))
		dp.upd(pp[i].y, dp.get(pp[i].y) + 1);
 
	int lis = dp.get(inf);
	long double ans = 0;
 
	if (lis != min(f.y - s.y, f.x - s.x) + 1)
		ans = 100.0 * (f.y - s.y + f.x - s.x) - 20.0 * lis + 5 * M_PI * lis;
	else
		ans = 100.0 * (f.y - s.y + f.x - s.x) - 20.0 * lis + 5 * M_PI * (lis - 1) + 10 * M_PI;
 
	printf("%.15f\n", (double) ans);
}
 
int main()
{
#if SEREZHKA
	freopen("file.in", "r", stdin);
#endif
 
	while (read())
		solve();
 
	return 0;
}

Measured memory_bytes: 81008
n, m = [int(_) for _ in input().split()]
spam = [[int(_) for _ in input().split()] for _ in range(m)]

spam.sort(key=lambda x: x[1])
pre = -1
cnt = 0
for a, b in spam:
    if pre < a:
        cnt += 1
        pre = b - 1
print(cnt)


Measured memory_bytes: 22812
import java.util.Scanner;

public class Main
{
   public static void main(String[] args)
   {
     Scanner in=new Scanner(System.in);
     int m,n;
     m=in.nextInt();
     n=in.nextInt();
    
     System.out.println((m*n)+" "+(m+n)*2);
      
   }

}

Measured memory_bytes: 26224
#include <iostream>
#include <algorithm>

using namespace std;

template <typename T>
T gcd(T a, T b) {
    if (a > b) {
        T buf = a;
        a = b;
        b = buf;
    }
    return a == 0 ? b : gcd(a, b%a);
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        long a, b, c, d;
        cin >> a >> b >> c >> d;
        long ra = a % b;
        if (ra == a || ra > c) {
            cout << "No" << '\n';
            continue;
        }
        else if (b < c && b <= d) {
            cout << "Yes" << '\n';
            continue;
        }
        long g   = gcd(b, d),
             q1  = (c - ra) / g + 1,
             rra = ra % g;
        cout << (ra + g*q1 < b || rra + d < c ? "No" : "Yes") << '\n';
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		java.util.Scanner sin = new java.util.Scanner(System.in);
		int x = sin.nextInt();
		int ans;
		if(1 <= x && x <= 100){
			ans = x * x * x;
			System.out.println(ans);
		}
	}
}


Measured memory_bytes: 26220
a=[int(i) for i in input()]
for i in range(2**3):
    op=['-','-','-']
    for j in range(len(op)):
        if (i>>j)&1:
            op[j]='+'
    sum=a[0]
    for k in range(3):
        if op[k]=='+':
            sum+=a[k+1]
        else:
            sum-=a[k+1]
    if sum==7:
        print(str(a[0])+op[0]+str(a[1])+op[1]+str(a[2])+op[2]+str(a[3])+'=7')
        exit()

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

int const INF = 1000000;

int main() {
  int X, Y, A, B, C;
  cin >> X >> Y >> A >> B >> C;

  vector<int> p(A), q(B), r(C);
  rep(i, A) cin >> p[i];
  rep(i, B) cin >> q[i];
  rep(i, C) cin >> r[i];
  sort(p.begin(), p.end());
  reverse(p.begin(), p.end());
  sort(q.begin(), q.end());
  reverse(q.begin(), q.end());
  sort(r.begin(), r.end());
  reverse(r.begin(), r.end());
  
  vector<int> s(X + Y + C);
  rep(i, X) s[i] = p[i];
  rep(i, Y) s[i + X] = q[i];
  rep(i, C) s[i + X + Y] = r[i];
  sort(s.begin(), s.end());
  reverse(s.begin(), s.end());
  
  ll ans = 0;
  rep(i, X + Y) ans += s[i];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
import java.util.Scanner;

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

        int A = scanner.nextInt();
        int B = scanner.nextInt();

        if (A > B && B != 1) {
            System.out.println("Alice");
        } else if (A > B && B == 1) {
            System.out.println("Bob");
        } else if (B > A && A != 1) {
            System.out.println("Bob");
        } else if (B > A && A == 1) {
            System.out.println("Alice");
        } else {
            System.out.println("Draw");
        }

    }
}


Measured memory_bytes: 25044
N, K = map(int,input().split())

arr = [list(map(int,input().split())) for i in range(N)]

test = {}

for i in arr:
    if i[0] in test:
        test[i[0]] += i[1]
    else:
        test[i[0]] = i[1]

test = sorted(test.items())

tmp = 0
ans = 0
for i in test:
    if tmp >= K:
        break
    else:
        tmp += i[1]
        ans = i[0]
print(ans)

Measured memory_bytes: 67544
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int num1 = num/1000;
		int num2 = num%1000/100;
		int num3 = num%100/10;
		int num4 = num%10;
		String[] str =new String[]{"+","-"};
		
		int temp1 = num1 + num2;
		int temp2 = num1-num2;
		
		int temp3 = temp1 + num3;
		int temp4 = temp1 - num3;
		int temp5 = temp2 + num3;
		int temp6 = temp2 - num3;
		
		int temp7 = temp3 + num4;
		int temp8 = temp3 - num4;
		int temp9 = temp4 + num4;
		int temp10 = temp4 - num4;
		int temp11 = temp5 + num4;
		int temp12 = temp5 - num4;
		int temp13 = temp6 + num4;
		int temp14 = temp6 - num4;
		
		if(temp7 == 7){
			System.out.println(num1 +"+"+ num2+"+"+num3 +"+"+ num4+"=7");
		}else if(temp8 == 7){
			System.out.println(num1 +"+"+ num2+"+"+num3 +"-"+ num4+"=7");
		}else if(temp9 == 7){
			System.out.println(num1 +"+"+ num2+"-"+num3 +"+"+ num4+"=7");
		}else if(temp10 == 7){
			System.out.println(num1 +"+"+ num2+"-"+num3 +"-"+ num4+"=7");
		}else if(temp11 == 7){
			System.out.println(num1 +"-"+ num2+"+"+num3 +"+"+ num4+"=7");
		}else if(temp12 == 7){
			System.out.println(num1 +"-"+ num2+"+"+num3 +"-"+ num4+"=7");
		}else if(temp13 == 7){
			System.out.println(num1 +"-"+ num2+"-"+num3 +"+"+ num4+"=7");
		}else if(temp14 == 7){
			System.out.println(num1 +"-"+ num2+"-"+num3 +"-"+ num4+"=7");
		}
		
		
	}

}

Measured memory_bytes: 23636
def main(X, A):
    ans = 1
    if 0 in A:
        return 0
    for a in A:
        ans *= a
        if ans > 1e18:
            return -1
    return ans

if __name__ == '__main__':
    X = int(input())
    A = list(map(int, input().split()))
    ans = main(X, A)
    print(ans)



Measured memory_bytes: 21428