akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <sstream>
#include <bitset>
using namespace std;
#define INF	100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define rep(i,n) for(int i = 0; i < n; i++)
#define SORT(x) sort((x).begin(), (x).end())
#define clr(a,b) memset((a),(b),sizeof(a))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<P> Vp;
typedef priority_queue<P, vector<P>, greater<P> > PQ;

int dice[100][1000001];

double A(int x, int y){
	int ret = 1;
	rep(i,x){
		ret *= y;
	}
	return (double)ret;
}

int main(){
	int n, m, k;
	while(scanf("%d%d%d", &n, &m, &k),n||m||k){
		double ans = 0.0;
		rep(i,n) rep(j,n*m+1) dice[i][j] = 0;
		for(int i = 1; i <= m; i++) dice[0][i] = 1;
		for(int i = 1; i < n; i++){
			for(int j = 1; j <= n*m; j++){
				for(int k = 1; k <= m; k++){
					dice[i][j+k] += dice[i-1][j];
				}
			}
		}
		int f = 0;
		for(int i = 0; i <= k; i++){
			f += dice[n-1][i];
		}
		ans += (double)f;
		for(int i = 1; i <= n*m-k; i++){
			ans += (double)dice[n-1][i+k]*i;
		}
		ans /= A(n,m);
		printf("%.9f\n", ans);
	}
}

Measured memory_bytes: 42216
#include "bits/stdc++.h"
#include<assert.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
#define MRE assert(0);
const int inf = 1e17;
const int mod =998244353;
typedef pair<int, int> P;
struct edge {
	int to, dir;
};
vector<edge>G[100006];
vector<int>cn[100006];
int a[100006], b[100006];
int d[100006], ced[100006];
int par[100006], siz[100006];
void init(int n) {
	rep(i, n) {
		par[i] = i; siz[i] = 1;
	}
}
int find(int x) {
	if (x == par[x])return x;
	return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x); y = find(y);
	if (x == y)return;
	if (siz[x] > siz[y])swap(x, y);
	par[x] = y;
	siz[y] += siz[x];
}
void dfs(int now, int label) {
	for (auto e : G[now]) {
		int nl = (label + 3 + e.dir) % 3;
		int nv = e.to;
		if (!(d[nv] & (1 << nl))) {
			d[nv] += (1 << nl);
			dfs(nv, nl);
		}
	}
	return;
}
signed main() {
	int n, m; cin >> n >> m;
	init(n);
	rep(i, m) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		G[a[i]].push_back({ b[i],1 });
		G[b[i]].push_back({ a[i],-1 });
		unite(a[i], b[i]);
	}
	rep(i, m) {
		ced[find(a[i])]++;
	}
	rep(i, n) {
		if (!d[i]) {
			d[i] = 1;
			dfs(i, 0);
		}
		cn[find(i)].push_back(d[i]);
	}
	int ans = 0;
	
	rep(i, n) {
		vector<int>cnt(8);
		for (int e : cn[i]) {
			rep(j, 8) {
				if ((j&e)==j)cnt[j]++;
			}
		}
		if (!cnt[1] || !cnt[2] || !cnt[4])ans += ced[i];
		else ans+= cnt[1] * cnt[2] + cnt[2] * cnt[4] + cnt[4] * cnt[1] -2* cnt[7] * cnt[7];
		
	}
	cout << ans << endl;
}

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

using namespace std;

void ng(){
	cout << "Impossible" << endl;
	exit(0);
}

#define INF (1<<29)

int a, b;
int d[108][108];
int c[108][108];

int main(){
	cin >> a >> b;
	for(int i = 1;i <= a;i++){
		for(int j = 1;j <= b;j++){
			cin >> d[i][j];
		}
	}

	for(int i = 0;i <= 100;i++){
		for(int j = 0;j <= 100;j++){
			for(int x = 1;x <= a;x++){
				for(int y = 1;y <= b;y++){
					c[i][j] = max(c[i][j], d[x][y] - x*i - y*j);
				}
			}
		}
	}

	for(int x = 1;x <= a;x++){
		for(int y = 1;y <= b;y++){
			int dist = INF;
			for(int i = 0;i <= 100;i++){
				for(int j = 0;j <= 100;j++){
					dist = min(dist, c[i][j] + x*i+y*j);
				}
			}
			if(dist != d[x][y])ng();
		}
	}
	cout << "Possible" << endl;
	cout << 202 << " " << 101*101 + 200 << endl;
	for(int i = 0;i <= 100;i++){
		int u = i+1;
		for(int j = 0;j <= 100;j++){
			int v = j + 102;
			cout << u << " " << v << " " << c[i][j] << endl;
		}
	}
	for(int i = 0;i < 100;i++){
		int u = i + 1;
		int v = u + 1;
		cout << u << " " << v << " " << "X" << endl;
	}
	
	for(int i = 0;i < 100;i++){
		int v = i + 102;
		int u = v + 1;
		cout << u << " " << v << " " << "Y" << endl;
	}
	cout << 1 << " " << 102 << endl;
	return 0;
}

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

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

  bool ans = true;

  if (c < d) {
    for (int i = a; i < d-1; i++) {
      if (s.at(i) == '#' && s.at(i+1) == '#') {
        ans = false;
      }
    }
  }

  else  {
    bool flag_a = false;
    for (int j = b; j < d+1; j++) {
      if (s.at(j-1) == '.' && s.at(j) == '.' && s.at(j+1) == '.') {
        flag_a = true;
      }
    }

    bool flag_b = true;
    for (int k = a; k < d-1; k++) {
      if (s.at(k) == '#' && s.at(k+1) == '#') {
        flag_b = false;
      }
    }

    if (flag_a && flag_b) {
      ans = true;
    }
    else {
      ans = false;
    }
  }

  if (ans) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int n;
void dfs(string s,char nw)
{
	if(s.size()==n)
	{
		cout<<s<<endl;
		return ;
	}
	for(char i='a';i<nw;i++)
		dfs(s+i,nw);
	dfs(s+nw,nw+1);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n;
	dfs("",'a');
	return 0;
}




Measured memory_bytes: 1536
L, R = map(int, input().split(" "))

if R - L > 2019:
    print(0)
else:
    ans = 2018
    for l in range(L, R+1):
        for r in range(l+1, R+1):
            t = (l * r) % 2019
            if ans > t:
                ans = t
    print(ans)

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

int main() {
	double a=0.0, b=0.0, sum=0.0, sumw=0.0;
	double cnt = 0.0;
	while(scanf("%lf,%lf",&a,&b)!=EOF){
	 sum=sum+a*b;
	 sumw=sumw+b;
	 cnt=cnt+1.0;
	 }

	cout << sum << endl;
	cout << (int) floor((sumw / cnt) + 0.5) << endl;
}

Measured memory_bytes: 3284
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int[][] a = new int[2][N];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < N; j++) {
                a[i][j] = scan.nextInt();
            }
        }
        int[][] s = new int[2][N+1];
        s[0][0] = 0;
        for (int i = 0; i < N; i++) {
            s[0][i+1] = s[0][i]+ a[0][i];
            s[1][i+1] = s[1][i]+ a[1][i];
        }
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            int t = s[0][i]-s[0][0] + s[1][N]-s[1][i-1];
            answer = Math.max(t, answer);
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 21844
n, l = map(int, input().split())

tastes = [l+i-1 for i in range(1, n+1)]
if 0 in tastes:
    print(sum(tastes))
else:
    if tastes[-1] > 0:
        print(sum(tastes) - tastes[0])
    else:
        print(sum(tastes) - tastes[-1])

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

int main() {
  int n; cin>>n;
  vector<int> ans(n);
  
  for (int i=0; i<n-1; i++){
    int a; cin>>a;
    ans[a-1]+=1;
  }
  
  for (auto d : ans){
    cout<<d<<endl;
  }
}

Measured memory_bytes: 4008
#include <bits/stdc++.h>
using namespace std;
#define MAX 255

int A[MAX];

int main(void) {
	int H, i;
	cin >> H;
	for (i = 1; i <= H; i++)
		cin >> A[i];
	for (i = 1; i <= H; i++) {
		cout << "node " << i << ": key = " << A[i] << ", ";
		if (i / 2 >= 1) 
			cout << "parent key = " << A[i / 2] << ", ";
		if (i * 2 <= H)
			cout << "left key = " << A[i * 2] << ", ";
		if (i * 2 + 1 <= H)
			cout << "right key = " << A[i * 2 + 1] << ", ";
		cout << endl;
	}
}


Measured memory_bytes: 3112
package main

import (
	"fmt"
	"math"
)

var A, B, C, D int
var ans int

func main() {
	fmt.Scan(&A, &B, &C, &D)
	fmt.Println(max(A*B, C*D))
}

/*  ----------------------------------------  */
func lcm(x, y uint64) uint64 {
	return (x / gcd(x, y)) * y
}

func gcd(x, y uint64) uint64 {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

func combination(x, y int) int {
	return permutation(x, y) / permutation(y, y)
}

func permutation(x, y int) int {
	var ans int = 1
	for i := x - y; 0 < i; i-- {
		ans *= i
	}
	return ans
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }

type XY struct {
	x int
	y int
}

type SortBy [][]int

func (a SortBy) Len() int      { return len(a) }
func (a SortBy) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool {
	return a[i][1] < a[j][1]
}


Measured memory_bytes: 512
#include <cstdio>
#include <cmath>
#include <stack>
#include <algorithm>
using namespace std;

void getType(const double &a) {
    if (a <= 48) printf("light fly\n");
    else if (a > 48 && a <= 51) printf("fly\n");
    else if (a > 51 && a <= 54) printf("bantam\n");
    else if (a > 54 && a <= 57) printf("feather\n");
    else if (a > 57 && a <= 60) printf("light\n");
    else if (a > 60 && a <= 64) printf("light welter\n");
    else if (a > 64 && a <= 69) printf("welter\n");
    else if (a > 69 && a <= 75) printf("light middle\n");
    else if (a > 75 && a <= 81) printf("middle\n");
    else if (a > 81 && a <= 91) printf("light heavy\n");
    else printf("heavy\n");
}

int main() {
    double n;
    while(scanf("%lf", &n) != EOF) {
        getType(n);
    }

    return 0;
}



Measured memory_bytes: 2572
// Problem : D - Div Game
// Contest : AtCoder - AtCoder Beginner Contest 169
// URL : https://atcoder.jp/contests/abc169/tasks/abc169_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;	

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> para;
const ll inf = 1e18 + 7;
const ll maxN = 1e6 + 5;
const ll MOD = 1e9 + 7;

// sprawdz MODULO!
int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n; cin >> n;
	int ans = 0;
	ll cp_n = n;
	for (ll i = 2; i * i <= cp_n; i++) {
		int ile = 0;
		while (n % i == 0) {
			ile++;
			n /= i;
		}
		int sum = 0;
		RI(i, 64) {
			sum += i;
			if (ile < sum) {
				ans += i - 1;
				break;
			}
		}
	}
	if (n != 1) ans++;
	cout << ans;
	return 0;
}
 


Measured memory_bytes: 3648
use proconio::{fastout, input};
use proconio::marker::Chars;

#[fastout]
fn main() {
  input! {
    a: i64,
    s: Chars,
  }
  let mut b = 0;
  for c in s{
    if let Some(d) = c.to_digit(10) {
  		b = b * 10 + d;
	}
  }
  println!("{}", a * b as i64 /100);
}

Measured memory_bytes: 2160
main = do
  [x,y] <- map read . words <$> getLine
  print (scalc x y)
 
scalc x y
 | x <= y = d + sign1
 | otherwise = d + 1 + sign2 - (if y==0 || x==0 then 1 else 0)
  where
    d = abs (abs x - abs y)
    sign1 = if signum x == negate (signum y) then 1 else 0
    sign2 = if signum x == negate (signum y) then 0 else 1

Measured memory_bytes: 508
// CODE FESTIVAL 2016 qual B
// C - Gr-idian MST

#include <cstdio>
#include <algorithm>
#include <utility>
#define MAX_W 100000
#define MAX_H 100000
using namespace std;

typedef long long int ll;


int W, H;
pair<int, int> costs[MAX_W + MAX_H];
int cnt[2];
ll ans;

int main() {

  scanf("%d %d", &H, &W);
  for (int x = 0; x < W; x++) {
    scanf("%d", &costs[x].first);
    costs[x].second = 0;
  }
  for (int y = 0; y < H; y++) {
    scanf("%d", &costs[W + y].first);
    costs[y].second = 1;
  }

  sort(costs, costs + W + H);

  cnt[0] = 0;
  cnt[1] = 0;
  ans = 0;
  for (int i = 0; i < W + H; i++) {
    if (costs[i].second == 0) {
      ans += (ll)(H + 1 - cnt[1]) * (ll)costs[i].first;
      cnt[0]++;
    } else {
      ans += (ll)(W + 1 - cnt[0]) * (ll)costs[i].first;
      cnt[1]++;
    }
  }
  printf("%lld\n", ans);

  return 0;

}




Measured memory_bytes: 1664
#include <stdio.h>
 
int main(){
 int a,b;
 scanf("%d",&a);
 scanf("%d",&b);
 if(a<b){
  printf("a < b\n");
 }
 else if(a==b){
  printf("a == b\n");
 } 
 else{
  printf("a > b\n");
 }
 return 0;
}
 

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

bool solve(int n, int m){
  vector<string> vec(n);
  rep(i,n) cin>>vec[i];

  const int dx[] = {0,1,0,-1};
  const int dy[] = {-1,0,1,0};

  const int tx[] = {n-1, n-1, 0, 0};
  const int ty[] = {0, m-1, m-1, 0};

  int dir=0;
  int x=0, y=0;
  rep(i,4){
    auto ok = [&](int p, int q){
      return p>=0 && q>=0 && p<n && q<m && (vec[p][q]=='.' || vec[p][q]==i);
    };
    int step = 0;
    while(x!=tx[i] || y!=ty[i]){
      int nd = 0;
      while(nd<4 && !ok(x+dx[(dir+nd)%4], y+dy[(dir+nd)%4])) nd++;
      if(nd==4) return false;
      x += dx[(dir+nd)%4];
      y += dy[(dir+nd)%4];
      dir = (dir+nd+3)%4;
      vec[x][y] = i;
      if(step++ > n*m) return false;
    }
  }
  return true;
}

int main(){
  int n,m;
  while(cin>>n>>m, n|m){
    if(solve(n,m)) cout << "YES" << endl;
    else cout << "NO" << endl;
  }

  return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(3*n);
    for(int i=0; i<3*n; i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end(),greater<int>());
    ll sum=0;
    for(int i=1; i<2*n+1; i+=2){
        sum+=a[i];
    }
    cout << sum << endl;
}

Measured memory_bytes: 1408
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
      return Array.new(size1){init}
  else
      return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N=gets.to_i
c=get_nsp
r=array(N+1,0)
w=array(N+1,0)
N.times do|i|
  r[i+1]=r[i]
  r[i+1]+=1 if c[N-1-i]=="R"
end
N.times do|i|
   w[i+1]=w[i]
   w[i+1]+=1 if c[i]=="W"
end
if w[N]==N or r[N]==N
    puts 0
    exit
end
ans=INF
(N+1).times do|i|
  ans=min(ans,(r[i]-w[N-i]).abs+min(r[i],w[N-i]))
end
puts ans

Measured memory_bytes: 33812
#include<iostream>
#include<iomanip>
#include<set>
#include<vector>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;


int main(void)
{
  string s;
	int cou = 0;
	cin >> s;
	int ans = 0;
	rep(i,s.size()){
		if((0 == i%2 && '1' == s[i]) || (0 != i%2 && '0' == s[i])) cou++;
		if((0 == i%2 && '0' == s[i]) || (0 != i%2 && '1' == s[i])) ans++;
	}
	ans = min(ans,cou);

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


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr);
#endif
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" ";cout<<endl;}
void solve(){
   int n;
   cin>>n;
   int val=1;
  for(int i=2;i<=n;i++){
    int ans=i;
    if(i*i>n){break;}
    while(ans*i<=n)ans*=i;
    val=max(ans,val);
  }  
  cout<<val<<endl;
}
int32_t main(){
  IOS;
  solve();
  #ifdef LOCAL_DEFINE
  cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
  #endif
}

Measured memory_bytes: 256
//                                                   ¯\_(ツ)_/¯
  //#pragma GCC optimize("Ofast")
 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long
#define pi pair<int,int>
const int N=1e6+5,MOD=1e9+7;

using namespace std;

int n,k;
bool dp[N];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	
	scanf("%d %d",&n,&k);

	dp[0]=0;

	for(int i = 1;i<=k;i++)dp[i]=1;
	std::vector<int> a(n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);

	for(int i=1;i<=k;i++){
		bool gg = false;
		for(int j=0;j<n;j++){

			if(a[j]<=i && !dp[i-a[j]])gg=true;
		}

		if(!gg)dp[i]=false;
	}

	if(dp[k])printf("First\n");
	else printf("Second\n");
}

Measured memory_bytes: 384
# 入力
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))


MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# LCSと同様にDPで解を求める
dp = [[ModInt(1) for _ in range(M + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, M + 1):
        dp[i][j] = (
            dp[i - 1][j] + dp[i][j - 1] if S[i - 1] == T[j - 1] else
            (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1])
        )
ans = dp[N][M]

# 出力
print(ans)


Measured memory_bytes: 574976
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n) ; i++)
#define rrep(i,n) for(int i = n-1; i >= 0 ; i--)
using ll = long long;
constexpr auto INFI = 2147483647;
const ll INFL = 9223372036854775807;
const ll MOD = 1000000007;

int pow_two(int n){
  int tmp = 1;
  rep(i,n) tmp = (tmp*2) % MOD;
  return tmp;
}

int main(){
  map<pair<ll,ll>, pair<int,int>> fish_var;
  ll n, a, b, gcd_ab, tmp_a;
  ll zero = 0;
  pair<ll,ll> fish_vec;
  cin >> n;
  rep(i,n){
    bool isInv = false;
    cin >> a >> b;
    if (a == 0 && b == 0) {
      zero++;
      continue;
    } else if (a == 0) {
      a = 1;
      b = 0;
      isInv = true;
    } else if (b == 0) {
      a = 1;
      b = 0;
    } else {
      gcd_ab = abs(__gcd(a, b));
      a /= gcd_ab;
      b /= gcd_ab;
      if (a < 0) {
        a *= -1;
        b *= -1;
      }
      if (b < 0){
        isInv = true;
        tmp_a = a;
        a = -1 * b;
        b = tmp_a;
      }
    }
    if (isInv){
      fish_var[make_pair(a, b)].second++;
    } else{
      fish_var[make_pair(a, b)].first++;
    }
  }

  ll ans = 1;

  for (auto p : fish_var) {
    int s = p.second.first;
    int t = p.second.second;
    ll now = (1 + (pow_two(s) - 1) + (pow_two(t) - 1));
    ans = ((ans * now) % MOD) + MOD;
  }
  ans =  (ans + zero - 1) % MOD;
  cout << ans << endl;
}

Measured memory_bytes: 15996
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define ll long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define bs binary_search
#define mp make_pair
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ld long double
#define meme(a,no)  memset(a,no,sizeof(a))
using namespace std; 

const int INF=1e9+7;

/*const int N=1000+5;

int x;

//const int mod=998244353;

//const int N=100000+9;

vector<vector<int>>v(N);

int vis[N]={0};

int level[N];*/

long long binpow(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}

long long binpow_mod(ll a,ll b,ll c){
    ll res=1;
    while(b>0){
        if(b&1){
            res=res*a%c;
        }
        a=a*a%c;
        b>>=1;
    }
    return res;
}

/*void dfs(int a){
    vis[a]=1;
    for(auto x:v[a]){
        if(!vis[x]){
            sz++;
            dfs(x);
        }
    }
}*/
vector<bool>v;
vector<int>isfactor;

void Seive(int n){
    v.assign(n+1,true);
    isfactor.assign(n+1,0);
    v[0]=false; v[1]=false;
    for(int i=2;i<=n;i++){
        if(v[i]){
            isfactor[i]=i;
            for(int j=i*i;j<=n;j+=i){
                if(v[j]){
                    v[j]=false;
                    isfactor[j]=i;
                }
            }
        }
    }
    
}

int32_t main(){
    ios
    int T;
    //cin>>T;
    T=1;
    while(T--){
        string s,t;
        cin>>s>>t;
        int y=s.length();
        int x=t.length();
        int a[x+1][y+1];
        int i,j;
        vector<char>ch;
        meme(a,0);
        for(i=1;i<=x;i++){
            for(j=1;j<=y;j++){
                if(t[i-1]==s[j-1]){
                    //cout<<s[j-1]<<endl;
                    a[i][j]=max(a[i-1][j-1]+1,max(a[i-1][j],a[i][j-1]));
                    
                }
                else a[i][j]=max(a[i][j-1],a[i-1][j]);
            }
        }
        int px=x,py=y;
        while(a[px][py]!=0){
            if(a[px][py]-1==a[px-1][py-1] && t[px-1]==s[py-1]){
                ch.pb(t[px-1]);
                //cout<<t[px-1]<<endl;
                px--;
                py--;
                continue;
            }
            if(a[px][py]==a[px-1][py]){
                px--;
                continue;
            }
            if(a[px][py]==a[px][py-1]){
                py--;
                continue;
            }
        }
        int pos=(int)ch.size()-1ll;
        if(pos>=0){
            for(j=pos;j>=0;j--){
                cout<<ch[j];
            }  
        }
        cout<<endl;
        
    }
    
    
}

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int n,L;
    cin >>n >>L;
    vector<int> a(n);
    rep(i,n) scanf(" %d", &a[i]);

    int idx=-1;
    rep(i,n-1)
    {
        if(a[i]+a[i+1]>=L)
        {
            idx=i;
            break;
        }
    }

    if(idx>=0)
    {
        printf("Possible\n");

        vector<int> ans;
        rep(i,idx) ans.pb(i+1);
        for(int i=n-2; i>=idx; --i) ans.pb(i+1);

        rep(i,ans.size()) printf("%d\n", ans[i]);
    }
    else printf("Impossible\n");

    return 0;
}


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

vector<vector<ll> > h(100000,vector<ll> (3));
vector<vector<ll> > dp(100000,vector<ll> (3,-1));
ll n;

ll foo(ll start, ll prev){
    if(start == n) return 0;
    if(dp[start][prev]!=-1) return dp[start][prev];
    if(prev == 0){
        dp[start][prev] = max(h[start][1]+foo(start+1,1),h[start][2]+foo(start+1,2));
    }
    else if(prev == 1){
        dp[start][prev] = max(h[start][0]+foo(start+1,0),h[start][2]+foo(start+1,2));
    }
    else if(prev == 2){
        dp[start][prev] = max(h[start][1]+foo(start+1,1),h[start][0]+foo(start+1,0));
    }
    return dp[start][prev];
}

int main(){
    ll a1;
    cin>>n;
    for(a1=0;a1<n;++a1){
        cin>>h[a1][0]>>h[a1][1]>>h[a1][2];
    }
    ll x1=foo(0,0);
    ll x2=foo(0,1);
    cout<<max(x1,x2);
    return 0;
}

Measured memory_bytes: 15872
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int h, w; cin >> h >> w;
  set<pair<int, int>> st;
  multiset<int> dist;
  REP(j, w) {
    st.emplace(j, j);
    dist.emplace(0);
  }
  FOR(r, 1, h + 1) {
    int a, b; cin >> a >> b; --a; --b;
    int mx = -1;
    auto t = st.lower_bound({b + 1, -1});
    for (auto it = st.lower_bound({a, -1}); it != t; it = st.erase(it)) {
      chmax(mx, it->second);
      dist.erase(dist.lower_bound(it->first - it->second));
    }
    if (mx != -1 && b + 1 < w) {
      st.emplace(b + 1, mx);
      dist.emplace(b + 1 - mx);
    }
    cout << (dist.empty() ? -1 : *dist.begin() + r) << '\n';
  }
  return 0;
}


Measured memory_bytes: 22352
n=int(input())
while n>0:
    m=1000-n
    a=int(m/500)
    b=int(int(m%500)/100)
    c=int(int(m%100)/50)
    d=int(int(m%50)/10)
    e=int(int(m%10)/5)
    f=int(int(m%5)/1)
    print(a+b+c+d+e+f)
    n=int(input())
    


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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> l(N);
  for (int i = 0; i < N; i++) cin >> l[i];

  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());

  int ans = 0;

  for (int i = 0; i < K; i++) ans += l[i];

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#define pb push_back 
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
typedef long long ll;
const int INF = 100000000, mod = 1000000007;
const double pi = 3.14159265;
const ll LLINF = 1LL << 50;
using namespace std;


int main() {
    int n, a[200005];
    cin >> n;
    for (int i = 0; i < n; i++)cin >> a[i];
    int r = 0, nowsum = 0, nowxor = 0;
    ll ans = 0;
    for (int l = 0; l < n; l++) {
        while (r < n && (nowsum + a[r]) == (nowxor^a[r])) {
            nowsum = nowsum + a[r];
            nowxor = nowxor^a[r];
            r++;
        }
        ans += r - l;
        nowsum -= a[l];
        nowxor ^= a[l];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
module Main where
import qualified Control.Monad as C
import qualified Data.Char as C
import qualified Data.List as L
import qualified Data.Map as M
import qualified Data.Array as A

int = read :: String -> Integer
getWord :: IO String
getWord = do
  c <- getChar
  if C.isSpace c
  then
    return []
  else do
    ws <- getWord
    return (c:ws)
getInt = fmap int getWord
replace pred a = map (\x -> if pred x then a else x)

main = interact $ printer . solver . parser
parser = map int . words
printer = unlines . (:[]) . show

solver (a:b:c:d:ss) = result -- [uc,cc,dc,cdc,result]
  where
    result = uc - cc - dc + cdc

    uc = b - a + 1

    cc =
      if a <= (b`div`c)*c && (b`div`c)*c <= b
      then
        b `div` c + 1 -
        (a `div` c + if a `mod` c == 0 then 0 else 1)
      else
        0

    dc = 
      if a <= (b`div`d)*d && (b`div`d)*d <= b
      then
        b `div` d + 1 -
        (a `div` d + if a `mod` d == 0 then 0 else 1)
      else
        0

    cd = c `div` ( gcd c d ) * d
    cdc = 
      if a <= (b`div`cd)*cd && (b`div`cd)*cd <= b
      then
        b `div` cd + 1 -
        (a `div` cd + if a `mod` cd == 0 then 0 else 1)
      else
        0



Measured memory_bytes: 508
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, A, B = LI()
V = LI()

MAX = 51
finv = [None] * MAX


def comb_init():
    finv[0] = 1
    for i in range(1, MAX):
        finv[i] = finv[i - 1] * i


def comb(n, k):
    return finv[n] // finv[k] // finv[n - k]


def main():
    comb_init()
    V.sort(reverse=True)
    s = sum(V[:A])
    mx = s // A if s % A == 0 else s / A
    print(mx)
    if A == N or V[A - 1] > V[A]:
        print(1)
        return
    
    x = V.count(V[A])
    ans = 0
    if mx == V[A]:
        for i in range(A, B + 1):
            ans += comb(x, i)
    else:
        y = V[:A].count(V[A])
        ans = comb(x, y)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <cstdio>
#include <algorithm>
typedef long long int64;

int64 n, a, b, c, d;

inline bool intersects(int64 l1, int64 r1, int64 l2, int64 r2) {
    if (l1 > l2) std::swap(l1, l2), std::swap(r1, r2);
    return (r1 >= l2);
}

int main()
{
    scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
    n -= 2;
    b -= a;

    for (int64 i = 0; i < n; ++i) {
        if (intersects((i + 1) * c, (i + 1) * d, b + (n - i) * c, b + (n - i) * d)) {
            puts("YES"); return 0;
        }
    }

    puts("NO"); return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
ll cnt[100010];
int main()
{
    int n; ll k;
    cin>>n>>k;
  if(n==1){
    cout<<k<<endl;
    return 0;
  }
    for(int i=0; i<n-1; i++){
        int a, b; cin>>a>>b;
        a--; b--;
        cnt[a]++; cnt[b]++;
    }
    ll ans=k*(k-1)%MOD;
    for(int i=0; i<n; i++){
        for(ll j=0; j<cnt[i]-1; j++){
            ans*=(k-2-j);
            ans%=MOD;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main()
{
  int t,n;
  int s,f;
  int stu;
  cin>>t;
  while(t!=0){
    cin>>n;
    stu=0;
    for(int i=0;i<n;i++){
      cin>>s>>f;
      stu+=(f-s);
    }
    if(t<=stu)
      cout<<"OK\n";
    else
      cout<<t-stu<<'\n';
    cin>>t;
  }
  return 0;
}



Measured memory_bytes: 3108
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

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

class AX {
public:
	void solve(std::istream& in, std::ostream& out) {
        int a,b;
        in >> a >> b;
        out << max({a+b,a-b,a*b}) << endl;
	}
};


int main() {
	AX solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"strconv"
)

type Card struct {
	suit  string
	value int
}

func (c Card) inspect() string {
	return c.suit + strconv.Itoa(c.value)
}

func trace(arr []Card) {
	for i, card := range arr {
		if i == len(arr)-1 {
			fmt.Printf("%s\n", card.inspect())
		} else {
			fmt.Printf("%s ", card.inspect())
		}
	}
}

func isEqual(a, b []Card) bool {
	for i, e := range a {
		if e.inspect() != b[i].inspect() {
			return false
		}
	}
	return true
}

func bubbleSort(arr []Card, len int) []Card {
	change := true
	for i := 0; change; i++ {
		change = false
		for j := len - 1; j > i; j-- {
			if arr[j].value < arr[j-1].value {
				arr[j], arr[j-1] = arr[j-1], arr[j]
				change = true
			}
		}
	}
	trace(arr)
	return arr
}

func selectionSort(arr []Card, len int) []Card {
	for i := 0; i < len; i++ {
		minIndex := i
		for j := i + 1; j < len; j++ {
			if arr[j].value < arr[minIndex].value {
				minIndex = j
			}
		}
		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}
	trace(arr)
	return arr
}

func main() {
	var n int
	fmt.Scan(&n)
	cards := make([]Card, n)
	var tmp string
	for i := 0; i < n; i++ {
		fmt.Scan(&tmp)
		suit := string(tmp[0])
		value, _ := strconv.Atoi(string(tmp[1]))
		cards[i] = Card{suit, value}
	}
	bubble := make([]Card, n)
	copy(bubble, cards)
	bubble = bubbleSort(bubble, n)
	fmt.Println("Stable")

	selection := make([]Card, n)
	copy(selection, cards)
	selection = selectionSort(selection, n)
	if isEqual(bubble, selection) {
		fmt.Println("Stable")
	} else {
		fmt.Println("Not stable")
	}
}



Measured memory_bytes: 1172
#include<iostream>
#include<stdio.h>
#include<math.h>

using namespace std;

int main() {
	double a, b, C;
	
	cin >> a;
	cin >> b;
	cin >> C;
	
	//cout << 0.5 * a * b * sin(M_PI*C/180.0) << endl;
	//cout << a + b + sqrt(a*a+b*b-2*a*b*cos(M_PI*C/180.0)) << endl;
	//cout << b * sin(M_PI*C/180.0) << endl;
	
	printf("%f \n", 0.5 * a * b * sin(M_PI*C/180.0));
	printf("%f \n", a + b + sqrt(a*a+b*b-2*a*b*cos(M_PI*C/180.0)));
	printf("%f \n", b * sin(M_PI*C/180.0));
	
	return 0;
}

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

#define I cin
#define O cout
#define EN endl
#define ln cout<<endl
#define pb(a) push_back(a)

typedef unsigned long long int llint;

int n;
int i, j;
llint cnt = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

llint gcd(llint a, llint b)
{
  return (a % b ? gcd(b, a % b) : b);
}

int main()
{
  I >> n;

  llint a = 1, b = 1;
  for(i = 0; i < n; i++) {
    llint m;
    I >> m;
    b = gcd(a, m);
    a = a / b * m;
  }

  O << a << EN;
  
  return 0;
}


Measured memory_bytes: 256
var read = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
var obj;
var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  myerr("-----start-----");
  var start = new Date();
  Main();
  var end = new Date() - start;
  myerr("----- end -----");
  myerr("time : " + (end) + "ms");
});
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  var returnObj = {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(!this.hasNext()){throw "ArrayIndexOutOfBoundsException これ以上ないよ";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す 1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}
function Main(){
	var one = nextIntArray();
	var A = one[0];
	var B = one[1];
	var H = one[2];
	var M = one[3];
	var Akaku = ((H / 12) + ((M / 60) / 12));
	var Bkaku = (M / 60);
	var Atate = Math.sin(Akaku * Math.PI * 2) * A;
	var Ayoko = Math.cos(Akaku * Math.PI * 2) * A;
	var Btate = Math.sin(Bkaku * Math.PI * 2) * B;
	var Byoko = Math.cos(Bkaku * Math.PI * 2) * B;
	
	/*
	if(H < 12 && H >= 7){
		Ayoko *= -1;
	}else if(H == 6 && M != 0){
		Ayoko *= -1;
	}
	if(H >= 4 && H < 9){
		Atate *= -1;
	}else if(H == 3 && M != 0){
		Atate *= -1;
	}
	if(!(M >= 0 && M <= 30)){
		Byoko *= -1;
	}
	if(!(M >= 45 || M <= 15)){
		Btate *= -1;
	}*/
	myerr(Atate);
	myerr(Ayoko);
	myerr(Btate);
	myerr(Byoko);
	myout(Math.sqrt(Math.pow(Atate - Btate,2) + Math.pow(Ayoko - Byoko,2)));
}

Measured memory_bytes: 30380
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define ld long double
#define PI 3.141592653L
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll INF = (ll)1e18;
const int N = 5e5 + 5;
const ll MOD = 1e9+7;
 
int parent[N];
 
int gcd(int a, int b) { 
    if (a == 0) 
        return b;  
    return gcd(b%a, a);  
} 
   
int lcm(int a, int b) {  
    return (a*b)/gcd(a,b);  
} 
 
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
 
int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}
 
void Union(int x, int y) {
    int xPar = find(x), yPar = find(y);
    if(xPar != yPar) parent[xPar] = yPar;
}
 
ll nCr(ll n, ll r) {
    ll res = 1;
    for(ll i=1;i<=r;i++) {
        res = res * (n - r + i) / i;
        // is different from
        // res *= (n -r + i) / i;
    }
    return res;
}
 
int ask(int i, int j) {
    cout << "? " << i + 1 << ' ' << j + 1 << endl;
    int v;
    cin >> v;
    return v;
}

void solve() {
    int s;
    cin >> s;
    vector<ll> dp(s + 1, 0);
    dp[0] = 1;
    for(int i=1;i<=s;i++) {
        for(int j=i;j>=3;j--) {
            dp[i] = (dp[i] + dp[i-j]) % MOD;
        }
    }
    dp[s] %= MOD;
    cout << dp[s] << endl;
    return;
} 

int main()
{
    IOS
    //int t;
    //cin >> t;
    //while(t--) solve();
    solve();
    return 0; 
}


Measured memory_bytes: 3640
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto nm = readln.split.to!(long[]);
    auto N = nm[0];
    auto M = nm[1];
    if (N > M) swap(N, M);
    if (N == 1) {
        writeln(M == 1 ? 1 : M-2);
    } else if (N == 2) {
        writeln(0);
    } else {
        writeln((N-2) * (M-2));
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(double i=(a);i<(b);i++)
#define REP(i,n) rep(i,0,n)

int main()
{
    int w,s,n,e,up,down;
    cin>>up>>s>>e>>w>>n>>down;
    char st;
    while(cin>>st)
    {
        int temp;
        if(st=='S')
        {
            temp=s;
            s=up;
            up=n;
            n=down;
            down=temp;
        }
        if(st=='N')
        {
            temp=n;
            n=up;
            up=s;
            s=down;
            down=temp;
        }
        if(st=='E')
        {
            temp=e;
            e=up;
            up=w;
            w=down;
            down=temp;
        }
        if(st=='W')
        {
            temp=w;
            w=up;
            up=e;
            e=down;
            down=temp;
        }
        if(st=='/n')break;
    }cout<<up<<endl;
}




Measured memory_bytes: 3116
//_nebula_
#include<bits/stdc++.h>
using namespace std;
#define int long  long
#define double long double
int t;
const int M=1e9+7;
int factt(int n)
{
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        ans*=i;
        ans=ans%M;
    }
    return ans;
}
int max(int a,int b,int c)
{
    return max(a,max(b,c));
}
int min(int a,int b,int c)
{
    return min(a,min(b,c));
}
int fspow(int x,int y)
{
    int ans;
    if(y==0) return 1;
    ans=fspow(x, y/2);
    if(y%2==0) return (ans*ans)%M;
    return (x*((ans*ans)%M))%M;;
}
int gcd(int x,int y)
{
    if(x<y) swap(x,y);
    if(y==0) return x;
    return gcd(x%y,y);
}
int p2(int x)
{
    int ans=0;
    while(x>=1)
    {
        ans++;
        x/=2;
    }
    return ans;
}
int v=0;
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    t=1;
    // freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //  cin>>t;
    // int tmp=t;
    while(t--)
    {
        int d,T,s;
        cin>>d>>T>>s;
        if(d<=s*T) cout<<"Yes\n";
        else cout<<"No\n";
    }
}



Measured memory_bytes: 3652
# include <iostream>
using namespace std ;
int main()
{
string s,n;
cin>>s>>n;
//for (int i=0; i<=3; i++)
if (s[0]==n[2] && s[1]==n[1] && s[2]==n[0]){
    cout<<"YES";
}
else
    cout<<"NO";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){	
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int x[5] = {0};
	REP(i, 6){
		cin >> x[i];
	}
	if(x[4]-x[0]>x[5]) cout << ":(" << '\n';
	else cout << "Yay!" << '\n';

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int MOD=1e9+7;
#ifndef HOME
#define cerr if(0)cerr
#endif

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    map<char,int>m;
    int p,q,r;
    cin>>p>>q>>r;
    int a[3];
    a[0]=p;
    a[1]=q;
    a[2]=r;
    sort(a,a+3);
    cout<<a[0]+a[1]<<endl;
    
    return 0;
    
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int n, h, w;
    cin >> n >> h >> w;
    cout << (n-h+1)*(n-w+1) << endl;
}


Measured memory_bytes: 256
import sys


fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = fin().rstrip("\n")[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
base = 1
for i, c in enumerate(S, start=1):
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
    base = base * 10 % 13
print(dp[-1][5])


Measured memory_bytes: 61532
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
constexpr auto mod = 1000000007;
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
const int MAX = 330000;
int fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int 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;
	}
}
int COMB(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
struct edge { int to, cost; };
class UnionFind {
protected:
	int* par, * rank, * size;
public:
	UnionFind(unsigned int size) {
		par = new int[size];
		rank = new int[size];
		this->size = new int[size];
		rep(i, size) {
			par[i] = i;
			rank[i] = 0;
			this->size[i] = 1;
		}
	}
	int find(int n) {
		if (par[n] == n)return n;
		return par[n] = find(par[n]);
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m)return;
		if (rank[n] < rank[m]) {
			par[n] = m;
			size[m] += size[n];
		}
		else {
			par[m] = n;
			size[n] += size[m];
			if (rank[n] == rank[m])rank[n]++;
		}
	}
	bool same(int n, int m) {
		return find(n) == find(m);
	}
	int getsize(int n) {
		return size[find(n)];
	}
};
signed main() {
	int n, m;
	cin >> n >> m;
	cout << comb(n, 2) + comb(m, 2) << endl;
	ggr
}


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

int main() {
  vector<vector<int>>c(3,vector<int>(3));
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++) cin>>c[i][j];
  }
  string ans="No";
    int a1=0;
    int b1=c[0][0]-a1;
    int b2=c[0][1]-a1;
    int b3=c[0][2]-a1;
    int a21=c[1][0]-b1;
    int a22=c[1][1]-b2;
    int a23=c[1][2]-b3;
    int a31=c[2][0]-b1;
    int a32=c[2][1]-b2;
    int a33=c[2][2]-b3;
    if((a21==a22 && a22==a23) && (a31==a32 && a32==a33)) ans="Yes";
  cout<<ans<<endl;
      
}


Measured memory_bytes: 256