akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

//conversion
//------------------------------------------
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();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define LB lower_bound
#define UB upper_bound

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL INF = 1e9;
const LL MOD = 1e9+7;

//other
//-------------------------------------------
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define FI first
#define SE second

//memo
// setprecision()

LL Gcd(LL a, LL b) {
  if (a < b) {
    return Gcd(b,a);
  }
  if (b == 0) {
    return a;
  }
  else {
    return Gcd(b,a%b);
  }
}

LL Lcm(LL a, LL b) {
  LL abd = Gcd(a,b);
  LL x = a / abd, y = b / abd;
  
  return x*y*abd;
}

//-------------------------------------------

int main() {
  int N,K,ans=0;
  cin >> N >> K;
  
  while(N>0){
    N /= K;
    ans++;
  }
  
  if(ans==0)ans++;
  
  cout << ans << endl;
  
  
  return 0;
}

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

const int nmax = 8;
bool graph[nmax][nmax];

int main()
{

    int n, m;
    cin >> n >> m;
    for (auto i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        graph[a][b] = graph[b][a] = true;
    }

    int node[n];
    for (auto i = 0; i < n; i++)
    {
        node[i] = i;
    }

    int ans = 0;

    do
    {
        int num = 0;
        for (auto i = 0; i < n-1; i++)
        {
            if(graph[node[i]][node[i+1]]){
                num += 1;
            }
        }

        if(num == n-1){
            ans += 1;
        }
        
    } while (next_permutation(node + 1, node + n));
    cout << ans << endl;
}

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

#define sd(x) scanf("%d", &(x))
#define pd(x) printf("%d\n",x)
#define sl(x) scanf("%lld", &(x))
#define pl(x) printf("%lld\n",x)
#define nl printf("\n")
#define ll long long 
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define all(v) (v).begin() , (v).end()
#define fill(x) memset(x , 0 , sizeof(x))
#define Pi 3.141592653589793
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug 0
#define Mod 1000000007 

int main(){
	ll x , y;
	sl(x); sl(y);
	if( x % y == 0 ){
		cout << "-1";
	}
	else{
		cout << x;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		
		int mod=(int)Math.pow(10,9)+7;
		
		long power=1;
		
		for(int i=1;i<=n;i++) {
			
			power=(power*i)%mod;
			
		}
		
		System.out.println(power);
		
		sc.close();


	}



}



Measured memory_bytes: 21844
<?php

while(($line = trim(fgets(STDIN))) !== false){
    // ??????????????????
    if($line == 0){
        //echo 'xx??????xx';
        break;
    }
    
    // ???????????°(???????????°???)
    $bank_count = $line;
    
    // ???????????´??°
    $year = trim(fgets(STDIN));
    
    $result_ar = [0, 0];
    for($i=0; $i<$bank_count; $i++){
        $line_in = trim(fgets(STDIN));
        list($b, $r, $t) = explode(' ', $line_in);
        
        if($t == 1){
            // ??????
            $result_tmp = 10000 * (1+$year*$r/100);
        }else{
            // ??????
            $result_tmp = 10000 * ((1+$r/100)**$year);
        }
        
        if($result_ar[1] < $result_tmp){
            $result_ar = [$b, $result_tmp];
        }
    }
    // ????????????????????????
    echo($result_ar[0]."\n");

}

Measured memory_bytes: 15688
# AtCoder
N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    A[i] += A[i-1]

for i in range(1, M+1):
    B[i] += B[i-1]

ans, b_cnt = 0, M
for a_cnt in range(N+1):
    if A[a_cnt] > K:
        continue
    while A[a_cnt] + B[b_cnt] > K:
        b_cnt -= 1
    ans = max(ans, a_cnt+b_cnt)
print(ans)


Measured memory_bytes: 119748
#include <stdio.h>

int main(void){
    
    long A,B,K;

    scanf("%ld %ld %ld",&A,&B,&K);

    if(A >= K){
        A -= K;
    }else if(K <= (A+B)){
        K -= A;
        B -= K;
        A = 0;
    }else {
        A = 0;
        B = 0;
    }

    printf("%ld %ld",A,B);

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) (A).begin(),(A).end()
#define ll long long
const ll mod = 1e9+7;
int main(void){
	int N;
	cin >> N;
	vector<vector<vector<vector<ll>>>> dp(105,vector<vector<vector<ll>>>(4,vector<vector<ll>>(4,vector<ll>(4))));
	//AGCT = 0 1 2 3
	for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)dp[3][i][j][k]=1;
	dp[3][0][1][2]=0;
	dp[3][0][2][1]=0;
	dp[3][1][0][2]=0;
	for(int i=4;i<=N;i++){
		for(int a=0;a<4;a++){//3つ前の文字
			for(int b=0;b<4;b++){//2つ前の文字
				for(int c=0;c<4;c++){//1つ前の文字
					for(int d=0;d<4;d++){//新たに追加する文字
						if(b==0&&c==1&&d==2)continue;
						if(b==0&&c==2&&d==1)continue;
						if(b==1&&c==0&&d==2)continue;
						if(a==0&&c==1&&d==2)continue;
						if(a==0&&b==1&&d==2)continue;
						dp[i][b][c][d]+=dp[i-1][a][b][c];
						dp[i][b][c][d]%=mod;
					}
				}
			}
		}
	}
	ll ans = 0;
	for(int a=0;a<4;a++)for(int b=0;b<4;b++)for(int c=0;c<4;c++){
		ans += dp[N][a][b][c];
		ans%=mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
N = int(input())
X = [int(input()) for _ in range(N)]
if X[0]:
    print(-1)
    exit()

ans = 0
for i in range(1, N):
    if X[i] == X[i-1] + 1:
        ans += 1
    elif X[i] > X[i-1] + 1:
        print(-1)
        exit()
    else:
        ans += X[i]
print(ans)

Measured memory_bytes: 11052
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 305;
const int MOD = (int)1e9 + 7;
int dp[2][N][N];
vector<pii> rule[N];

void add(int &a, int b){
    a += b;
    if(a >= MOD)
        a -= MOD;
}

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    int l, r, x;
    for(int i = 1; i <= m ; i ++ ){
        cin >> l >> r >> x;
        rule[r].push_back(mp(l,x));
    }
    dp[0][0][0] = 1;
    int p3;
    int bit = 1;
    int sum;
    for(int i = 1; i <= n; i ++ ){
        for(int p1 = 0; p1 < i ; p1 ++ ){
            for(int p2 = p1 + (p1 > 0) ; p2 < i; p2 ++ ){
                p3 = i - 1;
                // choose p1
                add(dp[bit][p2][p3], dp[!bit][p1][p2]);
                // choose p2
                add(dp[bit][p1][p3], dp[!bit][p1][p2]);
                // choose p3
                add(dp[bit][p1][p2], dp[!bit][p1][p2]);
            }
        }
        
        for(int p1 = 0 ; p1 < i ; p1 ++ ){
            for(int p2 = 0 ; p2 < i ; p2 ++ ){
                p3 = i;
                for(auto p : rule[i]){
                    sum = 0;
                    sum += (p.fi <= p1);
                    sum += (p.fi <= p2);
                    sum += (p.fi <= p3);
                    if(sum != p.se)
                        dp[bit][p1][p2] = 0;
                }
            }
        }
        for(int p1 = 0 ; p1 < i ; p1 ++ ){
            for(int p2 = 0 ; p2 < i ; p2 ++ ){
                dp[!bit][p1][p2] = 0;
            }
        }
        bit = !bit;
    }
    int res = 0;
    for(int p1 = 0 ; p1 < n ; p1 ++ ){
        for(int p2 = 0 ; p2 < n ; p2 ++ ){
            add(res,dp[!bit][p1][p2]);
        }
    }
    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 1024
A, B, C, D = [int(x) for x in input().split()]
if A<=B<=C<=D:
    ans = 0
elif A<=C<=B<=D:
    ans = B-C
elif C<=A<=B<=D:
    ans = B-A
elif C<=A<=D<=B:
    ans = D-A
elif A<=C<=D<=B:
    ans = D-C
elif C<=A<=D<=B:
    ans = D-A    
else:
    ans = 0
print(ans)


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

int main() {
  string s;
  getline(cin, s);
  for (int i = 0; i < s.size(); i ++) {
    if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 32;
    else if (s[i] >= 'a' && s[i] <= 'z') s[i] -= 32;
  }
  cout << s << endl;
}



Measured memory_bytes: 3216
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,a,b = LI()
    ab = a - b
    h = sorted([I() for _ in range(n)], reverse=True)
    def ff(t):
        bt = b*t
        c = 0
        for w in h:
            if w <= bt:
                return False
            c += (w - bt + ab - 1) // ab
            if c > t:
                return True
        return False

    return bs(ff, 0, sum(h) // b + 1)



print(main())


Measured memory_bytes: 10760
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int N;
string get(const vector<int> &v) {
    cout << "?";
    for (auto vi : v) cout << " " << vi+1;
    cout << endl;
    string res;
    cin >> res;
    return res;
}

string get(int f) {
    vector<int> v(N);
    for (int i = 0; i < N; ++i) v[i] = f + i;
    return get(v);
}

int main() {
    cin >> N;

    if (N == 1) {
        auto tmp = get(0);
        if (tmp == "Red") cout << "! RB" << endl;
        else cout << "! BR" << endl;
        return 0;
    }
    
    int left = 0, right = N;
    string start = get(left);
    while (right - left > 1) {
        int mid = (left + right) / 2;
        if (get(mid) == start) left = mid;
        else right = mid;
    }

    vector<int> base(N-1), nbase;
    for (int i = 0; i < N-1; ++i) base[i] = left + i+1;

    int blue = 0, red = 0;
    string res(N*2, 'U');
    for (int i = 0; i < N*2; ++i) {
        if (i >= base[0] && i <= base.back()) continue;
        base.push_back(i);
        auto tmp = get(base);
        if (tmp == "-1") return 0;
        if (tmp == "Red") {
            res[i] = 'R';
            if (red < N/2) ++red, nbase.push_back(i);
        }
        else {
            res[i] = 'B';
            if (blue < N/2) ++blue, nbase.push_back(i);
        }
        base.pop_back();
    }

    for (auto i : base) {
        nbase.push_back(i);
        auto tmp = get(nbase);
        if (tmp == "-1") return 0;
        if (tmp == "Red") res[i] = 'R';
        else res[i] = 'B';
        nbase.pop_back();
    }
    cout << "! " << res << endl;
    return 0;
}


Measured memory_bytes: 724
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<=n;i++)
typedef int long long ll;
using namespace std;

int main(){
    string s;
    int a,b;
    cin>>a>>b;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(i!=a){
            if(!isdigit(s[i])){
                cout<<"No"<<endl;
                return 0;
            }
        }else{
            if(s[i]!='-'){
                cout<<"No"<<endl;
                return 0;
            }
        }
        
    }
    cout<<"Yes"<<endl;
    

    
return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int p,i,j,a,b,d;string s,u="[<++++++++++>-]>",v="+++++",c=">"+v+"[<++++++>-]>"+v+"[<++++++++>-]>"+v+u+v+"+"+u+v+"++"+u+v+"+++"+u+v+"++++"+u+v+v+u+v+v+"+"+u+v+v+"++"+u+"<<<<<<<<<<<";main(){for(cin>>s;i<s.length();++i){a=s[i]/10-3,b=a-p,p=a,d=s[i]-a*10-30;for(j=b>0?b:-b;j--;)c+=b>0?62:60;for(j=d;j--;)c+=43;c+=46;for(j=d;j--;)c+=45;}cout<<c<<endl;}

Measured memory_bytes: 1252
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int m;
  int month = 12;
  int day = 30;
  int ans = -1;
  cin >> m;
  if(m < 1 || m > 23){
   	ans = 0;
  }else{
  	ans = 24 * 2 - m;  
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include<stdio.h>
int saidai(int ,int);
int main(void)
{
	int a,b;
	long long m,n;
	
	while(scanf("%d %d",&a,&b)!=EOF)
	{
		m=saidai(a,b);
		n=(a/m)*b;
		printf("%d %d\n",m,n);
	}
	return 0;
}
int saidai(int a,int b)
{
	while(a!=0&&b!=0)
	{
		if(a>b)
		{
			a=a%b;
		}
		else
		{
			b=b%a;
		}
	}
	if(a==0)
	{
		return(b);
	}
	else
	{
		return(a);
	}
}

Measured memory_bytes: 596
/*Anup Ghosh*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi acos(-1)
#define ull unsigned long long
#define nl printf("\n")
#define MAXN 1000005
#define gcd(a,b) __gcd(a,b)
#define pb push_back
#define fio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main()
{
	fio();
	int n;
	cin>>n;
	if(n<30)cout<<"No\n";
	else cout<<"Yes\n";
	return 0;
}


Measured memory_bytes: 3644
def main():
	N = int(input())
	H = [int(x) for x in input().split()]
	
	h_prev = H[0]
	H = H[1:]
	max_counter = 0
	counter = 0
	for h in H:
		if h_prev >= h:
			counter += 1
			if max_counter < counter:
				max_counter = counter
		else:
			if max_counter < counter:
				max_counter = counter
			counter = 0
		h_prev = h
	print(max_counter)

if __name__ == "__main__":
	main()


Measured memory_bytes: 14224
def main():
    input = sys.stdin.readline
    try:
        n = int(input())
        p = 1
        for i in range(1, n + 1):
            p = p * i % (10**9+7)
        print(p)
        
    finally:
        input = None

import sys; sys.setrecursionlimit(50000)
if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PipedInputStream;
import java.util.*;

public class Main {
    private static final int MOD = (int) Math.pow(10, 9);
    private static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int a = sc.nextInt();
        int b = sc .nextInt();

        if (a > 9 || b > 9) {
            print("-1");
        } else {
            print("" + (a*b));
        }
        System.exit(0);
    }

    static  private void print(String s) {
        System.out.println(s);
    }

    static private int log2(int x) {
        return (int)(Math.log(x) / Math.log(2));
    }

    static private long gcd(long m, long n) {
        if (m < n) { return gcd(n, m); }
        if (m % n == 0) { return n; }
        return gcd(n, m%n);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

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

        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}


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

int main(){
    int N,K;
    cin >> N >> K;
    string S;cin >> S;
    int score = 0;
    rep(i,N-1) {
        if(S[i] == S[i+1])score++;
    }
    int ans = min(score+2*K,N-1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>

#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
//cout << fixed << setprecision(10) << ans << endl;
//int gcd(int a,int b){return b?gcd(b,a%b):a;}

signed main(){
    int n;
    cin >> n;
    int cnt = 0;
    REP(i,n){
        int a1,a2;
        cin >> a1 >> a2;
        if(a1==a2){
            cnt ++;
            if(cnt==3){
                cout << "Yes" << endl;
                return 0;
            }
        }
        else{
            cnt = 0;
        }
    }
    cout << "No" << endl;



    return 0;
}

Measured memory_bytes: 3624
//============================================================================
// Name        : HelloCPP.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {

	int a,b;
	double r;
	double pi = 3.141592653589;
	cin >> r;

	//cout << pi*r*r << " " <<  2*pi*r << endl;
	printf("%lf %lf\n",pi*r*r, 2*pi*r);


	return 0;
}

Measured memory_bytes: 3192
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		char c[] = s.toCharArray();
		int couA=0;
int couB=0;
		for (int i = 0; i < c.length; i++) {
			if (i % 2 == 0) {
				if(c[i]=='0'){couA++;}
			} else {
				if(c[i]!='0'){couA++;}
			}
		}
		for (int i = 0; i < c.length; i++) {
			if (i % 2 != 0) {
				if(c[i]=='0'){couB++;}
			} else {
				if(c[i]!='0'){couB++;}
			}
		}
	System.out.println(Math.min(couA, couB));
	}
}

Measured memory_bytes: 27720
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
/*int find(int a){
     if(a==par[a])return a;
     return par[a]=find(par[a]);
}
void unite(int a,int b){
     a=find(a),b=find(b);
     if(a==b)return ;
     par[b]=a;
}
ll modexpo(ll a,ll b)
{
     ll ans=1LL;
     while(b>0)
     {
          if(b&1)ans=(ans*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return ans;
}
*/
vector<int> adj[100005];
int k,n;
ll dfs(int node,int par){
     int num;
     if(par==-1){
          num=k-1;
     }
     else num=k-2;
     if(k<adj[node].size()){return 0;}
     else{
          ll tmp=1LL;
          for(auto it:adj[node]){
               if(it==par)continue;
               tmp*=num;
               tmp%=mod;
               num--;
              // cout<<tmp<<"\n";
          }
          for(auto it:adj[node]){
               if(it==par)continue;
               tmp*=dfs(it,node);
               tmp%=mod;
          }
          return tmp;
     }
}
int main(){
     cin>>n>>k;
     for(int i=1;i<n;i++){
          int a,b;cin>>a>>b;
          adj[a].pb(b);adj[b].pb(a);
     }
     ll ans=(1LL*k*dfs(1,-1))%mod;
     cout<<ans;
}
 
 
 
 

























Measured memory_bytes: 13660
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;
			StringBuilder shp=new StringBuilder();
			
			for (int i=0;i<h;i++){
				for (int j=0;j<w;j++){
					shp.append("#");
				}
				shp.append("\n");
			}//for 
			System.out.println(shp);
		}//while
	}
}

Measured memory_bytes: 20836
N=int(input())
A=list(map(int,input().split()))
i=0
a=1
t=0
while i<N-1:
    if A[i]<A[i+1]:
        if t==-1:
            a+=1
            t=0
        elif not t:
            t=1
    elif A[i]>A[i+1]:
        if t==1:
            a+=1
            t=0
        elif not t:
            t=-1
    i+=1
print(a)

Measured memory_bytes: 20124
def main():
    n = int(input())
    a = [int(_) for _ in input().split()]

    order = [0 for i in range(n)]

    for i in range(n):
        order[a[i] - 1] = i + 1


#        order.append(a.index(i+1) + 1)

    print(*order)


if __name__ == '__main__':
    main()


Measured memory_bytes: 94080
n = gets.to_i
ds = gets.split.map(&:to_i)

def f(ans, ls)
  if ls.length==2
    puts ans + ls[0]*ls[1]
  else
    new_ans =  ls.drop(1).map{|i|i*ls[0]}.inject{|sum, i| sum + i } + ans
    f(new_ans ,ls.drop(1))
  end
end

f(0, ds)

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <cctype>
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP1(j,n) for(int j=0;j<(int)n;++j)
#define REPD(i,n) for(int i=n;i>=0;--i)
#define REPD1(j,n) for(int j=n;j=>0;--j)
#define REPS(i,n) for(int i=1;i<=(int)n;++i)
#define REPS1(j,n) for(int j=1;j<=(int)n;++j)
#define rep(i,a,n) for(int i=a;i<=(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;

int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	bool can = false;
	for (int i = 1; i <= b; i++) {
		if ((a*i)%b == c)
			can = true;
	}
	if (can)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	
	return 0;
}



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

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void()
#endif

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n;
  cin >> n;
  if (n % 2) {
    cout << 0 << '\n';
    return 0;
  }
  long long ans = 0;
  for (long long add = n / 10; add > 0; add /= 5) {
    ans += add;
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=2e5+5;

int n,a[N];
LL ans;

bool check() {
	if(a[1]!=0) return 0;
	for(int i=2;i<=n;i++) {
		if(a[i]>a[i-1]+1) return 0;
	}
	return 1;
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	if(!check()) {
		printf("-1\n");
	}
	else {
		ans=0;
		for(int i=2;i<=n;i++) {
			if(a[i]<=a[i-1]) {
				ans+=a[i-1];
			}
		}
		ans+=a[n];
		printf("%lld\n",ans);
	}
}

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

int main() {
  char b;
  cin >> b;
  if (b == 'A') cout << "T" << endl;
  else if (b == 'G') cout << "C" << endl;
  else if (b == 'C') cout << "G" << endl;
  else cout << "A" << endl;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::HashSet;
use std::cmp;
use std::f64::consts;

fn main() {
    let mut s: Vec<char> = read::<String>().chars().collect();
    let mut t: Vec<char> = read::<String>().chars().collect();

    let mut s_map: HashMap<char, char> = HashMap::new();
    let mut t_map: HashMap<char, char> = HashMap::new();

    let mut ans: bool = true;

    for i in 0..s.len() {
        if s_map.contains_key(&s[i]) {
            let before = s_map.get(&s[i]).unwrap();
            if &t[i] != before {
                ans = false;
            }
        }
        s_map.insert(s[i], t[i]);
    }

    for i in 0..s.len() {
        if t_map.contains_key(&t[i]) {
            let before = t_map.get(&t[i]).unwrap();
            if &s[i] != before {
                ans = false;
            }
        }
        t_map.insert(t[i], s[i]);
    }

    println!("{}", if ans {"Yes"} else {"No"});
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 6396
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279
 
#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define REP1(i, n) for(ll i = 1; i <= n; i++)
#define REPR1(i, n) for(ll i = n; i >= 1; i--)
#define FOR1(i, m, n) for(ll i = m; i <= n; i++)
const ll INF = LLONG_MAX;
const ull MOD = 1000000007;
#define VEC(type,A,N) vector<type> A(N)
#define VECi(type,A,N,i) vector<type> A(N,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N,vector<type>(M))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N,vector<type>(M,i))
#define ALL(v) v.begin(), v.end()
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
int main(){
    ll N,K;
    cin>>N>>K;
    
    VEC(ll,A,N+1);
    REP1(i,N){
        cin>>A[i];
    }
    
    VECi(ll,af,N+1,0);
    ll now=1,cnt=0,ii=K;
    bool cnf=true;
    REP(i,2*100000){
        //sl(now);
        if(ii<=0){
            cout<<now;
            return 0;
        }
        if(cnf&&af[now]!=0){
            ll t=i-af[now];
            ii=(K-af[now])%t;
            //sl(t,ii);
            cnf=false;
            if(ii==0){
                cout<<now;
                return 0;
            }
        }
        af[now]=i;
        now=A[now];
        ii--;
    }
    //cout<<fixed<<setprecision(32)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 6436
#include<iostream>
#include<map>
#include<set>
using namespace std;
#define df 0
#define MOD 998244353
typedef long int li;

void print(const map<int,li>& mp){
  for(const auto& x:mp){
    printf("(%d %ld)",x.first,x.second);
  }
  printf("\n");
}

int main(){
  if(df) printf("*debug mode*\n");

  li n,k; cin >>n >>k;
  if(2*k-1>n){
    printf("-1");
    return 0;
  }
  li l=k+2*n;
  for(int i=0;i<k;i++){
    printf("%ld %ld %ld\n",k+i,l-k+i,l+2*i);
  }
  for(int i=0;i<k-1;i++){
    printf("%ld %ld %ld\n",2*k+i,l-2*k+i+1,l+2*i+1);
  }
  for(int i=0;2*k-1+i<n;i++){
    printf("%ld %ld %ld\n",3*k-1+i,l-2*k-i,l+2*k-1+i);
  }
}

/// confirm df==0 ///


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

int main() {
  int a,b,c,k;
  cin >> a >> b >> c >> k;
  if(a > k) cout << k << endl;
  else if(a+b >= k) cout << a << endl;
  else cout << a-(k-a-b) << endl;
}

Measured memory_bytes: 3676
import java.util.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;
public class Main {

	static Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
		while (read())
			solve();
	}
	
	static final int INF = 1 << 25;
	static int N, M, S, G1, G2;
	static int[][] W = new int[101][101];
	static boolean read() {
		N = sc.nextInt();
		M = sc.nextInt();
		S = sc.nextInt();
		G1 = sc.nextInt();
		G2 = sc.nextInt();
		if (N == 0 && M == 0) return false;
		
		for (int i = 0; i <= 100; i++) {
			fill(W[i], INF);
			W[i][i] = 0;
		}
		
		for (int i = 0; i < M; i++) {
			int b1, b2, c;
			b1 = sc.nextInt();
			b2 = sc.nextInt();
			c = sc.nextInt();
			W[b1][b2] = c;
		}
		
		return true;
	}

	static void solve() {
		// WF
		for (int k = 0; k < 101; k++) {
			for (int i = 0; i < 101; i++) {
				for (int j = 0; j < 101; j++) {
					W[i][j] = min(W[i][j], W[i][k] + W[k][j]);
				}
			}
		}
		
		int ans = INF * 2;
		for (int i = 0; i < 101; i++) {
			ans = min(ans, W[S][i] + W[i][G1] + W[i][G2]);
		}
		System.out.println(ans);
	}	
}

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

int m=1e9+7;
int n;
int arr[25][25];
int dp[1<<22];

void add_self(int&a, int b){
    a = a+b;
    if(a>m) a=a-m;
}

int pop_count(int mask){
    int ans=0;
    while(mask){
        mask = mask&(mask-1);
        ans++;
    }
    return ans;
}

int f(int mask){
    if(mask==0) return 1;
    
    int p=n-pop_count(mask);
    
    int &ans = dp[mask];
    if(ans!=-1) return ans;
    
    ans = 0;
    for(int i=0;i<n;i++){
        if(mask&1<<i and arr[p][n-i-1]){
            //ans = ans + f(mask^1<<i);
            add_self(ans,f(mask^1<<i));
        }
    }
    
    return ans;
}

int main() {
    memset(dp,-1,sizeof(dp));
	cin>>n;
	for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	        cin>>arr[i][j];
	    }
	}
	int mask=0;
	for(int i=0;i<n;i++){
	    mask = mask|1<<i;
	}
	
	cout<<f(mask);
	return 0;
}

Measured memory_bytes: 16640
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
using Graph = vector<vector<int>>;
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
struct edge{ll to, cost;};
typedef pair<ll,ll> P;
struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    rep(i,V){
      d[i] = INF;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }

  void dijkstra(ll s){
    rep(i,V){
      d[i] = INF;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};
int main(){
  ll n; cin>>n;
  ll a[n]={};
  ll b[65]={};
  rep(i,n){
    cin>>a[i];}
  ll ans = 0;
  rep(i,n){
    bitset<61> s(a[i]);
    rep(j,61){
      if(s.test(j))b[j]++;}
  }
  ll k = 1;
  rep(i,61){
    ll m = b[i]*(n-b[i]);
    m%=MOD;
    ans += m*k;
    k*=2;
    k%=MOD;
  ans%=MOD;}
  cout << ans << endl;}


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

int main() {
	int n, l; cin >> n >> l;
	vector<string>S(n); for (auto&& x : S)cin >> x;
	sort(S.begin(), S.end());
	for (auto&& x : S)cout << x; cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()
#define dump(v) (cerr << #v << ": " << v << endl)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;

// ll n = to_T<ll>("114514")
template <class T> T to_T(const string &s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T> string to_s(const T &a) {
  ostringstream os;
  os << a;
  return os.str();
}

struct Node {
  std::vector<Node *> v;
  int index = -1;
};

Node nodes[1000100];

vi rec(int s, int g, int N) {
  vi d(N, 1 << 25);
  int st[1001000] = {};
  int index = 0;
  d[s] = 0;
  st[index++] = s;

  for (int i = 0; i < index; ++i) {
    for (Node *n : nodes[st[i]].v) {
      if (d[st[i]] + 1 > d[n->index])
        continue;
      d[n->index] = d[st[i]] + 1;
      st[index++] = n->index;
    }
  }

  return d;
}

// void dfs(int from, int to, int d, int distance[]) {
//   distance[to] = d;
//   for (int e : E[to]) {
//     if (from != e)
//       dfs(to, e, d + 1, distance);
//   }
// }

void solve(long long N, vector<long long> a, vector<long long> b) {
  REP(i, N) nodes[i].index = i;

  REP(i, N - 1) {
    nodes[a[i]].v.push_back(&nodes[b[i]]);
    nodes[b[i]].v.push_back(&nodes[a[i]]);
    // E[a[i]].push_back(b[i]);
    // E[b[i]].push_back(a[i]);
  }

  vi f = rec(0, N - 1, N);
  vi s = rec(N - 1, 0, N);

  // int f[1000100] = {};
  // int s[1000100] = {};

  // dfs(-1, 0, 0, f);
  // dfs(-1, N - 1, 0, s);

  ll ans = 0;
  REP(i, N) {
    ans += (f[i] <= s[i]) ? 1 : -1;

    cerr << i << "  " << f[i] << ":" << s[i] << endl;
  }

  cout << ((ans > 0) ? "Fennec" : "Snuke") << endl;
}

int main() {
  ios::sync_with_stdio(false);
  long long N;
  cin >> N;
  vector<long long> a((N - 1) - 1 + 1);
  vector<long long> b((N - 1) - 1 + 1);
  for (int i = 0; i <= (N - 1) - 1; i++) {
    cin >> a[i];
    a[i]--;
    cin >> b[i];
    b[i]--;
  }
  solve(N, a, b);
  return 0;
}


Measured memory_bytes: 42880
import java.util.*;

public class Main {
    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
//        long a = calcNumOfCombination(99999999, 2);
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        char[] s = new char[10];
        Map<String, Long> hoge = new HashMap<>();
        for (int i = 0; i < N; i++) {
            scanner.next().getChars(0, 10, s, 0);
            Arrays.sort(s);
            String fuga = String.valueOf(s);
            if (hoge.containsKey(fuga)) {
                hoge.put(fuga, hoge.get(fuga) + 1);
            } else {
                hoge.put(fuga, 1L);
            }

        }
        long count = 0;
        for (String key : hoge.keySet()) {
            Long p = hoge.get(key);
            if (p >= 2) {
                long tmp = calcNumOfCombination(p, 2);
                count += tmp;
            }
        }

        System.out.println(count);
    }

    long calcNumOfCombination(long n, long r){
        long num = 1;
        for(long i = 1; i <= r; i++){
            num = num * (n - i + 1) / i;
        }
        return num;
    }
}


Measured memory_bytes: 52936
import numpy as np
N,M,Q = map(int,input().split())


table = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    table[l][r]+=1

# 二次元累積和
table = np.array(table)
table = table.cumsum(axis=0).cumsum(axis=1)

for i in range(Q):
    p,q = map(int,input().split())
    ans = table[q][q]-table[p-1][q]-table[q][p-1]+table[p-1][p-1]
    print(ans)

Measured memory_bytes: 20276
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
  int n;
  cin >> n;
  vector<ll> a(n);
  for(int i=0;i<n;i++)cin >> a[i];
  sort(a.rbegin(), a.rend());
  ll sum = 0, cnt = 0;
  for(int i=0;i+2<n && cnt<2;i++){
    if(a[i] < a[i+1] + a[i+2]){
      ++cnt;
      sum += a[i] + a[i+1] + a[i+2];
      i += 2;
    }
  }
  ll res = (cnt == 2 ? sum : 0);
  for(int i=0;i+5<n;i++){
    for(int bit=0;bit<1<<6;bit++)if(__builtin_popcount(bit) == 3){
      vector<ll> A, B;
      for(int j=0;j<6;j++){
        ((bit >> j) & 1 ? A : B).push_back(a[i+j]);
      }
      if(A[0] < A[1] + A[2] && B[0] < B[1] + B[2]){
        res = max(res, A[0] + A[1] + A[2] + B[0] + B[1] + B[2]);
      }
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3632
n = int(input())
ans = [0]*(n+1)
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            k = x**2+y**2+z**2+x*y+y*z+z*x
            if k<=n: ans[k]+=1
for i in range(1, n+1):
    print(ans[i])


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

using namespace std;
int main()
{
	string s,mmm;
	cin>>s;
	long long cont=0,res=0;
	for(long long i=0;i<s.size();i++){
		if(s[i]=='W')
			res+=cont;
		else
			cont++;
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 640
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
    long long h,w;
    cin>>h>>w;
    long long ans=(h*w+1)/2;
    if(h==1||w==1) ans=1;
    cout<<ans<<endl;
    return 0;
}


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

int main(){
  int a, b;
  cin >> a >> b;
  if (a==1 || b==1) {
    if (a==b) {
      cout << "Draw" << endl;
    } else if (a!=1) {
      cout << "Bob" << endl;
    } else {
      cout << "Alice" << endl;
    }
  } else {
    if (a==b) {
      cout << "Draw" << endl;
    } else if (a>b) {
      cout << "Alice" << endl;
    } else {
      cout << "Bob" << endl;
    }
  }
}


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

string itos(int x){
  ostringstream s;
  s << x;
  return s.str();
}

int main(){
  int flag,casenum;
  string num;

  cin >> casenum;
  while(casenum--){
    cin >> num;
    flag = 0;

    while(num.size()>1){
      int a = num[0] - '0'; num.erase(num.begin());
      int b = num[0] - '0'; num.erase(num.begin());
      string tmp = itos(a+b);
      num = tmp + num;
      flag = 1-flag;
    }

    if(!flag)cout << "Audrey wins.\n";
    else cout << "Fabre wins.\n";
  }
}

Measured memory_bytes: 0
//2020年4月17日現在

#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>
#include<iomanip>
#include<limits>
#include<thread>
#include<map>
#include<stack>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<tuple>
#include <cstdio>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

template <class... A>
void prints() { cout << "\n"; }
template <class... A>
void prints_rest() { cout << "\n"; }
template <class T, class... A>
void prints_rest(const T &first, const A &... rest) { cout << " " << first; prints_rest(rest...); }
template <class T, class... A>
void prints(const T &first, const A &... rest) { cout << first; prints_rest(rest...); }
template <class T, class... A>
void printd(const T &first, const A &... rest) { cout << fixed << setprecision(15) << first; prints_rest(rest...); }


namespace {
	// printElems(&a[0], &a[n]);　みたいな感じで使う。
	void printElems(const int* begin, const int* end)
	{
		for (const int* p = begin; p != end; ++p) {
			cout << *p << ' ';
		}
		cout << endl;
	}
}

#define rep(i,n) for(ll i=0; i<n; i++)
#define rep1(i,n) for(ll i=1; i<n+1; i++)
#define repr(i,n) for(ll i=n-1; i>=0; i--)
#define repr1(i,n) for(ll i=n; i>0; i--)
#define FOR(i,j,n) for(ll i=j; i < n; i++)
#define souatari(i,j,n) rep1(i,n-1)rep(j,i)
#define souatari1(i,j,n) for(ll i=2; i<n+1; i++)rep1(j,i-1)
#define mp make_pair
#define F first
#define S second
#define elif else if

typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef array<ll,3> arr3;
typedef long double D;


const ll llinf =  numeric_limits<ll>::max();
const ll _llinf = numeric_limits<ll>::lowest();
const int inf = numeric_limits<int>::max();
const int _inf = numeric_limits<int>::lowest();
const double dinf = numeric_limits<double>::infinity();
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const ll BIG = 1LL<<60;
const string yes = "Yes";
const string no = "No";

//----------------------------------------------


int main(){
/*	int n,q;
	cin >> n >> q;
	rep(i,n){
		ll a;
		cin >> a;
		f.add(i,a);
	}
	vll ans;
	rep(i,q){
		ll t,u,v;
		cin >> t >> u >> v;
		if(t == 0){
			f.add(u,v);
		}
		else{
			ans.push_back(f.sum(u,v));
		}
	}
	for(ll x : ans){
		prints(x);
	}

*/

	ll t;
	cin >> t;
	vll ans;
	rep(_,t){
		ll n,m,a,b;
		cin >> n >> m >> a >> b;
		ans.push_back(floor_sum(n,m,a,b));
	}

	for(ll x : ans){
		prints(x);
	}


	return 0;
}




Measured memory_bytes: 4140
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n', '', _, String).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==
*/

f(700, []).
f(X, ['o'|Cs]) :- f(X2, Cs), X is X2 + 100, !.
f(X, ['x'|Cs]) :- f(X2, Cs), X is X2, !.

main :-
	get_string(S),
    string_chars(S, S2),
    f(X, S2),
    writeln(X).


Measured memory_bytes: 8136
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define MEM(a,b) memset(a,b,sizeof(a))

using namespace std;

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

int main() {
	IOS;
	ll x, y;
	cin >> x >> y;
	ll ans = 0;
	while (x <= y) {
		x *= 2;
		ans++;
		
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/
#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define INF (~(1<<31))
#define eps 1e-8
#define PI 3.141592653589793238462643383
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define all(v) (v).begin(),(v).end()
#define dbg(x,y) cout<<(x)<<" = "<<(y)<< endl;
#define fi first
#define se second
#define ls (rt<<1)
#define rs (rt<<1|1)
#define ll long long
#define int ll
typedef bitset<2010> bt;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const ll N = 1e6 + 7;
const ll M = 1e9 + 7;
const ll MAXN = 2e18 + 7;
const ll Mod = 1e6 + 3;

int _,i,j,k,n,m,p,q,s,T,t,l,r,o,u,v,w,x,y,z,ans,nex,sum,num,len,st,en,sx,sy,tx,ty,th,ma,mi,mod,op,res,flag,cas,ret,mid,cnt,now,tmp,rt;
int a[N],b[N],c[N],d[N],e[N],f[N];
char ch;
vector<int> h;
string s1,s2,s3;

int inv[N];
void get_inv(int n,int p){
	inv[0]=inv[1]=1;
	for (int i=2;i<n;i++){
		inv[i]=inv[p%i]*(p-p/i)%p;
	}
}
ll qpow(ll a,ll n)
{
    ll ret=1;
    a%=Mod;
    while(n){
        if(n&1) (ret*=a)%=Mod;
        a=a*a%Mod;
        n>>=1;
    }
    return ret;
}
int sol()
{
    if(y==0) return qpow(x,n);
    l=x*inv[y]%Mod;
    if(l+n-1>=Mod) return 0;
    return c[l+n-1]*inv[c[max(0ll,l-1)]]*qpow(y,n)%Mod;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    get_inv(N,Mod);
    c[0]=1;
    for(i = 1;i < N;i++) c[i]=c[i-1]*i%Mod;
    d[0]=1;
    for(i = 1;i < N;i++) d[i]=d[i-1]*inv[i]%Mod;
    T=read();
    while(T--){
        x=read();y=read();n=read();
        ans=sol();
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 27112
#include <stdio.h>

int main()
{
    int value;
    int happiness = 0;

    scanf("%d", &value);

    while (value / 500) {
        happiness += 1000;
        value -= 500;
    }

    while (value / 5) {
        happiness += 5;
        value -= 5;
    }

    printf("%d\n", happiness);

    return 0;
}

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

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

using namespace std;

typedef long long ll;

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

  ll n; cin >> n;
  ll ans = 0;

  if ( n & 1 ) {
    cout << ans << endl;
    return 0;
  }
  ll cnt = 10;
  while (cnt <= n) {
    ans += n / cnt;
    cnt *= 5;
  }

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


Measured memory_bytes: 256