akhauriyash/Code-Regression huggingface dataset:
require 'stringio'

class Vector
  attr_accessor :x, :y

  def initialize(x, y)
    @x, @y = x.to_f, y.to_f
  end

  def -(other)
    dx = @x - other.x
    dy = @y - other.y
    Vector.new(dx, dy)
  end

  def magnitude
    Math.sqrt(@x * @x + @y * @y)
  end

  def self.cross(pt1, pt2)
    pt1.x * pt2.y - pt1.y * pt2.x
  end
end

class Command
  attr_accessor :direction, :distance

  def initialize(direction, distance)
    @direction, @distance = direction, distance.to_f
  end
end

class DataSet
  START_POINT = Vector.new(10, 10)
  attr_reader :gem_locations, :commands, :line_segments

  def initialize(gem_locations, commands)
    @gem_locations, @commands = gem_locations, commands
    @line_segments = get_line_segments
  end

  private
  def get_line_segments
    line_segments = []
    current = START_POINT.clone
    @commands.each { |command|
      dx, dy = 0, 0
      case command.direction
      when 'N'
        dy = command.distance
      when 'E'
        dx = command.distance
      when 'S'
        dy = -command.distance
      when 'W'
        dx = -command.distance
      end

      start = current.clone
      current.x += dx
      current.y += dy
      line_segments << [start, current.clone]
    }
    line_segments
  end
end

def read_data(data)
  datasets = []
  StringIO.open(data, 'r') { |f|
    loop {
      # Read number of gems
      n_gems = f.gets.to_i
      break if n_gems.nil? or n_gems.to_i == 0

      # Read gem locations
      gem_locations = []
      n_gems.times {
        x, y = f.gets.split(/\s+/).map(&:to_i)
        gem_locations << Vector.new(x, y)
      }

      # Read number of commands
      n_commnands = f.gets.to_i

      # Read commands
      commands = []
      n_commnands.times {
        direction, distance = f.gets.split(/\s+/)
        commands << Command.new(direction, distance.to_i)
      }
      datasets << DataSet.new(gem_locations, commands)
    }
  }
  datasets
end

def dot(pt1, pt2)
  pt1.x * pt2.x + pt1.y * pt2.y
end

def distance(vec0, vec1)
  Vector.cross(vec0, vec1).abs / vec0.magnitude
end

data = STDIN.read
datasets = read_data(data)

datasets.each { |dataset|
  judge = [false] * dataset.gem_locations.size
  dataset.gem_locations.each_with_index { |location, i|
    dataset.line_segments.each { |line_segment|
      next if dot(line_segment[1] - line_segment[0], location - line_segment[0]) < 0
      next if dot(line_segment[0] - line_segment[1], location - line_segment[1]) < 0

      vec0 = line_segment[1] - line_segment[0]
      vec1 = location - line_segment[0]
      d = distance(vec0, vec1)
      if d < 0.1
        judge[i] = true
        break
      end
    }
  }
  puts judge.all? ? 'Yes' : 'No'
}

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

int main() {
        long long x, y, z, k;
        scanf("%lld%lld%lld%lld", &x, &y, &z, &k);
        vector<long long> xs(x), ys(y), zs(z);
        rep(i, x) scanf("%lld", &xs[i]);
        rep(i, y) scanf("%lld", &ys[i]);
        rep(i, z) scanf("%lld", &zs[i]);
        vector<long long> xys;
        rep(i, x) rep(j, y) xys.push_back(xs[i] + ys[j]);
        sort(xys.rbegin(), xys.rend());
        vector<long long> ans;
        rep(i, (long long) x * y > 1000000 ? k : min(x * y, k)) rep(j, z) ans.push_back(xys[i] + zs[j]);
        sort(ans.rbegin(), ans.rend());
        rep(i, k) printf("%lld\n", ans[i]);
        return 0;
}


Measured memory_bytes: 43208
#include<bits/stdc++.h>
using namespace std;
long long a,b,qw,wq,qq=1,ww=1,f[500001],o=0,h[500001],c[500001],v[500001];
long long q[500001],w[500001],ans=0;
long long get(long long y)
{
    if(f[y]==y) return y;
    return f[y]=get(f[y]);
}
void dfs(long long n,long long m)
{
    c[n]=m;
    for(int i=h[n];i;i=w[i])
    {
        if(q[i]!=f[n])
        {
            f[q[i]]=n;
            dfs(q[i],-m);
            c[n]+=c[q[i]];
        }
    }
}
int main()
{
    for(int i=1;i<=500000;i++)
    {
        f[i]=i;
    }
    cin>>a>>b;
    for(int i=1;i<=b;i++)
    {
        cin>>qw>>wq;
        if(get(qw)!=get(wq))
        {
            f[f[qw]]=f[wq];
        }
        else
        {
            qq=qw;
            ww=wq;
            continue;
        }
        o++;
        q[o]=wq;
        w[o]=h[qw];
        h[qw]=o;
        o++;
        q[o]=qw;
        w[o]=h[wq];
        h[wq]=o;
    }
    f[qq]=0;
    dfs(qq,1);
    if(a==b)
    {
        long long u=0;
        for(int i=ww;i;i=f[i])
        {
            u++;
            v[u]=c[i];
        }
        if(u%2)
        {
            if(c[qq]%2)
            {
                cout<<"-1";
                return 0;
            }
            for(int i=ww;i;i=f[i])
            {
                c[i]-=c[qq]/2;
            }
        }
        else
        {
            if(c[qq]!=0)
            {
                cout<<"-1";
                return 0;
            }
            sort(v+1,v+u+1);
            for(int i=ww;i;i=f[i])
            {
                c[i]-=v[u/2];
            }
        }
    }
    else
    {
        if(c[qq]!=0)
        {
            cout<<"-1";
            return 0;
        }
    }
    for(int i=1;i<=a;i++)
    {
        ans+=abs(c[i]);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 19064
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main() {
	long long n, m,ans=0;
	cin >> n >> m;
	for (long long i = 1; i*i <= m; i++) {
		if (m%i != 0)continue;
		long long j = m / i;
		if ( n*i <= m)ans = max(ans, i);

		if (n*j <= m)ans = max(ans, j);
		
	}
	cout << ans << endl;
	return 0;
}

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

#define mp make_pair
typedef long long ll;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
const int N = 1e5;
ll dist[N+100];
vector<pil>graph[N+100];
void dfs(int u,int p,ll d)
{
	dist[u] = d;
	for(auto it:graph[u])
	{
		if(it.first!=p){
			dfs(it.first,u,d+it.second);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for(int i=1;i<n;i++){
		int u,v;
		ll w;
		cin >> u >> v >> w;
		graph[u].push_back(mp(v,w));
		graph[v].push_back(mp(u,w));
	}
	dfs(1,-1,0);
	for(int i=1;i<=n;i++){
		if(dist[i]%2){
			cout << 1 << "\n";
		}
		else{
			cout << 0 << "\n";
		}
	}
}


Measured memory_bytes: 10240
// Date: 2020-03-13

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

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define FIO ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 3000 + 10;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

char s[N], t[N];
int n, m, dp[N][N];
pii pre[N][N];

int main() {
    scanf("%s%s", s+1, t+1);
    n = strlen(s+1), m = strlen(t+1);
    rep(i, 1, n) rep(j, 1, m) {
        if(dp[i-1][j] > dp[i][j-1]) dp[i][j] = dp[i-1][j], pre[i][j] = mk(i-1, j);
        else dp[i][j] = dp[i][j-1], pre[i][j] = mk(i, j-1);
        if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1] + 1, pre[i][j] = mk(i-1, j-1);
    }
    string ans;
    int x = n, y = m;
    while(dp[x][y] != 0) {
        if(s[x] == t[y]) ans += s[x];
        pii pa = pre[x][y];
        x = pa.fi, y = pa.se;
    }
    reverse(all(ans));
    cout << ans;

    return 0;
}

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

using namespace std;

typedef long long ll;

ll N, K;
ll A[200000 + 10];

bool f(ll L) {
	ll cnt = 0;
	if (L == 0)return true;
	for (int i = 0; i < N; i++) {
		cnt += A[i] / L;
		if (A[i] % L == 0)cnt--;
	}
	if (K >= cnt)return true;
	else return false;
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++)cin >> A[i];


	if (K == 0) {
		cout << *max_element(A, A + N) << endl;
		return 0;
	}

	ll ok = 0, ng = 1100000000;
	for (int i = 0; ng - ok > 1; i++) {
		ll mid = (ng + ok) / 2;

		if (f(mid))ng = mid;
		else ok = mid;
	}
	cout << ng << endl;
	return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int n, m, r, t, a, b, c, d[200][200];
vi to;

int main() {
	cin >> n >> m >> r;
	rep(i,r) {
		cin >> t;
		to.pb(t-1);
	}
	rep(i,n) {
		fill(d[i], d[i]+n, inf);
		d[i][i] = 0;
	}
	rep(i,m) {
		cin >> a >> b >> c;
		a--, b--;
		d[a][b] = d[b][a] = c;
	}
	
	// 全点対最短距離
	rep(k,n) rep(i,n) rep(j,n)
	    chmin(d[i][j], d[i][k]+d[k][j]);
	// 順列全列挙
	// 配列を事前にソートしないとnext_permutationで全ての順列が作れないことに注意
	sort(all(to));
	int ans = INT_MAX;
	do {
		int tmp = 0;
		reps(i,1,r) tmp += d[to[i-1]][to[i]];
		chmin(ans, tmp);
	} while (next_permutation(all(to)));
	cout << ans << ln;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll MOD = 1e9 + 7;
static const ll INF = (ll)1 << 62;
static const ll MAX_N = 100001;
static const ll MAX_M = 100001;

struct edge {
	ll to, cost;
};
typedef pair<ll, ll> P;
vector<edge> G[MAX_N];
ll V;
ll d[MAX_N];

//???
priority_queue<P, vector<P>, greater<P>> que;

void dijkstra(ll s) {
	fill(d, d + V, INF);
	d[s] = 0;
	que.push(P(0, s));
	while (!que.empty()) {
		P p = que.top(); que.pop();
		ll v = p.second;
		if (d[v] < p.first) continue;
		rep(i, 0, G[v].size()) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main() {
	ll E, r;
	cin >> V >> E >> r;
	rep(i, 0, E) {
		ll s, t, d; cin >> s >> t >> d;
		G[s].push_back(*(new edge{ t,d }));
	}
	dijkstra(r);

	rep(i, 0, V) {
		if (d[i] == INF)  cout << "INF" << endl;
		else cout << d[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 34752
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
    int tmp;
    string n;
    cin >> n;
    vector<string> week =
     {"SUN", "SAT", "FRI", "THU", "WED","TUE", "MON", "SUN"};
    REP1(i, 7){
        if(n == week[i]){
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
int main()
{
    she_told_me_dont_worry
    float r ;
    cin>>r;
    r *= (double)44;
    r /= (double)7;
    cout<<fixed<<setprecision(10);
    cout<<r<<endl;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 3780
#include<iostream>
using namespace std;
 
int main(){
  std::ios::sync_with_stdio(false);
  int n, k, i;
  cin >> n;
  for(i = 0; i != n; ++i){// 対照実験
    cin >> k;
    if((k & 1)){
      puts("first");
      return 0;
    }
  }
  puts("second");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
int main(void){
    ll n;
    cin>>n;
    vector<ll>l(n);
    rep(0,i,n)cin>>l[i];
    sort(l.begin(),l.end());
    ll ans=0;
    rep(0,i,n){
        rep(i+1,j,n){
            rep(j+1,k,n){
                if(l[i]+l[j]>l[k]&&l[i]!=l[j]&&l[j]!=l[k]&&l[i]!=l[k])++ans;
            }
        }
    }
    cout<<ans;
}

Measured memory_bytes: 3624
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで
//vector<vector<ll>> piyo(tate,vector<ll> (yoko));

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1000000000
#define ll long long
#define ln cout<<endl;
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

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

    ll maxi=0,f=0,mini=INF,sum=0;
    string str1,str2;
    ll h,w;
    ll n;
    ll a,b;
    cin>>n;
    vector<ll> v(n);
    rep(i,n) cin>>v[i];
    while(1){
    for(ll i=0;i<n;i++){
            if(v[i]%2) {f=1;break;}
            v[i]/=2;
    }
    if(f==1) break;
                sum++;

    }
    cout<<sum<<endl;
    return 0;
}


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

using lint = int64_t;

int main() {
    int n;
    cin >> n;
    vector<lint> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        a[i] += a[i - 1];
    }

    map<lint, lint> num;
    for (int i = 0; i < n; i++) {
        num[a[i]]++;
    }

    lint ans = num[0];
    for (auto p: num) {
        ans += p.second * (p.second - 1) / 2;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 14336
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = list(iss())
    print('Good' if N[0] != N[1] != N[2] != N[3] else 'Bad')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
using System;

namespace AGC014A{
	public class Program{
		public static void Main(string[] args){
			var sr = new StreamReader();
			//---------------------------------
			var A = sr.Next<int>();
			var B = sr.Next<int>();
			var C = sr.Next<int>();

			for(var i = 0; i < 114514; i++){
				if(A % 2 == 1 || B % 2 == 1 || C % 2 == 1){
					Console.WriteLine(i);
					return;
				}

				var na = (B + C) / 2;
				var nb = (C + A) / 2;
				var nc = (A + B) / 2;
				A = na;
				B = nb;
				C = nc;
			}

			Console.WriteLine(-1);
			//---------------------------------
		}
	}

	public class StreamReader{
		private readonly char[] _c = {' '};
		private int _index = -1;
		private string[] _input = new string[0];
		private readonly System.IO.StreamReader _sr = new System.IO.StreamReader(Console.OpenStandardInput());

		public T Next<T>(){
			if(_index == _input.Length - 1){
				_index = -1;
				while(true){
					string rl = _sr.ReadLine();
					if(rl == null){
						if(typeof(T).IsClass) return default(T);
						return (T) typeof(T).GetField("MinValue").GetValue(null);
					}
					if(rl != ""){
						_input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
						break;
					}
				}
			}
			return (T) Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
		}

		public T[] Next<T>(int x){
			var ret = new T[x];
			for(var i = 0; i < x; ++i) ret[i] = Next<T>();
			return ret;
		}

		public T[][] Next<T>(int y, int x){
			var ret = new T[y][];
			for(var i = 0; i < y; ++i) ret[i] = Next<T>(x);
			return ret;
		}
	}
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
#define rep(i,a) for(int i=0;i<a;i++)
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b;
    cout<<6-a-b<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    static final long DIV = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] pos = new int[n];
        int[] dpos = new int[2];
        Arrays.fill(pos, -1);
        for(int i=0; i<n+1; i++){
            int a = sc.nextInt() - 1;
            if(pos[a]<0){
                pos[a] = i;
            }else{
                dpos[0] = pos[a];
                dpos[1] = i;
            }
        }
        sc.close();

        long nleft = dpos[0];
        long nright = n - dpos[1];
        long[] fact = new long[n+1];
        long[] ifact = new long[n+1];

        fact[0] = 1;
        ifact[0] = 1;
        for(int i=1; i<n+1; i++){
            fact[i] = (fact[i-1] * (i+1)) % DIV;
            ifact[i] = inverseElement(fact[i], DIV);
        }
        long[] lcomb = new long[(int)nleft+1];
        long[] rcomb = new long[(int)nright+1];
        for(int i=0; i<nleft+1; i++){
            lcomb[i] = comb(nleft, i, fact, ifact);
        }
        for(int i=0; i<nright+1; i++){
            rcomb[i] = comb(nright, i, fact, ifact);
        }


        for(int i=0; i<n+1; i++){
            long ans = comb(n+1, i+1, fact, ifact);
            ans -= comb(nleft+nright, i, fact, ifact);
            if(ans < 0) ans += DIV;
            // for(int j=0; j<i+1; j++){
            //     if(j > nleft || (i-j) > nright) continue;
            //     ans -= lcomb[j] * rcomb[i-j];
            //     if(ans < 0) ans = (ans + (DIV*DIV))%DIV;
            // }
            System.out.println(ans);
        }
    }

    static long comb(long n, long k, long[] fact, long[] ifact){
        if(n < k) return 0;
        if(n <= 0 || k <= 0 || n-k == 0) return 1;
        return (((fact[(int)n-1] * ifact[(int)n-(int)k-1])%DIV) * ifact[(int)k-1])%DIV;
    }

    public static long inverseElement(long a, long n){
        long b = n, u=1, v=0;
        while(b > 0) {
            long t = a/b;
            a -= t*b;
            u -= t*v;
            //swap
            t = a;
            a = b;
            b = t;
            t = u;
            u = v;
            v = t;
        }
        u = u % n;
        if(u < 0) u += n;
        return u;
    }
}

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

int main(){
	int a;
	cin >> a;
	int ma = -1, flag;
	for(int i=1; i<=a; i++){
		int tmp = i, cnt = 0;
		while(tmp%2==0){
			cnt++;
			tmp = tmp/2;
		}
		if(cnt > ma){
			flag = i;
			ma = cnt;
		}
	}
	cout << flag << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc=new Scanner(System.in)){
			String line=sc.nextLine();
			String answer="";
			int length=line.length();
			for(int i=0;i<length;i++) {
				char ch=line.charAt(i);
				if(Character.isLowerCase(ch)==true) {
					ch=Character.toUpperCase(ch);
				}else {ch=Character.toLowerCase(ch);
			}System.out.printf("%c",ch);
		}System.out.println("");
	}

}
}


Measured memory_bytes: 29748
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
DP[left][right]
leftに何個はいったか、rightに何個入ったか、で管理すればいいか
*/
int main(){
  ll N; cin>>N;
  vector<pair<ll,ll>> K(N,make_pair(0,0));
  vector<vector<ll>> DP(N+1,vector<ll>(N+1,0));
  for(int i=0; i<N; i++){
    ll A; cin>>A;
    K[i].first=A;
    K[i].second=i;
  }
  sort(K.begin(), K.end(), [](auto& x, auto& y){return x.first > y.first;});
  for(int i=0; i<N; i++){//総数-1
    for(int R=0; R<=i+1; R++){//右側に何個入ってるか
      ll L=(i+1)-R;//左側に何個はいってるか
      if(L>0)
        DP[L][R]=max(DP[L][R], DP[L-1][R] + K[i].first*abs(K[i].second-(L-1))); 
      if(R>0)
        DP[L][R]=max(DP[L][R], DP[L][R-1] + K[i].first*abs(K[i].second-(N-R)));
    }
  }
  ll ans=0;
  for(int i=0; i<=N; i++)
    ans=max(ans, DP[i][N-i]);
  cout<<ans<<endl;
}

Measured memory_bytes: 34620
s=input()
a,b,c,d=[int(s[i]) for i in range(4)]
for i in range (2**3):
    res=a
    ans=[str(a)]
    for j in range (3):
        if i >> j &1:
            res+=int(s[j+1])
            ans+=["+",s[j+1]]
        else:
            res-=int(s[j+1])
            ans+=["-",s[j+1]]
    if res==7:
        ans+=["=7"]
        print("".join(ans))
        break

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

int main(){
  int n;  cin >> n;
  vector<int> l(n+1);  l[n] = 1e9;
  for(int i=0; i<n; i++)  cin >> l[i];
  sort(l.begin(), l.end());

  int ans = 0;
  for(int i=0; i<n-2; i++)    
    for(int j=i+1; j<n-1; j++)
      ans += (int)(lower_bound(l.begin()+j, l.end(), l[i]+l[j]) - l.begin()) - j - 1;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3648
<?php

$str = trim(fgets(STDIN));
list ($n, $m) = array_map("intval", explode(" ", $str));

$array = [];
for ($i=0; $i<$n; $i++) {
    $tmpStr = trim(fgets(STDIN));
    list ($day, $reward) = array_map("intval", explode(" ", $tmpStr));
    // 報酬が多い順、日数が少ない順にsortして、順番に受けていく
    // 残り日数的に受けられない仕事はスキップ

    if ( !isset($array[$day]) ) {
        $array[$day] = [];
    }
    $array[$day][] = $reward;
}

ksort($array);


$result = 0;
$queue = new SplPriorityQueue();
for ($i=$m-1; 0<=$i; $i--) {
    $remain = $m-$i;

    if ( isset($array[$remain]) ) {
        foreach ($array[$remain] as $reward) {
            $queue->insert($reward, $reward);
        }
    }

    if (!$queue->isEmpty()) {
        $result += $queue->extract();
    }
}

echo "$result\n";


Measured memory_bytes: 60660
#15
import sys

s = input()
l = len(s) 
for i in range(l+1):
    for j in range(l+1):
        mozi1 = s[0:i]
        mozi2 = s[j:]
        if mozi1+mozi2 == "keyence":
            print("YES")
            sys.exit()
print("NO")

Measured memory_bytes: 9112
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int EA(int a,int b){
  if(a==0||b==0){
    return max(a,b);
  }else{
    if (a%b==0){
        return b;
      }else{
        return EA(b,a%b);
      }
    }
}
int main(){
  int N;
  cin>>N;
  int A[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  int tmp1[N+1];
  int tmp2[N+1];
  tmp1[0]=0;
  tmp2[0]=0;

  for(int i=0;i<N;i++){
    tmp1[i+1] = EA(tmp1[i],A[i]);
  }
  //tmp2[i]:後ろからi番目までの最大公約数
  for(int i=0;i<N;i++){
    tmp2[i+1] = EA(tmp2[i],A[N-1-i]);
  }
  int ans = 0;
  for(int i=0;i<N;i++){
    ans = max(ans,EA(tmp1[i],tmp2[N-1-i]));
      
  }
  cout<<ans<<"\n";
}


Measured memory_bytes: 1408
N, M, P = map(int, input().split())
E = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a - 1, b - 1, P - c)
INF = float("inf")
d = [INF for _ in range(N)]
d[0] = 0
for i in range(2*N):
    for f, t, w in E:
        if d[t] > d[f] + w:
            d[t] = d[f] + w
            if i >= N:
                d[t] = -INF
    if i == N-1:
        dN = d[-1]
if dN != d[-1]:
    print(-1)
elif dN > 0:
    print(0)
else:
    print(-dN)

Measured memory_bytes: 51820
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>


using namespace std;

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

const long long INF = 1LL << 60;

#define rep(i, e) for(int i = 0; i < e; i++)
#define repp(i, s, e) for(int i = s; i < e; i++)
#define N_Max 100
#define Card_Max 36
#define p(a) printf("%d\n", a);
#define ll long long
#define ull unsigned long long
#define MAX 1e9
#define NIL -1

void print(const std::vector<ll>& v)
{
  std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
  });
  std::cout << std::endl;
}

int main() {
    ull N,cnt=0;
    string S;
    cin >> N >> S;
 
    for (int i = 0; i < N-2; i++)
    {
        if(S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C'){
            cnt++;
        }
    }
    cout << cnt << endl;
}

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

int main(){
	int len=0;
	int i;
	char str[21];
	
	while(scanf("%20s",str) != EOF){
	
		len = strlen(str);
	
		for(i=len-1;i>-1;--i){
			printf("%c",str[i]);
		}
		printf("\n");
	}
	
	return 0;
}

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

#include <math.h>
#include <stdio.h>

using namespace std;

int main(void) {
	int a[3];
	scanf("%d%d%d", &a[0], &a[1], &a[2]);
	sort(a, a+3);
	int ans = 0;
	int d1 = a[2] - a[0];
	int d2 = a[2] - a[1];

	ans += d1/2;
	d1 %= 2;
	ans += d2/2;
	d2 %= 2;

	if (d1 * d2 == 1) ans++;
	else if (d1 + d2 == 1) ans += 2;
	printf("%d\n", ans);
	return 0;
}




Measured memory_bytes: 256
s = input()
if int(len(s)%2) == 1:
  s = s[:len(s)//2] + s[(len(s)//2 + 1):]
n = 0
lens = int(len(s) / 2)
for i in range(lens):
  if s[0] != s[-1]:
    n+= 1
  s = s[1:-1]
print(n)

Measured memory_bytes: 3060
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		String s = sc.next();
		char[] c = s.toCharArray();

		Arrays.sort(c);
		if(c[0]==c[1]&&c[2]==c[3]&&c[1]!=c[2]) out.println("Yes");
		else out.println("No");

		out.flush();
	}
}


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

using namespace std;

int main(){
    int n;
    cin >> n;
    double arr[n];
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    sort(arr, arr + n);
    for(int i = 1; i < n; ++i){
        arr[i] = (arr[i] + arr[i - 1])/2;
    }
    cout << arr[n - 1];
    return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
typedef long long ll;
#define PI 3.14159265
ll exponent(ll x,ll n,ll m)
{  if(n==0)
    return 1;
    if(n%2!=0)
    {
        return (x*exponent(((x%m)*(x%m))%m,(n-1)/2,m))%m;
    }
    else
    return exponent(((x%m)*(x%m))%m,n/2,m);
}
ll find(ll fact[],ll invfact[],ll n,ll a,ll r)
{
    if(r>a)
        return 0;
    ll ans=fact[a];
    ans=(ans%mod*invfact[r]%mod)%mod;
    ans=(ans%mod*invfact[a-r]%mod)%mod;
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(NULL);
    ll n,k;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    ll fact[n+1];
    fact[0]=1;
    for(int i=1;i<=n;i++)
        fact[i]=(fact[i-1]%mod*i%mod)%mod;
    ll invfact[n+1];
    invfact[n]=exponent(fact[n],mod-2,mod);
    for(int i=n-1;i>=0;i--)
        invfact[i]=(exponent(fact[i],mod-2,mod)+mod)%mod;
   // cout<<find(fact,invfact,n,4,3)<<endl;
    //cout<<fact[6]<<" "<<invfact[3]<<" "<<invfact[3]<<endl;
    ll sum_max=0,sum_min=0;
    for(int i=k-1;i<n;i++)
        {sum_max=(sum_max%mod+(find(fact,invfact,n,i,k-1)%mod*a[i]%mod)%mod)%mod;
   // cout<<i<<" "<<find(fact,invfact,n,i,k-1)*a[i]<<endl;
   }
    for(int i=0;i<=(n-k);i++)
        sum_min=(sum_min%mod+(find(fact,invfact,n,n-i-1,k-1)%mod*a[i]%mod)%mod)%mod;
    cout<<(sum_max-sum_min+mod)%mod;
    return 0;
}


Measured memory_bytes: 2560
#!/usr/bin/env python3
import sys
import itertools
import bisect


def solve(N: int, P: "List[int]", Q: "List[int]"):

    nums = [i for i in range(1, N + 1)]
    perm = list(itertools.permutations(nums, N))
    perm.sort()

    p_at = 0
    for i, pr in enumerate(perm):
        if pr == tuple(P):
            p_at = i + 1
        if pr == tuple(Q):
            q_at = i + 1
    print(abs(p_at - q_at))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P, Q)


if __name__ == "__main__":
    main()


Measured memory_bytes: 8052
#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector <int> v(3);
    for(int i=0;i<3;i++)
    {
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    double a=(v[0]*v[1])/2;
    cout<<(int)a<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  char str[4];
  int r = 0, maxn;
  for(;scanf("%s", str) != EOF;)
  {
    r = 0; maxn = 0;
	if(str[0] == 'R') maxn = r = 1;
	for(int i = 1;i < 3;i++)
	{
		if(str[i] == 'R' && str[i-1] == 'R')
		{
			r++;
			if(maxn < r) maxn = r;
		}
		else if(str[i] == 'R' && str[i-1] != 'R')
		{
			r = 1;
			if(maxn < r) maxn = r;
		}
	}
    printf("%d\n", maxn);
  }
  return 0;
}

Measured memory_bytes: 3808
import sys
sys.setrecursionlimit(1000001)

def main():
    n, m = map(int, input().rstrip().split())
    dist = [[500000 for i in range(n)]for j in range(n)]

    for i in range(n):
        for j in range(n):
            if (i==j):
                dist[i][j]=0

    a = []
    b = []
    c = []

    for i in range(m):
        x, y, z = map(int, input().rstrip().split())
        dist[x-1][y-1] =  min(dist[x-1][y-1], z)
        dist[y-1][x-1] =  min(dist[x-1][y-1], z)
        a.append(x-1)
        b.append(y-1)
        c.append(z)
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
    #print(dist)
    result = m

    for i in range(m):
        for j in range(n):
            if dist[j][a[i]] + c[i] == dist[j][b[i]]:
                result -= 1
                break

    print(result)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 40944
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define REP(i, start, end) for (ll i = start, i##Len = (end); i < i##Len; ++i)
#define REPR(i, start, end) for (ll i = start, i##Len = (end); i > i##Len; --i)
using ll = long long;
using namespace std;

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

    ll n;
    cin >> n;
    ll ans = 0;
    REP(i, 1, n + 1)
    REP(j, 1, min(i, n / i) + 1)
    {
        if (n - i * j > 0)
        {
            if (i != j)
                ans += 2;
            else
                ++ans;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3648
#include <iostream>
#include <stack>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <map>

#define rep(i,n) for(int i=0; i < n; i++)
using ll =  long long;
using namespace std;

int main()
{
    int ans = 0;
    ll yokin = 100, x;
    cin >> x;
    
    
    while (x > yokin)
    {
        yokin *= 1.01;
        ans++;
    }
    
    cout << ans << endl;
    return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int T;
int N;
ll A[202];
string S;

template<class C> int gf2_rank(vector<C>& V) { /* input */
	int i,j;
	int N=V.size();
	FOR(i,N) {
		int x=max_element(V.begin()+i,V.end())-V.begin();
		if(V[x]==0) break;
		swap(V[i],V[x]);
		C msb=1;
		while(msb<<1 <= V[i]) msb<<=1;
		FOR(j,N) if(j!=i) if(V[j]&msb) V[j]^=V[i];
	}
	sort(ALL(V));
	reverse(ALL(V));
	while(V.size() && V.back()==0) V.pop_back();
	return V.size();
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<ll> V;
		FOR(i,N) cin>>A[i];
		cin>>S;
		
		for(i=N-1;i>=0;i--) {
			if(S[i]=='0') {
				V.push_back(A[i]);
				gf2_rank(V);
			}
			else {
				x=V.size();
				V.push_back(A[i]);
				gf2_rank(V);
				if(V.size()>x) break;
				
			}
		}
		if(i>=0) cout<<1<<endl;
		else cout<<0<<endl;
		
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 3612
import java.io.*;
import java.util.*;

public class Main{
  public static void main(String[] args){
    try {
      Scanner sc = new Scanner(System.in);
      int s, m=0;
      LinkedList<Integer> a = new LinkedList<Integer>();
      
      s=Integer.parseInt(sc.next());
      a.add(s);
      out: for(int i=0; i<=1000000; i++){
        if(a.get(i)%2==0){
          a.add(a.get(i)/2);
        }else{
          a.add(a.get(i)*3+1);
        }
        for(int j=0; j<i+1; j++){
          if(a.get(i+1)==a.get(j)){
            m=i+2;
            break out;
          }
        }
      }

      System.out.println(m);
      
                
      }catch (Exception e) {
      System.out.println("out");
    }
  }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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; }

int dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍


int main(){
	string s;cin>>s;
    ll ans=9999999999;
    rep(i,0,s.size()-2){
        if(ans > abs(753-stoi(s.substr(i,3)))) ans=abs(753-stoi(s.substr(i,3)));
    }
    cout<<ans<<ednl;
}


Measured memory_bytes: 256
#include <stdio.h>
using namespace std;

int main()
{
    int a, b;
    char *str = "No";
    scanf("%d %d", &a, &b);
    if(b == 100) b += a*1000;
    else if(b < 10) b += a*10;
    else b += a*100;

    for(int i = 4; i <= 1000; i++){
        if(i*i >= b){
            if(i*i == b) str = "Yes";
            break;
        }
    }
    printf("%s", str);
    return 0;
}

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


int main(){
    stack<int> s;
    string input;
    cin >> input;
    s.push(stoi(input));
    int temp;
    while (cin >> input) {
        if (input[0] == '+'){
            temp = s.top();
            s.pop();
            temp += s.top();
            s.pop();
            s.push(temp);
        }
        else if (input[0] == '-'){
            temp = -1 * s.top();
            s.pop();
            temp += s.top();
            s.pop();
            s.push(temp);
        }
        else if (input[0] == '*'){
            temp = s.top();
            s.pop();
            temp *= s.top();
            s.pop();
            s.push(temp);
        }
        else {
            s.push(stoi(input));
        }
    }
    cout << s.top() << endl;
}


Measured memory_bytes: 3184
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define MAXN 1000005
#define PLI pair<long long,int>
#define fi first
#define se second
#define mp make_pair
#define ha 99994711
#define ba 823
#define MOD 1000000007
//#define ivorysi
using namespace std;
typedef long long int64;
int64 fac[MAXN],invfac[MAXN],ans;
int N;
int64 fpow(int64 x,int64 c) {
	int64 res = 1,t = x;
	while(c) {
		if(c & 1) res = res * t % MOD;
		t = t * t % MOD;
		c >>= 1;
	}
	return res;
}
int64 C(int n,int m) {
	if(n < m) return 0;
	return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
}
int64 W(int k) {
	int x = N - 2 - k;
	int y = k - x;
	if(x < 0 || y < 0) return 0;
	return fac[k] * invfac[y] % MOD * invfac[x] % MOD;
}
void Solve() {
	scanf("%d",&N);
	if(N == 2) {
		puts("1");
		return;
	}
	fac[0] = invfac[0] = 1;
	for(int i = 1 ; i <= N ; ++i) {
		fac[i] = fac[i - 1] * i % MOD;
	}
	invfac[N] = fpow(fac[N],MOD - 2);
	for(int i = N - 1 ; i >= 1 ; --i) {
		invfac[i] = invfac[i + 1] * (i + 1) % MOD;
	}
	ans += fac[N - 1];
	for(int i = 1 ; i < N - 1 ; ++i) {
		ans += (C(N - 2,i) + C(N - 2,i - 1) + MOD - W(i - 1))* fac[i] % MOD * fac[N - 1 - i] % MOD;
		ans %= MOD;
	}
	printf("%lld\n",ans);
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
	return 0;
}

Measured memory_bytes: 15872
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

template <class T>
class cumulativeSum
{
private:
    int n;
    vector<T> sum;
public:
    cumulativeSum(const vector<T>& a)
    {
        n = a.size();
        sum.assign(n+1, 0);
        for(int i=0; i<n; ++i)
            sum[i+1] = a[i] + sum[i];
    }
    T getSum(int x1, int x2)
    {
        x1 = max(x1, 0);
        x2 = min(x2, n-1);
        if(x1 > x2)
            return 0;
        return sum[x2+1] - sum[x1];
    }
};

int main()
{
    vector<vector<int> > v(2);
    for(int i=0; i<2; ++i){
        string s;
        cin >> s;
        v[i].resize(s.size()+1);
        for(unsigned j=0; j<s.size(); ++j){
            if(s[j] == 'A')
                ++ v[i][j+1];
        }
    }
    vector<cumulativeSum<int> > cs = {v[0], v[1]};

    int q;
    cin >> q;
    while(--q >= 0){
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        int x = cs[0].getSum(a, b);
        int y = cs[1].getSum(c, d);
        x = x + ((b - a + 1) - x) * 2;
        y = y + ((d - c + 1) - y) * 2; 
        if(x % 3 == y % 3)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 2744
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    cin>>a;
    b=a;
    reverse(a.begin(),a.end());
    for(int i=0;i<a.size();++i)
    {
        if(a[i]=='b')
            a[i]='d';
        else if(a[i]=='d')
            a[i]='b';
        else if(a[i]=='p')
            a[i]='q';
        else if(a[i]=='q')
            a[i]='p';
    }
    if(a==b)
        cout<<"Yes";
    else
        cout<<"No";
}

Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
const long long MOD = (long long)1e9 + 7;

int len, ans, t1, t2;
string s;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> s;
    len = s.length();
    for (int i = 0; i < len; i++) {
        if (i%2) {
            if (s[i] == '0') t1++;
        }
        else {
            if (s[i] == '1') t1++;
        }
        if (i%2) {
            if (s[i] == '1') t2++;
        }
        else {
            if (s[i] == '0') t2++;
        }
    }
    ans = min(t1, t2);
    cout << ans << "\n";
    //system("pause");
    return 0;
}

Measured memory_bytes: 512
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using namespace std;
//LLONG_MAX = 90^18
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No"); }
void Yes() { cout << "Yes"; }
void No() { cout << "No"; }
//max_element


char T[300000];
signed main()
{
	cin >> T;
	int len = strlen(T);
	for (int i = 0; i < len; i++)
	{
		if (T[i] == '?') T[i] = 'D';
	}
	cout << T << endl;
}




Measured memory_bytes: 3812
class Arrow
  attr_reader :source, :sink, :label

  def initialize(source, sink, label)
    @source = source
    @sink = sink
    @label = label
  end
end

def push(queue, key, value)
  index = queue.index{|target, _| target >= key}
  return queue[index][1] if index && queue[index][0] == key
  return nil if index && index > 0 && !key.start_with?(queue[index - 1][0])
  queue.slice!(index..-1) if index && !queue[index][0].start_with?(key)
  queue.insert(index || queue.size, [key, value])
  value
end

def collect(n, arrows, goal)
  come_from = Array.new(n){[]}
  arrows.each do |arrow|
    come_from[arrow.sink] << arrow.source
  end

  reachable_from = {}
  stack = [goal]
  until stack.empty?
    node = stack.pop
    reachable_from[node] = true
    come_from[node].each do |source|
      stack << source unless reachable_from[source]
    end
  end
  reachable_from
end

def work(n, arrows, start, goal)
  reachable_from = collect(n, arrows, goal)
  return nil unless reachable_from[start]
  arrows.select!{|arrow| reachable_from[arrow.sink]}

  go = Array.new(n){[]}
  arrows.each do |arrow|
    go[arrow.source] << arrow
  end

  max = n * arrows.map{|arrow| arrow.label.size}.max

  queue = [['', {start => true}]]
  until queue.empty?
    spell, map = queue.shift
    return spell if map[goal]

    return nil if spell.size > max

    map.each do |node, unused|
      go[node].each do |arrow|
        t = push(queue, spell + arrow.label, {})
        t[arrow.sink] = true if t
      end
    end
  end
  nil
end

loop do
  n, a, s, g = gets.split.map(&:to_i)
  break if n == 0

  arrows = (0...a).map do |i|
    x, y, lab = gets.split
    Arrow.new(x.to_i, y.to_i, lab)
  end

  puts work(n, arrows, s, g) || 'NO'
end

Measured memory_bytes: 9824
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
int main(){
   int N,M,p,flg=true;
   std::cin >> N >> M >> p;
   std::vector<int> d;
   for(int i = 0; i < M; ++i){
     int a;
     std::cin>>a;
     a -= p;
     if(a < 0)a += N;
     if(a == 0)flg=false;
     d.push_back(a);
   }
   if(flg)d.push_back(0);
   M = d.size();
   std::sort(d.begin(), d.end());
   
   int ans = 1e9;
   for(int i = 0; i < M; ++i){
     //i+1 ??¨ i+2??????????????????????????????0???????§???????,??¨????????????
     int bet = abs(d[0] - d[(i + 1) %M]);
     int bet2 = N - abs((d[0] - d[(i + 2) % M]));
     if(bet2==N)bet2=0;
     
     if(bet > bet2)std::swap(bet, bet2);
     ans = std::min(ans, bet * 2 + bet2);
   }
   std::cout << ans * 100 << std::endl;
   return 0;
}

Measured memory_bytes: 1324
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=100000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u];i;i=sq[i].nxt)
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

namespace My_Math{
	#define N 100000

	int fac[N+100],invfac[N+100];

	int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
	int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
	int mul(int x,int y) {return 1ll*x*y%maxd;}
	ll qpow(ll x,int y)
	{
		ll ans=1;
		while (y)
		{
			if (y&1) ans=mul(ans,x);
			x=mul(x,x);y>>=1;
		}
		return ans;
	}
	int inv(int x) {return qpow(x,maxd-2);}

	int C(int n,int m)
	{
		if ((n<m) || (n<0) || (m<0)) return 0;
		return mul(mul(fac[n],invfac[m]),invfac[n-m]);
	}

	int math_init()
	{
		fac[0]=invfac[0]=1;
		rep(i,1,N) fac[i]=mul(fac[i-1],i);
		invfac[N]=inv(fac[N]);
		per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
	}
	#undef N
}
using namespace My_Math;

char s[100100];
int n;

int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	if (n&1) {puts("No");return 0;}
	rep(i,1,n)
	{
		if (((i&1) && (s[i]=='h')) || ((!(i&1)) && (s[i]=='i'))) continue;
		puts("No");return 0;
	}
	puts("Yes");
	return 0;
}



Measured memory_bytes: 256