akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N,T,A;
  cin>>N>>T>>A;
  vector<int> h(N);
  int c,d,m=1000000;
  for(int i=0;i<N;i++){
    
    cin>>c;
    h.at(i)=(T*1000-c*6)-A*1000;
    if(h.at(i)<0)h.at(i)=-1*h.at(i);
    if(h.at(i)<m){
      m=h.at(i);
      d=i+1;
  }
  }
  cout<<d;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
// #include <windows.h>
// #include <conio.h>
// #include <mac.h>
// #include <linux.h>
#include <bits/stdc++.h>
using namespace std;
int For(int n,int ans,int k){
    if(n==0)return ans;
    ans+=min(ans,k);n--;
    return For(n,ans,k);
}
int n,k;
int main(){
    cin>>n>>k;
    cout<<For(n,1,k);
    return 0;
}

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

#define int long long
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) begin(x),end(x)

int mod = 1e9+7;
int inf = 4e18;
const int N = 5e5+5;
		
signed main()
{
    flash
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
		int a,b,c;
		cin>>a>>b>>c;
		if(b*c>=a)
		cout<<"Yes";
		else
		cout<<"No";
    }
    return 0;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define hell                         1000000007 
#define M                            1000000007
#define Maxi                      10000000000000000
#define lcm(a,b)                     (a*b)/__gcd(a,b)
#define ll                           long long
 
#define vll                          vector<ll>
#define vi                           vector<long long>
#define pll                          vector< pair<ll,ll> >
#define pb                           push_back
//#define mp                           make_pair
#define all(v)                       v.begin(),v.end()
#define lbnd                         lower_bound
#define ubnd                         upper_bound
#define bs                           binary_search
#define F                            first  
#define S                            second
#define rep(i,a,b)                   for(i=a;i<b;i++)
#define parr(a,n)                    for(i=0;i<n;i++) cout<<a[i]<<" ";cout<<endl;
#define pcont(a)                     for(auto i:a) cout<<i<<" ";cout<<endl;
#define ret(x)                       return cout<<x,0;
#define dbg(x)                       cout << #x << " is " << x << endl;
#define endl                           '\n'
 
 
// Debug //
 
#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
using namespace std;


int main()
{
    ll r;
    long double c;
    cin>>r;
    c=3.141592653589793238;
    cout<<2*c*r<<endl;
    return 0;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) do{}while(0)
#endif




int main(){
	ll n, d;
	cin >> n >> d;
	ll dd = d*d;
	
	ll ct = 0;
	rep(i,n) {
		ll x, y;
		cin >> x >> y;
		
		if ( x*x + y*y <= dd )
			ct++;
	}
	
	cout << ct << endl;

	return 0;
}




Measured memory_bytes: 3628
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

const int N = 110;

int n, x[N], y[N], h[N], p[N];
int H;

bool check(int X, int Y) {
	H = abs(x[p[1]] - X) + abs(y[p[1]] - Y) + h[p[1]];
	for (int j = 2; j <= n; ++j) {
		int &i = p[j];
		if (H - abs(x[i] - X) - abs(y[i] - Y) < 0 && h[i] == 0) continue;
		if (H != abs(x[i] - X) + abs(y[i] - Y) + h[i]) return false;
	}
	return true;
}

bool cmp(int a, int b) { return h[a] > h[b]; }

int main() {
#ifdef WYXLOCAL
	freopen("tmp.in", "r", stdin);
	freopen("tmp.out", "w", stdout);
#endif // WYXLOCAL
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d%d", &x[i], &y[i], &h[i]), p[i] = i;
	std::sort(p+1, p+n+1, cmp);
//	for (int i = 1; i <= n; ++i) printf("%d ", p[i]); puts(""); 
	for (int X = 0; X <= 100; ++X) for (int Y = 0; Y <= 100; ++Y) if (check(X, Y)) { 
			printf("%d %d %d\n", X, Y, H); // break; 
	}
	return 0;
}


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

#define ll long long
#define tc(t) int t;cin >> t; while(t--)
#define pb push_back
#define fi first
#define se second
#define debug1(x) cerr << #x << " = " << x << '\n';
#define debug2(x, y) cerr << #x << " = " << x << "   " << #y << " = " << y << "\n";
#define _ ios_base::sync_with_stdio(0);cin.tie(NULL);

void solve() {
    int n;
    cin >> n;
    while(n) {
        int rem = n%10;
        if(rem == 7) {
            cout << "Yes\n";
            return;
        }
        n /= 10;
    }
    cout << "No";
}

int main() {_
    int t = 1;
    //cin >> t;
    // Please remember to uncomment for taking test cases
    for(int i = 1; i<=t; i++) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <math.h>
#include <queue>
#include <stdio.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)
#define INF 1<<29;

int main()
{
    int n,k;
    string s;
    cin >> n >> k >> s;

    int cnt = 0;
    int d = 0;
    rep(i,n)
    {
        string si = s.substr(i,1);
        if(si == "L")
        {
            if(i > 0 && s.substr(i-1,1) == "L")
                ++cnt;
            if(i < n-1 && s.substr(i+1,1) == "R")
                ++d;
        }            
        else
        {
            if(i < n-1 && s.substr(i+1,1) == "R")
                ++cnt;
            if(i < n-1 && s.substr(i+1,1) == "L")
                ++d;
        }
    }

    if(d >= 2*k)
        cnt += 2*k;
    else
    {
        cnt += (d/2) * 2;
        if(d%2==1) cnt++;
    }
    
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 512
import java.util.*;
 
public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        sc.close();

        if(C%gcd(A,B) == 0)
            System.out.println("YES");
        else
            System.out.println("NO");

        
    }
    static int gcd(int n, int m){
        if(m > n)
            return gcd(m, n);
        else {
            if(m == 0)
                return n;
            else
                return gcd(m, n%m);
        }
    }
}

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

int main(){
    int n, m;
    cin >> n;
    map<int, int> mp;

    for(int i = 0;i < n;i++){
        int a;
        cin >> a;
        mp[a]++;
    }

    cin >> m;

    for(int i = 0;i < m;i++){
        int b;
        cin >> b;
        if(mp[b] == 0){
            cout << "NO" << endl;
            return 0;
        }
        mp[b]--;
    }

    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 9600
/* -------------------------------- Template -------------------------------- */

#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 ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }

// template<typename T> constexpr T inf = [](){ assert(false); };
// template<> constexpr int inf<int> = 1e9;
// template<> constexpr ll inf<ll> = 1e18;
// template<> constexpr ld inf<ld> = 1e30;

struct yes_no : std::numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

void solve();

int main() {
  std::locale loc(std::locale(), new yes_no);
  std::cout << std::boolalpha << std::setprecision(12) << std::fixed;
  std::cout.imbue(loc);
  solve();
  return 0;
}

using namespace std;

/* -------------------------------- Library -------------------------------- */

/* ---------------------------------- Main ---------------------------------- */

void solve() {
  int N;
  cin >> N;
  vector<int> a(1 << N);
  for (int &i: a) cin >> i;
  REP(i,N) {
    vector<int> b;
    for (int i = 0; i < int(a.size()); i += 2) {
      b.push_back(a[i] == a[i+1] ? a[i] : abs(a[i] - a[i+1]));
    }
    a = b;
  }
  cout << a.front() << endl;
  return;
}


Measured memory_bytes: 1916
n = int(input())
p = list(map(int, input().split()))

ruiseki = [10**9] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = min(ruiseki[i], p[i])

cnt = 0
for i in range(n):
    if p[i] < ruiseki[i]:
        cnt += 1
print(cnt)

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

using namespace std;
using ll = long long;

const ll MOD = 1000000007LL; // = 10^9 + 7
const double PI = 3.14159265358979;

void solve()
{
	string s, t;
	cin >> s >> t;
	int ans = 0;
	for(int i = 0; i < s.length(); ++i)
	{
		ans += s[i] != t[i];
	}
	cout << ans;
}

int main()
{
	fastio;
	solve();

	return 0;
}

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

int main() {
  long long n, a, b;
  cin >> n >> a >> b;
  if ((n == 1 && a != b) || a > b) {
    cout << 0 << endl;
    return 0;
  }
  long long ans = b*(n - 2) - a*(n - 2) + 1;
  cout << ans << endl;
  return 0;
}

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

int main() {
  string s;
  cin >> s;
  map<string, string> next_weather;
  next_weather["Sunny"] = "Cloudy";
  next_weather["Cloudy"] = "Rainy";
  next_weather["Rainy"] = "Sunny";
  cout << next_weather[s] << endl;
}

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

int main() {

    int N;
    int Y;

    int x = 0;
    int y = 0;
    int z = 0;

    int x10000 = 10000;
    int y5000  = 5000;
    int z1000  = 1000;

    cin >> N >> Y;

    for (int i = 0; i <= N; i++) {

        if ((x10000 * i) == Y && i == N){
            x = i;
            y = 0;
            z = 0;
            //break;

            cout << x << " " << y << " " << z << endl;
            return 0;
        }

        for (int j = 0; j <= N - i; j++) {
            x = i;
            y = j;
            z = N - i - j;

            // cout << "------" << endl;
            // cout << "x: " << x << endl;
            // cout << "y: " << y << endl;
            // cout << "z: " << z << endl;

             if ((x10000 * x) + (y5000 * y) + (z1000 * z) == Y && x + y + z == N) {
                cout << x << " " << y << " " << z << endl;
                return 0;
            }
        }
    }

    // cout << "---------------------" << endl;
    // cout << "x: " << x << endl;
    // cout << "y: " << y << endl;
    // cout << "z: " << z << endl;

    //if (x + y + z != N){
        
        cout << "-1 -1 -1" << endl;
    //}
    //else{

        //cout << x << " " << y << " " << z << endl;
    //}

    return 0;

}

Measured memory_bytes: 3608
#include <stdio.h>
#include <math.h>
#include <iostream>

using namespace std;

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

  int* W = new int[N];

  int S1 = 0, S2 = 0;

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

  int min = 9999;

  for (int i = 1; i <= N-1; i++)
  {
    S1 = 0, S2 = 0;
    for (int j = 0; j < N; j++)
    {
      if (j < i)
      {
        S1 += W[j];
      }
      else
      {
        S2 += W[j];
      }
    }
    if (abs(S1-S2) < min) min = abs(S1-S2);
  }

  printf("%d\n",min);
  return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AOddsOfOddness solver = new AOddsOfOddness();
        solver.solve(1, in, out);
        out.close();
    }

    static class AOddsOfOddness {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int oo = 0;
            for (int i = 1; i <= n; i++) if (i % 2 == 1) oo++;
            out.println(oo * 1.0 / n);
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}



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

using ll = long long;

int main() {
  int X, Y;
  cin >> X >> Y;

  int a,b;
  int ori_b = Y - 2*X;
  int ori_a = 4*X - Y;
  bool a_point = (ori_a % 2 == 0);
  bool b_point = (ori_b % 2 == 0);

  a = ori_a / 2;
  b = ori_b / 2;
  bool a_cond = (0 <= a);
  bool b_cond = (0 <= b);

  // cout << a << endl;
  if (a_point && b_point && a_cond && b_cond) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3624
#include <iostream>

using namespace std;

int main() {
    char a;
    cin >> a;
    if (a == 'A') {
        cout << 'T';
    }
    else if (a == 'T') {
        cout << 'A';
    }
    else if (a == 'G') {
        cout << 'C';
    }
    else {
        cout << 'G';
    }
    return 0;
}


Measured memory_bytes: 3556
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

#define POS(i,j) ((i)*(k-1)+(j))

void run(void){
  int n;
  scanf("%d",&n);
  int k=1;
  while((k+1)*k/2<=n) k++;
  if(n!=k*(k-1)/2){
    printf("No\n");
    return;
  }
  printf("Yes\n%d\n",k);
  if(n==1){
    printf("1 1\n1 1\n");
    return;
  }
  int *ans=(int *)calloc((k-1)*k,sizeof(int));
  int *alen=(int *)calloc(k,sizeof(int));
  int i,p;
  for(i=0,p=1;p+3<n;i++){
    for(int j=1;alen[i]<k-1;j++){
      ans[POS(i,alen[i])]=p;
      ans[POS(i+j,alen[i+j])]=p;
      p++;
      alen[i]++;
      alen[i+j]++;
    }
  }
  ans[POS(i,alen[i])]=p;
  ans[POS(i,alen[i]+1)]=p+1;
  ans[POS(i+1,alen[i+1])]=p+1;
  ans[POS(i+1,alen[i+1]+1)]=p+2;
  ans[POS(i+2,alen[i+2])]=p;
  ans[POS(i+2,alen[i+2]+1)]=p+2;
  for(i=0;i<k;i++){
    printf("%d ",k-1);
    for(int j=0;j<k-1;j++) printf("%d ",ans[POS(i,j)]);
    printf("\n");
  }
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 2048
#include <iostream>
#include <cstdio>

using namespace std;

long long n, ans = 1, pre = 1;
string s, t;

int main()
{
    cin>>n>>s>>t;
    long long i = 0;
    if(s[0] == t[0])
    {
        i++;
        ans *= 3;
    }
    else
    {
        i += 2;
        ans *= 6;
        pre = 2;
    }
    for(; i < n;)
    {
        if(s[i] == t[i] && pre == 1)
        {
            ans *= 2;
            i++;
        }
        else if(s[i] == t[i] && pre == 2)
        {
            i++;
            pre = 1;
        }
        else if(pre == 1)
        {
            ans *= 2;
            i += 2;
            pre = 2;
        }
        else
        {
            ans *= 3;
            i += 2;
        }
    }
    printf("%lld", ans % 1000000007);
    return 0;
}


Measured memory_bytes: 256
import math
a,b,c = map(float, input().split())
C = math.radians(c)
S = a*b*math.sin(C)*0.5
L = (a**2 + b**2 - 2.0*a*b*math.cos(C))**0.5+a+b
h = 2*S/a

print(S)
print(L)
print(h)



Measured memory_bytes: 5696
val pNum = LongArray(50 + 1) { 0L }
val pbNum = LongArray(50 + 1) { 0L }
fun main(args: Array<String>) {
    pNum[0] = 1
    pbNum[0] = 1
    for (i in 1..50) {
        pNum[i] = pNum[i - 1] * 2 + 1
        pbNum[i] = pbNum[i - 1] * 2 + 3
    }

    val (n, x) = readLongList()
    val ans = pan(n, x)
    println(ans)
}

// 食べたパティ・全体
fun pan(level: Long, eat: Long): Long {
    if (level == 0L) {
        return if (eat >= 1) 1L else 0
    }

    val next = level.toInt() - 1
    return if (eat <= 1 + pbNum[next]) {
        pan(next.toLong(), eat - 1)
    } else {
        pNum[next] + 1 + pan(level - 1, eat - (pbNum[next] + 2))
    }
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 38004
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    if(n == 1){
        cout << "Hello World" << endl;
    } else {
        int a, b;
        cin >> a >> b;
        cout << a + b << endl;
    }
    return 0;
}

Measured memory_bytes: 256
using System;

namespace abc070_c
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            long ret = long.Parse(Console.ReadLine());
            for (int i = 1; i < n; i++)
            {
                long now = long.Parse(Console.ReadLine());
                long a = Math.Min(ret, now);
                long b = Math.Max(ret, now);
                while (a != 0)
                {
                    long x = b % a;
                    b = a; a = x;
                }
                ret = ret / b * now;
            }
            Console.WriteLine(ret);
        }
    }
}

Measured memory_bytes: 13140
//abc077_b.cpp
//Sun Mar 11 20:45:08 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

int main(){
	int x;
	cin >> x;
	long long num=1;
	long long ans=0;
	while (num*num<=1000000000){
		if (num*num <= x){
			ans = num*num;
		}else{
			break;
		}
		num++;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
<?php
$inVal = explode(" ", trim(fgets(STDIN)));
if(($inVal[2] + $inVal[4]) < 0 
    || ($inVal[3] + $inVal[4]) < 0
    || ($inVal[2] + $inVal[4]) > $inVal[0]
    || ($inVal[3] + $inVal[4]) > $inVal[1]
    || ($inVal[2] - $inVal[4]) < 0 
    || ($inVal[3] - $inVal[4]) < 0
    || ($inVal[2] - $inVal[4]) > $inVal[0]
    || ($inVal[3] - $inVal[4]) > $inVal[1]
){
    echo "No".PHP_EOL;
} else {
    echo "Yes".PHP_EOL;
}
?>


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

using namespace std;

const int md = 1e9 + 7;

inline void add(int &x, int y) {
  x += y;
  if (x >= md) {
    x -= md;
  }
}

inline int mul(int x, int y) {
  return (int) ((long long) x * y % md);
}

inline int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) {
      res = mul(res, x);
    }
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}

inline int inv(int a) {
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  if (u < 0) {
    u += md;
  }
  return u;
}

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> segments;
  segments.emplace_back(0, 0);
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    segments.emplace_back(l - 1, i + 1);
    segments.emplace_back(r, i + 1);
  }
  sort(segments.begin(), segments.end());
  ++m;
  vector<vector<pair<int, int>>> extra(m);
  vector<int> adj(m);
  int ans = 1, inv9 = inv(9);
  for (int i = 1; i < (int) segments.size(); ++i) {
    int x = segments[i - 1].second, y = segments[i].second;
    if (segments[i - 1].first == segments[i].first) {
      adj[x] |= 1 << y;
      adj[y] |= 1 << x;
    } else {
      int base = mul(inv9, power(10, segments[i].first - segments[i - 1].first) - 1);
      ans = mul(ans, base);
      base = mul(base + 1, inv(base));
      extra[x].emplace_back(y, base);
    }
  }
  ans = mul(ans, power(10, n - segments.back().first));
  vector<int> coef(1 << m);
  for (int i = 0; i < 1 << m; ++i) {
    coef[i] = 1;
    for (int j = 0; j < m; ++j) {
      if (i >> j & 1) {
        if ((adj[j] & i) != adj[j]) {
          coef[i] = 0;
          break;
        }
        for (auto p : extra[j]) {
          if (i >> p.first & 1) {
            coef[i] = mul(coef[i], p.second);
          }
        }
      }
    }
  }
  vector<int> dp(1 << m);
  dp[0] = 1;
  for (int group = 0; group < 9; ++group) {
    vector<int> new_dp(1 << m);
    for (int i = 0; i < 1 << m; ++i) {
      if (dp[i]) {
        int subset = ((1 << m) - 1) ^ i;
        for (int j = subset; ; j = (j - 1) & subset) {
          if (group || (j & 1)) {
            add(new_dp[i | j], mul(dp[i], coef[j]));
          }
          if (!j) {
            break;
          }
        }
      }
    }
    swap(dp, new_dp);
  }
  ans = mul(ans, dp.back());
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 1144
//yukicoder@cpp14
//author:luckYrat(twitter:@luckYrat_)
//<ここに一言>

//せんげん！
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <bitset>

#include <cctype>
#include <utility>
#include <climits>


//なまえくーかん！
using namespace std;
using ll = long long;
using P = pair<ll,ll>;

//てーすう！
const int mod = 1000000007;
const int inf = (1<<30)-1;
const ll linf = (1LL<<62LL)-1;
const double EPS = (1e-10);

//でふぁいん！
#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)

//みじかく！
#define pb push_back
#define fir first
#define scn second
#define ednl endl

//いぇすのー！
#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")

//きんぼーnほーこー！！
P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる

計算量は変わらないが楽できるシリーズ
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる
*/
template <typename T>
T gcd(T a,T b){
  if(a%b==0)return b;
  else return gcd(b,a%b);
}
template <typename T>
T lcm(T a,T b){
  return a/gcd(a,b)*b;
}
int dp[200][200];
struct z{
	int a,b,c;
};
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}
int main(){
	int n,k;cin>>n>>k;
	int nw = 1;
	int z = 1;
	int ans = 1;
	while(n >= nw){
		while(nw > k*z){
			z++;
		}
		nw+=z;
		ans++;
	}
	cout << ans-1 << endl;
}



Measured memory_bytes: 3184
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int x;
    cin >> x;
    cout << 1-x << endl;
}


Measured memory_bytes: 3580
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,q[305][305],ans;
int main(void){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            char c;
            scanf(" %c",&c);
            q[i][j]=c-'a';
        }
    }
    for(int k=0;k<n;k++){
        bool o=true;
        for(int i=0;i<n&&o;i++){
            for(int j=0;j<n&&o;j++){
                if(q[i][(j+n-k)%n]!=q[j][(i+n-k)%n])o=false;
            }
        }
        if(o)ans++;
    }
    printf("%d\n",ans*n);
}

Measured memory_bytes: 640
// prakhsri_
#include<iostream>
#include<bits/stdc++.h>
#include<string>
#include<time.h>
using namespace std;
#define ll long long int
#define pb push_back
#define fi first i
#define se second
#define mod 1000000007
#define PI 3.1415926535897

int main(){
    int x,y;
    cin>>x>>y;
    if(4*x-y>=0 && (4*x-y)%2==0 && (4*x-y)/2<=x)
        cout<<"Yes";
    else if(y-2*x>=0 &&(y-2*x)%2==0 && (y-2*x)/2<=x)
        cout<<"Yes";
    else
        cout<<"No";
}   


Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
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; }
const long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}


int main(){
    ll sx, sy, tx, ty;
    cin>>sx>>sy>>tx>>ty;
 
    for(ll i=0;i<ty-sy;++i){
        cout<<'U';
    }
    for(ll i=0;i<tx-sx;++i){
        cout<<'R';
    }
    for(ll i=0;i<ty-sy;++i){
        cout<<'D';
    }
    for(ll i=0;i<tx-sx;++i){
        cout<<'L';
    }
 
    cout<<'L';
    for(ll i=0;i<ty-sy+1;++i){
        cout<<'U';
    }
    for(ll i=0;i<tx-sx+1;++i){
        cout<<'R';
    }
    cout<<'D'<<'R';
    for(ll i=0;i<ty-sy+1;++i){
        cout<<'D';
    }
    for(ll i=0;i<tx-sx+1;++i){
        cout<<'L';
    }
    cout<<'U';
    cout<<endl;
}


Measured memory_bytes: 256
count=int(raw_input())
ans =[]
for i in range(0,count):
    a,b,c=map(int,raw_input().split())
    if pow(a,2)+pow(b,2)==pow(c,2):
        ans.append("YES")
    elif pow(a,2)+pow(c,2)==pow(b,2):
        ans.append("YES")
    elif pow(b,2)+pow(c,2)==pow(a,2):
        ans.append("YES")
    else:
        ans.append("NO")

for i in range(0,count):
    print ans[i]


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


vector<int> sieve(int n) {
	vector<int> res(1, 2);
	vector<bool> prime(n, true);
	for(int i = 3; i < n; i += 2) {
		if(prime[i]) {
			res.push_back(i);
			for(int j = i * 3; j < n; j += i * 2)
				prime[j] = false;
		}
	}

	return res;
}

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

	vector<int> prime = sieve(10000000), q;

	for(int i = 3; i < prime.size(); ++i) {
		if(prime[i - 3] + 8 == prime[i])
			if(prime[i - 3] + 6 == prime[i - 1])
				if(prime[i - 3] + 2 == prime[i - 2])
					q.push_back(prime[i]);
	}

	for(int n; cin >> n, n;) {
		int idx = upper_bound(q.begin(), q.end(), n) - q.begin();
		cout << q[idx - 1] << endl;
	}
	
	return EXIT_SUCCESS;
}

Measured memory_bytes: 7384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+7;
const int mod=1e9+7;
int x;
int main()
{
  scanf("%d",&x);
  int a=x/500;
  int b=(x-a*500)/5;
  printf("%lld",1ll*a*1000+1ll*b*5);
 } 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    ll a, b;
    cin >> a >> b;
    map<ll, ll> ay;
    vector<ll> cd;
    for(ll i=1LL;i*i<=a;i++){
        if(a%i==0){
            if(i*i!=a){
              ay[i] = 1;
              ay[a/i] = 1;
            }else{
                ay[i] = 1;
            }
            
        }
    }
    for (ll i = 1LL; i * i <= b; i++) {
      if (b % i==0) {
        if (i * i != b) {
            if(ay[i]){
                cd.push_back(i);
            }
            if(ay[b/i]){
                cd.push_back(b/i);
            }
        } else {
          if (ay[i]) {
            cd.push_back(i);
          }
        }
      }
    }

    sort(cd.begin(), cd.end());
    int len=cd.size(), cnt=1;
    map<ll, int> com;
    rep2(i, 1, len){
        com[cd[i]] = 1;
    }
    rep2(i, 1, len){
        if(com[cd[i]]){
            cnt++;
        }
        rep2(j, i+1, len){
            if(cd[j]&&cd[j]%cd[i]==0){
                com[cd[j]] = 0;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 4304
X, K, D = map(int, input().split()) # 6, 2, 4

x = abs(X)
syo = x // D # 1 = 6 // 4
zan = K - syo # 1 = 2 - 1
ima = x - (D * syo) # 2 = 6 - (4 * 1)

if zan <= 0:
    ans = x - (K * D)
elif zan % 2 == 0:
    ans = min(ima, abs(ima - (D * 2)))
elif zan % 2 == 1:
    ans = min(ima + D, abs(ima - D))

print(ans)

Measured memory_bytes: 9180
package main

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

func main(){
  var sc = bufio.NewScanner(os.Stdin)
  var s string
  if sc.Scan() {
    s = sc.Text()
  }
  m := make(map[string]int)
  for _, c := range s {
    if times, ok := m[string(c)]; ok {
      m[string(c)] = times + 1
    }else{
      m[string(c)] = 1
    }
  }
  if len(m) == 2 {
    for _, times := range m {
      if times != 2 {
        fmt.Println("No")
        return
      }
    }
  }else{
    fmt.Println("No")
    return
  }
  fmt.Println("Yes")
}

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


int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i,N) cin >> A.at(i);

    for (int i = K; i < N; ++i) {
        if(A.at(i) > A.at(i - K)) {
            cout << "Yes" << endl;
        } else cout << "No" << endl;
    }
}



Measured memory_bytes: 4816
#include <stdio.h>
 
int main(void)
{
 
  long a, b;
  scanf("%ld %ld", &a,&b);

  long x = a * b;
 

 int tmp;

  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  int r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
  printf("%ld", x/b);
 
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ull = long long unsigned;
using P = pair<int,int>;
const int INF=1001001;
const int NMAX=8;

int main()
{
	int n;
	cin>>n;
	vector<ll>a(n);
	vector<ll>b(n);
	vector<ll>c(n,0);
	rep(i,n){
		cin>>a[i];
		b[i]=abs(a[i]);
		if (a[i]<0) c[i]=1;
	}

	sort(b.begin(),b.end());
	rep(i,n-1){
		if (c[i]==1){
			c[i]=0;c[i+1]=1-c[i+1];
		//	cout<<c[i+1]<<endl;
		}
	}
	ll ans;
	for (ll i=1;i<n;i++){
		ans+=b[i];
	}
	if (c[n-1]==0) ans+=b[0];
	else ans-=b[0];
	cout<<ans;

}


Measured memory_bytes: 2560
#include "bits/stdc++.h"

using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define lin "\n"
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(0)

void solve() {
    long double a, b, c, d;
    cin >> a >> b >> c >> d;
    cout.precision(0);
    cout << fixed << max(a * c, max(a * d, max(b * c, b * d))) << lin;
}

int main() {
    fast_io;
    int t = 1;
//    cin >> t;
//    scanf("%d",&t);
    int c = 1;
    while (t--) {
//        printf("Case %lld: ",c);
//        cout<<"Case "<<c<<": ";
        solve();
        c++;
    }
}

Measured memory_bytes: 3804
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl
const int MAX = 1000000;
const int MOD = 1000000007;

int main(){
	int n;
	cin>>n;
	bool p=true;
	REP(i,n){
		int a;
		cin>>a;
		if(a%2==0){
			if(!(a%3==0||a%5==0)){
				p=false;
				break;
			}
		}
	}
	if(p) OUT("APPROVED");
	else OUT("DENIED");
	return 0;
}

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9 + 7;

vll adj[MAXN]; ll visit[MAXN] = {};
int dx8[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dx4[] = {0, 1, 0, -1}, dy4[] = {1, 0, -1, 0};

// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, x, y, r, p, h, k;
string s, t;

ll node[4000000];
ll fours[4000000];
// <------------- Implement Functions Here ----------> //



// <------------- Start of main() -------------------> //

void MAIN() {
	ll a,b,k;
	cin>>a>>b>>k;

	ll cou = 0;
	while(cou < k) {
		if(cou & 1) {
			if(b&1) {
				b--;
			}
			b-=b/2;
			a+=b;
		}
		else {
			if(a&1) {
				a--;
			}
			a-=a/2;
			b+=a;
		}
		cou++;
	}
	cout<<a<<" "<<b;
}

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}


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

int main(){
  string s; cin >> s;
  int count0=0, count1=0;
  for(int i=0; i<s.size(); i++){
    if(i%2==0){
      if(s[i]=='1') count0++;
      else count1++;
    } else {
      if(s[i]=='0') count0++;
      else count1++;
    }
  }
  cout << min(count0,count1) << endl;
  return 0;
}

Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main()
{
    int x, y, z;
    int a, b, c;

    cin >> x >> y >> z;
    a = x;
    b = y;
    c = z;

    swap(a, b);
    swap(a, c);

    cout << a << " " << b << " " << c << "\n";

    return 0;
}

Measured memory_bytes: 256
import math
n = int(input())
mi =11
def f(a,b):
    return max(int(math.log10(a))+1,int(math.log10(b))+1)

for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
        t=f(i,n//i)
        if t<mi:
            mi=t
print(mi)


Measured memory_bytes: 3316
#include<iostream>
using namespace std;
int main(){
  string s,t;
  int r=0;
  cin>>s>>t;
  for(int i=0;i<s.size();i++){
    if(s[i]!=t[i]) r= r+1;
  }
  cout<< r<<endl;
  return 0;
}

Measured memory_bytes: 3920
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d,e,f,i;scanf("%d%d%d",&a,&b,&c);
  if(a==b && b==c && a%2==0){
    printf("-1\n");return 0;
  }
  for(i=0;a%2==0 && b%2==0 && c%2==0;i++){
    d = a;e = b;f = c;
    a = (e+f)/2;
    b = (d+f)/2;
    c = (d+e)/2;
  }
  printf("%d\n",i);
}

Measured memory_bytes: 3764
/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 998244353
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 200005
#define fi(a, b, c, d) for(int a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(int a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)

ll N, M, K, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;
ll fact[MAX_INT];
ll invfact[MAX_INT];

ll modMul(ll A, ll B) {
	return (A * B) % MOD;
}

ll modSum(ll A, ll B) {
	return (A + B) % MOD;
}

ll modPow(ll a, ll b, ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}

ll modInv(ll x) {
	return modPow(x, MOD - 2, MOD);
}

void precompute() {
	fact[0] = 1;
	fei(i, 1, N, 1) {
		fact[i] = modMul(fact[i - 1], i);
	}
	invfact[N] = modInv(fact[N]);
	for(int i = N - 1; i >= 0; i--) {
		invfact[i] = modMul(invfact[i + 1], i + 1);
	}
}

ll ncr(ll n, ll r) {
	if(n < r) {
		return 0;
	}
	ll ans = fact[n];
	ans = modMul(ans, invfact[r]);
	ans = modMul(ans, invfact[n - r]);
	return ans;
} 

int main() {
	scanf("%lld %lld %lld", &N, &M, &K);
	precompute();
	// fei(i, 0, N, 1) {
	// 	cout << fact[i] << " " << invfact[i] << "\n";
	// }
	ll ans = 0;
	ll curr = 0;
	fei(i, 0, K, 1) {
		curr = modMul(M, modPow(M - 1, N - 1 - i, MOD));
		curr = modMul(ncr(N - 1, i), curr);
		ans = modSum(ans, curr);
	}
	printf("%lld\n", ans);
	return 0;
}
/*
	Powered by Buggy Plugin
*/




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

using namespace std;

const int maxn = 1e6 + 3;

int n;
int a[maxn];
void read()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char ch;
        cin >> ch;

        a[i] = ch - '0';
    }
}

int cnt2(int num)
{
    int ans = 0;
    while (num % 2 == 0)
    {
        ans++;
        num /= 2;
    }

    return ans;
}

int cnt2fact[maxn];
void precompute()
{
    cnt2fact[0] = 0;
    for (int i = 1; i <= n-1; i++)
        cnt2fact[i] = cnt2fact[i-1] + cnt2(i);
}

bool comb_parity(int n, int k)
{
    return cnt2fact[n] - cnt2fact[k] - cnt2fact[n-k] > 0 ? 0 : 1;
}

void solve()
{
    for (int i = 1; i <= n-1; i++)
        a[i] = abs(a[i] - a[i+1]);

    precompute();

    bool parity = 0;
    for (int i = 1; i <= n-1; i++)
        if (comb_parity(n-2, i-1))
            parity ^= a[i] % 2;

    if (parity == 1)
    {
        cout << 1 << endl;
        return;
    }

    else
    {
        bool is_there = false;
        for (int i = 1; i <= n-1; i++)
            if (a[i] == 1)
            {
                is_there = true;
                break;
            }

        if (is_there)
        {
            cout << 0 << endl;
            return;
        }

        parity = 0;
        for (int i = 1; i <= n-1; i++)
            if (comb_parity(n-2, i-1))
            parity ^= a[i] / 2;

        if (parity)
            cout << 2 << endl;

        else
            cout << 0 << endl;
    }

}

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

    read();
    solve();
}


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

#ifdef DEBUG
#include "debug.h"
#endif

using namespace std;

#define mp make_pair
#define mt make_tuple
#define all(a) (a).begin(), (a).end()
#define rep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
#define sz(a) ((int)(a).size())
#define make_unique(a) (a).resize(unique(all((x))) - (x).begin())

typedef long long ll;

template<typename T> inline bool mmin(T& a, const T &b) { return a < b ? (a = b, true) : false; }
template<typename T> inline bool mmax(T& a, const T &b) { return a > b ? (a = b, true) : false; }

ll calc(int b, vector<int> &a) {
    ll res = 0;
    for (int i = 0; i < sz(a); ++i) {
        res += abs(a[i] - b);
    }
    return res; 
}

int main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= (i + 1);
    }
    sort(all(a));
    cout << min(calc(a[n / 2], a), calc(a[max(n / 2 - 1, 0)], a)) << '\n';
    
    return 0;
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl;
#define NN cout << "No" << endl;
#define ve vector
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
// *max_element(all(d))
// priority_queue<int,vector<int>,greater<int>>
int solve(){
  int n;
  cin >> n;
  vector<string>s(n);
  rep(i,n)cin >> s[i];
  rep(i,n)sort(all(s[i]));
  int msi = INF;
  rep(i,n)msi = min(msi,(int)s[i].size());
  string ans;
  string tmp;
  rep(i,n)if(msi == s[i].size())tmp = s[i];
  rep(i,tmp.size()){
    bool check = true;
    REP(j,1,n){
      bool can = false;
      rep(k,s[j].size()){
        if(tmp[i] == s[j][k]){
          can = true;
          s[j][k] = 'A';
          k = s[j].size() - 1;
        }
      }
      if(!can)check = false;
    }
    if(check){
      ans.push_back(tmp[i]);
    }
  }
  sort(all(ans));
  cout << ans << endl;
  return 0; 
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
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 main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<ll> A(N);
  for(int i=0; i<N; i++){
    cin >> A[i];
  }
  ll ans = 0;
  while(1){
    ll mx = 0;
    int id;
    for(int i=0; i<N; i++){
      if(chmax(mx,A[i])) id = i;
    }
    if(mx < N) break;
    ll cnt = mx/N;
    for(int i=0; i<N; i++){
      if(i == id){
        A[i] %= N;
      }else{
        A[i] += cnt;
      }
    }
    ans += cnt;
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 3536
#include<bits/stdc++.h>
#define se second
#define fi first
#define pb push_back
#define cn cout<<"\n"
#define rep(i,a,b) for(int i = a; i < b; i++)
#define repr(i,a,b) for(int i = a; i >= b; i--)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

#define _ ios::sync_with_stdio(0); cin.tie(0);

#define vi vector<int>
#define ii pair<int,int>
#define vii vector<ii>
#define ll long long
#define vll vector<ll>
#define flush fflush(stdout)

const int INF = 1e8;
const ll MOD = 1e9 + 7;

using namespace std;

int main(){
	_

	int t = 1;

	string s;
	cin>>s;

	int n = s.size();
	string a, b;
	rep(i, 0, n)
		if(i%2) a += '1';
		else a += '0'; 

	rep(i, 0, n)
		if(!(i%2)) b += '1';
		else b += '0'; 

	int a1 = 0, a2 = 0;
	rep(i, 0, n){
		if(a[i] != s[i]) a1++;
		if(b[i] != s[i]) a2++;
	}

	cout<<min(a1, a2); cn;


	return 0;
}

Measured memory_bytes: 720