akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int M = scanner.nextInt();

        scanner.close();

        int a = N*(N-1)/2;
        int b = M*(M-1)/2;
        System.out.println(a+b);
    }
}

Measured memory_bytes: 21972
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

tot = 0

for i in range(1,N+1):
  tot+=B[i-1]
  if i>1:
    if A[i-2]==A[i-1]-1:
      tot+=C[A[i-2]-1]

print(tot)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <stdlib.h> //for exit
#include <algorithm> //for sort...etc
#include <numeric> //for accumulate
using namespace std;

int main()
{
    while(1)
        {
            int n,n_sum=0;
            vector<int> income;
            cin >> n; // mは制限値
            if(n == 0) exit(0); //END STATE
            for(int i = 0 ; i < n; i++) //INPUT
            {
                int tpprice;
                cin >> tpprice;
                income.push_back(tpprice);
            }

            for(int i = 0; i < n; i++)
            {
                int target = accumulate(income.begin(),income.end(),0)/n;
                if(income[i] <= target)
                {
                    n_sum++;
                }
            }

            cout << n_sum << endl;  
        }
}


Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d;
	string s;
	cin>>s;
	a=s[0]-48;
	b=s[1]-48;
	c=s[2]-48;
	d=s[3]-48;
	
	if((a+b+c+d)==7)
	cout<<a<<'+'<<b<<'+'<<c<<'+'<<d<<"=7"<<endl;
	else if((a+b-c+d)==7)
	cout<<a<<'+'<<b<<'-'<<c<<'+'<<d<<"=7"<<endl;
	else if((a+b-c-d)==7)
	cout<<a<<'+'<<b<<'-'<<c<<'-'<<d<<"=7"<<endl;
	else if((a-b+c-d)==7)
	cout<<a<<'-'<<b<<'+'<<c<<'-'<<d<<"=7"<<endl;
	else if((a+b+c-d)==7)
	cout<<a<<'+'<<b<<'+'<<c<<'-'<<d<<"=7"<<endl;
	else if((a-b+c+d)==7)
	cout<<a<<'-'<<b<<'+'<<c<<'+'<<d<<"=7"<<endl;
	else if((a-b-c+d)==7)
	cout<<a<<'-'<<b<<'-'<<c<<'+'<<d<<"=7"<<endl;
	else
	cout<<a<<'-'<<b<<'-'<<c<<'-'<<d<<"=7"<<endl;
//	main();
}

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

using namespace std;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

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

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;


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

    ll N, K; cin >> N >> K;
    vi P(N); REP(i, N) cin >> P[i], --P[i];
    vll C(N); REP(i, N) cin >> C[i];

    vi used(N);

    ll ans = -LINF;
    REP(i, N) {
        if (used[i]) continue;
        vi cycle;
        ll sum = 0;
        int j = i;
        do {
            cycle.push_back(j);
            sum += C[j];
            used[j] = 1;
            j = P[j];
        } while (j != i);

        ll size = cycle.size();

        ll rem = K % size;

        ll max0 = -LINF, max1 = -LINF;
        REP(k, size) {
            ll t = 0;
            REP(u, size) {
                t += C[cycle[(k + u) % size]];
                if (u < rem) chmax(max0, t);
                else chmax(max1, t);
            }
        }
        ll m = K / size;
        if (sum < 0) {
            chmax(ans, max0);
            chmax(ans, max1);
        } else {
            chmax(ans, sum * m + max0);
            if (m > 0) chmax(ans, sum * (m-1) + max1);
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3792
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pp=pair<ll,pair<int,int>>;
using Graph=vector<vector<pair<int,ll>>>;

int main(){
  int N;
  cin>>N;
  if(N==3){
    cout<<"2 5 63"<<endl;
  }else{
    vector<bool> ans(300001,false);
    int count=0;
    int i=2;
    ll sum=0;
    while(count<N-1){
      while(!(i%2==0||i%3==0)){
        i++;
      }
      if(N%4==2||(N%4==3&&N<10)){
        if(i==2||i==4){
          i++;
          continue;
        }
      }
      if(N%4==3&&N>=10){
        if(i==3){
          i++;
          continue;
        }
      }
      ans.at(i)=true;
      count++;
      sum+=(ll)i;
      i++;
    }
    ll nth=0;
    while(sum%6!=0||nth==0){
      nth++;
      sum++;
    }
    while(ans.at(nth)==true){
      nth+=6;
    }
    ans.at(nth)=true;
    for(int i=0;i<300001;i++){
      if(ans.at(i)){
        cout<<i<<" ";
      }
    }
    cout<<endl;
  }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

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

int main(){

  string s;
  cin >> s;
  int a=0,b=0;
  rep(i,0,s.size()){
    if(i%2==0){
      if(s[i]!='0')a++;
      else b++;
    }else{
      if(s[i]!='1')a++;
      else b++;
    }
  }
  cout << min(a,b) << endl;

  return 0;
}


Measured memory_bytes: 512
n, k = map(int, input().split())
m = (n - 1) * (n - 2) // 2
if k > m:
    print(-1)
else:
    print(n - 1 + m - k)
    for i in range(2, n + 1):
        print(1, i)
    t = 0
    for i in range(2, n + 1):
        for j in range(i + 1, n + 1):
            if t >= m - k:
                break
            print(i, j)
            t += 1


Measured memory_bytes: 3608
class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数

    def find(self, x):
        #要素xが属するグループの根を返す
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        #要素xが属するグループと要素yが属するグループとを併合する
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.size(x) < self.size(y):
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x

    def same(self, x, y):
        #要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def size(self, x):
        #要素xが属するグループのサイズ（要素数）を返す
        x = self.find(x)
        return -self.parent[x]

    def is_root(self, x):
        #すべての根の要素をリストで返す
        return self.parent[x] < 0

    def members(self, x):
        #要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def group_count(self):
        #グループの数を返す
        return len(self.roots())

    def all_group_members(self):
        #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}
#############################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
AB = [LI() for _ in range(M)]

dp = [0]*M
dp[M-1] = N*(N - 1)//2

uf = UnionFind(N)

for i in range(M-1, 0, -1):
    x = AB[i][0] - 1
    y = AB[i][1] - 1
    if uf.same(x, y):
        #x,yが同じ木にある時
        dp[i-1] = tmp
    else:
        xs = uf.size(x)
        ys = uf.size(y)
        uf.unite(x, y)
        tmp = dp[i] - xs * ys
        dp[i-1] = tmp
        if tmp==0:
            break
#    print(uf.find(x),uf.find(y))
for i in range(M):
    print(dp[i])



Measured memory_bytes: 108764
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>
#include <bitset>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

string T;

int main() {

	cin >> T;

	for (auto c : T) {
		if (c == '?') cout << 'D';
		else cout << c;
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 3752
def main():
    N, K = map( int, input().split())
    P = list( map( int, input().split()))
    now = sum(P[:K])
    ans = now
    for i in range(K,N):
        now -= P[i-K]
        now += P[i]
        if now > ans:
            ans = now
    print((ans+K)/2)
if __name__ == '__main__':
    main()

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	if (n % 2 == 0){
		cout << n / 2;
		return 0;
	}
	else{
		cout << n / 2 + 1;
		return 0;	
	}
}

Measured memory_bytes: 256
function memoization(f) {
  const cache = {};
  return (...param) => {
    const c = cache[param];
    return typeof c === 'undefined' ? cache[param] = f(...param) : c;
  };
}

class _Node {
  constructor(id, parentId, leftId, rightId) {
    this.id = id;
    this.parentId = parentId;
    this.leftId = leftId;
    this.rightId = rightId;
  }
  get type() {
    return this.parentId === -1
        ? 'root'
        : this.leftId === -1 && this.rightId === -1
            ? 'leaf'
            : 'internal node'}
}

class BinaryTree {
  constructor() {
    this.nodes = [];
    this._nodeInfo = [];
    this.getDepth = memoization(this.getDepth.bind(this));
    this.getHeight = memoization(this.getHeight.bind(this));
  }
  static get Node() {return _Node;}

  add(id, leftId, rightId) {this.nodes[id] = new BinaryTree.Node(id, -1, leftId, rightId);}

  connect() {
    for (let i = 0; i < this.nodes.length; i++ ) this._nodeInfo[i] = {node:null, sibling:-1, degree:0};
    this.nodes.forEach(n => {
      if (n.leftId !== -1) {
        this.nodes[n.leftId].parentId = n.id;
        this._nodeInfo[n.leftId].sibling = n.rightId;
      }
      if (n.rightId !== -1) {
        this.nodes[n.rightId].parentId = n.id;
        this._nodeInfo[n.rightId].sibling = n.leftId;
      }
    });
    this.nodes.forEach(n => {
      this._nodeInfo[n.id] = {sibling: this._nodeInfo[n.id].sibling, node: n, degree: (n.leftId !== -1) + (n.rightId !== -1)}
    });
  }

  getDepth(id, i = 0) {
    let pid = this.find(id).parentId;
    return pid === -1 ? i : this.getDepth(pid, i + 1);
  }

  getHeight(id, i = 0) {
    if (id === -1) return i - 1;
    let n = this.find(id);
    let [lid, rid] = [n.leftId, n.rightId];
    return Math.max(this.getHeight(lid, i + 1), this.getHeight(rid, i + 1))
  }

  find(id) {return this.nodes[id]}

  print() {
    console.log(this._nodeInfo.map(o =>
      `node ${o.node.id}: parent = ${o.node.parentId}, sibling = ${o.sibling}, degree = ${o.degree}, depth = ${this.getDepth(o.node.id)}, height = ${this.getHeight(o.node.id)}, ${o.node.type}`
    ).join('\n'));
  }
}

(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());

  let tree = new BinaryTree();

  let id, l, r;
  lines.map(l => l.split(' ').map(Number)).forEach(function(line) {
    tree.add(line.shift(), line.shift(), line.shift());
  });
  tree.connect();
  tree.print();
})();



Measured memory_bytes: 16508
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define MP make_pair
typedef long long ll;
const int mod=1e9+7;
const int M=1e6+6;
const int inf=0x3f3f3f3f;
const ll INF=1e18;
int a[M],b[M],vis[M];
void pn(){
    cout<<"NO"<<'\n';
}
void py(){
    cout<<"YES"<<'\n';
}
int main(){
    int T;
    scanf("%d",&T);
    if(T==0)
        puts("1");
    else
        puts("0");
    return 0;
}


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

int main()
{
  int n,ans;
  vector<int> d(100);
  cin>>n;
  ans=n;
  for(int i=0;i<n;i++)
  {
    cin>>d.at(i);
  }
  for(int i=0;i<n-1;i++)
  {
    for(int j=0;j<n-1-i;j++)
    {
      if(d.at(j)>d.at(j+1))
      {
        swap(d.at(j),d.at(j+1));
       // cout<<i<<" "<<j<<endl;
      }
    }
  }
  for(int i=0;i<n-1;i++)
  {
    //cout<<d.at(i)<<" ";
    if(d.at(i)==d.at(i+1))ans--;
  }
  cout<<ans;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <string>
#include <tuple>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
//#include "toollib.h"
#pragma warning (disable:4018)
using namespace std;

int solve_GCD(int x, int y) {
	while (x != y) {
		if (x > y) {
			x -= y;
		}
		else {
			y -= x;
		}
	}
	return x;
}

int main() {
	int x, y;
	cin >> x >> y;
	cout << solve_GCD(x, y) << endl;
	return 0;
}

Measured memory_bytes: 3096
"use strict";
// 人様のコード参照
const main = arg => {
  	// お決まりの処理たち
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const K = parseInt(arg[0].split(" ")[1]);
    const p = arg[1].split(" ").map(n=>parseInt(n));
    
    // 期待値はpが大きいほど大きくなる
    // 最後に計算すれば良い
  	// 累積和の定義
  	let totalSum = new Array(N + 1).fill(0);
  	
    // 累積和
  	for(let i = 0; i < N; i++){
    	totalSum[i + 1] += totalSum[i] + p[i];
    }
  
    let max = 0;
    let index  = 0;    
    // Kの範囲で大きくなってるとこ探す
  	for(let j = K; j < N + K - 1; j++){
      	// 暫定チャンピオンを常に見ておく
      	let cand = totalSum[j] - totalSum[j - K];
       	// console.log(`cand${j}: ${cand}`);
        //累積和と最大値の紐付けはiのK個前からKまでそれは記憶しておく
      	// 暫定チャンピオンの情報を記録していく
      	if(max < cand){
        	max = cand;
          	index = j - K;
        }
	}
    let expectation = 0;
    // 期待値を計算
    for(let l = 0; l < K; l++){
	  	expectation += (1 + p[index + l])/2;
    }
    
    console.log(expectation);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 34592
from collections import Counter

N, K = map(int, input().split())
A = list(map(int, input().split()))

a = Counter(A).most_common()

L = []
if K < len(a):
    need = len(a) - K
    for i in range(1, need+1):
        L.append(a[-i][1])

print(sum(L))

Measured memory_bytes: 115656
#include<iostream>

int paper[10][10]={0};
int sx[] ={1, 0, -1, 0, 1, 1, -1,-1, -2, 2, 0, 0};
int sy[] ={0, 1, 0, -1, 1, -1, 1, -1, 0, 0, -2, 2};


void solve(int x, int y, int le){
	if(le==1){
		paper[x][y]++;
		for(int i=0;i<4;++i){
			int sx_=x+sx[i],sy_=y+sy[i];
			if(sx_ >= 0 && sx_ < 10 && sy_ >= 0 && sy_ < 10)paper[sx_][sy_]++;
		}
	}else if(le==2){
		paper[x][y]++;
		for(int i=0;i<8;++i){
			int sx_=x+sx[i],sy_=y+sy[i];
			if(sx_ >= 0 && sx_ < 10 && sy_ >= 0 && sy_ < 10)paper[sx_][sy_]++;
		}
	}else if(le==3){
		paper[x][y]++;
		for(int i=0;i<12;++i){
			int sx_=x+sx[i],sy_=y+sy[i];
			if(sx_ >= 0 && sx_ < 10 && sy_ >= 0 && sy_ < 10)paper[sx_][sy_]++;
		}
	}
}

int main(){
	int x, y, le;
	char dummy;
	while(std::cin>>x&&std::cin>>dummy&&std::cin>>y&&std::cin>>dummy&&std::cin>>le){
		solve(x,y,le);
	}
	int blank=0;
	int max=0;
	for(int i=0;i<10;++i){
		for(int j = 0; j < 10; ++j){
			if(paper[i][j]>max)max=paper[i][j];
			if(paper[i][j]==0)blank++;
		}
	}
	std::cout<<blank<<std::endl<<max<<std::endl;
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);

const ll mod=1e9+9;
const ll MAXN=5e3+5;
const ll inf=1e17;

int main()
{
    fastio;
    ll n,k;
    cout<<fixed<<setprecision(15);
    cin>>n>>k;
    vector<double > p(n);
    for(int i=0;i<n;i++){
        cin>>p[i];
        p[i]=(p[i]+1.0)/2.0;
    }
    double sum=0.0,max_sum=0.0;
    for(int i=0;i<k;i++) sum+=p[i];
    max_sum=sum;
    for(int i=k;i<n;i++){
        sum=sum+p[i]-p[i-k];
        max_sum=max(sum,max_sum);
    }
    cout<<max_sum<<endl;
}


Measured memory_bytes: 1792
n=int(input())
a=[[]] * n
x=[[]] * n
y=[[]] * n
for i in range(n):
  a[i]=int(input())
  x[i]=[[]] * a[i]
  y[i]=[[]] * a[i]
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())

com=[[0 for i in range(n) ] for j in range(2**n)]

for i in range(2**n):
  for j in range(n):
    if ((i >> j) & 1) == 1:
      com[i][j]=1
  #正直者の証言が全て合っているか。
  for j in range(n):
    if com[i][j]==1:
      for k in range(a[j]):
        if y[j][k]!=com[i][x[j][k]-1]:
          com[i]=[0 for l in range(n) ]
          break
sum=[sum(com[i]) for i in range(2**n) ]
print(max(sum))

Measured memory_bytes: 10356
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
int i=0;
int ans[10002];
while(cin>>x,x)
{
  ans[i]=x;
  i++;
}
for(int k=1;k<=i;k++)
{
  cout<<"Case "<<k<<": "<<ans[k-1]<<endl;
}
return 0;
}



Measured memory_bytes: 3108
N,K = map(int,input().split())
l = list(map(int,input().split()))
d = dict()
for a in l:
   if a in d:
      d[a] += 1
   else:
      d[a] = 1
v = list(d.values())
if len(v) <= K:
   print(0)
else:
   v.sort()
   print(sum(v[:-K]))

Measured memory_bytes: 33152
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int main(){
    int n;
    cin >> n;
    vector<string> a(3);
    in_arr(string, a, 3);
    int ret = 0;
    rep(i, n){
        if(a[0][i] == a[1][i]){
            if(a[0][i] == a[2][i]){
                continue;
            }
            ret++;
            continue;
        }
        if(a[0][i] == a[2][i]){
            ret++;
            continue;
        }
        if(a[1][i] == a[2][i]){
            ret++;
            continue;
        }
        ret += 2;
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void) {
    char S[27];
    int i,j,k=0;
    scanf("%s",S);
    for(i=0;i<strlen(S);i++){
    	for(j=0;j<strlen(S);j++){
    		if(i==j) continue;
    		if(S[i]==S[j]){
    			k=1;
    			break;
    		}
    	}
    }
    if(k==1){
    	printf("no\n");
    }else{
    	printf("yes\n");
    }
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define All(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
#define IN(a, b, x) (a<=x&&x<b)
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<ll>>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename t, typename u, typename Comp=less<>>
bool chmax(t& xmax, const u& x, Comp comp={}) { if(comp(xmax, x)) { xmax = x; return true; } return false;}
template<typename t, typename u, typename Comp=less<>>
bool chmin(t& xmin, const u& x, Comp comp={}) { if(comp(x, xmin)) { xmin = x; return true;} return false;}
const int INF = 1e8;
const ll infl = ll(1e18)+5;
/*
*ios::sync_with_stdio(false);
*cin.tie(0);
*/

const ll mod = 1e9+7;
ll dfs(int K,const vector<vector<ll>>&graph, int now, int from){
  int can_use_color_num;
  if(from == -1){
    can_use_color_num = K-1;
  }else{
    can_use_color_num = K-2;
  }
  if(K < graph[now].size()){
    return 0;
  }else{
    ll case_num = 1;
    for(auto e: graph[now]) {
      if(e == from) continue;
      case_num*=can_use_color_num;
      can_use_color_num--;
      case_num%=mod;
    }
    for(auto e:graph[now]){
      if(e == from) continue;
      case_num *= dfs(K,graph,e,now);
      case_num %= mod;
    }
    return case_num;
  }
}

int main(){
  int N,K;cin >> N >> K;
  vector<vector<ll>> graph(N);
  for(int i=0;i<N-1;i++){
    int a,b; cin >> a >> b,a--,b--;
    graph[a].push_back(b);
    graph[b].push_back(a); 
  }
  ll answer = K*dfs(K,graph,0,-1);
  answer%=mod;
  cout << answer << endl;
  return 0;

}

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

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> ans(N, 0);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        ans.at(a - 1)++;
        ans.at(b - 1)++;
    }
    for (int i = 0; i < N; i++)
    {
        cout << ans.at(i) << endl;
    }
}

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

int main(){
  int A,B,C,D;
  cin>>A>>B>>C>>D;
  for(int i=1; i<=100; i++){
    C-=B;
    if(C<=0){
      cout<<"Yes"<<endl;
      return 0;
    }
    A-=D;
    if(A<=0){
      cout<<"No"<<endl;
      return 0;
    }
  }
}
  

Measured memory_bytes: 3620
#include<stdio.h>
int main(void){
	int a,b;
	
	scanf("%d%d",&a,&b);
	if(a%3==0){
		printf("Possible");
		return 0;
	}
	
	if(b%3==0){
		printf("Possible");
		return 0;
	}
	
	if((a+b)%3==0){
		printf("Possible");
		return 0;
	}
	printf("Impossible");
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <limits.h>

int m[101][101];
int p[101];
int n;

void matrixchain(void);
int min(int, int);

main() {
  int i, tate, yoko;
  
  scanf("%d", &n);
  for(i = 0; i < n; i++) {
    scanf("%d %d", &tate, &yoko);
    if(i == 0) {
      p[i] = tate;
      p[i + 1] = yoko;
    }
    else {
      p[i + 1] = yoko;
    }
  }
  matrixchain();
  printf("%d\n", m[1][n]);
  return 0;
}

int min(int x, int y) {
  if(x >= y) {
    return y;
  }
  else {
    return x;
  }
}

void matrixchain(void) {
  int i, j, k, l, q;
  for(i = 1; i < n + 1; i++) {
    m[i][i] = 0;
  }
  for(l = 2; l < n + 1; l++) {
    for(i = 1; i < n - l + 2; i++) {
      j = i + l - 1;
      m[i][j] = INT_MAX;
      for(k = i; k < j; k++) {
	q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
	m[i][j] = min(m[i][j], q);
      }
    }
  }
}

Measured memory_bytes: 632
#include <iostream>
#include <queue>
#include <vector>

int main() {
  int n, x, y;
  std::cin >> n >> x >> y;

  std::vector<std::vector<int>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    g[i].push_back(i + 1);
    g[i + 1].push_back(i);
  }
  g[x - 1].push_back(y - 1);
  g[y - 1].push_back(x - 1);

  std::vector<int> res(n + 7, 0);
  for (int s = 0; s < n; ++s) {
    std::vector<int> dist(n, -1);
    std::queue<int> pool;
    dist[s] = 0;
    pool.push(s);
    while (!pool.empty()) {
      int v = pool.front();
      pool.pop();
      for (auto nv : g[v]) {
        if (dist[nv] >= 0)
          continue;
        dist[nv] = dist[v] + 1;
        pool.push(nv);
      }
    }
    for (auto &v : dist)
      res[v] += 1;
  }
  for (int k = 1; k < n; ++k)
    std::cout << res[k] / 2 << std::endl;
}


Measured memory_bytes: 3700
using System;
using System.Collections.Generic;

class program{

  static void Main(){
    string[] s=Console.ReadLine().Split(' ');
    int N=int.Parse(s[0]);
    int L=int.Parse(s[1]);
    
    int min=10000000;
    int point=10000000;
    for(int i=0;i<N;i++){
      int v = Math.Abs(L+i);
      if(v<=min) {
        point=i;
        min=v;
      }      
    }
    int sum=0;
    for(int i=0;i<N;i++){
      if(i!=point){
        sum+=L+i;
      }
    }    
    Console.WriteLine(sum);
  }
}

Measured memory_bytes: 13140
s=input()
ls=len(s)

sl=[]
for i in range(ls):
    sl.append(s[i])
nl=[int(j) for j in sl]

#"+"が入りうる箇所はls-1箇所ある
sumn=[]
#i=0~3
#i=0x00,0x01,0x10,0x11
for i in range(2**(ls-1)):
    #j=0~1
    mul=1
    for j in range(ls-1):
        number=mul*nl[ls-j-1]
        if ((i>>j)&1):
            mul=1
        else:
            mul*=10
        sumn.append(number)
    sumn.append(nl[0]*mul)
print(sum(sumn))


Measured memory_bytes: 9200
#include <cstdio>

int n, cnt, ans;
int num[6] = {0, 9, 90, 900, 9000, 90000};

int NumerofDigits(int key) {
    int tmp = 0;
    while(key) {
        key /= 10;
        ++tmp;
    }
    return tmp;
}

int main() {
    scanf("%d", &n);
    cnt = NumerofDigits(n);
    for (int i = 1; i < cnt; i += 2) {
        ans += num[i];
    }
    if (cnt == 5)
        ans += (n - 10000 + 1);
    else if (cnt == 3)
        ans += (n - 100 + 1);
    else if (cnt == 1)
        ans += n;
    printf("%d", ans);
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
const int INF = numeric_limits<int>::max();
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

bool is_prime(ll n) {
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return n != 1;
}

int main()
{
    ll n; cin >> n;
    deque<ll> b;
    rep(i,n) {
        ll a; cin >> a;
        if (i % 2 == 0)
            b.push_back(a);
        else
            b.push_front(a);
    }
    if (n % 2 == 1) reverse(b.begin(), b.end());

    rep(i,n) 
        cout << b[i] << " ";

    return 0;
}


Measured memory_bytes: 5196
#include<iostream>
using namespace std;
int main(){
    int w,h,x,y,r;
    cin >> w >> h >> x >> y >> r;
    if(r <= x && x <= w - r && r <= y && y <= h-r){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3116
n, m = map(int, input().split()) 
s = list(map(int, input().split())) 
t = list(map(int, input().split())) 

MOD = 1000000007

dp= [[0] * m for _ in range(n)] 

for i, si in enumerate(s):  
  for j, tj in enumerate(t):
    if i > 0:
      dp[i][j] += dp[i-1][j]
      
    if j > 0:
      dp[i][j] += dp[i][j-1]

    if si == tj:
      dp[i][j] += 1
    elif i > 0 and j > 0:
      dp[i][j] -= dp[i-1][j-1]
    
    dp[i][j] %= MOD

print((dp[n-1][m-1] + 1) % MOD)

Measured memory_bytes: 73180
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdio>
#include <queue>
using namespace std;

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

bool dp[100005];

int main(){
    rep(i,100005)  dp[i] = false;
    int n,k; cin >> n >> k;
    vector<int> a(n); rep(i,n){ 
        cin >> a[i];
    }
    rep(i,k+1){
            if(i < a[0]) dp[i] = false;
            else {
                bool flag = false;
                rep(j,n) {
                    if(i - a[j] >= 0 && dp[i - a[j]] == false) flag = true;
                }
                dp[i] = flag;
            }
           // cout << i <<  ":"  << ":" << dp[i] <<  endl;
    }
    if(dp[k]) cout << "First" << endl;
    else cout << "Second" << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
#include <math.h>
#include <typeinfo>
using namespace std;

struct obj {
	int t;
	int x;
	int y;
};

int main(void) {
	
	int N;
	cin >> N;

	vector<obj> list(N);
	for (int i = 0; i < N; i++)
	{
		cin >> list[i].t >> list[i].x >> list[i].y; 
	}

	string ans = "Yes";
	int preX, preY;
	preX = 0; preY = 0;
	for (int i = 0; i < N; i++)
	{
		int a = (list[i].x - preX) + (list[i].y - preY);
		if (list[i].t < abs(a))
		{
			ans = "No";
			break;
		}

		if ((list[i].x + list[i].y) % 2 != list[i].t % 2)
		{
			ans = "No";
			break;
		}

		preX = list[i].x;
		preY = list[i].y;
	}

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

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


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

    const int N = 1e6 + 5;
    vector<int> v(n) , is(N);
    for( int i = 0 ; i < n ; ++i ){
        cin >> v[i];
        is[v[i]]++;
    }

    vector<int> ga(N);
    for( int i = 1 ; i < N ; ++i ){
        if( is[i] ){
            for( int j = 2 ; j * i < N ; ++j ){
                ga[i * j] = 1;
            }
        }
    }

    int ans = 0;
    for( int &num : v ){
        if( ga[num] == 0 && is[num] == 1 ) ans++;
    }
    cout << ans ;

    return 0;
}

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

#ifndef M_PI
#define M_PI 3.14159265358979
#endif
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

using namespace std;

typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const ll INF = 1e15;
const ll MOD = 1e9 + 7;

int main() {
    ll i, j, k;
    ll N;
    cin >> N;
    vll A(N);
    for(auto &e : A)
        cin >> e;

    ll all = 0;
    for(i = 0; i < N; i++) {
        all ^= A[i];
    }
    for(i = 0; i < N; i++) {
        ll a = all ^ A[i];
        cout << a << endl;
    }

    return 0;
}


Measured memory_bytes: 4772
#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
#define ll long long
#define ld long double
#define pll pair<ll ,ll >
#define plll pair<ll,pll>
#define ppll pair<pll, pll>
#define pii pair<int, int> 
#define mod 998244353
#define pb push_back
ll power(ll a,ll b){
    ll res=1ll;
    while(b>0){
        if(b%2!=0) res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}
ll ncr(ll n,ll k){
    if(k>n-k) k=n-k;
    ll pro=1;
    for(ll i=0;i<k;i++){
        pro=(pro*(n-i))%mod;
        pro/=(i+1);
    }
    return (pro%mod);
}
vector<ll> prime;
void seive(){
    vector<bool > isprime(2000001,true);
    for(int i=2;i*i<=2000000;i++){
        if(isprime[i]){
            for(int j=i*i;j<=2000000;j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2;i<=1000000;i++){
        if(isprime[i]) prime.push_back(i);
    }
}
void swap(ll *a,ll *b) {
    ll temp=*a;
    *a=*b;
    *b=temp;
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    ll n,m;
    cin>>n>>m;
    ll ans=((n*(n-1))/2)+((m-1)*m)/2;
    cout<<ans<<endl;
    return 0; 
}


Measured memory_bytes: 256
def judge(s)
    if s[0] != ?A
        return false
    end
    if s[2..-2].count(?C) != 1
        return false
    end
    if s[1].downcase != s[1]
        return false
    end
    3.upto(s.size-2) do |i|
        if s[i] != ?C && s[i].downcase != s[i]
            return false
        end
    end
    if s[-1].downcase != s[-1]
        return false
    end
    return true
end

s = gets.chomp
puts judge(s) ? :AC : :WA

Measured memory_bytes: 1788
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N, K, S = map(int, input().split())
    A = [S for _ in range(K)]
    if S != 10 ** 9:
        B = [S + 1 for _ in range(N - K)]
    else:
        B = [S - 1 for _ in range(N - K)]
    C = A + B
    print(*C, sep=" ")


if __name__ == "__main__":
    main()


Measured memory_bytes: 10480
#include<bits/stdc++.h>
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;

#define int long long
#define cint cpp_int
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) (((a)+(b)-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2
#define PI acos(-1.0)

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;
typedef priority_queue<int> PQi;

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;}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vout(Vs &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vvout(VVi &v){for(int i=0;i<(v).size();i++) vout(v[i]);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int mypow(int x, int n, int m){if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}
int digit(int k,int i){string s = to_string(k);return s[s.size()-i]-'0';}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());} //vectorの同じ要素消す
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
int leng(int n){string s=to_string(n); return s.size();} //intの桁数
int digitsum(int n){int ret=0; while(n>0){ret+=n%10;n/=10;}return ret;} //桁和
int lesscount(int x,Vi &a){return lower_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx未満の数の個数
int orlesscount(int x,Vi &a){return upper_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx以下の数の個数
int morecount(int x,Vi &a){return a.size()-orlesscount(x,a);} //vector aにおけるxより大きい数の個数
int ormorecount(int x,Vi &a){return a.size()-lesscount(x,a);} //vector aにおけるx以上の数の個数
int count(int x,Vi &a) {return upper_bound(ALL(a),x)-lower_bound(ALL(a),x);} //vector aにおけるxの個数
Vi accum(Vi &v){Vi ret((v).size()+1);REP(i,0,(v).size()) ret[i+1]=ret[i]+v[i];return ret;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);
    string s;
    cin>>s;
    Vi alphabet(26,0);
    REP(i,0,s.size()){
        alphabet[s[i]-'a']++;
    }
    REP(i,0,26){
        if(alphabet[i]==0){cout<<(char)('a'+i)<<endl; return 0;}
    }
    cout<<"None"<<endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>vi,vs;
vector<ll> :: iterator vt;
ll arr[200009];
int main()
{
    ll n,t,x,y,z,j,i,k,flag =0,maxi=LONG_LONG_MIN ,mini=LONG_LONG_MAX,sum=0,c=0;
    map<ll,ll>mp;
    map<ll,ll> :: iterator mt;
    string s, ss;
    cin>>n;
    for(i = 0 ;i< n;i++)
    {
        cin>>x;
        vi.push_back(x);
    }
    for(i = 0 ;i<n ;i++)
    {
        cin>>x;
        vs.push_back(x);
    }
    for(i = 0 ;i<n ;i++)
    {
        sum+=vi[i];
        ll sum1=sum;
        for(j = i ;j< n ;j++)
        {
            sum1+= vs[j];
        }
        maxi = max(sum1,maxi);
    }
    cout<<maxi<<endl;
    return 0;
}


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

template <class T = long long>
struct BIT {
	//もとの配列a[i]はBIT内部ではvec[i+1]に対応
	vector<T> vec;
	int n;
	int pw2 = 1;  // n以下の最大の2冪
	BIT(int sz) : vec(sz + 1, 0), n(sz) {
		while(pw2 * 2 <= n) {
			pw2 *= 2;
		}
	}
	//元の値に足す 更新は不可
	void add(int place, T val, bool index = 0) {
		if(!index) place++;
		for(int x = place; x <= n; x += x & -x) vec[x] += val;
	}
	//端からの合計値計算
	T sum0(int a, bool index = 0) {
		if(index) a--;
		T ret = 0;
		for(int x = a; x > 0; x -= x & -x) ret += vec[x];
		return ret;
	}
	//クエリ
	T sum(int a, int b) { return sum0(b) - sum0(a); }
	//更新 クエリと併用で可能にした
	void update(int place, T val, bool index = 0) {
		T old = sum(place, place + 1);
		add(place, val - old);
		return;
	}
	int LowerBound(T val, int start = 0) {
		// startから足していって初めてval以上になる箇所を0-indexedで返す
		// 要素が全て非負のときのみ
		// [start, ret) >= val を満たすstart以上の最小のret
		// どこまで足してもvalに達しないときはn+1を返す
		if(val <= 0) return start;
		val += sum0(start);
		int x = 0;
		for(int k = pw2; k > 0; k /= 2) {
			if(x + k <= n && vec[x + k] < val) {
				val -= vec[x + k];
				x += k;
			}
		}
		return max(start, x + 1);
	}
	int UpperBound(T val, int start = 0) {
		// startから足していって初めてvalより大になる箇所を0-indexedで返す
		// 要素が全て非負のときのみ
		// [start, ret) > val を満たすstart以上の最小のret
		// どこまで足してもvalより大に達しないときはn+1を返す
		if(val < 0 /*LBとの変更点*/) return start;
		val += sum0(start);
		int x = 0;
		for(int k = pw2; k > 0; k /= 2) {
			if(x + k <= n && vec[x + k] <= /*LBとの変更点*/ val) {
				val -= vec[x + k];
				x += k;
			}
		}
		return max(start, x + 1);
	}
};

int main() {
	// https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_B
	int n, q;
	cin >> n >> q;
	BIT<int> b(n);
	for(int i = 0; i < q; i++) {
		int com, x, y;
		cin >> com >> x >> y;
		if(com) {
			cout << b.sum(x - 1, y) << endl;
		} else {
			b.add(x - 1, y);
		}
	}
}


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

int main(){
    int n,k,q;
    cin >> n >> k >> q;
    vector<int> a(q);
    rep(i,q) {
        cin >> a.at(i);
    }
    vector<int> points(n);
    rep(i,q){
        points[a[i]-1]++;
    }
    rep(i,n){
        if(k+points[i]-q > 0){
            cout << "Yes" << endl;
        }
        else cout << "No" << endl;
    }
    return 0;
}

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

using namespace std;

template <class T>inline T updmax(T& a, T b) {return a = max(a, b);}
template <class T>inline T updmin(T& a, T b) {return a = min(a, b);}

template <unsigned long long mod> class modint {
public:
	unsigned long long v;
	modint(const long long x = 0) : v(x % mod) {}
	modint operator+(const modint rhs) { return modint(*this) += rhs; }
	modint operator-(const modint rhs) { return modint(*this) -= rhs; }
	modint operator*(const modint rhs) { return modint(*this) *= rhs; }
	modint operator/(const modint rhs) { return modint(*this) /= rhs; }
	modint operator-() { return modint(mod - this->v); }
	modint& operator+=(const modint rhs) {
		v += rhs.v;
		if (v >= mod) v -= mod;
		return *this;
	}
	modint& operator-=(const modint rhs) {
		if (v < rhs.v) v += mod;
		v -= rhs.v;
		return *this;
	}
	modint& operator*=(const modint rhs) {
		v = v * rhs.v % mod;
		return *this;
	}
	modint inverse(modint a) {
		unsigned long long exp = mod - 2;
		modint ret(1ULL);
		while (exp) {
			if (exp % 2) { ret *= a; }
			a *= a;
			exp >>= 1;
		}
		return ret;
	}
	modint& operator/=(modint rhs) {
		(*this) *= inverse(rhs);
		return *this;
	}
	friend ostream& operator<<(ostream& os, modint& u) {
		os << u.v;
		return (os);
	}
	friend istream& operator>>(istream& is, modint& u) {
		is >> u.v;
		return (is);
	}
};

const int MOD = 998244353;
using mint = modint<MOD>;

template<class T>
T fastpow(T a, long long p){
	T tmp = a;
	T ret = 1;
	while(p){
		if(p & 1)ret *= tmp;
		p >>= 1;
		tmp = tmp * tmp;
	}
	return ret;
}

class Solution {
public:
	void solve() {
		int n;
		cin >> n;
		vector<int> a(n, 0);
		for(int i=0; i<n; i++)cin >> a[i];
		if(a[0] != 0){
			cout << 0 << endl;
			return;
		}
		sort(a.begin(), a.end());
		if(n != 1 && a[1] == 0){
			cout << 0 << endl;
			return;
		}
		int m = a[n-1];
		vector<int> cnt(m+1, 0);
		for(auto v: a)cnt[v]++;
		mint ret = 1;
		for(int i=0; i < m; i++){
			ret *= fastpow(mint{cnt[i]}, cnt[i+1]);			
		}
		cout << ret << endl;
		
		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ri register
#define int long long
#define E (n+1)
using namespace std; const int N=200010;
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;
}
int h,w;
string s[N];
signed main()
{
    h=read(), w=read();
    for(ri int i=1;i<=h;i++) cin>>s[i];
    for(ri int i=1;i<=h*2;i++) cout<<s[(i+1)/2]<<endl;
    return 0;
}

Measured memory_bytes: 9848
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()
#define pl pair<ll,ll>
#define fi first
#define se second
#define inf 1000000007

ll N,M;
ll a,b;
vector<pl> kukan;
vector <ll> west;


int main() {
    scanf("%lld%lld",&N,&M);
    rep(i,M) {
        scanf("%lld%lld",&a,&b);
        kukan.push_back(make_pair(a,b));
        west.push_back(a);
    }
    sort(kukan.begin(),kukan.end());
    sort(west.begin(),west.end());
    ll ans = 0;
    ll temp;
    for(ll i = M-1; i>= 0; i--){
        if (i == M-1){
            ans++;
            temp = kukan[i].fi;
            continue;
        }
        if (kukan[i].se > temp) continue;
        else{
            ans++;
            temp = kukan[i].fi;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3568
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
long long gcd(long long x, long long y){
    if(y==0) return x;
    else return gcd(y,x%y);
}
//最小公倍数
long long lcm(long long x, long long y){
    return x / gcd(x, y) * y;
}
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N,K; cin >> N >> K;
    string S; cin >> S;
    K--;
    for(int i=0;i<N;i++){
        if(i==K) cout << (char)(S[i]-'A'+'a');
        else cout << S[i];
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 3580
#include <stdio.h>

int main(void) 
{
  int n, q,i,z,count=0;
  int s[10000], t[500];
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &s[i]);
  }
  scanf("%d", &q);
  for (i = 0; i < q; i++) {
    scanf("%d", &t[i]);
  }
  for(i=0;i<q;i++){
    for(z=0;z<n;z++){
      if(t[i] == s[z]){
	count++;
	break;
      }
    }
  }
  
  printf("%d\n", count);
  return 0;
}



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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define mp            make_pair
#define pb            push_back
template<class T1, class T2> inline void minup(T1& m, T2 x){ if(m>x) m=static_cast<T2>(x); }
template<class T1, class T2> inline void maxup(T1& m, T2 x){ if(m<x) m=static_cast<T2>(x); }

#define INF 1000000000
#define MOD 1000000009
#define EPS 1E-9

const int N = 4000;
int n;
ll cost[N+1];
int id;
ll dc, dn;
ll res[N];

int main()
{
  while((cin >> n) && n){
    bool flag = true;
    rep(i, N+1) cost[i] = 0LL;
    int ptr = 0;

    rep(i, n){
      cin >> id >> dc >> dn;
      if(!cost[id]) res[ptr++] = id;
      cost[id] += dc * dn;
    }

    rep(i, ptr) if(cost[res[i]] >= 1000000){
      flag = false;
      cout << res[i] << endl;
    }
    if(flag) puts("NA");
  }

  return 0;
}

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

const int nax = 1e5+10, m = 3;
tuple<int,int,int> par[nax][m*2+1][m*2+1][m*2+1];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  int a, b, c;
  cin >> a >> b >> c;
  for (int i = 0; i <= n; i++) {
    for (int x = 0; x < m*2+1; x++) {
      for (int y = 0; y < m*2+1; y++) {
	for (int z = 0; z < m*2+1; z++) {
	  par[i][x][y][z] = {-1,-1,-1};
	}
      }
    }
  }
  par[0][m][m][m] = {0,0,0};
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    tuple<int,int,int> d[2];
    if (s == "AB") {
      d[0] = {1,-1,0};
      d[1] = {-1,1,0};
    } else if (s == "AC") {
      d[0] = {1,0,-1};
      d[1] = {-1,0,1};
    } else if (s == "BC") {
      d[0] = {0,1,-1};
      d[1] = {0,-1,1};
    } else assert(0);
    for (auto [dx,dy,dz] : d) {
      for (int x = 0; x < m*2+1; x++) {
	for (int y = 0; y < m*2+1; y++) {
	  for (int z = 0; z < m*2+1; z++) {
	    if (get<0>(par[i][x][y][z]) != -1 &&
		a+x-m+dx >= 0 && b+y-m+dy >= 0 && c+z-m+dz >= 0 &&
		x+dx >= 0 && x+dx < m*2+1 &&
		y+dy >= 0 && y+dy < m*2+1 &&
		z+dz >= 0 && z+dz < m*2+1) {
	      par[i+1][x+dx][y+dy][z+dz] = {x,y,z};
	    }
	  }
	}
      }
    }
  }
  for (int x = 0; x < m*2+1; x++) {
    for (int y = 0; y < m*2+1; y++) {
      for (int z = 0; z < m*2+1; z++) {
	if (get<0>(par[n][x][y][z]) != -1) {
	  cout << "Yes" << endl;
	  string ans;
	  for (int i = n; i; i--) {
	    auto [nx,ny,nz] = par[i][x][y][z];
	    if (x == nx+1) ans += 'A';
	    else if (y == ny+1) ans += 'B';
	    else if (z == nz+1) ans += 'C';
	    else assert(0);
	    x = nx, y = ny, z = nz;
	  }
	  reverse(ans.begin(), ans.end());
	  for (char ch : ans)
	    cout << ch << '\n';
	  return 0;
	}
      }
    }
  }
  cout << "No" << endl;
}


Measured memory_bytes: 405752
N = int(input())
X = [list(map(int, input().split())) for i in range(N)]
LR = [[x[0]-x[1], x[0] + x[1]] for x in X]
LR.sort(key=lambda x:x[1])

A = 1
right = LR[0][1]
for i in range(1, N):
    if right <= LR[i][0]:
        A += 1
        right = LR[i][1]
print(A)

Measured memory_bytes: 42792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define per(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define INF 2e9
#define LINF 1e18
typedef long long ll;
typedef pair<int, int> P;

int main() {
    string s; cin >> s;
    rep(i, 3) {
        if (s[i] == s[i+1]) {
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    string s;
    cin >> s;
    int ans = 0;
    string t = "ACGT";
    rep(i, s.size())
    {
        rep(j, s.size())
        {
            bool suc = true;
            for (int k = i; k < s.size() - j; k++)
            {
                bool flag = false;
                rep(c, 4)
                {
                    if (s[k] == t[c])
                        flag = true;
                }
                if (!flag)
                {
                    suc = false;
                    break;
                }
            }
            if (suc)
                ans = max(ans, int(s.size() - j) - i);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256