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

#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

// 400012- 128


void oneCase() {
    int n,z, w;
    cin >> n >> z >> w;
    vector<int> a(n);

    for (auto& el : a) {
        cin >> el;
    }
    if (n == 1) {
        cout << abs(a[0] - w) << "\n";
        return;
    }
    cout << max(abs(a.back() - w), abs(a[n - 1] - a[n - 2])) << "\n";
}

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

    int t = 1;
//    cin >> t;
    while (t--) {
       oneCase();
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(e) e.begin(), e.end()
#define RALL(e) e.rbegin(), e.rend()
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define dbg(x) (cerr << #x << ":" << x << endl)
#define mid (l + r) / 2
#define pii pair <int, int>
#define fi first
#define sc second
#define N 1000000009

using namespace std;

typedef long long int lli;

int main(){
	ios::sync_with_stdio(0);
	string s;
	cin >> s;
	int res = 0;
	for(int i=0; i<s.size(); i++){
		res += (s[i] == '+' ? 1 : -1);
	}
	cout << res;
	return 0;
}

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

struct Card {
	char mark;
	int value;
};
Card c[110];
Card c1[110];
Card c2[110];

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

	int n;
	cin >> n;

	for(int i = 0; i < n; ++i){
		cin >> c[i].mark >> c[i].value;
		c1[i].mark = c[i].mark;
		c2[i].mark = c[i].mark;
		c1[i].value = c[i].value;
		c2[i].value = c[i].value;
	}

	for(int i = 0; i < n; ++i){
		for(int j = n - 1; j >= 0; --j){
			if(c1[j].value < c1[j - 1].value){
				swap(c1[j].value, c1[j - 1].value);
				swap(c1[j].mark, c1[j - 1].mark);
			}
		}
	}

	for(int i = 0; i < n; ++i){
		cout << c1[i].mark << c1[i].value;
		if(i != n - 1)
			cout << " ";
		else
			cout << endl;
	}
	cout << "Stable" << endl;

	for(int i = 0; i < n; ++i){
		int minj = i;
		for(int j = i; j < n; ++j){
			if(c2[j].value < c2[minj].value){
				minj = j;
			}
		}
		swap(c2[minj].value, c2[i].value);
		swap(c2[minj].mark, c2[i].mark);
	}

	for(int i = 0; i < n; ++i){
		cout << c2[i].mark << c2[i].value;
		if(i != n - 1)
			cout << " ";
		else
			cout << endl;
	}

	bool flag = true;
	for(int i = 0; i < n; ++i){
		if(c1[i].mark != c2[i].mark){
			flag = false;
			break;
		}
	}
	cout << (flag ? "Stable" : "Not stable") << endl;

	return 0;
}

Measured memory_bytes: 1200
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

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

inline void setin(string s) {
	freopen(s.c_str(), "r", stdin);
}

inline void setout(string s) {
	freopen(s.c_str(), "w", stdout);
}

template <typename T> inline T range(T l, T r) {
	return uniform_int_distribution <T>(l, r)(rng);
}

template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

#define int long long

const int inf = 2e9;
const int mod = 1e9 + 7;
const int N = 1e5 + 15;
int n;
pii a[N];
multiset <pii> l, r;

inline bool lie(int l, int x, int r) {
	return l <= x && x <= r;
}

inline int d(int x, int y) {
	return abs(x - y);
}

main() {
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	// setin("input.txt");
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i].f >> a[i].se;
		l.insert({a[i].f, i});
		r.insert({a[i].se, i});
	}
	l.insert({0, 0});
	r.insert({0, 0});
	int ans = 0, cur = 0, pos = 0;
	for(int i = 1, j; i <= n/2 + 1; ++i) {
			j = l.rbegin()->se;
			cur += a[j].f;
			l.erase({a[j].f, j});

			j = r.begin()->se;
			cur -= a[j].se;
			r.erase({a[j].se, j});

		Max(ans, cur);
	}
	cout << 2 * ans << endl;
	return 0;
}


Measured memory_bytes: 14336
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M; cin >> N >> M;
  map<ll, ll> mp;
  ll A[200100]; 
  rep(i, N) {
    cin >> A[i];
    mp[A[i]] ++;
  }
  ll C[200100];
  Rep(i, N, N + M) {
      cin >> C[i] >> A[i];
      mp[A[i]] += C[i];
  }
  sort(A, A + (N + M));
  reverse(A, A + (N + M));
  int cnt = N; ll ans = 0; int j = 0;
  while(cnt > 0) {
      if(mp[A[j]] > 0) {
          ans += A[j];
          cnt --;
          mp[A[j]] --;
          continue;
      } else {
         j ++;
      }
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
  int m;
  cin>>m;
  ll n=0,s=0;
  rep(i,m){
    ll d,c; cin>>d>>c;
    s+=d*c; n+=c;
  }
  cout<<n-1+(s-1)/9<<endl;
}

Measured memory_bytes: 3580
/* *****fireice**** */

#include<bits/stdc++.h>

#define ll long long int
#define ld long double
#define vi vector<int>
#define vc vector<char>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define el '\n'
#define N 1000000007
#define re return
#define F first
#define S second
#define L length
#define mp make_pair
#define PI 3.14159265
#define all(a) (a).begin(),(a).end()
#define forup(i,n) for(int i=0;i<n;i++)
#define forf(i,x,n) for(int i=x;i<n;i++)
#define ford(i,n) for(int (i)=(n)-1;i>=0;(i)--)
#define take(a,n) forup(i,n) cin>>a[i];
using namespace std;

int gcdExtended(int a, int b, int *x, int *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }

    int x1, y1; // To store results of recursive call
    int gcd = gcdExtended(b%a, a, &x1, &y1);

    // Update x and y using results of recursive
    // call
    *x = y1 - (b/a) * x1;
    *y = x1;

    return gcd;
}

ll modInverse(int a, int m)
{
    int x, y;
    int g = gcdExtended(a, m, &x, &y);
        // m is added to handle negative x
    ll res = ((ll)x%m + (ll)m) % m;

    return res;
}

ll poww(ll x,ll n)
{
    if(n==0)
        return 1;
    else if(n==1) return x;
    else if(n%2 == 0)        //n is even
        return poww(x*x,n/2);
    else                              //n is odd
        return x*poww(x*x,(n-1)/2);
}

ll modularExponentiation(ll x,ll n,ll M)
{
    ll result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}

template<typename T>
T maxx(T a,T b)
{
  if(a<b) re b;
  re b;
}
template<typename T, typename... Args>
T maxx(T a,T b, Args... args)
{
    re(maxx(maxx(a,b),args...));
}

template<typename T>
T minn(T a,T b)
{
  if(a<b) re a;
  re b;
}
template<typename T, typename... Args>
T minn(T a,T b, Args... args)
{
    re(minn(minn(a,b),args...));
}

int gcd(int a, int b)
{
    if (a == 0)
       return b;
    if (b == 0)
       return a;

    if (a == b)
        return a;

    if (a > b)
        return gcd(a-b, b);
    else return gcd(a, b-a);
}

ll ncr(int n,int r)
{
  ll ans=1;
  r=min(r,n-r);
  forup(i,r)
  {
    ans=(ans*(n-i)/(i+1))%N;
  }
  re ans;
}
ll su(ll n, ll z)
{
  ll k=n%z;
  k=n-k;
  ll ans=((k/z)*(2*z+((k/z-1)*z)))/2;
  re ans;
}

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

  int t=1;
  //cin>>t;
  while(t--)
  {
    ll n,m,k,z;
    cin>>n;
    m=(n*(n+1))/2;
    if(n>2){
    m-=su(n,3);}
    if(n>4){
    m-=su(n,5);}
    if(n>=15){m+=su(n,15);}

    cout<<m<<el;

  }


  return 0;
}


Measured memory_bytes: 3696
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef long long int ll;
void swap(ll *x,ll *y){ll temp;temp=*x;*x=*y;*y=temp;}
ll asc(const void *a,const void *b){return *(ll*)a-*(ll*)b;}
ll desc(const void *a,const void *b){return *(ll*)b-*(ll*)a;}
ll max(ll x,ll y){return x>y?x:y;}
ll min(ll x,ll y){return x>y?y:x;}

int main(){
    ll l,r;

    scanf("%lld %lld",&l,&r);

    ll l2;
    ll r2;
    if(l<2019){
        l2=l;
    }else{
        l2=2019+l%2019;
    }

    if(r<2019){
        r2=r;
    }else{
        r2=2019+r%2019;
    }
    ll x=r/2019;
    if(l<=2019*x&&2019*x<=r){
        printf("0\n");
        return 0;
    }

    //printf("l2:%lld r2:%lld\n",l2,r2);
    ll min=5000;
    for(ll i=l2;i<=r2-1;i++){
        for(ll j=i+1;j<=r2;j++){
            //printf("i:%lld j:%lld\n",i,j);
            if((i*j)%2019<min){
                min=(i*j)%2019;
                
                /*if(min==2){
                    printf("i:%lld j:%lld\n",i,j);
                }*/
            }
        }
    }

    if(l2==r2)min=l2*(l2+1)%2019;
    

    printf("%lld\n",min);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#define INF 1e9
#define MOD 1000000007
#define MAX_N 100001
#define mod(x) ((x % MOD) + MOD) % MOD

using namespace std;

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

struct edge { int from, to; };
vector<edge> G[MAX_N];
int value[MAX_N];
bool used[MAX_N];
vector<int> idx_list;
vector<int> value_list;

void dfs(int i) {
    used[i] = true;
    idx_list.push_back(i);
    value_list.push_back(value[i]);
    
    for (int j = 0; j < G[i].size(); j++) {
        edge e = G[i][j];
        if (!used[e.to]) {
            dfs(e.to);
        }
    }
}




int main() {
    int N, M;
    cin >> N >> M;
    
    for (int i = 1; i <= N; ++i) {
        cin >> value[i];
    }
    for (int i = 1; i <= M; ++i) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(edge{x, y});
        G[y].push_back(edge{y, x});
    }
    
    int ans = 0;
    
    fill(used, used + MAX_N, false);
    for (int i = 1; i <= N; ++i) {
        idx_list.clear();
        value_list.clear();
        if (!used[i]) {
            dfs(i);
            sort(idx_list.begin(), idx_list.end());
            sort(value_list.begin(), value_list.end());
        
            vector<int> list_inter;
            set_intersection(idx_list.begin(), idx_list.end(), value_list.begin(), value_list.end(), back_inserter(list_inter));
            ans += (int)list_inter.size();
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 9764
import sys
def input(): return sys.stdin.readline().rstrip()
from math import gcd

K = int(input())

one = 0
two = 0
three = 0
for i in range(1,K-1):
    for j in range(i+1,K):
        for k in range(j+1,K+1):
            d = gcd(i,j)
            d = gcd(d,k)
            three += d

for i in range(1,K):
    for j in range(i+1,K+1):
        d = gcd(i,j)
        two += d
for i in range(1,K+1):
    one += i

ans = one + two * 6 + three * 6
print(ans)

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

using ll = long long;
using P = pair<ll, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  int N, M;
  cin >> N >> M;
  ll x[N][3];
  for (int i = 0; i < N; i++) for (int j = 0; j < 3; j++) {
    cin >> x[i][j];
  }

  ll ans = 0;
  for (int i = 0; i < 8; i++) {
    ll xx[N][3];
    for (int j = 0; j < 3; j++) {
      if ((i >> j) & 1) {
        for (int k = 0; k < N; k++) xx[k][j] = -x[k][j];
      } else {
        for (int k = 0; k < N; k++) xx[k][j] = x[k][j];
      }
    }
    vector<ll> v;
    for (int j = 0; j < N; j++) {
      v.push_back(xx[j][0] + xx[j][1] + xx[j][2]);
    }
    sort(v.begin(), v.end());

    ll sum = 0;
    for (int j = N - 1; j >= N - M; j--) sum += v[j];

    ans = max(ans, sum);
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
import numpy as np

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


# >>> binary indexed tree >>>
# 必要な要素数+1 の長さの ndarray の 1 要素目以降を使う
def bitify(arr):
    for i in range(1, len(arr)-1):
        arr[i + (i & -i)] += arr[i]
def bit_sum(bit, i):  # [bit_sum, "i8(i8[:],i8)"],
    # (0, i]
    res = 0
    while i:
        res += bit[i]
        i -= i & -i
    return res
def bit_add(bit, i, val):  # [bit_add, "void(i8[:],i8,i8)"],
    n = len(bit)
    while i < n:
        bit[i] += val
        i += i & -i
# <<< binary indexed tree <<<

numba_compile([
    [bitify, "void(i8[:])"],
    [bit_sum, "i8(i8[:],i8)"],
    [bit_add, "void(i8[:],i8,i8)"],
])


def main():
    N = int(sys.stdin.buffer.readline())
    S = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.uint8).astype(np.int64) - 97
    Q = int(sys.stdin.buffer.readline())
    bits = np.zeros((26, (1<<19)+1), dtype=np.int64)
    bits[S, np.arange(1, N+1)] = 1
    for i in range(26):
        bitify(bits[i])
    Ans = []
    for t, i, c in zip(*[iter(sys.stdin.buffer.read().split())]*3):
        if t == b"1":
            i = int(i)
            c = ord(c)-97
            c_old = S[i-1]
            S[i-1] = c
            bit_add(bits[c_old], i, -1)
            bit_add(bits[c], i, 1)
        else:
            l, r = int(i), int(c)
            ans = 0
            for bit in bits:
                ans += bool(bit_sum(bit, r)-bit_sum(bit, l-1))
            Ans.append(ans)
    print("\n".join(map(str, Ans)))

main()


Measured memory_bytes: 140732
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vs = vector<string>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vvp = vector<vector<pair<int,int>>>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}




int main(){
    int N,M;
    cin >> N >> M;
    
    vi A(N);
    in(N,A);
    int S = 0;
    rep(i,N) S += A[i];
    sort(all(A));
    reverse(all(A));
    bool ans = true;
    rep(i,M) if(S > A[i]*4*M) ans = false;
    if(ans) cyes;
    else cno;
    
    
    

    
    
    
    

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <iomanip>
#include <typeinfo>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <set>
#include <numeric>
using namespace std;


typedef long long       ll;
typedef struct edge_ { ll to; ll cost; } edge;
typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef vector<double>  vd;
typedef vector<bool>    vb;
typedef vector<string>  vs;
typedef vector<char>    vc;
typedef vector<edge>    ve;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;
typedef vector<vll>		vvll;
typedef vector<vi>		vvi;
typedef vector<ve>      vve;
typedef vector<vc>		vvc;

#define repr(itr, bgn, end) for (ll itr = (ll)bgn; itr < (ll)end; ++itr)
#define rep(itr, end) repr(itr, 0, end)
#define reprrev(itr, bgn, end) for (ll itr = (ll)end - 1; itr >= (ll)bgn; --i)
#define reprev(itr, end) reprrev(itr, 0, end)
#define all(container) container.begin(), container.end()
#define sortall(container) sort(all(container))
#define yn(cond) cond ? (cout << "Yes" << endl) : (cout << "No" << endl)
#define YN(cond) cond ? (cout << "YES" << endl) : (cout << "NO" << endl)

// 定数
#define LLONG_MAX numeric_limits<ll>::max()
#define INT_MAX numeric_limits<int>::max()
constexpr double PI = 3.14159265358979323846;
constexpr ll INF = 1 << 15;
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-7;

// よく使うもの
constexpr int dy[4] = { 0, 1, 0, -1 };
constexpr int dx[4] = { 1, 0, -1, 0 };


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}

// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
	for (T& x : vec) os << x << " ";
	return os;
}



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

	int c = 0;
	for (int i = 1; i <= 100; i += 2) {
		if (i <= N)
			c++;
	}

	YN(c >= K);

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

const int mod=1e9+7;
const int sz=200005;

int fact[sz],inv[sz],ifact[sz];

void make(){
    fact[0]=fact[1]=inv[1]=ifact[0]=ifact[1]=1;
    for(int i=2;i<sz;i++){
	fact[i]=fact[i-1]*i%mod;
	inv[i]=inv[mod%i]*(mod-mod/i)%mod;
	ifact[i]=ifact[i-1]*inv[i]%mod;
    }
}

int comb(int n,int k){
    if(n<k) return 0;
    return fact[n]*ifact[k]%mod*ifact[n-k]%mod;
}

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

void add(int &a,int b)
{
    a=(a+b)%mod;
}

signed main()
{
    make();
    int N,A,B,C; cin>>N>>A>>B>>C;

    int ans=0;
    for(int i=N;i<2*N;i++){
	int tmp1=i*comb(i-1,N-1)%mod*mod_pow(A,N)%mod*mod_pow(B,i-N)%mod;
	tmp1=tmp1*mod_pow(inv[A+B],i)%mod;
	int tmp2=i*comb(i-1,N-1)%mod*mod_pow(B,N)%mod*mod_pow(A,i-N)%mod;
	tmp2=tmp2*mod_pow(inv[A+B],i)%mod;
	add(ans,tmp1+tmp2);
    }
    ans=ans*100%mod*inv[100-C]%mod;
    cout<<ans<<endl;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define all(X) X.begin(),X.end()

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   str.substr (x) : returns a substring str[x],... end of string
   str.find(qtr) : returns the first occurenece of qtr in str.
   builtin functions :
   __builtin_popcount(n) : no. of set bits in n.
   __builtin_parity(n) : parity of no. of set bits
   __builtin_clz(n) : no. of leading zeros before 1
   __builtin_ctz(n) : no of zeros from last to first occurrence of 1
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

ll binlen(ll a)
{
	ll v = 0;
	for(ll i=0;i<61;++i)
	{
		v += (1ll<<i);
		if(a<=v) return i;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll k,n;
	string str;
	cin >> k;
	cin >> str;
	n = str.size();
	if(n <= k)
		cout << str << endl;
	else
		cout << str.substr(0,k) << "..." << endl;
}

Measured memory_bytes: 3644
import java.util.*;

public class Main {
	public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
		int k = sc.nextInt();
		int MAX = 200001;
		int[] a = new int[MAX];
		Set<Integer> set = new HashSet<Integer>();

		for (int i = 0; i < n; i++) {
			int ai = sc.nextInt();
			a[ai]++;
			set.add(ai);
		}

		Arrays.sort(a);

		int cnt = 0;
		int setSize = set.size();
		for (int i = MAX - setSize; i < MAX - k; i++) {
			cnt += a[i];
		}

		System.out.println(cnt);
	}
}


Measured memory_bytes: 101744
N=int(input())
a=[int(input()) for i in range(N)]

num=1
cnt=1
for i in range(N):
  if a[num-1]==2:
    print(cnt)
    break
  else:
    cnt+=1
    num=a[num-1]
    #print(cnt,num,a[num-1])
else:
  print(-1)

Measured memory_bytes: 7084
#include <bits/stdc++.h>
// #include <cstdlib>  // abs() for integer
// #include <algorithm>  // std::sort, std::unique
using namespace std;

int main() {

  int N;
  cin >> N;
  int count = 0;

  vector<int> vec(N);

  for (int i = 0; i < N; i++) {
    cin >> vec.at(i) ;
  }

  // sort(vec.begin(),vec.end());
  // vec.erase(unique(vec.begin(),vec.end()),vec.end());
  // N = vec.size();

  int a,b,c;

  for(int i = 0;i<N;i++){
    for(int j = i+1; j < N;j ++){
      for(int k = j+1;k < N;k++){
        a = vec.at(i);
        b = vec.at(j);
        c = vec.at(k);
        if(a == b || b == c || c == a){
          continue;
        }

        if(abs(a-b) < c && c < a+b){
          count++;
        }
      }
    }
  }


  cout << count << endl;
}


Measured memory_bytes: 3592
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    counter = Counter(S)
    ans = counter['R'] * counter['G'] * counter['B']

    for i in range(N):
        for j in range(i + 1, (N + i + 1) // 2):
            if 2 * j - i >= N:
                break
            if S[i] != S[j] and S[i] != S[2 * j - i] and S[j] != S[2 * j - i]:
                ans -= 1

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 74140
#include <bits/stdc++.h>
#define INF 1e9
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()

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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

void solve() {
    int N,A,B,C,D;
    cin >> N >> A >> B >> C >> D;
    string s;
    cin >> s;
    int len = 0;
    FOR(i,A-1,C) {
        if (s[i] == '#') len++;
        else len = 0;
        if (len == 2) {
            cout << "No" << endl;
            exit(0);
        }
    }

    len = 0;
    FOR(i,B-1,D+1) {
        if (s[i] == '#') len++;
        else len = 0;
        if (len == 2) {
            cout << "No" << endl;
            exit(0);
        }
    }

    if (C>D) {
        len = 0;
        FOR(i,B-2,D+1) {
            if (s[i] == '.') len++;
            else len = 0;
            if (len == 3) {
                cout << "Yes" << endl;
                exit(0);
            }
        }
        cout << "No" << endl;
        exit(0);
    }

    cout << "Yes" << endl;

}

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


Measured memory_bytes: 640
//yashverma

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

#define rep(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define pb push_back
#define Pi 3.141592653589793
#define MOD 1000000007
// For i/o
#define sd1(a) scanf("%d",&a)
#define sd2(a,b) scanf("%d %d",&a,&b)
#define sd3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sf scanf
#define pf printf
// For debugging
#define deb(a) printf("deb%d\n",a)

typedef pair<int,int> ii;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(false);
	int n;cin >> n;
	int p, p2 = 0, p4 = 0, po = 0;
	rep(i,0,n)
	{
		cin >> p;
		if(p%4 == 0)p4 += 1;
		else if(p%2 == 0)p2 += 1;
		else po += 1;
	}
	p2 = p2%2;
	po += p2;
	if(p4+1 >= po)
		cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
#define ll long long
#define re register
using namespace std;
inline int gi()
{
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9' && ch>='0'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=233333;
int front[N],nxt[N<<1],to[N<<1],w[N<<1],W[N],n,m,cnt;
int siz[N],g[N],root,sum,vis[N];
struct node
{
	int u,v;ll w;
	bool operator<(const node&b)const
		{
			return w<b.w;
		}
}e[N*50];
ll Min;
int p;
void Add(int u,int v,int val)
{
	to[++cnt]=v;nxt[cnt]=front[u];front[u]=cnt;
	w[cnt]=val;
}
void getroot(int u,int fa)
{
	siz[u]=1;g[u]=0;
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa || vis[v])continue;
		getroot(v,u);
		siz[u]+=siz[v];
		g[u]=max(g[u],siz[v]);
	}
	g[u]=max(g[u],sum-siz[u]);
	if(g[u]<g[root])root=u;
}
void dfs(int u,int fa,ll dep)
{
	if(Min>W[u]+dep){Min=W[u]+dep;p=u;}
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa || vis[v])continue;
		dfs(v,u,dep+w[i]);
	}
}
void Link(int u,int fa,ll dep)
{
	e[++m]=(node){u,p,dep+Min+W[u]};
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa || vis[v])continue;
		Link(v,u,dep+w[i]);
	}
}
void solve(int u)
{
	vis[u]=1;
	Min=1e18+10;p=0;
	dfs(u,0,0);Link(u,0,0);
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(vis[v])continue;
		sum=siz[v];root=0;
		getroot(v,u);
		solve(root);
	}
}
int f[N];
int find(int x)
{
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
int main()
{
	n=gi();
	for(int i=1;i<=n;i++)W[i]=gi();
	for(int i=1;i<n;i++)
	{
		int u=gi(),v=gi(),val=gi();
		Add(u,v,val);Add(v,u,val);
	}
	g[0]=n+1;sum=n;
	getroot(1,0);
	solve(root);
	sort(e+1,e+m+1);
	for(int i=1;i<=n;i++)f[i]=i;
	ll ans=0;int k=0;
	for(int i=1;i<=m;i++)
	{
		int u=find(e[i].u),v=find(e[i].v);
		if(u!=v)
		{
			ans+=e[i].w;
			k++;f[v]=u;
			if(k==n-1)break;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 73600
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include<string>
#include<queue>
 
using namespace std;
 
int dist[2003][2003];
int sum[2003][2003];
int H, W;
 
int vx[]{ 1,0,-1,0 };
int vy[]{ 0,1,0,-1 };
 
bool inside(int y, int x)
{
	return y >= 0 && x >= 0 && y < H && x < W;
}
 
vector<string> board;
 
int main() {
	int Q;
	cin >> H >> W >> Q;
	board = vector<string>(H);
	for (int i = 0; i < H; i++)
	{
		cin >> board[i];
	}
	int MAX = 99999999;
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			dist[i][j] = MAX;
		}
	}
 
 
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			if (board[i][j] == '1')
			{
				if (dist[i][j] != MAX) continue;
				sum[i + 1][j + 1]++;
 
				queue<pair<int, int>> q;
				dist[i][j] = 0;
				q.push(make_pair(i, j));
				while (!q.empty())
				{
					pair<int, int> now = q.front(); q.pop();
					int y = now.first;
					int x = now.second;
					for (int k = 0; k < 4; k++)
					{
						int ny = y + vy[k];
						int nx = x + vx[k];
						if (!inside(ny, nx)) continue;
						if (board[ny][nx] == '0') continue;
						if (dist[ny][nx] != MAX) continue;
 
						//ここに更新処理を挿入
						dist[ny][nx] = dist[y][x] + 1;
 
						q.push(make_pair(ny, nx));
					}
				}
			}
		}
	}
 
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			sum[i + 1][j + 1] += sum[i + 1][j] + sum[i][j + 1] - sum[i][j];
		}
	}
 
	for (int t = 0; t < Q; t++)
	{
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
		y1--; x1--;
 
		long ans = 0;
		ans += sum[y2][x2] - sum[y1][x2] - sum[y2][x1] + sum[y1][x1];
 
		if (x1 != 0)
		{
			for (int y = y1; y < y2; y++)
			{
				if (dist[y][x1] - 1 == dist[y][x1 - 1]) ans++;
			}
		}
		if (x2 != W)
		{
			for (int y = y1; y < y2; y++)
			{
				if (dist[y][x2 - 1] - 1 == dist[y][x2]) ans++;
			}
		}
 
 
		if (y1 != 0)
		{
			for (int x = x1; x < x2; x++)
			{
				if (dist[y1][x] - 1 == dist[y1 - 1][x]) ans++;
			}
		}
		if (y2 != H)
		{
			for (int x = x1; x < x2; x++)
			{
				if (dist[y2 - 1][x] - 1 == dist[y2][x]) ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

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

using namespace std;

int main()
{
  string s;
  cin >> s;
  char a,b,c,d;

  a=s.at(0);
  b=s.at(1);
  c=s.at(2);
  d=s.at(3);
  
  int flag=0;
  if(a==b&&a==c&&a==d){
    flag=0;
  }
  else if(a==b){
    if(c==d){
      flag=1;
    }
  }
  else if(a==c){
    if(b==d){
      flag=1;
    }
  }
  else if(a==d){
    if(b==c){
      flag=1;
    }
  }
  else{
    flag=0;
  }
  
  if(flag==1){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        if(n <= k) {
            System.out.println(n * x);
        } else {
            System.out.println((k * x) + ((n - k) * y));
        }
    }
}

Measured memory_bytes: 35708
#include <algorithm>
#include <vector>
#include <cfloat>
#include <string>
#include <cmath>
#include <set>
#include <cstdlib>
#include <map>
#include <ctime>
#include <iomanip>
#include <functional>
#include <deque>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <stack>
#include <climits>
#include <sys/time.h>
#include <cctype>

using namespace std;

int main(){
        
  int w,d;

  int front[10],side[10];
  int art[10][10];
  bool fuse[10],suse[10];
  int ans=0;


  while(true){
    ans = 0;
    scanf("%d %d",&w,&d);
                
    if(w == 0 && d == 0) break;

    for (int i = 0; i < 10; i++){
      front[i] = 0;
      side[i] = 0;
      fuse[i] = false;
      suse[i] = false;
      for (int j = 0; j < 10; j++){
	art[i][j] = 0;
      }                       
    }

    //????????????
    for (int i = 0; i < w; i++){
      scanf("%d ",&front[i]);
    }
    for (int i = 0; i < d; i++){
      scanf("%d ",&side[i]);
    }


    //?????´?????????????????\???
    for (int i = 0; i < w; i++){
      for (int j = 0; j < d; j++){
	if (front[i] == side[j] && !suse[j]){
	  art[i][j] = front[i];
	  suse[j] = true;
	  break;
	}
      }
    }
    for (int i = 0; i < d; i++){
      for (int j = 0; j < w; j++){
	if (side[i] == front[j] && !fuse[j]){
	  art[j][i] = side[i];
	  fuse[j] = true;
	  break;
	}
      }
    }

    //??¨??¨0???????????°?????????
    for (int i = 0; i < w; i++){
      bool zero = true;
      for (int j = 0; j < d; j++){
	if (art[i][j] != 0){
	  zero = false;
	  break;
	}
      }
      if (zero){
	for (int j = 0; j < d; j++){
	  if (front[i] <= side[j]){
	    art[i][j] = front[i];
	    break;
	  }
	}
      }
    }
    for (int i = 0; i < d; i++){
      bool zero = true;
      for (int j = 0; j < w; j++){
	if (art[j][i] !=0){
	  zero = false;
	  break;
	}
      }
      if (zero){
	for (int j = 0; j < w; j++){
	  if (side[i] <= front[j]){
	    art[j][i] = side[i];
	    break;
	  }
	}
      }
    }

    //????????????????????????????¢????
    for (int i = 0; i < w; i++){
      bool zero = true;
      for (int j = 0; j < d; j++){
	if (art[i][j] == front[i]){
	  zero = false;
	  break;
	}
      }
      if (zero){
	for (int j = 0; j < d; j++){
	  if (front[i] <= side[j]){
	    art[i][j] = front[i];
	    break;
	  }
	}
      }
    }

    for (int i = 0; i < d; i++){
      bool zero = true;
      for (int j = 0; j < w; j++){
	if (art[j][i] == side[i]){
	  zero = false;
	  break;
	}
      }
      if (zero){
	for (int j = 0; j < w; j++){
	  if (side[i] <= front[j]){
	    art[j][i] = side[i];
	    break;
	  }
	}
      }
    }


    //??????????????????
    for (int i = d-1; i >=0; i--){
      for (int j = 0; j < w; j++){
	ans+= art[j][i];
      }

    }
    cout << ans<< endl;

  }
  return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
int main()
{
	double N, K;
	while (cin >> N >> K)
	{
		int std = 1;
		while (std < K)
		{
			std *= 2;
		}
		double son = 1;
		for (int i = 2; i <= N; i++)
		{
			int tp = i;
			int tp2 = 1;
			while (tp < K)
			{
				tp *= 2;
				tp2 *= 2;
			}
			son += std / tp2;
		}
		double ans = son / std / N;
		printf("%.12f\n", ans);
	}
}




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

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int n, wmax;
  cin >> n >> wmax;
  int w[n], v[n];
  for(int i = 0; i < n; i++)
    cin >> w[i] >> v[i];
  int val[wmax+1];
  for(int i = 1; i <= wmax; i++)
    val[i] = -1e9;
  val[0] = 0;
  for(int i = 0; i < n; i++) {
    for(int j = wmax; j >= w[i]; j--)
      val[j] = max(val[j], val[j-w[i]] + v[i]);
    for(int j = 1; j <= wmax; j++)
      val[j] = max(val[j], val[j-1]);
  }
  cout << val[wmax];
}

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

// main.cpp

constexpr bool equals(const std::int_fast64_t x, const std::int_fast64_t y, const std::int_fast64_t z) {
  return x == y && y == z;
}

int main() {
  std::array<std::array<std::int_fast64_t, 3>, 3> c;
  for (std::array<std::int_fast64_t, 3>& c_i : c) {
    std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), 3, c_i.begin());
  }

  std::cout << (equals(c[0][0] - c[1][0], c[0][1] - c[1][1], c[0][2] - c[1][2]) && equals(c[1][0] - c[2][0], c[1][1] - c[2][1], c[1][2] - c[2][2]) && equals(c[2][0] - c[0][0], c[2][1] - c[0][1], c[2][2] - c[0][2]) ? "Yes" : "No") << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  ll N;
  cin >> N;
  ll a[N];
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < N; i++) {
    while (a[i] % 2 == 0) {
      a[i] /= 2;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

class Main {

	public static void main(String args[]){

		Scanner scan = new Scanner(System.in);
		int n;
		n = scan.nextInt();
		int x[][] = new int[2][n];
		
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < n; j++)
				x[i][j] = scan.nextInt();
		
		scan.close();
		
		int sum;
		int max = 0;
		

		for(int i = 0; i < n; i++){
			sum = 0;
			for(int j = 0; j <= i; j++){
				sum += x[0][j];
			}
			for(int j = i; j < n; j++){
				sum += x[1][j];
			}
			if(sum >= max)max =sum;
		}	
		System.out.print(max);
	}
}

Measured memory_bytes: 23636
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

// 1 <= k <= n <= 10^7
#define CNKMAX 100003
class CNK1 {
    std::vector<long long> fac, finv, inv;
    int MOD;
public:
    CNK1(int mod = 1000000007): MOD(mod), fac(CNKMAX), finv(CNKMAX), inv(CNKMAX) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < CNKMAX; 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;
        }
    }
    int get(const int &n, const int &k) const {
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }
};

long long power(long long x, long long n, long long mod = 1000000007) {
    if (n == 0) return 1;
    if (n % 2 == 0) return power(x * x % mod, n/2, mod);
    else return x * power(x, n-1, mod) % mod;
}

void solve() {
    string l;
    cin >> l;
    int len = l.size();
    CNK1 cnk;
    VI cs(100000+2);
    LL ans = 0;
    int c1 = 0;
    REP(i,0,len) {
        if (l[i] == '0') continue;
        LL sum = power(3, len - i - 1);
        sum = (sum * power(2, c1)) % MOD;
        ans = (ans + sum) % MOD;
        ++c1;
    }
    ans = (ans + power(2, c1)) % MOD;

    cout << ans << endl;
}

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

Measured memory_bytes: 3200
p = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(p[k-1])

Measured memory_bytes: 38256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main implements Runnable {
	//@start
	public static class WeightedUnionFind {
		int[] par; // 親の番号
		int[] ws; // 親との重みの差

		public WeightedUnionFind(int n) {
			par = new int[n];
			ws = new int[n];
			for (int i = 0; i < n; i++) {
				par[i] = -1;
			}
		}

		public int find(int x) {
			if (par[x] < 0) {
				return x;
			} else {
				final int parent = find(par[x]);
				ws[x] += ws[par[x]];
				return par[x] = parent;
			}
		}

		public int weight(int x) {
			find(x);
			return ws[x];
		}

		public boolean union(int x, int y, int w) { // x <-(w)- y (x + w = y)
			w += weight(x);
			w -= weight(y);
			x = find(x);
			y = find(y);

			if (x != y) {
				if(par[y] < par[x]) {  // 多い方が根になるようにスワップする.
	                int tmp = x; x = y; y = tmp; w = -w;
	            }
				par[x] += par[y];
				par[y] = x;
				ws[y] = w;

				return true;
			} else {
				return false;
			}
		}

		public boolean same(int x, int y) {
			return find(x) == find(y);
		}

		public Integer diff(int x, int y) { // x - y を求める. 比較不能ならnull.
			if (!same(x, y)) {
				return null;
			} else {
				return this.weight(x) - this.weight(y);
			}
		}

		public int size(int x) {
			return -par[find(x)];
		}
	}
	//@end
	
	public void run() {

		try {
			Scanner sc = new Scanner(System.in);

			while (true) {
				final int n = sc.nextInt();
				final int m = sc.nextInt();

				if (n == 0 && m == 0) {
					break;
				}

				WeightedUnionFind uf = new WeightedUnionFind(n);

				for (int i = 0; i < m; i++) {
					final String ops = sc.next();

					if ("?".equals(ops)) {
						final int r = sc.nextInt() - 1;
						final int l = sc.nextInt() - 1;

						if (!uf.same(r, l)) {
							System.out.println("UNKNOWN");
						} else {
							System.out.println(uf.weight(l) - uf.weight(r));
						}
					} else {
						final int r = sc.nextInt() - 1;
						final int l = sc.nextInt() - 1;
						final int w = sc.nextInt();

						uf.union(r, l, w);
					}
				}
			}

			sc.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public static void main(String[] args) throws IOException {
		new Thread(null, new Main(), "RUN", 8 * 1024 * 1024).start();
	}

	public static class Scanner {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

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

		// 他のnextXXXもXXX.parseXXX()メソッドを使って作れるので省略

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 61288
#include<string>
#include<vector>
#include<iostream>
using namespace std;
bool map[20][20][4];
vector< string > maphor,mapver;
int xsize,ysize;
void init(){
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
for(int k=0;k<4;k++){
map[i][j][k]=0;
}
}
}
}
void setmap(){
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
if(-1<i&&i<maphor.size()&&-1<j&&j<maphor[0].size()){
if(maphor[i][j]=='1'){
map[i][j][0]=1;
}
}
if(-1<i&&i<maphor.size()&&-1<j-1&&j-1<maphor[0].size()){
if(maphor[i][j-1]=='1'){
map[i][j][2]=1;
}
}
if(-1<i&&i<mapver.size()&&-1<j&&j<mapver[0].size()){
if(mapver[i][j]=='1'){
map[i][j][3]=1;
}
}
if(-1<i-1&&i-1<mapver.size()&&-1<j&&j<mapver[0].size()){
if(mapver[i-1][j]=='1'){
map[i][j][1]=1;
}
}
}
}
}
int solve(){
int x=0,y=0;
int v=0;
string vec="RULD";
int loop[4]={1,0,3,2};
int vx[4]={1,0,-1,0};
int vy[4]={0,-1,0,1};
int count=0;
while(1){
count++;
if(count>100)return -1;
for(int i=0;i<5;i++){
if(i==4)return -1;
if(x==0
&& y==0
&&(((v+loop[i])%4)==2)){
return 0;
}
if(map[y][x][(v+loop[i])%4]==1){
v+=loop[i];
v=v%4;
x+=vx[v];
y+=vy[v];
cout<<vec[v];
break;
}
}
}
}
int main(){
string tmp;
for(int i=0;cin>>tmp;i++){
if(i%2==0){
maphor.push_back(tmp);
}else{
mapver.push_back(tmp);
}
}
xsize=maphor[0].size()+1;
ysize=mapver.size()+1;
init();setmap();
/*
for(int i=0;i<xsize;i++){
for(int j=0;j<ysize;j++){
for(int k=0;k<4;k++){
cout<<map[i][j][k];
}
cout<<" ";
}
cout<<endl;
}
*/
if(solve()==-1)return -1;
cout<<endl;
return 0;
}

Measured memory_bytes: 1188
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = inp()
y3 = math.ceil(s/(10**9))
x3 = 10**9*y3 - s
print(0,0,10**9,1,x3,y3)





Measured memory_bytes: 38764
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <string>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef long long ll;

#define REP(j,n) for (int (j)=0; j<(int)(n); ++j)
#define FOR(j,k,n) for (int (j)=(k); j<(int)(n); ++j)
#define FOREQ(j,k,n) for (int (j)=(k); j<=(int)(n); ++j)

#define MEMSET(z,val) memset(z,val,sizeof(z))
#define SZ(z) ((int)(z).size())

int sea[300][300];
int land[300][300];
int dp[2][300];
int ar[2000];

int main() {
    int N,M;
    while (cin>>N>>M,N|M) {
        MEMSET(sea, 0x0f);
        MEMSET(land, 0x0f);
        REP(k,M) {
            int x,y,w; char c;
            cin>>x>>y>>w>>c;
            x--; y--;
            if (c == 'L') {
                land[x][y] = min(land[x][y], w);
                land[y][x] = min(land[y][x], w);
            } else {
                sea[x][y] = min(sea[x][y], w);
                sea[y][x] = min(sea[y][x], w);
            }
        }
        REP(k, N) REP(i, N) REP(j, N) {
            sea[i][i] = 0;
            land[i][i] = 0;
            sea[i][j] = min(sea[i][j], sea[i][k] + sea[k][j]);
            land[i][j] = min(land[i][j], land[i][k] + land[k][j]);
        }
        int R; cin>>R;
        REP(j,R) { cin>>ar[j]; ar[j]--; }
        int px = ar[0];
        MEMSET(dp, 0x0f);
        dp[0][px] = 0;
        REP(iter, R) {
            int nx = ar[iter];
            int prev = iter & 1;
            int next = (iter + 1) & 1;
            MEMSET(dp[next], 0x0f);
            REP(i, N) {
                REP(j, N) {
                    dp[next][j] = min(dp[next][j], dp[prev][i] + land[px][i] + sea[i][j] + land[j][nx]);
                }
                dp[next][i] = min(dp[next][i], dp[prev][i] + land[px][nx]);
                assert(dp[next][i] >= 0);
            }
            px = nx;
        }
        int ans = 0x0f0f0f0f;
        REP(i, N) {
            ans = min(ans, dp[R & 1][i]);
        }
        assert(ans >= 0 && ans != 0x0f0f0f0f);
        printf("%d\n",ans);
    }
}

Measured memory_bytes: 1584
import java.util.Scanner;

class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		
		while(true)
		{
			try
			{
				int n = sc.nextInt() + sc.nextInt();
				int i = 1;
				while (n >= 10)
				{
					n /= 10;
					i++;
				}
				System.out.println(Integer.toString(i));
			}
			catch(Exception e)
			{
				break;
			}
		}
	}
}

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

using namespace std;

int main()
{
	// const int MAX_N = 100000;
	long long n;
	cin >> n;
	
	string s;
	cin >> s;
	
	vector<char> str;
	
	for (long long i = 0; i < n; i++)
	{
		str.push_back(s[i]);
	}
	
	int index = 1;
	bool keep = true;
	while (keep)
	{
		if (str[index] == str[index-1])
		{
			str.erase(str.begin() + index);
			n-=1;
		}
		else
		{
			index += 1;
		}
		
		if (index >= n)
			keep = false;
	}
	
	cout << str.size();
}


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

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

    cout << n * (n + 1) / 2 << endl;

    return 0;
}

Measured memory_bytes: 256