akhauriyash/Code-Regression huggingface dataset:
/****************************
/////  Shubham Singhal
/////  LNMIIT
*****************************/
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// #include <functional> 
// using namespace __gnu_pbds;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define eb emplace_back
#define lwr lower_bound
#define upr upper_bound
#define pq priority_queue
#define umap unordered_map
#define rep(i,n) for(i=0; i<n;i++)
#define repp(i,a,n) for(i=a; i<n;i++)
#define precise(x) cout<<fixed<<setprecision(x)
#define all(x) x.begin(),x.end()
#define lcm(a,b) (a*b)/__gcd(a,b)
#define prn(x) cout<<x<<"\n"
#define prn2(x, y) cout<<x<<" "<<y<<"\n"
#define prn3(x, y, z) cout<<x<<" "<<y<<" "<<z<<"\n"
#define prn4(x, y, z, a) cout<<x<<" "<<y<<" "<<z<<" "<<a<<"\n"
#define prnv(x) for(auto i:x) cout<<i<<" "; cout<<"\n"
#define MOD 1000000007
#define MaX 300005
using namespace std;

 
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd; 
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pil> vpil;
typedef vector<pli> vpli;
typedef vector<pll> vpll;
const long long INF64 = 1e18;
clock_t time_p=clock();
void time()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
void doc()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
}
// typedef tree<int, null_type, less<int>, rb_tree_tag, 
//              tree_order_statistics_node_update> 
//     new_data_set; 
bool isprime(ll n) 
{ 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (ll i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
    return true; 
}


int main()
{
    fast();
    map<string,int> m;
    int n;
    cin>>n;
    string s;
    while(n--)
    {
        cin>>s;
        m[s]++;
    }
    cout<<"AC x "<<m["AC"]<<'\n';
    cout<<"WA x "<<m["WA"]<<'\n';
    cout<<"TLE x "<<m["TLE"]<<'\n';
    cout<<"RE x "<<m["RE"]<<'\n';
}


Measured memory_bytes: 3676
from typing import List


def insertion_sort(elems: List[int], interval: int) -> int:
    cnt = 0
    for i in range(interval, len(elems)):
        v = elems[i]
        j = i - interval
        while (j >= 0) and (elems[j] > v):
            elems[j + interval] = elems[j]
            j = j - interval
            cnt += 1
        elems[j + interval] = v
    return cnt


def get_intervals(num: int) -> List[int]:
    intervals = []
    h = 1
    intervals.append(h)
    while True:
        h = 3 * h + 1
        if h >= num:
            break
        intervals.append(h)
    return sorted(intervals, reverse=True)


if __name__ == "__main__":
    elem_num = int(input())
    elems = [int(input()) for elem in range(elem_num)]

    cnt = 0
    intervals = get_intervals(elem_num)
    for interval in intervals:
        cnt += insertion_sort(elems, interval)

    print(f"{len(intervals)}")
    print(" ".join([str(elem) for elem in intervals]))
    print(f"{cnt}")
    for elem in elems:
        print(f"{elem}")



Measured memory_bytes: 47024
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    int N;
    cin >> N;
    vector<int> A;
    int tmp;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        A.push_back(tmp);
    }
    int count = 0;
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        ans += (A[i] - 1);
    }
  	cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long v = sc.nextLong();
		long b = sc.nextLong();
		long w = sc.nextLong();
		long t = sc.nextLong();
		if(w >= v) {
			System.out.print("NO");
			System.exit(0);
		}

		long dis = (long)Math.abs(a - b);
		long num = v - w;
		num *= t;

		if(num >= dis) {
			System.out.print("YES");
		}else {
			System.out.print("NO");
		}
	}
}

Measured memory_bytes: 35832
x=int(input())
if 400<=x<=599:
       print(8)
elif 600<=x<=799:
        print(7)
elif 800<=x<=999:
        print(6)
elif 1000<=x<=1199:
        print(5)
elif 1200<=x<=1399:
        print(4)
elif 1400<=x<=1599:
        print(3)
elif 1600<=x<=1799:
        print(2)
elif 1800<=x<=1999:
        print(1)


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

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<long long> a(n + 1), b(m + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] += a[i - 1];
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    b[i] += b[i - 1];
  }
  int ans = 0;
  for (int i = 0; i <= n; i++) {
    if (a[i] > k) continue;
    int l = 0, r = m + 1, c;
    while (r - l > 1) {
      c = (l + r) / 2;
      ((a[i] + b[c] > k) ? r : l) = c;
    }
    if (ans < i + l) ans = i + l;
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  double sum = 0;
  for(int i = 0; i < N; i++) {
    int a;
    cin >> a;
    double b = a;
    sum += 1 / b;
  }
  double ans = 1 / sum;
  cout << fixed << setprecision(6) << ans << endl;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define sz(x) (int)((x).size())
# define F first
# define S second
# define pb push_back
# define ub upper_bound
# define lb lower_bound
# define all(x) x.begin(), x.end()
# define pqueue priority_queue
# define mset multiset
# define umap unordered_map
# define Speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
# define rep(i,n) for(int i=0;i<n;++i)
# define forn(i,n) for(int i=1;i<=n;++i)
# define lr(i,l,r) for(int i=l;(l>r?i>=r:i<=r);(l>r?--i:++i))

using namespace std;

template<class T> void umin(T &a,T b){a=min(a,b);}
template<class T> void umax(T &a,T b){a=max(a,b);}

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int dx[]={1,0,-1,0,-1,-1,1,1},dy[]={0,1,0,-1,-1,1,-1,1}; 
const int mod = 1e9+7;
const int N = 2e6+5;



void solve(){
	int n;
	cin>>n;
	int ans=-n;
	rep(i,n){
		int x;
		cin>>x;
		ans+=x;
	}
	cout<<ans;
}

int main(){
	Speed();
	int T=1; 
	//cin>>T;	
	while(T--)
		solve();
	return 0;
}

Measured memory_bytes: 3608
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using P   = pair<ll, ll>;
using mat = vector<vector<ll>>;
typedef string::const_iterator State;
class ParseError {};

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

constexpr ll INF = 1e16;
constexpr ll INM = 114514;
constexpr ll MOD = 1e9 + 7;
constexpr ld EPS = 1e-12;

template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, int t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll b) {
	if (a > 0) return a % b;
	if (a % b == 0) return 0;
	ll x = -a / b + 1;
	a += x * b;
	return a % b;
}
ll powm(ll a, ll b, ll c) {
	if (b == 0)
		return 1;
	else if (b % 2 == 0) {
		ll d = powm(a, b / 2, c);
		return (d * d) % c;
	} else
		return (a * powm(a, b - 1, c)) % c;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};

int main() {
	IOS();
	ll n;
	cin >> n;
	vector<ll> h(n);
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	ll ans = 0, tmp = 0;
	for (int i = 1; i < n; i++) {
		if (h[i] <= h[i - 1])
			tmp++;
		else {
			tmp = 0;
		}
		ans = max(ans, tmp);
	}
	dump(ans);
	return 0;
}

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

vector<int> a;
int N;

int two(int num);

int main(){
  cin >> N;
  int buf;
  a = {0};
  for (int i = 0; i<N; i++){
    cin >> buf;
    a.push_back(buf);
  }
  cout <<two(a.at(1))<<endl;
}



int two(int num){
  // cout << num << endl;
  if(num == 2){
    return 1;
  }else if(num == -1){
    return -1;
  }else{
    int buf = a.at(num);
    a.at(num) = -1;
    int bango = two(buf);
    if(bango == -1){
      return -1;
    }else{
      return bango + 1;
    }
  }
}


Measured memory_bytes: 2296
n, x = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != n-1:
        if x >= a:
            ans += 1
            x -= a
        else:
            break
    else:
        if x == a:
            ans += 1
        else:
            break
print(ans)


Measured memory_bytes: 61936
#include<cstdio>
int main(){
	int n,m;
	char a[50][50],b[50][50];
	char str[50];
	bool result = false;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",str);
		for(int j=0;j<n;j++){
			a[i][j] = str[j];
		}
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			printf("%c",a[i][j]);
		}
		printf("\n");
	}*/
	for(int i=0;i<m;i++){
		scanf("%s",str);
		for(int j=0;j<m;j++){
			b[i][j] = str[j];
		}
	}
	/*for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			printf("%c",b[i][j]);
		}
		printf("\n");
	}*/

	for(int i=0;i<=n-m;i++){
		for(int j=0;j<=n-m;j++){
			int def = 1;
			for(int k=0;k<m;k++){
				for(int l=0;l<m;l++){
					if(a[i+k][j+l] != b[k][l]) def = -1;
				}
			}
			//printf("i=%d j=%d def=%d\n",i,j,def);
			if(def == 1) result = true;
		}
	}
	if(result) printf("Yes\n");
	else printf("No\n");
	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main()
{
    int A,B,C,ans;

    scanf("%d %d %d", &A , &B,&C);

    if(A>=1 && A<=100 && B>=1 && B<=100 && C>=1 && C<=100)
    {
        if(B-A == C-B)
            printf("YES\n");
            else
            printf("NO\n");

    }
    else
            return;

}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define debug1 cout<<"?"<<endl;
#define debug2 cout<<"?"<<i<<endl;
typedef long long ll;
#define PII pair<ll,ll>
const int maxn=3e3+9;
const double pi=acos(-1);
const int mod=998244353;
const int INF=0x3f3f3f3f;
const double ep=1e-10;
using namespace std;
int main()
{
	ll n,s,i,j,a[maxn]={0};
	ll dp[maxn][maxn]={1},ans=0;
	//dp[i][j]表示前i个数和为j的个数 
	scanf("%lld%lld",&n,&s);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=s;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(a[i]<=j)dp[i][j]=(dp[i][j]+dp[i-1][j-a[i]])%mod;
		}
		ans=(ans+dp[i][s])%mod;
		dp[i][0]=dp[i-1][0]+1;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 71040
n, k = map(int,input().split())
h = []

for i in range(n):
    h.append(int(input()))
h = sorted(h)

minval = int(1e10)

#print(h)
for i in range(n-k+1):
    if minval >= h[i+(k-1)] - h[i]:
        minval = h[i+(k-1)] - h[i]
print(minval)

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

int main() {
 
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  
  int total = 0;
  
  if(k <= a){
    total = 1 * k;
  }
  else if(a < k){
    total = total + 1 * a;
    int l = k - a;
    if(b >= l){
      
    }
    else if(b < l){
      int m;
      m = l - b;
      total = total + -1 * m;
    }
    
  }
  
  cout << total << endl;
  
  
}



Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  int A[200];
  cin >> n;
  for(int i=0;i<n;i++)
    cin >> A[i];
  
  int cnt = -1;
  bool flag = true;
  while(flag){
    for(int i=0;i<n;i++){
      if(A[i] % 2 == 0)
        A[i] /= 2;
      else
        flag = false;
    }
    cnt++;
  }
  cout << cnt << endl;
}


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

int main() {
	int64_t s,tmp,bi=1000000000;
	vector<int64_t>x(3);
	vector<int64_t>y(3);
  cin >> s;
  if(s==bi*bi){
	  x.at(1)=bi;
 	  x.at(2)=0;
  	y.at(1)=1;
  	y.at(2)=bi;
  }
  else{
	  x.at(1)=s/bi+1;
 	  x.at(2)=x.at(1)*bi-s;
  	y.at(1)=1;
  	y.at(2)=bi;
  }
  for(int i=0;i<=2;i++) cout<< x.at(i) << " " << y.at(i) << " " ;
}


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

int main(){
  int a,b; cin>>a >>b;
  int r=0;
  for(int i=a;i<=b;i++){
    int s=i%10,t=i/10000%10;
    int u=i/10%10,v=i/1000%10;
    if(s==t&&u==v)r++;
  }
  cout<<r<<endl;
}

Measured memory_bytes: 256
N = int(input())
S = sorted([int(input()) for _ in range(N)])

non_10s = None
for s in S:
    if s % 10 != 0:
        non_10s = s
        break

answer = sum(S)

if answer % 10 == 0 and non_10s is not None:
    answer -= non_10s

if answer % 10 == 0:
    answer = 0
print(answer)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool is_prime(ll n) {
  for (ll i = 2; i*i <= n; i++) {
    if (n%i == 0) return false;
  }
  return n != 1;
}
ll mod_pow(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll res = mod_pow(x*x%mod, n/2, mod);
  if (n & 1) res = res * x % mod;
  return res;
}

int main() {
  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  if (a >= k) {
    cout << k << endl;
  } else if (a+b >= k) {
    cout << a << endl;
  } else {
    cout << a-(k-a-b) << endl;
  }
}

Measured memory_bytes: 3636
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

# https://note.nkmk.me/python-union-find/

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n, k = ns()
    p = na1()
    c = na()

    uf = UnionFind(n)
    for i, pi in enumerate(p):
        uf.union(i, pi)

    cycledist = [[-INF for _ in range(2)] for __ in range(n)]
    for lis in uf.all_group_members().values():
        tmp = 0
        l = len(lis)
        for idx in lis:
            tmp += c[idx]
            cycledist[idx][1] = l
        for idx in lis:
            cycledist[idx][0] = tmp

    ans = -INF

    for i in range(n):
        flg = k // cycledist[i][1] > 0
        tmp_ans = cycledist[i][0] * ((k // cycledist[i][1]) - 1) if flg else 0

        tmp = 0
        idx = i
        for j in range(cycledist[i][1] * flg + k % cycledist[i][1]):
            tmp += c[p[idx]]
            idx = p[idx]
            ans = max(ans, tmp_ans + tmp)

        tmp = 0
        idx = i
        for j in range(min(k, cycledist[i][1])):
            tmp += c[p[idx]]
            idx = p[idx]
            ans = max(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 72064
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
const int N_MAX = 100000;

long long mod(long long a) {
	a %= MOD;
	return a >= 0 ? a : a+MOD;
}

long long inverse[N_MAX+1+64];
long long factorial[N_MAX+1+64];
long long factorial_inverse[N_MAX+1+64];

void calc(int n) {
	inverse[1] = 1;
	factorial[0] = factorial[1] = 1;
	factorial_inverse[0] = factorial_inverse[1] = 1;
	for (int i = 2; i <= n; i++) {
		inverse[i] = MOD - inverse[MOD%i] * (MOD/i) % MOD;
		factorial[i] = i * factorial[i-1] % MOD;
		factorial_inverse[i] = inverse[i] * factorial_inverse[i-1] % MOD;
	}
}

long long comb(long long n, long long k) {
	return factorial[n] * (factorial_inverse[k] * factorial_inverse[n-k] % MOD) % MOD;
}

long long rep_comb(long long n, long long k) {
	return comb(n + k - 1, k);
}

vector<pair<long long, int>> prime_factorization(long long n) {
	vector<pair<long long, int>> v;
	for (long long i = 2; i * i <= n; ++i) {
		int e = 0;
		while (n % i == 0) {
			++e;
			n /= i;
		}
		if (e != 0) v.emplace_back(i, e);
	}
	if (n != 1) v.emplace_back(n, 1);
	return v;
}

int main() {
	calc(N_MAX+65);
	long long n, m;
	cin >> n >> m;
	long long ans = 1;
	auto v = prime_factorization(m);
	for (auto el : v) {
		long long e = el.second;
		ans = mod(ans * rep_comb(n, e));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
#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 VRSORT(v) sort(v.rbegin(), v.rend());//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

typedef tuple<ll, int, int> T;

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 n,a,b;
  cin>>n>>a>>b;
  cout<<min(a,b)<<" "<<max(0,a+b-n)<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
const int MOD = 1000000007;
int N, f[1000001], s[1000001];
int main()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		if (i == 1)
			f[i] = N;
		else if (i == 2)
			f[i] = (long long)N * N % MOD;
		else
			f[i] = (f[i - 1] + s[i - 3] + (long long)N * (N - 1) - i + 3) % MOD;
		s[i] = (s[i - 1] + f[i]) %MOD;
	}
	printf("%d\n", f[N]);
	return 0;
}


Measured memory_bytes: 7936
var x,y,z,n,k,a:longint;
begin
  readln(k,n);
  for x:=0 to k do
    for y:=0 to k do
    begin
      z:=n-x-y;
      if (z>=0) and (z<=k) then
        inc(a);
    end;
  writeln(a);
end.

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  int H, W; cin >> H >> W;
  int A, B; cin >> A >> B;

  int res{};
  for (int row = 0; row < H; ++row){
    res ^= 1;
    if(row == B) res ^= 1;
    for (int column = 0; column < W; ++column){
      if(column == A) res ^= 1;
      cout << res;
    }
    cout << CRLF;
  }

  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int i;
  bool p = true;
  while(p)
  {
    if(n%10==7)
    {
      cout<<"Yes";
      p=false;
    }
    n=n/10;
    if(n==0)
      break;
  }
  if(p)
    cout<<"No";
  return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;

int main(){
	int N,W,x,y,j;
	cin >> N >> W ;
	vector<int> value;
	vector<int> weight;
	for (int i=0;i<N;i++){
		cin >> x >> y;
		for(j=0;j < value.size();j++){
			if(weight[j]==y){
				if(value[j]<=x){
					value[j]=x;
				}
				break;
			}
		}
		if(j==value.size()){
			value.push_back(x);
			weight.push_back(y);
		}
	}
	
	N=value.size();
	/*
	for (int k=0;k < value.size();k++){
		cout<<weight[k] <<endl;
	}
	*/
	
	int table[W+1][N];
	for (int i=0;i<W+1;i++){
		if(i==0){
			table[i][0]=0;
		}else if(i%weight[0]==0){
			table[i][0]=value[0]*(i/weight[0]);
		}else{
			table[i][0]=-1;
		}
	}
	
	for (int j=1;j<N;j++){
		table[0][j]=0;
		for (int i=1;i<W+1;i++){
			int k=0;
			int val=-1;
			while(i-k*weight[j]>=0){
				if(val < table[i-k*weight[j]][j-1]+k*value[j]){
					val = table[i-k*weight[j]][j-1]+k*value[j];
				}
				k++;
			}
			table[i][j]=val;
		}
	}
	
	int res=0;
	for (int i=0;i<W+1;i++){
		if(res<table[i][N-1]){
			res=table[i][N-1];
		}
	}
	cout << res <<endl;
	
	
	return 0;
}

Measured memory_bytes: 4576
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt();
            var N = line[0];
            var K = line[1];
            var V = consoleReader.SplitInt();
            var V2 = V.Concat(V).ToArray();

            var max = 0;
            for (int k = 1; k <= K; k++)
            {
                if (k > N) break;
                for (int i = 0; i <= k; i++)
                {
                    var arr = V2.Skip(N - i).Take(k).ToArray();
                    Array.Sort(arr);

                    var sum = 0;
                    for (int j = 0; j < k; j++)
                    {
                        if (arr[j] > 0 || j >= K - k)
                            sum += arr[j];
                    }
                    if (max < sum)
                        max = sum;
                }
            }

            return max;
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc()); static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
}

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

int main() {
  int n;
  scanf("%d", &n);
  if (n % 2 == 0) {
    printf("%d\n", n / 2 - 1);
  } else {
    printf("%d\n", (n - 1) / 2);
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <bitset>
#include <map>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#include <sstream>
#include <math.h>

using namespace std;

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecchar vector<char>
#define vecstr vector<string>
#define vec2str vector<vector<string>>
#define vecbool vector<bool>
#define vec2bool vector<vector<bool>>
#define pairll pair<ll,ll>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)

#define Pi 3.1415926535897932384626

int main() {
	ll n, ans = 0;
	bool flag = false;
	string s;

	cin >> n;

	vecll a(n);

	forll(i, 0, a.size())
		cin >> a[i];

	ll before = a[0];

	forll(i, 1, a.size())
	{
		if (before > a[i])
		{
			ans += before - a[i];
		}
		else if (before < a[i])
		{
			before = a[i];
		}
	}



	cout << ans;
}

Measured memory_bytes: 4784
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

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

    int H, W;
    cin >> H >> W;
    vector<vector<bool>> S(H, vector<bool>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            char c;
            cin >> c;
            S[i][j] = (c == '.');
        }
    }

    queue<pii> que;
    int ans = 0;

    int dx[4] = {1, -1, 0, 0},
        dy[4] = {0, 0, 1, -1};
    for (int sy = 0; sy < H; ++sy) {
        for (int sx = 0; sx < W; ++sx) {
            if (!S[sy][sx])
                continue;
            for (int gy = 0; gy < H; ++gy) {
                for (int gx = 0; gx < W; ++gx) {
                    if (!S[gy][gx])
                        continue;
                    vector<vector<int>> dist(H, vector<int>(W, -1));
                    dist[sy][sx] = 0;
                    que.push(make_pair(sy, sx));
                    while (!que.empty()) {
                        int x = que.front().second, y = que.front().first;
                        que.pop();
                        for (int i = 0; i < 4; ++i) {
                            int nx = x + dx[i], ny = y + dy[i];
                            if (nx < 0 || nx >= W || ny < 0 || ny >= H)
                                continue;
                            if (dist[ny][nx] != -1)
                                continue;
                            if (!S[ny][nx])
                                continue;
                            que.push(make_pair(ny, nx));
                            dist[ny][nx] = dist[y][x] + 1;
                        }
                    }
                    ans = max(dist[gy][gx], ans);
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


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

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define INF 1000000009
#define mod 1000000007
using namespace std;
typedef long long ll;

int n;
pair<ll, int> h[200005];
ll b[200005];
ll st[800005];

void stc(int node, int l, int r){
	if (l == r) st[node] = 0;
	else {
		int m = (l+r)/2;
		stc(node*2, l, m);
		stc(node*2+1, m+1, r);
		st[node] = 0;
	}
}

void stu(int node, int l, int r, int ind, ll val){
	if (l == r) st[node] = val;
	else {
		int m = (l+r)/2;
		if (ind <= m) stu(node*2, l, m, ind, val);
		else stu(node*2+1, m+1, r, ind, val);
		st[node] = max(st[node*2], st[node*2+1]);
	}
}

ll stq(int node, int l, int r, int sl, int sr){
	if (inside) return st[node];
	else if (outside) return 0;
	else {
		int m = (l+r)/2;
		return max(stq(node*2, l, m, sl, sr), stq(node*2+1, m+1, r, sl, sr));
	}
}

int main(){
	//freopen("stl.gir", "r", stdin);
	
	cin >> n;
	for (int i = 0; i < n; i++){
		int a;
		cin >> a;
		h[i] = mp(a, i);
	}
	for (int i = 0; i < n; i++) cin >> b[i];
	
	sort(h, h+n);
	stc(1, 0, n);
	ll ans = 0;
	for (int i = n-1; i >= 0; i--){
		ll ansp = b[h[i].second] + stq(1, 0, n, h[i].second, n);
		ans = max(ansp, ans);
		stu(1, 0, n, h[i].second, ansp);
	}
	
	cout << ans << endl;
	
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 2000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

string s;
int k;
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    cin >> s >> k;
    rep(i, 0, s.size()) {
        int dist = 0;
        dist = (26 - (s[i] - 'a')) % 26;
        if (dist <= k) {
            s[i] = 'a';
            k -= dist;
        }
    }
    s[s.size() - 1] += k % 26;
    cout << s << endl;
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

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

  cout << a * b << endl;
  return 0;
}


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

int keta_sum(int n);

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

	int mn=1010101010;
	int t;
	for (int i=1;i<n;i++) {
		t = keta_sum(i) + keta_sum(n - i);
		mn = min(mn, t);
	}
	cout<<mn;

	return 0;
}

int keta_sum(int n)
{
	int result = 0;
	while (n != 0) {
		result += n % 10;
		n /= 10;
	}
	return result;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long mod2 = 998244353;
const long long INF = 1LL << 60;
const int inf = pow(10, 9) + 7;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

int main()
{
  int N;
  cin >> N;
  vector<string> S(N), Sa(N), Sz(N);
  for (int i = 0; i < N; i++)
  {
    string s;
    cin >> s;
    S.at(i) = s;
    Sa.at(i) = s;
    Sz.at(i) = s;
  }
  string T;
  cin >> T;

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < S.at(i).size(); j++)
    {
      if (S.at(i).at(j) == '?')
      {
        Sa.at(i).at(j) = 'a';
        Sz.at(i).at(j) = 'z';
      }
    }
  }

  Sa.push_back(T);
  Sz.push_back(T);
  
  sort(Sa.begin(), Sa.end());
  sort(Sz.begin(), Sz.end());
  
  auto ita = upper_bound(Sa.begin(), Sa.end(), T);
  int inda = ita - Sa.begin() + 1;
  auto itz = lower_bound(Sz.begin(), Sz.end(), T);
  int indz = itz - Sz.begin() + 1;

  for (int i = indz; i < inda - 1; i++)
  {
    cout << i << " ";
  }
  cout << inda - 1 << endl;
}

Measured memory_bytes: 2176
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
 

public class Main{
          
    static int n=0;
     
     public static void main(String args[]){
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
         try{ String line;
            ArrayList<Double> xs= new ArrayList<Double>();
            ArrayList<Double> ys= new ArrayList<Double>();
            
             while((line=br.readLine())!=null){if(line.isEmpty())break;
                String spl[] = line.split(",");
                double x=Double.parseDouble(spl[0]);
                double y=Double.parseDouble(spl[1]);
                xs.add(x); ys.add(y);
             } br.close();
            double x0 = xs.get(0), y0=ys.get(0);
            double allS=0;
            for(int i=2;i<=xs.size()-1;i++){
                double x2=xs.get(i),y2=ys.get(i);
                double x1=xs.get(i-1),y1=ys.get(i-1);
                double a=Math.sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0));
                double b=Math.sqrt((x2-x0)*(x2-x0)+(y2-y0)*(y2-y0));
                double c=Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
                double z=(a+b+c)/2;
                double s=Math.sqrt(z*(z-a)*(z-b)*(z-c));
                allS+=s;
            }
             System.out.println(allS);
         }catch(Exception e){e.printStackTrace();}         
     }  
    static String _4keta(int n){
        if(n/10==0) return "   "+n;
        if(n/100==0) return "  "+n;
        if(n/1000==0) return " "+n;
        return n+"";
    }
     static int[] migisita(int[] inV){
         int nowX = inV[0], nowY=inV[1];
         int nexX = (nowX==n-1)? 0 : nowX+1;
         int nexY = (nowY==n-1)? 0 : nowY+1;
         return new int[]{nexX, nexY};         
     }
     static int[] hidarisita(int[] inV){
         int nowX = inV[0], nowY=inV[1];
         int nexX = (nowX==0)? n-1 : nowX-1;
         int nexY = (nowY==n-1)? 0 : nowY+1;
         return new int[]{nexX, nexY};         
     }
     
}
 

Measured memory_bytes: 16920
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define div _zzd001
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=75*2,mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
int n,k;
int C[N][N];
char s[N];
vector <int> div;
int ans=0;
int cr=0,cb=0;
void Solve(){
//	ans++;
//	outarr(div,0,(int)div.size()-1);
	int nr=0,nb=0;
	for (auto i : div)
		nr++,nb+=i>1;
	if (nr>cr||nb>cb)
		return;
	static int a[N],rem[N];
	clr(a),clr(rem);
	int m=div.size();
	For(i,0,m-1)
		a[i+1]=div[i];
	reverse(a+1,a+m+1);
	int pp=0;
	For(i,1,m)
		if (a[i]>1)
			pp=i;
	int need=0,p=0,sp=0;
	For(i,1,k)
		if (s[i]=='r'&&p<m){
			p++;
		}
		else if (s[i]=='b'){
			if (sp<min(p,pp)){
				need+=a[++sp]-2;
			}
			else if (need>0)
				need--;
		}
		else if (need>0){
			need--;
		}
	if (need>0||sp<pp)
		return;
	static int dp[N];
	static int cs[4]={0,0,1,0};
	clr(dp);
	dp[0]=1;
	for (auto i : div){
		Fod(j,n,0){
			if (!dp[j])
				continue;
			Fod(k,3,1){
				if (j+i*2-k+1>n)
					break;
				if (i==1&&k>1)
					continue;
				Add(dp[j+i*2-k+1],Add(dp[j]<<cs[k]));
			}
			dp[j]=0;
		}
	}
	int tmp=0;
//	outarr(dp,0,n);
	For(i,0,n)
		if (dp[i])
			Add(tmp,(LL)dp[i]*C[n][i]%mod);
	int las=1;
	a[m+1]=-1;
	int s=0;
	For(i,2,m+1){
		if (a[i]!=a[i-1]){
			int len=i-las;
			las=i;
			tmp=(LL)tmp*C[s+=len][len]%mod;
		}
	}
//	outval(tmp);
	Add(ans,tmp);
}
void dfs(int rem,int n,int now,int flag){
	if (n<0)
		return;
	if (flag)
		Solve();
	if (rem>=now){
		div.pb(now);
		dfs(rem-now,n-max(1,now*2-3)-1,now,1);
		div.pop_back();
		dfs(rem,n,now+1,0);
	}
}
int main(){
	For(i,0,N-1)
		C[i][0]=1;
	For(i,1,N-1)
		For(j,1,i)
			C[i][j]=Add(C[i-1][j-1]+C[i-1][j]);
	n=read()+1,k=read();
	cin>>(s+1);
	For(i,1,k)
		if (s[i]=='r')
			cr++;
		else
			cb++;
	div.clear();
	dfs(k,n,1,1);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll a,b;
    while(1)
    {
        cin>>a>>b;
        if(a==0 && b==0) break;
        else
        {
                for(ll i=1; i<=a; i++)
            {
                    for(ll j=1; j<=b; j++)
                    {
                        cout<<'#';
                    }
                    cout<<endl;
            }
            cout<<endl;
        }
    }
    return 0;
}



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

int main() {
  
  int X; cin >> X;
  
  int pointOf500YEN = X / 500 * 1000;
  
  int pointOf5YEN = X % 500 / 5 * 5;
  
  cout << pointOf500YEN + pointOf5YEN << endl;
  
}

Measured memory_bytes: 256
eval"N,A,*X="+`dd`.split*?,;d=[i=0]*2e4;d[N*=A]=1;X.map{|x|(0..2*N).map{|j|d[5e3-i+j]=d[i+j]+d[[0,i+j-x+A].max]};i=5e3-i};p d[i+N]-1

Measured memory_bytes: 4232
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main(void)
{
    int n, x, t, counter = 0;
    scanf("%d %d %d", &n, &x, &t);
    for (int i = 1; i <= n; i++)
    {
        if (i * x >= n)
        {
            counter = i;
            break;
        }
    }
    printf("%d\n", t * counter);
    return 0;
}

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

constexpr long long MOD = 1'000'000'007;

class binomial_coefficients {
public:
	long long MAX_VAL;
	vector<long long> fac, mmi;


	binomial_coefficients(){
	}
	
	binomial_coefficients(long long num){
		init(num);
	}
	
	~binomial_coefficients(){
		
	}
	
	void init(long long num){
		MAX_VAL = num+1; 
		fac.resize(MAX_VAL);
		mmi.resize(MAX_VAL);
		
		factorial_mod();
		modular_multiplicatibe_inverse();
	}
	
	void factorial_mod(){
		 fac[0] = 1;
		for(long long i = 1; i < MAX_VAL; fac[i] %= MOD, i++)
			fac[i] = fac[i - 1] * (i % MOD);
	}
	
	long long power(long long x, long long n){
		long long ans = 1;
		for(;n;n >>= 1, x *= x, ans %= MOD, x %= MOD)
			if(n&1)ans*=x;
		return ans % MOD;
	}
	
	void exgcd(long long a, long long b, long long &x, long long &y){
		if(b == 0){
			x = 1;
			y = 0;
			return ;
		}
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
	
	void modular_multiplicatibe_inverse(){
		long long x, y;  
		exgcd(fac[MAX_VAL - 1], MOD, x, y);
		mmi[MAX_VAL-1] = (x % MOD + MOD) % MOD;
		// mmi[MAX_VAL-1] = power(fac[MAX_VAL-1], MOD-2);
		for(long long i = MAX_VAL - 2; i >= 0; mmi[i]%=MOD, i--)
			mmi[i] = mmi[i + 1] * ((i + 1) % MOD);
	}
	
	long long combination(long long n, long long r){
		return n < r ? 0 :fac[n] * (mmi[r] * mmi[n-r] % MOD) % MOD;
	}
};


int main(){
	
	long long n, k;
	long long ans = 0;
	binomial_coefficients bc;
	
	cin>>n>>k;
	
	bc.init(n+k);
	
	
	for(int i = 0; i <= k; i++){
		if(i%2) {
			ans += (MOD - bc.combination(k, i) * bc.power(k - i, n)%MOD);
		} else {
			ans += bc.combination(k, i) * bc.power(k - i, n);
		}
		
		ans %= MOD;
	}
	
	ans *= bc.mmi[k];
	ans %= MOD;
	
	cout<<ans<<endl;
}


Measured memory_bytes: 3120
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  [a, b, c, k] <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    m :: Int
    m | k <= a + b = min a k
      | otherwise  = a - (k - a - b)
  print m

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
{-# INLINE unsafeTextToInt #-}


Measured memory_bytes: 3784
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <assert.h>

using namespace std;

#define N 2005

int in[N];
pair<int,int> pp[N];
bool isErased[N];

int isPossible(int n,int k,int q) {
  isErased[n+1] = true;
  int last = 1,ret = 0;
  vector<int> cand,tmp;
  for(int i=1;i<=n+1;++i) {
    if(isErased[i]) {
      if(tmp.size()>=k) {
        sort(tmp.begin(),tmp.end());
        for(int j=0;j+k-1<tmp.size();++j) {
          cand.push_back(tmp[j]);
        }
      }
      tmp.clear();
    } else {
      tmp.push_back(in[i]);
    }
  }
  if(cand.size()>=q) {
    sort(cand.begin(),cand.end());
    return cand[q-1] - cand[0];
  } else {
    return 1e9;
  }
}
void solve() {
  int n,k,q;scanf("%d %d %d",&n,&k,&q);
  if(q==1) {
    printf("0\n");
    return;
  }
  for(int i=1;i<=n;++i) {
    scanf("%d",&in[i]);
    pp[i] = make_pair(in[i],i);
  }
  sort(pp+1,pp+n+1);
  int ret = 1e9;
  for(int i=1;i<=n;) {
    int j;
    vector<int> v;
    for(j= i;j<=n;++j) {
      if(pp[j].first != pp[i].first) {
        break;
      }
      v.push_back(pp[j].second);
    }
    ret = min(ret, isPossible(n,k,q));
    i = j;
    for(j=0;j<v.size();++j) {
      isErased[v[j]] = true;
    }
  }
  printf("%d\n",ret);
}

int main() {
  //freopen("input.txt","r",stdin);
  solve();
  return 0;
}


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

using namespace std;

void solve(int N, long Y) {
  rep(i, N + 1) {
    rep(j, N + 1 - i) {
      int k = N - i - j;
      if (10 * i + 5 * j + k == Y / 1000) {
	cout << i << " " << j << " " << k << endl;
	return;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
}

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

  int N;
  long Y;
  cin >> N >> Y;
  solve(N, Y);
  return 0;
}


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

int main(){
    int N,A,B;
    cin >> N >> A >> B;
    string s;
    cin >> s;
    
    int passed=0;
    int a1 = 0;
    int b1 = 0;
    int passed2 = 0;
    for(int i = 0; i < N; i++){
        if(s[i] == 'a' && a1 == 0){
            if(passed < A+B){
                cout << "Yes"<<endl;
                passed += 1;
            }else{
                cout << "No"<<endl;
            }
        }
        
        if(s[i] == 'b' && b1 == 0){
            if(passed < A+B && passed2<B){
                cout << "Yes"<<endl;
                passed+= 1;
                passed2 += 1;
            }else{
                cout << "No" << endl;
            }
        }
        if(s[i] == 'c'){
            cout << "No" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 896
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void getSum(int a[],int x,int y){
    int i;
    int sum=0;
    for(i=x;i<=y;i++){
        sum+=a[i];
    }
    printf("%d\n",sum);
}

int main(void){
    int i;
    
    int n;
    scanf("%d ",&n);
    
    int a[n];
    for(i=0;i<n;i++)a[i]=0;

    int q;
    scanf("%d\n",&q);
    
    int com,x,y;
    while(q--){
        scanf("%d %d %d\n",&com,&x,&y);
        switch(com){
            case 0:
                a[x-1]+=y;
                break;
            case 1:
                getSum(a,x-1,y-1);
                break;
        }
    }

    return 0;
}



Measured memory_bytes: 2176
#include<stdio.h>
#include<stdlib.h>

int linearSearch( int n , int a[n] , int key);


int main( void ){
	
	int n , q;
	int *s , *t;
	int i;
	int c = 0;
	
	scanf( "%d" , &n );
	s = (int *)malloc(n * sizeof(int));  
	for( i = 0; i < n; i++ ){
		scanf( "%d" , &s[i] );
	}
	
	scanf( "%d" , &q );
	t = (int *)malloc(q * sizeof(int));  
	for( i = 0; i < q; i++ ){
		scanf( "%d" , &t[i] );
	}
	
	for( i = 0; i < q; i++ ){
		if( linearSearch( n , s , t[i]) != -1 ){
			c++;
		}
	}
	
	printf( "%d\n" , c );
	
}

int linearSearch( int n , int a[n] , int key){

	int i;
	
	i = 0;
	a[n] = key;
	
	while( a[i] != key ){
		i++;
	}
	
	if( i == n ){
		return -1;
	}
	
	return i;
	
}


Measured memory_bytes: 2092
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
  size_t N, M;
  scanf("%zu %zu", &N, &M);

  std::vector<int> deg(N);
  for (size_t i=0; i<2*M; ++i) {
    int a;
    scanf("%d", &a);
    --a;

    ++deg[a];
  }

  auto even=[](int x)->bool {
    return x % 2 < 1;
  };

  printf("%s\n", std::all_of(deg.begin(), deg.end(), even)? "YES":"NO");
}


Measured memory_bytes: 640