akhauriyash/Code-Regression huggingface dataset:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


def main():
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        y = []
        for j in range(a):
            y.append(list(map(int,input().split())))
        xy.append(y)

    #print(xy)
    #print(xy[0])
    #print(len(xy[0]))

    ans = 0
    for i in range(2**n):   # パターンが2のn乗
        flag = False
        count = 0
        for j in range(n):                # n人

            if i >> j & 1 == 1:                         #はなす人が正直者
                for k in range(len(xy[j])):
                    if (i >> xy[j][k][0]-1 & 1) != xy[j][k][1]:        # 違っていたら
                        flag = True
                        break

                if flag == True:
                    break

                else:
                    count += 1


        if flag == False:
            ans = max(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

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

int main() {
  int K;
  cin >>K;
  vector<int> S={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout << S.at(K-1) <<endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
const int mod=1000000007;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;cin >> n;
	if(n==0){
		cout << 0 << endl;
		return 0;
	}
	string ans="";
	while(n!=0){
		if(n%2==0){
			ans='0'+ans;
		}
		else{
			ans='1'+ans;
		}
		if(n<0) n--;
		n/=-2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<ll> dqll;

#define MOD 1000000007

int main() {
  ll N;

  cin >> N;

  ll res = N % 11;
  ll ans = 2*(N / 11);
  if (res == 0) {
  } else if(res <= 6){
    ans++;
  } else{
    ans += 2;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    while(true){
      int H = sc.nextInt();
      int W = sc.nextInt();
      if(H==0 && W==0){
        break;
      }else{
        for(int i=0;i<H;i++){
          for(int j=0;j<W;j++){
            System.out.print("#");
          }
          System.out.println();
        }
        System.out.println();
      }
    }
  }
}


Measured memory_bytes: 34844
// https://atcoder.jp/contests/abc171/tasks/abc171_f

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define FORR(i,b,e) for(int i=(b); i>=(int)(e); i--)

#define DEBUG 1
#if DEBUG
  #define _GLIBCXX_DEBUG
  #define DUMP(a) REP(_i, a.size()) cout << a[_i] << (_i + 1 == a.size() ? "\n" : " ")
  #define DUMP2D(b) REP(_j, b.size()) DUMP(b[_j]); cout << endl
#else
  #define DUMP(a)
  #define DUMP2D(b)
#endif

//------------------------------------------------------------------------------
ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) {
      res = res * x % mod;
    }
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}

ll mod_inverse(ll x, ll mod) {
  return mod_pow(x, mod - 2, mod);
}

//------------------------------------------------------------------------------
const int F_MAX = 2e6;

ll fact[F_MAX + 1];
ll fact_inv[F_MAX + 1];

void init_fact(int m) {
  fact[0] = 1;
  FOR(i, 1, F_MAX) fact[i] = fact[i - 1] * i % m;
  fact_inv[F_MAX] = mod_inverse(fact[F_MAX], m);
  FORR(i, F_MAX - 1, 0) fact_inv[i] = fact_inv[i + 1] * (i + 1) % m;
}

ll mod_comb_fast(ll n, ll k, ll mod) {
  if (n < 0 || k < 0 || n < k) return 0;
  ll a = fact[n];
  ll b = fact_inv[k] * fact_inv[n - k] % mod;
  ll ret = a * b % mod;
  // printf("%lld_C_%lld = %lld\n", n, k, ret);
  return ret;
}

//------------------------------------------------------------------------------
const int K_MAX = 1e6;
const ll MOD = 1e9+7;

int K;
string S;

int N, L;

int main() {
  cin >> K;
  cin >> S;

  L = S.size();
  N = L + K;
  init_fact(MOD);

  ll ans = 0;
  ll base = mod_pow(26, K, MOD);
  ll mul = 25 * mod_inverse(26, MOD) % MOD;
  REP(i, K + 1) {
    ll add = base * mod_comb_fast(L - 1 + i, L - 1, MOD) % MOD;
    ans = (ans + add) % MOD;
    base = base * mul % MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 35580
N = int(input())
ans = 0

#奇数判定
for i in range(1, N+1, 2):
    cnt = 0
    #約数判定
    for j in range(1, i+1):
        if i % j == 0:
            cnt += 1
        
    if cnt == 8:
        ans += 1

print(ans)
        



Measured memory_bytes: 2940
#include <stdio.h>

int min(int a, int b) {
  return a < b ? a : b;
}

int main(void) {
  int i, j, k, n, t, inf = 10e8;
  scanf("%d", &n);
  int w[n + 1], b[n + 1], wt[n + 1], bt[n + 1];
  int dp[n + 1][n + 1], wm[n + 1][n + 1], bm[n + 1][n + 1];
  for(i = 0; i <= n; ++i) wt[i] = 0, bt[i] = 0;
  for(i = 0; i <= n; ++i) for(j = 0; j <= n; ++j) dp[i][j] = inf;
  char c;
  for(i = 0; i < 2 * n; ++i) {
    scanf("%c", &c);
    scanf("%c%d", &c, &t);
    if(c == 'B') {
      b[t] = i;
      for(j = 0; j <= n; ++j) bm[t][j] = bt[t] + wt[j];
      for(j = t; j <= n; ++j) bt[j]++;
    } else {
      w[t] = i;
      for(j = 0; j <= n; ++j) wm[t][j] = wt[t] + bt[j];
      for(j = t; j <= n; ++j) wt[j]++;
    }
  }
  /*for(i = 1; i <= n; ++i) {
    for(j = 0; j <= n; ++j) printf("%d ", bm[i][j]);
    printf("\n");
  }
  printf("\n");
  for(i = 1; i <= n; ++i) {
    for(j = 0; j <= n; ++j) printf("%d ", wm[i][j]);
    printf("\n");
  }*/
  dp[0][0] = 0;
  for(i = 1; i <= n; ++i) {
    dp[0][i] = dp[0][i - 1] + b[i] - bm[i][0];
    dp[i][0] = dp[i - 1][0] + w[i] - wm[i][0];
  }
  for(i = 1; i <= n; ++i) {
    for(j = 1; j <= n; ++j) {
      dp[i][j] = min(dp[i - 1][j] + w[i] - wm[i][j], dp[i][j - 1] + b[j] - bm[j][i]);
    }
  }
  printf("\n");
  /*for(i = 0; i <= n; ++i) {
    for(j = 0; j <= n; ++j) printf("%d ", dp[i][j]);
    printf("\n");
  }*/
  printf("%d", dp[n][n]);
  return 0;
}

Measured memory_bytes: 47104
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2
{
    class Program
    {
        static void Main(string[] args)
        {
            // スペース区切りの整数の入力
            string[] x = Console.ReadLine().Split(' ');
            int a = int.Parse(x[0]);
            int b = int.Parse(x[1]);
            int sum = 0;


            for (int i = 0; i <= 1; ++i)
            {
                if (a <= b)
                {
                    sum += b;
                    b -= 1;
                }
                else
                {
                    sum += a;
                    a -= 1;
                }

            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 11092
#include<stdio.h>
int main()
{
    int arr[10],i,temp,j;
    for( i=0 ; i<10 ; i++ )
    {
        scanf("%d",&arr[i]);
    }
    for( i=0 ; i<10 ; i++ )
    {
        for( j=0 ; j<10-i ; j++ )
        {
            if(arr[j]>arr[j+1])
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    for( i=9 ; i>=7 ; i-- )
    {
        printf("%d\n",arr[i]);
    }
    return 0;
}

Measured memory_bytes: 600
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N,K;
	static int arr[];
	public static void main(String[] args) throws NumberFormatException, IOException  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		br.close();
		arr = new int[N];
		for(int i= 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int zero = N;
		for(int i= 0; i < N; i++) {
			if(arr[i] >= 0) {
				zero = i;
				if(arr[i] == 0) {
					K--;
				}
				break;
			}
		}
		int min = 300000000;
		int tempmin;
		for(int i = 0 ; i <= K && i <= zero; i++) {
			if((zero-1+K-i) >= N) {
				continue;
			}
			int left = 0; 
			int right = 0;
			if(i > 0) {
				left = arr[zero-i]*(-1);
			}
			if(K-i > 0) {
				right = arr[zero-1+K-i];
			}
			tempmin = Math.min(left+2*right, 2*left+right);
			min = Math.min(min, tempmin);
			
		}
		System.out.println(min);
	}
	
	
}

Measured memory_bytes: 37388
#define _USE_MATH_DEFINES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1000000007; 
const int INF = 1000000000; //1e9
const int NIL = -1;
const long long LINF = 1000000000000000000; // 1e18
const long double EPS = 1E-10;

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

void dfs(int v, int prv, 
              std::vector<std::vector<long long>>& dp,
              std::vector<std::vector<int>>& G){
    if(dp[v][0] != -1) return;
    dp[v][0] = dp[v][1] = 1;
    for(int e: G[v]){
        if(e == prv) continue;
        dfs(e, v, dp, G);
        dp[v][0] = dp[v][0] * dp[e][1] % MOD;
        dp[v][1] = dp[v][1] * (dp[e][0] + dp[e][1]) % MOD;
    }
    return;
}




int main(){
    int N; std::cin >> N;
    //dp[i][j] := iを根とする部分木でj:0根が黒, 1白
    std::vector<std::vector<long long>> dp(N, std::vector<long long>(2, -1));
    std::vector<std::vector<int>> G(N);
    {
        int x, y;
        for(int i(0), i_len(N-1); i < i_len; ++i){
            std::cin >> x >> y;
            --x; --y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
    }
    dfs(0, -1, dp, G);
    std::cout << (dp[0][0] + dp[0][1]) % MOD << std::endl;
    return 0;
}


Measured memory_bytes: 18176
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include <bits/stdc++.h>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int         long long
#define ll          long long
#define ld	    long double
#define pb          push_back
#define pp	    pop_back()
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define mp          make_pair
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),a.rend()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define endl        '\n'
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repj(j,a,b) for(ll j=a;j<b;j++)
#define lexistr(x,y)      lexicographical_compare(x.begin(),x.end(),y.begin(),y.end())
#define IOS	    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef tree<ll,null_type,less<ll>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;

//CONSTANTS----------------------------------
#define PI 	    3.141592653589793238462643
const ll hell=1000000007;
const ll mod=1000000007;
//function-----------------------------------
ll GCD(ll a , ll b)
{
    if(b==0)
        return a;
    else
        return GCD(b,a%b);
}
ll LCM(ll a, ll b)
{
    return a*(b/GCD(a,b));
}
bool isPrime(ll n) {

    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ll i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}
ll fact(ll n)
{
    ll f=1;
    for(ll i=2;i<=n;i++)
	f=f*i;
    return f;
}
ll power(ll a,ll b)
{
  if(b==0)return 1;
  if(b==1)return a;
  ll t=power(a,b/2);
  t%=hell;
  t*=t;
  t%=hell;
  if(b%2)return (t*a)%hell;
  else
     return t;
}
//CODE------------------------------------------
ll solve()
{
    ll n; cin>>n;
    string s,x; cin>>s;
    rep(i,0,n) x+=s[i];
    rep(i,0,3) x.pb('.');
    if(sz(s)<=n) cout<<s;
    else cout<<x;
    return 0;
}
//MAIN------------------------------------------
signed main(){
    IOS
    #ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3668
import bisect
N = int(input())
P = list(map(int, input().split()))

count = 0
last_min = P[0]
for i in range(N):
    last_min = min(last_min, P[i])
    if i == 0:
        count += 1
    elif last_min == P[i]:
        count += 1
print(count)

Measured memory_bytes: 24744
#include <iostream>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <numeric>

using namespace std;

using ll = long long;
using vll = vector<ll>;

#define loopi(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define loop(i, n) for (int i = 0; i < (int)n; i++)
#define loopeq(i, n) for (int i = 0; i <= (int)n; i++)
#define rloopi(i, a, b) for(int i = (int)a - 1; i >= (int)b; i--)
#define rloop(i, n) for (int i = (int)n - 1; i >= 0; i--)
#define rloopeq(i, n) for (int i = (int)n - 1; i >= 1; i--)
#define all(a) (a).begin(), (a).end()

void prime_factors(ll n)
{  
    ll sum = 0;
    ll divide2 = 2;
    while (n % divide2 == 0)  
    {
        sum++;
        n = n / divide2;
        divide2 *= 2;
    }
    while (n % 2 == 0) {
        n /= 2;
    }
  
    for (ll i = 3; i <= sqrt(n) + 1; i = i + 2)  
    {
        ll divide = i;
        while (n % divide == 0)  
        {  
            sum++;
            n = n / divide;
            divide *= i;
        }  
        while (n % i == 0) {
            n /= i;
        }
    }  
  
    if (n > 2) {
        sum++;
    }
    cout << sum << endl;
}  

int main() {
    ll n; cin >> n;
    prime_factors(n);
}

Measured memory_bytes: 3688
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int n,m,cnt=0,o,p,aa[220000],cntl=0,ab[220000];
pair<int,int> pp[220000];
string s,ss[220000];
char c,cc[5000][5000]={};
queue<int> que;
signed main(){
    cin>>n>>m;
    rep(i,m){
        cin>>aa[i];
        rep(j,aa[i]){
            cin>>o;
            ab[o]=1;
        }
    }
    rep(i,n){
        if(ab[i+1]==0){
            cnt++;
        }
    }
    cout<<cnt;
}

Measured memory_bytes: 10524
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  int n;
  cin>>n;
  vector<int> v(n);
  rep(i,n){
    cin>>v.at(i);
  }
  sort(v.begin(), v.end(), std::greater<int>());
  int s=1;
  rep(j,n-1){
    if(v.at(j)>v.at(j+1)){
      s++;
    }
  }
  cout<<s;
}

Measured memory_bytes: 256
#include <cstdio>
typedef long long ll;
ll gcd(ll a,ll b){
	if(b == 0){
		return a;
	}
	return gcd(b,a%b);
}
ll lcm(ll a,ll b){
	return a*b/gcd(a,b);
}

int main(){
	int a[3],m[3];
	while(scanf("%d%d%d%d%d%d",&a[0],&m[0],&a[1],&m[1],&a[2],&m[2]), a[0] != 0){
		int t[3];
		for(int i = 0; i < 3; i++){
			t[i] = 1;
			int x = 1;
			while(x = (a[i]*x)%m[i],x != 1){
				t[i]++;
			}
		}
		printf("%lld\n",lcm(t[0],lcm(t[1],t[2])));
	}
	return 0;
}



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

typedef long long ll;
int n,m,a[55],b[55],c[55],d[55];
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n >> m;
    for(int i=1;i<=n;++i)
    {
    	cin >> a[i] >> b[i];
    }
    for(int i=1;i<=m;++i)
    {
    	cin >> c[i] >> d[i];
    }
    for(int i=1;i<=n;++i)
    {
    	int mind=1000000000,mini=-1;
    	for(int j=1;j<=m;++j)
    	{
    		if(abs(a[i]-c[j])+abs(b[i]-d[j])<mind)
    		{
    			mind=abs(a[i]-c[j])+abs(b[i]-d[j]);
    			mini=j;
    		}
    	}
    	cout << mini << "\n";
    }
    return 0;                             
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main()
{
    FASTINOUT;
    ll d,t,s;
    cin>>d>>t>>s;
    if (d<=t*s)
        cout<<"Yes\n";
    else
        cout<<"No\n";
    return 0;
}


Measured memory_bytes: 3648
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int ab = sc.nextInt();
        int bc = sc.nextInt();
        int ca = sc.nextInt();

        int res = ab * bc / 2;
        System.out.println(res);
    }
}


Measured memory_bytes: 21844
let () =
  let open Queue in
  let m = ref 0 in
  let q = create () in
  let rec read () =
    let n = read_int () in
    m := max !m n;
    push n q;
    read ()
  in
  try read() with _ -> begin
    incr m;
    let a = Array.make !m false in a.(0) <- true;
    let dp = Array.make !m 0 in
    let rec aux i j =
      if i*j < !m then (a.(i*j) <- true; aux i (j + 1))
    and make i =
      if i < !m then begin
        if not a.(i) then aux i 2;
        dp.(i) <- dp.(i - 1) + (if a.(i) then 0 else 1);
        make (i + 1)
      end
    in
    make 2;
    iter (fun n -> Printf.printf "%d\n" dp.(n)) q
  end

Measured memory_bytes: 18092
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int d[100][101];
bool b[100];
vector<pair<int,int>> g[100];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m,l,k,a,h;
	while(1){
		cin >> n >> m >> l >> k >> a >> h;
		if(n==0)break;
		for(int i=0;i<n;i++){
			b[i]=0;
			g[i].clear();
			for(int j=0;j<=100;j++){
				d[i][j]=1e9;
			}
		}
		for(int i=0;i<l;i++){
			int t; cin >> t;
			b[t]=1;
		}
		for(int i=0;i<k;i++){
			int x,y,t; cin >> x >> y >> t;
			g[x].push_back({y,t});
			g[y].push_back({x,t});
		}
		priority_queue<pair<int,pair<int,int>>> q;
		q.push(make_pair(0,make_pair(a,m)));
		d[a][m]=0;
		while(q.size()){
			auto p=q.top(); q.pop();
			if(d[p.second.first][p.second.second]!=-p.first)continue;
			for(auto t:g[p.second.first]){
				if(p.second.second-t.second<0)continue;
				if(b[t.first]){
					for(int i=p.second.second-t.second;i<=m;i++){
						if(d[t.first][i]>-p.first+t.second+i-(p.second.second-t.second)){
							d[t.first][i]=-p.first+t.second+i-(p.second.second-t.second);
							q.push(make_pair(-d[t.first][i],make_pair(t.first,i)));
						}else break;
					}
				}
				else if(d[t.first][p.second.second-t.second]>-p.first+t.second){
					d[t.first][p.second.second-t.second]=-p.first+t.second;
					q.push(make_pair(-d[t.first][p.second.second-t.second],make_pair(t.first,p.second.second-t.second)));
				}
			}
		}
		int res=1e9;
		for(int i=0;i<=m;i++){
			res=min(res,d[h][i]);
		}
		if(res==1e9)printf("Help!\n");
		else printf("%d\n",res);
	}
}


Measured memory_bytes: 3468
#include <iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
char a[21][21];
int dist[21][21];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	int n, m; cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == '#')continue;
			queue<pair<int, int>> q;
			memset(dist, -1, sizeof(dist));
			dist[i][j] = 0;
			q.push({ i,j });
			while (!q.empty()) {
				int x = q.front().first;
				int y = q.front().second; q.pop();
				for (int k = 0; k < 4; k++) {
					int nx = x + dx[k];
					int ny = y + dy[k];
					if (nx >= 0 && ny >= 0 && nx < n && ny < m && dist[nx][ny] == -1 && a[nx][ny] != '#') {
						dist[nx][ny] = dist[x][y] + 1;
						q.push({ nx,ny });
						ans = max(ans, dist[nx][ny]);
					}
				}
			}
		}
	}

	cout << ans << '\n';



}

Measured memory_bytes: 256
#include <cstdio>
int main(void){
    int a,b,c,d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    if (a+b < c+d)
    {
        printf("Right");
    }
    else if (a+b > c+d)
    {
        printf("Left");
    }
    else
    {
        printf("Balanced");
    }
    return 0;
    
}


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

int main(){
    
    string str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    str = str + str + str;
    /*for(int i = 0; str[i] != '\0'; i++){
        cout << i << ":" << str[i] << endl;
    }*/
    while(1){
        int n; cin >> n;
        if(!n) break;
        vector<int> key(n);
        for(int i = 0; i < n; i++){
            cin >> key[i];
        }

        string s; cin >> s;
        int j = 0;
        int idx;
        for(int i = 0; i < s.size(); i++){
            for(int k = 52; k <= 103; k++){
                if(s[i] == str[k]) idx = k;
            }
            //cout << idx << " " << key[j];
            idx -= key[j];
            s[i] = str[idx];
            j++;
            if(j == n) j = 0;
        }

        cout << s << endl;
    }

    return 0;
}

Measured memory_bytes: 3228
#include <stdio.h>
#include <string.h>
 
int main(void){
  int a,b,c,d;
  int x = 0;
  int y = 0;
  scanf("%d %d",&a,&b);
  scanf("%d %d",&c,&d);
 
  x=a-c;
  y=b-d;
  
  printf("%d",x*y);
 
  return 0;
}


Measured memory_bytes: 128
import java.io.InputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.math.BigInteger;

public class Main{

static PrintWriter out;
static InputReader ir;

static void solve(){
 int q=ir.nextInt();
 Arrays.fill(dp,-1);
 while(q-->0){
  int n=ir.nextInt();
  out.println(dfs(n));
 }
}

static int[] dp=new int[1000001];

public static int dfs(int a){
 if(dp[a]>=0) return dp[a];
 if(a<10) return dp[a]=0;
 int ma=0;
 int base=10;
 for(int i=1;i<Integer.toString(a).length();i++){
  ma=Math.max((int)(a/base)*(a%base),ma);
  base*=10;
 }
 return dp[a]=dfs(ma)+1;
}

public static void main(String[] args) throws Exception{
 ir=new InputReader(System.in);
 out=new PrintWriter(System.out);
 solve();
 out.flush();
}

static class InputReader {
 private InputStream in;
 private byte[] buffer=new byte[1024];
 private int curbuf;
 private int lenbuf;

 public InputReader(InputStream in) {this.in=in; this.curbuf=this.lenbuf=0;}
 
 public boolean hasNextByte() {
  if(curbuf>=lenbuf){
   curbuf= 0;
   try{
    lenbuf=in.read(buffer);
   }catch(IOException e) {
    throw new InputMismatchException();
   }
   if(lenbuf<=0) return false;
  }
  return true;
 }

 private int readByte(){if(hasNextByte()) return buffer[curbuf++]; else return -1;}
 
 private boolean isSpaceChar(int c){return !(c>=33&&c<=126);}
 
 private void skip(){while(hasNextByte()&&isSpaceChar(buffer[curbuf])) curbuf++;}
 
 public boolean hasNext(){skip(); return hasNextByte();}
 
 public String next(){
  if(!hasNext()) throw new NoSuchElementException();
  StringBuilder sb=new StringBuilder();
  int b=readByte();
  while(!isSpaceChar(b)){
   sb.appendCodePoint(b);
   b=readByte();
  }
  return sb.toString();
 }
 
 public int nextInt() {
  if(!hasNext()) throw new NoSuchElementException();
  int c=readByte();
  while (isSpaceChar(c)) c=readByte();
  boolean minus=false;
  if (c=='-') {
   minus=true;
   c=readByte();
  }
  int res=0;
  do{
   if(c<'0'||c>'9') throw new InputMismatchException();
   res=res*10+c-'0';
   c=readByte();
  }while(!isSpaceChar(c));
  return (minus)?-res:res;
 }
 
 public long nextLong() {
  if(!hasNext()) throw new NoSuchElementException();
  int c=readByte();
  while (isSpaceChar(c)) c=readByte();
  boolean minus=false;
  if (c=='-') {
   minus=true;
   c=readByte();
  }
  long res = 0;
  do{
   if(c<'0'||c>'9') throw new InputMismatchException();
   res=res*10+c-'0';
   c=readByte();
  }while(!isSpaceChar(c));
  return (minus)?-res:res;
 }

 public double nextDouble(){return Double.parseDouble(next());}

 public int[] nextIntArray(int n){
  int[] a=new int[n];
  for(int i=0;i<n;i++) a[i]=nextInt();
  return a;
 }

 public long[] nextLongArray(int n){
  long[] a=new long[n];
  for(int i=0;i<n;i++) a[i]=nextLong();
  return a;
 }

 public char[][] nextCharMap(int n,int m){
  char[][] map=new char[n][m];
  for(int i=0;i<n;i++) map[i]=next().toCharArray();
  return map;
 }
}
}

Measured memory_bytes: 29028
N = int(input())
S = input().split(" ")
S = [int(c) for c in S]

lock = [0] * N

# print(N, S)


ans = True

for i in range(0, N - 1):
    if S[i + 1] == S[i]:
        lock[i+1] = lock[i]

    if S[i + 1] - S[i] >= 0:
        # print("そのまま")
        pass
    elif S[i + 1] - S[i] >= -1 and lock[i] == 0:
        # print("小さく")
        S[i] -= 1
        lock[i+1] = 1
    else:
        # print("勝ち目なし")
        ans = False
        break

# print(lock)
# print(S)
if ans:
    print("Yes")
else:
    print("No")


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

int main(){
  int n;
  cin>>n;
  vector<int> x(n);
  vector<int> y(n);
  for(int i=0;i<n;i++){
    int a,b;
    cin>>a>>b;
    x[i] = a+b;
    y[i] = a-b;
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());

  int ans = max(abs(x[n-1]-x[0]),abs(y[n-1]-y[0]));
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 4824
#include<bits/stdc++.h>
#define boost ios::sync_with_stdio(false); cin.tie(0)
#define ll              long long int
#define ld              long double
#define mk              make_pair
#define pb              push_back
#define f               first
#define s               second
#define fo(i,a,b)       for(i=a;i<b;i++)
#define foe(i,a,b)      for(i=a;i<=b;i++)
#define all(x)          x.begin(),x.end()
// #define vi               vector<int>
#define vl              vector <long long int>
// #define pii          pair <int,int>
#define pll             pair <long long int, long long int>
// #define vpii         vector< pair<int,int> >
#define vpll            vector < pair <long long int,long long int> >
#define MOD             1000000007
using namespace std;
const int inf = INT_MAX;
const ll inf64 = LLONG_MAX;


int main()
{
    boost;
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    vl vect;
    vect.pb(a * c);
    vect.pb(a * d);
    vect.pb(b * c);
    vect.pb(b * d);
    cout << *max_element(all(vect));
    return 0;
}

Measured memory_bytes: 3652
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(dead_code)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;
use num_traits::*;
use superslice::*;
use std::ops::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;


#[fastout]
fn solve() {
    const MOD: usize = 1_000_000_007;
    const INF: usize = std::usize::MAX;
    
    input!{
        n: usize,
        mut p_vec: [usize; n],
    }

    p_vec.sort();

    println!("{}", p_vec[..n-1].iter().sum::<usize>() + p_vec[n-1]/2);
}

fn main() {
    solve()
}

#[cfg(test)]
mod test {
    use super::solve;
}


Measured memory_bytes: 2120
#include<stdio.h>
#include<assert.h>
typedef long long ll;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
void exgcd(ll a,ll b,ll&x,ll&y){
	if(!b){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int phi(int n){
	int i,s=n;
	for(i=2;i*i<=n;i++){
		if(n%i==0){
			s=s/i*(i-1);
			while(n%i==0)n/=i;
		}
	}
	if(n>1)s=s/n*(n-1);
	return s;
}
int pow(int a,ll b,int p){
	int s=1;
	while(b){
		if(b&1)s=(ll)s*a%p;
		a=(ll)a*a%p;
		b>>=1;
	}
	return s;
}
ll solve(int a,int m){
	if(m==1)return 1;
	int p,g,ay;
	ll t,x,y;
	p=phi(m);
	g=gcd(m,p);
	t=solve(a,g);
	ay=pow(a,t,m);
	exgcd(p,m,x,y);
	ay-=t%p;
	if(ay<0){
		x=-x;
		ay=-ay;
	}
	x=((ay/g*x%m+m)%m)*p+t%p;
	t=(ll)m/g*p;
	if(x<t)x+=t;
	return x;
}
void work(){
	int a,m;
	scanf("%d%d",&a,&m);
	printf("%lld\n",solve(a,m));
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)work();
}

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

#define N 10
#define D 30

int lot[N+2][D];
int n,d;

int simulate(int from){
  int x = from;
  for (int i=0; i<d; i++){
    if (lot[x][i]) x--;
    else if (lot[x+1][i]) x++;
  }
  return x;
}

int main(void){
  int st,rwd, flg;
  char c;
  
  while (cin >> n){
    if (n==0) break;
    cin >> st >> rwd >> d;
    st--; rwd--; // 1-orgin -> 0-origin
    for (int i=0; i<d; i++){
      lot[0][i] = lot[n][i] = 0;
      for (int j=1; j<n; j++){
        cin >> c;
        lot[j][i] = c-'0';
      }
    }
    if (simulate(st)==rwd){
      cout << 0 << endl;
    } else {
      flg = 0;
      for (int i=0; i<d; i++){
        for (int j=1; j<n; j++){
          if (flg) continue;
          if (lot[j][i]==0 && lot[j-1][i]==0 && lot[j+1][i]==0){
            lot[j][i]=1;
            if (simulate(st)==rwd){
              cout << (i+1) << " " << (j) << endl;
              flg = 1;
            }
            lot[j][i] = 0;
          }
        }
      }
      if (flg==0) cout << 1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3064
using System;

namespace _174_c
{
    internal class Repsept
    {
        private static void Main(string[] args)
        {
            var k = int.Parse(Console.ReadLine() ?? throw new InvalidOperationException());

            long seven = 7;
            for (var i = 0; i < 1000000; i++)
            {
                var remainder = seven % k;
                if (remainder == 0)
                {
                    Console.WriteLine(i + 1);
                    return;
                }

                seven = remainder * 10 + 7;
            }

            Console.WriteLine(-1);
        }
    }
}

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

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

    switch (op)
    {
        case '+':
            cout << a+b << endl; break;
        case '-':
            cout << a-b << endl; break;
    }    

    return 0;
}


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

int main(){
    ll A,B;
    cin >> A >> B;
    cout << max(A+B,max(A-B,A*B)) << endl;
    return 0;
}

Measured memory_bytes: 764
require 'prime'
require 'set'
require 'tsort'
include Math
ALP = ('a'..'z').to_a
INF = 0xffffffffffffffff
def max(a,b);              a > b ? a : b                              end
def min(a,b);              a < b ?  a : b                             end
def swap(a,b);             a, b = b, a                                end
def gif;                   gets.to_i                                  end
def gff;                   gets.to_f                                  end
def gsf;                   gets.chomp                                 end
def gi;                    gets.split.map(&:to_i)                     end
def gf;                    gets.split.map(&:to_f)                     end
def gs;                    gets.chomp.split.map(&:to_s)               end
def gc;                    gets.chomp.split('')                       end
def pr(num);               num.prime_division                         end
def pr?(num);              Prime.prime?(num)                          end
def digit(num);            num.to_s.length                            end
def array(s,ini=nil);      Array.new(s){ini}                          end
def darray(s1,s2,ini=nil); Array.new(s1){Array.new(s2){ini}}          end
def rep(num);              num.times{|i|yield(i)}                     end
def repl(st,en,n=1);       st.step(en,n){|i|yield(i)}                 end
n = gi
puts max(0,n[0]-n[1])


Measured memory_bytes: 2556
import sys
input = sys.stdin.readline

S = input()
T = input()
q = int(input())
ls = len(S)
lt = len(T)

cs_s = [0] * (ls+1)
cs_t = [0] * (lt+1)
for i in range(ls):
    tmp = 1 if S[i] == 'A' else -1
    cs_s[i+1] = cs_s[i] + tmp
for i in range(lt):
    tmp = 1 if T[i] == 'A' else -1
    cs_t[i+1] = cs_t[i] + tmp

for _ in range(q):
    a, b, c, d = map(int, input().split())
    # print(cs_s[b] - cs_s[a-1], cs_t[d] - cs_t[c-1])
    if (cs_s[b] - cs_s[a-1]) % 3 == (cs_t[d] - cs_t[c-1]) % 3:
        print('YES')
    else:
        print('NO')


Measured memory_bytes: 54104
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input! {
        n: usize,
        k: usize,
        h: [i64; n],
    }
    let mut h = h;
    h.sort();
    let mut sum = vec![0; n];
    for i in 0..n {
        sum[i] = if i < k - 1 {
            std::i64::MAX
        } else {
            -h[1 + i - k] + h[i]
        };
    }
    let ans = sum.iter().min().unwrap();
    println!("{}", ans);
}


Measured memory_bytes: 6524
require 'pp'
h, w = gets.split.map(&:to_i)
n = gets.to_i
a = gets.split.map(&:to_i) # 個数
c = Array.new(h){ Array.new(w) }

n.times do |i|
  a[i]
end

aa = a.flat_map.with_index(1){|x,i|[i] * x}
vec = true
h.times do |i|
  if vec
    0.upto(w-1) do |ii|
      c[i][ii] = aa.pop
    end
  else
    (w-1).downto(0) do |ii|
      c[i][ii] = aa.pop
    end
  end
  vec = !vec
end
puts c.map{|cc|cc.join(' ')}.join("\n")


Measured memory_bytes: 3324
#include<bits/stdc++.h>
#define ll long long
const long double pi=acos(-1);
const int N=2e5+10;
using namespace std;
int arr[N];
int main()
{
  	ll n;
  	ll sum1=0,sum=0;
  	cin>>n;
  	for(int i=0;i<n;i++)
  	{
  		cin>>arr[i];
		sum+=arr[i];	
	}
	if(sum%n==0)
	{
		ll tmp=sum/n;
		for(int i=0;i<n;i++)
		{
			ll k=(arr[i]-tmp);
			sum1+=k*k;
		} 
	}
	else
	{
		ll tmp=sum/n;
		for(int i=0;i<n;i++)
		{
			ll k=(arr[i]-tmp);
			sum1+=k*k;
		} 
		tmp++;
		ll sum2=0;
		for(int i=0;i<n;i++)
		{
			ll k=(arr[i]-tmp);
			sum2+=k*k;
		} 
		sum1=min(sum1,sum2);
	}
	cout<<sum1<<"\n";
	return 0;
}

Measured memory_bytes: 256
/*
 * ALDS1_4_C.cpp
 *
 *  Created on: Apr 26, 2018
 *      Author: 13743
 */

#include<cstdio>

using namespace std;

const int SIZE = 1045527;
int table[SIZE];

int getKey(char* s) {
	int key = 0;
	int exp = 1;
	for(int i=0; s[i]!='\0'; i++) {
		switch(s[i]) {
		case 'A': key += 4 * exp; break;
		case 'C': key += 3 * exp; break;
		case 'G': key += 2 * exp; break;
		default: key += 1 * exp; break;
		}
		exp *= 5;
	}
	return key;
}

void insert(char* s) {
	int key = getKey(s);
	int hash = key % SIZE;
	while(true) {
		if(table[hash] == 0 || table[hash] == key) {
			table[hash] = key; break;
		}
		hash = (hash + (1 + (key%(SIZE-1)))) % SIZE;
	}
}

bool find(char* s) {
	int key = getKey(s);
	int hash = key % SIZE;
	while(true) {
		if(table[hash] == key) {
			return true;
		}
		else if(table[hash] == 0) {
			return false;
		}
		hash = (hash + (1 + (key%(SIZE-1)))) % SIZE;
	}
	return false;
}

int main() {
	int n;
	scanf("%d", &n);
	char d[10];
	char s[13];
	for(int i=0; i<n; i++) {
		scanf("%s %s", d, s);;
		if(d[0] == 'i') {
			insert(s);
		}
		else {
			if(find(s)) printf("yes\n");
			else printf("no\n");
		}
	}
}





Measured memory_bytes: 6584
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace ConsoleAppAtCoderABC169
{
    class Program
    {
        static void Main(string[] args)
        {
            var ab = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var (a, b) = (ab[0], ab[1]);

            WriteLine(a * b);
        }
    }
}


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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;

template<typename T>
T gcd(T a,T b){
    T c=a,d=b,r;
    do{r=c%d;c=d;d=r;}while(r);
    return c;
}

template<typename T>
T lcm(T a,T b){return a*b/gcd(a,b);}

const ll MOD = 998244353;

ll pow(const ll n, ll r){
    if(r == 0) return 1ll;
    ll ret = pow(n, r / 2);
    ret = (ret * ret) % MOD;
    if(r % 2 != 0) ret = (ret * n) % MOD;
    return ret;
}

class Solver {
  public:
    bool solve() {
        ll N, A, B, K; cin >> N >> A >> B >> K;


        for(ll a = 0; a*A <= K; a ++) {
            if((K - a*A) % B == 0) {
                cerr << a << " : " << (K - a * A) / B << endl;
            }
        }

        // K = KM + left
        // left % A = left % B = 0

        if(A < B) swap(A, B);
        ll l = lcm(A, B);
        ll nKM = max(0ll, K / l - 1);
        ll KM = K - nKM * l;
        assert((K - KM) % A == 0 and (K - KM ) % B == 0);
        // init
        vector<ll> factorial(max({N, A, B}) + 1);
        factorial[0] = 1;
        rep(i, factorial.size() - 1) factorial[i + 1] = (factorial[i] * (i + 1)) % MOD;
        auto nCk = [&] (ll n, ll k) {
            ll q = (factorial[k] * factorial[n - k]) % MOD;
            return factorial[n] * pow(q, MOD - 2) % MOD;
        };
        ll ans = 0;

        ll max_na = KM / A;
        set<pair<ll, ll>> s;
        for(ll na = 0; na <= max_na; na++) {
            ll a = na * A;
            if((KM - a) % B != 0) continue;
            ll nb = (KM - a) / B;
            for(ll k = 0; k <= nKM; k++) {
                ll naa = na + k * (l / A);
                ll nbb = nb + (nKM - k) * (l / B);
                if(naa <= N and nbb <= N) {
                    auto p = pair<ll, ll>(naa, nbb);
                    if(s.count(p)) continue;
                    s.insert(p);
                    // cerr << " -- " << na << " - " << nb << " - " << k << endl;
                    // cerr << naa << " v " << nbb << " : " << nCk(N, naa) * nCk(N, nbb) <<endl;
                    ans += nCk(N, naa) * nCk(N, nbb) % MOD;
                    ans %= MOD;
                }
            }
        }
        cout << ans << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


Measured memory_bytes: 16896
/* Simplicity and Goodness */

#include <bits/stdc++.h>
using namespace std;
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define deb(x) cout << #x << ' ' << x << '\n'
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define per(i,ini) for(int i=ini;i>=0;i--)
#define tc int tt; scn(tt); while(tt --)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int N = 1e5+2;

vector<int> v[N];

int main()
{
	int n, m;
	scn(n); scn(m);

	rep(i, 0, m)
	{
		int a, b;
		scn(a); scn(b);

		v[a].pb(b); v[b].pb(a);
	}

	vector<int> signal(n+1, 0), dist(n+1, 0);
 	
 	int root;

 	queue<int> q;

 	signal[1] = 1; dist[1] = 0;

 	q.push(1);

	while(!q.empty())
	{
		int node = q.front(); q.pop();

		for(int i : v[node])
		if(signal[i] == 0)
		{
			signal[i] = node; dist[i] = dist[node] + 1;
			q.push(i);
		}
		else if(dist[i] > dist[node] + 1)
		{
			signal[i] = node; dist[i] = dist[node] + 1;
		}
	}

	bool ok = 1;

	rep(i, 2, n+1)
	if(signal[i] == 0)
	ok = 0;

	if(!ok)
	puts("No");
	else
	{
		puts("Yes");
		rep(i, 2, n+1)
		prin(signal[i]);
	}

	return 0;
}

Measured memory_bytes: 10640
#include <cmath>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>
#include <stack>

using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> t3;

using namespace std;

int n,m,r;
ll d[300][300];
const ll inf = 1 << 29;

void init()
{
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            d[i][j] = inf;
        }
    }
}

void wr()
{
    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]);
            }
        }
    }
}

void solve()
{
    cin >> n >> m >> r;
    vector<int> ri;
    for(int i = 0;i < r;i++)
    {
        int a;
        cin >> a;
        ri.push_back(a);
    }
    sort(ri.begin(), ri.end());
    init();
    for(int i = 0;i < m;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = c;
        d[b][a] = c;
    }
    wr();
    ll ret = inf;
    do{
        ll sum = 0;
        for(int i = 1;i < ri.size();i++)
        {
            sum += d[ri[i]][ri[i-1]];
        }
        ret = min(sum, ret);
    }while(next_permutation(ri.begin(), ri.end()));
    cout << ret << endl;
}

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

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

int main() {
double x,y,z;
cin >> x >> y >> z;
double a = (x-z)/(y+z);
int ans = a;
cout << ans << endl;
 

 }


Measured memory_bytes: 3660
def insert(num, list)
  list.unshift num
end

def delete(num, list)
  list.delete_at(list.index(num)) if list.include?(num)
  list
end

def deleteFirst(list)
  list.shift
  list
end

def deleteLast(list)
  list.pop
  list
end

def exec_commmand(input, list)
  if input.include?('First') || input.include?('Last')
    send(input, list)
  else
    command, num = input.split(' ')
    send(command, num, list)
  end
end

n = gets.to_i
list = []
n.times do
  list = exec_commmand(gets.chomp, list)
end

puts list.join(' ')


Measured memory_bytes: 81960
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC165
{
    class Program
    {
        static void Main(string[] args)
        {
            a();
        }

        public static void a()
        {
            int k = int.Parse(Console.ReadLine());
            int[] ab = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int a = ab[0], b = ab[1];
            bool flg = false;
            for(int i = a; i <= b; i++)
            {
                if (i % k == 0)
                    flg = true;
            }
            if (flg)
                Console.WriteLine("OK");
            else
                Console.WriteLine("NG");
        }
    }
}


Measured memory_bytes: 28288