akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

import sys
import os
import math
import re
import random

tableA = {
    "A": "00000",
    "B": "00001",
    "C": "00010",
    "D": "00011",
    "E": "00100",
    "F": "00101",
    "G": "00110",
    "H": "00111",
    "I": "01000",
    "J": "01001",
    "K": "01010",
    "L": "01011",
    "M": "01100",
    "N": "01101",
    "O": "01110",
    "P": "01111",
    "Q": "10000",
    "R": "10001",
    "S": "10010",
    "T": "10011",
    "U": "10100",
    "V": "10101",
    "W": "10110",
    "X": "10111",
    "Y": "11000",
    "Z": "11001",
    " ": "11010",
    ".": "11011",
    ",": "11100",
    "-": "11101",
    "'": "11110",
    "?": "11111"}

tableB = {
    "101": " ",
    "000000": "'",
    "000011": ",",
    "10010001": "-",
    "010001": ".",
    "000001": "?",
    "100101": "A",
    "10011010": "B",
    "0101": "C",
    "0001": "D",
    "110": "E",
    "01001": "F",
    "10011011": "G",
    "010000": "H",
    "0111": "I",
    "10011000": "J",
    "0110": "K",
    "00100": "L",
    "10011001": "M",
    "10011110": "N",
    "00101": "O",
    "111": "P",
    "10011111": "Q",
    "1000": "R",
    "00110": "S",
    "00111": "T",
    "10011100": "U",
    "10011101": "V",
    "000010": "W",
    "10010010": "X",
    "10010011": "Y",
    "10010000": "Z"}

def my_solve(s):
    # encode
    # lst = []
    # for c in s:
    #     lst.append(tableA[c])
    # s = ''.join(lst)

    en = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' + ' .,-\'?'
    a = b = c = ''
    for x in s: a += str(bin(en.index(x)))[2:].zfill(5)
    s = a

    de = {
        '101': ' ', '000000': '\'', '000011': ',', '10010001': '-', '010001': '.', '000001': '?',
        '100101': 'A', '10011010': 'B', '0101': 'C', '0001': 'D', '110': 'E', '01001': 'F',
        '10011011': 'G', '010000': 'H', '0111': 'I', '10011000': 'J', '0110': 'K', '00100': 'L',
        '10011001': 'M', '10011110': 'N', '00101': 'O', '111': 'P', '10011111': 'Q', '1000': 'R',
        '00110': 'S', '00111': 'T', '10011100': 'U', '10011101': 'V', '000010': 'W', '10010010': 'X',
        '10010011': 'Y', '10010000': 'Z'
    }
    for x in a:
        b += x
        if b in de: c += de[b];b = ''
    return c

    # tmp, ans = '', ''
    # for c in s:
    #     tmp += c
    #     if tmp in tableB:
    #         ans += tableB[tmp]
    #         tmp = ''
    # return ans

while True:
    try:
        s = input()
    except:
        break

    print(my_solve(s))

Measured memory_bytes: 11728
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};


int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int k;
    string s;
    cin>>k>>s;
    int n=s.size();
    if(n<=k) cout<<s<<endl;
    else{
        rep(i,k) cout<<s[i];
        cout<<"..."<<endl;
    }
}/*
./problem.exe
*/

Measured memory_bytes: 3600
#!/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

n = int(input())
A = list(map(int,input().split()))
dp = [[0]*(n+1) for i in range(n)]
for length in range(2,n+1):
  for i in range(n+1-length):
    j = i+length
    S = sum(A[i:j])
    tmp = inf
    for k in range(i+1,j):
      tmp = min(tmp,dp[i][k] + dp[k][j])
    dp[i][j] = tmp + S
print(dp[0][n])
# print(dp)

Measured memory_bytes: 44636
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>

ll n,cnt,ans,a[ohara],b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

//------ 自分を天才だと信じる ------

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

    cin>>n;
    rep(i,n)cin>>a[i];
    sort(a,a+n);
    reverse(a,a+n);
    ans=a[0]/2;
    rrep(i,1,n)ans+=a[i];
    Cout(ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1LL << 60;


const int MAX_N = 100010;
int dp[110][100010];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, W; cin >> n >> W;
	VE w(n), v(n); rep(i, n)cin >> w[i] >> v[i];
	rep(i, n) {
		rep(j, W + 1) {
			if (j < w[i]) {
				dp[i + 1][j] = dp[i][j];
			}
			else {
				dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
			}
		}
	}
	cout << dp[n][W] << endl;
	return 0;
}


Measured memory_bytes: 79360
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    string a,b,c;
    
    cin>>a>>b>>c;
    transform(a.begin(), a.end(), a.begin(), ::toupper);
    transform(b.begin(), b.end(), b.begin(), ::toupper);
    transform(c.begin(), c.end(), c.begin(), ::toupper);

    
    cout<<a[0]<<b[0]<<c[0]<<endl;
    return 0;
}


Measured memory_bytes: 256
T=int(input())
for t in range(T):
    N=int(input())
    A=list(map(int,input().split()))[::-1]
    S=input()
    S=[1 if c=='1' else 0 for c in S][::-1]
    l=[]
    r=0
    for i,a in enumerate(A):
        if S[i]:
            for e in sorted(l)[::-1]:
                b=pow(2,e.bit_length()-1)
                if a&b:
                    a^=e
            if a:
                r=1
        else:
            for e in l:
                if a>e^a:
                    a^=e
            if a:
                l.append(a)
    print(r)

Measured memory_bytes: 8948
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h,w;cin >> h >> w;
	vector<string> s(h);
	rep(i,h) cin >> s.at(i);
	rep(i,h){
		rep(j,w){
			if(s[i][j]=='#'){
				int cnt=0;
				if(i>0 && s[i-1][j]=='#') cnt++;
				if(i<h-1 && s[i+1][j]=='#') cnt++;
				if(j>0 && s[i][j-1]=='#') cnt++;
				if(j<w-1 && s[i][j+1]=='#') cnt++;
				if(cnt==0){
					cout << "No" << endl;
					return 0;
				}
			}
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
N = int(input())
A = []
c = 0

for i in range(2,int(N**0.5)+1):
    if N % i == 0:
        A.append(i)
        A.append(N//i)

for i in range(2,int((N-1)**0.5)+1):
    if (N - 1) % i == 0:
        A.append(i)
        A.append((N-1)//i)
        
A = list(set(A))
if N == 2:
    print(1)
else:
    for i in A:
        start = N
        while(True):
            if start % i != 0:
                break
            start = start//i
        if start % i == 1:
            c += 1
    print(c+2)

Measured memory_bytes: 41052
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#define ll long long 
#define MOD 10000007

int main(void){
int r,g,b;
scanf("%d%d%d",&r,&g,&b);
if((10*g+b)%4==0)
printf("YES\n");
else printf("NO\n");
return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
main(){
	int a=0,x=0,y=0,d=0,j,i[3000][2]={};
	
	while(1){
		scanf("%d %d",&x,&y);
		if(x==0 && y==0) break;
		if(x>y){a=x;x=y;y=a;}
		i[d][0]=x;i[d][1]=y;d++;
	}
	for(j=0;j<=d-1;j++){
		printf("%d %d\n",i[j][0],i[j][1]);
	}
}


Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

int main(void){
    ll n, h;
    cin >> n >> h;

    pair<ll, ll> d[n * 2];

    rep(i, 0, n * 2){
        cin >> d[i].first;
        if(i % 2 == 0){
            d[i].second = 0;
        }else{
            d[i].second = 1;
        }
    }

    sort(d, d + 2 * n, greater<pair<ll, ll>>());

    ll ans = 0;
    rep(i, 0, n * 2){
        if(d[i].second == 1){
            h -= d[i].first;
            ans++;
        }else{
            ans += ceil(h / double(d[i].first));
            break;
        }

        if(h <= 0){
            break;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <cmath>
using namespace std; 
inline void prime_fac(int n){
	int m=(int)floor(sqrt(n)+0.5);
	for (int i=2;i<=m;++i){
		if (n%i==0){
			while (n%i==0) cout <<" "<< i,n/=i ;
		}
	}
	if (n>1) cout << " " << n ;
}
int main(){
	int x;
	cin >> x;
	cout << x << ":";
	prime_fac(x);
	cout << endl;
	return 0;
}

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

int main() {
  int a,b,c,d,e,k;
  cin >> a>>b>>c>>d>>e>>k;

  if (b-a<=k && c-a<=k && d-a<=k && e-a<=k && c-b<=k && d-b<=k && e-b<=k && d-c<=k && e-c<=k && e-d<=k) {
  cout << "Yay!" << endl;
  }
  else{
  cout << ":(" << endl;
  }
}


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

int n;
int a[100000 + 1];

int binarysearch(int key){
  int left = 0;
  int right = n;
  int mid;

  while (left < right){
    mid = (left + right) / 2;
    if (a[mid] == key) return 1;
    if(a[mid] < key) left = mid + 1;
    else if(a[mid] > key) right = mid;
  }
  return 0;
}


int main(){
  int i,key , q, sum = 0; 
  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%d", &a[i]);
  }
  scanf("%d", &q);
  for(i = 0; i < q; i++){
    scanf("%d", &key);
    if(binarysearch(key)) sum ++;
  }
  printf("%d\n", sum);

  return 0;
}



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


#define ll long long
#define ld long double
#define sz(x) (x).begin(), (x).end()
#define all(x) (x).begin(), (x).end()
#define pb push_back

using namespace std;



const int MAXN = 200000;
int cnt[MAXN];
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
#ifdef NICK
    //freopen("input.txt", "r", stdin);
#endif
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        t++;
        cnt[t + 1]++;
        cnt[t - 1]++;
        cnt[t]++;
    }
    int ans = 0;
    for (int i = 0; i < MAXN; i++) {
        ans = max(ans, cnt[i]);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <bitset>
#include <array>

using namespace std;

#define fi first	
#define se second
#define long long long
typedef pair<int,int> ii;

int cnt1[100003], cnt2[100003];
int mx1, mx2;
int A[100003];

int main()
{
	// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// freopen("input.in", "r", stdin);

	int n; scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &A[i]);

	for(int i = 1; i <= n; i+=2) cnt1[A[i]]++;
	for(int i = 2; i <= n; i+=2) cnt2[A[i]]++;
	int res = 1e9;
	int mx1 = -1, mx2 = -1;
	int idx1, idx2;
	for(int i = 1; i <= 100000; i++)
	{
		if(cnt2[i] > mx1)
		{
			mx2 = mx1;
			idx2 = idx1;
			mx1 = cnt2[i];
			idx1 = i;
		}
		else if(cnt2[i] > mx2)
		{
			idx2 = i;
			mx2 = cnt2[i];
		}
	}
	for(int i = 1; i <= 100000; i++)
	{
		if(i == idx1) res = min(n - cnt1[i] - mx2, res);
		else res = min(n - cnt1[i] - mx1, res);
	}
	printf("%d\n", res);

}





Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,s,f) for(i=s;i<f;i++)
#define print(v) for(auto &z:v) cout<<z<<' ';cout<<'\n'
#define db cout<<"db: "
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define all(v) v.B,v.E
#define sz(v) (int)((v).size())
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define clk1 clock_t start_time=clock()
#define clk2 cout<<(clock()-start_time)/(double)CLOCKS_PER_SEC
#define clean(arr) memset(arr,0,sizeof(arr))
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;

    int x,y;
    cin>>x>>n;
    int arr[n];
    bool is[200]={0};
    rep(i,0,n)
    {
        cin>>j;
        is[j]=1;
    }
    vi v;
    rep(i,0,102) if(!is[i]) v.pb(i);

    
    j=lower_bound(all(v),x)-v.B;

    if(v[j]-x<x-v[j-1])
    {
        cout<<v[j];
    }
    else cout<<v[j-1];
    return 0;
}




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

int main(void) {
  int K, S;
  cin >> K >> S;
  
  int cnt = 0;
  for (int X = 0; X <= K; ++X) {
    for (int Y = 0; Y <= K; ++Y) {
      if (((X + Y) <= S) && ((X+Y) >= (S-K))) ++cnt;
    }
  }
  cout << cnt << endl;
  
 return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char a, b;
    cin >> a >> b;
    if(a=='H')
        cout << b << endl;
    else
    {
        if(b=='H')
            cout << "D" << endl;
        else
            cout << "H" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
N = input()

n1 = int(N[0])
n2 = int(N[1])
n3 = int(N[2])

if n1 >= n2 and n1 >= n3:
    n1String = str(n1)
    print(n1String * 3)
else:
    n1StringPlus = str(n1+1)
    print(n1StringPlus * 3)


Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;

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


int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    string str;
    cin >> str;
    sort(str.begin(), str.end());
    if (str.at(0) == str.at(1) && str.at(2) == str.at(3) && str.at(1) != str.at(2)) {
        cout << "Yes" << endl;

        return 0;
    }
    cout << "No" << endl;

    return 0;
}


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

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	int n, m;
	cin >> n >> m;
	priority_queue<long long> pq;
	for (int i = 0; i < n; ++i){
		int x;
		cin >> x;
		pq.push(x);
	}
	for (int i = 0; i < m; ++i){
		long long nn = pq.top();
		pq.pop();
		nn /= 2;
		pq.push(nn);
	}
	long long ans = 0;
	while (pq.size()){
		long long nn = pq.top();
		pq.pop();
		ans += nn;
	}
	cout << ans;
	return 0;
}



Measured memory_bytes: 1400
# seishin.py
from math import sqrt
n, s = map(int, open(0).read().split())

# s = n
if s == n:
    print(n+1)
    exit(0)

def f(b, n):
    res = 0
    while n:
        res += n % b
        n //= b
    return res

# 2 <= b <= sqrt(n)
for b in range(2, int(sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        exit(0)

# sqrt(n) <= b <= n
for p in range(int(sqrt(n)), 0, -1):
    if (n - s) % p > 0:
        continue
    b = (n - s) // p + 1
    if b*b <= n:
        continue
    if f(b, n) == s:
        print(b)
        exit(0)
print(-1)


Measured memory_bytes: 3064
#include <stdio.h>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <limits.h>
#include <time.h>
#include <iostream>
#include <string.h>
#include <unordered_set>
using namespace std;
using ll = long long;
const int N = 2e5+5;

int main(){
	ll n;
	scanf("%lld", &n);
	ll ans = n / 11 * 2;
	if(n % 11 > 6) ans += 2;
	else if(n % 11 > 0) ans++;
	printf("%lld\n", ans); 
	return 0;
}


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

typedef long long ll;
const int mod = 998244353;

ll mod_pow(ll x, int n){
    if(n == 0)      return 1;

    ll res = 1;
    while(n > 0){
        if(n & 1)   res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

int dist[1000005];   // 距離iのものが何個あるか

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> d(n);
    int len = 0;
    for(int i = 0; i < n; ++i){
        cin >> d[i];
        len = max(len, d[i]);
        ++dist[d[i]];
    }
    if(d[0] != 0){
        cout << 0 << endl;
        return 0;
    }
    
    ll res = mod_pow((ll)dist[0], dist[1]);
    if(res != 1){
        cout << 0 << endl;
        return 0;
    }
    for(int i = 1; i <= len; ++i){
        res = res * mod_pow((ll)dist[i], dist[i + 1]) % mod;
    }
    cout << res << endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  
  for (int i = 0; i < N; i++) {
   cin >> vec.at(i);
  }
  
  int a = 0;
  int b = 0;
  int x = 0;
  
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (x < vec.at(j))
      x = vec.at(j);
    }
    for (int j = 0; j < N; j++) {
      if (vec.at(j) == x) {
      vec.at(j) = 0;
      break;
      }
    }
    
    if (i % 2 == 0)
      a += x;
    else
      b += x;
    x = 0;
  }
  
  cout << a-b << endl;
}  
 
        

    
    

Measured memory_bytes: 256
def f(k,n):

    r=1
    t = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if t%i==0:
            c=0
            while t%i==0:
                c+=1
                t //= i
            if c>=k:
                r*=i**(c//k)
    if k==1 and t!=1:r*=t
    if r==k==1:r*=n
    print(r)

f(*map(int,input().split()))


Measured memory_bytes: 38512
while True:
  h, w = map(int, input().split())

  if h == 0 and w == 0:
    break
  
  for i in range(h):
    if i % 2 != 0:
      flag = -1
    else:
      flag = 1
    for j in range(w):
      if flag == 1:
        print("#", end="")
      else:
        print(".", end="")
      flag *= -1
    print("")
  
  print("")


Measured memory_bytes: 7008
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30);
const ll INFL = (1LL<<62);
const int MOD = 1000000007;
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> ll mod_pow(ll a, ll n, T mod) { mod=(ll)mod; ll res=1, p=a%mod; while(n){ if(n&1) res=res*p%mod; p=p*p%mod; n>>=1; } return res; }

int main() {
    int ball, box;
    cin >> ball >> box;
    if(ball > box){
        cout << 0 << endl;
        return 0;
    }
    ll ans = 1;
    int prev = box;
    while(ball--){
        ans *= prev--;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3104
n,m,R=map(int,input().split())
r=list(map(int,input().split()))

d=[[float("INF")]*n for i in range(n)]
for i in range(n):
  d[i][i]=0

for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c
  
#ワーシャルフロイド法
#d[i][j]:iからjへの最短経路
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])

      
from itertools import permutations
per=list(permutations(r,R))

ans=float("INF")
for l in per:
  cnt=0
  for j in range(R-1):
    cnt+=d[l[j]-1][l[j+1]-1]
  ans=min(cnt,ans)
print(ans)

      
      
  


Measured memory_bytes: 80932
#include <bits/stdc++.h>
#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

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

const int mod = 1e9+7;

template< int mod >
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};


// (a^n)%modを求めるライブラリ
long long modpow(long long a, long long n) {
    long long res = 1;
    static const int mod = 1e9+7;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

void solve2() {
    ll N; cin >> N;
    ll p = modpow(9,N) * 2;
    ll q = modpow(8,N);
    ll t = p-q;
    if (t < 0) t+= INF+7;
    ll x = modpow(10,N) - t;
    if (x < 0) x += INF + 7;
    cout << x << endl;
}
void solve3() {
    ll N; cin >> N;
    ModInt<mod> p(9),q(8),r(10);
    auto x = p.pow(N);
    x = x + x;
    auto t = q.pow(N);
    r = r.pow(N);
    cout << ( r - (x - t) ) << endl;

}

int main() {
    solve3();
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int N;
  cin >> N;
  vector<P> graph[N+1];
  rep(i, N-1) {
    int a, b;
    cin >> a >> b;
    graph[a].emplace_back(b, i);
    graph[b].emplace_back(a, i);
  }
  int root = 1;
  vector<int> parent(N+1, -1);
  vector<int> order;
  vector<int> color(N-1);
  vector<P> stk;
  stk.emplace_back(root, -1);
  int maxNum = 1;
  while (!stk.empty()) {
    auto p = stk.back();
    int cur = p.first;
    int colP = p.second;  // 親との辺をcolPとする
    stk.pop_back();
    order.push_back(cur);
    int col = 1;
    for (auto pa : graph[cur]) {
      int next = pa.first;
      if (next == parent[cur]) continue;
      if (col == colP) ++col;
      parent[next] = cur;
      color[pa.second] = col;
      stk.emplace_back(next, col);
      if (col > maxNum) maxNum = col;
      ++col;
    }
  }
  cout << maxNum << '\n';
  for (int i = 0; i < N-1; i++) {
    cout << color[i] << '\n';
  }
  return 0;
}

Measured memory_bytes: 10680
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

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

    bool ok = true;
    for (int i = 0; i < S.length(); i+= 2) {
        if (!(S[i]=='h' && S[i+1]=='i')) {
            ok = false;
        } 
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int main(){
    ll n; cin>>n;
    ll W; cin>>W;
    vector<ll> dp(W+1);
    // dp[i] - The maximum total value of items with total weight equal to i
    ll curr_weight;
    for(ll item=0; item<n; ++item){
        ll weight, value;  cin>>weight>>value;
        for(ll curr_weight =W-weight; curr_weight>=0; --curr_weight){
            dp[curr_weight+weight] = max(dp[curr_weight+weight], dp[curr_weight] + value);
        }
    }
    ll ans = 0;
    for(ll i=0; i<=W ;++i){
        ans = max(dp[i], ans);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1024
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	type point struct{ x, y int }
	rs := make(map[point]bool)
	for i := 0; i < n; i++ {
		p := point{}
		fmt.Scan(&p.x, &p.y)
		rs[p] = true
	}

	bs := make([]point, n)
	for i := range bs {
		fmt.Scan(&bs[i].x, &bs[i].y)
	}

	sort.Slice(bs, func(i, j int) bool { return bs[i].x < bs[j].x })
	ans := 0
	for _, b := range bs {
		ps := make([]point, 0, n)
		for r := range rs {
			if r.x < b.x && r.y < b.y {
				ps = append(ps, r)
			}
		}

		if len(ps) > 0 {
			sort.Slice(ps, func(i, j int) bool { return ps[i].y > ps[j].y })
			delete(rs, ps[0])
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 2032
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REP1(i, n) for (ll i = 1; i <= n; i++)
#define RREP(i, n) for (ll i = n - 1; i >= 0; i--)
#define RREP1(i, n) for (ll i = n; i >= 1; i--)
#define FOR(i, a, b, c) for (ll i = a; i <= b; i += c)
#define RFOR(i, a, b, c) for (ll i = a; i >= b; i -= c)
#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a < b ? a : b)
#define INF 1145141919
typedef long long ll;
    
int main() {
    int x;
    scanf("%d", &x);

    int sum = 0;
    REP(i, INF) {
        sum += i;
        if (sum >= x) {
            printf("%d", i);
            return 0;
        }
    }
}


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

using pll = pair<long long, long long>;

int main() {
    int n,m; cin >> n >> m;
    vector<pair<int,int>> r(m);
    for(int i=0; i<m; i++){
        int a,b; cin >> a >> b; a--; b--;
        r[i] = {a,b};
    }

    sort(r.begin(),r.end(),[](pair<int,int> a,pair<int,int> b){return a.second < b.second;});

    int res = 0;
    int cur = -1;
    for(int i=0; i<m; i++){
        if(cur > r[i].first) continue;
        res++;
        cur = r[i].second;
    }
    cout << res << endl;
}

Measured memory_bytes: 4040
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int n,a,b,p,t1,t2,t3,i,x;
	scanf("%d",&n);
	scanf("%d %d",&a,&b);
	t1=0; t2=0; t3=0;
	for(i=0;i<n;i++)	{
		scanf("%d",&p);
		if(p<=a)	t1++;
		else if(p<=b)	t2++;
		else t3++;
	}
	x=min(t1,t2);
	x=min(x,t3);
	printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false)
long long a[1001][1002];
int main()
{
        IO;
        string s; int i, n, j;
        cin>>n;
        j=2*(n-n%500); i=n%500; j+=i-(i%5);
        cout<<j<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,a,b;cin>>n>>m>>a>>b;
  vector<vector<int>>v(n, vector<int>(m));
  for(int i=a-1;i<n;i+=a){
    for(int j=b-1;j<m;j+=b){
      v[i][j]=-1000000;
    }
  }
  for(int i=0;i<n;i+=a){
    for(int j=0;j<m;j+=b)v[i][j]=999999;
  }
  if(n%a||m%b){
    cout<<"Yes"<<endl;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(j)cout<<' ';
        cout<<v[i][j];
      }
      cout<<endl;
    }
  }
  else cout<<"No"<<endl;
}
  


Measured memory_bytes: 3200
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){a %= mod;ll ans = 1;while(b){if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{bool operator()(const pii & a, const pii & b){return a.second > b.second;}};
int lb(int x){return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 1e5+5;
int a[maxn];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i ++ )
		scanf("%d",&a[i]);
	sort(a + 1, a + 1 + n);
	ll ans = 0;
	for (int i = 1; i <= m; i ++ )
	{
		ans += a[i];
	}
	printf("%lld\n",ans);

}

Measured memory_bytes: 3244
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rep(i, n) for(ll i = 0;i < n;i++)
template<class T, class U> void chmax(T& a, U b) { if (a<b) a = b; }
template<class T, class U> void chmin(T& a, U b) { if (a>b) a = b; }

int n;
int ans = 0;

// a, b, c = 3, 5, 7
void cnt(int a, int b, int c, ll x) {
  if (x > n) return;
  if (a > 0 && b > 0 && c > 0) ans++;

  cnt(a+1, b, c, x*10+3);
  cnt(a, b+1, c, x*10+5);
  cnt(a, b, c+1, x*10+7);
}

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

  cin >> n;

  cnt(1, 0, 0, 3);
  cnt(0, 1, 0, 5);
  cnt(0, 0, 1, 7);

  cout << ans << endl;
}


Measured memory_bytes: 256
//E.H//
# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<long long,long long>
typedef long long ll;
ll t,n,a,b,c,d;;
map<ll,ll>memo;
int divi[]={2,3,5};
ll cost[5];
ll f(ll x){
    if(x==0) return 0;
    if(x==1) return d;
    if(memo.count(x)) return memo[x];
    ll cnt=LLONG_MAX;
    if(x< LLONG_MAX/d) cnt=x*d;
    for(int i=0;i<3;i++){
        ll bwh =( x/divi[i] )* divi[i];
        ll atas=(x/divi[i] + (x%divi[i] > 0)) * divi[i];
        cnt=min(cnt,f(bwh/divi[i]) + cost[i] + ( abs(x-bwh) * d));
        cnt=min(cnt,f(atas/divi[i]) + cost[i] + ( abs(x-atas) * d));
    }
    //cout<<x<<" "<<cnt<<endl;
    return memo[x]=cnt;


}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>cost[0]>>cost[1]>>cost[2]>>d;
        memo.clear();
        cout<<f(n)<<endl;
    }
}

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

void solve(int N, int M, vector<ll> H){
    vector<int> ans;
    ans = vector<int> (N, 1);
    int s, t;
    ll low_h;
    for (int i=0; i<M; i++){
        cin >> s >> t;
        if (H[s-1]==H[t-1]){
            ans[s-1]=0;
            ans[t-1]=0;
        }else{
            low_h = min(H[s-1], H[t-1]);
            if (H[s-1]==low_h) ans[s-1]=0;
            else ans[t-1] = 0;
        }
    }
    //cout << ans[0] << ans[1] << ans[2]<< ans[3]<< ans[4]<< ans[5]<<endl;
    cout << accumulate(ans.begin(), ans.end(), 0) << endl;
}

int main(){
    int N, M;
    cin >> N >> M;
    vector<ll> H;
    H = vector<ll>(N, 0);
    ll h;
    for (int i=0; i<N; i++){
        cin >> h; H[i] = h;
    }
   solve(N, M, H);
}

Measured memory_bytes: 5028
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define Rep(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define Repr(i, b, e) for(int (i) = (b) - 1; (i) >= (e); --(i))
#define Print(x) cout << (x) << endl 
#define Min2(a, b) ((a) < (b)) ? (a) : (b)
#define Max2(a, b) ((a) > (b)) ? (a) : (b)

typedef long long ll;

using namespace std;

int N, K;
string C[10];
set<string> bt;

void dfs(string str, int k, int state){
    if(k == 0){
        bt.insert(str);
        return;
    }
    Rep(i, 0, N){
        if((1 << i) & state) continue;
        dfs(str + C[i], k - 1, state | (1 << i));
    }
}

int main(){
    while(true){
        cin >> N >> K;
        if(N == 0 && K == 0) break;
        Rep(i, 0, N) cin >> C[i];
        dfs("", K, 0);
        Print(bt.size());
        bt.clear();
    }
    return 0;
}


Measured memory_bytes: 3412
#include <stdio.h>
#include <string.h>

  int i,j,k,l,m;
  int n,e,s,w,un,up;
  int a[7];
int t;


void input() {
 for(i=0;i<6;i++){
  
    scanf("%d",&a[i+1]);
  
  }
}

 void N() {
   t = a[1];
   a[1] = a[2];
   a[2] = a[6];
   a[6] = a[5];
   a[5] = t;
 }

 void S() {
   t = a[1];
   a[1] = a[5];
   a[5] = a[6];
   a[6] = a[2];
   a[2] = t;
}

 void E() {
   t = a[1];
   a[1] = a[4];
   a[4] = a[6];
   a[6] = a[3];
   a[3] = t;
 }

 void W() {
   t = a[1];
   a[1] = a[3];
   a[3] = a[6];
   a[6] = a[4];
   a[4] = t;
 }

int main() {

  input();
  //  strlen(?) 文字の長さ(数)を表示
 char str[110];  
 scanf("%s",str);

 for(i=0;i<strlen(str);i++) {

   if(str[i] == 'N') {
     N();
   } else if(str[i] == 'S') {
     S();
   } else if(str[i] == 'W') {
     W();
   } else if(str[i] == 'E') {
     E();
   }
 }

 printf("%d\n",a[1]);

 return 0;
}

Measured memory_bytes: 596
from collections import Counter

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

C = Counter(a)
C_items = list(C.items())
if len(C_items) == 1:
    if C_items[0][0] == 0:
        print('Yes')
    else:
        print('No')
elif len(C_items) == 2:
    if C_items[0][0] == 0 and C_items[0][1] * 2 == C_items[1][1]:
        print('Yes')
    else:
        print('No')
elif len(C_items) == 3:
    if C_items[0][0] ^ C_items[1][0] == C_items[2][0] and C_items[0][1] == C_items[1][1] == C_items[2][1]:
        print('Yes')
    else:
        print('No')
else:
    print('No')


Measured memory_bytes: 60784
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func stringLineScan() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000009)
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(stringLineScan())
	ans := make([]string, 0)
	for i := 1; ; i *= -2 {
		if n%(i*2) == 0 {
			ans = append(ans, "0")
		} else {
			ans = append(ans, "1")
			n -= i
		}
		if n == 0 {
			break
		}
	}
	for i := len(ans) - 1; i >= 0; i-- {
		fmt.Print(ans[i])
	}
	fmt.Println("")
}


Measured memory_bytes: 640
/*||>>>> Praveen Ojha <<<<>>>> 10 June 2019 <<<<>>>> 02:44:47 <<<<||*/
// #pragma GCC optimize("Ofast") //(Very Fast but Inaccurate)
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //(Small operations in many loops)
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define mod 1000000007
#define inf 1e18+5
#define sz(x) (int)x.size()
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vpii vector<pair<int,int> > 
#define vvi vector<vector<int> >
#define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long double ld;
typedef pair<int,int> pii;
//Read Problems Carefully & Check for corner cases N=0,1 ?
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////

int32_t main(){__
	int n,m,x;
	cin>>n>>m;
	vi dp(n+1,0),brk(n+1,0);
	for(int i=0;i<m;i++)
		cin>>x,brk[x]=1;
	dp[0]=1;
	if(!brk[1])
		dp[1]=1;
	for(int i=2;i<=n;i++){
		if(brk[i])
			continue;
		dp[i]=(dp[i-1]+dp[i-2])%mod;
	}
	cout<<dp[n]<<"\n";
return 0;
}

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

#define rep(i, n) for ( ll i = 0; i < (n); ++i )
#define reps(i, n) for ( ll i = 1; i <= (n); ++i )
#define _rep(i, n) for ( ll i = (n) - 1; i >= 0; --i )
#define _reps(i, n) for ( ll i = n; i > 0; --i )
#define all(x) (x).begin(), (x).end()
#define _all(x) (x).rbegin(), (x).rend()

using namespace std;
using ll =  long long;
using P = pair<ll, ll>;

int main( void )
{
	ll n, k;
	cin >> n >> k;

	bool sn[n] = {};
	rep( i, k ) {
		ll d;
		cin >> d;
		rep( j, d ) {
			ll a;
			cin >> a;

			sn[a - 1] = true;
		}
	}

	ll cnt = 0;
	rep( i, n ) {
		if ( !sn[i] ) {
			cnt++;
		}
	}

	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
#define N 36

typedef struct
{
  char ki;
  int su;
}inf;

int main()
{
  int n,i,j,de1,minj,de2,flag=0;
  char ni1,ni2;
  inf cards1[N],cards2[N];
  scanf("%d",&n);
  for(i=0;i<=n-1;i++)
    {
      scanf(" %c%d",&cards1[i].ki,&cards1[i].su);
    }

  for(i=0;i<=n-1;i++)
    {
      cards2[i].ki=cards1[i].ki;
      cards2[i].su=cards1[i].su;
    }
  /*
  for(i=0;i<=n-1;i++)
    {
      printf("%c%d ",cards2[i].ki,cards2[i].su);
    }
  printf("\n");
  */
  for(i=0;i<=n-1;i++)
    {
      for(j=n-1;j>=i+1;j--)
	{
	  if(cards1[j].su<cards1[j-1].su)
	    {
	      //C[j] と C[j-1] を交換
	      de1=cards1[j].su;
	      ni1=cards1[j].ki;
	      cards1[j].su=cards1[j-1].su;
	      cards1[j].ki=cards1[j-1].ki;
	      cards1[j-1].su=de1;
	      cards1[j-1].ki=ni1;
	    }
	}
    }
  for(i=0;i<=n-1;i++)
    {
      minj=i;
      for(j=i;j<=n-1;j++)
	{
	  if(cards2[j].su<cards2[minj].su)
	    {
	      minj=j;
	    }
	}
      //C[i] と C[minj] を交換
      de2=cards2[i].su;
      ni2=cards2[i].ki;
      cards2[i].su=cards2[minj].su;
      cards2[i].ki=cards2[minj].ki;
      cards2[minj].su=de2;
      cards2[minj].ki=ni2;
    }
  for(i=0;i<=n-1;i++)
    {
      if(cards1[i].ki!=cards2[i].ki)
	{
	  flag=1;
	}
    }
  for(i=0;i<=n-1;i++)
    {
      if(i==n-1)
	{
	  printf("%c%d\n",cards1[i].ki,cards1[i].su);
	}
      else
	{
	  printf("%c%d ",cards1[i].ki,cards1[i].su);
	}
    }
  printf("Stable\n");
  for(i=0;i<=n-1;i++)
    {
      if(i==n-1)
	{
	  printf("%c%d\n",cards2[i].ki,cards2[i].su);
	}
      else
	{
	  printf("%c%d ",cards2[i].ki,cards2[i].su);
	}
    }
  if(flag==1)
    {
      printf("Not stable\n");
    }
  else
    {
      printf("Stable\n");
    }

  return 0;
}

/*
#include <stdio.h>
#define N 36
tepedef struct
{
  char kigou;
  int suuzi;
}cardsinf;

void BubbleSort(char,int);
void SelectionSort(char,int);

int main()
{
  int casu,i;
  cardsinf cards[N];
  scanf("%d",&casu);
  for(i=0;i<casu;i++)
    {
      scanf("%c%d",&cards[i].kigou,&cards[i].suuzi);
    }

  for(i=0;i<casu;i++)
    {
      BubbleSort(cards[i].kigou,cards[i].suuzi);
      SelectionSort(cards[i].kigou,cards[i].suuzi);
    }



  for(i=0;i<casu;i++)
    {
      if(i<casu-1)
	{
	  printf("%c%d ",cards[i].kigou,cards[i].suuz);
	}
      else
	{
	  printf("%c%d",cards[i].kigou,cards[i].suuz);
	}
    }
  return 0;
}

void BubbleSort(char kigou,int suuzi)
{

}

void SelectionSort(char kigou,int suuzi)
{

}

void BubbleSort(C, N)
{
  for (i=0;i<=N-1;i++)
    {
      for (j=N-1;j>=i+1;i--)
	{
	  if (C[j].value < C[j-1].value)
	    {
	      //C[j] と C[j-1] を交換
	    }
	}
    }
}

void SelectionSort(C, N)
{
  for(i=0;i<=N-1;i++)
    {
      minj=i;
      for(j=i;j<=N-1;j++)
	{
	  if(C[j].value < C[minj].value)
	    {
	      minj=j;
	    }
	}
      //C[i] と C[minj] を交換
    }
}

*/



Measured memory_bytes: 2112
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<float.h>

using namespace std;
#define ll long long


int main(void){
    int batsu=0;
    string S;
    cin>>S;
    for(int i=0;i<S.size();i++) if(S.at(i)=='x') batsu++;
    if(batsu<=7) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios::base_sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
#define M 1000000007
#define pie 3.141592653589793238
using namespace std;


signed main(){  
    int k,x;
    cin >> k >> x;
    if(500*k >= x){
        cout << "Yes";
    }
    else{
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
#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;
typedef pair<ll, int> P;
struct BIT{
  vector<ll> data;
  int n;
  // 最大値求めたいとき最初は0を入れておく？
  // データはaddで随時追加してもいいし最初に全部入れても良い問題による
  BIT(int n) : data(n + 1, 0), n(n){return;}
  ll sum(int l, int r){return sum_(r) - sum_(l);}
  ll sum_(int i){
    ll res = 0;
    while(i > 0){res += data[i];i -= i & -i;}
    return res;
  }
  void add(int i, int x){
    while(i <= n){data[i] += x;i += i & -i;}
    return;
  }
};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K;
  cin >> N >> K;
  ll A[N+1], sum[N+1];
  CLR(A);
  CLR(sum);
  vector<P> v(N+1);
  FOR(i,0,N){
    cin>>A[i];
    A[i] -= K;
    sum[i+1] = sum[i] + A[i];
  }
  FOR(i,0,N+1){
    v[i] = P(sum[i], i);
  }
  sort(v.begin(), v.end());
  int num = 1;
  FOR(i,0,N+1){
    if(i > 0 && v[i].first != v[i-1].first) num++;
    A[v[i].second] = num;
  }
  BIT bit(202020);
  ll ans = 0;
  FOR(i,0,N+1){
    ans += bit.sum_(A[i]);
    bit.add(A[i], 1);
  }
  cout<<ans<<endl;
  
}

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

int main () {
  int N , D;
  cin >> N >> D;

  if(N % (D * 2 + 1) == 0){
    cout << N / (D * 2 + 1) << endl;
  }

  else{
    cout << N / (D * 2 + 1) + 1 << endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void){
	char a[]="XYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
	char x[1005];
	char y[1005];
	scanf("%s",x);
	int length;
	length=(int)strlen(x);
	int i,j;
	for (i=0;i<length;i++){
		for (j=28;j>2;j--){
			if (strncmp(&x[i],&a[j],1)==0){
				strncpy(&y[i],&a[j-3],1);
			}
		}
	}
	y[length]='\0';
	printf("%s\n",y);
	return 0;
}

Measured memory_bytes: 532
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 500005;

int a, b, c, ok, i, tab1[9], tab2[9], tab[9], n;

int main() {
scanf("%d", &n);
for (i=0;i<n;i++) scanf("%d", &tab1[i]);
for (i=0;i<n;i++) scanf("%d", &tab2[i]);
for (i=0;i<n;i++) tab[i] = i + 1;
c = 0;
do {
	ok = 1;
	for (i=0;i<n;i++) if (tab1[i] != tab[i]) ok = 0;
	if (ok) a = c;
	ok = 1;
	for (i=0;i<n;i++) if (tab2[i] != tab[i]) ok = 0;
	if (ok) b = c;
	c++;
} while (next_permutation(tab, tab + n));
printf("%d\n", abs(a - b));
}





Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << (x) << endl;
typedef long long ll;
const int MAX = 999999999;

ll cal_gcd(ll n, ll m){
    ll tmp;
    while(m % n != 0){
        tmp = n;
        n = m % n;
        m = tmp;
    }

    return n;
}


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

    vector<ll> clocks(n);
    rep(i, n) cin >> clocks[i];

    ll max_value = *max_element(all(clocks));
    rep(i, n){
        if(max_value % clocks[i] != 0){
            max_value = clocks[i] / cal_gcd(clocks[i], max_value) * max_value;
        }
    }

    cout << max_value << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<vector<int>> score(n, vector<int>(2));
	for (int i = 0; i < n; i++) {
		cin >> score.at(i).at(0) >> score.at(i).at(1);
	}
	sort(score.begin(), score.end());
	int ans = score.at(n - 1).at(0) + score.at(n - 1).at(1);
	cout << ans << endl;
}

Measured memory_bytes: 7808
import collections
N=int(input())
A=list(map(int,input().split()))

d=collections.Counter(A)
e=0
f=list(d.values())

for i in range(len(f)):
  e+=(f[i]*(f[i]-1))/2

for j in range(N):
  if d[A[j]]==1:
    print(int(e))
  else:
    print(int(e-d[A[j]]+1))

Measured memory_bytes: 90700