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

struct Edge {
    int to, id;
    Edge(int to, int id) : to(to), id(id) {}
};

vector<Edge> g[55];

vector<int> es;

bool dfs(int v, int tv, int p = -1) {
    if(v == tv) return true;
    for(Edge e : g[v]) {
        if(e.to == p) continue;
        if(dfs(e.to, tv, v)) {
            es.push_back(e.id);
            return true;
        }
    }
    return false;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--;
        b--;
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }
    int m;
    cin >> m;
    vector<long long> eset(m);
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--;
        b--;
        es = vector<int>();
        dfs(a, b);
        for(auto&& e : es) {
            eset[i] |= (1LL << e);
        }
    }
    long long ans = 0;
    for(int i = 0; i < (1 << m); i++) {
        long long mask = 0;
        for(int j = 0; j < m; j++) {
            if(i >> j & 1) mask |= eset[j];
        }
        int white = __builtin_popcountll(mask);
        long long now = 1LL << (n - 1 - white);
        if(__builtin_popcountll(i) % 2 == 0) ans += now;
        else ans -= now;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3696
#include<iostream>
#include<cstdio>
#include<vector>

int n,m;

struct edge{int to,nxt;}E[4050];
int H[2050],tot;
void add_edge(int a,int b){
	E[++tot]=(edge){b,H[a]},H[a]=tot;
	E[++tot]=(edge){a,H[b]},H[b]=tot;
}

int Lson[8000050],Rson[8000050],ptot;
std::pair<int,int> paths[8000050],res[2050];
bool removed[8000050];

int dep[2050],Fa[2050],accu[2050],lst[2050],lsttop;
std::vector<int> Id[2050],tmp;
std::vector<int> roots;

void pre(int now,int fa){
	lst[++lsttop]=now;
	dep[now]=dep[fa]+1,Fa[now]=fa;
	for (int i=H[now];i;i=E[i].nxt)
		if (E[i].to!=fa) pre(E[i].to,now);
}
int LCA(int x,int y){
	while (dep[x]>dep[y]) x=Fa[x];
	while (dep[y]>dep[x]) y=Fa[y];
	while (x!=y) x=Fa[x],y=Fa[y];
	return x;
}

void solve(int now,int fa){
	for (int i=H[now];i;i=E[i].nxt)
		if (E[i].to!=fa) solve(E[i].to,now);
	tmp.clear();
	for (std::vector<int>::iterator it=Id[now].begin();it!=Id[now].end();++it)
		if (!removed[*it]){
			if (paths[*it].first==paths[*it].second) roots.push_back(*it),removed[*it]=true;
			else tmp.push_back(*it);
		}
	Id[now]=tmp;
	while (Id[now].size()>=2){
		int nxt=++ptot,x,y;
		x=paths[Id[now].back()].first==now?paths[Id[now].back()].second:paths[Id[now].back()].first;
		Lson[nxt]=Id[now].back();
		removed[Id[now].back()]=true;
		Id[now].pop_back();
		y=paths[Id[now].back()].first==now?paths[Id[now].back()].second:paths[Id[now].back()].first;
		Rson[nxt]=Id[now].back();
		removed[Id[now].back()]=true;
		Id[now].pop_back();

		paths[nxt]=std::make_pair(x,y);

		Id[x].push_back(nxt);
		Id[y].push_back(nxt);
	}
	if (Id[now].size()){
		int nxt=++ptot,x;
		x=paths[Id[now].back()].first==now?paths[Id[now].back()].second:paths[Id[now].back()].first;
		Lson[nxt]=Id[now].back();
		removed[Id[now].back()]=true;
		paths[nxt]=std::make_pair(x,Fa[now]);
		Lson[nxt]=Id[now].back();
		Id[now].pop_back();

		Id[Fa[now]].push_back(nxt);
		if (x!=Fa[now]) Id[x].push_back(nxt);
	}
}

void gett(int now,bool way){
	if (!Lson[now]){
		if (way) std::swap(paths[now].first,paths[now].second);
		res[now]=paths[now];
	}
	else if (!Rson[now]){
		if (paths[now].first==paths[Lson[now]].first||paths[now].second==paths[Lson[now]].second) gett(Lson[now],way);
		else gett(Lson[now],!way);
	}
	else{
		if (paths[now].first==paths[Lson[now]].first) gett(Lson[now],way);
		else gett(Lson[now],!way);
		if (paths[now].second==paths[Rson[now]].first) gett(Rson[now],!way);
		else gett(Rson[now],way);
	}
}

int ans;

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add_edge(x,y);
	pre(1,0);
	for (int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y),paths[i]=std::make_pair(x,y);
		Id[x].push_back(i),Id[y].push_back(i);
		accu[x]++,accu[y]++,accu[LCA(x,y)]-=2;
	}
	for (int i=n;i;i--) accu[Fa[lst[i]]]+=accu[lst[i]];
	for (int i=1;i<=n;i++) ans+=std::min(accu[i],2);
	printf("%d\n",ans);
	ptot=m;

	solve(1,0);
	for (std::vector<int>::iterator it=roots.begin();it!=roots.end();++it) gett(*it,false);
	for (int i=1;i<=m;i++) printf("%d %d\n",res[i].first,res[i].second);
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); i++)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FOREACH(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define SIZE(v) ((int)(v).size())
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define ll long long
#define llint long long
#define pii pair<int, int>
#define UNVISITED -1


template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(vc.empty()) return "";
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}
 
template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
 
class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

const int MAX = 10100;
int D[MAX];

int main() {
    int N; scanf("%d", &N);
    REP(i, N) {
        int x, y; scanf("%d %d", &x, &y);
        D[i] = x - y;
    }
    bool possible = false;
    REP(i, N) if(i + 2 < N) {
        if((D[i] | D[i + 1] | D[i + 2]) == 0) possible = true;
    }
    if(possible) printf("Yes\n");
    else printf("No\n");
}

Measured memory_bytes: 3760
s=input()
an=[]
for m in "qwertyuiopasdfghjklzxcvbnm":
  i=0
  d=[len(s)-j for j in range(len(s))]
  while s.find(m,i)>=0:
    t=s.find(m,i)
    for j in range(t+1):
      d[j]=min(t-j,d[j])
    i=t+1

  mi=0
  for i in range(len(s)):
    mi=max(mi,d[i])
  an.append(max(d))
print(min(an))


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

int const N = 12, M = 200000, K = 531441;
int n, p3[N + 1], an[K];
char s[M + 1];

struct S{
	int x;
	bool fl;
	S* g[3];
	S():fl(false) { f(i, 0, 3)g[i] = 0; }
}*R;

void pl(S* &v = R, int m = 0, int x = 0){
	v = new S();
	if (m == n){
		v->x = x;
		return;
	}
	pl(v->g[0], m + 1, x);
	pl(v->g[1], m + 1, x + p3[m]);
	pl(v->g[2], m + 1, x + 2 * p3[m]);
}

void flp(S* v = R){
	swap(v->g[1], v->g[2]);
	v->fl ^= 1;
}

void sl(S* v){
	if (!v->fl)return;
	v->fl = false;
	flp(v->g[0]);
	flp(v->g[1]);
	flp(v->g[2]);
}

void ad(S* v = R){
	if (!v->g[0])return;
	sl(v);
	S* t = v->g[2];
	v->g[2] = v->g[1];
	v->g[1] = v->g[0];
	v->g[0] = t;
	ad(t);
}

void fn(S* v = R, int m = 0, int x = 0){
	if (m == n){
		an[v->x] = x;
		return;
	}
	sl(v);
	fn(v->g[0], m + 1, x);
	fn(v->g[1], m + 1, x + p3[m]);
	fn(v->g[2], m + 1, x + 2 * p3[m]);
}

int main(){
	scanf("%d%s", &n, s);
	p3[0] = 1;
	f(i, 1, n + 1)p3[i] = p3[i - 1] * 3;
	pl();
	
	int m = strlen(s);
	f(i, 0, m)if (s[i] == 'S')flp();
	else ad();
	
	fn();
	printf("%d", an[0]);
	f(i, 1, p3[n])printf(" %d", an[i]);
	printf("\n");
}

Measured memory_bytes: 43684
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

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

	vector<long> v;
	rep(i,0,n){
		long l;
		cin >> l;
		v.push_back(l);
	}
	
	vsort(v);
	int cnt = 0;
	while(1){
		rep(i,0,n){
			if(v[i] % 2 == 1){
				P(cnt);
				ret 0;
			}
			v[i] /= 2;
		}
		cnt++;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iomanip>
#include <unordered_map>
#include <string>
#include <unordered_set>
using namespace std;
int a,b,k;
int main() {
    cin >> k >> a >> b;
    for(int i = a; i <= b;i ++) {
        if(i % k == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" <<endl;
    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main (void) {
	int n, i, j, key;
	int* data;
	scanf("%d", &n);
	data = (int*)malloc(sizeof(int) * n);
	for (i = 0; i < n; i++) {
		scanf("%d", data + i);
	}
	for (i = 1; i < n; i++) {
		for (j = 0; j < n; j++) {
			printf("%d", data[j]);
			if (j < n - 1) printf(" ");
			else printf("\n");
		}
		key = data[i];
		j = i - 1;
		while (j >= 0 && data[j] > key) {
			data[j + 1] = data[j];
			j--;
		}
		data[j + 1] = key;
	}
	for (j = 0; j < n; j++) {
		printf("%d", data[j]);
		if (j < n - 1) printf(" ");
		else printf("\n");
	}
	free(data);
	return 0;
}


Measured memory_bytes: 1992
n = gets.to_i
s = gets.chomp.split(" ")
qn = []
cnt = 0

(2 * n).times{|i|
    qn.push(s[i].to_i)
}

qn.sort! {|a, b| b <=> a }

n.times{|i|
   cnt += qn[2 * i + 1]
}
puts cnt


Measured memory_bytes: 1788
import java.util.*;
    public class Main
    {
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            double A = sc.nextDouble();
            double B = sc.nextDouble();
            if(A==B)
            {
                System.out.println("EQUAL");
            }
            else if(A>B)
            {
                System.out.println("GREATER");
            }
            else
            {
                System.out.println("LESS");
            }
        }
    }

Measured memory_bytes: 23252
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                       _oo0oo_
                      o8888888o
                      88" . "88
                      (| -_- |)
                      0\  =  /0
                    ___/`---'\___
                  .' \\|     |// '.
                 / \\|||  :  |||// \
                / _||||| -:- |||||- \
               |   | \\\  -  /// |   |
               | \_|  ''\---/''  |_/ |
               \  .-\__  '-'  ___/-. /
             ___'. .'  /--.--\  `. .'___
          ."" '<  `.___\_<|>_/___.' >' "".
         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
         \  \ `_.   \_ __\ /__ _/   .-` /  /
     =====`-.____`.___ \_____/___.-`___.-'=====
                       `=---='
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
    Sourav Verma IPG_2013  ABV_IIITMG Task @ Codeforces 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/    

#include<bits/stdc++.h>

#define ll                    long long int
#define loop(i,a,b)           for(int i=(int)a;i<(int)b;++i)
#define rloop(i,a,b)          for(int i=(int)a;i<=(int)b;++i)
#define loopr(i,a,b)          for(int i=(int)a;i>=(int)b;--i)
#define count_1(n)            __builtin_popcountll(n)
#define pb                    push_back
#define mset(a,b,c)           loop(i,0,b) a[i]=c
#define F                     first
#define S                     second
#define mp                    make_pair
#define clr(x)                x.clear()
#define MOD                   1000000007
#define MAX                   1e9
#define MIN                   -1e9
#define itoc(c)               ((char)(((int)'0')+c))
#define vi                    vector<int>
#define vvi                   vector<vi>
#define pll                   pair<ll,ll>
#define pii                   pair<int,int>
#define all(p)                p.begin(),p.end()
#define mid(s,e)              (s+(e-s)/2)
#define mini                  INT_MIN
#define sv()                  int t; scanf("%d",&t); while(t--)
using namespace std;
ll extgcd(ll a,ll b,ll& x,ll& y){if(b==0){x=1;y=0;return a;}else{int g=extgcd(b,a%b,y,x);y-=a/b*x;return g;}}
ll lcm(int x, int y) { return x * 1ll * y / (int)__gcd(x, y); }
ll hcf(ll a, ll b) {if(b>a) return (hcf(b, a)); if(a%b==0) return b; return (hcf(b, a%b));} 
ll modpow(ll a,ll b) {ll res=1;a%=MOD;for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}

int main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0);
    string s,s1; cin>>s;
    loop(i,0,s.length()){
        if(s[i]!='B') s1+=s[i];
        else if(s1!="") s1.pop_back();
    }
    cout<<s1;
    return 0;
}

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

typedef long double ld;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

#define FOR(i, b, e) for (int i = b; i <= e; i++)
#define FORD(i, b, e) for (int i = b; i >= e; i--)
#define SIZE(x) ((int)(x).size())
#define pb push_back
#define st first
#define nd second
#define all(a) begin(a), end(a)
#define watch(x) cerr << (#x) << " is " << (x) << '\n';

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

    string s;
    cin >> s;

    bool ok = 1;

    for (int i = 0; i < SIZE(s); i += 2) {
        if (s[i] == 'L') ok = 0;
    }
    for (int i = 1; i < SIZE(s); i += 2) {
        if (s[i] == 'R') ok = 0;
    }

    cout << (ok ? "Yes" : "No");

    return 0;
}


Measured memory_bytes: 256
import math
MOD = 10**9+7
N = int(input())
X = list(map(int,input().split()))
Y = [0]*N
Y[0] += 1
X[0] = 1
hoge = 0
for i in range(1,N):
    X[i] = min(X[i-1]+2,X[i])
    Y[hoge] += 1
    if X[i]-X[i-1] == 1:
        hoge += 1
        X[i] = X[i-1]
ans = 1
mem = 0
for i in range(N):
    mem += Y[i]
    ans *= mem
    ans %= MOD
    mem -= 1
print(ans)

Measured memory_bytes: 14716
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

int main(){

  int M, D; cin >> M >> D;

  int ans = 0;
  for (int i = 1; i <= D; i++){
    int dig1 = i / 10;
    int dig2 = i % 10;

    if (dig1 >= 2 && dig2 >= 2){
      if (dig1 * dig2 <= M){
        ans++;
      }
    }
  }
  
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;int64_t N,P,a,c[1<<20],i,j;string S;main(){cin>>N>>P>>S;if(10%P){reverse(S.begin(),S.end()),c[0]=j=1;for(char v:S)i+=(v-48)*(j=j*10%P),a+=c[i%=P]++;}else for(;i<N;a+=(S[i++]-48)%P?0:i);cout<<a;}

Measured memory_bytes: 644
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>
#include <cmath>
#include <numeric>
#include <iomanip>

using namespace std;

#define int long long

#define rep(i, n) for (int i=0;i<(int)n;++i)
#define rep1(i, n) for (int i=1;i<=(int)n;++i)
#define rrep(i, n) for (int i=(int)n-1;i>=0;--i)
#define rrep1(i, n) for (int i=n;i>=1;--i)
#define range(i, l, r) for (int i=l;i<(int)r;++i)
#define rrange(i, l, r) for (int i=(int)r-1;i>=(int)l;--i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
int read(){int a;scanf("%lld",&a);return a;}
constexpr int TEN(int n){return n==0?1:10*TEN(n-1);}

signed main()
{
	int n; cin >> n;
	vi a(n);
	rep(i, n) cin >> a[i];
	sort(all(a));

	int idx = lower_bound(begin(a), end(a) - 1, a[n - 1] / 2) - begin(a);

	int cur = a[idx];

	if (idx - 1 >= 0) {
		if (abs(2 * a[idx] - a[n - 1]) >= abs(2 * a[idx - 1] - a[n - 1])) {
			cur = a[idx - 1];
		}
	}

	cout << a[n - 1] << ' ' << cur << endl;
}



Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    if S[0] != 'A':
        return 'WA'
    if S[2:-1].count('C') != 1:
        return 'WA'

    u = 0
    for c in S:
        if c.isupper():
            u += 1
    if u != 2:
        return 'WA'
    return 'AC'


def main():
    S = read_str().strip()
    print(slv(S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 62572
#include <bits/stdc++.h>
#define fi first
#define se second
#define F(i,n) for (int i = 0; i < n; ++i)
#define pb push_back
#define int long long
using namespace std;
typedef vector<int> vi;
int a[100001];
main () {
	int n, b, sum = 0; cin >> n; 
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < n; ++i) sum += a[i];
	if (sum % (n * (n + 1) / 2)) { cout << "NO\n"; exit(0); }
	int m = sum / (n * (n + 1) / 2);
	for (int j = n - 1 ; j > 0; --j) {
		a[j] -= a[j - 1];
		if (a[j] > m) { cout << "NO\n"; exit(0); }
		if ((m - a[j]) % n) { cout << "NO\n"; exit(0); }
	}
	cout << "YES\n"; 
	return 0;
}



Measured memory_bytes: 1024
#include <stdbool.h>
#include <stdint.h>

#define MEM_SIZE 500
static int64_t fib_mem[MEM_SIZE];

int64_t fibonacchi_number(int64_t n)
{
  static bool initialized = false;
  if (!initialized) {
    uint32_t i;
    for (i = 0; i < MEM_SIZE; i++) {
      fib_mem[i] = -1;
    }
    initialized = true;
  }

  if (n == 0)
    return fib_mem[n] = 1;
  else if (n == 1)
    return fib_mem[n] = 1;
  else {
    int64_t fib1, fib2;
    if (fib_mem[n - 2] == -1) {
      fib2 = fib_mem[n - 2] = fibonacchi_number(n - 2);
    } else {
      fib2 = fib_mem[n - 2];
    }
    if (fib_mem[n - 1] == -1) {
      fib1 = fib_mem[n - 1] = fibonacchi_number(n - 1);
    } else {
      fib1 = fib_mem[n - 1];
    }

    return fib2 + fib1;
  }
}

#if !defined(TEST)
#include <stdio.h>
int32_t main(void)
{
  int32_t n;
  scanf("%d", &n);
  printf("%ld\n", fibonacchi_number(n));
  return 0;
}
#endif

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner scanner = new Scanner(System.in);
        String b = scanner.next();
        String res = "";
        for (int i = 0; i < b.length(); ++i) {
            if (b.charAt(i) == 'A') {
                res += 'T';
            } else if (b.charAt(i) == 'T') {
                res += 'A';
            } else if (b.charAt(i) == 'C') {
                res += 'G';
            } else {
                res += 'C';
            }
        }
        System.out.println(res);
    }
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

ll mod_pow(ll x, ll n, ll mod = MOD) {
	if (n == 0) return 1;
	ll res = mod_pow(x * x % mod, n / 2, mod);
	if (n & 1) res = res * x % mod;
	
	return res;
}

int N;
vector<int> g[212345];
int cnt[212345], oya[212345];

int dfs(int u, int par) {
	int res = 1;
	for (int v : g[u]) {
		if (v == par) continue;
		oya[v] = u;
		res += dfs(v, u);
	}
	return cnt[u] = res;
}

int main() {
	cin >> N;
	REP(i, N - 1) {
		int a, b;
		scanf("%d %d", &a, &b);
		--a; --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	if (N == 2) {
		cout << 0 << endl;
		return 0;
	}
	
	dfs(0, -1);
	
	ll ans = 0;
	REP(i, N) {
		ll cur = mod_pow(mod_pow(2, N, MOD), MOD - 2, MOD);
		vector<int> childs;
		if (N - cnt[i] > 0) childs.push_back(N - cnt[i]);
		for (int v : g[i]) if (v != oya[i]) {
			childs.push_back(cnt[v]);
		}
		if (childs.size() < 2) continue;
		vector<vector<ll> > dp(childs.size() + 1, vector<ll>(3, 0));
		dp[0][0] = 1;
		REP(i, childs.size()) REP(j, 3) {
			ll pat = (mod_pow(2, childs[i], MOD) - 1 + MOD) % MOD;
			if (j < 2) {
				(dp[i + 1][j + 1] += dp[i][j] * pat % MOD) %= MOD;
				(dp[i + 1][j] += dp[i][j]) %= MOD;
			}
			else (dp[i + 1][j] += dp[i][j] * (pat + 1)) %= MOD;
		}
		cur = cur * dp[childs.size()][2] % MOD;
		ans = (ans + cur) % MOD;
	}
	cout << ans << endl;
	return 0;
}


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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int N;
  cin >> N;
  cout << N/3 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define double long double
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define all(a) a.begin(),a.end()
#define sort(a) sort(all(a))
#define rsort(a) sort(all(a),greater<>())
#define debg(a) cout<<#a<<" "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef pair<int,int> P;
const long long MOD=1000000007;
clock_t time_ini = clock();
double time_diff(){
  ll time_tmp = clock();
  const double time = static_cast<double>(time_tmp - time_ini) / CLOCKS_PER_SEC * 1000.0;
  return time;
}
#define saiaku if(time_diff() > 1990)
vector <vector<ll>> dp;

void solve(long long N, long long W, std::vector<long long> w, std::vector<long long> v){
  vector <vector<ll>> dp(N+1, vector<ll>(W+1));
  for (ll i = 0; i < N; i++)
  {
    for (ll j = 0; j <= W; j++)
    {
      if (j - w[i] < 0) {
        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] << "\n";
}

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


Measured memory_bytes: 80256
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <utility>
#include <numeric>

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;

const ullong MOD = 1000000000 + 7;

struct Point
{
	double x, y;
};

void koch(int n, Point a, Point b)
{
	if (n == 0)
	{
		return;
	}

	Point s, t, u;
	double ang = M_PI * 60.0 / 180.0;

	s.x = (2.0 * a.x + b.x) / 3.0;
	s.y = (2.0 * a.y + b.y) / 3.0;
	t.x = (a.x + 2.0 * b.x) / 3.0;
	t.y = (a.y + 2.0 * b.y) / 3.0;
	u.x = (t.x - s.x) * cos(ang) - (t.y - s.y) * sin(ang) + s.x;
	u.y = (t.x - s.x) * sin(ang) + (t.y - s.y) * cos(ang) + s.y;

	koch(n - 1, a, s);
	cout << s.x << " " << s.y << endl;
	koch(n - 1, s, u);
	cout << u.x << " " << u.y << endl;
	koch(n - 1, u, t);
	cout << t.x << " " << t.y << endl;
	koch(n - 1, t, b);
}

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

	Point a, b;

	a.x = 0;
	a.y = 0;

	b.x = 100;
	b.y = 0;


	cout << fixed << setprecision(8);
	cout << a.x << " " << a.y << endl;
	koch(n, a, b);
	cout << b.x << " " << b.y << endl;
}


Measured memory_bytes: 3256
#include<bits/stdc++.h>
using namespace std;
int A[11][11];
int main() {
	int a,b,i,j,k,w,m=0,t;
	cin>>a>>b;
	for(i=1; i<=a; i++)for(j=1; j<=b; j++)cin>>A[i][j];
	for(i=1; i<a; i++)for(j=i+1; j<=a; j++) {
			w=0;
			for(k=1; k<=b; k++)w+=(A[i][k]-A[j][k])*(A[i][k]-A[j][k]);
			t=sqrt(w);
			if(t*t==w)m++;
		}
	cout<<m;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

vector<ll> prime;

ll gcd(ll a, ll b)
{
    if (b==0) return a;
    return gcd(b, a%b);
}

void setPrime(ll n)
{
    for (int i=2; i*i<=n; i++) {
        bool flag = true;
        for (int e: prime) {
            if (i%e==0) {
                flag = false;
                break;
            }
            if (e*e>i) break;
        }
        if (flag) prime.push_back(i);
    }
}

int main(){
    ll a, b;
    cin >> a >> b;
    ll c = gcd(a, b);
    ll ans = 1;
    for (ll i=2; i*i<=c; i++) {
        if (c%i) {
            continue;
        }
        ans ++;
        while (c%i==0) c /= i;
    }
    if (c!=1) ans++;
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
 
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    } 
    
  int main(){
    lint n,p;
    cin>>n>>p;
    lint a[n];
    lint count0=0;
    lint count1=0;
    rep(i,n){
        cin>>a[i];
        a[i]=a[i]%2;
        if(a[i]==0)count0++;
        else count1++;
    }
    lint ans=(long)pow(2,count1)/2;
    lint ans1=(long)pow(2,count0);
    if(p==0&&ans==0)cout<<ans1;
   else cout<<ans*ans1<<endl;
    
  }
  
     


Measured memory_bytes: 256
def resolve():
    H, W, K = map(int, input().split())
    c = []
    ans = 0
    for i in range(H):
        C = list(input())
        c.append(C)
    for p in range(2**H):
        for q in range(2**W):
            count = 0
            for h in range(H):
                for j in range(W):
                    if ((p >> h) & 1) == 0 and ((q >> j) & 1) == 0 and c[h][j] == "#":
                        count += 1
            if count == K:
                ans += 1
    print(ans)
resolve()

Measured memory_bytes: 9164
# Echo

# input
N = int(input())
S = input()

# solve
if N % 2 != 0:
    res = 'No'
else:
    if S[:len(S)//2] == S[len(S)//2:]:
        res = 'Yes'
    else:
        res = 'No'

# output
print(res)

Measured memory_bytes: 2940
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                #ランクの更新
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1


n,m = map(int,input().split())
ufpc = UnionFindPathCompression(n)
for _ in range(m):
    a,b = map(int,input().split())
    a,b=a-1,b-1
    ufpc.union(a,b)

for i in range(n):
    ufpc.find(i)
    
counter = {}
for v in ufpc.parents:
    if v in counter:
        counter[v] += 1
    else:
        counter[v] = 1

ans = 0
for key,val in counter.items():
    ans = max(ans, val)
print(ans)

        

Measured memory_bytes: 106764
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

void solve(){
  int n, m; cin >> n >> m;
  vector<int> a(n), b(m), c(m);
  map<long long, int> mp;
  for(int i = 0; i < n; i++){
    int x; cin >> x;
    mp[x]++;
  }
  for(int i = 0; i < m; i++){
    cin >> b[i] >> c[i];
  }
  for(int i = 0; i < m; i++){
    for(auto it = mp.begin(); b[i] > 0 && it != mp.end();){
      int x = it->first, y = it->second;
      //cout << x << " : " << y << endl;
      if(x >= c[i]) break;
      if(y > b[i]){
        mp[x] -= b[i];
        mp[c[i]] += b[i];
        break;
      }
      else{
        it = mp.erase(it);
        b[i] -= y;
        mp[c[i]] += y;
      }
    }
    /*for(auto it = mp.begin(); it != mp.end(); it++){
      cout << it->first << " : " << it->second << endl;
      //sum += it->first * it->second;
    }*/
  }
  long long sum = 0;
  for(auto it = mp.begin(); it != mp.end(); it++){
    //cout << it->first << " : " << it->second << endl;
    sum += it->first * it->second;
  }
  cout << sum << endl;
  return;
}

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


Measured memory_bytes: 7680
#include<iostream>
using namespace std;
int main()
{
  string s;
  int kind=0;
  int hash[150]={0};
  cin>>s; //coffee
  int len=s.length();

  
    if(s.at(2)==s.at(3)&&s.at(4)==s.at(5))
        cout<<"Yes"<<endl;
    else
          cout<<"No"<<endl;
 
  return 0;
}


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


int main()
{
	int N,M;
	cin>>N>>M;
	vector<int> A(N);
	int sum=0;
	rep(i,N)
	{
		cin>>A[i];
		sum+=A[i];
	}
	int cnt=0;
	rep(i,N)
	{
		if(A[i]>=(sum+(4*M)-1)/(4*M)) cnt++;
	}
	if(cnt>=M)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}


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

int main() {
int N, M, totalnum;
  totalnum = 0;
  N =0;
  M =0;
  cin >> N >> M;//Nは夏休み　Mは宿題の個数
  
  vector<int> homework(N);
  
  for ( int i=0; i<N; i++){
  cin >> homework.at(i);
    totalnum = totalnum + homework.at(i);
  }
  
  int day = N - totalnum;
    if (day < 0){
      cout << -1 << endl;
    }
    else{
      cout << day << endl;
    }
  
}

Measured memory_bytes: 7224
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int a, b, h;
    cin >> a >> b >> h;
    cout << (a + b) * h / 2;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
int main(){
    int i,j,k;
    scanf("%d %d %d",&i,&j,&k);
    if (i>=k && i>=j) printf("%d\n",10*i+j+k);
    else if (j>=i && j>=k) printf("%d\n",10*j+i+k);
    else printf("%d\n",10*k+i+j);
    return 0;
}

Measured memory_bytes: 1728
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>



using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
/*
 execution in cmd of windows: g++ p1.cpp -op1
  
  
  p1
 
 */
typedef double dd;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define nl <<"\n"
#define con continue
#define br break
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
ll mx=INT_MAX;
ll mi=INT_MIN;
#define mem0(a)         memset(a,0,sizeof(a))
#define mem1(a)         memset(a,-1,sizeof(a))
#define all(v) v.begin(), v.end()
#define fsort(v) sort(all(v))  
#define rsort(v) sort(v.rbegin(),v.rend())
#define rev(v) reverse(all(v))
#define maxc(v) max_element(all(v))
#define minc(v) min_element(all(v))
#define sumv(v,x) accumulate(v.begin(),v.end(),x);
const ll mod = 1000000007;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const ll MOD=1e9+7;
#define io { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define cer cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
#define cs ll t;cin>>t;while(t--)
#define cs1 ll t;t=1;while(t--)

int main()
{
   #ifndef ONLINE_JUDGE
        ifstream cin("in.in");
        ofstream cout("out.out");
    #endif
    
        io;
        //////////////////////////////////
         cs1{
             ll i,j,s=0,c,k,q=0,n,m=0,e;
             string st;
             cin>>st;
             n=st.size();
             string ans="";
             if(st[n-1]=='s') ans=st+"es";
             else ans=st+"s";
             cout<<ans nl;

        }
        //////////////////////////////////
        cer;
}


Measured memory_bytes: 3800
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
#define ALL(x) x.begin(),x.end()
#define P pair<int,int>
#define mod 1000000007

int main() {
  int n;
  string s;
  vector<int> res(4, 0);
  cin >> n;
  rep(i, n) {
    cin >> s;
    if (s == "AC") res[0]++;
    else if (s == "WA") res[1]++;
    else if (s == "TLE") res[2]++;
    else if (s == "RE") res[3]++;
  }
  cout << "AC x " << res[0] << endl;
  cout << "WA x " << res[1] << endl;
  cout << "TLE x " << res[2] << endl;
  cout << "RE x " << res[3] << endl;

  return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>
#include <algorithm>

int A, B, C, D, E, F;
int ans;

int main(void) {
	scanf("%d%d%d%d%d%d", &A, &B, &C, &D, &E, &F);
	ans = A + B + C + D + E + F;
	ans -= std::min(std::min(A, B), std::min(C, D));
	ans -= std::min(E, F);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2688
@S=map$|++,@p=@i=0..1e5;$\-=<>;sub f{my$U=pop;$p[$U]=$U-$p[$U]?f($p[$U]):$U}/ />${*a=-$'}||($S[$p[$v=f$`]=f$a]+=$v-(f$a)&&$S[$v]),$a=$`for<>;$\+=$S[f${-$_}]for@i;print

Measured memory_bytes: 61184
#include <iostream>

using namespace std;

int main()
{
	int W, H, x, y, r;
	
	cin >> W >> H >> x >> y >> r;
	if (r <= x && x <= W-r && r <= y && y <= H-r) cout << "Yes\n";
	else cout << "No\n";
	
	return 0;
}

Measured memory_bytes: 1128
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define reps(i, m, n) for (int i = m; i < n; i++)
#define repr(i, m, n) for (int i = m; i >= n; i--)
#define db(x) cout << #x << "=" << x << endl;
template <class T>
bool maxi(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool mini(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
#define INF2 1000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 998244353
#define EPS 1e(-9);
using namespace std;
typedef long long ll;
//--GLOBAL---------------------------------
const int MAX = 10000010;
ll fac[MAX], finv[MAX], inv[MAX];
void cinit() { // O(nlogn)
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  reps(i, 2, MAX){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
ll c(int n, int k){ // 二項係数計算
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll modpow(ll a, ll n, ll mod=MOD){ // a^n % MOD の計算
  ll res = 1;
  while (n > 0){
      if(n & 1) res = res * a % mod;
      a = a * a  % mod;
      n >>= 1;
  }
  return res;
}

//--MAIN-----------------------------------
void Main() {

    ll N; cin>>N;
    cinit();

    ll res=modpow(3LL,N);

    ll hu=1;

    for(ll i=N;i>N/2;i--){
        res-=2*hu*c(N,i);

        res=res+(2LL*MOD*MOD);
        res%=MOD;
        hu*=2;
        hu%=MOD;
    }

    cout<< res<<"\n";


}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 234624
import java.util.Scanner;

public class Main {

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

		String c = sc.next();
		String ans = "";

		if ( c.equals("a") || c.equals("i") || c.equals("u") || c.equals("e") || c.equals("o")) {
			ans = "vowel";
		} else {
			ans = "consonant";
		}

		System.out.println( ans );
	}
}

Measured memory_bytes: 21972
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>

using namespace std;
const int INF = 1e9;

int main()
{
    int N, T, c, t, minc = INF;
    cin >> N >> T;
    for (int i = 0; i < N; ++i)
    {
        cin >> c >> t;
        if (t <= T)
        {
            minc = min(minc, c);
        }
    }
    if (minc == INF)
    {
        cout << "TLE" << endl;
    }
    else
    {
        cout << minc << endl;
    }

    return 0;
}


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

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

  switch (N % 10)
  {
  case 2:
  case 4:
  case 5:
  case 7:
  case 9:
    cout << "hon" << endl;
    break;  
  case 0:
  case 1:
  case 6:
  case 8:
    cout << "pon" << endl;
    break;
  default:
    cout << "bon" << endl;;
    break;
  }
  return 0;
}


Measured memory_bytes: 3636
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return ret


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()

    # 愚直に行うとO(N^2)となる
    # 各要素、約数を列挙(sqrt(N))
    # 約数がこれまでに存在したかをチェックO(1)*約数の個数
    # 存在すれば1を加える

    # print(A)
    ans = 0
    history = [False]*N
    for i in range(N):
        if history[i]:
            continue
        # A[i]を乗じていくとどうか
        k = i
        for j in range(2, A[-1]//A[i] + 1):
            k = bisect_left(A, A[i]*j, lo=k)
            # print(A[i], A[i]*j, k, A[k])
            if A[k] % A[i] == 0:
                history[k] = True
        #
        k = bisect_left(A, A[i])
        if k < i:
            history[i] = True
        if i+1 < N and A[i] == A[i+1]:
            history[i] = True
    print(N-sum(history))

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 92156
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double 
#define MOD 1000000007ll 
#define pb push_back
#define vl vector<ll>
#define pll pair<ll,ll>
#define mp make_pair
using namespace std;
#define pi (long double)3.14159265358979323846 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
}
ll lcm(ll a,ll b)
{
    return a*b/gcd(a,b);
}
ll power(ll a,ll p,ll m)
{
    ll re=1;
    re%=m;
    for(;p;p>>=1){
        if(p&1) re=re*a%m;
        a=a*a%m;
    }
    return re;
}
int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll p1 = a*c;
    ll p2 = a*d;
    ll q1 = b*c;
    ll q2 = b*d;
    cout<<max(max(p1,p2),max(q1,q2))<<endl;
}   

Measured memory_bytes: 3632
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]

from bisect import bisect_left


ans = 0

for k in range(29):
    a0 = []
    a1 = []
    a0a = a0.append
    a1a = a1.append
    
    b0 = []
    b1 = []
    b0a = b0.append
    b1a = b1.append
    for i in a: #基数ソート
        if i&(1<<k): a1a(i)
        else: a0a(i)
    for i in b: #基数ソート
        if i&(1<<k): b1a(i)
        else: b0a(i)
    
    a = a0+a1
    b = b0+b1
    mask = (1<<(k+1))-1
    
    aa = [i&mask for i in a]
    bb = [i&mask for i in b]
    
    res = 0
    p1 = 1<<k
    p2 = mask+1
    p3 = p1+p2

    j1=j2=j3=0    
    for ai in reversed(aa):
        while j1 < n and ai+bb[j1] < p1:
            j1 += 1
        while j2 < n and ai+bb[j2] < p2:
            j2 += 1
        while j3 < n and ai+bb[j3] < p3:
            j3 += 1
        res += j2-j1+n-j3
        #if k < 3: print(ai,p2,res,bb,j1,j2,j3,n)
        #print(bb,p2,ai,j1,j2,j3,n,"R",res)    
    ans |= (res&1)<<k
    



print(ans)    









Measured memory_bytes: 144408
import java.util.Scanner;

public class Main {

    private static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {
	String c = scan.next();

	String ans;
	switch(c.charAt(0)) {
	    case 'a':
	    case 'i':
	    case 'u':
	    case 'e':
	    case 'o':
		ans = "vowel";
		break;
	    default:
		ans = "consonant";
		break;
	}
		
	System.out.println(ans);
	scan.close();
    }
}


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

#define repfrom(i, from, n) for (ll i = (from); i < (n); i++)
#define rep(i, n) repfrom(i, 0, n)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)

using namespace std;

using ll = long long;
using p  = pair<ll, ll>;
constexpr ll INF = 1LL << 62;

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string S;
    cin >> S;
    
    ll N = ll(S.size());
    ll ans = N;
    rep(i, N - 1) {
        if (S[i] != S[i + 1]) {
            ans = min(ans, max(i + 1, N - (i + 1)));
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */

int main() {
    string s, t;
    cin >> s >> t;
    int ans = 0;
    rep(i, s.size()) {
        if(s[i] !=  t[i]) ans++;
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 3824
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>

using namespace std;
const int MX=200011;
int n,p[MX];
int v[MX],nv[MX],inr[MX];
vector<int>G[MX];
typedef vector<int>::iterator vit;

void calv(int k){
	if(~v[k])return;
	for(vit i=G[k].begin();i!=G[k].end();i++)if(!inr[*i])calv(*i);
	static int t[MX]={0};
	for(vit i=G[k].begin();i!=G[k].end();i++)if(!inr[*i])++t[v[*i]];
	int I;
	for(I=0;I<n;I++)if(!t[I]){v[k]=I;break;}
	for(I++;I<n;I++)if(!t[I]){nv[k]=I;break;}
	for(vit i=G[k].begin();i!=G[k].end();i++)if(!inr[*i])--t[v[*i]];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]),G[p[i]].push_back(i);
	
	int x=1,y=1;
	do x=p[x],y=p[p[y]];
	while(x!=y);
	for(;!inr[x];inr[x]=1,x=p[x]);
	
	memset(v+1,-1,sizeof(int)*n);
	for(int i=1;i<=n;i++)calv(i);
	
	static int t[MX];
	memset(t+1,-1,sizeof(int)*n);
	t[p[x]]=v[p[x]];
	for(y=p[x];y!=x;y=p[y])t[p[y]]=(t[y]==v[p[y]]?nv[p[y]]:v[p[y]]);
	if(t[p[x]]==(t[x]==v[p[x]]?nv[p[x]]:v[p[x]]))return puts("POSSIBLE"),0;
	
	memset(t+1,-1,sizeof(int)*n);
	t[p[x]]=nv[p[x]];
	for(y=p[x];y!=x;y=p[y])t[p[y]]=(t[y]==v[p[y]]?nv[p[y]]:v[p[y]]);
	if(t[p[x]]==(t[x]==v[p[x]]?nv[p[x]]:v[p[x]]))return puts("POSSIBLE"),0;
	
	puts("IMPOSSIBLE");
	return 0;
}


Measured memory_bytes: 14080
#include<stdio.h>

int main( ){

  int x,y,a,b,c;
scanf("%d %d %d",&a,&b,&c);
 y=0;
for (x=a;x<=b;x++){
  if(c%x==0){y++;}
}
 printf("%d\n",y);
return 0;
}

Measured memory_bytes: 596
n, m = map(int, input().split())
py = [[i] + list(map(int, input().split())) for i in range(m)]
py.sort(key=lambda x:(x[1], x[2]))

city = py[0][1]
num = 0

for i in py:
    if i[1] == city:
        num += 1
    else:
        num = 1
        city = i[1]
    i.append(num)

py.sort()

for i in py:
    print('{:06}{:06}'.format(i[1], i[3]))

Measured memory_bytes: 36096
import sys
sys.setrecursionlimit(10**6)
N, A, B = map(int, input().split())
h = []
for _ in range(N):
    h.append(int(input()))


def check(m):
    cnt = 0
    for i in range(N):
        cnt += max(-(-(h[i]-m*B)//(A-B)), 0)
    return cnt <= m


def binary_search(l, r):
    c = (l+r)//2
    if r-l == 1:
        return l if check(c) else r

    if check(c):
        return binary_search(l, c)
    else:
        return binary_search(c, r)

print(binary_search(0, 10**9+1))


Measured memory_bytes: 49880
#include <iostream>
#include <sstream>

int main()
{
    int N;
    int P[10];
    std::cin >> N;
    int max=0;
    int sum=0;
    for(int i=0; i<N; i++){
        std::cin >>P[i];
        if(max <=P[i]){
            max=P[i];
        }
    }
    for(int i=0; i<N; i++){
        sum+=P[i];
    }
    sum-=(max/2);
    std::cout << sum << std::endl;
    return 0;
}

Measured memory_bytes: 256