akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
using ll=long long;
static const ll mod = 1e9 + 7;
static const ll INF = 1LL << 50;
using namespace std;

int main() {
	int n, k;
	int maxv = 0;//何も操作しなければ0であるため
	cin >> n >> k;
	vector<int>v(n);
	repp(i, 0, n)cin >> v[i];
	repp(l, 0, k + 1) {//lは左から取り出す物
		repp(r, 0, k - l + 1) {//rは右から取り出す物
			if (l + r > n)continue;//nとkの大小は定義されていないため
			int d = k - l - r;//dは捨てる物
			int now = 0;//現在の価値
			vector<int>s;//取り出した物を入れる空配列、毎回再定義しているので初期化の必要なし
			for (int i = 0; i < l; ++i) {//順番に追加
				now += v[i];
				s.push_back(v[i]);
			}
			for (int i = n- 1; i >= n-r; --i) {
				now += v[i];
				s.push_back(v[i]);
			}
			sort(s.begin(), s.end());//取り出した物のうち、負のものをできるだけ捨てたいからまずソート
			for (int i = 0; i < d; ++i) {
				if (i >= s.size())break;//捨てる物は取り出した物より大きくなってはいけない
				if (s[i] >= 0)break;//正のものは捨てると合計が小さくなってしまう
				now -= s[i];
			}
			maxv = max(maxv, now);
		}
	}
	cout << maxv << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0, i_len = n; (i) < (i_len); ++(i))
#define repp(i,n) for(int (i) = 1, i_len = n; (i) <= (i_len); ++(i))
#define per(i,n) for(int (i) = n-1; (i) >= 0; --(i))
#define perr(i,n) for(int (i) = n; (i) > 0; --(i))
#define sz(x) ((int)(x).size())
#define popcnt __builtin_popcount
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define Pi 3.1415926535
#define MOD = 1e9+7;
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T,class S> inline bool chmax(T& a, S b){if(a<b){a = b; return true;} return false;}
template<class T,class S> inline bool chmin(T& a, S b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}

ll nc2(ll n){
    return n*(n-1ll)/2ll;
}

int solve(){
    int n; cin >> n;
    vint a(n);
    rep(i,n) cin >> a[i];
    rep(i,n) --a[i];

    vint cnt(n);
    rep(i,n) ++cnt[a[i]];

    ll sum = 0;
    rep(i,n) sum += nc2(cnt[i]);

    rep(i,n){
        cout << sum - nc2(cnt[a[i]]) + nc2(cnt[a[i]]-1) << endl;
    }

    return 0;
}

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


Measured memory_bytes: 4224
package main

import (
	"fmt"
	"strings"
)

func main() {
	s := scanStr()

	isEasy := true

	for i, k := range strings.Split(s, "") {

		switch (i + 1) % 2 {
		case 0:
			if !(k == "L" || k == "U" || k == "D") {
				isEasy = false
			}
		case 1:
			if !(k == "R" || k == "U" || k == "D") {
				isEasy = false
			}
		}
	}

	if isEasy {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}

}
func scanStr() string {
	var s string
	fmt.Scan(&s)
	return s
}

func scanInt() int {
	var i int
	fmt.Scan(&i)
	return i
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 510000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

int main() {
  ll A, V, B, W, T;
  cin >> A >> V >> B >> W >> T;
  if (abs(A-B)<=(V-W)*T) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <cstdio>

using namespace std;

int main()
{
	int c1,c2,c3;
	
	while(scanf("%d %d %d", &c1, &c2, &c3) != EOF){
		int num[] = {1,2,3,4,5,6,7,8,9,10};
		
		num[c1-1] = num[c2-1] = num[c3-1] = 0;
		
		int sum = 20 - (c1 + c2);
		int card = 0, card2 = 0;
		
		for(int i = 0; i < 10; i++){
			if(sum > i && num[i] != 0) card++;
			else if (sum < i && num[i] != 0)card2++;
		//	printf("%d,",num[i]);
		}
		//printf("\n %d %d %d\n", card, card2, sum);
		
		if(card2 < card) printf("YES\n");
		else printf("NO\n");
	}
	
	return(0);
}

Measured memory_bytes: 1008
// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

char s[1005];

void solve() {                   
	scanf("%s", s);
	bool south = 0, north = 0, west = 0, east = 0;

	for (int i = 0; s[i]; ++i) {
		if (s[i] == 'S') {
			south = 1;
		}

		if (s[i] == 'N') {
			north = 1;
		}

		if (s[i] == 'W') {
			west = 1;
		}

		if (s[i] == 'E') {
			east = 1;
		}
	}

	if ((south ^ north) || (west ^ east)) {
		printf("No\n");
	}
	else {
		printf("Yes\n");
	}
}

int main() {    
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

bool IsPrime[100100];
void sieve(int max){
    /*if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    }*/
    for(int i=0;i<max;i++){
      IsPrime[i]=true;
    }
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) // iが素数ならば
            for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                IsPrime[i*j] = false;      // 素数ではない
}

bool nearPrime[100010];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int Q;
  int l,r;
  cin >> Q;
  sieve(100010);
  for(int i=3;i<100010;i+=2){
    if(IsPrime[i]==true && IsPrime[(i+1)/2]){
      nearPrime[i]=true;
      //cout << i << endl;
    }
  }
  int a[100010]={0};
  for(int i=1;i<100010;i++){
    if(nearPrime[i]){
      a[i]=a[i-1]+1;
    }else{
      a[i]=a[i-1];
    }
  }
  for(int i=0;i<Q;i++){
    int ans=0;
    cin >> l >> r;
    ans=a[r]-a[l-1];
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
        using namespace std;
        #define int long long
const int MAX = 510000;
const int MOD = 1000000007;
//

        signed main() {
           int h,w,k;
           cin>>h>>w;
           string s[h];
           for(int i=0;i<h;i++)cin>>s[i];
            int dp[h][w];
           
            queue<pair<int,int>> que;pair<int,int> t;
            for(int i=0;i<h;i++)for(int j=0;j<w;j++){
                if(s[i][j]=='.'){
                    t=make_pair(i,j);
                    break;
                }
            }    int maxa=0;
            for(int i0=0;i0<h;i0++)for(int j0=0;j0<w;j0++){
                if(s[i0][j0]!='.')continue;
                t=make_pair(i0,j0);
             for(int i=0;i<h;i++)for(int j=0;j<w;j++)dp[i][j]=-1;
            dp[t.first][t.second]=0;
            que.push(t);
            while(!que.empty()){
                    t=que.front();
                    k=dp[t.first][t.second];
                    que.pop();
                    if(t.first>0&&dp[t.first-1][t.second]==-1&&s[t.first-1][t.second]=='.'){
                        dp[t.first-1][t.second]=k+1;
                        que.push(make_pair(t.first-1,t.second));
                    }
                     if(t.first<h-1&&dp[t.first+1][t.second]==-1&&s[t.first+1][t.second]=='.'){
                        dp[t.first+1][t.second]=k+1;
                        que.push(make_pair(t.first+1,t.second));
                    }
                     if(t.second>0&&dp[t.first][t.second-1]==-1&&s[t.first][t.second-1]=='.'){
                        dp[t.first][t.second-1]=k+1;
                        que.push(make_pair(t.first,t.second-1));
                    }
                     if(t.second<w-1&&dp[t.first][t.second+1]==-1&&s[t.first][t.second+1]=='.'){
                        dp[t.first][t.second+1]=k+1;
                        que.push(make_pair(t.first,t.second+1));
                    }

            }
              
        
            for(int i=0;i<h;i++)for(int j=0;j<w;j++){
                if(maxa<dp[i][j]){
                    maxa=dp[i][j];
                  
                }
            }
            }
            cout<<maxa;
            
         return 0;

        }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int c[200019];

int main() {
  int last,x,n;
  ll ans;
  cin >> n;
  ans=1;
  last=-1;
  
  for(int i=0; i<n; i++){
    cin >> x;
    if(x==last){continue;}
    last=x;
    ans = (ans+c[x])%1000000007;
    c[x]=ans;
  }

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

Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
    int q;
    double x;
    while (1) {
        scanf("%d",&q);
        if (q==-1) break;
        x = q/2.0;
        while (x*x*x-q<=-0.00001*q||0.00001*q<=x*x*x-q) {
            x = x - (x*x*x-q)/(3*x*x);
        }
        printf("%lf\n",x);
    }
    return 0;
}

Measured memory_bytes: 632
#不可能な場合の場合分け
n= int(input())
t = [0]+list(map(int, input().split( )))
tmx = max(t)
a = [tmx]+list(map(int, input().split( )))+[0]

if a[0]!= a[1]:
    print(0)
    exit()
ans = 1

for i in range(1,n+1):
    if t[i]>t[i-1]:
        if t[i]>a[i]:
            print(0)
            exit()
        continue
    if a[i]>a[i+1]:
        if a[i]>t[i]:
            print(0)
            exit()
        continue
    if t[i]>t[i-1] and a[i]>a[i+1]:
        if t[i]!=a[i]:
            print(0)
            exit()
        continue

    else:
        ans *= min(t[i],a[i])
        ans %=10**9+7
print(ans)

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef pair<ll, ll> pair_t;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = 1<<29;
/****** define constant end ********/

const int MAX = 10000000;
/****** define variable start ******/
ll n;
vl x;
/******* define variable end *******/
ll solve(){
    cin >> n;
    x.resize(n);
    REP(i, n){
        cin >> x[i];
    }
    ll ans = INF;
    for(ll i = 1; i <= 100; i++){
        ll anstmp = 0;
        REP(j, n){
            anstmp += pow(x[j] - i, 2);
        }
        if(anstmp < ans){
            ans = anstmp;
        }
    }
    cout << ans << endl;
    return 0;
}
int main(){
    //clock_t start = clock();
    cout << std::fixed << std::setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll end_solve = solve();
    /*
    clock_t end = clock();
    const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
    printf("time %lf[ms]\n", time);
    */
    
    return (int)end_solve;
}


Measured memory_bytes: 256
N = float(input())


def cnt_digits(n):
    digits = 0

    while n > 0:
        n = n//10
        digits += 1
    return digits


ans = cnt_digits(N)
A = 1
aa = 1000

while N ** 0.5 >= A:
    A = A+1
    if N % A == 0:
        B = N / A
        if aa > max(cnt_digits(A), cnt_digits(B)):
            aa = max(cnt_digits(A), cnt_digits(B))


if aa < ans:
    print(aa)
else:
    print(ans)


Measured memory_bytes: 3060
n = int(input())
dic = []
for i in range(n):
  name, point = input().split()
  dic.append((name, int(point), i+1))

srt = sorted(dic, reverse=True, key=lambda x: x[1])
srt = sorted(srt, key=lambda x: x[0])

for x in srt:
  print(x[2])
             

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

int main() {
  string S;
  string T;
  int flag = 0;
  cin >> S >> T;
  if (S.size() + 1 == T.size()) {
    for (int i = 0; i < S.size(); i++) {
      if (S.at(i) == T.at(i)) {
        continue;
      } else {
        cout << "No" << endl;
        flag = -1;
        break;
      }
    }
    if (flag == 0) {
      cout << "Yes" << endl;
    }
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3628
#include<stdio.h>

int main(){

	int a,b,c;

	scanf("%d %d %d",&a,&b,&c);
	
	if(a<b){
		if(a<c&&c<b){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	
	if(b<a){
		if(b<c&&c<a){
			printf("Yes\n");
		}else{
			printf("No\n");	
		}
	}

}

Measured memory_bytes: 128
#include <stdio.h>

int             main(void)
{
        char    s[1001];
        int             len = 0;

        scanf("%s", s);
        while (s[len])
        {
                len++;
        }
        if (s[len - 1] == 's')
        {
                printf("%s", s);
                printf("es\n");
        }
        else
        {
                printf("%s", s);
                printf("s\n");
        }
        return (0);
}

Measured memory_bytes: 1736
#include "bits/stdc++.h"

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl

typedef pair<int, int> P;
typedef long long ll;

vector<int> v(999);
int a, b, ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    REP(i,999) v[i] = (i+2)*(i+1)/2;
    cin>>a>>b;
    ans = v[b-a-1] - b;
    print(ans);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
 int n,x;
 int i=1;
 scanf("%d", &n);
 while(1){
  x=i;
  if(x%3 == 0){
   printf(" %d", i);
  }else if(x%10 ==3){
   printf(" %d", i);
  }else{
   x /=10;
   while(x){
    if(x%10 ==3){
     printf(" %d", i);
     break;
    }
    x /=10;
   }
  }
  if(++i > n){break;}
 }
printf("\n");
 return 0;
}
 
  

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
int main()
{   /// Standing in the hall of fame
    ios_base::sync_with_stdio() , cin.tie(NULL) , cout.tie(NULL);
    string s;
    int x;
    cin >> s;
    if(s == "SAT")     x = 1;
    else if(s == "FRI")x = 2;
    else if(s == "THU")x = 3;
    else if(s == "WED")x = 4;
    else if(s == "TUE")x = 5;
    else if(s == "MON")x = 6;
    else if(s == "SUN")x = 7;
    cout << x << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define rng(a) a.begin(), a.end()
#define ina(n,a) cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]
#define sz(x) (int)(x).size()
#define se second
#define fi first
#define prev            coyhhhhhhyoc    
#define next          sdNNNmNNNNNNNmds  
#define y0           hNNNNy_yNNNNNN_sNh
#define y1          mNNNNNdtdNNNNNNtsNNm
#define yn          mNNNNNNNNy___smNNNms
#define tm            oooooosyysooooot 
#define read               tyhyt        
#define rank              ytmNmo         
#define index              yyy
#define pb push_back
#define pcnt __builtin_popcountll
#define rrep(i,a,b) for(int i = (b); i >= (a); i--)
#define rall(x,a) for(auto x : a)
#define MOD 1000000007
#define endl "\n"
#define int long long
typedef long long ll;
using namespace std;

int solve(string& s, string& mask, int i, bool gr) {
    if(i == sz(mask)) {
        return 1;
    }
    if(mask[i] == '0') {
        return solve(s, mask, i + 1, gr || (s[i] > '0'));
    } else {
        if(gr) {
            return 9 * solve(s, mask, i + 1, gr);
        } else if(s[i] == '0') {
            return 0;
        } else {
            return solve(s, mask, i + 1, false) + (s[i] - '0' - 1) * solve(s, mask, i + 1, true);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s;
    int k;
    cin >> s >> k;
    int n = sz(s);
    int ans = 0;
    if(k == 1) {
        rep(i, 1, n) {
            string mask(n, '0');
            mask[i - 1] = '1';
            ans += solve(s, mask, 0, false);
        }
    } else if(k == 2) {
        rep(i, 1, n) {
            rep(j, i + 1, n) {
                string mask(n, '0');
                mask[i - 1] = '1';
                mask[j - 1] = '1';
                ans += solve(s, mask, 0, false);
            }
        }
    } else if(k == 3) {
        rep(i, 1, n) {
            rep(j, i + 1, n) {
                rep(k, j + 1, n) {
                    string mask(n, '0');
                    mask[i - 1] = '1';
                    mask[j - 1] = '1';
                    mask[k - 1] = '1';
                    ans += solve(s, mask, 0, false);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;

namespace _050_AppleandPeach
{
	class Program
	{
		static void Main ( string[] args )
		{
			char[] result = Console.ReadLine ().ToCharArray ();
			string Apple = "apple";
			string Peach = "peach";

			int index = 0;
			while (index <= result.Length - Apple.Length)
			{
				//apple
				Parse (result, index, Apple, Peach, out index);
				//peach
				Parse (result, index, Peach, Apple, out index);

				index++;
			}

			Console.WriteLine (result);
		}

		static void Parse ( char[] charArray, int index, string searchStr, string parseStr, out int resultIndex )
		{
			if (index + searchStr.Length <= charArray.Length) 
			{
				bool isParse = true;

				for (int index2 = 0; index2 < searchStr.Length; index++, index2++)
				{
					if (charArray[index] != searchStr[index2])
					{
						isParse = false;
						break;
					}
				}

				if (isParse)
				{
					int shift = index - parseStr.Length;
					for (int lp = 0; lp < parseStr.Length; lp++)
					{
						charArray[lp + shift] = parseStr[lp];
					}
				}
			}

			resultIndex = index;
		}
	}
}

Measured memory_bytes: 8800
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
ll Q,H,S,D,N,one,two;
int main(){
    cin>>Q>>H>>S>>D>>N;
    one=min(min(Q*4,H*2),S);
    two=min(one*2,D);
    cout<<N/2*two+N%2*one<<endl;
}


Measured memory_bytes: 256
"""
union-find木
"""


class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            x, y = y, x
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        self.size[x] += self.size[y]

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

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

def abc120_d():
    n, m = map(int, input().split())
    ab = [map(lambda x: int(x) - 1, input().split()) for _ in range(m)]

    ans = n * (n - 1) // 2
    uf = UnionFind(n)
    res = []
    for a, b in reversed(ab):
        res.append(ans)
        if not uf.same(a, b):
            ans -= uf.get_size(a) * uf.get_size(b)
        uf.unite(a, b)
    print("\n".join(map(str, reversed(res))))


if __name__ == '__main__':
    abc120_d()


Measured memory_bytes: 132356
def gcd2(i,j):
    if i<j:
        i,j=j,i
    while j>0:
        i=i%j
        i,j=j,i
    return i

k=int(input())
ans=0
for i in range(1,k+1):
    if i==1:
        ans+=k**2
        continue
    for j in range(1,k+1):
        tmp=gcd2(i,j)
        if tmp==1:
            ans+=k
            continue
        for p in range(1,k+1):
            ans+=gcd2(tmp,p)
print(ans)

Measured memory_bytes: 9212
M=[]
for _i in range(3):
  M.append(list(map(int,input().split())))
n= int(input())

cont_lin = [0,0,0]
cont_col = [0,0,0]
contdp = contds = 0
for a in range(n):
  b= int(input())
  for i in range(3):
    for j in range(3):
      if M[i][j]==b:
          cont_lin[i]+=1
          cont_col[j]+=1
          if i==j:
              contdp+=1
          if i==2-j:
              contds+=1
achou = False
if (contdp == 3) or (contds==3):
    achou=True
elif (cont_lin[0]==3) or (cont_lin[1]==3) or (cont_lin[2]==3) :
    achou=True  
elif (cont_col[0]==3) or (cont_col[1]==3) or (cont_col[2]==3) :
    achou=True

print('Yes' if achou else 'No')
                                              
              


Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
#define mask_type __int128
#define mod 1000003
int head[1000003], nxt[5000010];
int to1[5000010];
mask_type to2[5000010];
int val[5000010], tot;
#ifdef __cplusplus
extern "C" {
#endif
__attribute__((always_inline, optimize(3)))
__inline__ void set(int len, mask_type mask, int v) {
  int p = (mask + (mask_type(len) << 120)) % mod, i;
  for (i = head[p]; i; i = nxt[i])
    if (to1[i] == len && to2[i] == mask) {
      val[i] = v;
      return;
    }
  to1[tot] = len, to2[tot] = mask, val[tot] = v;
  nxt[tot] = head[p], head[p] = tot ++;
}
__attribute__((always_inline, optimize(3)))
__inline__ int get(int len, mask_type mask) {
  int p = (mask + (mask_type(len) << 120)) % mod, i;
  for (i = head[p]; i; i = nxt[i])
    if (to1[i] == len && to2[i] == mask) return val[i];
  return -1;
}
#ifdef __cplusplus
}
#endif
#undef mod
#define mod 998244353
#ifdef __cplusplus
extern "C" {
#endif
__attribute__((always_inline, optimize(3)))
__inline__ int add(int x, const int &y) {
  return (x += y) >= mod ? x - mod : x;
}
__attribute__((always_inline, optimize(3)))
__inline__ int mul(const int &x, const int &y) {
  return 1LL * x * y - 1LL * x * y / mod * mod;
}
#ifdef __cplusplus
}
#endif
int dfs(int len, mask_type mask) {
  if (!len) return 1;
  if (~get(len, mask)) return get(len, mask);
  int res = dfs(len - 1, mask >> 1);
  (mask & 1) && (res = add(res, res));
  for (int i = 1; i <= len; ++ i) {
    mask_type nmask = (mask_type(1) << i) - 1 & mask;
    for (int j = i << 1; j <= len; j += i) {
      nmask &= (mask >> j - i);
      res = add(res, mul(dfs(i, nmask), dfs(len - j, mask >> j)));
    }
  }
  set(len, mask, res);
  return res;
}

int main() {
  static char str[105] = { }; scanf("%s", str);
  mask_type mask = 0; int len = strlen(str);
  for (int i = len; ~-- i; ) (mask <<= 1) |= str[i] - '0';
  return printf("%d\n", dfs(len, mask)) & 0;
}

Measured memory_bytes: 11904
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int x = Integer.parseInt(st.nextToken());
      
      Book[] books = new Book[n];
      for(int k = 0; k < n; k++){
         st = new StringTokenizer(f.readLine());
         
         int cost = Integer.parseInt(st.nextToken());
         int[] algs = new int[m];
         for(int j = 0; j < m; j++){
            algs[j] = Integer.parseInt(st.nextToken());
         }
         
         books[k] = new Book(cost,algs);
      }
      
      int mincost = Integer.MAX_VALUE;
      for(int k = 0; k < 1<<n; k++){
         int index = 0;
         int i = k;
         
         int cost = 0;
         int[] values = new int[m];
         while(i > 0){
            if(i%2 == 1){
               cost += books[index].cost;
               for(int j = 0; j < m; j++){
                  values[j] += books[index].algs[j];
               }
            }
            i >>= 1;
            index++;
         }
         
         if(check(values,x)){
            mincost = Math.min(cost,mincost);
         }
      }
         
      if(mincost == Integer.MAX_VALUE){
         out.println("-1");
      } else {
         out.println(mincost);
      }
      
      
      
      
      
      out.close();
   }
   
   public static boolean check(int[] array, int x){
      for(int k = 0; k < array.length; k++){
         if(array[k] < x) 
            return false;
      }
      return true;
   }
   
   public static class Book{
      int cost;
      int[] algs;
      
      public Book(int a, int[] b){
         cost = a;
         algs = b;
      }
   }
      
}

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

int main(){
  int N;
  cin>>N;
  map<string,int> ma;
  for(int i=0;i<N;++i){
    string S;
    cin>>S;
    ++ma[S];
  }

  int rep=0;
  for(auto p:ma){
    rep=max(rep,p.second);
  }
  for(auto p:ma){
  if(p.second==rep) cout<<p.first<<endl;
  }
}


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

int main() {
  int N;
  int K;

  cin >> N;
  cin >> K;

  int sum = 0;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;

    if (x < (K - x)) {
      sum += x * 2;
    } else {
      sum += (K - x) * 2;
    }
  }

  cout << sum << endl;
}


Measured memory_bytes: 256
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p, INF = 1 << N, 1 << 60
    # bitDP of minimum cost to buy the subset of items represented by binary
    dp = [INF] * p
    dp[0] = 0
    for _ in range(M):
        a, _ = map(int, input().split())
        x = sum(1 << (i - 1) for i in map(int, input().split()))
        for y in range(p):
            dp[x | y] = min(dp[x | y], dp[y] + a)
    ans = dp[-1] if dp[-1] != INF else -1
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <map>
#include <bitset>

using namespace std;

using ll = long long;

int main() {
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);

    ll straight = min(K, X / D);
    K -= straight;
    X -= straight * D;

    if (K % 2 == 0) {
        cout << X << endl;
    } else {
        cout << D - X << endl;
    }

    return 0;
}








Measured memory_bytes: 3164
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <stack>

using namespace std;

int h, w;
string board[20];

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

void Solve()
{
    map<string, int> memo;
    string res;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            for (int d = 0; d < 8; ++d) {
                string s;
                int nx = j, ny = i;

                do {

                    s += board[ny][nx];
                    ++memo[s];

                    nx = (nx + dx[d] + w) % w;
                    ny = (ny + dy[d] + h) % h;

                    if (memo[s] >= 2) {
                        if (s.size() > res.size() ||
                            (s.size() == res.size() && (s < res)))
                            res = s;
                    }

                } while (nx != j || ny != i);

            }
        }
    }

    if (res.size() <= 1)
        cout << "0\n";
    else
        cout << res << endl;
}

int main()
{
    while (cin >> h >> w, h || w) {

        for (int i = 0; i < h; ++i)
            cin >> board[i];

        Solve();
    }

    return 0;
}

Measured memory_bytes: 36032
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;

#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<int,int>
#define PP pair<P,int>
#define F first
#define S second


ll n, a, b;

int main() {
    cin >> n >> a >> b;
    if (a == 0) {
        cout << 0 << endl;
        return 0;
    }
    ll ans = (n / (a + b))*a + min(a, n % (a + b));
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
const int MN = 1e5+5;
ll dp[MN], ans[MN], tot, N, i, a[MN], b[MN], c[MN], p;
int lol, wtf;

int main(){
	for(scanf("%lld",&N),i=1;i<=N;i++) scanf("%lld",&a[i]);
	for(i=1;i<=N;i++) scanf("%lld",&b[i]);
	for(i=1;i<=N;i++) scanf("%lld",&c[i]);
	sort(a+1,a+N+1);
	sort(b+1,b+N+1);
	sort(c+1,c+N+1);
	for(i=1;i<=N;i++){
		while(lol<=N&&b[lol]<=a[i]) lol++;
		dp[lol]++;
	}
	for(i=1;i<=N;i++){
		tot += dp[i];
		while(wtf<=N&&c[wtf]<=b[i]) wtf++;
		ans[wtf] += tot;
	}
	ll huh = 0;
	for(i=1;i<=N;i++)
		ans[i] += ans[i-1], huh += ans[i];
	printf("%lld\n",huh);
	return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    int h,w;
    cin >> h >> w;
    vector<vector<int>> a(h,vector<int>(w));
    rep(i,h) rep(j,w) {
        cin >> a[i][j];
    }
    int state = 0;
    int pre_x = 0;
    int pre_y = 0;
    if(a[0][0]%2 == 0) state = 0;
    else state = 1;
    vector<vector<int>> ans; 
    rep(i,h) rep(j,w) {
        if(i==0 && j == 0) continue;
        int y = i;
        int x = j;
        if(y%2 == 1) x = w-1-j;
        if(state == 1) {
            ans.push_back({pre_y+1, pre_x+1, y+1,x+1});
            if(a[y][x]%2 == 1) state = 0;
        } else if(a[y][x]%2 == 1) state = 1;
        pre_x = x;
        pre_y = y;
    }
    cout << ans.size() << endl;
    for(auto i :ans) {
        rep(j,4) {
            cout << i[j];
            if(j != 3) cout <<" ";
            else cout << endl;
        }
    }
}


Measured memory_bytes: 10032
#include <iostream>
#include<string>
#include<vector>
 using namespace std;
 int main() {
   int x;
   cin >> x;
   bool flag = 1;
   while(flag){
     int cnt = 0;
     for (int i=2; i<=x; i++){
       if(x%i==0){
         cnt++;
       }
     }
     if(cnt==1){
       flag = 0;
     }
     x++;
   }
   cout << x-1 << endl;
 }

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
  long nbChaines; 
  cin >> nbChaines; 
  string chaines[nbChaines]; 
  for (long iChaine = 0; iChaine < nbChaines; iChaine ++) {
    cin >> chaines[iChaine]; 
  }
  sort(chaines, chaines + nbChaines); 
  long nbObjets = 0, pointeur = 0;
  string chaine = " "; 
  
  while (pointeur < nbChaines) {
    if (chaines[pointeur] != chaine) {
      nbObjets ++; 
      chaine = chaines[pointeur]; 
    }
    pointeur ++; 
  }
  cout << nbObjets; 
  return 0; 
}

Measured memory_bytes: 9832
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

#define CH(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)
#define F first
#define S second

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

int N;
long long a[300005];
long long sum1[100005], sum2[100005];

int main() {
  cin>>N;
  REP(i,0,3*N) cin>>a[i];

  long long ans = -LLINF;

  priority_queue<long long> PQ1,PQ2;

  REP(i,0,N) PQ1.push(-a[i]), sum1[0]+=a[i];
  RREP(i,2*N,3*N) PQ2.push(a[i]), sum2[N]+=a[i];

  REP(i,N,2*N){
    sum1[i-N+1] = sum1[i-N];
    sum1[i-N+1] += a[i];
    PQ1.push(-a[i]);
    sum1[i-N+1] += PQ1.top();
    //cout<<"PQ1.top() : "<<-PQ1.top()<<endl;
    PQ1.pop();
  }
  RREP(i,N,2*N){
    sum2[i-N] = sum2[i-N+1];
    sum2[i-N] += a[i];
    PQ2.push(a[i]);
    sum2[i-N] -= PQ2.top();
    //cout<<"PQ2.top() : "<<PQ2.top()<<endl;
    PQ2.pop();
  }

  REP(i,0,N+1){
    //cout<<"sum1: "<<sum1[i]<<", sum2: "<<sum2[i]<<endl;
    ans = max(ans,sum1[i]-sum2[i]);
  }

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 5876
n = int(input())
dp = [[0] * 3 for _ in range(n + 1)]
for i in range(1, n + 1):
	a, b, c = map(int, input().split())
	dp[i][0] = max(dp[i][0], dp[i - 1][1] + a, dp[i - 1][2] + a)
	dp[i][1] = max(dp[i][1], dp[i - 1][0] + b, dp[i - 1][2] + b)
	dp[i][2] = max(dp[i][2], dp[i - 1][0] + c, dp[i - 1][1] + c)
print(max(dp[-1]))

Measured memory_bytes: 60524
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdint>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
int W,H; cin >> H >> W;
vector<string> a(H);
rep(i,H){
  cin >> a[i];
}
rep(i,W+2){
  cout << '#';
}
cout << endl;
rep(i,H){
  cout << "#" << a[i] << "#" << endl;
}
rep(i,W+2){
  cout << '#';
}
cout << endl;
}

Measured memory_bytes: 256
#define MYDEBUG
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <queue>
#include <stack>

#ifdef MYDEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define all(x) x.begin(), x.end()
#define umap unordered_map
using namespace std;

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  size_t last = v.size() - 1;
  for (size_t i = 0; i < v.size(); ++i) {
    out << v[i];
    if (i != last)
      out << ",";
 }
  out << "]";
  return out;
}

void solve() {
  ll a, b, c;
  cin >> a >> b >> c;
  ll cnt = 0;
  while (true) {
    if (a % 2 != 0 || b % 2 != 0 || c % 2 != 0) {
      cout << cnt << endl;
      return;
    } else if (a == b && b == c) {
      cout << -1 << endl;
      return;
    } else {
      ll pa = a, pb = b, pc = c;
      a = (pb + pc) / 2;
      b = (pa + pc) / 2;
      c = (pa + pb) / 2;
      cnt++;
    }
  }
}

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


Measured memory_bytes: 384
#include <iostream>

using namespace std;

int main() {
	// input
	int n, m;
	cin >> n >> m;
	int arr[n*m];

	for( int i=0; i<n; i++ ) {
		for( int ii=0; ii<m; ii++ ) {
			cin >> arr[ m * i + ii ];
		}
	}

	int vec[m];
	for( int j=0; j<m; j++ ) {
		cin >> vec[j];
	}

	// calc
	int arr_dst[n];
	int sum_tmp = 0;
	for( int k=0; k<n; k++ ) {
		for( int kk=0; kk<m; kk++ ) {
			sum_tmp += arr[ m * k + kk ] * vec[kk];
		}
		arr_dst[k] = sum_tmp;
		sum_tmp = 0;
	}

	// output
	for( int l=0; l<n; l++ ) {
		cout << arr_dst[l] << endl;
	}
}


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

const ll MAXN = 2000;

ll N, X, Y, ans=0, tmp=0;
vector<ll> A(MAXN, 0);
map<ll, ll> M;

void bfs(ll s) {
    queue<pair<ll, ll>> Q;
    vector<ll> color(N+1, 0);
    Q.push(make_pair(s, 0));
    color[s] = 1;
    while(!Q.empty()) {
        pair<ll, ll> p = Q.front();
        Q.pop();
        A[p.second]++;
        if(p.first==X&&color[Y]==0) {
            Q.push(make_pair(Y, p.second+1));
            color[Y] = 1;
        }
        if(p.first==Y&&color[X]==0) {
            Q.push(make_pair(X, p.second+1));
            color[X] = 1;
        }
        if(p.first!=1){
            if(color[p.first-1]==0) {
                Q.push(make_pair(p.first-1, p.second+1));
                color[p.first-1] = 1;
            }
        }
        if(p.first!=N){
            if(color[p.first+1]==0) {
                Q.push(make_pair(p.first+1, p.second+1));
                color[p.first+1] = 1;
            }
        }
    }
}

void bfsinit() {
    for(int i=1;i<=N;i++) {
        bfs(i);
    }
}

signed main(){
    cin >> N >> X >> Y;
    bfsinit();
    for(int i=1;i<N;i++) {
        cout << A[i]/2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll double
using namespace std;
int n;
char s[20],M;
void Go(int x,char M){ 
	if (x==n) {
		for (int i=0; i<n; i++)
			cout<<s[i];
			cout<<"\n";
		return ;
	}
	for (char c='a'; c<=M+1; c++) {
		s[x]=c;
		Go(x+1,max(c,M));
	}
	return ;	
}

main () {
	cin>>n;
	s[0]='a',M='a';
	Go(1,M);
}

Measured memory_bytes: 1536
#include <iostream>
#include <iomanip>
#include <atcoder/math>

int main(void){
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false);
    int n; std::cin >> n;
    while(n--){
        int n, m, a, b; std::cin >> n >> m >> a >> b;
        std::cout << atcoder::floor_sum(n, m, a, b) << '\n';
    }
    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[200005], b[200005];
int main(){
	int n;
	scanf("%d", &n);
	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
		b[i] = a[i]-i;
	}
	sort(b+1, b+1+n);

	int res = 0;
	LL ans = 0;
	if(n%2 == 0){
		res = b[n/2+1];
		for(int i=1;i<=n;i++){
			ans += abs(b[i]-res);
		}
	}
	else{
		res = b[n/2];
		LL res1 = 0, res2 = 0;
		for(int i=1;i<=n;i++){
			res1 += abs(b[i]-res);
		}
		res = b[n/2+1];
		for(int i=1;i<=n;i++){
			res2 += abs(b[i]-res);
		}
		ans = min(res1, res2);
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A;
  cin >> N >> A;
    int B = N % 500;
  if (A >= 499) {
    cout << "Yes"<< endl;
  }
  else if (A >= B) {
    cout << "Yes" << endl;
  }
  else if (A < B) {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import java.util.*;
public class Main{

  public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      long h = sc.nextLong();
      long w = sc.nextLong();

      long minDiff = calculateArea(h, w, Long.MAX_VALUE);
      minDiff = calculateArea(w, h, minDiff);
      
      System.out.println(minDiff);
  }

  private static long calculateArea(long h, long w, long minDiff) {
      long area1 = 0, area2 = 0, area3 = 0;
      for(long i = 1; i <= (h+1)/2; i++) {
          area1 = i * w;
          
          area2 = (h - i) * (w / 2);
          area3 = (h - i) * (w - w / 2);
          long diff = Math.max(area1, Math.max(area2, area3)) - Math.min(area1, Math.min(area2, area3));
          minDiff = Math.min(minDiff, diff);
          
          area2 = (h - i) / 2 * w;
          area3 = (h - i - (h - i) / 2) * w;
          diff = Math.max(area1, Math.max(area2, area3)) - Math.min(area1, Math.min(area2, area3));
          minDiff = Math.min(minDiff, diff);
      }
      return minDiff;
  }
}


Measured memory_bytes: 21972
#include <iostream>

int main()
{
    unsigned W, H;
    char c;
    std::cin >> W >> H >> c;
    auto edge = [=]() {
        std::cout << '+';
        for(unsigned i = 0; i + 2 != W; ++i)
        {
            std::cout << '-';
        }
        std::cout << "+\n";
    };
    edge();
    for(unsigned i = 0; i + 2 != H; ++i)
    {
        std::cout << '|';
        for(unsigned j = 0; j + 2 != W; ++j)
        {
            std::cout << ((i + 1 == H / 2) && (j + 1 == W / 2) ? c : '.');
        }
        std::cout << "|\n";
    }
    edge();
}



Measured memory_bytes: 3064
from itertools import combinations

inputs = []
n,x = map(int,input().split())
while n != 0 or x != 0:
     inputs.append((n,x))
     n,x = map(int,input().split())

for n,x in inputs:
    print(len([c for c in combinations(range(1,n+1),3) if sum(c) == x]))


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

#define int           long long
#define S             second
#define F             first
#define pb            push_back
#define all(c)        (c).begin(),(c).end()
#define rall(c)       (c).rbegin(),(c).rend() 
#define lb            lower_bound
#define si(c)         (int)((c).size())
#define lcm(a, b)      (a * (b / __gcd(a,b)))  
#define inf           (long long)(1e15)
//#define endl          '\n'
#define mp            make_pair
#define time(s)       (double(clock()-s)/double(CLOCKS_PER_SEC))
#define debug(args...)    _F(#args, args)
#define vi            std::vector<int>
#define pii           pair<int, int> 
#define vpi           vector<pii>

clock_t start;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

template<typename T> void _F(const char *name, T arg1){
    cerr << name << " = " << arg1 << endl;
}template<typename T, typename... Args> void _F(const char *names, T arg1, Args... args){
    const char *name = strchr(names, ',');
    cerr.write(names, name-names) << " = " << arg1 << endl;
    _F(name+2, args...);
}
template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2> &q){
    in >> q.F >> q.S; return in;
}template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> &q){
    out << q.F << " " << q.S; return out;
}template< typename T1, typename T2> pair<T1, T2> operator+(pair<T1, T2> p1, pair<T1, T2> p2){
    return {p1.F+p2.F, p1.S+p2.S};
}template< typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> p1, pair<T1, T2> p2){
    return {p1.F-p2.F, p1.S-p2.S};
}

const int mod = 1e9+7;

int modPow(int x, int p){
    int ans = 1;
    while(p){
        if(p&1)ans = (ans*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return ans;
}

void solve(){
    int n, k;
    cin >> n >> k;
    int ans[k+1];
    int res = 0;
    memset(ans, 0, sizeof(ans));
    for(int i = k; i >= 1; i--){
        for(int j = 2*i; j <= k; j += i)
            ans[i] = (ans[i]-ans[j]+mod)%mod;
        ans[i] = (ans[i]+modPow(k/i, n))%mod;
        res = (res+ans[i]*i)%mod;
    }
    cout << res << endl;
}

signed main(){

    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);   

    int t = 1;
    start = clock(); 

    cout << fixed << setprecision(12);

    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin); 
    // freopen("output.txt", "w", stdout);
    // freopen("error.txt", "w", stderr);
    // #endif

    //cin >> t;

    for(int i = 1; i <= t; ++i){
        //cout << "Case #" << i << ": ";
        solve();
        //cout << endl;
    }
    //cerr << time(start);
    return 0;
}

Measured memory_bytes: 4376
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
using namespace std;

typedef long long ll;

const int maxn = 100000+5;


int main()
{
	string stdstr = "CODEFESTIVAL2016";
	string str;
	while(cin>>str)
	{
		int ans = 0;
		for(int i = 0;i < str.length(); ++i)
		{
			if(str[i] != stdstr[i])ans += 1;
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
// Author : Sarthak Kapoor
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,a,n) for(int i=a;i<n;++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define repba(i,b,a) for(int i=b;i>=a;--i)
#define repab(i,a,b) for(int i=a;i<b;++i)
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define msi map<string,int>
#define mii map<int,int>
#define viip vector<pair<int,pair<int,int> > > 
#define mp make_pair
#define vip vector<pair<int,int> >
#define pb push_back 
#define po pop_back
#define fi first
#define sec second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define s(v) v.size()
ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//use rng()%n for numbers in range [0,n-1]
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin>>n;
	map<string,int> mp;
	string s;
	int max1 = 0;
	rep(i,n){
		cin>>s;
		mp[s]++;
		max1 = max(max1,mp[s]);
	}	
	for(auto x:mp){
		// cout<<x.fi<<" "<<x.sec<<"\n";
		if(x.sec == max1){
			cout<<x.fi<<"\n";
		}
	}
	return 0;
}

Measured memory_bytes: 23808
#include <stdio.h>
#include <limits.h>

int main(void){
    // Your code here!
    int n, p[5001], cnt;
    long long int k, c[5001], tmp = 0,tmptmp, ans = LLONG_MIN, tmpans = 0, i, ii, iii, tmpi;
 
    scanf("%d%d", &n, &k);
    for (i = 1; i <= n; i++)
        scanf("%d", p + i);
    for (i = 1; i <= n; i++)
        scanf("%lld", c + i);

    for (i = 1; i <= n; i++)
    {
        int f[5001] = {};

        cnt = 0;
        tmp = 0;
        tmptmp = 0;
        tmpi = p[i];

        tmptmp = c[tmpi];
        tmpans = c[tmpi];
        while (!f[tmpi])
        {
            f[tmpi] = 1;
            tmp += c[tmpi];
            tmpi = p[tmpi];
            cnt++;
            if (tmpans < tmp)
                tmpans = tmp;
        }
        tmp += c[tmpi];
        if (tmptmp < tmp)
        {
            tmpans = (tmp - tmptmp) * (k / cnt - 1);
            tmp = tmpans;
            for (ii = (k / cnt - 1) * cnt; ii < k; ii++)
            {
                tmp += c[tmpi];
                tmpi = p[tmpi];
                if (tmp > tmpans)
                    tmpans = tmp;
            }
        }
        if (ans < tmpans)
            ans = tmpans;
    }
    printf("%lld", ans);
}

Measured memory_bytes: 1788
N,Y = map(int,input().split())

flag = False
for i in range(N+1):
    if flag:
        break
    for j in range(N+1-i):
        if 10000*i + 5000*j + 1000*(N-i-j) == Y:
            l = [i,j,N-i-j]
            flag = True
            break
if flag:
    print(l[0],l[1],l[2])
else:
    print(-1,-1,-1)

Measured memory_bytes: 3064
#include<iostream>

using namespace std;

int main(){
	int w,a,b;

	cin >> w >> a >> b;

	if(a+w < b){
		cout << b-(a+w) <<endl;
	}else if(b+w < a){
		cout << a-(b+w) <<endl;
	}else{
		cout << 0 <<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

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

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

signed main(void)
{
	long long h, w;
	cin >> h >> w;
	if (h == 1 || w == 1)
		cout << 1 << endl;
	else 
		cout << (long long) (h * w + 1) / 2 << endl;
	return 0;
}


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

vector<int> dice(7);
vector<int> tmp(7);
void change_dice(char c){
    for(int i=1; i<=6; i++){
        tmp[i]=dice[i];
    }
    if(c=='E'){
        dice[1]=tmp[4];
        dice[3]=tmp[1];
        dice[4]=tmp[6];
        dice[6]=tmp[3];
    }
    else if(c=='N'){
        dice[1]=tmp[2];
        dice[2]=tmp[6];
        dice[5]=tmp[1];
        dice[6]=tmp[5];
    }
    else if(c=='S'){
        dice[1]=tmp[5];
        dice[2]=tmp[1];
        dice[5]=tmp[6];
        dice[6]=tmp[2];
    }
    else if(c=='W'){
        dice[1]=tmp[3];
        dice[3]=tmp[6];
        dice[4]=tmp[1];
        dice[6]=tmp[4];
    }
}

int main(){
    for(int i=1; i<=6; i++)
        cin >> dice[i];    
    int n;
    cin >> n;
    while(n--){
        int upper,front;
        cin >> upper >> front;
        
        //初期位置の探索
        int key;
        for(int i=1; i<=6; i++){
            if(dice[i]==front)
                key=i;
        }
        //frontを揃える
        switch(key){
            case 1: 
                change_dice('S');
                break;
            case 2:
                break;
            case 3:
                change_dice('W');
                change_dice('S');
                break;
            case 4:
                change_dice('E');
                change_dice('S');
                break;
            case 5:
                change_dice('S');
                change_dice('S');
                break;
            case 6:
                change_dice('N');
                break;
        }
        //upperを揃える
        while(dice[1]!=upper){
            change_dice('E');
        }
        cout << dice[3] << endl;
   }
   return 0;
}


Measured memory_bytes: 3108