akhauriyash/Code-Regression huggingface dataset:
/****************### With The name of ALLAH, most Gracious, most Compassionate ###****************/

/**============================================================================**\
|   Author      : Md Jubayer Hossen Jame
|   Study       : CSE, BRUR
|   Today       : Sunday, 13 September, 2020
|   Source      : AtCoder Online Judge
|   Problem link: https://atcoder.jp/contests/abc178/tasks/abc178_b
|   Algorithm   :

    After about 2 years latter ---> see you again
|
\**============================================================================**/

#include "bits/stdc++.h"
using namespace std;

#define FI                    freopen("input.txt", "r", stdin)
#define FO                    freopen("output.txt", "w", stdout)
#define FasterIO              ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

typedef long long             ll;
typedef unsigned long long    ull;
typedef unsigned int          ui;

#define mem(x,y)              memset(x,y,sizeof(x));
#define pii                   pair<int,int>
#define mk                    make_pair
#define ff                    first
#define ss                    second
#define pb                    push_back
#define ppb                   pop_back
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define for0(i, n)            for (int i = 0; i < (int)(n); ++i)
#define endl                  '\n'

const double PI = acos(-1.0);

#define gcd(a,b)              __gcd(a,b)
#define lcm(a,b)              (a*(b/gcd(a,b)))

///Direction Array
// 4 Direction - DOWN, UP, RIGHT, LEFT
int dx4[]= {+1, -1, +0, +0};
int dy4[]= {+0, +0, +1, -1};
#define isValid(a, b, R, C)   (0 <= a && a < R) && (0 <= b && b < C)
int dx8[]= {+0, +0, +1, -1, -1, +1, -1, +1};
int dy8[]= {-1, +1, +0, +0, +1, +1, -1, -1};

///Knight Moves
int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2};
int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};
/**************************************************************************************************/

void test_case()
{
    bool x;
    cin >> x;
    cout << !x << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
    //FI;
    //FO;
#endif // ONLINE_JUDGE
    //FasterIO

    int T = 1;
    //cin >> T;
    for(int tc = 1; tc <= T; ++tc)
    {
        //cout << "Case #" << tc << ":" << endl;
        test_case();
    }
    return 0;
}


Measured memory_bytes: 3560
//go:generate echo "https://atcoder.jp/contests/dp/tasks/dp_c"
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
)

type scanner struct{ *bufio.Scanner }

func newScanner(r io.Reader) *scanner {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	s.Buffer(nil, 100000000)
	return &scanner{s}
}

func (s *scanner) Int() int {
	s.Scan()
	n, _ := strconv.Atoi(s.Text())
	return n
}

func (s *scanner) IntSlice(l int) []int {
	if l == 0 {
		return []int{}
	}
	sl := make([]int, l, l)
	for i := range sl {
		sl[i] = s.Int()
	}
	return sl
}

func (s *scanner) IntSlice2(l, n int) []int {
	if l == 0 {
		return []int{}
	}
	sl := make([]int, l, l)
	for i := 0; i < n; i++ {
		sl[i] = s.Int()
	}
	return sl
}

func solve(n int, u [][]int) int {
	t := make([][]int, n+1, n+1)
	for i := range t {
		t[i] = make([]int, 3, 3)
	}
	t[0] = u[0]
	for d := 0; d < n; d++ {
		for sel := 0; sel <= 2; sel++ {
			for k := range u[d] {
				if k == sel {
					continue
				}
				if v := t[d][sel] + u[d+1][k]; t[d+1][k] < v {
					t[d+1][k] = v
				}
			}
		}
	}
	max := math.MinInt64
	for _, v := range t[n-1] {
		if max < v {
			max = v
		}
	}
	return max
}

func main() {
	scan := newScanner(os.Stdin)
	n := scan.Int()
	u := make([][]int, n+1, n+1)
	for i := 0; i <= n; i++ {
		u[i] = []int{scan.Int(), scan.Int(), scan.Int()}
	}
	fmt.Println(solve(n, u))
}


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

int gcd (int x, int y){
    if (y == 0) return x;
    return gcd (y, x % y);
}
int main(){
    int n;
    cin >> n;
    int x;
    int ans = 0;
    for (int i = 0; i < n; i++){
        cin >> x;
        ans = gcd(x, ans);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
ll X, Y, Z, K;
vector<ll> a, b, c;
vector<ll> ans;
bool solve(ll T, bool sp) {
  int cnt = 0;
  rep(i, X) {
    rep(j, Y) {
      rep(k, Z) {
        if(a[i]+b[j]+c[k]<T) break;
        if(sp) ans.emplace_back(a[i]+b[j]+c[k]);
        cnt++;
        if(!sp && cnt >= K) return true;
      }
    }
  }
  return false;
}
int main() {
  cin >> X >> Y >> Z >> K;
  a.resize(X);b.resize(Y);c.resize(Z);
  rep(i, X) cin >> a[i];
  rep(i, Y) cin >> b[i];
  rep(i, Z) cin >> c[i];
  sort(a.rbegin(), a.rend());
  sort(b.rbegin(), b.rend());
  sort(c.rbegin(), c.rend());
  ll front = 0;
  ll back = 30000000000;
  while(front != back) {
    ll half = (back + front) / 2;
    if(back == front+1) {
      back = front;
    }
    else if(solve(half, false)) front = half;
    else back = half - 1;
  }
  solve(front, true);
  sort(ans.rbegin(), ans.rend());
  rep(i, K) cout << ans[i] << endl;
  return 0;
}


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

int main(){
	int N;
	cin >> N;
	ll ans = (ll)N*(ll)(N-1)/2;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+20;
struct edge { int ver,next; } e[N<<1];
int n,m,q,t,Head[N],ans[N],v[N],d[N],c[N],dis[N];
inline void insert(int x,int y) { e[++t] = (edge){y,Head[x]} , Head[x] = t; }
inline void input(void)
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        insert( u , v );
        insert( v , u );
    }
    scanf("%d",&q);
    for (int i=1;i<=q;i++)
        scanf("%d%d%d",&v[i],&d[i],&c[i]);
}
inline void dfs(int x,int d,int col)
{
    if ( !ans[x] ) ans[x] = col;
    if ( !d || dis[x] >= d ) return void();
    dis[x] = d;
    for (int i=Head[x];i;i=e[i].next)
    {
        int y = e[i].ver;
        dfs( y , d-1 , col );
    }
}
int main(void)
{
    input();
    for (int i=q;i>=1;i--)
        dfs( v[i] , d[i] , c[i] );
    for (int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}


Measured memory_bytes: 4608
import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.StdIn._
object Main extends App{


  val n = readInt()
  val tasks = List.tabulate(n){_ ⇒
    val Array(a, b) = readLine.trim.split(' ').map(_.toLong)
    Task(a, b)
  }.sortBy(_.limit)
  println(if (canDo(tasks, 0)) "Yes" else "No")
  @tailrec def canDo(tasks: List[Task], currentTime: Long): Boolean = {
    tasks match {
      case Nil ⇒ true
      case h::t if h.limit >= currentTime + h.cost => canDo(t, currentTime + h.cost)
      case _ ⇒ false
    }
  }
  case class Task(cost: Long, limit: Long)

}


Measured memory_bytes: 130312
n, m = map(int, input().split())
array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x:x[1])

deleted_bridges = [array[0][1]-1]
for rule in array:
    bridge_flag = True
    for bridge in deleted_bridges:
        if rule[0] <= bridge < rule[1]:
            bridge_flag = False
            break
    if bridge_flag:
        deleted_bridges.append(rule[1]-1)

print(len(deleted_bridges))

Measured memory_bytes: 23588
#include<math.h>
#include<iostream>
#include <algorithm>
#include <string>
#include<vector>
#include <array>
#include<tuple>
#include<queue>
#include<stack>
#include<iomanip>
#include<bitset>
//AtCoderC++.cpp

using namespace std;

vector<long long> comb = vector<long long>(100 * 100,-1);

long long combination(long long n, long long r) {
	if (n == 1 || n == 0)return 1;
	if (n == r)	return 1;
	else if (r == 0)return 1;
	else if (r == 1)return n;
	else if (comb[100 * (n - 1) + (r - 1)] != -1) return comb[100 * (n - 1) + (r - 1)];
	else {
		auto res = combination(n - 1, r - 1) + combination(n - 1, r);
		comb[100 * (n - 1) + (r - 1)] = res;
		return res;
	}
}


int main() {
	string A, B; cin >> A >> B;
	if (A.length() > B.length()) {
		cout << "GREATER" << endl;
		return 0;
	}
	if (A.length() < B.length()) {
		cout << "LESS" << endl;
		return 0;
	}
	for (size_t i = 0; i < A.length(); i++) {
		if (A[i] < B[i]) {
			cout << "LESS" << endl;
			return 0;
		}
		if (A[i] > B[i]) {
			cout << "GREATER" << endl;
			return 0;
		}
	}
	cout << "EQUAL" << endl;
}


Measured memory_bytes: 384
# coding: utf-8
# Your code here!


#n = int(input())
#s = input()
#a = [int(i) for i in input().split()]
#m = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行


n = int(input())
w = [int(i) for i in input().split()]


ans = 10**9
for i in range(n):
    ans = min(ans, abs(sum(w[:i]) - sum(w[i:])))
    

print(ans)


Measured memory_bytes: 2940
#include<stdio.h>
int main(void){
  int n,k,i,j,temp,sum=0;
  int l[50];
  scanf("%d %d",&n,&k);
  for(i=0;i<n;i++)
    scanf("%d",&l[i]);
  for(i=0;i<n-1;i++){
    for(j=i+1;j<n;j++){
      if(l[i]<l[j]){
        temp=l[i];
        l[i]=l[j];
        l[j]=temp;
      }
    }
  }
  for(i=0;i<k;i++)
    sum+=l[i];
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 128
n = int(input())
s = input()
t = input()
for i in range(n):
  cnt = 0
  for j in range(i, n):
    if s[j] != t[j-i]:
      break
    cnt += 1
  if cnt == n-i:
    ans = n+i
    break
if cnt == 0:
  ans = 2*n
print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  ll K;
  cin>>K;
  ll tmp = 7;
  ll ten = 1;
  int ans = -1;
  for(ll i=1;i<10000000;++i) {
    ten *= 10;
    ten %= K;
    if(tmp%K==0) {
      ans = i;
      break;
    }
    tmp += 7*ten;
    tmp %= K;
  }
  cout<<ans<<endl;
}



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

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

void flag2func(bool flag){flag ? cout<<"Yes"<<endl : cout<<"No"<<endl;}

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  int a[3][3];rep(i,3)rep(j,3)cin>>a[i][j];
  vector<vector<bool>> b(3,vector<bool>(3,false));
  //vector<vector<int>> vec(n_rows, vector<int>(n_cols, value));
  int n,c;cin>>n;
  rep(i,n){
    cin>>c;
    rep(j,3){
      rep(k,3){
        if(a[j][k]==c){b[j][k]=true;}
      }
    }
  }
  bool flag=false;
  int cnt;
  rep(i,3){
    cnt=0;
    rep(j,3){
      if(b[i][j]==true)cnt++;
    }
    if(cnt==3){flag=true;break;}
  }
  for(int i=0;i<3 && flag==false;i++){
    cnt=0;
    for(int j=0;j<3;j++){
      if(b[j][i]==true)cnt++;
    }
    if(cnt==3){flag=true;break;}
  }
  if(b[0][0]==true &&b[1][1]==true &&b[2][2]==true&&flag==false)flag=true;
  if(b[0][2]==true &&b[1][1]==true &&b[2][0]==true&&flag==false)flag=true;
  flag2func(flag);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef string str;
static const long long INF = INT64_MAX;
static const long long MOD = (ll)1e9+7;

#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define REP(i, n) for(ll i=0;i<n;i++)
#define SZ(v) (ll)((v).size())
#define WHOLE(v) (v).begin(), (v).end()
#define ASC(v) sort((v).begin(), (v).end())
#define DESC(v) sort((v).rbegin(), (v).rend())
#define INV(v) reverse((v).begin(), (v).end())
#define FOLDL(src, dst, lambda) partial_sum((src).begin(), (src).end(), (dst).begin(), lambda)
#define FOLDR(src, dst, lambda) INV(src);partial_sum((src).begin(), (src).end(), (dst).begin(), lambda);INV(dst)
#define CUMSUML(src, dst) FOLDL(src, dst, [](auto a, auto b) {return a+b;})
#define CUMSUMR(src, dst) FOLDR(src, dst, [](auto a, auto b) {return a+b;})
#define ACCUM(v, d0, lambda) accumulate((v).begin(), (v).end(), d0, lambda)
#define SUM(v, d0) ACCUM(v, d0, [](auto a, auto b) {return a+b;})
#define ERASE(v, i) v.erase(v.begin() + i)
#define UNIQ(v) ASC(v);v.erase(unique(v.begin(), v.end()), v.end())

template <typename T>void debug(T t) {cerr << t << endl;}
template <typename T, typename ...Args>void debug(T t, Args ...args) {cerr << t << " ";debug(args...);}
template <typename T>void out(T t) {cout << t << endl;}
template <typename T, typename ...Args>void out(T t, Args ...args) {cout << t << " ";out(args...);}

ll gcd(ll a, ll b){if (a < b){a ^= b;b ^= a;a ^= b;}return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


void solve() {
    ll N, M;
    cin >> N >> M;
    str S, T;
    cin >> S >> T;
    ll g = gcd(N, M);
    REP(i, g) {
        if(S[i*N/g] != T[i*M/g]) {
            out(-1);
            return;
        }
    }
    out(lcm(N, M));
}

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


Measured memory_bytes: 640
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  ll H, N;
  cin>>H>>N;
  ll sum = 0;
  ll A;
  for(int i=0;i<N;++i) {
    cin>>A;
    sum += A;
  }
  if(H<=sum) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}



Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef std::pair<int,int> pair2;
typedef std::pair<int,pair2> pair3;
const ll INF = 1LL<<60;

int main(){
int N[32]={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};
int a;
  cin>>a;
  
cout<<N[a-1]<<endl;
  
  
}


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

int main() {
  int x_1,y_1,x_2,y_2;
  cin >> x_1 >> y_1 >> x_2 >> y_2;
  int dx=x_2-x_1,dy=y_2-y_1;
  cout << x_2-dy << " " << y_2+dx << " " << x_2-dy-dx << " " << y_2+dx-dy << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)
	len := len(s)
	min := 0
	for i := 0; i < len; i++ {
		if string(s[i]) == "A" {
			min = i
			break
		}
	}

	max := len - 1
	for i := len - 1; i >= 0; i-- {
		if string(s[i]) == "Z" {
			max = i + 1
			break
		}
	}

	fmt.Println(max - min)
}


Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define FILL(a, b) memset(a, b, sizeof(a))

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    for (auto& x : s)
        x = 'x';
    cout << s;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }

        int[] ans = solve(N, A);
        for (int i=0; i<N; i++) {
            if (i != 0) System.out.print(" ");
            System.out.print(ans[i]);
        }
        System.out.println();

    }

    private static int[] solve(int N, int[] A) {
        int[] ans = new int[N];
        int max = A[0];
        for (int i=0; i<N; i++) {
            max = Math.max(max, A[i]);
        }

        int keta;
        for (keta=1; ; keta++) {
            if (max < Math.pow(2, keta)) {
                break;
            }
        }
        int[] count = new int[keta];
        for (int i=0; i<N; i++) {
            int a = A[i];

            for (int idx=0; a>0; idx++) {
                count[idx] += a%2;
                a /= 2;
            }
        }

        /*
        for (int i=0; i<count.length; i++) {
            System.err.println(count[i]);
        }
         */

        for (int i=0; i<N; i++) {
            int a = A[i];
            int val = 1;

            for(int k=0; k<keta; k++) {
                if(count[k]%2 == 0 && a%2 == 1 || count[k]%2 == 1 && a%2 == 0) {
                    ans[i] += val;
                }
                val *= 2;
                a /= 2;
            }
        }

        return ans;
    }
}

Measured memory_bytes: 61312
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll x;
  cin>>x;
  vector<ll>a;
  rep(i,1e6){
    a.push_back((ll)i*(i+1)/2);
  }
  //rep(i,10)cout<<a[i]<<endl;
  int res=(lower_bound(all(a),x)-a.begin());
  cout<<res<<endl;


  return 0;

}


Measured memory_bytes: 10604
#include<bits/stdc++.h>
using namespace std;
int main(){
  int t;
  t=1;
  while(t--){
     long long int a,b,k;
     cin>>a>>b>>k;
     vector<long long int> arr(a);
     vector<long long int> brr(b);
     for(int i=0;i<a;i++){
     	cin>>arr[i];
	 }
	 for(int j=0;j<b;j++){
	 	cin>>brr[j];
	 }
	 vector<long long int> temp;
	 vector<long long int> temp2;
	 long long int sum=arr[0];
	 long long int h=0;
	 while(sum<=k&&h<a){
	 	temp.push_back(sum);
	 	h++;
	 	sum+=arr[h];
	 }
	 sum=brr[0];
	 h=0;
	 while(sum<=k&&h<b){
	 	temp2.push_back(sum);
	 	h++;
	 	sum+=brr[h];
	 }
	 long long int ans=0;
	 long long int j=temp.size();
	 ans=max(ans,j);
	 j=temp2.size();
	 ans=max(ans,j);
	 for(long long int i=0;i<temp.size();i++){
	 	sum=k-temp[i];
	 	long long int index=upper_bound(temp2.begin(),temp2.end(),sum)-temp2.begin();
		ans=max(ans,i+1+index);
	 }
	 cout<<ans<<"\n";
  }
 
   return 0;
}

Measured memory_bytes: 11040
k = int(input())
if k % 2 == 0:
    print(-1)
    exit()
modk = 7 % k
num = 0
for i in range(1,10**8):
    num = (num+modk)%k
    if num == 0:
        print(i)
        exit()
    modk = (modk * 10)%k
print(-1)

Measured memory_bytes: 63312
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=(int)1000000007;
int fac[200005];
int n,m,a,b;
int binpow(int a, int b)
{
	if(!b) return 1;
	int t=binpow(a, b/2);
	if(b%2) return t*t%MOD*a%MOD;
	else return t*t%MOD;
}
int inv(int x)
{
	return binpow(x, MOD-2);
}
int calc(int x, int y)
{
//	cout<<x<<" "<<y<<" "<<fac[x+y-2]<<" "<<fac[x-1]<<" "<<fac[y-1]<<endl;
	return fac[x+y-2]*inv(fac[x-1])%MOD*inv(fac[y-1])%MOD;
}
signed main()
{
	for(int i=0; i<200005; i++)
	{
		if(i==0) fac[i]=1;
		else fac[i]=fac[i-1]*i%MOD;
	}
	cin>>n>>m>>a>>b;
	int x=n-a, y=b+1, ans=0;
	while(x>0 and y<=m)
	{
//		cout<<x<<" "<<y<<endl;
		ans=(ans+calc(x, y)*calc(n-x+1, m-y+1)%MOD)%MOD;
		x--;
		y++;
	}
	cout<<ans;
}


Measured memory_bytes: 5204
H,W, M = map(int, input().split())
HW = [[int(i) - 1 for i in input().split()] for _ in range(M)]

from collections import defaultdict

S = defaultdict(bool)
Hcnt = [0] * H
Wcnt = [0] * W
for h, w in HW:
    S[(h, w)] = True
    Hcnt[h] += 1
    Wcnt[w] += 1

# Hを先に決めるver
ans = 0
Hmax = max(Hcnt)
Wmax= max(Wcnt)
Hidx = []
Widx = []
for i,h in enumerate(Hcnt):
    if Hmax == h:
        Hidx.append(i)
for j,w in enumerate(Wcnt):
    if Wmax == w:
        Widx.append(j)

for i in Hidx:
    for j in Widx:
        if S[(i, j)]:
            ans = Hmax + Wmax - 1
        else:
            ans = Hmax + Wmax
            print(ans)
            exit()

print(ans)

Measured memory_bytes: 174060
import java.util.*;
import java.io.*;
public class Main{
  public static void main(String [] args){

	Scanner sc=new Scanner(System.in);
	int a=sc.nextInt();
	int b=sc.nextInt();
	if(a>b){
		System.out.println("safe");
	}
	else{
		System.out.println("unsafe");
	}

  }

}

Measured memory_bytes: 27084
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 
const static int tx[] = {0,1,0,-1};
const static int ty[] = {-1,0,1,0};
 
static const double EPS = 1e-8;

int main(){
  int col_num,row_num;
  int col[32],row[32];
  int freq[32];
  
  while(~scanf("%d %d",&col_num,&row_num)){
    if(col_num == 0 && row_num == 0) break;

    memset(col,0,sizeof(col));
    memset(row,0,sizeof(row));
    memset(freq,0,sizeof(freq));

    int total = 0;
    for(int i=0;i<col_num;i++){
      int num;
      scanf("%d",col+i);
      freq[col[i]]++;
      total += col[i];
    }

    for(int i=0;i<row_num;i++){
      scanf("%d",row+i);
      if(freq[row[i]]>0) {
	freq[row[i]]--;
	continue;
      }
      else{
	total += row[i];
      }
    }
    
    printf("%d\n",total);
  }
}

Measured memory_bytes: 1188
from collections import defaultdict
from string import ascii_uppercase
import sys, bisect
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

arr = sorted([read_int()[0] for _ in range(5)])
k = read_int()[0]

if __name__ == "__main__":
    if arr[4] - arr[0] > k:
        print(":(")
    else:
        print("Yay!")


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

int main()
    {
    int n;
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
       for(int j=1;j<=n;j++)
       {
           for(int k=1;k<=n;k++)
           {
              sum+=__gcd(i,__gcd(j,k));
           }
       }
    }
    cout<<sum;
    return 0;
    
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
const int AX = 1e3+66;
int vis[AX][AX];
int res[AX][AX];
int main(){
	int n , m , t,  p;
	while ( scanf("%d%d%d%d",&n,&m,&t,&p) && n && m && t && p ){
		memset( vis , 0 , sizeof(vis) );
		for( int i = 0 ; i < m ; i++ ){
			for( int j = 0 ; j < n ; j++ ){
				vis[i][j] = 1;
			}
		}
		int left = 0 ;
		int down = 0 ;
		int x , y ;  
		int op;
		for( int i = 0 ;  i < t ;i ++ ){
			//cout << "?? : " << vis[3][4] << endl;
			scanf("%d%d",&op,&x);
			if( op == 2 ){
				down += x  ;
				int s = 0 ;
				m = max( m , down + x );
				for( int k = down ; k < down + x ; k++ ){
					s ++;
					for( int j = left ; j < n ; j++ ){
						vis[k][j] += vis[down-s][j];
					}
				}
			}else{
				left += x  ;
				int s = 0;
				n = max( n , left + x );
				for( int j = left ; j < left + x ; j++ ){
					s ++;
					for( int k = down ; k < m ; k++ ){
						vis[k][j] += vis[k][left-s];
					}
				}
			}
		}

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

			printf("%d\n",vis[y+down][x+left]);
		}
	}
	return 0 ;
}



Measured memory_bytes: 7624
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

#define NMAX 1000000

signed main(){   

    vector<int> A;
    int N;

    cin>>N;

    for(int i=0;i<N;i++){
        int in;
        cin>>in;
        A.push_back(in);
    }

    sort(A.begin(),A.end());

    int tbl[NMAX+1]={0};
    int ans=0;
    for(int i=0;i<A.size();i++){
        if(tbl[A[i]]==0){
            if(i==A.size()-1||A[i]!=A[i+1]){
                ans++;
            }
            for(int j=A[i];j<=NMAX;j+=A[i]){
                tbl[j]=1;
            }
        }
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 12344
/*
https://t.me/unstoppabIesoIvemachinechannel
*/
#pragma ARCENIY_KIRILLOV_POVELITEL_KROKODILOV
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC push_options
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC pop_options
//#pragma GCC target("popcnt")
//#pragma GCC target("sse4")
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rng(a) a.begin(),a.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for (int i = 0; i < n; i++)
#define per(i, n) for (int i = n - 1; i > -1; i--)
#define rer(i, x, n) for (int i = x; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef long double ld;







ll gcd(ll a, ll b){
    if (b == 0)
        return a;
    return gcd (b, a % b);
}



signed main(){
    int t;
    cin >> t;
    while(t--){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        ll g = gcd(b, d);
        if (b > a || b > d){
            cout << "No" << '\n';
            continue;
        }
        if (c >= b){
            cout << "Yes" << '\n';
            continue;
        }
        ll ost = a%g;
        if (b/g > c/g + 1){
            cout << "No" << '\n';
            continue;
        }
        ll osta = c%g;
        if ( (osta < ost) ){
            cout << "No" << '\n';
        }else cout << "Yes" << '\n';
    }




}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
typedef long long ll;
int main(){
	int n;
	int a;
	cin >> n;
	vector<int> v;
	rep(i,2*n){
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	int cnt =0;
	for(int i=1;i<2*n;i+=2){
		cnt += v[i];
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 384
from collections import deque

def bfs(maze, dist, sy, sx):
    queue = deque([[sy, sx]])
    dist[sy][sx] = 0
    md = 0
    l = []
    while queue:
        y,x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x]=="." and dist[new_y][new_x]==-1:
                    dist[new_y][new_x] = dist[y][x] + 1
                    queue.append([new_y, new_x])
                    md=max(dist[new_y][new_x],md)
    return md

H, W=map(int, input().split())
maze=[input() for i in range(H)]

ans=0
for i in range(H):
  for j in range(W):
    dist=[[-1]*W for j in range(H)]
    if maze[i][j]!='#':
      a=bfs(maze,dist,i,j)
      ans=max(a,ans)
print(ans)


Measured memory_bytes: 3316
#include <iostream>

using namespace std;

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

    if(a == 1){
        a = 14;
    }
    if(b == 1){
        b = 14;
    }

    if(a > b){
        cout << "Alice" << endl;
    }else if(b > a){
        cout << "Bob" << endl;
    }else{
        cout << "Draw" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int N,M,C;
int B[21];
int A[21][21];
int cnt=0;
int main(){
    cin >>N >>M >>C;
    for (int i=0;i<M;i++)cin >>B[i];
    for(int i=0;i<N;i++){
        for (int j=0;j<M;j++){
            cin >>A[i][j];
        }
    }
    

   for(int i=0;i<N;i++){
       int expr=0;
       for(int j=0;j<M;j++){
           expr+=A[i][j]*B[j];
       }
       if(expr>-1*C)cnt++;
   }   
    cout <<cnt <<endl;
}

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

int main(){
	double N;
	cin >> N;
	for(int n=1;n<=N;n++){
		int cnt = 0;
		for(int x=1;x<sqrt(n);x++){
			for(int y=1;y<sqrt(n);y++){
				double D = sqrt(pow(x+y,2) - 4*(pow(x,2)+pow(y,2)+x*y-n));
				double ans = (-(x+y)+D) / 2;
				if(floor(ans) == ans & ans > 0){
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
}


Measured memory_bytes: 3184
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>


using namespace std;
using ll = long long;

string str;

ll ans = 0;

int main() {
	cin >> str;
	while (true) {
		str.erase(str.end() - 1);
		ll len = str.size();
		if (len % 2 == 0) {
			if (str.substr(0, len / 2) == str.substr(len / 2, len / 2)) {
				cout << len << endl;
				return 0;
			}
		}
	}
	return 0;
}

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

int main() {
  int N, A, B, op, count = 0;
  
  cin >> N >> A >> B;

  for (int i = 1; i < N+1; i++) {
    op = i % 10;
    for (int j = 1; j < 5; j++) {
      op = op + (int(i/pow(10, j)) % 10);
    }
    if (A <= op && op <= B){
      count = count + i;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
 
int main(void){
  int i,p;
  scanf("%d",&i);
  while(i>=1000){
   i=i-1000;}
  if(i==0){
    printf("0");}else{
  p=1000-i;
  printf("%d",p);}
  return 0;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

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

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	llong N;
	string s, t;

	cin >> N >> s >> t;
	vector<vector<llong> > rui(N+1, vector<llong>(26,0));
	for(int i = 1; i <= N; i++){
		for(int j = 0; j < 26; j++){
			rui[i][j] = rui[i-1][j];
			if(s[i-1] == 'a'+j)
				rui[i][j]++;
		}
	}

	vector<llong> dp(26, 0);
	dp[s[0]-'a']++;
	llong ans = 0;
	for(int i = 1; i < N; i++){
		ans = dp[t[i]-'a'] % mod;
		dp[s[i]-'a'] = (dp[s[i]-'a'] + dp[t[i]-'a']) % mod;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 27448
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (a <= b) {
            if (a + w >= b) {
                System.out.println(0);
            } else {
                System.out.println( b - (a+w));
            }
        } else {
            if (b + w >= a) {
                System.out.println(0);
            } else {
                System.out.println(a - (b+w));
            }
        }
    }
}

Measured memory_bytes: 21716
s = input()

ret = 0
g, p = 0, 0
for s_ in s :
    if s_ == 'g' :
        if p < g :
            p += 1
            ret += 1
        else :
            g += 1
    else :
        if p < g :
            p += 1
        else :
            g += 1
            ret -= 1
            
print(ret)

Measured memory_bytes: 39792
a, b, c = map(int, input().split())

if a == b and b == c:
    print(1)
elif a == b and b != c:
    print(2)
elif a != b and b == c:
    print(2)
elif a == c and a != b:
    print(2)
elif a != b and b != c:
    print(3)

Measured memory_bytes: 9052
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int,int> pii;
int dr[] = {1,0,-1,0};
int dc[] = {0,1,0,-1};
queue<pii> q;
int h, w;
char grid[1005][1005];
int dist[1005][1005];
inline bool inside(int r, int c){
  return 1 <= r && r <= h && 1 <= c && c <= w;
}
int main(){
  memset(dist, 0x3f,sizeof(dist));
  cin >> h >> w;
  for (int i = 1; i <= h; i++){
    cin >> (grid[i] + 1);
    for (int j = 1; j <= w; j++)
      if (grid[i][j] == '#'){
        q.push(make_pair(i, j));
        dist[i][j] = 0;
      }
  }
  while (!q.empty()){
    pii u = q.front(); q.pop();
    for (int i = 0, x, y; i < 4; i++){
      x = u.first, y = u.second;
      x += dr[i], y += dc[i];
      if (inside(x, y) && dist[x][y] > dist[u.first][u.second] + 1){
        dist[x][y] = dist[u.first][u.second] + 1;
        q.emplace(x, y);
      }
    }
  }
  int mx = 0;
  for (int i = 1; i <= h; i++)
    for (int j = 1; j <= w; j++)
      mx = max(mx, dist[i][j]);
  cout << mx << '\n';
  return 0;
}


Measured memory_bytes: 13328
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
a = factorization(n)
# print(a)

i = 0
count = 1
allcount = 0

while n > 1:
    if a[i][1] >= count:
        n /= a[i][0]
        a[i][1] -= count
        count += 1
        allcount += 1
    else:
        i += 1
        count = 1
    if i >= len(a):
        break

print(allcount)

Measured memory_bytes: 9508
#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>;
using Graph = vector<vector<int>>;

int main() {
    int n,k,sum, a[200005],b[200005];
    cin >> n >> k;
    rep(i,n) cin >> a[i];
    if(k>50){
        rep(i,n){
			cout << n << " \n"[i == n - 1];
		}
		return 0;
    }else{
        rep(i,k){
            memset(b,0,sizeof(b));
            rep(j,n){
                ++b[max(0,j-a[j])];
                --b[min(n,j+a[j]+1)];
            }
            sum=0;
            rep(j,n){
                sum += b[j];
                a[j] = sum;
            }
        }
        rep(i,n){
		    cout << a[i] << " \n"[i == n - 1];
	    }
        return 0;
    }
}

Measured memory_bytes: 5144
n=gets.to_i
a=gets.split.map(&:to_i)
sum=0
count=Array.new(10**6,0)
a.each {|i| count[i]+=1}
#p count

count.each {|i| sum += i*(i-1)/2}

a.each do |i| 
    j=count[i]
    p sum-j*(j-1)/2+(j-1)*(j-2)/2 if j!=0
end


Measured memory_bytes: 36132
#include <array>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;


typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define PB push


#define MOD 1000000007LL
#define EPS 1e-10

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    cout << min(B / A, C) << endl;
    return 0;
}


Measured memory_bytes: 256
M = int(raw_input())
d = [0] * M
c = [0] * M 
for i in range(M):
    d[i], c[i] = map(int, raw_input().split())
D = 0
S = 0 
for i in range(M):
    D += c[i]
    S += d[i] * c[i]
print (D - 1) + (S - 1) / 9

Measured memory_bytes: 16900
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x,y;
int l,r,ans=1;
pair<int,int> p[100005];
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	cin>>p[i].first>>p[i].second;
	sort(p,p+m);
	l=p[0].first,r=p[0].second;
	for(int i=1;i<m;i++)
	{
		x=p[i].first,y=p[i].second;
		if(x<r)
		{
			if(x>l)l=x;
			if(y<r)r=y;
		}
		else ans++,l=x,r=y;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1152
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
Acount = Counter(A)
Adic = dict(Acount)
Akey = set(Adic.keys())
M = max(A)
L = [0 for i in range(10**5)]
for i in range(M):
    if i+1 in Akey:
        L[i] = Adic[i+1]
s = 0
for i in range(M):
    s += (i + 1) * L[i]
for i in range(q):
    b, c = map(int, input().split())
    s += (c - b) * L[b - 1]
    L[c - 1] += L[b - 1]
    L[b - 1] = 0
    print(s)


Measured memory_bytes: 23132
#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdlib.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P, ll> T;
 
long long int INF = 2e18;
const ll fact_table = 1200008;
double Pi = 3.1415926535897932384626;

priority_queue <ll> pql;
priority_queue <P> pqp;
priority_queue <P> bag;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
ll dx[8]={1,0,-1,0,1,1,-1,-1};
ll dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//↓,→,↑,←

#define endl "\n"
#ifdef ENJAPMA
    #undef endl
#endif
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
#define pc(x) cout << x << ",";
 
// const ll mod = 998244353ll;
const ll mod = 1000000007ll;
  
ll mypow(ll number1,ll number2, ll mod){
    if(number2 == 0){
        return 1ll;
    }else{
        ll number3 = mypow(number1,number2 / 2, mod);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
void YES(bool condition){
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5]; 
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = mypow(fact[fact_table],mod - 2, mod);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/

bool multicase = false;

ll n,m,num,a,b,c,d,e,h,q;
ll w, k;
ll x[500005], y[500005], z[500005];
string s;

void solve(){
    cin >> n >> k;
    ll ans = 0;
    ll maxi = 0, mini = 0;
    for(ll i=1;i<=n+1;i++){
        maxi += n + 1 - i;
        mini += i - 1;
        if(i >= k)ans += (maxi - mini + 1);
        ans %= mod;
    }
    p(ans);
    return;
}

int main(){
    // init();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, testcase = 1;
 
    if(multicase){
        cin >> q;
    }else{
        q = 1;
    }
    while(q--){
        // pu("Case ");pu("#");pu(testcase);pu(": ");
        solve();
        testcase++;
    }
    
    // solve();
    return 0;
 
}
















Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; ++i)
#define REPR(i,n) for(int i = n; i >= 0; --i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = b-1;i >= a;--i)
#define p(s) cout << (s) << endl
#define p2(s,t) cout << (s) << " " << (t) << endl 
#define ALL(v) (v).begin(), (v).end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;

static const ll MOD  = 1e9 + 7;
static const ll INF  = 1e18;

static const int White = 0;
static const int Gray = 1;
static const int Black = 2;

void pvector(vector<int> A){
    cout << "[vector]";
    for(int i = 0; i < A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

int main(){
    int X, A , B,C;
    cin >>X >> A ;
    if(X < A) p(0);
    else p(10);
}

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

int main()
{
  //int A, B, C, X, Y;
//  int m[101]={};
  int A, B, C, D;
//  int sosu[20000]={};
  int i,j,k;
  int flag=0;  
//    int k=0;

  scanf("%d %d %d %d", &A, &B, &C, &D);
  //printf("%d\n", A);

  ;

  
  
  if(abs(A-C)<=D) printf("Yes\n");
  else{
  if(abs(A-B)>D){
    printf("No\n");
    return 0;
  }
  if(abs(B-C)>D){
    printf("No\n");
    return 0;
  } 
   printf("Yes\n");
  }
  
return 0;
}


Measured memory_bytes: 128
package main

import "fmt"

func main() {
	var a, b, c, x int
	fmt.Scan(&a, &b, &c, &x)

	count := 0
	for i := 0; i <= a; i++ {
		for j := 0; j <= b; j++ {
			for k := 0; k <= c; k++ {
				if 500*i+100*j+50*k == x {
					count++
				}
			}
		}
	}
	fmt.Println(count)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#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 _GLIBCXX_DEBUG
static const int MAX = 50;

int main(){
  int N, V[MAX], C, ans = 0;
  cin >> N;
  rep(i, N) cin >> V[i];
  rep(i, N){
    cin >> C;
    if(V[i] - C > 0) ans += V[i] - C;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define LAST(vec) vec[vec.size() - 1]
string get_line() {
  string line;
  cin >> line;
  return line;
}
// 整数: 一桁
int main() {
  while (true) {
    auto line_num = stoi(get_line());
    if (line_num == 0) return 0;
    if (line_num == 1) {
      cout << stoi(get_line()) << endl;
      continue;
    }
    vector<int> stack;
    vector<bool> is_adds;
    auto calc = [&](int num) {
      if (LAST(is_adds)) {
        LAST(stack) += num;
      } else {
        LAST(stack) *= num;
      }
    };
    auto reduction = [&](int n) {
      REP(j, n) {
        auto num = LAST(stack);
        is_adds.pop_back();
        stack.pop_back();
        calc(num);
      }
    };

    REP(i, line_num) {
      auto line = get_line();
      auto level = line.size() - 1;
      // リダクション
      if (level < stack.size()) {
        auto n = stack.size() - level;
        reduction(n);
      }
      // パース
      auto chr = line[line.size() - 1];
      if (chr == '+') {
        stack.push_back(0);
        is_adds.push_back(true);
      } else if (chr == '*') {
        stack.push_back(1);
        is_adds.push_back(false);
      } else {
        calc(chr - '0');
      }
    }
    if (stack.size() > 1) {
      reduction(stack.size() - 1);
    }
    cout << LAST(stack) << endl;
  }
}



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

#define ull unsigned long long int
#define ll long long int
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define MOD (ull)(double)(1e9 + 7)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define pull pair<ull, ull>
#define m_p make_pair
#define debug(x) cout << #x << " " << x << endl

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	set<string> s;
	string S;
	for(int i=0 ; i<n ; ++i){
		cin >> S;
		s.insert(S);
	}
	
	cout << s.size();
}


Measured memory_bytes: 19276
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;} 

template<typename T, typename U> bool chmax(T &a,const U& b){if(a<b){a=b;return true;}return false;}

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

int N, T; cin >> N >> T;
VI A(N), B(N); rep(i, 0, N) cin >> A[i] >> B[i];

VVI L(N+1, VI(T+1, 0)), R(N+1, VI(T+1, 0));

rep(i, 0, N) rep(t, 0, T+1){
    L[i+1][t] = max(L[i+1][t], L[i][t]);
    if (t + A[i] <= T) L[i+1][t + A[i]] = max(L[i+1][t+A[i]], L[i][t] + B[i]);
}
Rrep(i, N-1, 0) rep(t, 0, T+1){
    R[i][t] = max(R[i][t], R[i+1][t]);
    if (t + A[i] <= T) R[i][t + A[i]] = max(R[i][t+A[i]], R[i+1][t] + B[i]);
}

rep(i, 0, N+1) rep(j, 0, T){
    L[i][j+1] = max(L[i][j], L[i][j+1]);
    R[i][j+1] = max(R[i][j], R[i][j+1]);
}

i64 maxi = 0;
rep(i, 0, N) rep(t, 0, T) {
    maxi = max(maxi, B[i] + L[i][t] + R[i+1][T-1-t]);
}

cout << maxi << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 問題文から考える。自分ができることから考える。
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索。逆から考える。
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



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

int main() {
  int N, Y;
  cin >> N >> Y;

  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
      if (i + j <= N) {
        int k = N - i - j;
        if (10000 * i + 5000 * j + 1000 * k == Y) {
          printf("%d %d %d\n", i, j, k);
          return 0;
        }
      }
    }
  }
  printf("%d %d %d\n", -1, -1, -1);
}

Measured memory_bytes: 256
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
#include<set>
using namespace std;

int main()
{

	int s;
	cin >> s;

	set<int>st;
	int x = s;

	while (st.count(x) == 0) {
		st.insert(x);
		if (x % 2 == 0) {
			x /= 2;
		}
		else {
			x = x * 3 + 1;
		}
	}

	cout << (st.size() + 1) << endl;

}

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

#define PI 3.1415926535897932


int main(){
    int mod=1000000007;
    int n;
    scanf("%d",&n);
    vector <int> a(n);
    for (auto&e:a) scanf("%d",&e);
    vector <int>d;
    for (int i=0;i<n;i++) {
        auto it=lower_bound(d.rbegin(),d.rend(),a[i]);
        if (it==d.rbegin()) {
            d.push_back(a[i]);
        } else {
            --it;
            *it=a[i];
        }
    }
    int ans=d.size();
    printf("%d\n",ans);
    return 0;
}

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

template <
    typename TYPE,
    std::size_t SIZE>
std::size_t a_len(const TYPE (&array)[SIZE])
{
    return SIZE;
}

using namespace std;
using ll = long long int;
using vi = vector<ll>;

#define REPS(a, i, n) for (ll(i) = a; (i) < (n); ++(i))
#define REP(i, n) REPS(0, i, n)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 912345678;

int n,a,b;

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

Measured memory_bytes: 256