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

#pragma region Macro
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v) sort(v.begin(), v.end())
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define vvi vector<vector<int>>
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#pragma endregion

void solve(){
	#define int ll
	// ここに処理を記述
	// コンパイル時はエイリアス「gpp」--> c++17でコンパイル

	int n,m,x;
	cin >> n >> m >> x;
	vi c(n);
	vvi a(n,vi(m));
	rep(i,n){
		cin >> c[i];
		rep(j,m){
			cin >> a[i][j];
		}
	}

	int cost;
	vi now(m);
	int ans = 1e9 + 7;
	for(int bit = 0; bit < (1<<n); ++bit){
		fill(now.begin(), now.end(), 0);
		cost = 0;
		rep(i,n){
			if(bit & (1<<i)){
				cost += c[i];
				rep(j,m){
					now[j] += a[i][j];
				}
			}
		}
		bool check = true;
		rep(i,m){
			if(now[i] < x){
				check = false;
			}
		}
		if(check){
			// cout << cost << endl;
			chmin(ans, cost);
		}
	}

	if(ans == 1e9+7) cout << "-1" << endl;
	else cout << ans << endl;

}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	
	solve();
	return 0;
}

Measured memory_bytes: 3616
#include<time.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
using namespace std;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

template<typename ...Ts>
void show(Ts... ts){
  cout<<"#:";
  auto print=[](auto v){cout<<v<<" ";};
  initializer_list<int>{(void(print(ts)),0)...};
  cout<<endl;
}

int main(void){
    int n,x,a;
    int m=1e9;
    cin>>n>>x;
    int ans=n;
    rep(i,n){
        cin>>a;
        x-=a;
        m=min(m,a);
    }
    
    ans+=x/m;
    cout<<ans;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
    int A,B,C;
    cin >> A >> B >> C;
    
    if(A-B>C){
        cout << 0 << endl;
    }else{
        cout << C-(A-B) << endl;
    }
    return 0;
}


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

int ans[100010], mx;

void dfs(vector<vector<pair<int, int>>> &v, int key){
	int proh=0;
	for(int i=0; i<v[key].size(); ++i){
		proh=ans[v[key][i].first];
		if(proh>0) break;
	}
	int now=1;
	for(int i=0; i<v[key].size(); ++i){
		while(now==proh) ++now;
		if(ans[v[key][i].first]==0){
			ans[v[key][i].first]=now;
			dfs(v, v[key][i].second);
			++now;
		}
	}
}

int main() {
	int N;
	cin >> N;
	vector<vector<pair<int, int>>> g(N+1);
	for(int i=1; i<N; ++i){
		int a, b;
		cin >> a >> b;
		g[a].push_back(make_pair(i, b));
		g[b].push_back(make_pair(i, a));
	}
	mx=0;
	for(int i=1; i<=N; ++i){
		if(mx<g[i].size()) mx=g[i].size();
	}
	dfs(g, 1);
	cout << mx << endl;
	for(int i=1; i<N; ++i) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 6912
n = int(input())
di = [[0]*9 for _ in range(9)]
for i in range(1, n+1):
    p = list(str(i))
    if p[-1] == '0':
        continue
    di[int(p[0])-1][int(p[-1])-1]+=1
result = 0
for i in range(9):
    for j in range(9):
        c = di[i][j]
        d = di[j][i]
        result+=c*d
print(result)

Measured memory_bytes: 40556
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

typedef long long ll;
using namespace std;

int main() {
    
    int n, k;
    cin >> n >> k;
    
    vector<int> h(n, 0);
    for (int i = 0; i < n; i++)
        cin >> h[i];
    
    sort(h.begin(), h.end());
    
    int ans = 0x7FFFFFFF;
    for (int i = 0; i + k - 1 < n; i++) {
        ans = min(ans, h[i + k - 1] - h[i]);
    }
    
    cout << ans << endl;
    
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int A[100010];
int cnt[100010];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		cnt[A[i]]++;
	}
	for (int i = 1; i < N; i++) {
		if (cnt[i] > 2) {
			cout << 0 << endl;
			return 0;
		}
	}
	if (N % 2 == 1 && cnt[0]!=1) {
		cout << 0 << endl;
		return 0;
	}
	int ans = 1;
	for (int i = 0; i < N / 2; i++) {
		ans = (ans * 2) % mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
    int n,i,s=0;
    char c;
    scanf("%d",&n);
    for(i=0;i<n;i++){
    	scanf(" %c",&c);
    	if(c=='Y'){
    		s=1;
    	}
    }
    if(s){
    	printf("Four\n");
    }else{
    	printf("Three\n");
    }
    
    return 0;
}

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

// 0-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T, T)> F;
  int n;
  F f;
  T unit;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t) : f(f), unit(t) { init(newn); }
  SegmentTree(const vector<T> &v, F f, T t) : f(f), unit(t) {
    int _n = v.size();
    init(v.size());
    for (int i = 0; i < _n; ++i) dat[n + i] = v[i];
    for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
  }
  void init(int newn) {
    n = 1;
    while (n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while (k >>= 1) {
      dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
    }
  }
  // [a,b)
  T query(int a, int b) {
    T vl = unit, vr = unit;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
  // func(unit) == false
  // min left: st <= res && func(seg.query(res,n))
  template <typename C>
  int find_left(int st, C &func, T acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = f(acc, dat[k]);
      return func(acc) ? k - n : -1;
    }
    int mid = (l + r) >> 1;
    if (mid <= st) return find_left(st, func, acc, (k << 1) | 1, mid, r);
    if (st <= l && !func(f(acc, dat[k]))) {
      acc = f(acc, dat[k]);
      return -1;
    }
    int nres = find_left(st, func, acc, (k << 1), l, mid);
    if (~nres) return nres;
    return find_left(st, func, acc, (k << 1) | 1, mid, r);
  }
  template <typename C>
  int find_left(int st, C &func) {
    T acc = unit;
    return find_left(st, func, acc, 1, 0, n);
  }

  // max right: res <= st && func(seg.query(0,res))
  template <typename C>
  int find_right(int st, C &func, T acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = f(dat[k], acc);
      return func(acc) ? r : -1;
    }
    int mid = (l + r) >> 1;
    if (st <= mid) return find_right(st, func, acc, k << 1, l, mid);
    if (r <= st && !func(f(dat[k], acc))) {
      acc = f(dat[k], acc);
      return -1;
    }
    int nres = find_right(st, func, acc, (k << 1) | 1, mid, r);
    if (~nres) return nres;
    return find_right(st, func, acc, k << 1, l, mid);
  }
  template <typename C>
  int find_right(int st, C &func) {
    T acc = unit;
    return find_right(st, func, acc, 1, 0, n);
  }
};

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (auto &p : a) cin >> p;
  reverse(a.begin(), a.end());
  auto f = [](int l, int r) { return max(l, r); };
  SegmentTree<int> seg(a, f, -1);
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1)
      seg.update(n - 1 - (x - 1), y);
    else if (t == 2)
      cout << seg.query(n - 1 - (y - 1), n - (x - 1)) << endl;
    else {
      auto c = [&](int p) { return p >= y; };
      int res = seg.find_right(n - (x - 1), c);
      if (res < 0)
        res = n + 1;
      else
        res = n - (res - 1);
      cout << res << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 6164
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
  
int main()
{
  int N;
  cin >> N;
  vector<string> a(N);
  REP(i, N) cin >> a[i];
  int M;
  cin >> M;
  vector<string> b(M);
  REP(i, M) cin >> b[i];
  
  map<string,int> A;
  REP(i,N){
    A[a.at(i)]++;
  }

  REP(i,M){
    A[b.at(i)]--;
  }

  int MAX = 0;
  for(auto x:A){
    MAX = max(MAX,x.second);
  }
  cout << MAX << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
long long inf=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};
 
int main(){
  char a,b;
  cin>>a>>b;
  if(a=='H'){
    cout<<b<<endl;
  }else{
    if(b=='D'){
      cout<<'H'<<endl;
    }else{
      cout<<'D'<<endl;
    }
  }
  return 0;
}



Measured memory_bytes: 256
from itertools import product

import numpy as np


def solve(string):
    n, m, *xyz = map(int, string.split())
    xyz = [[x, y, z] for x, y, z in zip(xyz[::3], xyz[1::3], xyz[2::3])]
    xyz = np.asarray(xyz)
    ans = 0
    for i, j, k in product([-1, 1], repeat=3):
        tmp = xyz.copy()
        tmp[:, 0] = i * xyz[:, 0]
        tmp[:, 1] = j * xyz[:, 1]
        tmp[:, 2] = k * xyz[:, 2]
        base = sum(sorted(np.sum(tmp, axis=1), reverse=True)[:m])
        ans = max(ans, base)
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))


Measured memory_bytes: 12588
if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    A = list([0])
    A.extend(a)
    A.append(0)

    sum = 0
    for i in range(1, n+2):
        sum += abs(A[i]-A[i-1])
    for i in range(1, n+1):
        print(sum-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))


Measured memory_bytes: 14044
#include <iostream>
using namespace std;
int main(){
    string S;
    cin >> S;
    int N = S.size(), MOD = 1000000007;
 
    long long dp[100010][4] = {};
    for(int i = N; i >= 0; --i){
        for(int j = 3; j >= 0; --j){
            if(i == N){
                dp[i][j] = (j == 3 ? 1 : 0);
            }else{
                dp[i][j] = dp[i+1][j] * (S[i] == '?' ? 3 : 1);
                if(j < 3 && (S[i] == '?' || S[i] == "ABC"[j])){
                    dp[i][j] += dp[i+1][j+1];
                }
                dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[0][0] << endl;
  /*
  cout << 3LL << endl;
  cout << 1LL << endl;
  cout << 2LL << endl;
  */


}

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

using namespace std;

int sol, N, M, ap[100009], ap2[100009];

int cntP (int i)
{
    int curr = 0;
    for (int j=i; j<=100000; j+=M)
        curr += ap[j] / 2;
    return curr;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
{
    int x;
    scanf ("%d", &x), ap[x] ++, ap2[x % M] ++;
}
for (int i=0; i <= M - i; i++)
{
    if (i == M - i || i == 0)
    {
        sol += ap2[i] / 2;
        continue;
    }
    int x = cntP (i), y = cntP (M - i);
    if (ap2[i] <= ap2[M - i]) sol += ap2[i], sol += min (y, (ap2[M - i] - ap2[i]) / 2);
    else sol += ap2[M - i], sol += min (x, (ap2[i] - ap2[M - i]) / 2);
}
printf ("%d\n", sol);
return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
const int MAXN=200005;
int read(){int x;scanf("%d",&x);return x;}
int n,k,a[MAXN],ans;
void readin(){
	n=read(),k=read(),ans=1e9+7;
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+n+1);
	for(int i1=1;i1<=n-k+1;i1++){
		int j=a[i1+k-1],i=a[i1];
	//	ans=min(ans,i*j<0?min(abs(i),abs(j))*2+max(abs(i),abs(j)):max(abs(i),abs(j)));
		ans=min(ans,min(abs(i),abs(j))+abs(i-j));
	}
	printf("%d\n",ans);
}
int main(){
	readin();
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include<map>
#include<cstring>
#include<iomanip>
#include <string>
#include <vector>	
#include<unordered_map>
#include<unordered_set>
using namespace std;


typedef long long unsigned llu;
typedef long double ld;
#define ll long long
#define PI 3.14159265358979323846
#define For(i, a, b) for (int i = a, sz = (int)b; i < sz; i++)
#define rFor(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fill(a, b) memset(a, b, sizeof(a))
#define IO ios_base::sync_with_stdio(false), cin.tie(0),cout.tie(0)
const ll mod = 1000000007;
const ll inf = 1000000000009;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);}

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdoutn

int main()
{
	IO;
	
	string s,st;
	cin>>s>>st;
	int ans=st.size();
	For(i,0,s.size()-st.size()+1)
	{	
		int res{};
		For(j,0,st.size())
		{
			if(st[j]!=s[i+j])res++;
		}
		ans=min(ans,res);
	}
	cout<<ans<<'\n';
	//system("pause");
	return 0;	
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n))
#define Vec(a,n) vector<string> (a)((n))
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0))
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0))
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a))
#define Reverse(a) reverse(All(a))
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define Lower(a,t) lower_bound(All(a),t)
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int nokori(int n){
    
}

signed main(){
    int n,k;
    cin >> n >> k;
    vec(dp,n);
    vec(h,n);
    REP(i,n){
        cin >> h[i];
    }
    REP(i,n){
        if(i==0){
            dp[0] = 0;
          continue;
        }
        FOR(j,1,k+1){
            int t = i - j;
            if(t<0){
                break;
            }
            else{
                int x = dp[t] + abs(h[i] - h[t]);
                if(x==0){
                    dp[i] = 0;
                    break;
                }
                else if(dp[i] == 0){
                    dp[i] = x;
                }
                else{
                    dp[i] = min(dp[i],x);
                }
            }
        }
    }
    cout << dp[n-1];
    
    return 0;
}



void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main()
{
    // 整数の入力
    int N,K;
    cin >> N;
    N = N % 56;
    K = N % 28;
    if(N % 4 == 0 || N % 7 == 0 || N % 11 == 0 || N == 15 || N == 18 || N == 19 || N == 23 || N == 27 || N == 31 || N == 26 || N == 30 || N == 34 || N == 38 || N == 25 || N == 29 || N == 37 || N == 41 || N == 45 || K % 4 == 0 || K % 7 == 0 || K % 11 == 0 || K == 15 || K == 18 || K == 19 || K == 23 || K == 27 || K == 26 || K == 25){
         cout << "Yes" << endl;
    }else{
         cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S, T):
    ans = 0
    for s, t in zip(S, T):
        if s != t:
            ans += 1

    return ans


def main():
    S = read_str()
    T = read_str()
    print(slv(S, T))


if __name__ == '__main__':
    main()


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

int main() {
	int N, D, X;
	cin >> N >> D >> X;
	long long int chara = X;
	vector<int> vec (N);
	for(int i = 0;i < N;i++){
		cin >> vec.at(i);
	}
	for(int i = 0;i < D;i++){
		for(int j = 0;j < N;j++){
			if(i % vec.at(j) == 0){
				chara++;
			}
		}
	}
	cout << chara << endl;
}

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

#define LL long long

#define FOR(INDEX, START, END) for (LL INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (LL INDEX = 0; INDEX < (COUNT); ++INDEX)


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

	LL ans = 0;


	map<LL, LL> div;
	for (;;) {
		bool hit = false;
		LL m = sqrt(N) + 1;
		for (int i = 2; i < m; ++i) {
			if (N % i == 0) {
				N /= i;
				div[i] += 1;
				hit = true;
				break;
			}
		}

		if (hit == false) {
			if (N != 1) {
				div[N] += 1;
			}
			break;
		}
	}

	for (auto const& pr : div) {
		int v = pr.second;
		for (int i = 1;; ++i) {
			if (v >= i) {
				v -= i;
				ans += 1;
			}
			else {
				break;
			}
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3708
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<sstream>
#include<functional>
#include<map>
#include<stack>
#include<set>
#include<cmath>

#define REP(i,s,e) for(int i=int(s);i<=int(e);i++)
#define rep(i,n) for(int i=0;i<int(n);i++)

#define EPS 1e-6

using namespace std;

int main(){

	double v;
	double g=9.8;

	while(true){

	cin >> v;

	if(cin.fail()) break;

	int h=(v*v)/(10*g)+2;

	cout << h << endl;

	}

	return 0;
}

Measured memory_bytes: 1224
import sys
def input():
    return sys.stdin.readline()[:-1]
import fractions
from functools import reduce

n=int(input())
c = list(map(int, input().split()))
mod=pow(10,9)+7

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

v=lcm(*c)%mod
ans=0

for i in range(n):
    ans += v * pow(c[i],mod-2,mod)
    ans%=mod

print(ans%mod)

Measured memory_bytes: 69464
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
using namespace std;
#define int long long
#define double long double
int gcd(int x, int y){
    if (y == 0)
        return x;
    x = x % y;
    gcd(y, x);
}
int keta(int n) {
    return to_string(n).length();
}
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  int x; // typedef long long ll;
  mint(int x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(int t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
main(){
    int n;
    cin >> n;
    vector<int>a(n);
    rep(i,n) cin>>a[i];
    vector<int>c(n+1);
    rep(i,n) c[i]==0;
    c[0]=3;
    mint ans=1;
    rep(i,n){
        if (!c[a[i]]) {
      puts("0");
      return 0;
    }
        ans*=c[a[i]];
        c[a[i]]--;
        c[a[i]+1]++;
    }
    cout<<ans.x<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(void){
   
   string s;
   cin >> s;
   int len = s.size();
   int c = 0;
   for(int i=0;i<len;i++){
       if(i%2 == 0){
           if(s[i] == 'R' || s[i] == 'U' || s[i] == 'D') c++;
       }
       else{
           if(s[i] == 'L' || s[i] == 'U' || s[i] == 'D') c++;
       }
   }
   
   if(c == len){
       cout << "Yes" <<endl;
   }
   else{
       cout << "No" <<endl;
   }
}

Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {
	
	public void exec() {
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
		int H = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int r = sc.nextInt();
		System.out.println((r<=x && x<=W-r && r<=y && y<=H-r)?"Yes":"No");
		sc.close();
	}
	public static void main(String[] args)  {
		new Main().exec();
	}
}

Measured memory_bytes: 26224
//by (111110101)2
#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>
using namespace std;
double n,x[11],y[11],ans;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			ans+=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
	}
	ans*=2;
	for(double i=1;i<=n-1;i++)
	{
		ans*=i;
	}
	for(double i=1;i<=n;i++)
	{
		ans/=i;
	}
	printf("%.10f",ans);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main () {
	
	int a,b,k, j = 0;
	int count[100];
	
	scanf("%d %d %d", &a, &b, &k);
	
	for (int i = 1; i <= a && i <= b; i++){
		if((a%i == 0) && (b%i == 0)){
			count[j] = i;
			j++;
	//		printf("b");
		}
	//	printf("a\n");
	}
	//	printf("j = %d\n", j);
		printf("%d", count[j-k]);
	
	
	
	
	return 0;
}

Measured memory_bytes: 128
result = {}

n = gets.to_i
n.times{
	s = gets.chomp
	if result[s] == nil then
		result[s] = 1
	else
		result[s] += 1
	end
}

m = gets.to_i
m.times{
	t = gets.chomp
	if result[t] == nil then
		result[t] = -1
	else
		result[t] += -1
	end
}

puts (result.values + [0]).max


Measured memory_bytes: 1788
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------
bool mm(int n){
    if(n > 0 && n <= 12){
        return true;
    }
    else{
        return false;
    }
}
void solve(){
}
int main(){
    string s;
    cin >> s;
    int fi = stoi(s) / 100;
    int se = stoi(s) % 100;
    string ans;
    if(mm(fi) && mm(se)){
        ans = "AMBIGUOUS";
    }
    else if(mm(fi)){
        ans = "MMYY";
    }
    else if(mm(se)){
        ans = "YYMM";
    }
    else{
        ans = "NA";
    }
    cout << ans << endl;
    
    solve();
    return 0;
}



Measured memory_bytes: 256
N, M = list(map(int, input().split()))

d = [-1] * N
illegal = False

for _ in range(M):
  s,c = list(map(int, input().split()))
  ## 代入できる条件
  ## 未代入または、前に代入された値と同じ
  if(d[s-1] == -1 or d[s-1] == c or d[s-1] == 0):
    d[s-1] = c
  else:
    illegal = True

if(len(d) > 1 and d[0] == 0):
  illegal = True

if(illegal):
  print(-1)
else:
  if(len(d) > 1 and d[0] == -1):
    d[0] = 1
  
  res = ""

  for value in d:
    if(value == -1):
      res += "0"
    else:
      res += str(value)

  print(res)

Measured memory_bytes: 3064
IDENTIFICATION DIVISION.
PROGRAM-ID. PROGRAM_ID.

DATA DIVISION.
WORKING-STORAGE SECTION.
01 a          PIC 9(10).
01 ans        PIC 9(10).
01 zs         PIC Z(9)9.

PROCEDURE DIVISION.
  ACCEPT a.
  COMPUTE ans = a + a ** 2 + a ** 3.
  MOVE ans TO zs.
  DISPLAY FUNCTION TRIM(zs).
  STOP RUN.


Measured memory_bytes: 3888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+23;

int r[maxn],c[maxn],w[maxn];
int n,m,k;	
pii a[maxn];
set<int> s[maxn];
#define x first
#define y second

int main(){
	cin>>n>>m>>k;
	for(int i=0;i<k;i++){
		scanf("%d%d",&a[i].first,&a[i].second);
		r[a[i].x]++;
		c[a[i].y]++;
		s[a[i].x].insert(a[i].y);
	}
	vector<int> q,w;
	for(int i=1,mx=*max_element(r+1,r+n+1);i<=n;i++){
		if(r[i]==mx) q.push_back(i);
	}
	for(int i=1,mx=*max_element(c+1,c+m+1);i<=m;i++){	
		if(c[i]==mx) w.push_back(i);
	}
	int ans=0;
	for(int i:q){
		for(int j:w){
			if(!s[i].count(j)){
				ans=r[i]+c[j];
				cout<<ans;
				return 0;
			}
			else{
				ans=r[i]+c[j]-1;
			}
		}
	}
	cout<<ans;
}

Measured memory_bytes: 73152
#include <iostream>
#include <vector>
#include <queue>
#include <limits>

template<typename T>
struct Dinic {

  struct Edge {
    int to;
    T cost;
    int rev;
  };

  std::vector<std::vector<Edge> > G;

  std::vector<int> level;

  std::vector<int> iter;

  Dinic(int n) {
    G.resize(n, std::vector<Edge>());
    level.resize(n, 0);
    iter.resize(n, 0);
  };

  void add_edge(int from, int to, T cost) {
    G[from].push_back((Edge){to, cost, (int) G[to].size()});
    G[to].push_back((Edge){from, 0, (int) G[from].size() - 1});
  };

  void create_level_graph(int s) {

    std::queue<int> que;


    std::fill(level.begin(), level.end(), -1);
    level[s] = 0;

    que.push(s);
    while(!que.empty()) {
      int v = que.front();
      que.pop();

      for(auto& edge: G[v]) {
        if(edge.cost > 0 && level[edge.to] < 0) {
          level[edge.to] = level[v] + 1;
          que.push(edge.to);
        }
      }
    }
  }

    T remove_shortest_aug_path(int v, int t, T max_capacity) {
      if(v == t) return max_capacity;

      for(int &i = iter[v]; i < G[v].size(); i++) {
        Edge &e = G[v][i];
        if(e.cost > 0 && level[v] < level[e.to]) {
          T d = remove_shortest_aug_path(e.to, t, std::min(e.cost, max_capacity));
          if(d > 0) {
            e.cost -= d;
            G[e.to][e.rev].cost += d;
            return d;
          }
        }
      }
      return 0;
    }

  T max_flow(int s, int t) {
    T flow = 0;
    const T INF = std::numeric_limits<T>::max();
    while(true) {
      create_level_graph(s);

      if(level[t] < 0) return flow;

      std::fill(iter.begin(), iter.end(), 0);
      T f;
      while(f = remove_shortest_aug_path(s, t, INF)) {
        flow += f;
      }
    }
  }
};



int main(void) {
  //最小カット問題に帰着させる。
  //手順はnico_shindanさんの「燃やす埋める問題」についてのslideshareに載っている。

  //今回は、あるコストの宝石を「壊す」「壊さない」の小問題に、
  // 「i番目を壊したら必ずni番目も壊さなければならない」という制約が付いたタイプである。

  //従って、s-(壊さない)->(i番目の宝石)-(壊す)->t というパスを作った場合、
  //(i)->(ni) に向かって容量無限のパスを繋げれば良い

  //また最小カット問題の場合、グラフのコストが必ず正でなければならない。(負を含むとNP困難)
  //よって max_value = sum(min(0, (i番目の宝石のコスト))) とし、
  // max_valueからの損失をcostとしてパスを作る。
  // この時の各パスのコストは以下の通り
  //   壊さない | 壊す
  //i>0  0  | i
  //i<0  i  | 0
  int N;
  std::cin >> N;
  

  long long max_value = 0; //うまく壊せるときにもらえる最大の価値

  Dinic<long long> D(N+2);
  //sとtを含めて+2した。 sが0でtがN+1とする
  const int s = 0;
  const int t = N + 1;
  const long long INF = 1 << 30;
  if(INF < 0 && INF < 1000000000) std::cout << "INF < 0 :INF = " << INF << std::endl;

  for(int i = 1; i <= N; i++) {
    long long inp;
    std::cin >> inp;
    if(inp > 0) {
      D.add_edge(i, t, inp); //壊すと損失
      max_value += inp;
    } else {
      D.add_edge(s, i, -inp); //壊さないと損失
    }
    //iを壊すと倍数を叩き割らなければならない
    for(int j = 2 * i; j <= N; j += i) {
      D.add_edge(i, j, INF);
    }
  }

  long long flow = D.max_flow(s, t);
  /*
  for(auto x: D.G) {
    for(auto y: x) {
      std::cout << "to:" << y.to << "\tcost:" << y.cost << "\trev:" << y.rev << std::endl;
    }
  }
  */
  std::cout << max_value - flow << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<int>
#define vvint vector<vint>
#define P pair<int,int>
#define INT_MAX 2147483647
#define MOD 1000000007
using namespace std;
typedef long long ll;



int main(void) {
	int a, b, c, d; cin >> a >> b >> c >> d;
	while (true) {
		c -= b;
		if (c <= 0) {
			cout << "Yes" << endl;
			return 0;
		}
		a -= d;
		if (a <= 0) {
			cout << "No" << endl;
			return 0;
		}

	}
	return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,a=0;
	string s1,s2;
	cin>>s1>>s2;
	n=s1.length();
	for(int i=0;i<n;i++){
		if(s1[i]!=s2[i]){
			a++;
		}
	}
	cout<<a;
	return 0;
}

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

bool solve(int i,int n,int a[],int m){
    if(m==0) return true;
    else if(i>=n) return false;
    else return solve(i+1,n,a,m)||solve(i+1,n,a,m-a[i]);
}

int main(){
    int n,a[20],q,m;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>m;
        if(solve(0,n,a,m)) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
}


Measured memory_bytes: 3096
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
/*bipartite_matching(二部グラフの最大マッチングを求める)*/

const int MAX_V = 1500;
int V;//頂点数
vector<int> G[MAX_V];//グラフの隣接リスト表現
int match[MAX_V];//マッチングのペア
bool used[MAX_V];//DFSですでに調べたかのフラグ
//uとvを結ぶ辺をグラフに追加する
void add_edge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
//増加パスをDFSで探す
bool dfs(int v){
	used[v] = true;
	for(int i = 0;i < G[v].size();i++){
		int u = G[v][i];
		int w = match[u];
		if(w < 0 || !used[w] && dfs(w)){
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}
//二部グラフの最大マッチングを求める
int bipartite_matching(){
	int res = 0;
	memset(match,-1,sizeof(match));
	for(int v = 0;v < V;v++){
		if(match[v]<0){
			memset(used,0,sizeof(used));
			if(dfs(v)){
				res++;
			}
		}
	}
	return res;
}
int main(){
	int n,m;
	while(cin>>m>>n,n||m){
		int blue[m];//青のカード
		int red[n];//赤のカード
		memset(blue,0,sizeof(blue));
		memset(red,0,sizeof(red));
		V = n+m;//頂点数は合計
		rep(i,V){
			G[i].clear();
		}
		for(int i = 0;i < m;i++){
			cin>>blue[i];
		}
		for(int i = 0;i < n;i++){
			cin>>red[i];
		}
		for(int i = 0;i < m;i++){
			for(int j =0;j < n;j++){
				if(__gcd(blue[i],red[j])==1){
					continue;
				}
				add_edge(i,j+m);//0~m-1を青,m~m+n-1を赤とする
			}
		}
		cout <<bipartite_matching()<<endl;
	}
	return 0;
}

Measured memory_bytes: 3380
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

int main() {
    int A, B, C, D, E, F, x, y;
    vector <int> X, Y;
    cin >> A >> B >> C >> D >> E >> F;

    FOR(i, 0, 30){
        FOR(j, 0, 30){
            x = 100*A*i + 100*B*j;
            if (x <= F){
                X.push_back(x);
            }
        }
    }

    FOR(i, 0, F){
        FOR(j, 0, F){
            y = C*i + D*j;
            if (y <= F){
                Y.push_back(y);
            }
        }
    }

    int X_max = 0;
    int Y_max = 0;
    double conc;
    double conc_max = -1.0;

    for (int i = 0; i < SIZE(X); i++){
        for (int j = 0; j < SIZE(Y); j++){
            if ((X[i] + Y[j]) != 0 and X[i] + Y[j] <= F){
                conc = 100.0*Y[j]/(X[i] + Y[j]);
                if (conc <= 100.0*E/(100.0+E) and conc_max < conc){
                    conc_max = conc;
                    X_max = X[i];
                    Y_max = Y[j];
                }
            }
        }
    }

    cout << X_max+Y_max << " " << Y_max << endl;
}

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

int main()
{
	int n;
	cin >> n;
	vector<int> edges[n];
	int u,k,v;
	for (int i = 0; i < n; ++i)
	{
		cin >> u >> k;

		for (int j = 0; j < k; ++j)
		{
			cin >> v;
			edges[i].push_back(v-1);
		}
	}

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (j != 0)
			{
				cout << " ";
			}

			bool flag = false;

			for (int k = 0; k < edges[i].size(); ++k)
			{
				if (edges[i][k] == j)
				{
					flag = true;
				}
			}
			if (flag)
			{
				cout << "1";
			}
			else
			{
				cout << "0";
			}
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3168
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int l = scan.nextInt();
    String[] s = new String[n];

    for(int i = 0; i < n; i++){s[i] = scan.next();}

    Arrays.sort(s);
    for(int i = 0; i < n; i++){
      System.out.print(s[i]);
    }
    System.out.println();
  }
}


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

typedef long long ll;

int main(){
	cin.tie(0);	
	cout.tie(0);	
	ios_base::sync_with_stdio(0);
	ll ta,tb,af,ab,bf,bb;
	cin >> ta >> tb >> af >> ab >> bf >> bb;
	af *= ta;
	bf *= ta;
	ab *= tb;
	bb *= tb;
	if(af + ab == bf + bb){
		cout << "infinity" << '\n';
	}
	else{
		if(af + ab > bf + bb){
			swap(af,bf);
			swap(ab,bb);
		}
		if(af < bf){
			cout << 0 << '\n';
		}
		else{
			ll k = (af-bf)/(bf + bb - af - ab);
			ll cor = k * (bf + bb - af - ab) == af - bf;
			cout << 2*(k + 1) - 1 - cor << '\n'; 
		}
	}
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

import static java.lang.Character.isUpperCase;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        String str = in.next();



        int a = str.length()- 1;



        char ch = str.charAt(a);


        if(ch=='2'|| ch=='4'|| ch=='5' || ch=='7' || ch=='9')
        {
            System.out.println("hon");
        }

        else if(ch=='0' || ch=='1' || ch=='6' || ch=='8')
        {
            System.out.println("pon");
        }

        else if(ch=='3')
        {
            System.out.println("bon");
        }



    }







    }






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

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	final long MOD=(long)1e9+7;
	
	long pow(long a,long n) {
		return n==0?1:(pow(a*a%MOD,n/2)*(n%2==1?a:1))%MOD;
	}
	
	long inv(long a) {
		return pow(a,MOD-2);
	}
	
	long mul(long...a) {
		long r=1;
		for (long v:a) r=r*v%MOD;
		return r;
	}
	
	long add(long...a) {
		long r=0;
		for (long v:a) r=(r+v)%MOD;
		return r;
	}
	
	void run() {
		FastScanner sc=new FastScanner();
		int N=sc.nextInt();
		int K=sc.nextInt();
		// 0,1,..,N
		long ans=0;
		for (long num=K;num<=N+1;++num) {
			long min=mul(num,num-1,inv(2));
			long max=mul(num,N+(N-(num-1)),inv(2));
			long add=(max-min+1)%MOD;
			add=(add+MOD)%MOD;
			ans=add(ans,add);
		}
		System.out.println(ans);
	}
	
	void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}




class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 48924
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const long double PI=3.14159265358979323846264338327950;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  vector<pint> ji;
  int n;
  cin>>n;
  rep(i,n){
    int h,m;
    cin>>h>>m;
    ji.emplace_back(h,m);
  }
  int  m;
  cin>>m;
  rep(i,m){
    int k,g;
    cin>>k>>g;
    ji.emplace_back(k,g);
  }
  sort(all(ji));
  ji.erase(unique(all(ji)),ji.end());
  rep(i,(int)ji.size()){
    if(ji[i].second<10){
      if(i==(int)ji.size()-1){
        cout<<ji[i].first<<':'<<0<<ji[i].second<<'\n';
      }
      else{
        cout<<ji[i].first<<':'<<0<<ji[i].second<<' ';
      }
      
    }
    else{
      if(i==(int)ji.size()-1){
        cout<<ji[i].first<<':'<<ji[i].second<<'\n';
      }
      else{
        cout<<ji[i].first<<':'<<ji[i].second<<' ';
      }
      
    }
  }
  return(0);
}


Measured memory_bytes: 3260
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;

int main() {
	string S;
	cin >> S;
	int i = 0;
	bool ans = false;
	for (; i < S.length(); i++) {
		if (S[i] == 'C')break;
	}
	for (; i < S.length(); i++) {
		if (S[i] == 'F')ans = true;
	}
	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)
#define EPS 10e-8
#define MAX_N 100000

using namespace std;
typedef pair<int, int> ipair;
llong modulo(llong left, llong right) { return (left % right + right) % right; }

int N, A[MAX_N + 1], B[MAX_N + 1];
int main(int argc, char **argv) {
    cin >> N;
    for(int i = 0; i < N + 1; ++i)
        cin >> A[i];
    for(int i = 0; i < N; ++i)
        cin >> B[i];
    B[N] = 0;

    llong res = 0;
    int left = 0;
    for(int i = 0; i < N + 1; ++i) {
        int kill1 = min(A[i], left);
        res += kill1;

        int A_rest = A[i] - kill1;

        int kill2 = min(A_rest, B[i]);
        left = B[i] - kill2;
        res += kill2;
    }

    cout << res << endl;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;

signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  vector<int> rui(n+1,0);
  for(int i=0;i<n;i++){
    cin>>a[i];
    rui[i+1]=a[i]+rui[i];
  }
  int ans=1e18;
  int l=1;
  int r=3;
  for(int i=2;i<n-1;i++){
    while(l<i-1&&abs(abs(rui[i]-rui[l])-rui[l])>abs(abs(rui[i]-rui[l+1])-rui[l+1]))l++;
    if(r==i)r++;
    while(r<n&&abs(abs(rui[n]-rui[r])-abs(rui[r]-rui[i]))>abs(abs(rui[n]-rui[r+1])-abs(rui[r+1]-rui[i])))r++;
    int x=max(rui[l],max(rui[i]-rui[l],max(rui[r]-rui[i],rui[n]-rui[r])));
    int y=min(rui[l],min(rui[i]-rui[l],min(rui[r]-rui[i],rui[n]-rui[r])));
    ans=min(ans,x-y);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast;


int main() {
    int a, b;
    cin >> a >> b;
    cout << a * b << " " << a + a + b + b << endl;
}


Measured memory_bytes: 3128
// This code wrote by chtholly_micromaker(MicroMaker)
#pragma GCC optimize("Ofast,O3,inline")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define reg register
#define int long long
#define ALL(x) (x).begin(),(x).end()
#define mem(x,y) memset(x,y,sizeof x)
#define sz(x) (int)(x).size()
#define ln puts("")
#define lsp putchar(32)
#define pb push_back
#define MP make_pair
#define dbg(x) cerr<<">"<<__func__<<"\tLine: "<<__LINE__<<' '<<#x<<": "<<x<<endl
using namespace std;
const int MaxN=5050;
const int lim=5000*5000;
template <class t> inline void read(t &s){s=0;
reg int f=1;reg char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;}
template<class t,class ...A> inline void read(t &x,A &...a){read(x);read(a...);}
template <class t> inline void write(t x){if(x<0)putchar('-'),x=-x;
int buf[21],top=0;while(x)buf[++top]=x%10,x/=10;if(!top)buf[++top]=0;
while(top)putchar(buf[top--]^'0');return;}
inline void setIn(string s){freopen(s.c_str(),"r",stdin);return;}
inline void setOut(string s){freopen(s.c_str(),"w",stdout);return;}
inline void setIO(string s=""){setIn(s+".in");setOut(s+".out");return;}
template <class t>inline bool checkmin(t&x,t y){if(x>y){x=y;return 1;}return 0;}
template <class t>inline bool checkmax(t&x,t y){if(x<y){x=y;return 1;}return 0;}
inline int lowbit(int x){return x&(-x);}
int f[MaxN*MaxN];
signed main(void)
{
	int n;read(n);
	reg int ga,gb,sa,sb,ba,bb;
	read(ga,sa,ba,gb,sb,bb);
	for(int i=ga;i<=n;++i)
		checkmax(f[i],f[i-ga]+gb-ga);
	for(int i=sa;i<=n;++i)
		checkmax(f[i],f[i-sa]+sb-sa);
	for(int i=ba;i<=n;++i)
		checkmax(f[i],f[i-ba]+bb-ba);
	reg int t=0;
	for(int i=0;i<=n;++i)
		checkmax(t,f[i]);
	reg int ans=n+t;
	n=ans;
	mem(f,0);
	for(int i=gb;i<=n;++i)
		checkmax(f[i],f[i-gb]+ga-gb);
	for(int i=sb;i<=n;++i)
		checkmax(f[i],f[i-sb]+sa-sb);
	for(int i=bb;i<=n;++i)
		checkmax(f[i],f[i-bb]+ba-bb);
	t=0;
	for(int i=0;i<=n;++i)
		checkmax(t,f[i]);
	write(ans+t),ln;
	return 0;
}

/*
 * Check List:
 * 1. Input / Output File (USACO and OI and UVa)
 * 2. long long 
 * 3. Special Test such as n=1
 * 4. Array Size
 * 5. Memory Limit (OI) int is 4 and longlong is 8
 * 6. Mod (a*b%p*c%p not a*b*c%p  ,  (a-b+p)%p not a-b )
 * 7. Name ( int k; for(int k...))
 * 8. more tests , (T=2 .. more)
 * 9. blank \n after a case
*/






Measured memory_bytes: 202880
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
  int i;
  ll k,t=7;
  cin >> k;
  for(i=1;i<=k;i++){
    t%=k;
    if(t==0){
      cout << i << endl;
      return 0;
    }
    t=t*10+7;
  }
  cout << "-1" << endl;
  return 0;
}

Measured memory_bytes: 3648