akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        int h = num / 3600;
        num -= h*3600;
        int m = num / 60;
        num -= m*60;
        System.out.println(h+":"+m+":"+num);

    }
}


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

int main() {
  int d; cin >> d;
  if (d == 25) cout << "Christmas" << endl;
  else if (d == 24) cout << "Christmas Eve" << endl;
  else if (d == 23) cout << "Christmas Eve Eve" << endl;
  else cout << "Christmas Eve Eve Eve" << endl;
}


Measured memory_bytes: 256
using System;

namespace ALDS1_6_A
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = int.Parse(Console.ReadLine());
            string[] str = Console.ReadLine().Split(' ');
            int[] input = new int[num];
            int[] output = new int[num+1];
            int max = 0;

            for (int i=0; i<num; i++)
            {
                input[i] = int.Parse(str[i]);
                if (input[i] > max) max = input[i];
            }

            output = counting_sort(input, output, max);
            result(output);
        }

        static int[] counting_sort(int[] A, int[] B, int k)
        {
            int[] C = new int[k+1];

            for (int i=0; i<=k; i++)
            {
                C[i] = 0;
            }

            for (int j=0; j<A.Length; j++)
            {
                C[A[j]]++;
            }

            for (int i=1; i<=k; i++)
            {
                C[i] += C[i-1];
            }

            for (int j=A.Length-1; j>=0; j--)
            {
                B[C[A[j]]] = A[j];
                C[A[j]]--;
            }

            return B;
        }

        static void result(int[] D)
        {
            string[] e = null;

            e = Array.ConvertAll(D, delegate (int value)
            {
                return value.ToString();
            });

            string str = string.Join(" ", e);   
            Console.WriteLine(str.Substring(2));
        }
    }
}

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

ll dp[100005][105];    /// dp[x][i] = max sum of values for total weight x using 0....i weights

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


    int n, W;
    cin>>n>>W;

    vector<int> weights(n), values(n);

    for(int i = 0; i<n; i++){
        cin>>weights[i];
        cin>>values[i];
    }


    for(int w = 1; w<=W; w++){
        for(int i = 0; i<n; i++){
            dp[w][i] = dp[w][i-1];

            if(w >= weights[i])
                dp[w][i] = max(dp[w][i], dp[w-weights[i]][i-1] + values[i]);
        }
    }

    cout<<dp[W][n-1];


    return 0;
}


Measured memory_bytes: 85536
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod =  998244353;
const int INF = 1e18;

struct Combination {
    vector<int64_t> fact, rfact;
    Combination(int sz) : fact(sz + 1), rfact(sz + 1) {
        fact[0] = 1;
        for(int i = 1; i < fact.size(); i++){
            fact[i] = fact[i - 1] * i % mod;
        }
        rfact[sz] = inv(fact[sz]);
        for(int i = sz - 1; i >= 0; i--){
            rfact[i] = rfact[i + 1] * (i + 1) % mod;
        }
    }
    int64_t inv(int x) const {
        return pow(x, mod - 2);
    }
    int64_t pow(int64_t x, int64_t n) const {
        int64_t ret = 1;
        while(n > 0){
            if(n & 1) (ret *= x) %= mod;
            (x *= x) %= mod;
            n >>= 1;
        }
        return (ret);
    }
    int64_t P(int n, int r) const {
        if(r < 0 || n < r) return (0);
        return (fact[n] * rfact[n - r] % mod);
    }

    int64_t C(int p, int q) const {
        if(q < 0 || p < q) return (0);
        return (fact[p] * rfact[q] % mod * rfact[p - q] % mod);
    }

    int64_t H(int n, int r) const {
        if(n < 0 || r < 0) return (0);
        return (r == 0 ? 1 : C(n + r - 1, r));
    }
};

signed main(){
    int n, a, b, k;
    cin >> n >> a >> b >> k;
    int ans = 0;
    Combination cmb(n);
    for(int i = 0; i <= n; i++){
        int tmp = k - a * i;
        if(tmp % b != 0) continue;
        int j = tmp / b;
        if(j < 0) continue;
        ans += cmb.C(n, i) * cmb.C(n, j) % mod;
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4992
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define int long long

using namespace std;


int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };




ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}

long long nCr(int n, int r) {
	if (r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
	long long ans = 1;
	int i;

	for (i = 1; i <= r; i++) {
		ans *= n - r + i;
		ans /= i;
	}

	return ans;
}


const int MOD = 1000000007;


ll v[60];
signed main() {
	int N, A, B; cin >> N >> A >> B;
	REP(i, N) {
		cin >> v[i];
	}
	SORT(v, N); REVERSE(v, N);
	double ave = 0;
	REP(i, A) {
		ave += v[i] / double(A);
	}
	cout <<setprecision(10)<< ave << endl;
	bool equal = true;
	int c = 0;
	REP(i, A) {
		if (v[i] != v[0]) {
			equal = false;
			c = i;
			break;
		}
	}
	int c2 = 0;
	bool equal2=true;

	if (equal) {
		FOR(i, A, B) {
			if (v[i] != v[0]) {
				equal2 = false;
				c2 = i;
				break;
			}
		}
		ll ans = 0;
		if (equal2) {
			int cnt = 0;
			REP(i, N) {
				if (v[i] == v[0])cnt++;
			}
			FOR(i, A, B + 1) {
				ans += nCr(cnt, i);
			}
			cout << ans << endl;
			return 0;
		}
		else {
			FOR(i, A, c2+1) {
				ans += nCr(c2, i);
			}
			cout << ans << endl;
			return 0;
		}
	}
	else {
		int cnt = 0;
		int c3 = 0;
		REP(i, N) {
			if (v[i] == v[A - 1]) {
				c3 = i;
				break;
			}
		}
		REP(i, N) {
			if (v[i] == v[A - 1]) {
				cnt++;
			}
		}
		ll ans = 0;
		ans = nCr(cnt, A-c3);
		cout << ans << endl;
	}
}




Measured memory_bytes: 256
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;


__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}

int main()
{
	string s;
	
	cin >> s;

	int year = stoi(s.substr(0,4));
	int month = stoi(s.substr(5,2));
	int day = stoi(s.substr(8,2));
	//cout << year << " " << month << " " << day << endl;
	if (year < 2019)
	{
		cout << "Heisei" << endl;
	}
	else if (year == 2019)
	{
		if (month < 4)
		{
			cout << "Heisei" << endl;
		}
		else if (month == 4)
		{
			if (day <= 30)
			{
				cout << "Heisei" << endl;
			}
			else
			{
				cout << "TBD" << endl;
			}
		}
		else
		{
			cout << "TBD" << endl;
		}

	}
	else
	{
		cout << "TBD" << endl;
	}	
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <array>
#include <set>
#include <climits>
#include <cassert>
#include <bitset>
#include <numeric>
using namespace std;
#define mod 1000000007



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

#ifdef HELL_JUDGE
    freopen("input","r",stdin);
    freopen("output","w",stdout);
    freopen("error","w",stderr);
#endif 

    string s; cin>>s;
    cout<<string((int)s.size(),'x')<<endl;
    return 0;
}

Measured memory_bytes: 256
import fractions
from functools import reduce
import sys
n, m = map(int, input().split())
a = [int(i)//2 for i in input().split()]
a = list(set(a))
flg = -1
for i in a:
    if i%2==0 and flg!=1:
        flg = 0
    elif i%2==1 and flg!=0:
        flg = 1
    else:
        print(0)
        sys.exit(0)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

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

l = lcm(a)
for i in a:
    if (l//i)%2==0:
        print(0)
        sys.exit(0)
print((m+l)//(l*2))

Measured memory_bytes: 16344
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
typedef pair<int,vector<int> > P;
map<P,bool> mv;
int ax[]={0,1,2,-1,-2,0,0,0,0};
int ay[]={0,0,0,0,0,1,2,-1,-2};
int in(int y,int x){
  return 0<=y&&y<3&&0<=x&&x<3;
}
int in2(int y,int x){
  return 0<=y&&y<4&&0<=x&&x<4;
}
bool solve(int d,vector<int> m){
  if(d==n-1) return true;
  if(mv.count(P(d,m))) return mv[P(d,m)];
  int y=m[0]/3,x=m[0]%3;
  for(int k=0;k<9;k++){
    int ny=y+ay[k],nx=x+ax[k];
    if(!in(ny,nx)) continue;
    bool f=0;
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
	int ty=ny+i,tx=nx+j;
	if(!in2(ty,tx)) continue;
	if((v[d+1]>>(ty*4+tx))&1) f=1;
      }
    }
    if(f) continue;
    if(d>4){
      int a[4][4]={};
      for(int l=0;l<6;l++){
	int dy=m[l]/3,dx=m[l]%3;
	for(int i=0;i<2;i++){
	  for(int j=0;j<2;j++){
	    int ty=dy+i,tx=dx+j;
	    if(!in2(ty,tx)) continue;
	    a[ty][tx]++;
	  }
	}
      }
      for(int i=0;i<2;i++){
	for(int j=0;j<2;j++){
	  int ty=ny+i,tx=nx+j;
	  if(!in2(ty,tx)) continue;
	  a[ty][tx]++;
	}
      }
      for(int i=0;i<4;i++)
	for(int j=0;j<4;j++)
	  if(!a[i][j]) f=1;
    }
    
    vector<int> u(6);
    for(int i=1;i<6;i++) u[i]=m[i-1];
    u[0]=ny*3+nx;
    if(f) continue;
    if(solve(d+1,u)) return mv[P(d,m)]=true;
  }
  return mv[P(d,m)]=false;
}
signed main(){
  while(cin>>n,n){
    v.resize(n);
    for(int i=0;i<n;i++){
      v[i]=0;
      for(int j=0,k;j<16;j++){
	cin>>k;
	v[i]+=(1<<j)*k;
      }
    }
    vector<int> m(6,-1);
    m[0]=4;
    mv.clear();
    bool f=0;
    for(int i=0;i<2;i++){
      for(int j=0;j<2;j++){
	int ty=1+i,tx=1+j;
	if((v[0]>>(ty*4+tx))&1) f=1;
      }
    }
    //cout<<"f:"<<f<<endl;
    if(f) cout<<0<<endl;
    else  cout<<solve(0,m)<<endl;
  }
  return 0;
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) max((a),-(a))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define INF 1000000000

typedef long long LL;
typedef long double LD;

int main(){
  while(1){
    int n,m,c,s,g;
    cin >> n >> m >> c >> s >> g;
    if(n==0) return 0;
    s--,g--;
    vector<vector<vector<LL>>> dist(c,vector<vector<LL>>(n,vector<LL>(n,INF)));
    vector<vector<LL>> di(n,vector<LL>(n,INF));
    int u,v,d,cc;
    for(int i=0;i<m;i++){
      cin >> u >> v >> d >> cc;
      u--,v--,cc--;
      dist[cc][u][v]=min(dist[cc][u][v],d);
      dist[cc][v][u]=min(dist[cc][v][u],d);
    }
    vector<int> p(c);
    vector<vector<LL>> q(c),r(c),price(c);
    for(int i=0;i<c;i++){
      cin >> p[i];
      p[i]--;
      q[i]=vector<LL>(p[i]+1,0);
      r[i]=vector<LL>(p[i]+1,0);
      price[i]=vector<LL>(p[i]+1,0);
    }
    for(int i=0;i<c;i++){
      for(int j=1;j<=p[i];j++){
        cin >> q[i][j];
      }
      for(int j=0;j<=p[i];j++){
        cin >> r[i][j];
      }
      for(int j=1;j<=p[i];j++){
        price[i][j]=price[i][j-1]+r[i][j-1]*(q[i][j]-q[i][j-1]);
      }
    }
    for(int t=0;t<c;t++){
      for(int i=0;i<n;i++) dist[t][i][i]=0;
      for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
            dist[t][i][j]=min(dist[t][i][j],dist[t][i][k]+dist[t][k][j]);
          }
        }
      }
    }
    for(int i=0;i<n;i++) di[i][i]=0;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        for(int t=0;t<c;t++){
          int idx=distance(q[t].begin(),upper_bound(all(q[t]),dist[t][i][j]));
          idx--;
          di[i][j]=min(di[i][j],(price[t][idx]+r[t][idx]*(dist[t][i][j]-q[t][idx])));
        }
      }
    }
    for(int k=0;k<n;k++){
      for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
          di[i][j]=min(di[i][j],di[i][k]+di[k][j]);
        }
      }
    }
    if(di[s][g]==INF) cout << -1 << endl;
    else cout << di[s][g] << endl;
  }
  return 0;
}



Measured memory_bytes: 4720
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  ll v[2][102] = {};
  rep(i,2) repl(j,1,n+1) cin>>v[i][j];
  repl(i,1,n+1) v[0][i] += v[0][i-1];
  repl(i,1,n+1) v[1][i] += v[1][i-1];
  ll ans = -INF;
  rep(i,n) if(v[0][i+1] + v[1][n] - v[1][i] > ans) ans = (v[0][i+1] + v[1][n] - v[1][i]);
  cout<<ans<<endl;
}

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


Measured memory_bytes: 256
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

n=int(input())
print(l[n-1])

Measured memory_bytes: 3060
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>
#include <list>
#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for (long long i = 0; i < (n); ++i)
#define rep(i, a, b) for (long long i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;

typedef long long ll;
const ll MOD = 2019;
// xにmultをn回%modでかける
ll mod_pownum(ll x,ll mult, ll n, ll mod)
{
    if(n == 1)
    {
        return x * mult;
    }
    else if(n == 0)
    {
        return x;
    }
    ll res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * mult % mod;
        mult = mult * mult % mod;
        n >>= 1;
    }
    return (res * x) % mod;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    int len = s.length();

    vector<ll> cnt(2019);
    ll sum = 0;
    cnt[0]++;
    ll ans = 0;
    int x = 1;
    REP(i, len)
    {
        int val = s[i] - '0';
        val = mod_pownum(val, 10,  i, MOD);
        // val = val * x % MOD;
        sum = (sum + val) % MOD;
        ans += cnt[sum];
        cnt[sum]++;
        // x = x * 10 % MOD;
    }

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


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

const ll INF = 1e18;

int main(){
  int n,m,X,Y;
  cin >> n >> m >> X >> Y;
  vector<int> x(n);
  vector<int> y(m);
  rep(i,n) cin >> x[i];
  rep(i,m) cin >> y[i];

  sort(x.begin(),x.end());
  sort(y.begin(),y.end());

  int x_max = *x.rbegin();
  int y_min = *y.begin();

  for(int i=-100; i<=100; i++){
    if(X<i&&i<=Y&&x_max<i&&i<=y_min){
      cout << "No War" << endl;
      return 0;
    }
  }

  cout << "War" << endl;

  return 0;
}

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


int main() {
    char s[105];
    scanf("%s",s);
    int i,j;
    int len=strlen(s);
    int flag=1;
    for(i=0;i<=len-1;i++){
        int count=0;
        for(j=0;j<=len-1;j++){
            if(s[i]==s[j])count++;
        }
        if(count%2!=0)flag=0;
    }
    
    if(flag==0)printf("No");
    else printf("Yes");
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef unsigned long long ll;
const int maxn = 2005;
const int mod = 1000000007;

int n,m;
ll c[maxn][maxn];
void upd(ll &x, ll val){
  x+=val;
  if(x>=mod)x-=mod;
}
int Lowbit(int x)
{
  return x & (-x);
}
void Updata(int x,int y, ll val)
{
  int i,k;
  for(i=x; i<=n; i+=Lowbit(i))
    for(k=y; k<=m; k+=Lowbit(k))
      upd(c[i][k],val);
}
ll Get(int x,int y) {
  int i, k;
  ll sum = 0;
  for (i = x; i > 0; i -= Lowbit(i))
    for (k = y; k > 0; k -= Lowbit(k))
      upd(sum, c[i][k]);
  return sum;
}

ll s[maxn],t[maxn];
int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>s[i];
  for(int i=1;i<=m;i++)cin>>t[i];
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
      if(s[i]==t[j]){
        ll tt = Get(i-1,j-1);
        ll ret = tt;
        upd(ret, 1);
        Updata(i,j,ret);
      }
    }
  ll ret = Get(n,m);
    upd(ret, 1);
    cout<<ret<<endl;
  return 0;
}

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

using namespace std;

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

const long long INF = 1LL << 60;

#define rep(i, e) for(int i = 0; i < e; i++)
#define repp(i, s, e) for(int i = s; i < e; i++)
#define N_Max 100
#define Card_Max 36
#define p(a) printf("%d\n", a);
#define ll long long
#define ull unsigned long long
#define MAX 100005
#define NIL -1

int main() {
    int N;
    int h[100005] = {};
    int dp[100005] = {};
    cin >> N;
    rep(i, N) cin >> h[i];

    dp[0] = 0;
    dp[1] = abs(h[0]-h[1]);
    repp(i, 2, N) {
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
    }
    
    cout << dp[N-1] << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;



int main() {
	REP(i, 12) {
		char c;
		scanf("%c", &c);
		printf("%c", c);
		if(i == 3) printf(" ");
	}
	puts("");
	return 0;
}


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

int main(){
  int n,m; cin >> n >> m;
  int c=0,p=0;
  string s; cin >> s;
  reverse(s.begin(), s.end());
  vector<int> v;
  for(int i=0;i<n+1;i++){
  	if(p==n) break;
    bool f = false;
    for(int j=min(n,p+m); j>p; j--){
    	if(s[j]=='0'){f = true;v.push_back(j-p); p = j;  break;}
    }
    if(f) c++;
    else{
      cout << "-1" << endl;
      return 0;
    }
  }
  reverse(v.begin(), v.end());
  for(auto x: v) cout << x << " ";
  cout << endl;
  return 0;
}

Measured memory_bytes: 1080
class Node:
    def __init__(self, x):
        self.x = x
        self.left = None
        self.right = None


def reconstruct(x, y):
    top = x[0]
    root = Node(top)
    # print("root:", top)

    mid = y.index(top)
    left = y[:mid]
    right = y[mid+1:]
    if len(left) > 0:
        root.left = reconstruct(x[1:mid+1], left)
    if len(right) > 0:
        root.right = reconstruct(x[mid+1:], right)

    return root


def postorder(L, node):
    if node is None:
        return
    postorder(L, node.left)
    postorder(L, node.right)
    L.append(node.x)


if __name__ == "__main__":
    input()
    preorder = input().split()
    inorder = input().split()
    root = reconstruct(preorder, inorder)
    L = []
    postorder(L, root)
    print(' '.join(L))

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

int main() {
  int a, b;
  cin >> a >> b;
  if(a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0) {
    cout << "Possible\n";
  } else {
    cout << "Impossible\n";
  }
}


Measured memory_bytes: 3572
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {

    int n, m;
    scanf("%d %d", &n, &m);

    int arr[m];

    //初期化
    for (int i = 0; i < m; i++) {
        arr[i] = 0;
    }

    for (int j = 0; j < n; j++) {
        int k;
        scanf("%d", &k);

        int a;
        for (int l = 0; l < k; l++) {
            scanf("%d", &a);
            arr[a - 1] += 1;
        }

    }

    int cnt = 0;
    for (int x = 0; x < m; x++) {
        if (arr[x] == n) {
            cnt += 1;
        }
    }

    printf("%d",cnt);



    return 0;

}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const long double pi=3.14159265358979323846;
#define x  first
#define y  second
#define deb(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}

bool isPar(string s)
{
    ll n=s.size();
    for(int i=0;i<n/2;i++)
    {
        if(s[i]!=s[n-i-1])
        {
            return 0;
        }
    }
    return 1;
}

ll nOfD(ll n)
{
    ll d=0;
    ll i=1;
    while(i * i < n)
    {
        if(n%i ==0) d+=2;
        i++;
    }
    if(i * i == n)d++;
    return d;
}
ll sOfD(ll n)
{
    ll sum=0;
    ll i=1;
    while(i * i < n)
    {
        if(n%i ==0) sum+=i,sum+=n/i;
        i++;
    }
    if(i * i == n)sum+=i;
    return sum;
}
bool isP(ll x)
{
    if(x==2)return 1;
    if(x<2 || x%2==0)return 0;
    for(ll i=3;i * i <= x;i+=2)
    {
        if(x%i==0)return 0;
    }
    return 1;
}
ll lcm(ll a, ll b)
{
    return (a / __gcd(a, b) * b);
}

int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
    ///freopen("ss.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t=1;
    //cin>>t;
    while(t--)
    {
        int n;
        string s;
        cin>>n>>s;
        int r=count(s.begin(),s.end(),'R');
        int w=n-r;
        string ss=string(r,'R')+string(w,'W');
        int ans=0;
        for(int i=0;i<n;i++)ans+=s[i]!=ss[i];
        cout<<ans/2;
    }
    return 0;
}


Measured memory_bytes: 3944
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    int n;
    cin >> n;
    vi a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    ll ret = 0;
    for (ll i = 1; i <= (1 << 28); i <<= 1) {
        ll num = 0;
        vi aa = a;
        vi bb = b;
        for (int j = 0; j < n; ++j) {
            aa[j] %= i * 2;
            bb[j] %= i * 2;
        }
        sort(bb.begin(), bb.end());
        for (int j = 0; j < n; ++j) {
            num += lower_bound(bb.begin(), bb.end(), i * 2 - aa[j]) - lower_bound(bb.begin(), bb.end(), i - aa[j]);
            num += lower_bound(bb.begin(), bb.end(), i * 4 - aa[j]) - lower_bound(bb.begin(), bb.end(), i * 3 - aa[j]);
        }
        ret += i * (num % 2);
    }
    cout << ret << "\n";
    return 0;
}

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

#define INCANT cin.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define out(a) cout << a << endl
#define PRINT(V) for (auto v : (V)) cout << v << " "

const int MOD = 1000000007;
const double PI = acos(-1.0);

void solve() {
    ll N, K;
    cin >> N >> K;
    N = N%K;
    if(N < K){
        if(N < K-N) {
            out(N);
            return;
        }else{
            out(K-N);
            return;
        }
    }
}
int main() {
    INCANT;
    solve();
    return 0;
}




Measured memory_bytes: 3580
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
def POW(x, y):
  bin_ = []
  while y:
    bin_.append(y % 2)
    y >>= 1
  ret = 1
  for j in reversed(bin_):
    ret = (ret * ret) % mod
    if j == 1:
      ret = (ret * x) % mod
  return ret
def comb(x, y):
  ret = 1
  for i in range(1, y+1):
    ret = (ret * (x+1-i)) % mod
    ret = (ret * POW(i, mod-2)) % mod
  return ret
print((POW(2, n) - 1 - comb(n, a) - comb(n, b)) % mod)

Measured memory_bytes: 73856
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        for j in range(max_capacity, w - 1, -1):
            tmp = dp[j - w] + v
            if dp[j] < tmp:
                dp[j] = tmp
    return dp[max_capacity]


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


Measured memory_bytes: 11836
#include <bits/stdc++.h>
#include <stdio.h>
#include <cmath>

using namespace std;

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const ll inf = 1e9+7;
const ll mod = 1e9+7;

int main() {
    int n,cnt=0;
    cin>>n;

    vector<int>x(100001);
    rep(i,n){
        int l,r;
        cin>>l>>r;

        rep2(i,l,r)x[i]++;
    }

    rep2(i,1,100000)cnt+=x[i];

    cout<<cnt<<endl;

}





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

int main() {
    int n;
    scanf("%d", &n);
    set<vector<int> > data;
    rep(i,n) {
        vector<int> MEN(3);
        scanf("%d %d %d", &MEN.at(0), &MEN.at(1), &MEN.at(2));
        sort(all(MEN));
        data.insert(MEN);
    }
    printf("%d\n", n-data.size());
}



Measured memory_bytes: 3356
#include <bits/stdc++.h>
using namespace std;
struct N {
	long long c0, c1, id;
};
bool operator<(const N &a, const N &b) {
	return a.c1 * b.c0 < a.c0 * b.c1 || a.c1 * b.c0 == a.c0 * b.c1 && a.id < b.id;
}
set<N> s;
int n;
int f[200020];
int p[200020];
int c0[200020];
int c1[200020];
long long z;
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		scanf("%d", &p[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &c1[i]);
		c0[i] = 1 - c1[i];
		f[i] = i;
	}
	for (int i = 2; i <= n; i++) {
		s.insert({c0[i], c1[i], i});
	}
	while (s.size()) {
		N u = *s.begin();
		s.erase(s.begin());
		int x = u.id;
		int y = f[x] = F(p[x]);
		z += (long long)c1[y] * c0[x];
		if (y != 1) {
			s.erase({c0[y], c1[y], y});
		}
		c0[y] += c0[x];
		c1[y] += c1[x];
		if (y != 1) {
			s.insert({c0[y], c1[y], y});
		}
	}
	printf("%lld\n", z);
	return 0;
}

Measured memory_bytes: 15872
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<climits>
#include<set>
#include<utility>
using namespace std;
typedef long long int ll;

int main(){

	int n, m, x, a[100], ans=0, tmp;
	cin >> n >> m >> x;
	for(int i=0; i<m; i++){
		cin >> a[i];
	}

	for(int i=0; i<m; i++){
		if(x<a[i]){
			ans++;
		}
	}
	tmp=ans;
	ans=0;
	for(int i=0; i<m; i++){
		if(a[i]<x){
			ans++;
		}
	}

	cout << min(ans, tmp) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int main(int argc, char *argv[])
{
    int n;
    long long d;
    scanf("%d%lld",&n,&d);
    long long dis=d*d;
    long long x,y;
    int ans=0;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&x,&y);
        long long xy=x*x+y*y;
        if(xy<=dis){
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}

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

int main(){
  double n, d, x, y, ways = 0;
  cin >> n >> d;
  for (int i = 0; i < n; i++){
    cin >> x >> y;
    if (hypotl(x, y) <= d){
      ways = ways + 1;
    }
  }
  cout << ways << endl;
}

Measured memory_bytes: 3880
def main():
    n = int(input())
    a = [None]*n
    for i in range(n):
        x, y = map(int, input().split())
        a[i] = [x, y]
    p, q = 0, 0
    cnt = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            sp, sq = a[i][0]-a[j][0], a[i][1]-a[j][1]
            scnt = 0
            for k in range(n):
                for l in range(n):
                    if k == l:
                        continue
                    if a[k][0]-a[l][0] == sp and a[k][1]-a[l][1] == sq:
                        scnt += 1
            if scnt > cnt:
                cnt = scnt
                p = sp
                q = sq
    print(n-cnt)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL mod = 1000000007;

LL N, M;
std::vector<LL>memo;
std::vector<bool>flag;

LL dp(LL i)
{
	if (i == N) return 1;
	if (i > N) return 0;
	if (flag[i]) return 0;
	if (memo[i] != -1) return memo[i];
	LL res1 = dp(i + 1);
	LL res2 = dp(i + 2);
	return memo[i] = (res1 + res2) % mod;
}

int main()
{
	in >> N >> M;
	std::vector<LL>a(M);
	rep(i, M) in >> a[i];

	flag.resize(N + 1, false);
	rep(i, M) flag[a[i]] = true;

	memo.resize(N + 1, -1);
	out << dp(0) << std::endl;
}


Measured memory_bytes: 4224
n,m=map(int,input().split())
a=[[j for j in input()] for i in range(n)]
b=[[j for j in input()] for i in range(m)]
for i in range(n-m+1):
    for j in range(n-m+1):
        if all(k[j:j+m]==b[bi] for bi,k in enumerate(a[i:i+m])):
            print("Yes")
            quit()
print("No")

Measured memory_bytes: 3064
H, W = map(int, input().split())
S = []
D = [[-1, 0], [0, -1], [1, 0], [0, 1]]
for i in range(H):
  S.append(input())
f = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      g = 0
      for k in range(4):
        if 0 <= i + D[k][0] < H and 0 <= j + D[k][1] < W and S[i+D[k][0]][j+D[k][1]] == "#":
          g = 1
      if g == 0:
        f = 1
if f == 0:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 68252
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  int N;
  string S,res="";
  cin >> N;
  cin >> S;
  REP(i,2){
    REP(j,2){
      res = "";
      if(i == 0){
        res += "S";
      }else{
        res += "W";
      }
      if(j == 0){
        res += "S";
      }else{
        res += "W";
      }
      for(int k=1;k<N-1;k++){
        if(res[k] == 'S'){
          if(S[k] == 'o'){
            res.push_back(res[k-1]);
          }else{
            res.push_back(res[k-1] == 'S' ? 'W' : 'S');
          }
        }else{
          if(S[k] == 'x'){
            res.push_back(res[k-1]);
          }else{
            res.push_back(res[k-1] == 'S' ? 'W' : 'S');
          }
        }
      }
      int f=1;
      REP(i,N){
        if(S[i] == 'o'){
          if(res[i] == 'S'){
            if(res[(N+i-1)%N] != res[(N+i+1)%N])
              f=0;
          }else{
            if(res[(N+i-1)%N] == res[(N+i+1)%N])
              f=0;
          }
        }else{
          if(res[i] == 'S'){
            if(res[(N+i-1)%N] == res[(N+i+1)%N])
              f=0;
          }else{
            if(res[(N+i-1)%N] != res[(N+i+1)%N])
              f=0;
          }
        }
      }
      if(f){
        cout << res << endl;
        return 0;
      }
    }
  }
  cout << -1 << endl;
  return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
#define all(i) i.begin(),i.end()
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  ll X;
  cin>>X;
  ll A,B;
  for(int i=-120;i<=119;i++){
    for(int j=-120;j<=119;j++){
      if(i*i*i*i*i-j*j*j*j*j==X){
        A=i;
        B=j;
        break;
      }
    }
  }
  cout<<A<<" "<<B<<endl;
}


Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <map>

using ull = unsigned long long;

static ull const P = 1000000007;

template<typename INT, INT P>
class Modulo {
  INT val;

  friend
  std::ostream&
  operator<<(std::ostream& os, Modulo const& m) {
    return os << m.val;
  }

  friend
  Modulo<INT, P>
  operator*(Modulo<INT, P> const& a, Modulo<INT, P> const& b) {
    return a.val * b.val;
  }

  static std::vector<INT> _facts;

public:
  Modulo(INT v) : val(v % P) {};

  Modulo<INT, P>& operator*=(Modulo<INT, P> const& other) {
    val *= other.val;
    val %= P;
    return *this;
  }

  static INT facts(size_t n) {
    auto s = _facts.size();
    if (s < n+1) {
      _facts.resize(n+1);
      for (size_t i=s; i<n+1; i++) {
        if (i==0) {
          _facts[0] = 1;
        } else {
          _facts[i] = (_facts[i-1] * i) % P;
        }
      }
    }
    return _facts[n];
  }
};

template<typename INT, INT P>
std::vector<INT> Modulo<INT, P>::_facts;

template <typename INT, INT P>
Modulo<INT, P>
power(INT a, INT b) {
  if (b == 0) {
    return 1;
  }

  if (b % 2 == 0) {
    auto d = power<INT, P>(a, b/2);
    return d*d;
  }

  return a * power<INT, P>(a, b-1);
}

template <typename INT, INT P>
Modulo<INT, P>
comb(INT n, INT k) {
  if (n<0 || k<0 || n<k) return 0;
  if (n==0 || k==0) return 1;

  auto a = Modulo<INT, P>::facts(n);
  auto b = Modulo<INT, P>::facts(k);
  auto c = Modulo<INT, P>::facts(n-k);

  return a * power<INT, P>(b, P-2) * power<INT, P>(c, P-2);;
}

std::map<ull, ull>
get_prime_factors(ull const N) {
  std::map<ull, ull> prime_factors;

  if (N<2) {
    // prime_factors.insert(std::make_pair(N, 1));
    return prime_factors;
  }

  auto n = N;
  for (ull p=2; p*p<=N; p++) {
    while (n % p == 0) {
      prime_factors[p]++;
      n /= p;
    }
  }

  if (n > 1) prime_factors[n]++;

  return prime_factors;
}

int main() {
  ull N, M;
  std::cin >> N >> M;

  Modulo<ull, P> ans(1);

  for (auto const& p : get_prime_factors(M)) {
    auto k = std::get<1>(p);
    ans *= comb<ull, P>(N+k-1, k);
  }

  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 1792
#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 rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define show(x) cout << #x << " = " << (x) << endl;
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl;
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
//cout << fixed << setprecision(10);

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 () {
  int n, k;
  cin >> n >> k;
  vi d(k);
  rep(i,k) cin >> d[i];

  for (int i = n; i <= 10*n; ++i) {
    string s = to_string(i);
    bool ok = true;
    rep(j,sz(s)) {
      if (binary_search(rng(d), s[j]-'0')) {
        ok = false;
        break;
      }
    }
    if (ok) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}

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

int main() {
  int c = 0;
  while(true){
    string s;
    cin >> s;
    if(s.size() == 0){
      cout << "" << endl;
      return 0;
    }
    if(c != 0) cout << " ";
    for(int i = 0;i < s.size();i++){
      if(islower(s[i])) s[i] = toupper(s[i]);
      else if(isupper(s[i])) s[i] = tolower(s[i]);
      cout << s[i];
    }
    c++;
  }
}



Measured memory_bytes: 3168
class UnionFindTree:
    
    def __init__(self, n):
        if n == 0:
            raise Exception("n is more than 1")
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.num = {}
        for i in range(n):
            self.num.update({i:1})
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[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.parent[x] = y
            self.num[y] += self.num[x]
            del self.num[x]
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.num[x] += self.num[y]
            del self.num[y]
        
    
    def same(self, x, y):
        X = self.find(x)
        Y = self.find(y)
        return X == Y

def add_dict(d, a, b):
    d[a].append(b)
    d[b].append(a)

def Main(N, M, K, A, B, C, D):
    uft = UnionFindTree(N)
    df = {}
    db = {}
    for i in range(N):
        df.update({i:[]})
        db.update({i:[]})
    for i in range(M):
        uft.unite(A[i]-1, B[i]-1)
        add_dict(df, A[i]-1, B[i]-1)
    for i in range(K):
        add_dict(db, C[i]-1, D[i]-1)
    ans = []
    for i in range(N):
        num_b = 0
        for e in db[i]:
            if uft.same(i, e):
                num_b += 1
        a = uft.num[uft.find(i)] - len(df[i]) - num_b - 1
        ans.append(str(a))
    return ans
                    
def main():
    N, M, K = map(int, input().split())
    A = []
    B = []
    C = []
    D = []
    for i in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    for i in range(K):
        c, d = map(int, input().split())
        C.append(c)
        D.append(d)
    out = Main(N, M, K, A, B, C, D)
    print(" ".join(out))

if __name__ == '__main__':
    main()

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


int main() {
	int W, H, x, y, r;
	cin >> W >> H >> x >> y >> r;
	bool inside = true;
	if((x - r) < 0) inside = false;
	if((x + r) > W) inside = false;
	if((y - r) < 0) inside = false;
	if((y + r) > H) inside = false;
	if(inside) cout << "Yes";
	else cout << "No";
	cout << endl;
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define It set<node>::iterator
#define endl '\n'
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=2e6+10;
const int inf=0x3f3f3f3f;

int n;
vector<int> v;
vector<int> ans;

inline void addval(){
	int x=0;
	for(int i=0;i<v.size();++i){
		x=x*10+v[i];
	}
	ans.pb(x);
}

inline void dfs(int depth,int val){
	if(depth==1){
		addval();
		return ;
	}
	for(int i=val-1;i<=val+1;++i) if(i>=0&&i<=9){
		v.pb(i);
//		cout<<v.size()<<endl;
		dfs(depth-1,i);
		v.pop_back();
//		cout<<v.size()<<endl;
	}
}

signed main(){
	cin>>n;
	for(int i=1;i<=10;++i){
		for(int j=1;j<=9;++j){
			v.pb(j);
			dfs(i,j);
			v.pop_back();
		}
	}
	sort(ans.begin(),ans.end());
	cout<<ans[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 2420
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main(){
	int n;
	long num;
	vector<long> R;
	
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>num;
		R.push_back(num);
	}

	long maxv = R[1] - R[0], minv = R[0];
	for(int j=1;j<n;j++){
		maxv = max(maxv, R[j] - minv);
		minv = min(minv, R[j]);
	}

	cout<<maxv<<endl;

	return 0;
}

Measured memory_bytes: 3112
#pragma once
#include <stdio.h>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

ll bit[200010];
int max_n = 200000;
int pm = 0;
void add(int x) {

	while (max_n >= x)
	{
		bit[x]++;
		x += x & -x;
	}
}
void sub(int x) {
	while (max_n >= x)
	{
		bit[x]--;
		x += x & -x;
	}
}
int search(int x) {

	int k = 0;
	int p = 1;
	while (p * 2 <= max_n)
	{
		p *= 2;
	}
	for (int i = p; i > 0; i /= 2)
	{
		if (i + k < max_n && bit[i + k] < x) {
			x -= bit[i + k];
			k += i;
		}
	}
	return k + 1;
}
void solv() {
	string s;
	map<char, int> mp;
	while (cin >> s) {
		for (size_t i = 0; i < s.size(); i++)
		{
			mp[s[i]]++;
		}

	}

	for (char c = 'a',C = 'A'; c <= 'z'; c++,C++)
	{
		cout << c << " : " << mp[c] + mp[C] << endl;
	}

}
int main() {
	//	COMinit();
	solv();
	return 0;
}



Measured memory_bytes: 3156