akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
vector<ll> BellmanFord(int s, vector<vector<pair<ll, ll>>>& graph) {
    int n = sz(graph);
    vector<ll> dist(n, LINF);
    dist[s] = 0;
    rep(i, n - 1) {
        rep(from, n) {
            for (auto p : graph[from]) {
                int to = p.first;
                ll cost = p.second;
                chmin(dist[to], dist[from] + cost);
            }
        }
    }
    rep(i, n) {
        rep(from, n) {
            for (auto p : graph[from]) {
                int to = p.first;
                ll cost = p.second;
                if (dist[to] > dist[from] + cost) {
                    dist[to] = -LINF;
                }
            }
        }
    }
    return dist;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<ll, ll>>> g(n);
    rep(i, m) {
        int s, t;
        ll x;
        cin >> s >> t >> x;
        g[s].emplace_back(t, x);
    }

    auto ans = make_vec<string>(n, n);
    rep(i, n) {
        auto bf = BellmanFord(i, g);
        rep(j, n) {
            if (bf[j] == -LINF) {
                cout << "NEGATIVE CYCLE" << endl;
                return 0;
            }
            if (bf[j] >= LINF / 2) {
                ans[i][j] = "INF";
            } else {
                ans[i][j] = to_string(bf[j]);
            }
        }
    }

    rep(i, n) rep(j, n) cout << ans[i][j] << " \n"[j == n - 1];
}


Measured memory_bytes: 3804
x, y = map(int, input().split())

score = 0

for z in [x, y]:
  if z == 1:
    score += 300000
  elif z == 2:
    score += 200000
  elif z == 3:
    score += 100000

if (x == 1) and (y == 1):
  score += 400000
  
print(score)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> moves(n);
    for (int& x : moves) cin >> x;
    vector<bool> win(k + 1);
    for (int i = 1; i <= k; ++i)
        for (int j = 0; j < n && moves[j] <= i; ++j)
            win[i] = win[i] | !win[i - moves[j]];
    cout << (win[k] ? "First" : "Second");
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////

int main() {
	int N;
	cin >> N;
	int count = 1;
	int h[110];
	for (int i = 0; i < N; ++i) {
		cin >> h[i];
	}
	int key = h[0];
	for (int i = 1; i < N; ++i) {
		if (key <= h[i]) {
			count++;
			key = h[i];
		}
	}
	cout << count << endl;
	return 0;
}



Measured memory_bytes: 256
//?????§??¬?´???°
#include<stdio.h>

#define swap(type, x, y)        do{type t = x; x = y; y = t;} while(0)


long gcd(long x, long y){
    if(x % y == 0) return y;
    else {
        return gcd(y, x % y);
    }
}



int main(void){
    long x;
    long y;
    long ans;
    scanf("%ld", &x);
    scanf("%ld", &y);
    
    if(x < y) swap(long, x, y);
    
    ans = gcd(x, y);
    
    printf("%ld\n", ans);
    
    return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
int main()
{
 int n,m,a,b,s=0;cin>>n>>m;
 a=n-1;
 for(int i=1;i<=a;i++)
  s+=i;
 b=m-1;
 for(int i=1;i<=b;i++)
  s+=i;
 cout<<s;
 return 0;
}

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    rep(i,0,N) cin >> a[i];

    ll ans = 15000000000;
    rep(bit, 0, 1<<N) {
        if (__builtin_popcount(bit) != K) continue;

        ll price = 0;
        int highest = 0;
        rep(i,0,N) {
            if (bit & (1<<i)) {
                price += max(0, highest + 1 - a[i]);
                highest = max(highest + 1, a[i]);
            } else highest = max(highest, a[i]);
        }
        ans = price < ans ? price : ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/integer/common_factor_rt.hpp>
using namespace std;
using ll=long long;
const int MOD=1000000007;

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

int main() {
  ll n,x;
  cin >> n >> x;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  if(n==1){
    cout << abs(x-a.at(0)) << endl;
    return 0;
  }
  else{
    ll ans=abs(x-a.at(0));
    for(int i=0;i<n-1;i++){
      ans=gcd(ans,abs(a.at(i+1)-a.at(i)));
    }
    cout << ans << endl;
  }
}

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

int count_change(int x, int* a, int n, int* c, int d) {
  if (n < 0) return 0;
  if (x == 0) return 1;
  else if (x < 0 or d == 3) return 0;
  else {
    return count_change(x, a, a[d + 1], c, d + 1) +
           count_change(x - c[d], a, n - 1, c, d);
  }
}

int main() {
  int c[3] = {500, 100, 50};
  int a[3], x; cin >> a[0] >> a[1] >> a[2] >> x;
  cout << count_change(x, a, a[0], c, 0) << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(raw_input())
t = []
a = []
for i in xrange(n):
    mem = map(int, raw_input().split())
    t.append(mem[0])
    a.append(mem[1])

for i in xrange(n):
    if i == 0:
        tn = t[0]
        an = a[0]
    else:
        mt = tn / t[i] if (tn%t[i] == 0) else tn / t[i] + 1
        ma = an / a[i] if (an%a[i] == 0) else an / a[i] + 1
        if mt > ma:
            tn = mt * t[i]
            an = mt * a[i]
        else:
            tn = ma * t[i]
            an = ma * a[i]
print tn + an
            


Measured memory_bytes: 2692
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){ 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
 } 
ll lcm(ll a, ll b)  
 {  
    return (a*b)/gcd(a, b);  
 }  

int main()
{
  ll n;cin>>n;
  vector<pair<int,int> > a(n);
  for(ll i=0;i<n;i++)
  {
      cin>>a[i].second>>a[i].first;
  }
  sort(a.begin(),a.end());
  ll time=0;
  for(ll i=0;i<n;i++)
  {
      time+=a[i].second;
      if(time>a[i].first)
      {cout<<"No";return 0;}
  }
  cout<<"Yes";
  return 0;  
}


Measured memory_bytes: 1792
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll n;
    cin >> n;
    if(n > 999) cout << "ABD"<<endl;
    else cout << "ABC" << endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


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

int main(){
    int A[3][3];
    int N;
    int b[100];
    int hole[3][3];
    string answer = "No";
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            hole[i][j] = 0;
        }
    }
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cin >> A[i][j];
        }
    }
    cin >> N;
    for(int k = 0; k < N; k++){
        cin >> b[k];
    }
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < N; k++){
                if(A[i][j]==b[k]){
                    hole[i][j] = 1;
                }
            }
        }
    }
    for(int i = 0; i < 3; i++){
        if(hole[i][0] == 1 && hole[i][1] == 1 && hole[i][2] == 1){
            answer = "Yes";
        }
    }
    for(int j = 0; j < 3; j++){
        if(hole[0][j] == 1 && hole[1][j] == 1 && hole[2][j] == 1){
            answer = "Yes";
        }
    }
    if(hole[0][0] == 1 && hole[1][1] == 1 && hole[2][2] == 1){
        answer = "Yes";
    }
    if(hole[0][2] == 1 && hole[1][1] == 1 && hole[2][0] == 1){
        answer = "Yes";
    }
    cout << answer << endl;
    system("pause");
    return 0;

}

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

int main()
{
	int high[10],copy;

	for(int i=0;i<10;i++)
		cin>>high[i];

	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(high[i]>high[j])
			{
				copy=high[i];
				high[i]=high[j];
				high[j]=copy;
			}
	cout<<high[0]<<endl<<high[1]<<endl<<high[2]<<endl;
}

Measured memory_bytes: 1160
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MON 1000000007
#define INF (1<<29)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))


class Vec{
public:
  double x, y;
  Vec(double x = 0, double y = 0):x(x),y(y){}

  void read(){
    cin >> x >> y;
  }
  
  Vec operator+(const Vec &other)
  {
    Vec result = *this;
    result.x += other.x;
    result.y += other.y;
    return result;
  }

  Vec operator-(const Vec &other)
  {
    Vec result = *this;
    result.x -= other.x;
    result.y -= other.y;
    return result;
  }

  Vec operator*(const float &k)
  {
    Vec result = *this;
    result.x *= k;
    result.y *= k;
    return result;
  }

  Vec operator/(const float &k)
  {
    Vec result = *this;
    result.x /= k;
    result.y /= k;
    return result;
  } 
  
  double cross(const Vec &other)
  {
    return x*other.y - y*other.x;
  }

  double dot(const Vec &other){
    return x*other.x + y*other.y;
  }
  
  bool operator==(const Vec &other) const
  {
    return abs(x - other.x) < EPS && abs(y - other.y) < EPS;
  }

  float norm()
  {
    return sqrt(x*x+y*y);
  }

  float norm2()
  {
    return x*x+y*y;
  }

  Vec standard(){
    Vec result = *this;
    return result/result.norm();
  }
};

//ccw:1, cw:-1, other:0
Int CCW(Vec a, Vec b, Vec c){
  b = b - a;
  c = c - a;
  if(b.cross(c) > EPS)return -1;
  if(b.cross(c) < -EPS)return 1;
  return 0;
}



class Line{
public:
  Vec a, b;
  Vec vect;
  Line(Vec a = Vec(), Vec b = Vec()):a(a),b(b),vect(b-a){}

  //projection
  Vec proj(Vec p){
    p = p - a;
    return a + vect * vect.dot(p) / vect.norm2();
  }

  //reflection
  Vec reflect(Vec p){
    return proj(p) * 2 - p;
  }

  bool onSegment(Vec p){
    return abs((p-a).cross(b-a)) < EPS && (p-a).dot(p-b) < EPS;
  }

  //other -> LineSegment(not inclusive), this -> Line
  bool intersect(Line &other){
    return CCW(a, b, other.a) * CCW(a, b, other.b) < 0;
  }
};


int main(){
  Int q;
  cin >> q;
  while(q--){
    Vec p0, p1, p2, p3;
    p0.read();
    p1.read();
    p2.read();
    p3.read();
    Line l1(p0, p1), l2(p2, p3);
    if(l1.onSegment(p2) || l1.onSegment(p3) || l2.onSegment(p1) || l2.onSegment(p0) || l1.intersect(l2) && l2.intersect(l1))cout << 1 << endl;
    else cout << 0 << endl;
  }
  return 0;
}


Measured memory_bytes: 3224
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <stack>
#include <array>
#include <limits>
//#include <tuple>

using namespace std;

//constexpr long long mod = static_cast<long long>(1e9 + 7);


int main() {
    int V, E, r;
    std::cin >> V >> E;

    std::vector<std::vector<int>> dist(V, std::vector<int>(V, std::numeric_limits<int>::max()));
    while(--E >= 0) {
        int s, t, d;
        std::cin >> s >> t >> d;
        dist[s][t] = d;
    }

    for(int i = 0; i < V; ++i)
        dist[i][i] = 0;

    for(int k = 0; k < V; ++k) {
        for(int i = 0; i < V; ++i) {
            for(int j = 0; j < V; ++j) {
                if(dist[i][k] != std::numeric_limits<int>::max()
                   && dist[k][j] != std::numeric_limits<int>::max())dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    bool isNegative = false;
    for(int i = 0; i < V; ++i)
        isNegative |= dist[i][i] < 0;

    if(isNegative) {
        std::cout << "NEGATIVE CYCLE" << std::endl;
    } else {
        for(const auto& ds: dist) {
            for(int i = 0; i < V; ++i){
                std::cout << (ds[i] != std::numeric_limits<int>::max() ? std::to_string(ds[i]) : "INF");
                if(i < V - 1) std::cout << " ";
            }
            std::cout << std::endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3304
n, l = (int(i) for i in input().split())

lst = []
for i in range(n):
     lst.append(l + i)

avg = [sum(lst) - i for i in lst]

cnt = 0
tmp = 999
for n in range(len(avg) ):
    ans = abs(sum(lst) - avg[n])
    if abs(sum(lst) - avg[n]) < tmp:
        cnt = n
        tmp = ans
print(sum(lst) - lst[cnt])



Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String s1 = cin.nextLine();
        String s2 = cin.nextLine();
        int x = s2.indexOf(s1);
        if(x==0 && s1.length()+1==s2.length())
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 35728
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
	long long x;
	cin >> x;

	long long n = x;
	long long ret = 0;
	
	ret = n / 11 * 2;
	n %= 11;
	if(n != 0)
		if(n > 6)
			ret += 2;
		else
			ret++;

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <deque> 
using namespace std;
 
int main() {
  int A,B,C;
  cin >> A >> B >> C;
  set<int> s;
  s.insert(A);
  s.insert(B);
  s.insert(C);
  if(s.size()==2){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}
 

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

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)

using namespace std;

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

const int MX = 200005;
int n, a[MX];
ll res;
map<int, int> mp;

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	forn (i, n) {
		cin >> a[i];
		res += mp[i - a[i]];
		mp[i + a[i]]++;
	}
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 21460
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9+7
cnt = 0
for i in range(n):
  for j in range(i+1,n):
      if a[i] > a[j]:
        cnt += 1
ans = cnt*k
cnt2 = 0
for i in range(n):
  for j in range(n):
    if a[i] > a[j]:
      cnt2 += 1
ans += (k*(k-1)//2)*cnt2
print (ans%mod)

Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int x = sc.nextInt();
		int t = 0;
		int cnt = 0;
		while (x > t) {
			cnt++;
			t += cnt;
		}
		System.out.println(cnt);
	}
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll = long long;
 
int main(){
  int h,w,k;
  cin >> h >> w >> k;
  char c[h][w];
  rep(i,h){
    rep(j,w)
      cin >> c[i][j];
  }
  int black=0;
  rep(i,h){
    rep(j,w)
      if(c[i][j]=='#') black++;
  }
  int all = 1<<(h+w);
  //cout << all << endl;
  int count=0;
  if(black<k) cout << 0 << endl;
  else{
    rep(mask,all){
      black=0;
      rep(i,h){
        rep(j,w){
          //cout << mask << endl;
          if((mask>>i&1)&&(mask>>(h+j)&1)){
            //cout << "あ" << endl;
            if(c[i][j]=='#') black++;
          }
        }
      }
      if(black==k) count++;
    }
    cout << count << endl;
  }
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int INF=1e9;
const ll MX = 1e18;
const ll MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
const string tr="abcdefghijklmnopqrstuvwxyz";
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define YN {puts("YES");}else{puts("NO");}
const ll MAX = 1000001;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (ll 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(ll n, ll k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}
ll llpow(ll n,ll i){ll cnt=n;  for(ll j=0;j<i-1;j++){n*=cnt;}return n;}
bool ip/*is_prime*/(long long N) {if (N == 1) return false;for (long long i = 2; i * i <= N; ++i) {if (N % i == 0) return false;}return true;}
int digit(ll N) {int ans = 0;while (N) {++ans;N /= 10;}return ans;}
vector<pair<ll,ll>> pf/*prime_factorize*/(ll n){vector<pair<ll,ll>> res;for(ll a=2;a*a<=n;a++){if(n%a!=0) continue;ll ex=0;while(n%a==0){ex++;n/=a;}res.pb({a,ex});}if(n!=1) res.pb({n,1});return res;}
vector<ll> div/*divisor*/(ll n){  vector<ll> res={1};for(ll a=2;a*a<=n;a++){if(n%a!=0) continue;ll b=n/a;res.pb(b);if(b!=a) res.pb(a);}sort(all(res));return res;}

int main(){
    string s;
    cin>>s;
    string t=s.substr(0,3);
    cout<<t<<endl;
}


Measured memory_bytes: 3592
#D
N=int(input())
A=list(map(int,input().split()))
B=[]

for i in range(N-1):
    if A[i+1]>A[i]:
        B.append(["up",i])
    elif A[i+1]<A[i]:
        B.append(["down",i])
        
C=[]
for i in range(len(B)-1):
    if B[i][0]==B[i+1][0]:
        continue
    C.append(B[i])
if B!=[]:
    C.append(B[-1])

while True:
    if C==[]:
        break
    if C[-1][0]=="down":
        C.pop(-1)
    else:
        break
        
kabu=0
money=1000
if C!=[]:
    if C[0][0]=="up":
        kabu+=money//A[0]
        money%=A[0]
for act in C:
    if act[0]=="up":
        money+=A[act[1]+1]*kabu
        kabu=0
    else:
        kabu+=money//A[act[1]+1]
        money%=A[act[1]+1]
print(money)

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

int main(){
  string a, b, c;
  cin >> a >> b >> c;
  int la = a.length();
  int lb = b.length();
  int lc = c.length();
  int ans = la + lb + lc;
  int lbc = lb + lc;
  string q = "";
  rep(i,lbc) q += "?";
  a = q + a + q;
  la = a.length();
  vector<bool> bf(la,false);
  vector<bool> cf(la,false);
  for(int i = 0; i + lb <= la; i++) {
    bool f = true;
    rep(j,lb) {
      if(a[i+j] != '?' && b[j] != '?' && a[i+j] != b[j]) f = false;
    }
    if(f) bf[i] = true;
  }
   for(int i = 0; i + lc <= la; i++) {
    bool f = true;
    rep(j,lc) {
      if(a[i+j] != '?' && c[j] != '?' && a[i+j] != c[j]) f = false;
    }
    if(f) cf[i] = true;
  };
  map<int,bool> bcf;
  for(int i = -lc+1; i < lb; i++) {
    bool f = true;
    rep(j,lc) {
      if(i+j >= 0 && i+j < lb && b[i+j] != '?' && c[j] != '?' && b[i+j] != c[j]) f = false;
    }
    if(f) bcf[i] = true;
    else bcf[i] = false;
  }
  rep(i,la) {
    rep(j,la) {
      if(j-i >= -lc+1 && j-i < lb) {
        if(bcf[j-i] && bf[i] && cf[j]) ans = min(ans,max({i+lb,j+lc,la-lbc})-min({i,j,lbc}));
      } else {
        if(bf[i] && cf[j]) ans = min(ans,max({i+lb,j+lc,la-lbc})-min({i,j,lbc}));
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


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

    ll ans = 0;
    ll A = 1;
    while(A <= (N - 1) / 2){
        ans += (N - 1) / A;
        A++;
    }
    ans += (N - 1) - A + 1;

    cout << ans << endl;        

    return 0;
}


Measured memory_bytes: 3632
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	static final int MOD = (int)1e9+7;
	int N;
	public void solve() {
		N = nextInt();

		long ans = 1;
		for(int i = 1;i <= N;i++){
			ans *= i;
			ans %= MOD;
		}
		out.println(ans);
	}
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

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

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 21076
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b,c;
	cin>>a>>b>>c;
	set<int> st={a,b,c};
	cout<<(st.size()==2?"Yes":"No")<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
	int m, f, r, g;
	scanf("%d %d %d", &m, &f, &r);
	while (m != -1 || f != -1 || r != -1) {
		g = m + f;
		if (m == -1 || f == -1 || g < 30)printf("F\n");
		else if (g >= 80)printf("A\n");
		else if (g >= 65 && g < 80)printf("B\n");
		else if (g >= 50 && g < 65 || g >= 30 && g < 50 && r >= 50)printf("C\n");
		else if (g >= 30 && g < 50)printf("D\n");
		scanf("%d %d %d", &m, &f, &r);
	}
}


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

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

// 間隔gを指定した挿入ソート
void insertionSort(int A[], int n, int g) {
  for ( int i = g; i < n; i++ ) {
    int v = A[i];
    int j = i - g;
    while ( j >= 0 && A[j] > v ) {
      A[j + g] = A[j];
      j -= g;
      cnt++;
    }
    A[j + g] = v;
  }
}

void shellSort(int A[], int n) {
  // 数列G = {1, 4, 13, 40, 121, 364, 1093, ...}を生成
  for ( int h = 1; ; ) {
    if ( h > n ) break;
    G.push_back(h);
    h = 3*h + 1;
  }

  for ( int i = G.size()-1; i >= 0; i-- )  // 逆順にG[i] = g を指定
    insertionSort(A, n, G[i]);
}

int main() {
  cin >> n;
  // より速い入力scanf関数を使用
  for ( int i = 0; i < n; i++ ) scanf("%d", &A[i]);
  cnt = 0;

  shellSort(A, n);

  cout << G.size() << endl;
  for ( int i = G.size() - 1; i >= 0; i-- ) {
    printf("%d", G[i]);
    if ( i ) printf(" ");
  }
  printf("\n");
  printf("%d\n", cnt);
  for ( int i = 0; i < n; i++ ) printf("%d\n", A[i]);

  return 0;
}


Measured memory_bytes: 7176
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int sum = a+b+c;
        System.out.println(sum - Math.max(Math.max(a, b), c));
    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef set <int> :: iterator sitr;
typedef set <ll> :: iterator sltr;
#define mset multiset
typedef mset <int> msi;
typedef mset <ll> msll;
typedef mset <int> :: iterator msitr;
typedef mset <ll> :: iterator msltr;
#define mp make_pair
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
int x,y;
int main(){
    cin>>x>>y;
    cout<<x+(y/2)<<endl;


}


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

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

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

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

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
    cin>>n>>x;
    Cout(3*(n-__gcd(n,x)));
    return 0;
}


Measured memory_bytes: 256
class Dice:
    def __init__(self, dice: list):
        self.top = dice[0]
        self.bottom = dice[5]
        self.front = dice[1]
        self.behind = dice[4]
        self.right = dice[2]
        self.left = dice[3]

    def __eq__(self, other):
        if not isinstance(other, Dice):
            return NotImplemented
        return self.top == other.top and self.bottom == other.bottom and self.front == other.front \
                and self.behind == other.behind and self.right == other.right

    def roll(self, direction: str):
        buffer = self.top
        if direction == 'E':
            self.top = self.left
            self.left = self.bottom
            self.bottom = self.right
            self.right = buffer
        elif direction == 'N':
            self.top = self.front
            self.front = self.bottom
            self.bottom = self.behind
            self.behind = buffer
        elif direction == 'S':
            self.top = self.behind
            self.behind = self.bottom
            self.bottom = self.front
            self.front = buffer
        else:
            self.top = self.right
            self.right = self.bottom
            self.bottom = self.left
            self.left = buffer

    def turn(self):
        buffer = self.front
        self.front = self.right
        self.right = self.behind
        self.behind = self.left
        self.left = buffer


def main():
    dice1, dice2 = [Dice(list(map(int, input().split()))) for _ in range(2)]
    for _ in range(2):
        for _ in range(4):
            for _ in range(4):
                if dice1 == dice2:
                    print('Yes')
                    return
                dice2.turn()
            dice2.roll('N')
        dice2.roll('E')
    print('No')


if __name__ == '__main__':
    main()



Measured memory_bytes: 5612
def ncr(n, r):
    return fac[n] * facinv[r] * facinv[n - r] % MOD


MOD = 10 ** 9 + 7
X, Y = map(int, input().split())

N = 10 ** 6
fac = [1, 1]
facinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fac.append(fac[i - 1] * i % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    facinv.append((facinv[-1] * inv[-1]) % MOD)

if (X + Y) % 3 or Y > 2 * X or Y < X // 2:
    print(0)
    exit()
d = (X + Y) // 3
print(ncr(d, X - (X + Y) // 3))


Measured memory_bytes: 127692
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9+5;
signed main(){
	int n,k;
	cin>>n>>k;
	vector<int> v(n,0);
	for(int& x:v){
		cin >> x;
	}
	vector<int> dp(n,INF);
	dp[0]=0;
	for(int i=0;i<n;++i){
		//for(int j:{i+1,i+2}){
		for(int j=i+1;j<=i+k;j++){
			if(j<n){
				dp[j] = min(dp[j],dp[i]+abs(v[i]-v[j]));
			}
		}
	}
	cout << dp[n-1] ;
}

Measured memory_bytes: 1792
// https://atcoder.jp/contests/abc173/tasks/abc173_d

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

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

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

template <typename T>
inline ll len(V<T> arr) {
  return arr.size();
}

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

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

const ll INF = 1e18;

void solve();

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

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

  return 0;
}
#endif

void solve() {
  ll N;
  cin >> N;

  VL as(N);
  rep(i, N) cin >> as[i];

  sort(as.rbegin(), as.rend());

  ll res = 0;

  rep(i, N - 1) res += as[(i + 1) / 2];

  cout << res << "\n";
}


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

int main() {
	int N;
	cin >> N;
	for (int i = 0; i <= N; ++i) {
		int num = i * 108;
		num /= 100;
		if (N == num) {
			cout << i << endl;
			return 0;
		}
	}
	cout << ":(" << endl;
	return 0;
}

Measured memory_bytes: 3640
#include <iostream>
int gcd(int y, int x) {
	if (y < x) std::swap(x, y);
	int r;
	while (x > 0) {
		r = y % x;
		y = x;
		x = r;
	}

	return y;

}

void solve_C(){
	int K;
	std::cin >> K;

	int sum = 0;
	for (int i = 1; i <= K; i++) {
		for (int j = 1; j <= K; j++) {
			for (int k = 1; k <= K; k++) {
				sum += gcd(gcd(i, j), k);
			}
		}
	}

	std::cout << sum;

}

int main(){
solve_C();
}


Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <queue>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;

int main()
{
    int N;
    int a[100005] = { 0 };
    int total_cost = 0;
    cin >> N;
    REP(i, N) {
        cin >> a[i + 1];
        total_cost += abs(a[i + 1] - a[i]);
    }
    total_cost += abs(a[N + 1] - a[N]);
    REP(i, N) {
        cout << total_cost - abs(a[i + 1] - a[i]) - abs(a[i + 2] - a[i + 1]) + abs(a[i + 2] - a[i]) << endl;
    }
    return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n; cin >> n;
    string s;
    unordered_map<string, long> T;
    long sum = 0;

    for(int i = 0; i < n; i++){
        cin >> s;
        sort(s.begin(), s.end());
        T[s]++;
    }

    for(const auto& p : T){
        sum += p.second * (p.second -1) /2;
    }
    cout << sum << endl;

}

Measured memory_bytes: 10660
#include<cstdio>

typedef long long ll;ll s,a[19];
ll dfs(int l,int e,int r,ll d,ll b)
{
	if(l--==e)return d?0:e==r?10:1;
	if(d%a[r]!=0)return 0;
	ll c=0;
	for(int i=-9;i<=(r?9:8);i++)
		c+=(i<0?10+i:r?10-i:9-i)*dfs(l,e,r+1,d-i*b,b-a[l]-a[r]);
	return c;
}

int main()
{
	int d,i=1;scanf("%d",&d);
	for(ll b=*a=9;i<20;b=b*10+9,a[i]=a[i-1]*10,i++)
		s+=dfs(i,i>>1,0,d,b);
	printf("%lld\n",s);
}

Measured memory_bytes: 128
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while(true) {
      int h = sc.nextInt();
      int w = sc.nextInt();
      if(h == 0 && w == 0) {
        break;
      } else {
        for(int i = 0; i < h; i++) {
          for(int j = 0; j < w; j++) {
            System.out.print("#");
          }
          System.out.println();
        }
        System.out.println();
      }
    }
  }
}



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

int value(int a[], int size, int p){
	int w = 0, k = 1;
	for (int i = 0; i < size; i++){
		if (w + a[i] <= p){
			w += a[i];
		}else{
			w = a[i];
			k++;
		}
	}
	return k;
}
int main(){
	int n, k;
	cin >> n >> k;
	int w[n];
	int max = 0; int sum = 0;
	for (int i = 0; i < n; i++){
		std::cin >> w[i];
		if (max < w[i]){
			max = w[i];
		}
		sum += w[i];
	}
	while (max != sum){
		int mid = (max + sum) / 2;
		if (value(w, n, mid) > k){
			max = mid + 1;
		}else{
			sum = mid;
		}
	}
	cout << max << endl;
	return 0;
}



Measured memory_bytes: 3496
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI acos(-1.0)
#define test() int t; cin>>t; while(t--)
#define ll long long int

int main()
{
	IOS;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int d, t, s;
	cin >> d >> t >> s;
	if (d <= t * s) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}
	return 0;
}


Measured memory_bytes: 3656
#include <stdio.h>

using namespace std;

int main() {
    int W, H, x, y, r;
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
    if (( x >= r && x <= W-r ) && ( y >= r && y <= H-r ))
    printf("Yes\n");
    else printf("No\n");
    
}


Measured memory_bytes: 2676
from collections import deque
n = int(input())
l = input().split()
d = deque()
for idx, i in enumerate(l):
    if (idx +1) % 2 == 1:
        d.appendleft(i)
    else:
        d.append(i)
if n % 2 == 0:
    d.reverse()
print(' '.join(d))

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

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;
const int MOD = 1000000007;

typedef long long ll;

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

ll LCM(ll x, ll y)
{
    return x * y / GCD(x, y);
}

using Graph = vector<vector<int>>;

typedef pair<int, int> P;
int main()
{
    int n, m;
    cin >> n >> m;
    priority_queue<ll> que;
    rep(i, n)
    {
        int a;
        cin >> a;
        que.push(a);
    }

    rep(i, m)
    {
        int a = que.top();
        que.pop();
        a = a / 2;
        que.push(a);
    }

    ll sum = 0;
    rep(i, n)
    {
        sum += que.top();
        que.pop();
    }

    cout << sum << endl;
}

Measured memory_bytes: 1400
n,m = map(int,input().split())
x = list(map(int,input().split()))
if n >= m:
    print(0)
    exit()
x.sort()
dist =[]
for i in range(1,m):
    dis = x[i]-x[i-1]
    dist.append(dis)
dist.sort()
#print(dist)
ans = 0
for i in range(m-n):
    ans += dist[i]
print(ans)

Measured memory_bytes: 56872
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int MAXN=3e5+10;
const ll mod=998244353;
ll a,b,k,n,ans;
ll fac[MAXN],inv[MAXN];
ll poww(ll x,ll y)
{
	ll ans=1;
	for (;y;y>>=1,x=(x*x)%mod) if (y&1) ans=(ans*x)%mod;
	return ans;
}
void init()
{
	fac[0]=1;
	inv[0]=1;
	for (int i=1;i<=n;i++) fac[i]=(fac[i-1]*(ll)i)%mod;
	for (int i=1;i<=n;i++) {
		inv[i]=(inv[i-1]*poww(i,mod-2))%mod;
	}
}
ll C(ll x,ll y){
	if (x<0||y<0||x<y) return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
	scanf("%d%lld%lld%lld",&n,&a,&b,&k);
	init();
	for (ll i=0;i<=n;i++) 
	if ((k-i*a)%b==0)
	{
		ll sum=(k-i*a)/b;
		ans=(ans+C(n,i)*C(n,sum)%mod)%mod;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 4992
#include<iostream>
using namespace std;
int main()
{
	string a,b;
	int n;
	cin>>n;
	cin>>a;
	cin>>b;
	string x;
	for(int i=0;i<n;i++){
		string str1 =a.substr(i,a.size());
		string str2 =b.substr(0,str1.size());
		if(str2.compare(str1)==0){
			cout<<i+b.size()<<"\n";
			return 0;
		}
		str1.clear();
		str2.clear();
	}
	cout<<a.size()+b.size()<<"\n";
}

Measured memory_bytes: 256
/*
 * short          2^15-1 ~ 3e4
 * int, long x86  2^31-1 ~ 2e9
 * long long      2^63-1 ~ 9e18
 */
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define fr(a, b) for (int a = 0; a < b; ++a)
using namespace std; typedef long long ll; const int inf = numeric_limits<int>::max(); void print() {cerr << endl;}
template<typename T, typename... Ts> void print(T&&a, Ts&&...etc) {cerr << a << ' '; print(etc...);}
template<typename T, typename U> ostream& operator<<(ostream& s, const pair<T,U>&p) {s << "<" << p.x << ", " << p.y << ">"; return s;} // ver. 2020-02-17
template<typename T> ostream& operator<<(ostream& s, const vector<T>&v) {s << "["; for (auto &x : v) s << x << ", "; if (!v.empty()) s << "\b\b"; s << "]"; return s;}
struct io{io(){ios_base::Init i; ios_base::sync_with_stdio(0); cin.tie(0);}}io;
const ll m = 1000000007;

ll fact[11] = {
    1,
    927880474,
    933245637,
    668123525,
    429277690,
    733333339,
    724464507,
    957939114,
    203191898,
    586445753,
    698611116,
};

ll pw(ll a, ll n) {
    if (n == 0) return 1;
    if (n % 2) {
        return (a * pw(a, n-1)) % m;
    }
    ll a2 = pw(a, n/2);
    return (a2 * a2) % m;
}

ll f(ll n) {
    if (n < 2) return 1;
    ll ans = 1;
    ll j = 1;
    for (ll i = 1; i <= 10; ++i) {
        if (n >= i * 100000000) {
            ans = fact[i];
            j = i * 100000000;
        }
    }
    // print("for n", n, " starting from", j, " ans", ans);
    for (++j; j <= n; ++j) {
        ans = (ans * j) % m;
    }
    return ans;
}

ll ch(ll n, ll k) {
    ll ans = f(n);
    ll x= f(k);
    ll y = f(n-k);
    ll t = pw((x * y) % m, m-2);
    return (ans * t) % m;
}

int main() {
    ll n, a, b;
    cin >> n >> a >> b;


    ll t1, t2, t3;
    t1 = pw(2, n);
    // print("2*n", t1);

    /*ll fn = f(n);
    print("f(n)", fn);
    for (int i = 1; i < 10; ++i) {
        print("fact", 100000000 * i, f(100000000 * i));
    }*/
    /*t2 = ch(n, a);
    print("C_n^a", t2);
    t3 = ch(n, b);
    print("C_n^b", t3);*/

    ll tmp;
    ll f_n = f(n);
    // print("f(n)", f_n);

    ll f_a = f(a);
    // print("f(a)", f_a);
    ll f_n_a = f(n-a);
    // print("f(n-a)", f_n_a);
    tmp = pw((f_n_a * f_a) % m, m-2);
    t2 = (f_n * tmp) % m;
    // print("C_n^a", t2);

    ll f_b = f(b);
    // print("f(b)", f_b);
    ll f_n_b = f(n-b);
    // print("f(n-b)", f_n_b);
    tmp = pw((f_n_b * f_b) % m, m-2);
    t3 = (f_n * tmp) % m;
    // print("C_n^b", t3);

    // print(pw(2, n), ch(n, a), ch(n, b));
    ll ans = t1 - t2 - t3 - 1;
    ans %= m;
    ans = (ans + m) % m;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
//@alok__10
#include <bits/stdc++.h>
using namespace std;
#define fastio      ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define MOD         1000000007
#define pie         3.141592653
#define ll          long long
#define lli         long long int
#define ulli        unsigned long long int
#define vi          vector<int>
#define vvi         vector<vi>
#define vlli        vector<lli>
#define vll         vector<ll>
#define pb          push_back
#define uset        unordered_set
#define useti       unordered_set<int>
#define umap        unordered_map
#define loop(i,n)   for(int i=0;i<n;i++)
#define clr(a,x)    memset(a,x,sizeof(a))
#define all(a)      a.begin(),a.end()
#define mp          make_pair
#define Pi          pair<int, int>
#define ppi         pair<ll,ll>
#define u_b         upper_bound
#define l_b         lower_bound
#define b_s         binary_search
bool prime(ll a) {
    if (a <= 1)return 0;
    if (a == 2 || a == 3)return 1;
    if (a % 2 == 0 || a % 3 == 0)return 0;
    for (int i = 5; i <= sqrt(a); i += 6) {
        if (a % i == 0 || a % (i + 2) == 0)return 0;
    }
    return 1;
}
bool cmp(pair<ll, ll>& p1, pair<ll, ll>&p2) {
    if (p1.first < p2.first)return 0;
    if (p1.first == p2.first)
        if (p1.second > p2.second)return 0;
    return 1;
}
//solution goes below
// -----------------------------------------------------------------------------------------------------------------------------------







int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("tin.txt", "r", stdin);
    freopen("tout.txt", "w", stdout);
#endif








    // int t;
    // cin >> t;
    // while (t--) {
    //     ll n;
    //     cin >> n;
    //     if (n < 31) {
    //         cout << "NO" << endl;
    //         continue;
    //     }
    //     cout << "YES" << endl;
    //     // cout << (2 * 3) << " " << (2 * 5) << " " << (2 * 7) << " ";
    //     ll x = (n - ((2 * 3) + (2 * 5) + (2 * 7)));
    //     ll a, b, c;
    //     a = (2 * 3);
    //     b = (2 * 5);
    //     c = (2 * 7);
    //     if (x == a || x == b || x == c) {
    //         cout << a << " " << b << " " << c + 1 << " " << x - 1 << endl;
    //         continue;
    //     }
    //     cout << a << " " << b << " " << c << " " << x << endl;


    // }
    ll k;
    cin >> k;
    ll m = 0;
    ll ans = -1;
    ll i = 0;
    while (i < 1000000) {
        i++;
        m = (m * 10 + 7) % k;
        if (!m) {
            ans = i;
            break;
        }
    }
    cout << ans;



















#ifndef ONLINE_JUDGE
    cout << "\n\nTime lap: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
#endif
    return 0;
}
//-----------------------------------------------------------------------------------------------------------------------------






















Measured memory_bytes: 3692
#include<stdio.h>
int main()
{
  int a,b,c=0,i,j;
  scanf("%d",&a);
  for(i=1;i<=9;i++)
    for(j=1;j<=9;j++)
    {
      if(i*j==a){c=1;break;}
    }
  if(c==1)printf("Yes\n");
  else printf("No\n");
  return 0;
}

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




int main() {

  int N,M,C;
  int B[110];
  int A[110][110];
  cin >> N >> M >> C;
  for(int i=0;i<M;i++){
    cin >> B[i];
  }

  for(int i=0;i<N;i++){
    for(int j =0;j<M;j++){
      cin >> A[i][j];
    }
  }

  int ans = 0;

  for(int i=0;i<N;i++){
    int sum = C;
    for(int j=0;j<M;j++){
      sum += (A[i][j]*B[j]);
    }
    if(sum > 0) ans++;
  }



  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<set>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<iomanip>
#define INF 1e9
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  return s;
}

template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
  s << vv[i] << endl;
  }
  return s;
}

int N;
vector<vector<int>> d;
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin >> N;
  for(int n = 0; n < N ; n++ ){
    int x,y,h;
    cin >> x >> y >> h;
    d.push_back({x,y,h});
  }
  for(int cx = 0 ; cx <= 100 ; cx++ ){
    for(int cy = 0 ; cy <= 100 ; cy++ ){
      for(int i = 0 ; i < N ; i++){
        if(d[i][2] <= 0){
          continue;
        }
        int h = d[i][2] + abs(cx - d[i][0]) + abs(cy - d[i][1]);
        //check validity
        bool is_valid = true;
        for(int n = 0 ; n < N ; n++){
          if(max(h - abs(cx - d[n][0]) - abs(cy - d[n][1]),0) != d[n][2]){
            is_valid = false;
            break;
          }
        }
        if(is_valid == true){
          cout << cx << " " << cy << " " << h << endl;
          return 0;
        }
      }
    }
  }

  return 0;
}


Measured memory_bytes: 256