akhauriyash/Code-Regression huggingface dataset:
from collections import deque
st = deque()
s = input()
ans = 0
for i in range(len(s)-1):
    if s[i:i+2] != 'BC' and s[i] != 'A' and (i>0 and s[i-1:i+1] != 'BC'):
        st.clear()
        continue
    if s[i] == 'A':
        st.append(0)
    elif s[i:i+2] == 'BC':
        ans += len(st)
print(ans)

Measured memory_bytes: 5092
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int count = map.getOrDefault(a, 0);
            map.put(a, count + b);
        }

        long count = 0;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            int price = e.getKey();
            int num = e.getValue();
            if (m == 0) break;
            int min = Math.min(m, num);
            count += (long) min * price;
            m -= min;
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 66700
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))

#keyはA[i]、valueは登場回数
A_unique = {}
 
for i in range(0,len(A)):
    if A[i] in A_unique:
        A_unique[A[i]] += 1
    else:
        A_unique[A[i]] = 1
v = list(A_unique.values())
v.sort() #登場回数が少ない順に書き換えていく
A_length = len(A_unique.keys()) #元々のAに含まれる数字の種類
d = 0
n = 0

for k in v:
    if  A_length - n <= K:
        print(d)
        break
    else:
        d += k #d個を書き換え
        n += 1 #数字が1種類減る


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


int main() {
	long X, Y, Z, K;
	vector<long>vec;

	cin >> X >> Y >> Z >> K;
	vector<long> A (X);
	vector<long> B (Y);
	vector<long> C (Z);

	for (int i = 0; i < X; i++) cin >> A[i];
	sort(A.begin(), A.end(), greater<long>());

	for (int i = 0; i < Y; i++) cin >> B[i];
	sort(B.begin(), B.end(), greater<long>());

	for (int i = 0; i < Z; i++) cin >> C[i];
	sort(C.begin(), C.end(), greater<long>());

	for (int i = 0; i < X; i++) {
		for (int j = 0; j < Y; j++) {
			for (int k = 0; k < Z; k++) {
				if ((i + 1) * (j + 1) * (k + 1) <= K) vec.push_back(A[i] + B[j] + C[k]);
				else break;
			}
		}
	}
/*
	for (int i = 0; i < X; i++) {
		for (int j = 0; j < Y; j++) {
			for (int k = 0; k < Z; k++) {
				if ((i + 1) * (j + 1) * (k + 1) <= K) vec.push_back(A[i] + B[j] + C[k]);
				else break;
			}
		}
	}
*/
	sort(vec.begin(), vec.end(), greater<long>());
	for (int i = 0; i < K; i++) cout << vec[i] << endl;
	return 0;
}



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

using namespace std;

typedef long long ll;
typedef long double ld;

int arr[3005];
ll dp[3005][3005][2];

int main()
{
  int n;
  cin >> n;
  for(int i = 0; i < n; i++)
    cin >> arr[i];
  for(int i = n - 1; i >= 0; i--)
  {
      for(int j = i; j < n; j++)
      {
        if(i == j)
        {
          dp[i][j][0] = arr[i];
          dp[i][j][1] = -arr[i];
        }
        else
        {
          dp[i][j][0] = max(arr[i] + dp[i + 1][j][1], arr[j] + dp[i][j - 1][1]);
          dp[i][j][1] = min(dp[i + 1][j][0] - arr[i], dp[i][j - 1][0] - arr[j]);
        }
      }
  }
  cout << dp[0][n - 1][0];
  return 0;
}


Measured memory_bytes: 139648
array = []
3.times do
  array << gets.split.map(&:to_i)
end

n = gets

numbers = readlines.map(&:to_i)
first_index = []
second_index = []
third_index = []

if (first = numbers & array.first)
  if (second = numbers & array[1])
    if (third = numbers & array[2])
      first.each do |e|
        first_index << array.first.find_index(e)
      end

      second.each do |e|
        second_index << array[1].find_index(e)
      end

      third.each do |e|
        third_index << array[2].find_index(e)
      end

      if (first_index.compact & second_index.compact & third_index.compact).any?
        puts 'Yes'
        exit
      end

      if second_index.include?(1) && ((first_index.include?(0) && third_index.include?(2)) || (first_index.include?(2) && third_index.include?(0)))
        puts 'Yes'
        exit
      end

      if first_index.compact.size == 3 || second_index.compact.size == 3 || third_index.compact.size == 3
        puts 'Yes'
        exit
      end
    end
  end
end

puts 'No'


Measured memory_bytes: 1788
MOD = 998244353
n, s = map(int, input().split())
a = list(map(int, input().split()))

dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j] = dp[i][j] * 2
		if j >= a[i]:
			dp[i+1][j] += dp[i][j-a[i]]
		dp[i+1][j] %= MOD
print(dp[n][s])

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> adj[n + 1];
    for (int i = 0; i < n - 1; i ++) {
    int u, v;
    cin >> u >> v;
    adj[u].emplace_back(v, i);
    adj[v].emplace_back(u, i);
}
int K = 0;
vector<int> color(n - 1);
function<void(int, int, int)> dfs = [&] (int u, int p, int col) -> void {
    int paint = 1;
    K = max(K, (int)adj[u].size());
for (auto& x : adj[u]) {
        if (x.first == p) continue;
        if (paint == col) paint ++;
        color[x.second] = paint;
        dfs(x.first, u, paint);
        paint ++;
}
};
dfs(1, 0, 0);
cout << K << "\n";
for (auto& col : color) cout << col << "\n";
}


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

typedef long long ll;

void solve(void) {
  ll N;
  cin >> N;
  vector<ll> H(N);
  for (ll hi = 0; hi < N; ++hi) cin >> H[hi];

  ll ans = 0;
  ll tmp = 0;
  for (ll hi = 0; hi+1 < N; ++hi) {
    if (H[hi] >= H[hi+1]) {
      ++tmp;
    } else {
      tmp = 0;
    }
    ans = max(ans, tmp);
  }
  cout << ans << endl;
}

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

Measured memory_bytes: 1152
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 400010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

int n, k;
ll f[MAXN], rev[MAXN];

ll mul(ll a, ll b) {
    return a * b % MODBASE;
}

ll add(ll a, ll b) {
    return (a + b) % MODBASE;
}

ll sub(ll a, ll b) {
    return (a - b + MODBASE) % MODBASE;
}

ll binPowMod(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1LL) res = res * a % MODBASE;
        a = a * a % MODBASE;
        b >>= 1LL;
    }
    return res;
}

ll C(int n, int k) {
    if (k > n || k < 0) return 0;
    return mul(f[n], mul(rev[n-k], rev[k]));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> k;
    f[0] = 1;
    rev[0] = binPowMod(f[0], MODBASE-2);
    FOR(i,1,400000) {
        f[i] = mul(f[i-1], i);
        rev[i] = binPowMod(f[i], MODBASE-2);
    }
    if (k >= n-1) {
        cout << C(2*n-1, n-1);
        return 0;
    }
    ll res = 1;
    FOR(i,1,k) res = add(res, mul(C(n,i), C(n-1, n-i-1)));
    cout << res;
    return 0;
}


Measured memory_bytes: 6528
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
long long N;

int a[100001];
int main() {
	cin >> N; 
	for (int i = 1; i < N+1; ++i) {
		cin >> a[i];
	}
	int cnt = 0;
	for (int i = 1; i < N+1; ++i) {
		int temp = a[i];
		if (a[temp] == i) {
			cnt++;
			a[temp] = 0;
		}
	}
	cout << cnt << endl;
	return 0;
}


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

int main() {
	int a1,a2,a3;
	cin>>a1>>a2>>a3;
	int MAX,MIX,MIN;
	MAX=max(a1,max(a2,a3));
	MIN=min(a1,min(a2,a3));
	MIX=(a1+a2+a3)-MAX-MIN;
	cout<<abs(MAX-MIX)+abs(MIN-MIX)<<endl;
}

Measured memory_bytes: 256
import bisect
INF = 10 ** 10
s = input()
t = input()
moji = [[] for _ in range(26)]

for i, m in enumerate(s):
    moji[ord(m) - ord("a")].append(i)

for i in range(26):
    moji[i].sort()

moji_o = [0 for _ in range(len(t))]

cnt = 0
ans = 1
# print(moji)
for i, m in enumerate(t):
    if len(moji[ord(m) - ord("a")]) == 0:
        ans = -1
        break
    if i == 0:
        moji_o[i] = moji[ord(m) - ord("a")][0]
    else:
        if moji_o[i - 1] >= moji[ord(m) - ord("a")][-1]:
            moji_o[i] =  moji[ord(m) - ord("a")][0]
        else:
            tmp = bisect.bisect_right(moji[ord(m) - ord("a")], moji_o[i - 1])
            if tmp == 0:
                moji_o[i] = moji[ord(m) - ord("a")][0]
            else:
                moji_o[i] = moji[ord(m) - ord("a")][tmp]
# print(moji_o)
for i in range(1, len(moji_o)):
    if ans == -1:
        break
    if moji_o[i - 1] >= moji_o[i]:
        cnt += 1

if ans == -1:
    print(-1)
else:
    print(cnt * len(s) + moji_o[-1] + 1)

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

#define ff first
#define ss second
#define pb push_back

using namespace std;
using ll = long long;
using ii = pair<int, int>;

const int N = 100005;

int main(){
	ll a, b, v, w, t;
	scanf("%lld %lld %lld %lld %lld", &a, &v, &b, &w, &t);
	if(w >= v){
		printf("NO\n");
		return 0;
	}
	ll d = abs(b - a);
	ll x = v - w;
	printf("%s\n", (d + x - 1) / x <= t ? "YES" : "NO");
		
	return 0;
}


Measured memory_bytes: 3688
function Main(input) {
    input = input.trim().split("\n");
    tmp = input[0].split(" ");
    var N = parseInt(tmp[0], 10);
    var X = parseInt(tmp[1], 10);
    var L = [];
    tmp = input[1].split(" ");
    for (var i = 0; i < N; i++){
        L[i] = parseInt(tmp[i], 10);
    }

    var D = 0;
    var bound = 1;
    for (var i = 0; i < N; i++){
        D += L[i];
        if (D > X) {
            break;
        }
        bound++;
    }
    console.log(bound);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include<iostream>
#include <bits/stdc++.h>
#include<stdio.h>
#include <stdlib.h>
#include<string>
#include<queue>
#include<algorithm>
#include<math.h>
#include<map>
using namespace std;


int main(){
	long long int N;
	long long int ans=0;
	cin>>N;
	vector<int> a,b,c;
	for(int i=0;i<N;i++){
		int an;
		cin>>an;
		a.push_back(an);
	}
	for(int i=0;i<N;i++){
		int bn;
		cin>>bn;
		b.push_back(bn);
	}
	for(int i=0;i<N;i++){
		int cn;
		cin>>cn;
		c.push_back(cn);
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	for(int i=0;i<N;i++){
		long long int ansa=lower_bound(a.begin(),a.end(),b[i])-a.begin();
		//b[i]個数
		long long int ansb=N-(upper_bound(c.begin(),c.end(),b[i])-c.begin());
		//b[i]以上の個数
		ans+=ansa*ansb;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1784
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

long long n,a[15],t=1,x=1;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        if(!(a[i]%2)) t*=2;
        x*=3;
    }
    cout << x-t;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    int X;cin>>X;
    int ans=1;
    rep(i,2,sqrt(X)+1.5){
        int tmp=i;
        while(tmp*i<=X){
            tmp*=i;
        }
        ans=max(ans,tmp);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
n = gets.to_i
a = (1..n).map { gets.chomp }

diff = []
min = [0] * n
diff_rev = []
min_rev = [0] * n
a.each_with_index do |s, i|
    x = 0
    s.each_char do |c|
        x += (c == ?( ? 1 : -1)
        min[i] = x if x < min[i]
    end
    diff[i] = x
    x = 0
    s.reverse.each_char do |c|
        x += (c == ?) ? 1 : -1)
        min_rev[i] = x if x < min_rev[i]
    end
    diff_rev[i] = x
end

if min.max < 0 || min_rev.max < 0 || diff.inject(:+) != 0
    puts 'No'
    exit
end

rest = (0..n-1).to_a

h = 0
while !rest.empty? && rest.map {|i| diff[i]}.max >= 0
    i = rest.select {|i| h + min[i] >= 0}.max_by {|i| diff[i]}
    if !i
        puts 'No'
        exit
    else
        h += diff[i]
        rest.delete(i)
    end
end

h = 0
until rest.empty?
    i = rest.select {|i| h + min_rev[i] >= 0}.max_by {|i| diff_rev[i]}
    if !i
        puts 'No'
        exit
    end
    h += diff_rev[i]
    rest.delete(i)
end

puts 'Yes'

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

int A, B, K;

int main() {

    cin>>A>>B>>K;

    for(int i=0;i<K;++i) {
        if (i%2==0) {
            if(A%2==1)A -= 1;
            A /= 2;
            B += A;
        }else {
            if(B%2==1)B -= 1;
            B /= 2;
            A += B;
        }
    }

    cout<<A<<' '<<B<<endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
int main()
{
    int n,i,j=0,k;
    char a[100],b[100];
    while(scanf("%d",&n)!=EOF)
    {
        int y=2*n;
        char c[y];
        scanf("%s%s",&a,&b);
        for(i=0,j=0,k=0;k<(y-1);i++,j++,k=k+2)
        {
            c[k]=a[i];
            c[k+1]=b[j];
        }
        c[y]='\0';
        cout<<c<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
#define EPS 1e-8
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,m;
ll k;
ll x[100005];
int a[100005];
int nextt[100005];
int tmp[100005];
int res[100005];

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lld",&x[i]);
	}
	for(int i=0;i<n-1;i++){
		nextt[i]=i;
		res[i]=i;
	}
	scanf("%d%lld",&m,&k);
	for(int i=0;i<m;i++){
		scanf("%d",&a[i]);
		a[i]--;
	}
	for(ll i=0;i<m;i++){
		swap(nextt[a[i]-1],nextt[a[i]]);
	}
	while(k>0){
		if(k&1){
			for(int i=0;i<n-1;i++){
				res[i]=nextt[res[i]];
			}
		}
		for(int i=0;i<n-1;i++){
			tmp[i]=nextt[nextt[i]];
		}
		for(int i=0;i<n-1;i++){
			nextt[i]=tmp[i];
		}
		k>>=1;
	}
	ll now=x[0];
	for(int i=0;i<n;i++){
		printf("%lld\n",now);
		now+=x[res[i]+1]-x[res[i]];
	}
	return 0;
}


Measured memory_bytes: 3584
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
int main() {
  double a, b, c, d;
  cin >> a >> b >> c >> d;
  // double e = d * 6.0;
  // double f = c * 30.0 + d * 0.5;
  double g = (c * 30.0 - d * 5.5) * acos(-1) / 180.0;
  cout << fixed << setprecision(10)
       << sqrt(a * a + b * b - 2.0 * a * b * cos(g)) << '\n';
  return 0;
}


Measured memory_bytes: 4252
// abc158_b.cc
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

	ll ans = n / (a+b) * a;
	ans += min(a, n % (a+b));
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String[] args){

    Scanner sc = new Scanner(System.in);

    double r = sc.nextDouble();
    double pi = Math.PI;
    double area = pi * r * r;
    double length = 2 * r * pi;
    System.out.printf("%f %f", area,length);
    sc.close();
    }
}


Measured memory_bytes: 28280
#include<iostream>
#include<string>
using namespace std;
int main(){
	int h,w,i,j;
	string s;
	cin >> h >> w;
	for(i=0;i<=w+1;i++)
		cout << "#" ;
	cout << endl;
	for(i=0;i<h;i++){
		cout << "#";
		cin >> s;
        cout << s;
		cout << "#" << endl;
	}
	for(i=0;i<=w+1;i++)
		cout << "#" ;
    cout << endl;
}


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

int main(){
  int N, K;
  cin >> N >> K;
  vector<vector<long long>> B(10);
  for(int i = 0; i < N; ++i){
    int c, g;
    cin >> c >> g;
    --g;
    B[g].push_back(c);
  }
  for(int i = 0; i < 10; ++i){
    sort(B[i].rbegin(), B[i].rend());
    for(size_t j = 1; j < B[i].size(); ++j){
      B[i][j] += B[i][j-1];
    }
    for(size_t j = 0; j < B[i].size(); ++j){
      B[i][j] += (j+1)*j;
    }
  }
  vector<long long> dp(K+1);
  for(auto b : B){
    vector<long long> dp_ = dp;
    for(size_t i = 0; i < b.size(); ++i){
      for(int j = K; j>= 0; --j){
        if(j+i+1 > K) continue;
        dp_[j+i+1] = max(dp_[j+i+1], dp[j]+b[i]);
      }
    }
    swap(dp,dp_);
  }
  cout << dp.back() << endl;
}



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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
// constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

struct Edge {
    ll to, rev;
    long double cap;
    Edge(ll _to, long double _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

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

ll mod_inv(ll x, ll mod) {
    return mod_pow(x, mod - 2, mod);
}

//ラグランジュ補間(d+1)点をとおるd次式を求める
ll LagrangeInterpolation(vector<ll> y, ll t) {
    int n = y.size() - 1;
    if(t <= n)
        return y[t];
    ll fi = 1, ft = 1;
    for(ll i = 0; i <= n; i++) {
        if(i)
            (fi *= MOD - i) %= MOD;
        (ft *= t - i) %= MOD;
    }
    ll ret = 0;
    for(ll i = 0; i <= n; i++) {
        (ret += y[i] * ft % MOD * mod_inv(t - i, MOD) % MOD * mod_inv(fi, MOD) % MOD) %= MOD;
        (fi *= (i + 1) * mod_inv(MOD - n + i, MOD) % MOD) %= MOD;
    }
    return ret;
}

ll nCr(int n, int r) {
    if(n < r)
        return 0;

    ll ret = 1;
    REP(i, r) {
        (ret *= n - i) %= MOD;
        (ret *= mod_inv(i + 1, MOD)) %= MOD;
    }
    return ret;
}

ll f(int n) {
    ll ret = 0;
    REP(i, (n - 5) / 2 + 1) {
        ret += nCr(i + 4, 4) * nCr(n - 2 * i + 5, 10) % MOD;
        ret %= MOD;
    }
    return ret;
}

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

    if(n < 5) {
        cout << 0 << en;
        return;
    }

    vec<ll> y(16); //15次式になるので16点取れば十分
    REP(i, 16) {
        y[i] = f(2 * i + 5 + (n - 5) % 2);
    }
    cout << LagrangeInterpolation(y, (n - 5) / 2) << en;
}

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

    ll t;
    cin >> t;
    while(t--)
        solve();

    return 0;
}


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

int main(){
  int n; cin>>n;
  vector<int> num(n);
  for(int i=0;i<n;i++){
    cin>>num[i];
  }
  long long ans=0;
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      ans+=num[i]*num[j];
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		//データ取り込み
		Scanner sc = new Scanner(System.in);
		//String S = sc.next();
		//int N = sc.nextInt();
		//System.out.println();
		String S = sc.next();
		int cnt = 0;
		
		for(char a : S.toCharArray()){
			if(a == '1'){
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

Measured memory_bytes: 23380
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;
using mapis = unordered_map<Int,string>;
using mapii = unordered_map<Int,Int>;
using pii = pair<Int,Int>;

Int GCD(Int a, Int b){
    if(b==0) return a;
    if(a < b) return GCD(b, a);
    unsigned r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}
Int printX(Int r, Int D, Int X, int count){
    if(count == 10){
        return 0;
    }
    Int nextX = r*X - D;
    cout<< nextX <<endl;
    printX(r,D,nextX,count+1);

}

int myPow(int x, int p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    return x * myPow(x, p-1);
}

int main() {
    string S;
    cin >>S;
    int ans =0;
    if(S.size()%2 == 1){
        int middle = S.size()/2;
        rep(i,middle){
            if(S[i]!=S[S.size()-1-i]){
                ans++;
            }
        }
    }else{
        int middle = S.size()/2;
        rep(i,middle){
            if(S[i]!=S[S.size()-1-i]){
                ans++;
            }
        }
    }




    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(){
    string S;
    cin >> S;
    int counter = 0;
    if (S[0] == 'o') ++counter;
    if (S[1] == 'o') ++counter; 
    if (S[2] == 'o') ++counter;
    cout << 700+counter*100 << endl;
    
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>
#include <fstream>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

constexpr int MOD = 1e9+7;

namespace graph { // not verified

constexpr int MaxV = 1010;

struct scc {

  int V = MaxV;
  vector<int> G[MaxV];
  vector<int> rG[MaxV];
  vector<int> vs;
  vector<bool> used;
  vector<int> comp;
  int SCCGraphSize;

  scc(): V(MaxV) { comp.resize(MaxV); }
  scc(int V_): V(V_) { comp.resize(MaxV); }

  void add_edge(int from, int to) {
    G[from].push_back(to);
    rG[to].push_back(from);
  }

  void dfs(int v) {
    used[v] = 1;
    for(auto e: G[v]) {
      if(!used[e]) dfs(e);
    }
    vs.push_back(v);
  }

  void rdfs(int v, int k) {
    used[v] = 1;
    comp[v] = k;
    for(auto e: rG[v]) {
      if(!used[e]) rdfs(e, k);
    }
  }

  void solve() {
    used.clear(); used.resize(MaxV);
    vs.clear();
    for(int i = 0; i < V; i++) {
      if(!used[i]) dfs(i);
    }
    used.clear(); used.resize(MaxV);
    int k = 0;
    for(int i = vs.size() - 1; i >= 0; i--) {
      if(!used[vs[i]]) rdfs(vs[i], k++);
    }
    SCCGraphSize = k;
  }

};

}

vector<vector<int>> tree;
ll dp[1010];

ll solve(int curr, int par) {
  ll& ret = dp[curr];
  if(ret + 1) return ret;
  ret = 1;
  for(auto e: tree[curr]) {
    if(e == par) continue;
    ret *= solve(e, curr);
    ret %= MOD;
  }
  return (ret + 1) % MOD;
}

int main() {

  int N, M; cin >> N >> M;
  graph::scc scc_graph(N);
  rep(i, M) {
    int S, D; cin >> S >> D; S --, D --;
    scc_graph.add_edge(S, D);
  }

  scc_graph.solve();

  auto& K = scc_graph.SCCGraphSize;
  auto& g = scc_graph.G;
  auto& comp = scc_graph.comp;

  tree.resize(K);
  int deg[1010] = {};

  rep(i, N) {
    for(auto e: g[i]) {
      if(comp[i] == comp[e]) continue;
      tree[comp[e]].push_back(comp[i]);
      deg[comp[i]] ++;
    }
  }

  rep(i, K) {
    sort(tree[i].begin(), tree[i].end());
    tree[i].erase(unique(tree[i].begin(), tree[i].end()), tree[i].end());
  }

  minus(dp);

  ll ans = 1;

  rep(i, K) if(deg[i] == 0 && dp[i] < 0) {
    ans *= solve(i, -1);
    ans %= MOD;
  }

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

Measured memory_bytes: 3288
#include <bits/stdc++.h>
#define LL long long
const LL MOD = 998244353;
const int MAXN = 100005;
using namespace std;

int N, L, R;
vector<int> G[2*MAXN];
bool vis[2*MAXN];

void dfs(int v) {
	if (v < MAXN) L++;
	else R++;
	
	vis[v] = true;
	for (int to : G[v]) {
		if (!vis[to]) {
			dfs(to);
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		G[x].push_back(y + MAXN);
		G[y + MAXN].push_back(x);
	}
	
	LL tot = 0;
	for (int i = 0; i < MAXN; i++) {
		L = R = 0;
		dfs(i);
		tot += (LL) L * R;
	}
	
	cout << tot - N << '\n';
}

Measured memory_bytes: 10240
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <string.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 2147483647
#define LLINF 9223372036854775807
using namespace std;
int main(){
	string s;
	cin>>s;
	string t=s;
	reverse(t.begin(),t.end());
	bool flag=0;
	if(s!=t)flag=1;
	t="";
	for(int i=0;i<s.size()/2;i++)t+=s[i];
	string k=t;
	reverse(k.begin(),k.end());
	if(k!=t)flag=1;
	t="";
	k="";
	for(int i=s.size()/2+1;i<s.size();i++)t+=s[i];
	k=t;
	reverse(k.begin(),k.end());
	if(k!=t)flag=1;
	if(flag)cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <time.h>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
#include <bitset>
using namespace std;
#define FOR(I,F,N) for(int I = F; I < (int)(N); I++)
#define rep(i, n) FOR(i, 0, n)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;
int StrToInt(string);
string IntToStr(int);
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main(void){
	string S;
	cin >> S;
	for(int i = S.size(); i--;)cout << S[i];
	cout << endl;

	return 0;
}



int StrToInt(string s){
	stringstream ss;
	ss << s;
	int val;
	ss >> val;
	return val;
}
string IntToStr(int i){
	stringstream ss;
	ss << i;
	return ss.str();
}

Measured memory_bytes: 1176
#include <vector>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <iomanip>
#include <limits>
#include <fstream>
#include <algorithm>
#include <sstream>
#include <map>
#include <unordered_map>
#include <ctime>
#include <cassert>
#include <cstring>
#include <sys/time.h>
#include <stdlib.h>
using namespace std;

int main(int argc, char *argv[]){
  int n;
  cin >> n;
  vector<int> a;
  for(int i=0;i<n;i++){
    int ai;
    cin >> ai;
    a.push_back(ai);
  }
  bool b = true;
  for(int i=0;i<n;i++){
    if(a[i]%2==0){
      if(!(a[i]%3==0||a[i]%5==0)){
        b = false;
      }
    }
  }
  if(b==true){
    cout << "APPROVED" << endl;
  }else{
    cout << "DENIED" << endl;
  }
  return 0;
}


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

int main()
{
  int a, b, k;
  cin >> a >> b >> k;
  int ans = 0;
  for (int i = min(a,b)+1; i > 0; i--)
  {
    if ((a % i == 0) && (b % i == 0))
    {
      ans++;
    }
    if (ans == k)
    {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int n; scanf("%d", &n);
    char s[100010]; scanf("%s", s);

    int count = 1;

    for (int i=1; i<n; i++)
    {
        if (s[i] != s[i-1]) count++;
    }

    printf("%d\n", count);
}

Measured memory_bytes: 1816
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pi>
#define vpl vector<pl>
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005

int n,p[200005],r[200005];
ll d,a[200005],f[200005],g[200005],ans;

vector <pair<ll,pi>> s;

int Par(int nod){
	if(p[p[nod]]==p[nod]) return p[nod];
	else return p[nod]=Par(p[nod]);
}

void Unite(int x, int y){
	x=Par(x); y=Par(y);
	if(x==y) return;
	if(r[x]>r[y]) swap(x,y);
	if(r[x]==r[y]) r[y]++;
	p[x]=y;
}

void DC(int l, int r){
	if(l==r) return;
	int mid=(l+r)/2;
	DC(l,mid);
	DC(mid+1,r);
	int x=0,y=0;
	for(int i=l;i<=mid;i++){
		if(f[i]<f[x]) x=i;
	}
	for(int i=mid+1;i<=r;i++){
		if(g[i]<g[y]) y=i;
	}
	for(int i=l;i<=mid;i++){
		s.pb({f[i]+g[y],{i,y}});
	}
	for(int i=mid+1;i<=r;i++){
		s.pb({f[x]+g[i],{x,i}});
	}
}

int32_t main(){
	ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
#ifdef LOCAL_DEFINE
	ifstream cin("input.in");
#endif

	cin >> n >> d;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		p[i]=i;
		f[i]=-d*i+a[i];
		g[i]=d*i+a[i];
	}
	f[0]=g[0]=LINF;
	DC(1,n);
	sort(s.begin(),s.end());
	for(pair<ll,pi> i : s){
		if(Par(i.y.x)==Par(i.y.y)) continue;
		Unite(i.y.x,i.y.y);
		ans+=i.x;
	}
	cout << ans;
	
#ifdef LOCAL_DEFINE
	cerr << "\nTime elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << " \n";
#endif
}


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

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

  int d = 0;
  int ans = 1;
  for (int i : v) {
    d += i;
    if (X < d) {
      cout << ans << endl;
      return 0;
    }
    ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <cmath>
#include <deque>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define mt make_tuple
#define pq priority_queue<ll>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vecpll vector<pll>
#define vecbl vector<bool>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
string stin(){string s;cin>>s;return s;}

int main(){
    ll a=in(),v=in(),b=in(),u=in(),t=in();
    bool flag=abs(a-b)<=(v-u)*t;
    if(flag)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


Measured memory_bytes: 3680
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int main(){

	vector<int> V;

	int num_query;
	scanf("%d",&num_query);

	int command,tmp;

	for(int loop = 0; loop < num_query; loop++){
		scanf("%d",&command);

		switch(command){
		case 0:
			scanf("%d",&tmp);
			V.push_back(tmp);
			break;
		case 1:
			scanf("%d",&tmp);
			printf("%d\n",V[tmp]);
			break;
		case 2:
			V.pop_back();
			break;
		}
	}

	return 0;
}




Measured memory_bytes: 3928
import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p]
        if tmp[0] == x: return True
        if x < tmp[0]:
            p = tmp[1]
        else:
            p = tmp[2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p]
    if x== tmp[0]: return p
    elif x<tmp[0]:
        tree[p][1]=insert(tmp[1],x)
    else:
        tree[p][2]=insert(tmp[2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='f':
        if search(0,int(s[5:])): print 'yes'
        else: print 'no'
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

Measured memory_bytes: 118628
let lower_bound (a : int array) first last v =
  let rec doit len first =
    if len = 0 then first
    else
      let half = len / 2 in
      let mid = first + half in
      if a.(mid) < v then doit (len - half - 1) (mid + 1)
      else doit half first in
  doit (last - first + 1) first

let () =
  let n = read_int () in
  let t = Array.make (n + 1) max_int in
  let rec doit i =
    if i = n then lower_bound t 0 n max_int
    else begin
      let a = read_int () in
      t.(lower_bound t 0 n a) <- a;
      doit (i + 1)
    end in
  Printf.printf "%d\n" (doit 0)

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

#define inf 0x7f7f7f7f
const int N=2100;

int n,k,q,x,y,ans=inf;
int a[N];
priority_queue<int,vector<int>,greater<int> >que;
multiset<int>lans;

int main()
{
	scanf("%d%d%d",&n,&k,&q);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1;i<=n;i++)
	{
		x=a[i];y=inf;
		lans.clear();
		que=priority_queue<int,vector<int>,greater<int> >();
		for(int j=1;j<=n+1;j++)
			if(j>n||a[j]<x)
			{
				while(que.size()>=k)
				{
					lans.insert(que.top());
					que.pop();
				}
				que=priority_queue<int,vector<int>,greater<int> >();
			}
			else que.push(a[j]);
		int cnt=1;
		for(auto it=lans.begin();it!=lans.end();it++,cnt++)
			if(cnt==q){y=*it;break;}
		//printf("%d %d\n",x,y);
		ans=min(y-x,ans);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 384
package main

import "fmt"

func main() {
	var s, t string
	fmt.Scan(&s, &t)

	cnt := 0
	for i := 0; i < 3; i++ {
		if s[i:i+1] == t[i:i+1] {
			cnt++
		}
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 512
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int Y = sc.nextInt();
    int out = 0;
    if (X <= 3) out += 400000 - X*100000;
    if (Y <= 3) out += 400000 - Y*100000;
    if (X == 1 && Y == 1) out += 400000;
    System.out.println(out);
  }
}


Measured memory_bytes: 23764
chars = gets.strip.to_s

n = chars.length
k1 = chars.slice((n-1)/2)

k2 = chars.slice((n+3)/2-1..n)
if chars == chars.reverse && k1 == k1.reverse && k2 == k2.reverse
  puts 'Yes'
else
  puts 'No'
end




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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    string S;
    ll abc[3] = {};
    ll maxi = 0;
    ll count = 0;
    ll mini = numeric_limits<ll>::max();
    cin >> S;
    iter(c, S) abc[c - 'a']++;
    iter(i, abc) {
        if(i > 0) count++;
        maxi = max(maxi, i);
        mini = min(mini, i);
    }
    cout << (S.size() == 1 || maxi - mini <= 1 ? "YES" : "NO") << endl;
    return 0;
}


Measured memory_bytes: 512
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let k: usize = it.next().unwrap().parse().unwrap();
    let mut e = vec![0f64; n + 1];
    for e in e.iter_mut().take(n) {
        let p: f64 = it.next().unwrap().parse().unwrap();
        *e = (p + 1.0) / 2.0;
    }
    for i in (0..n).rev() {
        e[i] += e[i + 1];
    }
    let mut ans = 0f64;
    for i in k..(n + 1) {
        ans = ans.max(e[i - k] - e[i]);
    }
    println!("{:.7}", ans);
}

fn main() {
    run();
}

Measured memory_bytes: 6396
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;


long long func( long long a, long long b, long long p ) {
    if ( b == 0 ) {
        return 1;
    }
    else if ( b%2 == 0 ) {
        long long temp = func( a, b/2, p );
        return (temp * temp)%p;
    }
    else {
        return ( func( a, b-1, p ) * a ) % p;
    }
    
}


int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    
    
    for ( int i = 0; i < N; i++ ) {
        cin >> A[i];    
    }
    long long ans = 0;

    vector<int> B(N);
    vector<long long> C(N,1);
    for ( long long x = 2; x * x <= (long long)1e+6; x++ ) {

        int m = 0;
        for ( int i = 0; i < N; i++ ) {
            
            int count = 0;
            while ( true ) {
                if ( A[i]%x != 0 ) { break; }
                A[i] /= x;
                count++;
            }
            B[i] = count;
            m = max( m, count );
        }
        for ( int i = 0; i < N; i++ ) {
            long long y = 1;
            for ( int j = 0; j < m - B[i]; j++ ) {
                y *= x;
                y %= MOD;
            }
            C[i] *= y;
            C[i] %= MOD;
        }
    }

    long long z = 1;
    set<long long> s;
    for ( int i = 0; i < N; i++ ) {
        if ( s.find(A[i]) == s.end() ) {
            s.insert(A[i]);
            z *= A[i];
            z %= MOD;
        }
        
    }

    for ( int i = 0; i < N; i++ ) {
        long long zz = (z * func(A[i],MOD-2,MOD))%MOD;
        ans += (C[i] * zz)%MOD;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define str string
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define all(x) x.begin(),x.end()
signed main(){
  int N,M,O=0,P,count=0,count2=0;
  str S,W,T;
  cin>>S;
  for(int i=0;i<S.size();i+=2)cout<<S.at(i);
  cout<<endl;
}


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


int main() {
    string S;
    cin>>S;
    int countB=0;
    int countA=0;
    rep(i,3){
        if(S[i]=='B')countB++;
    }
     rep(i,3){
        if(S[i]=='A')countA++;
    }
    if(countB==3||countA==3)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

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

int main(void){
    int n;
    vector<double> x(110),y(110);
    cin>>n;
    cout<<fixed<<setprecision(12);
    for(int i=0;i<n;i++){
        cin>>x.at(i);
    }
    for(int i=0;i<n;i++){
        cin>>y.at(i);
    }    
    double D1,D2,D3,Dinf=0;
    for(int i=0;i<n;i++){
        D1+=abs(x.at(i)-y.at(i));
        D2+=pow(abs(x.at(i)-y.at(i)),2);
        D3+=pow(abs(x.at(i)-y.at(i)),3);
        Dinf = max(Dinf , abs(x.at(i)-y.at(i) ) );
    }
    cout<<D1<<endl<<pow(D2,0.5)<<endl<<pow(D3,(double)1/3)<<endl<<Dinf<<endl;
}



Measured memory_bytes: 3468
n,k=map(int,input().split())
x=list(map(int,input().split()))
for i in range(n-k+1):
    if i==0:
        a=min(abs(x[i])+abs(x[i]-x[i+k-1]),abs(x[i+k-1])+abs(x[i]-x[i+k-1]))
    else:
        a=min(a,min(abs(x[i])+abs(x[i]-x[i+k-1]),abs(x[i+k-1])+abs(x[i]-x[i+k-1])))
print(a)

Measured memory_bytes: 14252
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
	int x=0,f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<3)+(x<<1)+ch-'0';
	return x*f;
}
inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<3)+(x<<1)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int N=2e5,p=1e9+7;
struct S1{
	int x,v;
	void rd(){x=read(),v=read();}
	bool operator <(const S1 &tis)const{return v<tis.v;}
}A[N+10];
struct S2{
	int l,r;
	void insert(int _l,int _r){l=_l,r=_r;}
	bool operator <(const S2 &tis)const{return r!=tis.r?r<tis.r:l<tis.l;}
}v[N+10];
int stack[N+10],top;
int s[N+10],f[N+10];
int main(){
	int n=read();
	for (int i=1;i<=n;i++)	A[i].rd();
	sort(A+1,A+1+n);
	for (int i=1;i<=n;i++){
		if (!top||A[i].x>A[stack[top]].x)	stack[++top]=i;
		int l=1,r=top;
		while (l<=r){
			int mid=(l+r)>>1;
			if (A[i].x<=A[stack[mid]].x)	r=mid-1;
			else	l=mid+1;
		}
		v[i].l=stack[l];
	}
	top=0;
	for (int i=n;i>=1;i--){
		if (!top||A[i].x<A[stack[top]].x)	stack[++top]=i;
		int l=1,r=top;
		while (l<=r){
			int mid=(l+r)>>1;
			if (A[stack[mid]].x<=A[i].x)	r=mid-1;
			else	l=mid+1;
		}
		v[i].r=stack[l];
	}
	sort(v+1,v+1+n);
	int now=1,Ans=0;
	for (int i=1;i<=n;i++){
		while (v[now].r<v[i].l-1)	now++;
		f[i]=(s[i-1]-s[now-1]+p)%p;
		if (v[i].l==1)	f[i]++;
		if (v[i].r==n)	Ans=(Ans+f[i])%p;
		s[i]=(s[i-1]+f[i])%p;
	}
	printf("%d\n",Ans);
	return 0;
}

Measured memory_bytes: 5760
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let ab = read_vec::<String>();
    let ans = if ab[0] == "H" {
        match &*ab[1] {
            "H" => "H",
            "D" => "D",
            _ => "",
        }
    } else {
        match &*ab[1] {
            "H" => "D",
            "D" => "H",
            _ => "",
        }
    };
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;
typedef pair<int,int> pii;

const int maxn = 110000;

int n, m, a, b;
vector <int> adj[maxn];
vector <pii> cut;

bool mark[maxn];
int dp[maxn], h[maxn], par[maxn];
void dfs(int v)
{
    mark[v]=1;
    dp[v] = -1;
    int t = max(0, h[v]-1);
    for(auto u : adj[v])
    {
        if(!mark[u])
        {
            par[u] = v, h[u] = h[v]+1, dfs(u);
            dp[v] = (dp[v]==-1 ? dp[u] : min(dp[v], dp[u]));
        }
        else
        {
            t = min(t, h[u]);
        }
    }

    if((dp[v] >= h[v] || dp[v] == -1) && t == h[v]-1)
        cut.pb(mp(min(par[v],v), max(par[v],v)));
    dp[v] = min((dp[v]==-1 ? t : dp[v]), t);
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m && cin>>a>>b; i ++)
        adj[a].pb(b), adj[b].pb(a);

    dfs(0);

    //for(int i = 0; i < n; i++)  cout << i << " : " << dp[i] << " , " << h[i]  << " , "  << par[i] << endl;

    sort(cut.begin(), cut.end(), [](pii a, pii b){return a.first == b.first ? a.second < b.second : a.first < b.first;});
    for(auto e : cut)
        cout << e.first << ' ' << e.second << endl;
    return 0;
}



Measured memory_bytes: 7136
using System;

class Prime_Numbers {
	public static void Main() {

		int count = 0;
		string num = Console.ReadLine();
		int n = int.Parse(num);
		int[] a = new int[n];

		for(int i = 0; i < n; i++) {
			a[i] = int.Parse(Console.ReadLine());
		}

		for(int i = 0; i < n; i++) {
			if(Prime(a[i])) {
				count++;
			}
		}

		Console.WriteLine(count);

	}

	static bool Prime(int n) {

		if(n == 2) return true;
		if(n < 2 || n % 2 == 0) return false;
		int i = 3;
		while(i <= Math.Sqrt(n)) {
			if(n % i == 0) {
				return false;
			}
			i = i + 2;
		}

		return true;

	}

}

Measured memory_bytes: 9140
// D - Redistribution
#include <bits/stdc++.h>
using namespace std;

using ll = int64_t;
using vl = vector<ll>;
#define MOD 1000000007
#define madd(a,b) (((a)+(b))%MOD)
#define mmul(a,b) (((a)*(b))%MOD)
vl fac{1,1}, inv{0,1}, finv{1,1};

// n 個の配列に、mod p で前処理する
void finv_init(int n){
	for(int i=2; i<=n; ++i){
		fac.push_back(mmul(fac.back(), i));
		inv.push_back(madd(MOD, -mmul(inv[MOD%i], MOD/i)));
		finv.push_back(mmul(finv.back(), inv.back()));
	}
}

// 組み合わせ nCr(mod m)
ll nCr(int n, int r){
	int m = MOD;
	if(n<r || n<0 || r<0) return 0;
	return fac[n] * (finv[n-r] * finv[r] % m) % m;
}

// 重複組合せ nHr(mod m)
#define nHr(n,r) nCr((n)+(r)-1,(r))

int main(){
	ll S; cin>>S;
	finv_init(S);
	ll ans = 0;
	for(int n=1; n<=S; ++n){
		if(S < 3*n) continue;
		ans += nHr(n, S - 3*n);
		ans %= MOD;
	}
	cout<< (ans + MOD) % MOD <<endl;
}


Measured memory_bytes: 3628