akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<int, int>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

using namespace std;
using ll = long long;
const int mod = 1e9+7;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int N; cin >> N;

  unordered_map<ll, ll> mp;
  rep(i, N) {
    int a;
    cin >> a;
    mp[a]++;
  }

  ll ans = 0;
  for(int k=30; k>=1; k--) {
    //debugln(k);
    int s = 1<<k;
    //debugln(s);
    //debugln(mp.size());
    for(auto e: mp) {
      if (e.first >= s) continue;
      if (e.first < s/2) continue;
      ll pos = e.first;
      ll cnt = e.second;
      if (pos == s/2) {
        ans += cnt/2;
      } else {
        ans += min(cnt,mp[s-pos]);
        mp[s-pos] = mp[s-pos]-cnt;
        if (mp[s-pos] <= 0) {
          mp.erase(s-pos);
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 8520
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9

bool prime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i < x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

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

    int a = x;
    while(!prime(a)) {
        a++;
    } 

    cout << a << endl;

    return 0;
}

Measured memory_bytes: 3564
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

typedef long long LL;
typedef vector<LL> VL;
typedef vector<vector<LL>> VVL;
typedef vector<string> VS;

#define REPD(i,a,b) for (LL i=(a);i<(b);i++)
#define REP(i,n) REPD(i,0,n)

LL llRead(){
  LL a;
  cin >> a;
  return a;
};

string stringRead(){
  string a;
  cin >> a;
  return a;
};

vector<LL> vlRead(LL a){
  vector<LL> rv;
  REP(i, a){
    LL input;
    cin >> input;
    rv.push_back(input);
  }
  return rv;
}

vector<string> vsRead(LL a){
  vector<string> rv;
  REP(i, a){
    string input;
    cin >> input;
    rv.push_back(input);
  }
  return rv;
}
vector<vector<LL>> vvlRead(LL a, LL b){
  vector<vector<LL>> rv;
  REP(i, a){
    rv.push_back(vector<LL>());
    REP(j, b) {
      LL input;
      cin >> input;
      rv.at(i).push_back(input);
    }
  }
  return rv;
}

#if 0
#define debug(d) debug1(__LINE__,#d, d)
void debug1(LL line, const char* name, VL& v) {
  cout << line << ":" << name << ":vector<LL>(" << v.size() << ") ";
  REP(i, (LL)v.size()) {
    cout << v.at(i) << " ";
  }
  cout << endl;
}
void debug1(LL line, const char* name, LL i) {
  cout << line << ":" << name << ":LL " << i << endl;;
}
void debug1(LL line, const char* name, VS& v) {
  cout << line << ":" << name << ":vector<string>(" << v.size() << ") ";
  REP(i, (LL)v.size()) {
    cout << v.at(i) << " ";
  }
  cout << endl;
}
void debug1(LL line, const char* name, VVL& v) {
  cout << line << ":" << name << ":vector<vector<LL>>(" << v.size() << ") ";
  REP(i, (LL)v.size()) {
    REP(j, (LL)v.at(i).size()) {
      cout << v.at(i).at(j) << " ";
    }
    cout << ", ";
  }
  cout << endl;
}
void debug1(LL line, const char* name, char* s) {
  cout << line << ":" << name << ":char* " << s << endl;;
}
void debug1(LL line, const char* name, vector<const char*>& v) {
  cout << line << ":" << name << ":vector<const char*>(" << v.size() << ") ";
  REP(i, (LL)v.size()) {
    cout << v.at(i) << " ";
  }
  cout << endl;
}
void debug1(LL line, const char* name, priority_queue<LL>& p) {
  cout << line << ":" << name << ":priority_queue<LL>(" << p.size() << ") ";
  priority_queue<LL> copy = p;
  while(!copy.empty()) {
    cout << copy.top() << " ";
    copy.pop();
  }
  cout << endl;
}
#else
#define debug(n)
#endif

int main(int argc, const char * argv[]) {
	cout.precision(16);
  // source code

  auto n = llRead();
  auto ls = vlRead(n);
  sort(ls.begin(), ls.end());
  debug(ls);

  LL c = 0;
  REP(i, n-2) {
    auto il = ls.at(i);
    REPD(j, i+1, n-1) {
      auto jl = ls.at(j);
      // il-jl < kl && jl-il < kl && kl < il+jl
      auto lower = max(il-jl, jl-il);
      auto upper = il+jl;
      REPD(k, j+1, n) {
        auto kl = ls.at(k);
        if (kl > lower && kl < upper) {
          debug("-------");
          debug(il);
          debug(jl);
          debug(kl);
          c++;
        }
      }
    }
  }
  cout << c << endl;

  return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
#define ll long long
int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll p=a*c,q=a*d,r=b*c,s=b*d;
    cout<<max(p,max(q,max(r,s)))<<endl;
    return 0;
}

Measured memory_bytes: 3632
#include <cstdio>

#define mx 1000006
bool seen[mx];

int main(){
    int k;
    scanf("%d",&k);

    for(int i=0;i<=k;i++) seen[i]=false;

    seen[7%k]=true;
    int rem=7%k;
    int steps=1;
    while(1){
        if(rem==0){
            printf("%d\n",steps);
            break;
        }
        steps++;
        rem=(rem*10+7)%k;
        if(seen[rem]){
            printf("-1\n");
            break;
        }
        seen[rem]=true;
    }
}


Measured memory_bytes: 2636
#include <stdio.h>

int main(void)
{
	int a[4][2],s,t,n;
	for(t=0;t<4;t++){
		for(n=0;n<2;n++){
			scanf("%d",&a[t][n]);
		}
	}
	for(t=0;t<4;t++){
		if(a[t][0]==1){
			s=a[t][1]*6000;
		}
		else if(a[t][0]==2){
			s=a[t][1]*4000;
		}
		else if(a[t][0]==3){
			s=a[t][1]*3000;
		}
		else{
			s=a[t][1]*2000;
		}
		printf("%d\n",s);
	}
		
	return 0;
}


Measured memory_bytes: 2120
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char X,Y;
  cin >> X >> Y;
  int x = 0, y = 0;
  
  if(X == 'A'){
  	x = 10;	
  }else if(X == 'B'){
  	x = 11;
  }else if(X == 'C'){
  	x = 12;
  }else if(X == 'D'){
  	x = 13;
  }else if(X == 'E'){
  	x = 14;
  }else if(X == 'F'){
  	x = 15;
  }
  
  if(Y == 'A'){
  	y = 10;	
  }else if(Y == 'B'){
  	y = 11;
  }else if(Y == 'C'){
  	y = 12;
  }else if(Y == 'D'){
  	y = 13;
  }else if(Y == 'E'){
  	y = 14;
  }else if(Y == 'F'){
  	y = 15;
  }
  
  if(x == y){
  	cout << "=" << endl;
  }else if(x > y){
  	cout << ">" << endl;
  }else if(x < y){
  	cout << "<" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M;
  char graph[128];
  while(cin >> N,N){
    for(int i = 0;i < 128;i++)graph[i] = i;
    char a,b;
    for(int i = 0;i < N;i++){
      cin >> a >> b;
      graph[a] = b;
    }
    cin >> M;
    for(int i = 0;i < M;i++){
      cin >> a;
      cout << graph[a];
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define int ll
using pii = pair <int, int>;
#define INF 0x7f7f7f7f7f7f7f7f
const bool debug = 0;
const int mod = 1000000007;

map<int, int> mp;
int h[202020];
int ans = 0;
int32_t main()
{
    usecppio
    int n; cin >> n;
    for (int i = 1; i<=n; i++)
        cin >> h[i];
    for (int i = 1; i<=n; i++)
        mp[i-h[i]]++;
    for (int i = 1; i<=n; i++)
        ans += mp[i+h[i]];
    cout << ans<< '\n';
}

Measured memory_bytes: 27956
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define INF 1000000000
#define rep(i,a,b) for (int i=(a);i<(b);i++)
#define rev(i,a,b) for (int i=(a)-1;i>=b;i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef queue<int> qi;
typedef vector<int> vi;
typedef vector<string> vs;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

int n, s;

int dfs(int sum, int num, int pre) {
  if (num == n) {
    if (sum == s) return 1;
    else return 0;
  }

  int ret = 0;
  rep(i,pre + 1,10) {
    ret += dfs(sum+i, num+1, i);
  }
  return ret;
}

int main() {

  while(1) {
    cin >> n >> s;
    if (!n && !s) break;

    cout << dfs(0, 0, -1) << endl;
  }

	return 0;
}

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

int main()
{
    int a , b;

    cin >> a >> b;

    if(a%3==0 || b%3==0 || (a+b)%3==0)
    {
        cout << "Possible";
        return 0;
    }
    cout << "Impossible";
    return 0;
}


Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;


static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var neighbours = Enumerable.Repeat(0, n).Select(x => new List<Tuple<int, int>>()).ToArray();
        for (int i = 0; i < n - 1; i++)
        {
            var uvw = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var u = uvw[0] - 1;
            var v = uvw[1] - 1;
            var w = uvw[2];
            neighbours[u].Add(new Tuple<int, int>(v, w));
            neighbours[v].Add(new Tuple<int, int>(u, w));
        }
        int[] res = Enumerable.Repeat(-1, n).ToArray();
        Stack<int> stack = new Stack<int>();
        stack.Push(0);
        res[0] = 0;
        while (stack.Count > 0)
        {
            var elem = stack.Pop();
            foreach (var neighbour in neighbours[elem])
            {
                if (res[neighbour.Item1] != -1) continue;
                res[neighbour.Item1] = res[elem] ^ (neighbour.Item2 & 1);
                stack.Push(neighbour.Item1);
            }
        }
        Console.WriteLine(string.Join("\n", res));
    }

}


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

using namespace std;

constexpr int mod = 1e9+7;

int n;
char str[2][53];

int main() {
  scanf("%d", &n);
  for(int i = 0; i<2; ++i)
    scanf("%s", str[i]);
  bool prv = (str[0][0] != str[1][0]);
  int ans = (prv ? 6 : 3);
  for(int i = prv+1; i<n; ++i) {
    if(str[0][i] != str[1][i]) {
      if(prv) ans = (3LL * ans) % mod;
      else ans = (2LL * ans) % mod;
      ++i;
      prv = true;
    } else {
      if(!prv) ans = (2LL * ans) % mod;
      prv = false;
    }
  }
  printf("%d\n", ans);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

map<ll,ll> cnt;

template <class T>
void prime_factor(T x){
	for(T i=2;i*i<=x;i++){
		while(x%i==0){
			x/=i;
			cnt[i]++;
		}
	}
	if (x!=1){
		cnt[x]++;
	}
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  FOR(i,1,n+1) prime_factor(i);
  map<int,int> now;
  for(auto itr:cnt){
    if(74<=itr.se) now[74]++;
    else if(24<=itr.se) now[24]++;
    else if(14<=itr.se) now[14]++;
    else if(4<=itr.se) now[4]++;
    else if(2<=itr.se) now[2]++;
  }
  int ans=now[74]+(now[24]+now[74])*(now[2]+now[4]+now[14]+now[24]+now[74]-1)+(now[14]+now[24]+now[74])*(now[4]+now[14]+now[24]+now[74]-1);
  ans+=(now[4]+now[14]+now[24]+now[74])*(now[4]+now[14]+now[24]+now[74]-1)*(now[4]+now[14]+now[24]+now[74]+now[2]-2)/2;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1335>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */
int N,K,S;
ll dp[22][12][200];
ll solve(){
    ll res = 0;
    fill(**dp,**dp+22*12*200,0);
    dp[1][0][0] = 1;
    for(int i = 1; i <= N;i++){
        for(int j = 0; j <= K;j++){
            for(int k = 0; k <= S; k++){
                if(dp[i][j][k] == 0) continue;
                dp[i+1][j][k] += dp[i][j][k];
                dp[i+1][j+1][k+i] += dp[i][j][k];
            }
        }
    }
    res = dp[N+1][K][S];
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    while(cin >> N >> K >> S,N){
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 3444
using System;
using System.Linq;

namespace _0317
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine(x[0] / x[1] + x[0] % x[1]);
        }
    }
}

Measured memory_bytes: 9588
import java.util.*;
public class Main 
{
	public static void main(String[] args) 
	{
		Scanner stdIn = new Scanner(System.in);
		while(stdIn.hasNext())
		{
			int num = stdIn.nextInt();
			int ans = 1;
			for(int i = 1; i <= num; ++i)
			{
				ans += i;
			}
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 12000
import sys
from itertools import product

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    bulbs = []
    for _ in range(M):
        b = tuple(map(int, input().split()))
        bulbs.append(b[1:])

    P = list(map(int, input().split()))

    ans = 0
    for switch in product((0, 1), repeat=N):
        check = [0] * M
        for i, bulb in enumerate(bulbs):
            cnt = 0
            for b in bulb:
                cnt += switch[b-1]

            if cnt % 2 == P[i]:
                check[i] = True
            else:
                check[i] = False

        if all(check):
            ans += 1

    return ans



if __name__ == '__main__':
    print(main())


Measured memory_bytes: 3064
/**
     **author : _KMS_
     **created : 12-03-2020
**/
#include<bits/stdc++.h>
using namespace std;
const long long M =1e5+100,MOD=2e9;
typedef long long ll;
int arr[10];
set<int>st,st2;
string s,p;
int main() 
{ 
      
  ios::sync_with_stdio(false);
  cin.tie(0);
 int n,k;
 cin>>n>>k;
 for(int i=0;i<k;i++){int a; cin>>a;
 st.insert(a);
 }
 for(int i=0;i<=9;i++)
 {
       if(st.find(i)==st.end())
       {
             st2.insert(i);
       }
 }
 while(n>0)
 {
       s+=(n%10)+'0';
       n/=10;
 }
 reverse(s.begin(),s.end());
 //cout<<s<<endl;
 bool f=0;
 for(int i=0;i<s.size();i++)
 {
       if(f)
       {
             auto x=st2.begin();
             int l=*x;
             p+=l+'0';
             
       }
       else
       {
             for(auto x : st2)
             {
                   int l=x;
                 
                   if(l>=s[i]-'0')
                   {
                         if(l>s[i]-'0')
                         {
                         
                               p+=l+'0';
                               f=1;
                         }
                         else
                         {
                               p+=s[i];
                         }
                         break;
                   }
             }
       }
 }
 for(int i=0;i<s.size();i++)
 {
       if(s[i]>p[i]&&!f)
       {
             p="";
             for(auto x: st2)
             {
                   int l=x;
                   if(l!=0)
                   {
                         p+=l+'0';
                         break;
                   }
             }
             for(int i=0;i<s.size();i++)
             {
                   auto x=st2.begin();
                   int l=*x;
                   p+=l+'0';
             }
             break;
       }
 }
 cout<<p<<endl;
 
 
   
   
	return 0; 
} 

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

int main()
{
    double max_m, min_m, tmp;

    max_m = numeric_limits<double>::min();
    min_m = numeric_limits<double>::max();
    while (cin >> tmp) {
        max_m = max(max_m, tmp);
        min_m = min(min_m, tmp);
    }
    cout << max_m - min_m << endl;

    return 0;
}

Measured memory_bytes: 1280
# include <bits/stdc++.h>
# define LL long long
using namespace std;
const int N = 2e6 + 10;
int d[N][2];
int main(){
	string s;
	cin >> s;
	d[0][0] = s[0] - '0';
	d[0][1] = 11 - (s[0] - '0');
	for(int i = 1; i < s.size(); i++){
		d[i][0] = min(d[i - 1][0], d[i - 1][1]) + s[i] - '0';
		d[i][1] = min(d[i - 1][0] + 1, d[i - 1][1] - 1) + 10 - (s[i] - '0');
	}
	cout << min(d[s.size() - 1][0], d[s.size() - 1][1]) << endl;
}


Measured memory_bytes: 9476
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define out(x) cout << x << '\n'
#define lli long long int
#define uli unsigned long long int
#define rep(i, m, n) for (lli i = m; i < (n); i++)
#define repe(i, m, n) for (lli i = m; i <= (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((lli)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define _GLIBCXX_DEBUG
const lli INF = 2147483647;
const lli MINF = -2147483648;
const lli LINF = 9223372036854775807;
const lli MOD = 1000000007; //10^9+7
const double PI = acos(-1);
#define SORT(n) sort(n.begin(), n.end())
#define SORTR(n) sort(n.begin(), n.end(), greater<int>())
#define REV(n) reverse(n.begin(), n.end())
#define pb push_back
#define eb emplace_back
#define mp make_pair
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vlli = vector<lli>;
using vvli = vector<vlli>;
using vs = vector<string>;
using vvs = vector<vs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using ll = long long;
//---------------------------------------------------------------------------------------------------
// vector入力
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (T &x : vec)
    is >> x;
  return is;
}
// vector出力
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec)
{
  // os << '{';
  for (int i = 0; i < vec.size(); i++)
  {
    os << vec[i] << (i + 1 == vec.size() ? "" : "");
  }
  // os << '}';
  return os;
}
// aよりもbが大きいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T &b)
{
  if (a > b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}
//---------------------------------------------------------------------------------------------------
lli a = 0, b = 0, c = 0, h = 0, n = 0, w = 0, ans = 0, count = 0;
string s = "", t = "";
vector<pair<lli, lli>> pr;
map<lli, lli> mp;
set<lli> st;

//---------------------------------------------------------------------------------------------------
lli solve()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> a >> b;
  ans = min(n * a, b);
  return ans;
}

//---------------------------------------------------------------------------------------------------
signed main()
{
  out(solve());
}

Measured memory_bytes: 3640
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

const int mod = 998244353;

template <typename T> struct SegmentTree {
  int SEG_LEN = 1;
  std::vector<T> node;
  SegmentTree(int n) {
    while (SEG_LEN < n) {
      SEG_LEN <<= 1;
    }
    node.assign(SEG_LEN * 2, 0);
  }
  void add(int idx, T v) {
    idx += SEG_LEN;
    node[idx] += v;
    node[idx] %= mod;
    while (true) {
      idx /= 2;
      if (idx == 0) {
        break;
      }
      node[idx] = node[idx * 2] + node[idx * 2 + 1];
      node[idx] %= mod;
    }
  }
  T sum(int l, int r) {
    l += SEG_LEN;
    r += SEG_LEN;
    T ret = 0;
    while (l < r) {
      if (l & 1) {
        ret += node[l++];
        ret %= mod;
      }
      if (r & 1) {
        ret += node[r - 1];
        ret %= mod;
        r--;
      }
      l /= 2;
      r /= 2;
    }
    return ret;
  }
};

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::setprecision(20) << std::fixed;

  int N, K;
  cin >> N >> K;

  vector<int> L(K), R(K);
  for (int i = 0; i < K; i++) {
    cin >> L[i] >> R[i];
  }

  SegmentTree<long long> seg_tree(N + 100);
  vector<long long> dp(N + 100, 0);

  seg_tree.add(0, 1);
  dp[0] = 1;
  for (int i = 1; i <= N; i++) {
    for (int k = 0; k < K; k++) {
      int l = max(0, i - R[k]);
      int r = i - L[k];
      if (r < 0) {
        continue;
      }
      long long s = seg_tree.sum(l, r + 1) % mod;

      dp[i] += (s);
      dp[i] %= mod;
      seg_tree.add(i, s);
    }
  }

  cout << ((dp[N - 1] % mod) + mod) % mod << endl;
  return 0;
}

Measured memory_bytes: 9000
var button =  [
    [],
    ['.',',','!','?',' '],
    ['a','b','c'],
    ['d','e','f'],
    ['g','h','i'],
    ['j','k','l'],
    ['m','n','o'],
    ['p','q','r','s'],
    ['t','u','v'],
    ['w','x','y','z']
]


function Main(input){
    input = input.split("\n");
    var n = parseInt(input[0],10);

    for(var i = 1;i <= n;i++){
        var c,pre = 0,ans = "";
        for(var j = 0;j < input[i].length;j++){
            if(input[i][j] === '0'){
                if(pre != 0)
                    ans += button[parseInt(input[i][j - 1],10)][c];
            }else if(pre == 0){
                c = 0;
            }else{
                c++;
                if(input[i][j] == "1")
                    c %= 5;
                else if(input[i][j] == "7" || input[i][j] == '9')
                    c %= 4;
                else
                    c %= 3;
            }
            pre = parseInt(input[i][j],10);
        }
        console.log(ans);
    }
}
Main(require("fs").readFileSync("/dev/stdin","utf8"));

 

Measured memory_bytes: 16988
#include "bits/stdc++.h"
using namespace std;

#define sz(x) (int)(x.size())
#define FOR(i,L,R) for(int i = L; (L <= R? i <= R : i >= R); (L <= R? i += 1 : i -= 1))
#define int long long

const int N = 2e5 + 2, inf = 1e18;

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

    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            bool yes = true;
            FOR(k,i,j) yes &= s[k] == 'R';
            if(yes) {
                ans = max(ans, j - i + 1);
            }
        }
    }
    cout << ans;
}


Measured memory_bytes: 3644
import math

x = int(input())

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

while True:
    if is_prime(x):
        print(x)
        break
    x += 1

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


int main()
{
  long long N;
  cin >> N;
  
  long long AN[1000001] = { 0 };
  long long T=0;
  for(int n=0; n<N; n++)
  { int A;
    cin >> A;
    T = T + A;
    AN[A] ++;
  }
  
  long long Q;
  cin >> Q;
    
  for(int n=0; n<Q; n++)
  { long long B, C;
    cin >> B >> C;
   
    if(AN[B]!=0)
    {
      long long AB = AN[B];
      AN[B] = 0;
      AN[C] = AN[C] + AB;      
      T = T - AB * B + AB * C;
    }   
    cout << T << endl;      
  }
}


Measured memory_bytes: 11440
n = list(map(int, list(input())))
n = n[::-1] + [0]
d = len(n)

ans = 0
for i, k in enumerate(n):
    if k < 5:
        ans += k
    elif k == 5 and n[i + 1] < 5:
        ans += k
    else:
        ans += 10 - k
        n[i + 1] += 1
print(ans)


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

const int MAX = 200005;
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;
}

int main() {
    int H, W, A, B;
    scanf("%d %d %d %d", &H, &W, &A, &B);
    long long ans = 0;
    COMinit();
    for (int i = 1; i <= H - A; i++) {
        ans += COM(B+i-2, i-1)* COM(W-B-1+H-i, H-i) % MOD;
        ans %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  long double h;
  cin >> h;

  if(h == 1) {
    cout << 1 << endl;
    return 0;
  }

  ll ans = 1;
  ll multi = 2;
  while(true) {
    if(h == (long double)1) break;
    h = floor(h/2);
    ans += multi;
    multi *= 2;
  }

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


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long base = 100;
        long time = 0;
        while (base < x) {
            time++;
            base += base / 100;
        }
        System.out.println(time);
    }
}

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

using namespace std;

int main(void)
{
    int array[5];
    int k;
    for(int i = 0; i<5 ;i++)
        cin >> array[i];
    cin >> k;
    
    bool flag = true;
    for(int i = 0; i < 4; i++){
        for(int j = i+1; j < 5;j++){
            if(k < (array[j] - array[i])){
                flag = false;
                break;
            }
        }
    }
    if(flag) cout << "Yay!" << endl;
    else cout << ":(" << endl;
}

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


int main(){
    ll n;
    cin >> n;
    ll d=1,e;
    for(ll i=2; i*i<=n; i++){
        if(n%i==0){
            d = i;
        }
    }
    e = n/d;
    cout << (d+e-2) << endl;
    

    return 0;
}


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


int main(){
  string S;
  cin >> S;
  if (S=="SUN")
    cout << 7 << endl;
  if (S=="MON")
    cout << 6 << endl;
  if (S=="TUE")
    cout << 5 << endl;
  if (S=="WED")
    cout << 4 << endl;
  if (S=="THU")
    cout << 3 << endl;
  if (S=="FRI")
    cout << 2 << endl;
  if (S=="SAT")
    cout << 1 << endl;
  
}

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

Measured memory_bytes: 572
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using data=pair<ll,ll>;
#define Rep(i,N) for(i=0;i<N;i++)
#define mod 1000000007

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}
 
ll modncr(ll n,ll r){
  ll i,plus=1;
  Rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

int main(){
  ll i,j,N,K,m=0,ans,pl=0,mi=0;
  cin>>N>>K;
  vector<ll> a(N),plus(N,0),minus(N,0);
  Rep(i,N){
    cin>>a[i];
    if(a[i]>0)m+=a[i];
    if(i<K){
      if(i==0){
        if(a[i]>=0){plus[i]=a[i];}
        else{minus[i]=a[i];}
      }else{
        if(a[i]>=0){plus[i]=plus[i-1]+a[i];minus[i]=minus[i-1];}
        else{minus[i]=minus[i-1]+a[i];plus[i]=plus[i-1];}
      }
    }else{
      pl=plus[i-1];mi=minus[i-1];
      if(a[i-K]>=0){pl-=a[i-K];}
      else{mi-=a[i-K];}
      if(a[i]>=0){pl+=a[i];}
      else{mi+=a[i];}
      plus[i]=pl;minus[i]=mi;
      //cout<<pl<<" "<<mi<<endl;
    }
  }
  ans=min(plus[K-1],0-minus[K-1]);
  for(i=K;i<N;i++){
    if(ans>min(plus[i],0-minus[i]))ans=min(plus[i],0-minus[i]);
  }
  cout<< m-ans <<endl;
  return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

const long long N = 1e3 + 17;
ll cnt, lnt, mn = N, mx, a[N], n, m ,k, x , y, z;
pair<ll,ll>pr[N];
vector<ll>v,v2,v3;
map<ll,ll>mp;
bool used[N], t1, t2;
vector<string>sv;

int main()
{
    cin >> n >> m;
    string s;
    cin >> s;
    vector<ll>hi(n);
    for(ll i = 0; i < s.size() - 1; i ++)
    {
        if(s[i] == 'A' and s[i+1] == 'C')
        {
            hi[i+1] = hi[i] + 1;
        }
        else
        {
            hi[i+1] = hi[i];
        }
    }
    for(ll i = 0; i < m; i ++)
    {
        cin >> x >> y;
        cout << hi[y - 1] - hi[x - 1] << endl;
    }
}


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

#define ll long long int
#define db double
#define fl float
#define endl '\n'

#define mod (ll)(1000000007)
#define mod1 (ll)998242353
#define mod2 (ll)998244353
#define PI 3.1415926535897932384626433832795

#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pb push_back
#define pob pop_back

#define Sort(v) sort(v.begin(),v.end())
#define Sortd(v) sort(v.begin(),v.end(),greater<>())

#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,n) for(int i=1;i<n;i++)
#define rf(i,n) for(int i=n-1;i>=0;--i)
#define rf1(i,n) for(int i=n-1;i>=1;--i)
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repn(i,a,b) for(int i=a;i<=b;++i)

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<vi> vvi;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;

//nC2
ll C2(ll n){
    ll ans= max(((n*(n-1))/2),(ll)0);
    return ans;
}
//square
ll sq(ll n){
    return n*n;
}

//GCD
ll gcd(ll a,ll b){
    if(a<b){
        swap(a,b);
    }
    if(b==0){
        return a;
    }    
    else{
        return gcd(b,a%b);
    }
}

//sort pair by second values
bool sortsec(const pair<ll,ll> &a, const pair<ll,ll> &b){ 
    return (a.second < b.second); 
}


//Binary Exponentiation
ll BinExp(ll a, ll b, ll m){
    a%=m;
    ll res =1;
    while(b>0){
        if(b&1){
            res = (res * a)%m;
        }
        a=(a*a)%m;
        b>>=1;
    }
    return res;
}
vi pr(1000007);
int N=1000007;
void sieve(){
    pr[0]=-1;//DNE
    pr[1]=-1;//DNE
    for(int i=2;i<N;++i){
        if(pr[i]==0){
            for(int j=2*i;j<N;j+=i){
                if(pr[j]==0)pr[j]=i;
            }
            pr[i]=i;
        }
    }
}


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

    int n;
    cin>>n;
    int a[n];

    f(i,n){
        cin>>a[i];
    }
    int g=a[0];
    f1(i,n){
        g=gcd(g,a[i]);
    }
    if(g!=1){
        cout<<"not coprime"<<endl;
    }
    else{
        sieve();
        bool flag=0;
        set<int> s;
        int x,f;
        f(i,n){
            x=a[i];
            while(x!=1){
                f=pr[x];
                if(s.count(f)){
                    flag=1;
                    break;
                }
                else{
                    s.insert(f);
                }
                while(x%f==0){
                    x/=f;
                }
            }
            if(flag){
                break;
            }
        }
        if(flag)cout<<"setwise coprime"<<endl;
        else cout<<"pairwise coprime"<<endl;
    }

    


    return 0;
}



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

#define rep(i, b) for(int i = 0; i < b; i++)
#define repi(i, a, b) for(int i = a; i < b; i++)
#define all(c) c.begin(),c.end()
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define MAX_V 1001
#define MAX_E 401
#define INF INT_MAX
#define MOD 1000000007
#define EPS 1e-7
typedef long long ll;
inline int toInt(std::string s) { int v; std::istringstream sin(s); sin >> v; return v; }
template<class T> inline std::string toString(T x) { std::ostringstream sout; sout << x; return sout.str(); }
using namespace std;

typedef double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
#define X real()
#define Y imag()
typedef pair<int, int> pii;

int main()
{
	string s;
	cin >> s;
	int flag = 0;
	rep(i, s.size())
	{
		if (s[i] == 'C')
		{
			flag = 1;
		}
		if (flag == 1 && s[i] == 'F')
		{
			flag = 2;
		}
	}
	if (flag == 2)
	{
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h> 

int main(void)
{
	int x,i;

	for(i=0; i<10000; i++)
	{
		
		scanf("%d",&x);

		if(x==0)
		{
			break;
		}

		printf("Case %d: %d\n",i+1, x);

	}


	return 0;
}

Measured memory_bytes: 592
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

int main(){
    std::ios::sync_with_stdio(false);
    ll a, b;
    cin >> a >> b;
    // f(A, B) = f(1, B) xor f(1, A-1)
    ll ret = 0;
    ll bit_a = 0;
    ll bit_b = 0;
    for(int i=0;i<40;++i)
    {
        
        if(i==0)
        {
            bit_a = ((a-1)%4 == 1 || (a-1)%4 == 2) ? 1 : 0;
            bit_b = (b%4 == 1 || b%4 == 2) ? 1 : 0;
        }
        else
        {
            ll base = 1ll << (i + 1);
            //cerr << base << endl;
            ll remain = (a-1) % base;
            if(remain >= base / 2 && (remain % 2) == 0)
            {
                bit_a |= 1ll << i;
            }

            remain = b % base;
            if(remain >= base / 2 && (remain % 2) == 0)
            {
                bit_b |= 1ll << i;
            }            
        }
        //cerr << bit_a << ' ' << bit_b << endl;
    }

    cout << (bit_a ^ bit_b) << endl;

}

Measured memory_bytes: 384
//F
//

#include <vector>
#include <iostream>
#define INF 100000000000000
long long XOR(std::vector<long long> Stone,int begin,int end);
void chmin(long long& a,long long b);

long long dp[51][2][2];   //前の桁からの繰り下がり有無・繰り上がり有無を踏まえた上での1番山から2番山までの最小の移動個数

int main(){
    int N;
    std::cin >> N;
    std::vector<long long> Stone(N);
    for(int i=0;i<N;i++){
        std::cin >> Stone[i];
    }
    for(int i=0;i<51;i++){
        for(int debt = 0;debt<2;debt++){
            for(int prof = 0;prof<2;prof++){
                dp[i][debt][prof] = INF;
            }
        }
    }
    dp[0][0][0] = 0;

    long long base = XOR(Stone,2,Stone.size()-1);
    long long ll1 = 1;
    for(int i=0;i<51;i++){
        for(int debt=0;debt<2;debt++){
            for(int prof=0;prof<2;prof++){
                int s0 = (Stone[0] & (ll1 << i)) != 0;
                int s1 = (Stone[1] & (ll1 << i)) != 0;
                int b = (base & (ll1 << i)) != 0;

                //前からの繰り上がり・繰り下がりに応じて対象桁の値、次の桁への繰り上がり、繰り下がりを更新
                int debt2=0,prof2=0;
                if (debt){s0 --;}
                if (s0 < 0){debt2 = 1; s0 = 1;}
                if (prof){s1 ++;}
                if (s1 > 1){prof2 = 1; s1 = 0;}

                //1番山から2番山に移動しないケースを計算(s0^s1 == bとならないならそのパターンはアウトなのでINFのまま)
                if((s0^s1) == b) {
                    chmin(dp[i + 1][debt2][prof2], dp[i][debt][prof]);
                }

                //1番山から2番山に移動するケースを計算(s0^s1 == bとならないならそのパターンはアウトなのでINFのまま)
                s0--;
                if(s0<0){debt2 = 1; s0 = 1;}
                s1++;
                if(s1>1){prof2 = 1;s1 = 0;}
                if((s0^s1) == b) {
                    chmin(dp[i + 1][debt2][prof2], dp[i][debt][prof] + (ll1 << i));
                }
            }
        }

    }
    long long ans;
    if(dp[50][0][0] == INF || dp[50][0][0] == Stone[0]) {
        ans = -1;
    }
    else{
        ans = dp[50][0][0];
    }
    std::cout << ans;

    return 0;
}

long long XOR(std::vector<long long> Stone,int begin,int end){
    if(end < begin){
        return 0;
    }
    long long tmp = Stone[begin];
    for(int i=begin + 1;i <= end;i++){
        tmp = tmp^Stone[i];
    }
    return tmp;
}

void chmin(long long& a,long long b){
    if(a>b) a = b;
    return;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define INT(str) stoi((str), 0)
#define INTB(str) stoi((str), 0, 2) // 2進数の文字列を int に

int main() {
  ll H, W;
  cin >> H >> W;
  if (W == 1 || H == 1)
    cout << 1 << endl;
  else
    cout << (H / 2) * (W / 2) + (H%2==0 ? H / 2 : (H / 2 + 1)) * (W%2==0 ? W / 2 : (W / 2 + 1)) << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace abc167_b
{
  class Program
  {
    static void Main(string[] args)
    {
      var A = CIn.ReadInt();
      var B = CIn.ReadInt();
      var C = CIn.ReadInt();
      var K = CIn.ReadInt();

      var a = Math.Min(A, K);
      var b = Math.Min(B, K - a);
      var c = Math.Min(C, K - a - b);

      Console.WriteLine(a - c);
    }
  }

  static class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(int n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(int n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(int n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(int n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }

    public static char[,] ReadCharMatrix(int h, int w)
    {
      var array = new char[h, w];
      for (var i = 0; i < h; i++)
      {
        var l = Console.ReadLine().ToCharArray();
        for (var j = 0; j < w; j++)
        {
          array[i, j] = l[j];
        }
      }
      return array;
    }
  }
}


Measured memory_bytes: 27924
#include<bits/stdc++.h>
using namespace std;
#define IO {ios_base::sync_with_stdio(false); cin.tie(0);}
#define ll long long
#define pi pair<ll,ll>
ll a[600008];
string s, s1;
map<ll, ll>mp;

ll f(ll n, ll b, ll mod)
{
    ll ans=1, aa;
    if(!b) return 1;
    if(b%2) ans=n;
    aa=f(n,b/2,mod); return ((aa*aa)%mod * ans)%mod;
}
int main()
{
    IO;
    ll i, j, k=0, l, n, m, t, h, cnt=0, curr, mx, mod=1e9+7;
    cin>>n>>m; a[0]=1;
    for(i=1; i<=m; i++) a[i]=(a[i-1]*i)%mod;
    l=1;
    for(i=0; i<=n; i++){
        j = ((a[n-i]*a[i])%mod*a[m-n])%mod;
        j = f(j,mod-2,mod); j = ((j*a[n])%mod*a[m-i])%mod; k=(k+l*j)%mod; l*=-1;
    }
    j = f(a[m-n],mod-2,mod); j =(j*a[m])%mod; j = (j*k)%mod;
    cout<<(j+mod)%mod<<endl;
    return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

vector<pair<char, ll>> RLE(const string &S) {
    ll cnt = 0;
    vector<pair<char, ll>> res;
    for (ll i = 0; i < (ll) S.size(); i++) {
        cnt++;
        if (i == (ll) S.size() - 1) {
            res.emplace_back(S[i], cnt);
            break;
        }
        if (S[i] != S[i + 1]) {
            res.emplace_back(S[i], cnt);
            cnt = 0;
        }
    }
    return res;
}

void Main() {
    string S; cin >> S;
    cout << RLE(S).size() - 1 << endl;
}

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


Measured memory_bytes: 5552
#include<bits/stdc++.h>
using namespace std;
int n,m;
int d[1000];
int c[1000];
int memo[1000][1000];
int dfs(int day,int tosi);
int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++) cin>>d[i];
  for(int i=0;i<m;i++) cin>>c[i];
  memset(memo,-1,sizeof(memo));
  cout<<dfs(0,0)<<endl;
  return 0;
}

int dfs(int day,int tosi){
  if(tosi==n){
    return 0;
  }else if(day==m){
    return (1<<30);
  }
  if(memo[day][tosi]!=-1) return memo[day][tosi];
  
  return memo[day][tosi]=min(dfs(day+1,tosi),dfs(day+1,tosi+1)+d[tosi]*c[day]);
}

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

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

using namespace std;

int main () {
	string s; cin >> s;
	if (s[0] == 'a') cout << "vowel" << '\n';
	else if (s[0] == 'i') cout << "vowel" << '\n';
	else if (s[0] == 'u') cout << "vowel" << '\n';
	else if (s[0] == 'e') cout << "vowel" << '\n';
	else if (s[0] == 'o') cout << "vowel" << '\n';
	else cout << "consonant" << '\n'; 

	return 0;

}

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

// Begin {{{
using namespace std;
#define all(x) x.begin(), x.end()
#define rep(i, n) for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, b, e) for (i64 i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (i64 i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T> using MaxHeap = priority_queue<T>;
template <class T> using MinHeap = priority_queue<T, vector<T>, greater<>>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
inline i64 sigma(i64 n) { return n * (1 + n) >> 1; }
inline i64 updiv(i64 n, i64 d) { return (n + d - 1) / d; }
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;
#ifndef DEBUG
#define dump(...)
#endif

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

inline void outs() { cout << "\n"; }
template <class Head, class... Tail>
inline void outs(Head&& head, Tail&&... tail) {
    cout << head << (sizeof...(tail) ? " " : "");
    outs(forward<Tail>(tail)...);
}

template <class T>
inline void outs(vector<T> &vec) { for (auto &e : vec) cout << e << " \n"[&e == &vec.back()]; }

template <class T>
inline void outs(vector<vector<T>> &df) { for (auto &vec : df) outs(vec); }

inline void outl() { cout << "\n"; }
template <class Head, class... Tail>
inline void outl(Head&& head, Tail&&... tail) {
    cout << head << (sizeof...(tail) ? "\n" : "");
    outl(forward<Tail>(tail)...);
}

template <class T>
inline void outl(vector<T> &vec) { for (auto &e : vec) cout << e << "\n"; }

inline void outn() {}
template <class Head, class... Tail>
inline void outn(Head&& head, Tail&&... tail) {
    cout << head;
    outn(forward<Tail>(tail)...);
}

template <class T>
inline void outn(vector<T> &vec) { for (auto &e : vec) cout << e; }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}
// }}} End

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    var(size_t, N);
    vector<i64> l(N);
    rep(i, N) {
        input(l[i]);
    }
    sort(all(l));
    i64 res = 0;
    for (size_t i = 0; i < N; ++i) {
        i64 a = l[i];
        for (size_t j = i + 1; j < N; ++j) {
            i64 b = l[j];
            for (size_t k = j + 1; k < N; ++k) {
                i64 c = l[k];
                if (a < b + c && b < c + a && c < a + b) {
                    ++res;
                } else {
                    break;
                }
            }
        }
    }
    outl(res);
    return 0;
}


Measured memory_bytes: 256