akhauriyash/Code-Regression huggingface dataset:
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   998244353
#define PI 2*acos(0.0)
#define dbg(a) cout<<#a<<" ->->->-> "<<a<<"\n"
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};

ll bigmod(ll x, ll p)
{
    ll res = 1;
    while(p)
    {
        if(p&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return res;
}

//=============================================ASIFAZAD==============================================//


int32_t main()
{
    io;
    ll n;
    cin>>n;
    if(n == 2)
        return cout<<1, 0;
    int ans = 2;
    for(ll i = 2; i*i <= n; i++)
    {
        if(n%i == 0)
        {
            ll ac = n;
            while(ac%i == 0)
                ac /= i;
            if(ac%i == 1)
                ans++;
            if(n/i != i)
            {
                ac = n;
                ll is = n/i;
                while(ac%is == 0)
                    ac/= is;
                if(ac%is == 1)
                    ans++;
            }
        }
    }

    n--;

    for(ll i = 2; i*i <= n; i++)
    {
        if(n%i == 0)
        {
            ans++;
            if(n/i != i)
                ans++;
        }
    }

    cout<<ans;
    return 0;
}



Measured memory_bytes: 3612
#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD=1e9+7;
 
//const int MOD=998244353;



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n,k;
    cin>>n>>k;
    
    vector<int> v(n), slen(n);
    for(int&i:v)cin>>i;
    
    set<int> s;
    for(int i=0; i<k; i++) s.insert(v[i]);
    
    for(int i=0; i<n; i++){
        if(i && v[i]>v[i-1]) slen[i]=slen[i-1]-1;
        else{
            int r=i+1;
            while(r<n && v[r-1]<v[r]){
                r++;
            }
            slen[i]=r-i;
        }
    }
    
    bool used=0;
    if(slen[0]>=k) used=1;
    
    int ans=1;
    
    vector<string> ss;
    for(int i=1; i+k-1<n; i++){
        
        /*
        vector<int> v2=v;
        sort(v2.begin()+i,v2.begin()+i+k);
        string s="";
        for(int j:v2) s+=to_string(j);
        ss.push_back(s);
        //cout<<'\n';
        */
        
        int a=0;
        if(*s.begin()!=v[i-1]) a=1;
        s.erase(v[i-1]);
        s.insert(v[i+k-1]);
        auto it=s.end();
        it--;
        //cout<<v[i+k-1]<<'\n';
        
        
        if(*it!=v[i+k-1]) a=1;
        //cout<<i<<' '<<v[i-1]<<' '<<v[i+k-1]<<' '<<a<<'\n';
        if(slen[i]>=k && used) a=0;
        if(slen[i]>=k && a==1) used=1;
        
        ans+=a;
        
    }
    /*
    //cout<<ss.size();
    sort(ss.begin(),ss.end());
    for(auto s:ss){
        cout<<s<<'\n';
    }
    */
    
    cout<<ans;
    
    return 0;
}


Measured memory_bytes: 11264
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp(a, b) make_pair(a, b)
#define pb(t) push_back(t)
#define ft first
#define sc second
#define pt(num) cout << num << "\n"
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

class Edge {
public:
    ll t, c;
    Edge(ll t, ll c) {
        this->t=t;
        this->c=c;
    }
};


ll N, M;
vector<Edge> g[2][MAX]; //(i, j)間がg[0][i]][j].c円、g[1][i]][j].cスヌークで結ばれている
ll d[2][MAX]; //d[0][i]:sからiまでのmin距離、d[1][i]:tからiまでのmin距離

void dijkstra(ll idx, ll S) {
    ll u, i;
    ll clr[MAX]={};
    for(i=0; i<N; i++) {
        d[idx][i]=INF;
        clr[i]=0;
    }
    
    d[idx][S]=0;
    priority_queue<P> q;
    q.push(P(0, S));
    
    while(q.size()) {
        P f=q.top(); q.pop();
        u=f.sc;
        clr[u]=1;
        if(d[idx][u]<-f.ft) continue;
        for(i=0; i<g[idx][u].size(); i++) {
            Edge e=g[idx][u][i];
            if(clr[e.t]==1) continue;
            if(d[idx][e.t]>d[idx][u]+e.c) {
                d[idx][e.t]=d[idx][u]+e.c;
                q.push(P(-d[idx][e.t], e.t));
            }
        }
    }
}

int main(void) {
    cin >> N >> M;
    ll s, t;
    cin >> s >> t;
    s--; t--;
    ll i;
    ll mo=1e15;
    for(i=0; i<M; i++) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        g[0][u].pb(Edge(v, a));
        g[0][v].pb(Edge(u, a));
        g[1][u].pb(Edge(v, b));
        g[1][v].pb(Edge(u, b));
    }
    
    dijkstra(0, s);
    dijkstra(1, t);
    
    priority_queue<P> q;
    for(i=0; i<N; i++) {
        q.push(P(-d[0][i]-d[1][i], i));
    }
    
    for(i=0; i<N; i++) {
        P f=q.top();
        while(i>f.sc) {
            q.pop();
            f=q.top();
        }
        
        pt(mo+f.ft);
    }
    
}


Measured memory_bytes: 20732
package main

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

func main() {

	answer := "123"
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	s := sc.Text()
	sc.Scan()
	t := sc.Text()
	answer = t + s

	fmt.Println(answer)
}


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

int main() {
	
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	
	int ans = 0;
	int cnt = 0;
	vector<pair<int, int>> v;
	rep(i, n){
		if(s[i] == '1'){
			if(s[i+1] == '1'){
				cnt++;
			}else{
				v.push_back(make_pair(cnt + 1, 1));
				cnt = 0;
			}
		}else{
			if(s[i+1] == '0'){
				cnt++;
			}else{
				v.push_back(make_pair(cnt + 1, 0));
				cnt = 0;
			}
		}
	}
	cnt = 0;
	int cnt_zero = 0;
	for(int i = 0; i < v.size(); i++){
		if(v[i].second == 0){
			cnt_zero++;
		}
		if(cnt_zero > k){
			cnt -= v[i - k*2].first;
			if(i - k*2 > 0) cnt -= v[i - k*2 - 1].first;
			cnt_zero--;
		}
		cnt += v[i].first;
		ans = max(ans, cnt);
	}
	
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1528
def get_char(x):
    return chr(ord('a') + x)


def submit():
    n = int(input())
    n -= 1

    ans = []
    while True:
        r, q = divmod(n, 26)
        c = get_char(q)
        ans.append(c)
        if r == 0:
            break
        n -= q
        n //= 26
        n -= 1
    
    print("".join(reversed(ans)))
    

submit()

Measured memory_bytes: 9060
n = int(input())
nodes = 0
edges = 0
used = [1 for i in range(n+1)]
if n == 1:
    print(1)
    exit()
for i in range(n-1):
    a, b = map(int, input().split())
    nodes += used[a] * a * (n-a+1) + used[b] * b * (n-b+1)
    used[a] = used[b] = 0
    edges += min(a,b) * (n - max(a,b) + 1)
print(nodes - edges)

Measured memory_bytes: 80520
let () =
  let (n, k) = Scanf.scanf "%d %d\n" (fun n k -> (n, k)) in
  let a = Array.make n 0 in
  let rec read i =
    if i >= n then ()
    else (Scanf.scanf "%d\n" (fun w -> a.(i) <- w); read (i + 1))
  in
  read 0;
  let check p =
    let rec doit i j s =
      if i = n then n
      else if j >= k then i
      else
        let x = s + a.(i) in
        if x > p then doit i (j + 1) 0
        else doit (i + 1) j x
    in
    doit 0 0 0
  in
  let rec bin_search l r =
    if r < l then l
    else
      let m = (l + r) / 2 in
      let v = check m in
      if v >= n then bin_search l (m - 1)
      else bin_search (m + 1) r
  in
  Printf.printf "%d\n" (bin_search 0 (100000 * 10000))

Measured memory_bytes: 5324
#include <bits/stdc++.h>
using namespace std;
const int maxn =1e5 + 5;
int a[maxn];
int main() {
	int n, res = 0;
	cin >> n;
	for (int i =1 ; i <= n; i++) {
		cin >> a[i];
	}
	for (int i =1 ; i <= n; i++) {
		if (a[i] != i) res++;
	}
	if (res > 2) {
		cout << "NO" << endl;
	} else {
		cout << "YES" << endl;
	}
	return 0;
}

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

#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define reps(i, s, n) for(int i = (int)s; i < (int)n; i++)
#define in(i) std::cin >> i;
#define print(i) std::cout << i;
#define println(i) std::cout << i << std::endl;

int main() {
    std::string str;
    in(str);
    int n = (str[str.length()-1] - '0');
    if(n == 2 || n == 4 || n == 5 || n == 7 || n == 9)
        print("hon")
    else if(n == 0 || n == 1 || n == 6 || n == 8)
        print("pon")
    else
        print("bon");
    return 0;
}

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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define dep(i, a, n) for(int i = a; i >= (n); i--)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll
#define INF 100000000

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

signed main() {
	ll p, m, c;
  cin >> p >> m >> c;
  cout << p + m + c << endl;
	return 0;
}


Measured memory_bytes: 3236
#include <iostream>
#include <array>
#include <vector>
#include <map>
#include <utility>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <string>
#include <limits.h>
#include <algorithm>
#include <assert.h>

using namespace std;

vector<tuple<int, int, int>> x;

deque<pair<int, pair<int, int>>> p;

bool xx(tuple<int, int, int> &lhs, tuple<int, int,int> &rhs){
    return get<1>(lhs) < get<1>(rhs);
}

set<int> contain;

vector<int> uf;

int find(int x){
    if(uf[x] == x){
        return x;
    }else{
        return uf[x] = find(uf[x]);
    }
}

void unio(int x, int y){
    uf[find(x)] = uf[find(y)];
}

map<pair<int, int>, int> costs;

pair<int, int> mp(int x, int y){
    if (x < y) {
        return make_pair(x, y);
    }else{
        return make_pair(y, x);
    }
}

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int xx,yy;
        cin >> xx >> yy;
        x.push_back(make_tuple(xx, yy,i));
    }
    
    for (int i = 0; i < n; i++) {
        uf.push_back(i);
    }
    

    sort(x.begin(), x.end());
    
    for (int i = 0; i < n-1; i++) {
        int cost = min(abs(get<0>(x[i]) - get<0>(x[i+1])) , abs(get<1>(x[i])-get<1>(x[i+1])));
        p.push_back(make_pair(cost, make_pair(get<2>(x[i]), get<2>(x[i+1]))));
    }
    
    sort(x.begin(), x.end(),xx);
    
    for (int i = 0; i < n-1; i++) {
        int cost = min(abs(get<0>(x[i]) - get<0>(x[i+1])) , abs(get<1>(x[i])-get<1>(x[i+1])));
        p.push_back(make_pair(cost, make_pair(get<2>(x[i]), get<2>(x[i+1]))));
    }
    
    sort(p.begin(), p.end());
    
    int sum = 0;
    for (int i = 1; i < n;) {
        auto mm = p.front();
        if(find(mm.second.first) != find(mm.second.second)){
            unio(mm.second.first, mm.second.second);
            sum += mm.first;
            i++;
        }
        p.pop_front();
    }
    
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 4212
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;

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

const int MAX = 1000000;
bool prime[MAX];

int main() {
	prime[0] = prime[1] = true;
	for(int i=2; i*i<MAX; i++) {
		if(!prime[i]) {
			for(int j=i+i; j<MAX; j+=i) {
				prime[j] = true;
			}
		}
	}
	vector<int> primes;
	rep(i,MAX) {
		if(!prime[i]) {
			primes.push_back(i);
		}
	}

	int n, p;
	while(cin>>n>>p, n!=-1&&p!=-1) {
		int index = 0;
		while(primes[index]<=n) index++;
		vector<int> nums;
		int lim = min((int)primes.size(), index+p);
		for(int i=index; i<lim; i++) {
			for(int j=i; j<lim; j++) {
				nums.push_back(primes[i]+primes[j]);
			}
		}
		sort( nums.begin(), nums.end() );
		cout << nums[p-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 2568
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner scan = new Scanner(System.in);
        String S = scan.nextLine();
        char[] Schar = S.toCharArray();
        String T = scan.nextLine();
        char[] Tchar = T.toCharArray();
        int weather = 0;
        for(int i = 0 ; i < Schar.length ; i++){
            if(Schar[i] == Tchar[i]){
                weather++;
            }
        }
        System.out.println(weather);
    }
}


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

using namespace std;

const int N = 205;
int n, d[N][N];
bool vis[N], parity[N];
vector<int> gr[N];

void dfs(int u, int curParity) {
    if (vis[u]) {
        if (parity[u] != curParity) { printf("-1"); exit(0); }
        return ;
    }
    vis[u] = 1; parity[u] = curParity;
    for (int v : gr[u]) dfs(v, curParity ^ 1);
}

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) if (i != j) d[i][j] = N;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            char c; scanf(" %c", &c);
            if (c == '1') gr[i].emplace_back(j), d[i][j] = 1;
        }
    }

    dfs(1, 0);

    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    int diameter = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) diameter = max(diameter, d[i][j]);
    }

    printf("%d\n", diameter + 1);

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
using namespace std;
using uint = unsigned int;

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


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

int main() {
  int s1, s2, s3 ;
  int n;
  cin >> n ;
  s1 = n/100;
  s2 = n/10%2;
  s3 = n%2;
 
  cout << s1+s2+s3 << endl; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>                                                         
                                                                                   
   using namespace std;                                                            
   typedef long long ll;                                                           
                                                                                   
   int main(){                                                                     
                                                                                   
       ios_base::sync_with_stdio(0);                                               
       int i,j=1;                                                                  
      cin>>i;                                                                                          
      while(i!=0){                                                                
          cout<<"Case "<<j<<": "<<i<<endl;                                        
          j++;                                                                    
          cin>>i;                                                                 
      }                                                                           
                                                                                  
      return 0;                                                                   
  }         


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

#define F first
#define S second
#define nl '\n'
#define gcd __gcd
#define nset __builtin_popcount
#define pb push_back
#define btoe(x) x.begin(), x.end()
#define trim_chains(x) (x).resize(unique(btoe(x)) - (x).begin())
#define remove_dups(x) sort(btoe(x)); trim_chains(x);
#define rep(i, a, b)  for (int i = int(a); i <= int(b); i++)
#define nrep(i, a, b) for (int i = int(a); i >= int(b); i--)
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL)

using ll  = long long;
using ull = unsigned long long;
using vi  = vector<int>;
using vl  = vector<long>;
using vll = vector<ll>;
using vb  = vector<bool>;
using vvb = vector<vb>;
using vvi = vector<vector<int> >;
using ii  = pair<int, int>;
using vii = vector<ii>;
using vs  = vector<string>;
using msi = map<string, int>;
using iss = istringstream;

int main()
{
    FASTIO;
    int a; cin >> a;
    cout << a + a*a + a*a*a << nl;
    return 0;
}


Measured memory_bytes: 3632
import java.util.Scanner;
public class Main{
  public static void main (String [] args){
    Scanner sc = new Scanner (System.in);
    int n = sc.nextInt(),x;
    if (n%2==0) x=n/2;
    else x=n/2+1;
    System.out.println(x);
    sc.close();
  }
}

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

int main(){
  long int q,h,s,d,n ;
  cin >> q >> h >> s >> d >> n ;
  h = min(h,q*2) ;
  s = min(s,h*2) ;
  d = min(d,s*2) ;
  n *= 4 ;
  long int ans = 0 ;
  ans += d*(n/8) ; n %= 8 ;
  ans += s*(n/4) ; n %= 4 ;
  ans += h*(n/2) ; n %= 2 ;
  ans += q*n ;
  cout << ans << endl ;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
#define pb push_back
#define REP(ii,aa,nn) for(long long int ii=(aa);(ii)<=(nn);(ii)++)
 
typedef vector<int> vi;
typedef long long int ll;


int main(){
int a,b;cin>>a>>b;
if(a>12)
cout<<b;
else if
(a>5)
cout<<b/2;
else
cout<<0;
	
	return 0;
}


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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  int n;
  cin >> n;
  vector<int> va(n);
  for (int i = 0; i < n; ++i) {
    cin >> va[i];
  }

  int md = 1e9 + 7;
  vector<ll> cnts(n + 1, 0);
  cnts[0] = 3;

  ll ans = 1;
  for (int i = 0; i < n; ++i) {
    ans = ans * cnts[va[i]] % md;
    cnts[va[i] + 1]++;
    cnts[va[i]]--;
  }

  cout << ans << '\n';
}

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

using namespace std;

typedef long long ll;

ll get_num(ll p, ll idx)
{
    vector<int> v;
    while (p > 0) {
        v.push_back(p%10);
        p /= 10;
    }
    reverse(v.begin(), v.end());
    return v[idx];
}

ll get_digit(ll p)
{
    ll res = 0;
    while (p > 0) {
        p /= 10;
        res++;
    }
    return res;
}

int main()
{
    ll dig[11] = {0};
    for (int i = 1; i < 11; i++) {
        dig[i] = (ll)(i)*(9*pow(10, i-1));
        dig[i] += dig[i-1];
    }

    ll N, K;
    while (cin >> N >> K, N) {
        ll j = -1;
        for (int i = 0; i < 11; i++) {
            if (N <= dig[i]) {
                j = i;
                break;
            }
        }
        ll n = (N - (dig[j-1] + 1));
        ll p = pow(10, j-1) + n/j;        
        ll idx = n % j;        
        for (int i = 0; i < K; i++) {
            cout << get_num(p, idx);
            idx++;
            if (idx == get_digit(p)) {
                idx = 0;
                p++;   
            }
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3248
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
A=many_int()

maxs=max(A)
A.remove(maxs)

mean = maxs//2
temp=0
temp_mean=10**10
for a in A:
    if abs(a-mean) < temp_mean:
        temp_mean = abs(a-mean)
        temp=a

print(str(maxs)+" "+str(temp))

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

using namespace std;
typedef long long ll;
typedef pair< int , int > P;
typedef tuple<int, int, int> T;


int main(){
    int h1,h2,m1,m2;
    int k;

    cin>>h1>>m1>>h2>>m2>>k;

    cout<<(h2-h1)*60+(m2-m1)-k;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<(n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) (s.substr(f-1,t-f+1))
#define ALL(a) (a).begin(),(a).end()

using namespace std;
struct Grid{ll x,y,t;};
struct Edge{ll to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}
};
ll calc(ll k,ll a,ll b){
  if(a>b)return k+1;
  if(k<=a)return k+1;
  k-=a+1;
  ll ret=b;
  if(k%2){
    ret+=(b-a)*(k/2)+1;
  }else{
    ret+=(b-a)*(k/2);
  }
  return ret;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll k,a,b;cin>>k>>a>>b;
  cout<<max(k+1,calc(k,a,b))<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;

int main(void) {

	int K=0, S=0;

	int res = 0;

	cin >> K >> S;

	for (int x = 0; x <= K; x++) {
		for (int y = 0; y <= K; y++) {
			

			if (0 <= S - x - y && S - x - y <= K)res++;

			
		}
	}

	cout << res << endl;
	return 0;
	



}

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

public class Hello{
    public static Scanner sc = new Scanner();
    public static void Main(){
        var n = sc.NextInt();
        var list = sc.NextIntList();
        var dic = new Dictionary<int, int> ();

        foreach(var a in list){
            foreach(var v in new int[] {-1, 0, 1}){
                if(!dic.ContainsKey(a + v)) dic.Add(a + v, 0);
                dic[a+ v] = dic[a + v] + 1; 
            }
        }
        
        Console.WriteLine(dic.Values.Max());
    }
}

public class Scanner{
    private string line;
    private string[] token;
    private int cursole = 0;
    
    public string ReadLine(){
        line = Console.ReadLine();
        token = line.Split(' ');
        cursole = 0;
        return line;    
    }
    
    public string Next(){
        if(token == null) ReadLine();
        if(token.Length <= cursole) ReadLine();
        var ret = token[cursole];
        ++cursole;
        return ret;
    }

    public IEnumerable<double> NextDoubleList(){
        return NextList().Select(s => Double.Parse(s));
    }

    public int NextInt(){return Int32.Parse(Next());}
    
    public long NextLong(){return Int64.Parse(Next());}

    public double NextDouble(){return Double.Parse(Next());}

    public IEnumerable<string> NextList(){
        ReadLine();
        cursole = Int32.MaxValue;
        return token;
    }
    
    public IEnumerable<int> NextIntList(){
        return NextList().Select(s => Int32.Parse(s));
    }
}

public static class Extension{
    public static IEnumerable<int> To(this int from, int to){
        return Enumerable.Range(from, to);
    }

    public static void Times(this int times, Action<int> action){
        0.To(times).ToList().ForEach(x => action(x));
    }
}

Measured memory_bytes: 30044
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int main(){
	int n;
	cin>>n;
	int a=0;
	REP(i,n){
		char p;
		int x;
		cin>>p>>x;
		if(p=='('){
			a+=x;
		}else{
			a-=x;
			if(a<0){
				cout<<"NO"<<endl;
				exit(0);
			}
		}
	}
	cout<<(a==0?"YES":"NO")<<endl;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
	int t, x, y;
	t = x = y = 0;
	int n;
	cin >> n;
	rep(i, n){
		int ti, xi, yi;
		cin >> ti >> xi >> yi;
		int le = fabs(xi-x)+fabs(yi-y);
		if(le > ti-t){
			cout << "No" << endl;
			return 0;
		}
		if((ti-t) % 2 == 1){
			if(le % 2 == 0){
				cout << "No" << endl;
				return 0;
			}
		}else{
			if(le % 2 == 1){
				cout << "No" << endl;
				return 0;
			}
		}
		t = ti;
		x = xi;
		y = yi;
	}
	cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr ll MOD = 998244353LL;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}
ll modpow(ll a, ll p) {
    if(a == 0) {
        return 0;
    }
    if(p == 0)
        return 1;
    if(p % 2 == 0) {
        ll halfp = p / 2;
        ll half = modpow(a, halfp);
        return half * half % MOD;
    } else {
        return a * modpow(a, p - 1) % MOD;
    }
}

int main() {
    ll N;
    cin >> N;
    vector<ll> D(N);
    REP(i, N) { cin >> D[i]; }
    if(D[0] != 0) {
        cout << 0 << endl;
        return 0;
    }
    for(ll i = 1; i < N; i++) {
        if(D[i] == 0) {
            cout << 0 << endl;
            return 0;
        }
    }

    map<ll, ll> pcnt;
    for(ll i = 1; i < N; i++) {
        pcnt[D[i]]++;
    }
    ll ans = 1LL;
    for(ll i = 2; i < N; i++) {
        if(pcnt[i] > 0 and pcnt[i - 1] <= 0) {
            cout << 0 << endl;
            return 0;
        }
    }
    pcnt[0] = 1;
    // cout << "hoge" << endl;
    for(auto x : pcnt) {
        if(x.first == 0) {
            continue;
        }
        if(x.second == 0) {
            continue;
        }

        ans *= modpow(pcnt[x.first - 1], x.second);
        ans %= MOD;
    }
    ans %= MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7296
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
N, A, B, C = map(int, input().split())
lA = [1]*(N+1)
lB = [1]*(N+1)
lAplusB = [1]*(2*N+1)
for i in range(N):
  lA[i+1] = lA[i]*A%MOD
  lB[i+1] = lB[i]*B%MOD
for i in range(2*N):
  lAplusB[i+1] = lAplusB[i]*(A+B)%MOD
ans = 0
for M in range(N, 2*N):
  num = comb(M-1, N-1) * (lA[N]*lB[M-N] + lA[M-N]*lB[N]) * M * 100
  num %= MOD
  den = lAplusB[M+1]
  ans += num*pow(den, MOD-2, MOD)
  ans %= MOD
print(ans)

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

int main() {
  int N,A,y;
  cin >> N>>A;
 y=N%500;
  N<500;
  if (y==0 ||y<=A||N<=A){
    cout << "Yes" <<endl;
  }
    else if (A<y||A<N){
  cout << "No"<<endl;
    }
}

Measured memory_bytes: 256
//ABC119 二分探索の練習
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b){return (a%b==0) ? b:gcd(b,a%b); }
ll N,A[100000];
int main(void){
    cin >>N;
    rep(i,N)cin >> A[i];
    ll g=A[0];
    rep(i,N){
        g = gcd(g,A[i]);
    }
    cout << g << endl;
}


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

typedef long long int ll;
const int maxn = 1e5 + 10;
void solved(){
	int k,a,b;cin>>k>>a>>b;
	for(int i = a; i <= b; i++){
		if(i % k == 0){
			cout<<"OK"<<endl;return;
		}
	}	
	cout<<"NG"<<endl;
}
int main(){
	solved();
	return 0;
} 

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
 
void fact(int n,int m){
  if(n==0){
    cout<<(m*(m-1))/2;
  }
  else if(m==0){
    cout<<(n*(n-1))/2;
  }
  else{
    cout<<(m*(m-1))/2+(n*(n-1))/2;
  }
}
int main(){
  int m,n;
  cin>>n>>m;
  if(m==1 && n==1)
    cout<<"0";
  else
    fact(n,m);
}

Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [i-1 for i in a] # 入力値を添字に合わせる
path = [] # 通った道を記録。通過済みのところに到達したら記録中止
now = 0
visited = [False] * n

while not visited[now]:
    path.append(now)
    visited[now] = True
    now = a[now]

# sはループの開始地点の添字
# whileループが終わった時点のnowには、堂々巡りの開始地点の添字が入っている
s = path.index(now)
length_loop = len(path) - s

if k < s:
    print(path[k]+1)
else:
    print(path[(k-s)%length_loop+s]+1)


Measured memory_bytes: 108532
#include <stdio.h>

int main(void){
	int x, y;
	scanf("%d %d", &x, &y);
	for(int t = 0; t <= x; t++){
		int k = x - t;
		if(t * 2 + k * 4 == y){
			printf("Yes\n");
			goto end;
		}
	}
	printf("No\n");
end:
	return 0;
}


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

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

	int p = c - a, q = d - b;

	cout << a + p - q << ' ' << b + p + q << ' ' << a - q << ' ' << b + p << endl;

	return 0;
}

Measured memory_bytes: 256
# http://ymduu.hatenablog.com/entry/2019/08/28/201134

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = [int(input()) for _ in range(N)]

    ret = A[0] - 1
    div = 2
    for x in A[1:]:
        if x == div:
            div += 1
            continue
        ret += (x - 1) // div
    print(ret)


if __name__ == '__main__':
    main()

# if x % div == 0:
#     ret += (x - div*2) // div + (div * 2 // (div+1))
#     # div未満を残せるので、次以降もdivが使える
# else:
#     ret += (x - 1) // div
#     # この方法だと、divに一致するものが来るまでは、div未満で抑えられる
# 結局ret += (x - 1) // div回数だけ増える
# div==xのときはどうしようもないので、div+1して避ける


Measured memory_bytes: 7888
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b; return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b; return true;
    }
    return false;
}
#define pb push_back
#define mp make_pair
#define mt make_tuple

constexpr ll MOD = 1e9 + 7;

int main(void)
{
    cin.sync_with_stdio(false);
    int H, W;
    cin >> H >> W;

    vector<string> cells(H);
    REP(h, H) {
        cin >> cells[h];
    }

    vector<vector<ll>> dp(H + 1, vector<ll>(W + 1));
    REP(h, H) {
        REP(w, W) {
            if (w == 0 && h == 0) {
                dp[h + 1][w + 1] = 1;
            } else {
                if (cells[h][w] == '.') {
                    dp[h + 1][w + 1] = (dp[h][w + 1] + dp[h + 1][w]) % MOD;
                }
            }
        }
    }
    // REP(h, H) {
    //     REP(w, W) {
    //         cout << dp[h][w] << " ";
    //     }
    //     cout << endl;
    // }

    cout << dp[H][W] << endl;

    return 0;
}


Measured memory_bytes: 9216
#include <iostream>

using namespace std;

int main(void)
{
    int a, b, k;
    cin >> a >> b >> k;
    for(int i = a; i <= b; i++){
        if((i - a) < k || (b - i) < k){
            cout << i << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main  implements Runnable {

    public static void main(String[] args) {
        new Thread(null, new Main(), "", 64 * 1024 * 1024).start();
    }

    public void run() {
    	FastScanner sc = new FastScanner(System.in);
		//long n = Long.parseLong(sc.next());
		int n = Integer.parseInt(sc.next());
		//long a = Long.parseLong(sc.next());
		//String str = sc.next();
		//char c[] = str.toCharArray();
		//ArrayList<Str_4> lists = new ArrayList<Str_4>();
		//lists = new ArrayList;
		PrintWriter out = new PrintWriter(System.out);
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n];
		for(int i =0; i < n; i++)
		{
			a[i] = Integer.parseInt(sc.next());
		}
		for(int i =0; i < n; i++)
		{
			b[i] = Integer.parseInt(sc.next());
		}
		for(int i =0; i < n; i++)
		{
			c[i] = Integer.parseInt(sc.next());
		}
		Arrays.parallelSort(a);
		Arrays.parallelSort(b);
		Arrays.parallelSort(c);
		int pa = 0;
		int pb = 0;
		int pc = 0;
		int[] pb_d = new int[n];
		for(int i =0; i < n; i++)
		{
			while(pa < n && b[i]>a[pa] )
			{
				pa++;
			}
			pb_d[i]=pa;
		}
		long tmp = 0;
		long ans = 0;
		for(int i =0; i < n; i++)
		{
			while(pb < n && c[i]>b[pb])
			{
				tmp += pb_d[pb];
				pb++;
			}
			ans += tmp;
		}

		out.println(ans);
		out.flush();
    }
    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;
        public FastScanner(String in) {
        	StringReader sr = new StringReader(in);
            reader = new BufferedReader(new BufferedReader(sr));
            tokenizer = null;
        }
        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }
        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
    }
}


Measured memory_bytes: 55076
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    odd, even = [], []
    for i in range(N):
        if i % 2 == 0:
            odd.append(A[i])
        else:
            even.append(A[i])
    if N % 2 == 0:
        return even[::-1] + odd
    else:
        return odd[::-1] + even

if __name__ == '__main__':
    output = main()
    print(" ".join(map(str, output)))

Measured memory_bytes: 29476
/**
 * ?????????????´¢

??????????????? W ??¨?????? T ????????????????????????T ??????????????? W
?????°???????????????????????°?????????????????????????????????

?????? T ????????????????????????????????????????????§????????????????????????????????? Ti
??¨???????????????????????? Ti ?????????????????? W ??¨??????????????????????????°??????????????????

???????????§????????¨?°???????????????\???????????????

Constraints
W????????????????????????10????¶????????????????
T??????????????????????????????????????????1000????¶????????????????
Input
?????????????????? W ????????????????????????

?¶???????????????°????????????????????£??????????????????????????????END_OF_TEXT
??¨??????????????????????????????????????????????????????

Output
?????? W ?????°???????????????????????????

Sample Input
computer
Nurtures computer scientists and highly-skilled computer engineers
who will create and exploit "knowledge" for the new era.
Provides an outstanding computer environment.
END_OF_TEXT
Sample Output
3
 */

#include <algorithm>
#include <iostream>
#include <locale>
#include <sstream>
#include <vector>

/**
 * split a string into a vector at a Delimiter
 * @param   str         sting to be splitted
 * @param   Delimiter
 * @return              vector of splitted strings
 */
std::vector<std::string> splitString(std::string str, char Delimiter) {
  std::vector<std::string> v;
  std::stringstream ss(str);
  std::string Token;

  while (getline(ss, Token, Delimiter)) {
    v.push_back(Token);
  }

  return v;
}

int main(int argc, char const *argv[]) {
  std::string W, T;
  std::cin >> W;
  std::transform(W.begin(), W.end(), W.begin(), tolower);
  unsigned int Count = 0;

  while (true) {
    std::cin >> T;
    if (T == "END_OF_TEXT") {
      break;
    } else {
      std::transform(T.begin(), T.end(), T.begin(), tolower);

      if (T == W) {
        Count++;
      }
    }
  }
  std::cout << Count << std::endl;
  return 0;
}

Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
#define acc(v) accumulate(v.begin(), v.end(), 0)
#define cinv(n,v) rep(i,n) cin >> v[i]
using namespace std;
const int INF = 1e9;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vchar;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
// const lint MOD = 998244353;
int x_pos[4] = {1,0,-1,0}, y_pos[4] = {0,1,0,-1};
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

char upper(char c){
	return c-0x20;
}

char lower(char c){
	return c+0x20;
}

void unique_vector(vector<int>& v){
	sort(all(v));
	v.erase(unique(all(v)), v.end());
}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll dp[110][10];

int main() {
    int n,m;cin>>n>>m;
    if(n==1){
        cout << m << endl;
        return 0;
    }
    vector<int> v;
    for(int i = 2; i*i <= m; i++){
        if(m%i==0)v.push_back(i);
    }
    int ans = 1;
    for(int i=2; i*i<=m; i++){
        if(!(m%i)){
            if(i<=m/n)
                ans = max(ans, i);
            if(m/i<=m/n)
                ans = max(ans, m/i);
            }
        }
    cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define foreach(i,n) for(auto &&i:n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REV(x) reverse(all(x))
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define LOWitr(x, n) lower_bound(all(x), n)
#define UPRitr(x, n) upper_bound(all(x), n)
#define cii(x) int x;cin >> x
#define cill(x) LL x;cin >> x
#define cis(x) string x;cin >> x
#define co(x) cout << x << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define truecheck assert
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef long long int64;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
template<class T,class U>bool chmax(T &a, const U &b){if (a<b){a=b;return true;}return false;}
template<class T,class U>bool chmin(T &a, const U &b){if (b<a){a=b;return true;}return false;}
template<class T,class U>void vcin(T &v, U n){rep(i, n){typename T::value_type a;cin >> a;v.pb(a);}}
const int INF = 1e9, MOD = 1e9 + 7;
const LL LLINF = 1e16;

int main() {
    fastcin();
    cout << fixed << setprecision(10);
    cii(n);
    cii(k);
    VI vi;
    vcin(vi, n);
    int ans = 0;
    rep(i, n){
        if (vi[i]>=k){
            ans++;
        }
    }
    co(ans);
    return 0;
}

Measured memory_bytes: 892
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <functional>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// #define int long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = (((1<<30)-1)<<1)+1;
const int nINF = 1<<31;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<char, int> pci;

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

const int N = 60, M = 1e9+7;
int n, a[N][N];
ll k;

int add(int x, int y) {return (x+y)%M;}
int mult(int x, int y) {return ((ll)x*y)%M;}

struct Mat {
	int r, c;
	vector<vector<int>> data;
	Mat(int _r, int _c, int** arr) : r(_r), c(_c) {
		data.resize(_r, vector<int>(_c));
		REP(i, _r) REP(j, _c) data[i][j] = a[i][j];
	}

	Mat(int _r, int _c) : r(_r), c(_c) {
		data.resize(_r, vector<int>(_c));
	}

	vector<int>& operator[](int id) {
		return data[id];
	}

	Mat operator*(Mat& oth) {
		assert(oth.r == c);
		Mat res(r, oth.c);
		REP(i, r)
			REP(j, oth.c)
				REP(k, c)
					res[i][j] = add(res[i][j], mult(data[i][k], oth[k][j]));
		return res;
	}

	Mat operator^(ll power) const {
		Mat base = *this, res(r, c);
		REP(i, r) res[i][i] = 1;
		while(power) {
			if(power & 1) res = res*base;
			base = base*base;
			power >>= 1;
		}
		return res;
	}
};

int fastPow(int base, int power) {
    int res = 1;
    while(power) {
        if(power & 1) res *= base;
        base *= base;
        power >>= 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);
    cin >> n >> k;
    REP(i, n) REP(j, n) cin >> a[i][j];
    Mat m(n, n, (int**)a);
    m = m^k;
    int ans = 0;
    REP(i, n) REP(j, n) ans = add(ans, m[i][j]);
    cout << ans << endl;

    return 0;
}

// Easy things to check:
// - LONG LONGS (WA)
// - const int N is correct (WA, RTE)
// - .size()-k underflow (WA, RTE, TLE)
// - small n edge cases (WA)

// Rare mistakes made in the past:
// - division by 0 (WA)
// - integer division (WA)
// - setprecision (WA)
// - INF not big enough using ll (WA)
// - setting min to 0 instead of -INF (WA)
// - outputting debug (WA)
// - allocating too much memory (locRTE, MLE)
// - stack size (locRTE)


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

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 RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int X, A;
    cin >> X >> A;
    cout << (X < A ? 0 : 10) << endl;
}


Measured memory_bytes: 256
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
def segfunc(x, y):
    return max(x,y)
#################

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る ※区間注意
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
seg = SegTree([0 for i in range(300050)], segfunc, ide_ele)

answer = 0
for i in range(N):
    
    under = max(0,A[i]-K)
    upper = min(300050,A[i]+K)
    now = seg.query(under, upper+1)
    seg.update(A[i], now+1)
    
print(seg.query(0,300001))

Measured memory_bytes: 128372