akhauriyash/Code-Regression huggingface dataset:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    matA = [list(input()) for _ in range(n)]
    matB = [list(input()) for _ in range(m)]

    a = np.array(matA)
    b = np.array(matB)

    for i in range(n - m + 1):
        for j in range(n - m + 1):
            if np.all(a[j:j + m, i:i + m] == b):
                print("Yes")
                exit(0)

    print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 13580
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define rep(i,x) for(int i=0;i<x;i++)
#include<string>

using namespace std;

int main(){
int N;
  cin>>N;
  int L[N];
  rep(i,N){
  	cin>>L[i];
  }
  
  int count=0;
  
  
  for(int a=0;a<N-2;a++){
  	for(int b=a+1;b<N-1;b++){
    	for(int c=b+1;c<N;c++){
        	if(L[a]<(L[b]+L[c])){
              
              if(L[b]< (L[a]+L[c])){
                
              	if(L[c] <( L[a]+L[b])){
              
              count++;
                }
              }
            }
        	
        }
    }
  }
  
  cout<<count;
  
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  string S, T;
  cin >> S >> T;
  long long minn = 1001001001;
  for(int i = 0; i < S.size() - T.size() + 1; i++){
    long long count = 0;
    for(int j = 0; j < T.size(); j++){
      if(S[i+j] != T[j]){
        count++; 
      }
    }  
    minn = min(minn, count);
  }
  cout << minn <<endl;
}



Measured memory_bytes: 3620
from collections import Counter
n = int(input())
d = Counter(list(map(int, input().split())))
m = int(input())
t = Counter(list(map(int, input().split())))
key = t.keys()
ans = True
for i in key:
    if t[i] > d[i]:
        ans = False
        break
if ans:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 55372
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
const lint mod=1e9+7;

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

  cout << r*r << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
   int n;
   cin >> n;
   vector<vector<int>> a(n, vector<int>(3));
   for(int i = 0; i < n; i++)
   {
       cin >> a[i][0] >> a[i][1] >> a[i][2];
   }
   vector<vector<int>> dp(n+10, vector<int>(3,0));
   for(int i = 0; i < n; i++)
   {
       for(int j = 0; j < 3; j++)
       {
           for(int k = 0; k < 3; k++)
           {
               if (j != k) {
                   dp[i+1][k] = max(dp[i+1][k], dp[i][j]+a[i][k]);
               }
           }
       }
   }
   cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
}

Measured memory_bytes: 11136
use proconio::input;
use proconio::marker::{Chars};
use std::cmp;

fn main() {
    input! { s: Chars, t: Chars}

    let mut ans = std::usize::MAX;
    for i in 0..(s.len() - t.len() + 1) {
        let mut count = 0;
        for j in 0..t.len() {
            if t.get(j).unwrap() != s.get(i + j).unwrap() {
                count = count + 1;
                continue;
            }
        }
        ans = cmp::min(ans, count);
    }

    println!("{}", ans);
}


Measured memory_bytes: 2120
#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;++i)
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vip;
int mis(char a,char b,char c){
  if (a==b&&b==c) return 0;
  if (a!=b&&b!=c&&a!=c) return 2;
  return 1;
}

int main(){
  int n;cin>>n;
  string a,b,c;cin>>a>>b>>c;
  int ans = 0;
  fol(i,n){
    ans += mis(a[i],b[i],c[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner  = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int area = a * b;
        int perimeter = (a + b) * 2;
        System.out.println(area + " " + perimeter);
        scanner.close();
    }
}



Measured memory_bytes: 26148
import collections
import bisect

def prim(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n=int(input())
p=prim(n)
c = collections.Counter(p)
d=c.values()
m=0

l=[1]
for i in range(2,100):
        l.append(i+l[-1])
for i in d:
        m+=bisect.bisect_right(l,i)
print(m)


Measured memory_bytes: 67744
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define loope(i,a,b) for(ll i=a;i<=b;i++)
#define test() ull t;cin>>t;while(t--)
#define pll pair<ll,ll>
#define puu pair<ull,ull>
#define f first
#define s second
#define pb push_back
#define mkp make_pair
#define ins insert
#define Vint vector<int>
#define Vll vector<ll>
#define Vull vector<ull>
#define nl cout<<endl
#define sp cout<<" "
#define MOD 1000000007
#define all(x) x.begin(),x.end()


int main() 
{
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	ll r,c,m;
	cin>>r>>c>>m;
	vector<ll> mr(r+1),mc(c+1);
	map<pair<ll,ll>,ll> mp;
	loop(i,0,m){
		ll nr,nc;
		cin>>nr>>nc;
		mp[make_pair(nr,nc)] = 1;
		mr[nr]++;
		mc[nc]++;
	}


	// for(auto i:mp)
	// 	cout<<i.f.f<<" "<<i.f.s<<endl;
	// for(auto i:mr)
	// 	cout<<i<<" ";

	// cout<<endl;

	// for(auto i:mc)
	// 	cout<<i<<" ";

	// cout<<endl;

	ll maxr = mr[max_element(mr.begin(),mr.end()) - mr.begin()];
	ll maxc = mc[max_element(mc.begin(),mc.end()) - mc.begin()];

	map<ll,ll> rpos,cpos;
	ll cntr,cntc;
	cntr = cntc = 0;
	loop(i,1,r+1){
		if(mr[i]==maxr){
			rpos[i] = 1;
			cntr++;
		}
	}

	loop(i,1,c+1){
		if(mc[i]==maxc){
			cpos[i] = 1;
			cntc++;
		}
	}

	// cout<<maxr<<" "<<maxc<<endl;

	ll result = maxr + maxc - 1;
	ll cnt = 0;
	for(auto i:mp){
		if(rpos[i.f.f] && cpos[i.f.s])
			cnt++;
	}

	if(cnt<cntr*cntc)
		result++;

	cout<<result;
}

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

int main(){
	int k, x;
	cin >> k >> x;
	for (int i = max(x - k + 1, -1000000);
		i <= min(x + k - 1,1000000);
		i++) {
		cout << i << endl;
	}
	return 0;
}


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

using namespace std;

int main()
{
    int N;
    vector<int> dp(100001);
    vector<int> coins;

    coins.push_back(1);
    for(int i = 1; i <= 6; ++i) {
        coins.push_back(int(pow(6, i)));
        coins.push_back(int(pow(9, i)));
    }

    cin >> N;

    fill(dp.begin(), dp.end(), 100001);
    dp[0] = 0;

    for(int i = 1; i <= N; ++i)
        for(int j = 0; j < 13; ++j)
            if(i >= coins[j])
                dp[i] = min(dp[i], dp[i-coins[j]]+1);

    cout << dp[N] << endl;

    return 0;
}

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

#define pb(s) push_back(s)
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    string str;
    cin>>n>>str;
    if(str.size()<=n){
        cout<<str<<endl;
        return 0;
    }
    string temp="";
    temp+=str.substr(0,n)+"...";
    cout<<temp<<endl;


    return 0;
}



Measured memory_bytes: 3600
#include<stdio.h>

int main()
{
	char s[3]={NULL};
	int cnt_a=0, cnt_b=0;
	scanf("%s", s);

	for(int i=0; i<3; i++){
		if (s[i]=='A') cnt_a++;
		else cnt_b++;
	}

	if (cnt_a == 0 || cnt_b ==0) printf("No\n");
	else printf("Yes\n");

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n;
int a[maxn];
ll ans;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	if (n>1) ans+=a[n];
	int k=n-1;n-=2;
	while (n>=2) ans=ans+2*a[k--],n=n-2;
	if (n==1) ans+=a[k];
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 4420
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <cmath>
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

int main(){
  int S;
  int W;
  cin >> S;
  cin >> W;
  if(S > W){
    cout << "safe" << endl;
  }else{
    cout << "unsafe" << endl;
  }
}


Measured memory_bytes: 3636
// 2011/01/12 Tazoe

#include <iostream>
#include <string>
using namespace std;

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

	string eng;
	getline(cin, eng);

	for(int i=0; i<n; i++){
		getline(cin, eng);
		while(true){
			string::size_type index = eng.find("Hoshino");
			if(index == string::npos)
				break;
			else
				eng.replace(index, 7, "Hoshina");
		}

		cout << eng << endl;
	}

	return 0;
}

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

int main() {
int a,b,c,d,e;
cin >> a >> b >> c >> d >> e;
if(a == 0){
	cout << 1 << endl;
} else if(b == 0){
	cout << 2 << endl;
} else if(c == 0){
	cout << 3 << endl;
} else if(d == 0){
	cout << 4 << endl;
} else if(e == 0){
	cout << 5 << endl;
}
}

Measured memory_bytes: 3620
r,c=map(int,input().split())
R=[]
A=[0]*(c+1)
for i in range(r):
    R.append(list(map(int,input().split())))
for i in range(r):    
    s=0
    for j in range(c):
        s+=R[i][j]
        A[j]+=R[i][j]
    print(' '.join(map(str,R[i]))+' '+str(s))
    A[c]+=s
print(' '.join(map(str,A)))


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

namespace ndifix{

}

int main(){
    int a,b,c,x,y;cin>>a>>b>>c>>x>>y;
    if(a+b<c+c)cout<<x*a+y*b<<endl;
    else cout<<c*2*min(x,y)+(x>y?(c+c<a?c*2*(x-y):a*(x-y)):(c+c<b?c*2*(y-x):b*(y-x)))<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define F first
#define S second

int32_t main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	string s[n];
	int t[n];
	for (int i = 0; i < n; i++)
		cin >> s[i] >> t[i];
	string d;
	cin >> d;
	int f = find(s, s + n, d) - s;
	int ans = 0;
//	cerr << f << endl;
	for (int i = f + 1; i < n; i++)
		ans += t[i];
	cout << ans << endl;
}



Measured memory_bytes: 256
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string t = Console.ReadLine();
            int cnt = 0;
            for(int i = 0; i < s.Length; i++)
            {
                if (s[i] != t[i]) cnt++;
            }
            Console.WriteLine(cnt);
        }
    }
}


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

#define rep(i,n) for(int (i) = 0;i < (int)(n);(i)++)
int main(){
    int n,m,sum;
    cin >> n >> m;
    vector<int> b(m);
    vector<vector<int> > a(n,vector<int>(m));
    rep(i,n) rep(j,m) cin >> a[i][j];
    rep(i,m) cin >> b[i];
    rep(i,n) {
        sum = 0;
        rep(j,m){
            sum += a[i][j] * b[j];
        }
        cout << sum << endl;
    }
}



Measured memory_bytes: 3188
#include <iostream>
using namespace std;
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string>
#include <cstdlib>

int main() {
	int k;
	cin >> k;
	long long int a[1000000];
	for(int i = 0; i < k; i++){
		cin >> a[i];
	}
	long long int max=2, min=2;
	for(int i = k-1; i > -1; i--){
		if((min+a[i]-1)/a[i]*a[i]>max){
			cout << -1 <<endl;
			return 0;
		}
		min = (min+a[i]-1)/a[i]*a[i];
		max = max/a[i]*a[i]+a[i]-1;
	}
	cout << min << " " <<max <<endl;
	return 0;
}

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


map<long long int, long long int> primeFactors(long long int n) {  
	map<long long int, long long int> ans;
    while (n % 2 == 0) {
    	ans[2]++;
    	n = n / 2;
    }  
    for (long long int i = 3; i <= (long long)sqrt(n) + 1; i = i + 2) {  
        while (n % i == 0) { 
            ans[i]++;
            n = n / i;
        }  
    }  
    if (n >= 2) ans[n]++;
 
    return ans;
}  
 

int main() {
    long long int A, B;
    cin >> A >> B;
 
    map<long long int, long long int> A_div = primeFactors(A);
    map<long long int, long long int> B_div = primeFactors(B);
 
    int cnt = 1;
 
    for(auto j : A_div) {
    	if(B_div.find(j.first) != B_div.end()) cnt++;
    }
 
    cout << cnt << endl;
    return 0;
}

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

class Mod{
    static final long MOD = 1000_000_007;
    static final long[] fact = makeFactorialArray(1000000);
    static final long[] factInv = makeInversedArray(fact);

    public static long add(long a, long b){
        long tmp = (a+b)%MOD;
        return tmp>=0 ? tmp : tmp+MOD;
    }
    public static long adds(long... ar){
        long ans=0;
        for(long x:ar) ans = Mod.add(ans, x);
        return ans;
    }
    public static long sub(long a, long b){
        return add(a,-b);
    }
    public static long mult(long a, long b){
        long tmp = (a*b)%MOD;
        return tmp>=0 ? tmp : tmp+MOD;
    }
    public static long mults(long... ar){
        long ans=1;
        for(long x:ar) ans = Mod.mult(ans, x);
        return ans;
    }
    public static long power(long a, long x){ //calculate a^x
        if(x<0)return 0;
        if(x==0)return 1;
        if(x%2==0) {
            long half = power(a,x/2);
            return mult(half,half);
        }
        return (a*power(a,x-1)) % MOD;
    }
    public static long inverse(long a){
        return power(a,MOD-2);
    }
    public static long div(long a, long b){
        return mult(a, inverse(b));
    }
    public static long[] makeFactorialArray(int size){
        long[] array = new long[size];
        array[0]=1;
        for(int i=1;i<size;i++){
            array[i]=mult(array[i-1],i);
        }
        return array;
    }
    public static long[] makeInversedArray(long[] original){
        long[] array = new long[original.length];
        for(int i=0;i<original.length;i++){
            array[i] = inverse(original[i]);
        }
        return array;
    }
    public static long combination(int n, int r){
        if(n<0 || r<0 || n<r) return 0;
        return mult(fact[n], mult(factInv[r],factInv[n-r]));
    }
    public static long gcd(long a, long b){
        if(a<b) return gcd(b,a);
        if(b==0) return a;
        if(a%b==0) return b;
        return gcd(b,a%b);
    }
    public static long lcm(long a, long b){
        return (a/gcd(a,b))*b;
    }

}
public class Main {

    static long gcd(long a, long b){
        if(a<b) return gcd(b,a);
        if(b==0) return a;
        if(a%b==0) return b;
        return gcd(b,a%b);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long N = sc.nextLong();
        long M = sc.nextLong();
        long K = sc.nextLong();

        System.out.println(Mod.mults(Mod.combination((int)(N*M-2),(int)(K-2)),
                                     Mod.add(Mod.mults(N+1, N, N-1, M, M), Mod.mults(M+1, M, M-1, N, N)),
                                     Mod.inverse(6)
                          ));
    }
}

Measured memory_bytes: 39636
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<utility>
#include<string>

using namespace std;

main(){
  int h,m,s;
  int ma,mi;
  int i;
  for(i=0;i<3;i++){
    scanf("%d %d %d",&h,&m,&s);
    mi=h*3600+m*60+s;
    scanf("%d %d %d",&h,&m,&s);
    ma=h*3600+m*60+s;
    ma-=mi;
    cout << ma/3600 <<' ';
    ma%=3600;
    cout << ma/60 <<' ';
    cout << ma%60 <<endl;
  }
}

Measured memory_bytes: 0
fun main(args: Array<String>) {
    var n = readLine()!!.toInt()
    var hs = readLine()!!.split(" ").map { it.toInt() }.toMutableList()

    println(solve(hs))
}

fun solve(list: MutableList<Int>): Int {
    if (list.size <= 2) {
        return list.max()!!
    }

    var count = 0
    if (list.all { it > 0 }) {
        while (true) {
            if (list.all { it > 0 }) {
                for (i in 0 until list.size) {
                    list[i] = list[i] - 1
                }
                count++
            } else {
                break
            }
        }
    }


    var sublists = mutableListOf<MutableList<Int>>()
    var sublist = mutableListOf<Int>()
    for (h in list) {
        if (h == 0) {
            if (!sublist.isEmpty()) {
                sublists.add(sublist)
            }
            sublist = mutableListOf()
        } else {
            sublist.add(h)
        }
    }
    if (!sublist.isEmpty()) {
        sublists.add(sublist)
    }

    var ans = count
    for (sublist in sublists) {
        ans += solve(sublist)
    }

    return ans
}

Measured memory_bytes: 37944
Module Module1
    Sub Main()
        Dim input As String() = Console.ReadLine.Split(" "c)

        Dim num1 As Integer = Convert.ToInt32(input(0))
        Dim num2 As Integer = Convert.ToInt32(input(1))

        Dim d1 As Integer
        Dim d2 As Integer
        Dim answer As Integer = 0

        For i As Integer = 10 To num2
            d1 = i.ToString.Substring(0, 1)
            d2 = i.ToString.Substring(1, 1)

            If d1 < 2 OrElse d2 < 2 Then
                Continue For
            End If

            If (d1 * d2) = 0 Then
                Continue For
            End If

            If num1 >= d1 * d2 Then
                answer = answer + 1
            End If

        Next

        Console.WriteLine(answer)

    End Sub
End Module

Measured memory_bytes: 13268
#include <stdio.h>
typedef long long ll;
using namespace std;

int main(void) {
  ll i, j, k, a, b, c, n, m, cnt = 0, now = 0;
  scanf("%lld%lld%lld", &a, &b, &k);
  for(i = 100; ; --i) {
    if(!(a % i) && !(b % i)) ++cnt;
    if(cnt == k) {
      printf("%lld", i);
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int ans = 0;
int Q;
const int MAX_Q = 55;
int a[MAX_Q],b[MAX_Q],c[MAX_Q],d[MAX_Q];

void dfs(vector<int> h, int n, int m)
{
	/*
	cout << "b";
	rep(i,h.size())
	{
		cout << h[i] << " ";
	}
	cout << endl;
	*/
	//cout << h.size() << endl;
	if (h.size() == n) 
	{
		//cout << "fff" << endl;
		int temp = 0;
		rep(i,Q)
		{
			if (h[b[i]-1] - h[a[i]-1] == c[i]) temp += d[i];
		}
		ans = max(ans,temp);
		//cout << "ggg" << endl;
		return;
	}
	//cout << "c";
	//auto it = h.end();
	//it--;
	//cout << "d";
	h.push_back(0);
	for (int i = h[h.size()-2]; i <= m; ++i)
	{
		//cout << "e";
		h[h.size()-1] = i;
		dfs(h,n,m);
	}
	return;
}

int main()
{
	int N,M;
	cin >> N >> M >> Q;
	rep(i,Q)
	{
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	//cout << "a";
	vector<int> h;
	h.push_back(1);
	//cout << "A";
	dfs(h,N,M);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
		if len(os.Args) > 2 {
			wfp, _ = os.Create(os.Args[2])
		}
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)

	prev := make([]int, 200000)
	for i := 0; i < 200000; i++ {
		prev[i] = -1
	}
	dp := make([]int, n)
	dp[0] = 1
	for i := 0; i < n; i++ {
		c := getNextInt(scanner) - 1
		if i == 0 {
			prev[c] = i
			continue
		}
		dp[i] = dp[i-1]
		if prev[c] == -1 {
			prev[c] = i
			continue
		}
		if i-prev[c] > 1 {
			dp[i] += dp[prev[c]]
			dp[i] %= int(1e9 + 7)
		}
		prev[c] = i
	}

	fmt.Fprintln(writer, dp[n-1])
	writer.Flush()
}


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

#define FOR(i, a, b) for(i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define comp(a, b) int comp(const void *a, const void *b)
#define MOD  1000000007

typedef unsigned int uint;
typedef unsigned long ulong;
typedef long long ll;
typedef unsigned long long ull;

void TF_print(char boolean, char T[], char F[]){
    if(boolean){
        printf("%s\n", T);
    }else{
        printf("%s\n", F);
    }
}

int main(){
    uint N, i;
    uint max = 100000;
    scanf("%d", &N);
    uint num[max], a;
    uint MAX = 0, cnt = 0;
    REP(i, max){
        num[i] = 0;
    }

    REP(i, N){
        scanf("%u", &a);
        num[a]++;
    }
    REP(i, max - 2){
        cnt = num[i] + num[i + 1] + num[i + 2];
        if(cnt > MAX){
            MAX = cnt;
        }
    }
    printf("%u\n", MAX);
    return 0;
}

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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair


int main() {
  int d;
  cin >> d;
  cout << "Christmas";
  while (d != 25) {
    cout << " Eve";
    d++;
  }
  cout << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
#define i_7 1000000007
#define i_5 1000000005

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
#define inf 100000000/*10^8*/



////////////////////////////////////////



int main(){
    int n;cin>>n;
    int a[3*n];for(int i=0;i<=3*n-1;i++)cin>>a[i];
    ll big[3*n],small[3*n];
    priority_queue<int,vector<int>,greater<int>>  q;ll sum=0;
    for(int i=0;i<=n-1;i++){
        sum+=a[i];
        q.push(a[i]);
    }
    big[n-1]=sum;
    for(int i=n;i<=2*n-1;i++){
        sum+=a[i];
        q.push(a[i]);
        sum-=q.top();q.pop();
        big[i]=sum;
    }
    priority_queue<int> p;sum=0;
    for(int i=3*n-1;i>=2*n;i--){
        sum+=a[i];
        p.push(a[i]);
    }
    small[2*n-1]=sum;
    for(int i=2*n-1;i>=n;i--){
        sum+=a[i];
        p.push(a[i]);
        sum-=p.top();p.pop();
        small[i-1]=sum;
    }
    ll ans=big[n-1]-small[n-1];
    for(int i=n;i<=2*n-1;i++)ans=max(ans,big[i]-small[i]);
    cout<<ans<<endl;
    return 0;
}


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

using namespace std ;

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

ll r,c,n,x,y,w ,z;
bool judge(pll p){
  ll x = p.fi,y = p.se;
  return (x == 0 || x == r) || (y == 0 || y == c);
}

int f(pll a){
  if(a.fi == 0 ){
    return 4;
  }
  else if(a.fi == r){
    return 2;
  }
  else if(a.se == 0){
    return 1;
  }
  else if(a.se == c){
    return 3;
  }
  return 0;
}

bool circle(const pair<pll,int> &p,const pair<pll,int> &q){
  pll a = p.fi,b = q.fi;
  if(a.fi == 0 && b.fi == 0){
    return a.se > b.se;
  }
  else if(a.fi == r && b.fi == r){
    return a.se < b.se;
  }
  else if(a.se == 0 && b.se == 0){
    return a.fi < b.fi;
  }
  else if(a.se == c && b.se == c){
    return a.fi > b.fi;
  }
  else{
    return f(a) < f(b);
  }
}

int pos(int x,int y){
  pll a = mp(x,y);
  if(a.se == 0){
    return x;
  }
  else if(a.fi == r){
    return y + r;
  }
  else if(a.se == c){
    return c + r + (r - x);
  }
  else if(a.fi == 0 ){
    return c + r + r + (c - y);
  }
  return -1;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> r >> c >> n;
  vector<pair<int,int>> v;
  stack<int> s;
  rep(i,n){
    cin >> x >> y;
    cin >> w >> z;
    if(judge(mp(x,y)) && judge(mp(w,z))){
      v.push_back(mp(pos(x,y),i));
      v.push_back(mp(pos(w,z),i));
    }
  }
  sort(all(v));
  /* map<ll,int> m; */
  /* rep(i,2 * n){                                              */
  /*   if(judge(v[i].fi)){                                      */
  /*     m[v[i].se]++;                                          */
  /*   }                                                        */
  /* }                                                          */
  bool ex[100001] = {};
  rep(i,v.size()){
      int v2 = v[i].se;
      if(ex[v2] == false){
        s.push(v2);
        ex[v2] = true;
      }
      else{
        if(v2 != s.top()){
          std::cout << "NO" << std::endl;
          return 0;
        }
        s.pop();
        ex[v2] = false;
      }
  }
  cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 2420
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


int main(){
  int N; cin >> N;
  int a[20], x[20][20], y[20][20];
  rep(i, N){
    cin >> a[i];
    rep(j, a[i]){
      cin >> x[i][j] >> y[i][j];
    }
  }
  int ans = 0;
  rep(i, 1<<N){
    bool can = true; int cnt = 0;
    rep(j, N){
      if((1<<j) & i){
        rep(k, a[j]){
          if(i &(1<<(x[j][k]-1))){
            if(y[j][k]==0) can = false;
          }
          else{
            if(y[j][k]==1) can = false;
          }
        }
      }
    }
    if(can){
      rep(j, N){
        if((1<<j) & i) cnt++;
      }
    }
    ans = max(ans, cnt); 
  }
  cout << ans << endl;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int mochi[101];
int main()
{
	int ans,i,n;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	     scanf("%d",&mochi[i]);
    sort(mochi,mochi+n);
    ans=unique(mochi,mochi+n)-mochi;
    printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

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

using namespace std;

int main(){
	long long int q,h,s,d,n;
	cin >> q >> h >> s >> d >> n;
	
	long long int cost=0;
	
	vector<pair<long long int,long double> > unit_price;		//2Lあたりの値段
	
	unit_price.push_back ( make_pair(q*8, 0.25) );
	unit_price.push_back ( make_pair(h*4, 0.5) );
	unit_price.push_back ( make_pair(s*2, 1) );
	unit_price.push_back ( make_pair(d, 2) );
	
	sort(unit_price.begin(), unit_price.end());
	
/*
	REP(i,4){
		cout << unit_price[i].first << " " << unit_price[i].second << endl;
	}
*/
	
	REP(i,4){
		if(unit_price[i].second==2 && n%2!=0){
			cost += (unit_price[i].first*unit_price[i].second/2)*((n-1)/unit_price[i].second);
			n -= unit_price[i].second*((n-1)/unit_price[i].second);

		}else{
			cost += (unit_price[i].first*unit_price[i].second/2)*(n/unit_price[i].second);
		//
		//			cout << i << ": " << (unit_price[i].first*unit_price[i].second/2)*(n/unit_price[i].second) << " ";
		//
		n -= unit_price[i].second*(n/unit_price[i].second);
		}
		//
		//cout << unit_price[i].second*(n/unit_price[i].second) << endl;
		//
		
		//cout << i << ": " << cost << endl;
		
	}


	cout << cost << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main(){
char ch;
int a[26]={0};
while ( cin>> ch){
int num;
if(isupper(ch)){
ch=tolower(ch);
}
num= ch - 'a';
a[num]++;
}
for(int i=0; i<26;i++){
	ch='a'+i;
	cout << ch << " : "<<a[i]<< endl;
}
    return 0;
}

Measured memory_bytes: 1140
#include <bits/stdc++.h>
#define int long long
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x)/gcd(x,y)*(y))
#define isin(x, l, r) ((l) <= (x) and (x) < (r))
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define fcout cout << fixed << setprecision(10)
#define rcout(n) cout << right << setw(n)
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define PI (acos(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define INF32 INT32_MAX
#define MOD 1000000007LL
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<PII>;
using VTIII = vector<TIII>;
using Complex = complex<double>;
template<typename T, template<typename> typename C = less> using PQ = priority_queue<T, vector<T>, C<T>>;
template<typename T> bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a == b)){ a=b; return true; } return false; }
template<typename T> bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a == b)){ a=b; return true; } return false; }


int N, K;
int A[200010];


signed main(){
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    sort(A, A+N);

    int n = lb(A, A+N, 0)-A;
    int z = ub(A, A+N, 0)-A;
    if(K <= n*(N-z)){
        int l = -1e18-1, r = -1;
        while(r-l > 1){
            int m = l+(r-l)/2;
            int c = 0;
            rep(i, 0, n) c += A+N-lb(A+n, A+N, m, [i](int x, int v){ return A[i]*x > v; });
            if(c < K) l = m;
            else r = m;
        }
        cout << r << endl;
    }
    else if(K <= n*(N-z)+(z-n)*(N-(z-n))+(z-n)*(z-n-1)/2) cout << 0 << endl;
    else {
        int l = 0, r = 1e18;
        while(r-l > 1){
            int m = l+(r-l)/2;
            int c = n*(N-z)+(z-n)*(N-(z-n))+(z-n)*(z-n-1)/2;
            rep(i, 0, n) c += A+n-lb(A+i+1, A+n, m, [i](int x, int v){ return A[i]*x > v; });
            rep(i, z, N) c += lb(A+i+1, A+N, m+1, [i](int x, int v){ return A[i]*x < v; })-1-(A+i);
            if(c < K) l = m;
            else r = m;
        }
        cout << r << endl;
    }

    return 0;
}

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

using namespace std;

const int maxn=1e5+5,mod=1e9+5;

typedef long long ll;


int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        int maxx=max(a,b),minn=min(a,b);
        int i;
        for(i=1;i<=maxx;i++)
            printf("%d",minn);
        printf("\n");
    }
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int xl, ans = 0;
  string x;
  cin >> x;
  xl = x.length();
  deque<char> dq;
  for (int i = 0; i < xl; ++i) {
    dq.push_back(x[i]);
    if (dq.size() >= 2 && dq[dq.size() - 2] == 'S' &&
        dq[dq.size() - 1] == 'T') {
      dq.erase(dq.end());
      dq.erase(dq.end());
    }
  }

  cout << dq.size() << endl;
  return 0;
}


Measured memory_bytes: 644
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b,c,d=0,e=0,f=2,g=0,h[300001],i,j,k=0,l=0,r=0,p[300001],n[101],m,q,u,v,w,y,z;
    string s,t,x;
    cin>>s;
    for(i=0;i<s.size();i++){
        if(s[i]=='A'){
            d=1;
        }
        else{
            e=1;
        }
    }
    if(d==1&&e==1){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
}

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

#define all(x) (x).begin(), (x).end()
#define itn int
#define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end())

using namespace std;

inline int nxt() {
	int x;
	scanf("%d", &x);
	return x;
}

int main() {
	int n = nxt(), x = nxt();
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		a[i] = nxt();
	}
	sort(all(a));
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (x >= a[i]) {
			x -= a[i];
			++ans;
		}
	}
	if (ans == n && x) {
		--ans;
	}
	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 768
#include<iostream>
#include<algorithm>

using namespace std;

const int INF = 10000000;
int n;
int d[10][10];

int main() {
	while (cin >> n, n) {
		int town_max = 0;
		for (int i = 0; i < 10; i++)for (int j = 0; j < 10; j++) {
			if (i == j)d[i][j] = 0;
			else d[i][j] = INF;
		}
		for (int i = 0; i < n; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			town_max = max(town_max, max(a, b));
			d[a][b] = f, d[b][a] = f;
		}
		for (int k = 0; k <= town_max; k++) {
			for (int i = 0; i <= town_max; i++) {
				for (int j = 0; j <= town_max; j++) {
					if (d[i][j] > d[i][k] + d[k][j]) {
						d[i][j] = d[i][k] + d[k][j];
					}
				}
			}
		}
		int ans = INF,node;
		for (int i = 0; i <= town_max; i++) {
			int total = 0;
			for (int j = 0; j <= town_max; j++) {
				total += d[i][j];
			}
			if (ans > total)node = i, ans = total;
		}
		cout << node << " " << ans << endl;
	}
	return 0;
}

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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  ll x;cin>>x;

  ll cnt = (x / 11ll) * 2ll;
  x = x % 11ll;
  if(0 < x && x <= 6)cnt++;
  else if (x > 6 ) cnt += 2;
  cout<<cnt<<endl;

  return 0;
}


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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct UnionFind
{
  vector<int> data;
  UnionFind(){}
  UnionFind(int sz):data(sz, -1){};
  int size(int x) { return -data[find(x)]; }
  int find(int x) {
    if(data[x] < 0) return x;
    return data[x] = find(data[x]);
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y]; data[y] = x;
    return;
  }
};


signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n, m;
  cin >> n >> m;
  vint p(n);
  rep(i, n) cin >> p[i], --p[i];
  UnionFind uf(n);
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    uf.unite(x, y);
  }
  vector<set<int> >  graph(n);
  rep(i, n) {
    graph[uf.find(i)].insert(p[i]);
  }
  int ans = 0;
  rep(i, n) {
    if(graph[uf.find(i)].count(i)) ++ans;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 2e5 + 5 ; 
const int P = 1e9 + 7 ; 
int n, m, fac[N], inv[N], Ans ;  
int fpow( int x, int k ) {
	int ans = 1, base = x ; 
	while( k ) {
		if( k & 1 ) ans = ans * base % P ;
		base = base * base % P, k >>= 1 ;
	} return ans ; 
}
int C( int x, int y ) {
	if( y > x ) return 0 ;
	return fac[x] * inv[y] % P * inv[x - y] % P ; 
}
signed main()
{
	n = gi(), m = gi(), inv[0] = fac[0] = 1 ;
	rep( i, 1, n ) fac[i] = fac[i - 1] * i % P, inv[i] = fpow( fac[i], P - 2 ) ;
	Ans = 1 ;
	for( re int i = 1; i <= min( n - 1, m ); ++ i ) {
		int ans = C( n, i ) ;
		int t = n - i, uu = C( n - 1, n - t )  ; 
		Ans = ( Ans + ans * uu % P ) % P ;
	} cout << Ans << endl ;
	return 0 ;
}

Measured memory_bytes: 3328
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace AGC025A
{
    public class Program
    {
        void Solve(StreamScanner ss, StreamWriter sw)
        {
            //---------------------------------
            var N = ss.Next(int.Parse);

            var ans = int.MaxValue;
            for (var i = 1; i < N; i++)
            {
                ans = Math.Min(ans, i.ToString().Sum(c => c - '0') + (N - i).ToString().Sum(c => c - '0'));
            }

            sw.WriteLine(ans);
            //---------------------------------
        }

        static void Main()
        {
            var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput()));
            var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            new Program().Solve(ss, sw);
            sw.Flush();
        }

        static readonly Func<string, string> String = s => s;
    }

    public class StreamScanner
    {
        static readonly char[] Sep = {' '};
        readonly Queue<string> buffer = new Queue<string>();
        readonly TextReader textReader;

        public StreamScanner(TextReader textReader)
        {
            this.textReader = textReader;
        }

        public T Next<T>(Func<string, T> parser)
        {
            if (buffer.Count != 0) return parser(buffer.Dequeue());
            var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries);
            foreach (var nextString in nextStrings) buffer.Enqueue(nextString);
            return Next(parser);
        }

        public T[] Next<T>(Func<string, T> parser, int x)
        {
            var ret = new T[x];
            for (var i = 0; i < x; ++i) ret[i] = Next(parser);
            return ret;
        }

        public T[][] Next<T>(Func<string, T> parser, int x, int y)
        {
            var ret = new T[y][];
            for (var i = 0; i < y; ++i) ret[i] = Next(parser, x);
            return ret;
        }
    }
}


Measured memory_bytes: 15432
using System;
class curtain{
  public static void Main(){
    String[] str = Console.ReadLine().Split(' ');
    int a = int.Parse(str[0]);
    int b = int.Parse(str[1]);
    int ret;
    if(a > 2*b){
      ret = a-2*b;
    }
    else{
      ret = 0;
    }
    Console.WriteLine(ret);
  }
}


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

int n, ans = 0, a[4];
string s;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        for (int j = 0; j < (int)s.size() - 1; j++)
            if (s[j] == 'A' && s[j + 1] == 'B')
                ans++;
        int msk = 0;
        if (s[0] == 'B')
            msk += 1;
        if (s.back() == 'A')
            msk += 2;
        a[msk]++;
    }
    if (a[3] >= 1)
    {
        ans += a[3] - 1;
        a[3] = 1;
    }
    if (a[3] == 1)
    {
        if (a[1] >= 1)
        {
            a[1]--;
            ans++;
        }
        if (a[2] >= 1)
        {
            a[2]--;
            ans++;
        }
    }
    ans += min(a[1], a[2]);
    cout << ans;
}


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

int main()
{
    int N, K, R, S, P;
    cin >> N >> K;
    cin >> R >> S >> P;
    string T;
    cin >> T;
    // 0:R, 1:S, 2:P
    int t[N];
    int v[3] = {R, S, P};
    for (int i = 0; i < N; i++) {
        if (T[i] == 'r') t[i] = 2;
        if (T[i] == 's') t[i] = 0;
        if (T[i] == 'p') t[i] = 1;
    }

    int dp[N][3] = {};

    for (int i = 0; i < K; i++) {
        dp[i][t[i]] = v[t[i]];
        for (int j = i + K; j < N; j += K) {
            for (int k = 0; k < 3; k++) {
                if (t[j] == k) {
                    dp[j][k] = max(dp[j - K][(k + 1) % 3], dp[j - K][(k + 2) % 3]) + v[k];
                }
                else {
                    dp[j][k] = max(dp[j - K][(k + 1) % 3], dp[j - K][(k + 2) % 3]);
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= K; i++) {
        ans += max({dp[N - i][0], dp[N - i][1], dp[N - i][2]});
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2048
//==========================================================================
//
//                   Bismillahir-Rahmanir-Rahim
//
// ==========================================================================
#include <bits/stdc++.h>
#define        ll                              long long int
#define        f(x,y,z)                        for(int x=y;x<z;x++)
#define        pii                             pair<int,int>
#define        pll                             pair<ll,ll>
#define        CLR(a)                          memset(a,0,sizeof(a))
#define        SET(a)                          memset(a,-1,sizeof(a))
#define        N                               100010
#define        M                               1000000007
#define        pi                              acos(-1.0)
#define        ff                              first
#define        ss                              second
#define        pb                              push_back
#define        inf                             (int)1e9
#define        eps                              1e-9
using namespace std;
int dx[]={0,0,1,-1,-1,-1,1,1};
int dy[]={1,-1,0,0,-1,1,1,-1};
template < class T> inline T biton(T n,T pos){return n |((T)1<<pos);}
template < class T> inline T bitoff(T n,T pos){return n & ~((T)1<<pos);}
template < class T> inline T ison(T n,T pos){return (bool)(n & ((T)1<<pos));}
template < class T> inline T gcd(T a, T b){while(b){a%=b;swap(a,b);}return a;}
template <typename T> string NumberToString ( T Number ) { ostringstream ss; ss << Number; return ss.str(); }
inline int nxt(){int aaa;scanf("%d",&aaa);return aaa;}
inline ll lxt(){ll aaa;scanf("%lld",&aaa);return aaa;}
inline double dxt(){double aaa;scanf("%lf",&aaa);return aaa;}
template <class T> inline T bigmod(T p,T e,T m){T ret = 1;
for(; e > 0; e >>= 1){
    if(e & 1) ret = (ret * p) % m;p = (p * p) % m;
} return (T)ret;}
#define sayed
#ifdef sayed
     #define debug(args...) {cerr<<"Debug: "; dbg,args; cerr<<endl;}
#else
    #define debug(args...)  // Just strip off all debug tokens
#endif
struct debugger{
    template<typename T> debugger& operator , (const T& v){
        cerr<<v<<" ";
        return *this;
    }
}dbg;
///******************************************START******************************************
vector<string> v;
int main(){
     //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(false);
   //cin.tie(0);
   int k,s;
   cin>>k>>s; ll ans=0;
   for(int i=0;i<=k;i++){
    for(int j=0;j<=k;j++){
        if(s-(i+j)<=k&&s-(i+j)>=0) ans++;
    }
   }
   cout<<ans<<endl;

return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string.h>
#include<queue>
#include<map>
#include<vector>
#include <cstdlib>
#include<algorithm>
#include <cstdio>
#include <cctype>
using namespace std;
const long long INF=10000000000000LL;
typedef long long ll;
typedef pair<ll,ll> P;
ll N,M,K=1,C;
ll A,B,W;
ll T,a,b;
double v[55],D[55],Q,l,r;
ll ans=0;
//bool D[100005];
ll S[50][50]={};
string str1[55],str2="abcdefghijklmnopqrstuvwxyz";
map<string,int> m;

int main(){
	cin>>N>>M;
	if(N*2<=M){
		ans+=N;
		M-=N*2;
		ans+=M/4;
	}else{
		ans+=M/2;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;


int main(){

// #ifndef ONLINE_JUDGE
//     // for getting input from input.txt
//     freopen("input.txt", "r", stdin);
//     // for writing output to output.txt
//     freopen("output.txt", "w", stdout);
// #endif
int n;
cin>>n;
int dp[n+1]= {0};
vector<int>h(n);
for(int i=0;i<n;i++){
	cin>>h[i];
}
dp[0] =1000000000;
dp[1] = 0;
for(int i=2;i<=n;i++){
	if(i>2)
		dp[i] = min(dp[i-1]+abs(h[i-1]-h[i-2]),dp[i-2]+abs(h[i-1]-h[i-3]));
	else
		dp[i]= dp[i-1]+abs(h[i-1]-h[i-2]);
}
cout<<dp[n];

}
		

Measured memory_bytes: 4028