akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

int sum(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int sub(int a, int b) {
    return a - b < 0 ? a - b + MOD : a - b;
}
int mul(int a, int b) {
    return (1LL*a*b)%MOD;
}

const int MAXN = 5007;
int df[MAXN];

vector< int >edg[MAXN];
int sbtr[MAXN];

int dp[MAXN][MAXN][2];
int tmp[MAXN][2];

void dfs(int u, int bap) {
    sbtr[u] = 1;

    dp[u][1][0] = 1;
    dp[u][1][1] = 0;
    for (int v : edg[u]) {
        if (v==bap) continue;
        dfs(v, u);

        for (int i = 1; i <= sbtr[u]+sbtr[v]; i++) {
            tmp[i][0] = tmp[i][1] = 0;
        }

        int s0 = 0;
        int s1 = 0;
        for (int niche = 2; niche <= sbtr[v]; niche += 2) {
            s0 = sum(s0, mul(dp[v][niche][0], df[niche]));
            s1 = sum(s1, mul(dp[v][niche][1], df[niche]));
        }

        for (int x = 1; x <= sbtr[u]; x++) {
            tmp[x][0] = sum(mul(dp[u][x][0], s1), mul(dp[u][x][1], s0));
            tmp[x][1] = sum(mul(dp[u][x][0], s0), mul(dp[u][x][1], s1));
        }

        for (int bam = 1; bam <= sbtr[u]; bam++) {
            for (int niche = 1; niche <= sbtr[v]; niche++) {
                tmp[bam+niche][0] = sum(tmp[bam+niche][0], mul(dp[u][bam][0], dp[v][niche][0]));
                tmp[bam+niche][0] = sum(tmp[bam+niche][0], mul(dp[u][bam][1], dp[v][niche][1]));
                tmp[bam+niche][1] = sum(tmp[bam+niche][1], mul(dp[u][bam][0], dp[v][niche][1]));
                tmp[bam+niche][1] = sum(tmp[bam+niche][1], mul(dp[u][bam][1], dp[v][niche][0]));
            }
        }

        sbtr[u] += sbtr[v];
        for (int x = 1; x <= sbtr[u]; x++) {
            dp[u][x][0] = tmp[x][0];
            dp[u][x][1] = tmp[x][1];
        }
    }

//    for (int total = 1; total <= sbtr[u]; total++) {
//        for (int p = 0; p < 2; p++) {
//            cout << "dp[" << u << "][" << total << "][" << p << "] = " << dp[u][total][p] << endl;
//        }
//    }
//    cout << endl;
}

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

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }

    df[0] = 1;
    for (int i = 2; i <= n; i += 2) {
        df[i] = mul(i-1, df[i-2]);
//        cout << "df[" << i << "] = " << df[i] << endl;
    }


    dfs(1, 0);

    int ans = 0;
    for (int sz = 2; sz <= n; sz++) {
        ans = sum(ans, mul(sub(dp[1][sz][0], dp[1][sz][1]), df[sz]));
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 92708
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll a[200000];
int main()
{
	ll i,j,n,m,head,tail,x;
	head=1;tail=9;
	for (i=1;i<=9;i++) a[i]=i;
	while (tail<=100010)
	{
		x=a[head]%10;
		if (x-1>=0) { tail++;a[tail]=a[head]*10+x-1;}
		tail++;a[tail]=a[head]*10+x;
		if (x+1<=9) { tail++;a[tail]=a[head]*10+x+1;}
		head++;
	}
	scanf("%lld",&n);
	printf("%lld",a[n]);
	return 0;
}

Measured memory_bytes: 1024
use std::collections::*;
use std::io::*;
use std::*;
macro_rules! get {
    ($($t:tt),*; $n:expr) => {
        {
            let stdin = std::io::stdin();
            let ret = std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
                let line = line.unwrap();
                let mut it = line.split_whitespace();
                _get!(it; $($t),*)
            }).collect::<Vec<_>>();
            ret
        }
    };
    ($($t:tt),*) => {
        {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut it = line.split_whitespace();
            _get!(it; $($t),*)
        }
    };
}
macro_rules! _get {
    // iterator(splitted input-string) => iterator(output-type)
    ($it:ident; [char]) => {
        _get!($it; String).chars().collect::<Vec<_>>()
    };
    ($it:ident; usize1) => {
        $it.next().unwrap().parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
    };
    ($it:ident; [usize1]) => {
        $it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
    };
    ($it:ident; [$t:ty]) => {
        $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
    };
    ($it:ident; $t:ty) => {
        $it.next().unwrap().parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
    };
    ($it:ident; $($t:ty),+) => {
        ($(_get!($it; $t)),*)
    };
}

fn main() {
    let (h, w, k) = get!(i32, i32, i32);
    let c = get!([char]; h as usize);
    let mut ans: i64 = 0;
    for i in 0..(1 << h) {
        for j in 0..(1 << w) {
            let mut black = 0;
            for k in 0..h {
                for l in 0..w {
                    if i & 1 << k == 0 && j & 1 << l == 0 && c[k as usize][l as usize] == '#' {
                        black += 1;
                    }
                }
            }
            if black == k {
                ans += 1;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2128
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;
typedef long long LL;

LL n,tot = 0;
LL a[5005];
bitset<4000005> dp;

int main(){
    ios::sync_with_stdio(false);
	cin >> n;
	for(LL i = 1;i <= n;i ++){
		cin >> a[i];
		tot += a[i];
	}
	dp[0] = 1;
	for(LL i = 1;i <= n;i ++) dp |= (dp << a[i]);
	for(LL i = (tot + 1) >> 1;i <= tot;i ++){
		if(dp[i]){
			cout << i << endl;
			break;
		}
	}
	return 0;
} 

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

using namespace std;

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

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

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


int dp[3030][3030][2];

vector<long long> AA, BB;
long long TT;

long long dfs(int r, int c, int f) {
    if (c > TT) return -1e18;
    if (r >= AA.size()) return 0;

    if (dp[r][c][f] != -1) return dp[r][c][f];

    long long ans = dfs(r + 1, c, f);
    if (!f) {
        ans = max(ans, dfs(r + 1, c + 1, 1) + BB[r]);
    }
    ans = max(ans, dfs(r + 1, c + AA[r], f) + BB[r]);

    return dp[r][c][f] = ans;
}

void solve(long long N, long long T, std::vector<long long> A,
           std::vector<long long> B) {
    AA = A;
    BB = B;
    TT = T;

    memset(dp, -1, sizeof(dp));

    cout << dfs(0, 0, 0) << endl;

}

int main() {
    long long N;
    scanf("%lld", &N);
    long long T;
    scanf("%lld", &T);
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
        scanf("%lld", &B[i]);
    }
    solve(N, T, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 72320
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mod 1000000007
//#define mad(a,b) a=(a+b)%mod
#define N 200010
ll n,mo;
void mad(ll &a,ll b){
    a=(a+b)%mo;
}
ll po(ll x,ll y,ll m){
    if(y<0)return 0;
    ll res=1;
    for(;y;y>>=1){
	if(y&1)res=res*x%m;
	x=x*x%m;
    }
    return res;
}
ll dp[3010][3010],nck[3010][3010];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>mo;
    
    nck[0][0]=1;
    for(int i=0;i<3010;i++)for(int j=0;j<3010;j++){
	nck[i][j]=0;
	if(i==0&&j==0)nck[i][j]=1;
	if(i)mad(nck[i][j],nck[i-1][j]);
	if(j)mad(nck[i][j],nck[i][j-1]);
    }
    
    for(int i=0;i<3010;i++)for(int j=0;j<3010;j++)dp[i][j]=0;
    dp[0][0]=1;
    for(int i=0;i<=n;i++)for(int j=0;j<=i;j++){
	mad(dp[i+1][j],dp[i][j]*(j+1));
	mad(dp[i+1][j+1],dp[i][j]);
	//cout<<i<<" "<<j<<":"<<dp[i][j]<<endl;
    }
    
    ll ans=0;
    for(int k=0;k<=n;k++){
	ll res=0;
	ll kei1=1,inc1=po(2,n-k,mo);
	ll kei2=po(2,po(2,n-k,mo-1),mo);
	for(int i=0;i<=k;i++){
	    
	    //ll cur=dp[k][i]*po(2,i*(n-k),mo)%mo;
	    ll cur=dp[k][i]*kei1%mo; kei1=kei1*inc1%mo;
	    
	    //cur=cur*po(2,po(2,n-k,mo-1),mo)%mo;
	    cur=cur*kei2%mo;
	    
	    mad(res,cur);
	    //cout<<"k="<<k<<" i="<<i<<":"<<cur<<endl;
	}
	//cout<<"#"<<k<<" "<<res<<" "<<nck[n-k][k]<<endl;
	if(k%2==0)mad(ans,+res*nck[n-k][k]);
	if(k%2==1)mad(ans,-res*nck[n-k][k]);
    }
    if(ans<0)ans+=mo;
    cout<<ans<<endl;
}




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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000001
#define INFL (1LL << 60)
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main() {
  int a, b;
  cin >> a >> b;
  if(a <= b) cout << a << endl;
  else cout << a-1 << endl;
  return 0;
}


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

int main () {
  int k, s;
  cin >> k >> s;
  int ans = 0;
  for(int i = 0; i <= k; i++) {
    for (int j = 0; j <= k; j++) {
      int temp = s - (i + j);
      if (temp <= k && 0 <= temp) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<stdlib.h>
#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007

using namespace std;


int main(void) {
	string s, t;
	int p;
	cin >> s;
	p = s.size() - 1;
	RFOR(i, p, 0) {
		t.push_back(s[i]);
	}
	FOR(i, 0, p) {
		if (t[i] == 'd') {
			t[i] = 'b';
		}
		else if (t[i] == 'b') {
			t[i] = 'd';
		}
		else if (t[i] == 'p') {
			t[i] = 'q';
		}
		else if (t[i] == 'q') {
			t[i] = 'p';
		}
	}
	if (s == t) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define rep(j,n) for(int i=(int)(j);i<(int)(n);i++)
int main(){
  int N;
  cin>>N;
  vector<int> A(N);
  rep(0,N)
    cin>>A.at(i);
  int sum=0;
  rep(0,N-1){
    for(int j=i+1;j<N;j++)
      sum+=A.at(i)*A.at(j);
    }
  cout<<sum<<endl;
  }

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for (int i=0; i<n;++i)
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
int n;
int A[200005];
int LastIdx[200005];
ll dp[200005];

int main() {
  INCANT;
  cin >> n;
  rep(i, n) {
    cin >> A[i];
    A[i]--;
  }
  vector<int> P(n, -1);
  fill(LastIdx, LastIdx+200005, -1);
  rep(i, n) {
    P[i] = LastIdx[A[i]];
    LastIdx[A[i]] = i;
  }

  fill(dp, dp+n, -1);
  dp[0] = 1ll;
  for (int i=1; i<n; i++) {
    dp[i] = dp[i-1];
    if (A[i]!=A[i-1] && P[i]>=0) {
      dp[i] += dp[P[i]];
      dp[i]%=MOD;
    } 
  }

  cout << dp[n-1] << endl;
  return 0;
}

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

int main() {
	int N;
	int K;
  	int p;
	cin >> N >> K;

	int q[N]; // N個のデータ

  	// データを受け取る
  	for (int i = 0; i < N; i++) {
    	cin >> q[i];
	}
	sort(q, q+N); //q[0:N] を値が小さい順にソート
    p=0;
	// 英語の点数データを受け取る
	for (int i = 0; i < K; i++) p+=q[i];
   cout << p << endl;
}

Measured memory_bytes: 3568
#include "bits/stdc++.h"
using namespace std;

int main()
{
	long long int  n,k,mod=1000000007;;
	long long int vect[110];
	static long long int dp[110][100010]={};
	cin>>n>>k;
	for(int i=0;i<n;i++)
	cin>>vect[i];
	dp[0][0]=1;
	for(int i=0;i<n;i++)
	{
		static long long int sum[100010]={};
		for(int j=0;j<=k;j++)
		{
			sum[j+1]=(sum[j]+dp[i][j])%mod;
		}

		for(int j=0;j<=k;j++)
		{
			dp[i+1][j]=(sum[j+1]-sum[max(0LL,j-vect[i])]+mod)%mod;
		}
	}
	cout<<dp[n][k];


	return 0;
}

Measured memory_bytes: 79360
n, k = gets.split.map(&:to_i)
trees = []
n.times do
  trees << gets.to_i
end
trees.sort!
ans = trees[-1] - trees[0]
n.times do |i|
  break if trees[i+k-1].nil?
  diff = trees[i+k-1] - trees[i]
  ans = [ans, diff].min
end

puts ans

Measured memory_bytes: 4016
from math import ceil
n, *CSF = map(int, open(0).read().split())
A = []
for i in range(0, 3*(n-1), 3):
    t = 0
    for c, s, f in zip(CSF[i::3], CSF[i+1::3], CSF[i+2::3]):
        if t <= s:
            t = s + c
        else:
            t = ceil((t-s) / f) * f + s + c
    A.append(t)
A.append(0)
print(*A, sep='\n')

Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

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

		int X = partition(A, 0, n);

		StringBuilder str = new StringBuilder();
		str.append(A[0]);
		for (int i = 1; i < X; i++) {
			str.append(" ");
			str.append(A[i]);
		}
		str.append(" [");
		str.append(A[X]);
		str.append("]");
		for (int i = X + 1; i < n; i++) {
			str.append(" ");
			str.append(A[i]);
		}
		System.out.println(str);

	}

	public static int partition(int[] A, int p, int r) {
		int x = A[r - 1];
		int i = p - 1;
		int kari = 0;
		for (int j = p; j < r; j++) {
			if (A[j] <= x) {
				i++;
				kari = A[i];
				A[i] = A[j];
				A[j] = kari;
			}
		}
		return i;
	}

}

Measured memory_bytes: 69072
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	int c;
	cin >> c;
	int a;
	cin >> a;
	int b;
	cin >> b;

	if ((10 * a + b) % 4 == 0)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;



}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
using namespace std;
using ll = long long;
using d = double;
// 2038
int main(){
  float l;
  cin >> l;
  printf("%.8f\n", l*l*l/27);
  return 0;
}


Measured memory_bytes: 3784
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1010
int s[N];
int main()
{
    int i,j,k,n,m,s1,s2,ans;
    s[0]=0;
    for(i=1;i<=1000;i++)
        s[i]=s[i-1]+i;
    scanf("%d%d",&n,&m);
    ans=s[1000];
    for(i=1;i<1000;i++)
    {
        if(n<s[i]&&m<s[i+1]&&s[i]-n==s[i+1]-m)
            ans=min(ans,s[i]-n);
        if(n<s[i+1]&&m<s[i]&&s[i+1]-n==s[i]-m)
            ans=min(ans,s[i+1]-n);
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF (1e20)
using namespace std;
using ld = long double;
using ll = long long;
struct P {
	ll x, y;
};
struct C {
	P c;
	ll r;
};

ld Dist(P a, P b) {
	return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

class Dijkstra {
	struct edge {
		ll to;
		ld cost;
		edge(ll to_, ld cost_) : to(to_), cost(cost_) {}
	};
	bool isdirected;
	vector<ld> d;
	vector<vector<edge>> G;
	ll V, E;
public:
	Dijkstra(ll _V, bool _isdirected = true) : isdirected(_isdirected), V(_V), E(0), d(_V), G(_V) { }
	void add(ll a, ll b, ld c) {
		G[a].push_back(edge(b, c));
		if (!isdirected) G[b].push_back(edge(a, c));
		E++;
	}
	void calc(ll start) {
		fill(d.begin(), d.end(), INF);
		priority_queue<pair<ld, ll>, vector<pair<ld, ll>>, greater<pair<ld, ll>>> que;
		d[start] = 0.0;
		que.push(pair<ld, int>(0.0, start));

		while (!que.empty()) {
			pair<ld, int> p = que.top(); que.pop();
			int v = p.second;
			if (d[v] < p.first) continue;
			for (size_t i = 0; i < G[v].size(); i++) {
				edge e = G[v][i];
				if (d[e.to] > d[v] + e.cost) {
					d[e.to] = d[v] + e.cost;
					que.push(pair<ld, ll>(d[e.to], e.to));
				}
			}
		}
	}
	ld dist(ll to) {
		return d[to];
	}
};

int main()
{
	ll N;
	P s, t;
	cin >> s.x >> s.y >> t.x >> t.y;
	cin >> N;
	vector<C> cir(N);
	for (int i = 0; i < N; i++) {
		cin >> cir[i].c.x >> cir[i].c.y >> cir[i].r;
	}
	Dijkstra dij(N + 2, false);
	dij.add(N, N + 1, Dist(s, t));
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			dij.add(i, j, max((ld)0, Dist(cir[i].c, cir[j].c) - cir[i].r - cir[j].r));
		}
		dij.add(i, N, max((ld)0, Dist(cir[i].c, s) - cir[i].r));
		dij.add(i, N + 1, max((ld)0, Dist(cir[i].c, t) - cir[i].r));
	}
	dij.calc(N);
	cout << fixed << setprecision(10) << dij.dist(N + 1) << endl;
	return 0;
}


Measured memory_bytes: 40940
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

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

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

void solve(vector<string> s) {
  string res;
  for (auto i: s) {
    res += toupper(i.front());
  }
  cout << res << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	vector<string> s(3-1+1);
	for (int i = 0 ; i <= 3-1 ; i++) {
	  cin >> s[i];
	}
	solve(s);
	return 0;
}


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

int main()
{
	string S;
	cin >> S;
	int N = S.size();
	rep(i,N/2)
	{
		if (S[i] != S[N-1-i])
		{
			cout << "No" << endl;
			return 0;
		}
	}
	rep(i,N/4)
	{
		if (S[i] != S[(N-1)/2-1-i])
		{
			cout << "No" << endl;
			return 0;
		}
	}
	rep(i,N/4)
	{
		if (S[(N+3)/2-1+i] != S[N-1-i])
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int n,k,ans,x;
bool pan;
int pan2;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		ans=__gcd(x,ans);
		if(k%ans==0)pan=1;
		pan2=max(pan2,x);
	}
	if(pan==1&&pan2>=k)
	cout<<"POSSIBLE"<<endl;
	else cout<<"IMPOSSIBLE"<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
// warm-up
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		Set<Integer> s = new HashSet<Integer>();
		int N = sc.nextInt();
		while (N-->0) s.add(sc.nextInt());
		System.out.println(s.size());
		sc.close();		
	}

	public static void main(String args[]) {
		solve();
	}

}

Measured memory_bytes: 35988
/**
 *    Creator :  bizarre
 *    Date : 4/2020
 *    Problem Number : 435
**/
#include <bits/stdc++.h>
using namespace std;
#define bizarre     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
#define ll long long
/*
vector<int> prime_Numbers;
int primes[1000005];
void prime(int n)
{
    primes[1]=primes[0]=0;
    for(int i=2; i<=n; i++)
        primes[i]=true;
    for(int i=2; i<=n; i++)
    {
        if(primes[i]==true)
        {
            prime_Numbers.push_back(i);
            for(int j=i+i; j<=n; j+=i)
                primes[j]=false;
        }
    }
    for(int i=2; i<=n; i++)
        primes[i]+=primes[i-1];
}

void move1step(long long& a, long long& b, long long q)
{
    long long c= a-q*b;
    a=b;
    b=c;
}
long long egcd(long long r0,long long r1,long long& x0,long long& y0)
{
    long long x1=0,y1=1;
    x0=1;
    y0=0;
    while(r1)
    {
        long long q=r0/r1;
        move1step(r0,r1,q);
        move1step(x0,x1,q);
        move1step(y0,y1,q);
    }
    return r0;
}
bool  solve (long long a, long long b, long long c,long long&x, long long& y)
{
    long long g=egcd(a,b,x,y);
    int m=c/g;
    x*=m;
    y*=m;
    return c%g==0;
}
int gcd(int a, int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
void PrimeFactorization(int n)
{
    for(int i=2; i*i<=n; i++)
    {
        int c=0;
        if(n%i==0)
        {
            while(n%i==0)
            {
                n/=i;
            }

        }
    }

}
long long ncrtane(long long n, long long r)
{
    long long ans=1,cntr=1;
    for(int i=n;i>n-r;i--)
    {
        ans*=i;
        ans/=cntr;
        cntr++;
    }
    return ans;
}
long long fact[N], inv[N];
long long fp(long long base, long long exp)
{
    if (exp == 0)
        return 1;
    long long ans = fp(base, exp / 2);
    ans = (ans * ans) % mod;
    if (exp % 2 != 0)
        ans = (ans * (base % mod)) % mod;
    return ans;
}
void pre(long long n)
{
    fact[0] = 1;
    inv[0] = 1;
    for (long long i = 1; i <= n; i++)
    {
        fact[i] = (i * fact[i - 1]) % mod;
        inv[i] = fp(fact[i], mod - 2);
    }
}
int ncr(long long n, long long r)
{
    return (((fact[n] * inv[n - r]) % mod) * inv[r]) % mod;
}

int npr(long long n, long long r)
{
    return (fact[n] * inv[n - r]) % mod;
}
*/
const int inf = 2e9, mod = 1e9 + 7,N=1e5+5;
ll a[105],dp[105][100005];
int main()
{
    ll n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    memset(dp,0,sizeof dp);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        ll sum=0;
        for(int j=0;j<=k;j++)
        {
            sum=(sum+dp[i-1][j])%mod;
            if(j>a[i])
            {
                sum-=dp[i-1][j-a[i]-1];
            }
            if(sum<0)sum=(sum+mod)%mod;
            else sum%=mod;
            dp[i][j]=(dp[i][j]+sum)%mod;
        }
    }
    cout << dp[n][k];
    return 0;
}



Measured memory_bytes: 82304
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000+10;
long long n,k,A[MAXN],B[MAXN],ans;
inline void dfs(long long len,long long now,bool all)
{
	if(all&&len>=0){
		if(k&(1ll<<len)){
			dfs(len-1,now^(1ll<<len),false);
			dfs(len-1,now,true);
		}
		else dfs(len-1,now^(1ll<<len),true);
	}
	else{
		long long res=0;
		for(register long long i=1;i<=n;++i)
			if((A[i]&now)==A[i])res+=B[i];
		if(ans<res)ans=res;
	}
}
int main(){
    scanf("%lld%lld",&n,&k);
	for(register int i=1;i<=n;++i){
		scanf("%lld%lld",&A[i],&B[i]);
	}
	dfs(30,-1,1);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1792
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let mut e = Vec::with_capacity(m);
    let mut z = Vec::with_capacity(2 * m + n);
    for _ in 0..m {
        let p: usize = it.next().unwrap().parse().unwrap();
        let q: usize = it.next().unwrap().parse().unwrap();
        let c: u32 = it.next().unwrap().parse().unwrap();
        e.push((p, q, c));
        z.push((p, c));
        z.push((q, c));
    }
    for i in 1..(n + 1) {
        z.push((i, 0));
    }
    z.sort();
    z.dedup();
    let size = z.len();
    let mut g = vec![vec![]; size];
    for (p, q, c) in e {
        let a = z.binary_search(&(p, c)).unwrap();
        let b = z.binary_search(&(q, c)).unwrap();
        g[a].push((b, 0));
        g[b].push((a, 0));
    }
    for i in 0..size {
        if z[i].1 != 0 {
            continue;
        }
        for j in (i + 1)..size {
            if z[j].0 != z[i].0 {
                break;
            }
            g[i].push((j, 1));
            g[j].push((i, 0));
        }
    }
    let mut dp = vec![size; size];
    dp[0] = 0;
    let mut q = std::collections::VecDeque::new();
    q.push_back(0);
    while let Some(v) = q.pop_front() {
        for &(u, c) in &g[v] {
            if c == 0 && dp[u] > dp[v] {
                dp[u] = dp[v];
                q.push_front(u);
            }
            if c == 1 && dp[u] > dp[v] + 1 {
                dp[u] = dp[v] + 1;
                q.push_back(u);
            }
        }
    }
    let ans = dp[z.binary_search(&(n, 0)).unwrap()];
    if ans == size {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}

fn main() {
    run();
}


Measured memory_bytes: 71928
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<utility>
#include<cstdlib>
#include<typeinfo>


using namespace std;
#define INF 1000000005
int main()
{
int n;
std::cin >> n;
std::vector<int> a;
for(int i = 0; i < n; i++){
    int tempa;
    std::cin >> tempa;
    a.push_back(tempa);
}
int twin = 0;
int pre = 0;
int flag = 0;
std::sort(a.begin(), a.end(), std::greater<int>());
for(int i = 0; i < n; i++){
    if(i == n - 1){
        flag = n - 1;
        break;
    }
    if(a[i] <= i + 1){
        flag = i;
        break;
    }
}
if(a[flag] == flag + 1){
    if(flag == n - 1){
        twin = 0;
    } else {
        int check = 0;
        for(int i = 1; i <= n - 1 - flag; i++){
            if(a[i + flag] < a[flag]){
                break;
            } else {
                check++;
            }
        }
        check = check % 2;
        if(check == 1){
            twin = 1;
        } else {
            twin = 0;
        }
    }
} else {
    if(a[flag] > flag + 1){
        twin = (a[flag] - flag + 1) % 2;
    } else {
        if(a[flag] == flag){
            int check = 0;
            for(int i = 1; i <= n - 1 - flag; i++){
                if(a[i + flag] < a[flag]){
                    break;
                } else {
                    check++;
                }
            }
            check = check % 2;
            if(check == 0){
                twin = 1;
            } else {
                twin = (a[flag - 1] - a[flag]) % 2; 
            }
        } else if((a[flag - 1] - flag) % 2 == 0){
            twin = 0;
        } else {
            twin = 1;
        }/*((a[flag - 1] - a[flag]) % 2 == 0){
            twin = 1;
        } else {
            twin = 0;
        } */
    }
}
if(twin == 1){
    std::cout << "First" << std::endl;
} else {
    std::cout << "Second" << std::endl;
}
return 0;
}

Measured memory_bytes: 892
# -*- coding: utf-8 -*-


def main():
    # 入力
    st = input()

    # 右からi文字目から最後の数字までを数値化したものについてmodを計算していく
    mod_res_dic = {0: [0]}
    tmp_mod_val = 0
    r_st = ''.join(list(reversed(st)))
    cnt = 0
    for i in range(len(r_st)):
        target_st = r_st[i:i+1]
        tmp_mod_val += int(target_st)*pow(10, i, 2019)
        tmp_mod_val %= 2019
        ls = mod_res_dic.setdefault(tmp_mod_val, [])
        ls.append(i-1)
        if len(ls) > 1:
            cnt += len(ls)-1

    print(int(cnt))


main()


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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> h(N), ans(N, 1000000000);
    for (int i = 0; i < N; i++) {
        cin >> h.at(i);
    }
    for (int i = 0; i < N; i++) {
        if (i == 0) {
            ans.at(i) = 0;
        }
        else {
            for (int j = 0; j < K && i - j > 0; j++){
                if (ans.at(i) > ans.at(i - j - 1) + abs(h.at(i) - h.at(i - j - 1))){
                    ans.at(i) = ans.at(i - j - 1) + abs(h.at(i) - h.at(i - j - 1));
                }
            }
        }
    }
    cout << ans.at(N - 1) << endl;
}


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

int d[310][310];

void dijk(int st, long long l, int n, vector<vector<pair<int, long long>>> &e) {
    vector<long long> v(n, 1e16);
    set<pair<long long, int>> s;
    s.insert({0, st}); v[st] = 0;
    while (!s.empty()) {
        auto f = *s.begin();
        s.erase(s.begin());
        int curr = f.second;
        long long currl = f.first;
        if (v[curr] < currl) continue;
        if (st != curr) d[st][curr] = 1;
        for (auto &iter : e[curr]) {
            auto to = iter.first;
            auto w = iter.second;
            if (v[to] > w + currl && w + currl <= l) {
                v[to] = w + currl;
                s.insert({v[to], to});
            }
        }
    }
}

int main() {
    int n, m; long long l; cin >> n >> m >> l;
    vector<vector<pair<int, long long>>> e(n);
    for (int i = 0; i < m; i++) {
        int a, b; long long c; cin >> a >> b >> c;
        a--; b--;
        e[a].emplace_back(b, c);
        e[b].emplace_back(a, c);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) d[i][j] = 1e9;
        }
    }
    for (int i = 0; i < n; i++) dijk(i, l, n, e);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
            }
        }
    }
    int q; cin >> q;
    while (q--) {
        int s, t; cin >> s >> t; s--; t--;
        if (d[s][t] == 1e9) cout << -1 << "\n";
        else cout << max(d[s][t]-1, 0) << "\n";
    }
    return 0;
}

Measured memory_bytes: 3328
let rec gcd n m =
  if m = 0 then n
  else gcd m (n mod m)

let () =
  let n, k = Scanf.scanf "%d %d\n" (fun n k -> n, k) in
  let as_ = Array.init n (fun _ -> Scanf.scanf "%d " (fun a -> a)) in
  if k <= Array.fold_left max 0 as_ && k mod Array.fold_left gcd 0 as_ = 0 then
    print_endline "POSSIBLE"
  else print_endline "IMPOSSIBLE"

Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int cnt=0,ans=1000001;
  for(int i=0;i<=n;i++){
    int t=i;
    int c6=0,c9=0;
    cnt=0;
    while(t){
      for(int j=1;pow(6,j)<=t;j++){
        c6++;
      }
      t-=pow(6,c6);
      cnt++;
      c6=0;
    }
    t=n-i;
    while(t){
      for(int j=1;pow(9,j)<=t;j++){
        c9++;
      }
      t-=pow(9,c9);
      cnt++;
      c9=0;
    }
    ans=min(ans,cnt);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define DB double
#define INF 1145141919810364364
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
//#define MOD 998244353
#define ERR 0.00000001
#define NUM 200010

void swap(LL* a,LL* b){LL tmp=*a;*a=*b;*b=tmp;}
LL lpow(LL a,LL n){LL ans=pow(a,n)*10;if(ans%10<5)return ans/10;return ans/10+1;}
LL dup(LL a,LL d){if(a%d==0)return a/d;else return a/d+1;}
LL GCD(LL a,LL b){LL c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
int lcmp(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return 1;if(*(LL*)a<*(LL*)b)return -1;return 0;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int scmp(const void* a,const void* b){return strcmp(*(char**)a,*(char**)b);}
LL mod(LL a,LL m){if(a<0)return a%m+m;else return a%m;}
LL DIV(LL a,LL d){LL m=MOD,x=1,y=0,k;while(m){k=d/m;d-=k*m;swap(&m,&d);x-=k*y;swap(&x,&y);}return mod(a*mod(x,MOD),MOD);}
LL FAC(LL a){LL i,ans=1;FOR(i,1,a+1){ans*=i;if(MOD>0&&ans>MOD)ans%=MOD;}return ans;}
LL POW(LL a,LL n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return ans;}

int main(){
  LL H,N,i,a=0,ans=0;
  scanf("%lld%lld",&H,&N);
  LL A[N];
  FOR(i,0,N)scanf("%lld",&A[i]);
  FOR(i,0,N)a+=A[i];
  if(H>a)printf("No\n");
  else printf("Yes\n");

  //printf("%lld\n",dup(H,A));
	return 0;
}


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

int main(){
  int64_t W,H,x,y;
  cin>>W>>H>>x>>y;
  double ans;
  ans=double(W)*double(H)/2;
  if(2*x==W && 2*y==H){
    printf("%lf %d\n",ans,1);
  }
  else{
    printf("%lf %d\n",ans,0);
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 
#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)
 
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int N; ll L;
    cin >> N >> L;
    vector<int> T(N);
    for (int n = 0; n < N; ++n) cin >> T[n];
    
    double SumX = 0.0, SumY = 0.0;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            double dTemp = M_PI * (T[i] + T[j]) / L;
            int nTemp = N - (j - i) - 1;
            SumX += nTemp * cos(dTemp);
            SumY += nTemp * sin(dTemp);
            
            dTemp += M_PI;
            nTemp = j - i - 1;
            SumX += nTemp * cos(dTemp);
            SumY += nTemp * sin(dTemp);
        }
        //cerr << SumX << " " << SumY << endl;
    }
    double dTemp = N * (N-1) * 0.5 * (N-2) / 3.0;
    SumX /= dTemp;
    SumY /= dTemp;
    cout.precision(15);
    cout << fixed <<  SumX << " " << SumY << endl;
 
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
	int k, t;
	vector<int> a;
	int tmp;
	int max = 0;

	cin >> k >> t;
	for (int i = 0; i < t; ++i) {
		cin >> tmp;
		a.push_back(tmp);
		if (max < tmp) {
			max = tmp;
		}
	}
	int ans = max - (k - max) - 1;
	if (ans <= 0) {
		cout << '0' << endl;
	}
	else {
		cout << ans << endl;
	}
}

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

int gcd(int a, int b) {
    int c = a%b;
    while(c!=0) {
        a = b;
        b = c;
        c = a%b;
    }
    return b;
}

int main() {
    int n;
    cin >> n;
    int a;
    cin >> a;
    for(int i = 0; i < n-1; i++) {
        int b;
        cin >> b;
        a = gcd(a,b);
    }
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = Integer.parseInt(scanner.next());
        int b = Integer.parseInt(scanner.next());
        int c = Integer.parseInt(scanner.next());
        scanner.close();

        boolean isBeautiful = b - a == c - b;

        System.out.println(isBeautiful ? "YES" : "NO");
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
int a, b, x;
const double PI = acos(-1);


int main() {
    double a,b,x; cin >> a >> b >> x;
    x /= a;
    auto f=[&](double t){
        if (tan(t)<=b/a) return a*b - (a*a*tan(t))/2;
        else return b*(b/tan(t))/2;
    };
    double ok = 0.0;
    double ng = PI/2.0; 
    for (int i=0; i< 100; ++i){
        double theta = (ok + ng)/2;
        if (f(theta) >= x) ok = theta;
        else ng = theta;
    }
    cout << fixed << setprecision(10) << ok * 180 / PI << endl;
    // cout << fixed << setprecision(8) << (a*a*b - (a*a*a*tan((double)PI/3.9))/2 - x) << endl; 
}


Measured memory_bytes: 4152
#include <bits/stdc++.h>
#define ri register
#define int long long
#define E (n+1)
using namespace std; const int N=1000010;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
    return s*w;
}
signed main()
{
    int n,lx,ly;
    n=read();
    lx=ly=0;
    int flg=1;
    int lt=0;
    for(ri int i=1;i<=n;i++)
    {
        int t,x,y;
        t=read(), x=read(), y=read();
        if(!flg) continue;
        if(t-lt<abs(lx-x)+abs(ly-y) || (t-lt)%2!=(abs(lx-x)+abs(ly-y))%2) { flg=0; continue; }
        lx=x, ly=y, lt=t;
    }
    (flg)?puts("Yes"):puts("No");
    return 0;
}

Measured memory_bytes: 3624
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

int main()
{	
	ll N, A, B, C, D, E;
	cin >> N >> A >> B >> C >> D >> E;

	ll M = A;
	chmin(M, B);
	chmin(M, C);
	chmin(M, D);
	chmin(M, E);

	cout << (N / M) + 4 + (N % M == 0 ? 0 : 1);

	return 0;
}

Measured memory_bytes: 256
// Aizu 1187: ICPC Ranking
// 2017.9.13 bal4u@uu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct { int id, sr, st, c[11]; } TM;
TM tm[55];

int cmp(TM *a, TM *b)
{
	if (b->sr - a->sr) return b->sr - a->sr;
	if (a->st - b->st) return a->st - b->st;
	return b->id - a->id;
}

int main()
{
	int M, T, P, R;
	int m, t, p, j, i;

	while (scanf("%d%d%d%d", &M, &T, &P, &R) && M) {
		memset(tm, 0, sizeof(tm)); for (i = 1; i <= T; i++) tm[i].id = i;
		while (R-- > 0) {
			scanf("%d%d%d%d", &m, &t, &p, &j);
			if (j == 0) tm[t].sr++, tm[t].st += m + 20*tm[t].c[p];
			else        tm[t].c[p]++;
		}
		qsort(tm+1, T, sizeof(TM), cmp);
		printf("%d", tm[1].id);
		for (i = 2; i <= T; i++) {
			if (tm[i].sr == tm[i-1].sr && tm[i].st == tm[i-1].st) putchar('=');
			else putchar(',');
			printf("%d", tm[i].id);
		}
		putchar('\n');
	}
	return 0;
}

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

int main(){
  string s,t;
  std::cin >> s>>t;
  for (int i = 0; i < s.size(); i++) {
    if( s[i]!=t[i]){
      std::cout << "No" << '\n';
      return 0;
    }
  }
  std::cout << "Yes" << '\n';
  return 0;
}


Measured memory_bytes: 3592
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


def mod_inverse(a):
	return pow(a, MOD - 2, MOD)


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	return (fact[nn] * invFact[rr] * invFact[nn - rr]) % MOD



pre()
n, m, k = map(int, input().split())


ans = 0
for i in range(k + 1):
	ans = (ans + m * pow(m - 1, n - 1 - i, MOD) * ncr(n - 1, i) ) % MOD

print(ans)


Measured memory_bytes: 24644
#include <stdio.h>

void print(int array[], int n);

int
main(void)
{
        int i, j, k;
        int v;
        int N;
        int A[100];

        scanf("%d", &N);

        for (i = 0; i < N; i++) {
                scanf("%d", &A[i]);
        }

        print(A, N);

        for (j = 1; j < N; j++) {
                v = A[j];
                k =  j - 1;

                while (k >= 0 && A[k] > v) {
                        A[k + 1] = A[k];
                        k--;
                }

                A[k + 1] = v;
                print(A, N);
        }

        return 0;
}

void
print(int array[], int n)
{
        int i;

        printf("%d", array[0]);

        for (i = 1; i < n; i++) {
                printf(" %d", array[i]);
        }

        printf("\n");
}



Measured memory_bytes: 2100
#include <stdio.h>
int main (){
long long int n,total=1;
scanf("%lld",&n);
long long int A[n];
	for (int c=0; c<n; c++){
		scanf("%lld", &A[c]);
	}
	for (int i=0;i<n; i++){
	
		if (A[i]==0){
			printf("0");
			return 0;
			}
	}
	for (int j=0;j<n;j++){
		if (A[j]<=1000000000000000000/total){
			total= total*A[j];}
		else{
			printf("-1");
			return 0;
		}
	}
printf("%lld",total);
return 0;
}


Measured memory_bytes: 2492
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//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 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())

//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);

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

  int N; cin >> N;
  vector<LL> a(N);
  REP(i,N) cin >> a[i];
  SORT(a);
  vector<LL> sum(N, 0);
  sum[0] = a[0];
  REP(i,N-1)
	sum[i+1] = sum[i] + a[i+1];

  int M; cin >> M;
  vector<LL> b(M), c(M);
  REP(i,M) cin >> b[i];
  REP(i,M) cin >> c[i];

  REP(i,M){
	int idx = upper_bound(ALL(a), b[i]) - a.begin() - 1;
	LL score = (idx<0? 0: sum[idx]);
	if(score < c[i])
	  cout << "No" << endl;
	else
	  cout << "Yes" << endl;
  }
  
  return 0;
}

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

using ll = long long;
using Field = vector<vector<ll>>;
using Graph = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VC = vector<char>;
using PI = pair<int, int>;

#define FOR(i, s, n) for (int i = s; i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()

const long long INF = 1LL<<60;
const int mod = 1000000007;

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

long long A;
long double B;

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

    cin >> A >> B;
    cout << (ll)(A * B + 0.001) << endl;

    return 0;
}

Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
ll a[maxn],b[maxn];
int main(){
	ll k,n;
	cin>>k>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++){
		b[i]=a[i+1]-a[i];
	}
	b[n]=k-a[n]+a[1];
	ll sum=0;
	ll ma=-1000000000;
	for(int i=1;i<=n;i++){
		sum+=b[i];
		ma=max(b[i],ma);
	}
	cout<<sum-ma<<endl;
	return 0;
}


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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

// n回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) // 1-indexed昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  // 0-indexed降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   // 1-indexed降順
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii;  // 2次元配列
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> PII;

template<typename T>
using vec = vector<T>;
template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

const ld Pi = std::acos(-1.0L);
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    // cout << fixed << setprecision(15);

    string s; cin >> s;
    ll k, i; cin >> k;
    for(i = 0; i < s.size(); ++i) {
        char ch = s[i];
        if(ch-'0' == 1) --k;
        else break;
    }

    if(k <= 0) cout << 1 << '\n';
    else cout << s[i] << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}

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

using namespace std;
typedef long long llint;
typedef long double ld;
#define inf 1e18


llint n;
llint r[200005];
llint a[200005];
void solve(){
	cin >> n;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(i==0)r[i]=a[i];
    else{
      r[i]=r[i-1]+a[i];
    }
  }
  llint ans=10000000007;
  for(int i=0;i<n;i++){
    llint s1=r[i];
    llint s2=r[n-1]-r[i];
    llint dif=abs(s1-s2);
    ans=min(ans,dif);
  }
  cout << ans << endl;
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, M;
int A[MAX_N], B[MAX_N];
ll dp[2010][2010];

void solve() {
	cin >> N >> M;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, M) cin >> B[i];
	A[N++] = 100001;
	B[M++] = 100002;
	rep(i, 0, N + 1) {
		dp[i][0] = 1;
	}
	rep(i, 0, M + 1) {
		dp[0][i] = 1;
	}
	rep(i, 1, N + 1) {
		rep(j, 1, M + 1) {
			ADD(dp[i][j], (mod + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) % mod);
			if(A[i - 1] == B[j - 1]) {
				ADD(dp[i][j], dp[i - 1][j - 1]);
			}
			// debug(i, j, dp[i][j]);
		}
	}
	cout << dp[N][M] << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 35072