akhauriyash/Code-Regression huggingface dataset:
#include <utility>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <iostream>
using namespace std;
typedef long long ll;
const long long mod = 1e9 + 7;
int main() {
    int n;
    cin >> n;
    ll a[n + 1];
    ll x[n + 1];
    ll y[n + 1];
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        x[i] = 0;
        y[i] = 0;
    }
    for (int i = 1; i <= n; i++){
        if (a[i] + i < n) {
            x[a[i] + i]++;
        }
        if(i - a[i] > 0) {
            y[i - a[i]]++;
        }
    }
    ll ret = 0;
    for (int i = 1; i <= n; i++){
        ret += x[i]*y[i];
    }
    cout << ret;
    return 0;
}

Measured memory_bytes: 8324
#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;

ll a,b;

ll pre(ll k){
	if(k % 4 == 1)
	    return 1;
	if(k % 4 == 2)
	    return k + 1;
	if(k % 4 == 3)
	    return 0;
	if(k % 4 == 0)
	    return k;
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%lld%lld",&a,&b);
	printf("%lld\n",pre(b) ^ pre(a - 1));
	return 0;
}


Measured memory_bytes: 256
N=int(input())
lst=list(map(int,input().split()))

swap=0

flag = 1
while flag:
    flag = 0
    for i in reversed(list(range(1,len(lst)))):
        if lst[i-1]>lst[i]:
            lst[i-1],lst[i] = lst[i],lst[i-1]
            flag = 1
            swap+=1

print(' '.join(map(str,lst)))
print(swap)


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

#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<long long,long long>
#define FOR(i,a,b)  for(long long i=a;i<b;++i)
#define RFOR(i,a,b) for(long long i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        400005
#define all(v)      v.begin(),v.end()
#define sz(x)       (long long)x.size()
//#define mod         1000000007
#define pqueue      priority_queue<long long>
#define pdqueue     priority_queue< long long,vector<long long> ,greater< long long >>
 
typedef long long ll;
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//const long long md = 998244353;
 
/*const long long mod = 998244353;
long long power(long long a,long long n)
{
	if(n == 1)return a%mod;
	if(n == 0)return 1;
	if(n&1)return ((a%mod)*(power((a*a)%mod,n/2))%mod)%mod;
	return power((a*a)%mod,n/2)%mod;
}
*/

int gcd(int x, int y)
{
	if (y > x) 
		swap(x, y);

	if (y == 0) return x;
	int a = x % y;
	if (a == 0) return y;
	return gcd(a, y);
}

int gcd(int ans, queue<int>& x)
{
	// cerr << ans << " " << x.front() << " ";
	ans = gcd(ans, x.front());
	// cerr << ans << endl;
	x.pop();
	if (x.empty()) return ans;
	return gcd(ans, x);
}

int main()
{
	int n;
	cin >> n;
	queue<int> m;

    int a;
	cin >> a;
	FOR (i,1,n) {
		int x;
		cin >> x;
		m.push(x);
	}

	cout << gcd(a, m) << endl;
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 105
#define MAX_K 10005

using namespace std;

int n,m,K;
int a[MAX_K];
int w[MAX_N][MAX_N];

int main()
{
	scanf("%d%d%d",&n,&m,&K);
	for(int i=1;i<=K;i++) scanf("%d",&a[i]);
	int col=1,cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=(i&1)?1:m;(i&1)?j<=m:j>=1;j+=(i&1)?1:-1)
		{
			if(a[col]==cnt) col++,cnt=0;
			w[i][j]=col,cnt++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			printf("%d ",w[i][j]);
		}
		printf("\n");
	}
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

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

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    cin>>a>>b;
    if(a<=b) cout<<a<<endl;
    else cout<<a-1<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int N, i, j, tmp=0, last=0, a[200000], flag=0;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &a[i]);
		if (a[i] == 1 && flag == 0) {
			flag = 1;
		}
	}
	if (flag == 0) {
		printf("-1");
		return 0;
	}

	for (i = 1; i <= N; i++) {
		for (j = tmp; j < N; j++) {
			if (a[j] == i) {
				tmp = j;
				last = i;
				break;
			}
		}
		if (last != i) {
			printf("%d", N - last);
			return 0;
		}
	}

	printf("0");
	return 0;
}

Measured memory_bytes: 896
import Data.Graph.Inductive

main :: IO ()
main = do
  n <- readLn
  hs <- map read . words <$> getLine
  print $ solve n hs

solve :: Int -> [Int] -> Int
solve n hs = spLength 1 n gr
  where
    gr = mkGraph ns es :: Gr () Int
    ns = [ (i, ()) | i <- [1..n] ]
    es = [ (i, i+k, abs (h0-h1)) | k <- [1,2], (i,h0,h1) <- zip3 [1..] hs (drop k hs) ]

Measured memory_bytes: 196988
#include<bits/stdc++.h>
#define itr(i, n) for(int i=1;i<=n;++i)
using namespace std;
const int SIZE = 5e5+1;
vector<int> num_arr(SIZE), idx_arr(SIZE);
stack<int> s, t;
int memo[SIZE];
int n, k;
void NIT(){ //Num Index Transform　数とインデックスを入れ替える
    itr(i, n) //両方とも要素を１からｎにする
        idx_arr[num_arr[i]] = i;
}
void INT(){ //Index Num Transform
    itr(i, n)
    {
        num_arr[idx_arr[i]] = i;
    }
    
}
void divide_and_conquer_method(int left, int right){
    if (left >= right) return;
    int median = (left + right) / 2;
    divide_and_conquer_method(left, median);
    divide_and_conquer_method(median+1, right);
    int Min = idx_arr[median];
    s.push(Min);
    t.push(idx_arr[median]);
    for (int i = median-1; i >= left; --i){
        Min = min(Min, idx_arr[i]);
        s.push(Min);
        t.push(idx_arr[i]);
    }
    int j = left;
    for (int i = median+1; i <= right; i++)
    {
        while (!(s.empty()) && s.top() - idx_arr[i] < k)
        {
            memo[j] = t.top();
            ++j;
            s.pop();
            t.pop();
        }
        memo[j] = idx_arr[i];
        j++;
    }
    while (!t.empty())
    {
        memo[j] = t.top();
        ++j;
        t.pop();
        s.pop();
    }
    
    for (int i = left; i <= right; i++){
        idx_arr[i] = memo[i];
    }
}
int main(){
    cin >> n >> k;
    itr(i, n)
        cin >> num_arr[i];
    NIT();
    divide_and_conquer_method(1, n);
    INT();
    itr(i, n){
        cout << num_arr[i] << endl;
    }
}

Measured memory_bytes: 11432
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <queue>

typedef long long ll;
const ll LL_MAX (1LL<<60);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

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

    ll a, b;
    cin >> a >> b;

    ll ans (0);
    if (a > b) ans+=a, a--;
    else ans+=b, b--;
    if (a > b) ans+=a, a--;
    else ans+=b, b--;

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


Measured memory_bytes: 256
#!/usr/bin/env python3
N, Y = map(int, input().split())

def solve():
    for x in range(3 * 10**3):
        for y in range(5 * 10**3):
            if x + y <= N and 9 * x + 4 * y == Y // 1000 - N:
                print(x, y, N - x - y)
                return
    print(-1, -1, -1)
    return

solve()


Measured memory_bytes: 2940
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int N,W;
    cin >> N >> W;
    vector<ll>w(N),v(N);
    REP(i,N)cin >> w[i] >> v[i];
    ll dp[N+1][W+10];
    REP(i,N+1)REP(j,W+10)dp[i][j]=0;
    FOR(i,0,N){
        FOR(j,1,W+3){
            if(j>=w[i])dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j]);
            else dp[i+1][j]=dp[i][j];
        }
    }

    cout << dp[N][W] << endl;
    return 0;
}

Measured memory_bytes: 82344
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int a,b;
int main()
{
    cin>>a>>b;
    if(a*b==15)
    {
        cout<<"*"<<endl;
        return 0;
    }
    if(a+b==15)
    {
        cout<<"+"<<endl;
        return 0;
    }
    cout<<"x"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <cstdlib>  // abs() for integer
#include <cmath>
#include <bitset>

using namespace std;


int main(void) {
    int N;
    cin >> N;
    //cout<<N<<endl;
    double tmp=0;
    int index = 0;
    for (int i=0;i<7;i++){
        index = i;
        //cout <<pow(10,i)<<endl;
        if (N<pow(10,i)) break;
        if (i%2==1){
            tmp = tmp + 9*pow(10,i-1);
        }}
    //cout<<index<<endl;
        if (index%2 ==0) cout<<int(tmp);
        double n;
        if (index%2 ==1){
            n = double(N)-pow(10,index-1)+1;
            tmp = tmp+n;
            cout << int(tmp);
        }
    
    
}

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


using ll = long long;
const int Mod = 1e9+7;
const int MaxN = 2e5+10;
int N;
ll fac[MaxN], facinv[MaxN];
vector<int> adj[MaxN];
int sz[MaxN];
ll dp[MaxN], num[MaxN];


void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}


ll invmod(ll a, ll m)
{
    ll x, y;
    exgcd(a, m, x, y);
    return (x % m + m) % m;
}


void init()
{
    fac[0] = 1;
    for (int i = 1; i < MaxN; i++)
        fac[i] = fac[i - 1] * i % Mod;
    facinv[MaxN - 1] = invmod(fac[MaxN - 1], Mod);
    for (int i = MaxN - 2; i >= 0; i--)
        facinv[i] = facinv[i + 1] * (i + 1) % Mod;
}


void dfs_dp(int u, int fa)
{
    int sz_u = 0;
    ll dp_u = 1;
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs_dp(v, u);
        sz_u += sz[v];
        dp_u = dp_u * dp[v] % Mod * facinv[sz[v]] % Mod;
    }
    sz[u] = sz_u + 1;
    dp[u] = dp_u * fac[sz_u] % Mod;
}


void dfs_num(int u, int fa)
{
    num[u] = (u == 1) ? dp[u] : (num[fa] * sz[u] % Mod * invmod(N - sz[u], Mod) % Mod);
    for (int v : adj[u]) {
        if (v != fa) dfs_num(v, u);
    }
}


void solve()
{
    dfs_dp(1, 0);
    dfs_num(1, 0);
    for (int i = 1; i <= N; i++) cout << num[i] << endl;
}


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

    cin >> N;
    int a, b;
    for (int i = 1; i <= N - 1; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    init();
    solve();
    return 0;
}


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

int main() {
  ios_base::sync_with_stdio(false);
  long long n;
  cin >> n;
  map<ll, ll> mapo;
  for (int i = 0; i < n; i++) {
    int stick;
    cin >> stick;
    if (!mapo.count(stick)) mapo[stick] = 0;
    mapo[stick]++;
  }
  ll area = 0;
  auto it = mapo.rbegin();
  bool first = false;
  bool done = false;
  while (it != mapo.rend()) {
    //cout << it->first << " " << it->second << endl;
    //cout << area << endl;
    if (it->second >= 4) {
      if (first) {
        area *= it->first;
      } else {
        area = it->first * it->first;
      }
      done = true;
      break;
    } else if (it->second >= 2) {
      if (first) {
        area *= it->first;
        done = true;
        break;
      } else {
        area = it->first;
        first = true;
      }
    }
    it++;
  }
  if (done) {
    cout << area << endl;
  } else {
    cout << 0<< endl;
  }

  return 0;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair

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

    ll n;
    cin>>n;

    vector<ll>a(n+1);
    vector<ll>b(n+1);
    vector<ll>c(n+1);

    for(ll i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
    }

    vector<vector<ll> >dp(3,vector<ll>(n+1));

    dp[0][1]=a[1];
    dp[1][1]=b[1];
    dp[2][1]=c[1];

    for(ll i=2;i<=n;i++)
    {
        dp[1][i]=b[i]+max(dp[0][i-1],dp[2][i-1]);
        dp[0][i]=a[i]+max(dp[1][i-1],dp[2][i-1]);
        dp[2][i]=c[i]+max(dp[0][i-1],dp[1][i-1]);
    }

    cout<<max({dp[0][n],dp[1][n],dp[2][n]});

    return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <stack>
#include <queue>
#include <set>

#define mod 1000000007
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if(s == "ABC") cout << "ARC";
    else cout << "ABC";
    return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-9;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int main(){
	cout << fixed << setprecision(4);
	ld t, x; cin >> t >> x;
	cout << t * t / (t*x) << endl;
	//stop
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double ans = 0.0;
        for (int i=0; i<n; i++) {
            double x = in.nextDouble();
            String u = in.next();

            if (u.equals("JPY")) {
                ans += x;
            } else {
                ans += x * 380000;
            }
        }

        System.out.println(ans);

        in.close();
    }
}

Measured memory_bytes: 22868
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};




int main(){
    LL n;cin >> n;
    if(n%2){
        cout << 0 << endl;
        return 0;
    }
    else{
        LL ans = 0;
        LL t = 2;
        while(true){
            t *= 5;
            if(n < t) break;
            ans += n / t;
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
N, A, B = map(int, input().split())
cnt = 0
for i in range(1, N + 1):
    j = list(str(i))
    sum_j = 0
    for k in j:
        sum_j += int(k)
    if A <= sum_j and sum_j <= B:
        cnt += i

print(cnt)


Measured memory_bytes: 2940
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,k=MI()
if k>((n-1)*(n-2))//2:
    print(-1)
else:
    s=(n*(n-1))//2
    print(s-k)
    count=0
    for i in range(1,n):
        for j in range(i+1,n+1):
            print(i,j)
            count+=1
            if count==s-k:
                sys.exit()

Measured memory_bytes: 42864
//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define fi first
#define SZ(x) (int((x).size()))
#define se second
#define ll long long
#define pq priority_queue
#define MP make_pair
#define pii pair<int,int>
#define mod 998244353
#define inf 0x3f3f3f3f
#define debug(x) cerr<<#x<<"="<<x<<'\n'
#define rep(i, a, b) for (int i=a; i<(b); i++)
 
const int maxn=1e6+10;
 
int n;
pii a[maxn];
 
bool cmp(pii x,pii y) {
	return (x.se>y.se&&x.fi>0)||(y.se-y.fi>x.se-x.fi&&y.fi<0);
}
 
int main(){
    std::ios::sync_with_stdio(false);
    cin>>n;
    rep(i,0,n) {
    	string s;
    	cin>>s;
    	int mn=mod,val=0; 
    	rep(j,0,SZ(s)) {
    		if (s[j]=='(') val++;
    		else val--;
    		mn=min(val,mn);
		}
		a[i]=MP(val,mn);
	}
	sort(a,a+n,cmp);
	int sum=0;
	rep(i,0,n) {
		if (sum+a[i].se<0) {
			cout<<"No";
			return 0;
		}
		sum+=a[i].fi; 
	}
	if (sum==0) cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 11436
package main

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

func scanInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func scanInt64() int64 {
	sc.Scan()
	i, _ := strconv.ParseInt(sc.Text(), 10, 64)
	return i
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func scanInts64(n int) []int64 {
	res := make([]int64, n)
	for i := range res {
		res[i] = scanInt64()
	}
	return res
}

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	k := scanInt()
	a, b := scanInt(), scanInt()

	for i := 1; i*k <= b; i++ {
		if a <= i*k && i*k <= b {
			fmt.Println("OK")
			return
		}
	}

	fmt.Println("NG")
}


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

using namespace std;

int main(){
	int N,ans=0; cin>>N;
  vector<int> V(N); for(int i=0;i<N;i++) cin>>V[i];
  vector<int> C(N); for(int i=0;i<N;i++) cin>>C[i];
  for(int i=0;i<N;i++) if(V[i]-C[i]>0) ans+=V[i]-C[i];
  cout<<ans<<endl;
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;

int n;
double x[maxn], y[maxn];

double dist(int i, int j) {
  return sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
}

double fac(int i) {
  if (i==1) return i;
  return i * fac(i-1);
}

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

  assert(fac(3) == 6.0);

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

  vector<int> v;
  for (int i=0; i<n; i++) {
    v.push_back(i);
  }

  double tot = 0;

  do {
    for (int i=0; i+1<n; i++) {
      tot += dist(v[i],v[i+1]);
    }
  } while (std::next_permutation(v.begin(), v.end()));

  tot = tot / fac(n);

  cout<<fixed<<setprecision(12)<<tot<<endl;
  
  

  return 0;
}


Measured memory_bytes: 2304
package main

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

var sc *bufio.Scanner

func init() {
	// 100MB
	bufsize := 100 * 1024 * 1024
	sc = bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, bufio.MaxScanTokenSize), bufsize)
	sc.Split(bufio.ScanWords)
}
func readInt() int              { return readIntArray(1)[0] }
func readInt2() (int, int)      { a := readIntArray(2); return a[0], a[1] }
func readInt3() (int, int, int) { a := readIntArray(3); return a[0], a[1], a[2] }
func readIntArray(n int) []int {
	s := readStringArray(n)
	a := make([]int, n)
	for i := range a {
		a[i], _ = strconv.Atoi(s[i])
	}
	return a
}
func readString() string            { return readStringArray(1)[0] }
func readString2() (string, string) { a := readStringArray(2); return a[0], a[1] }
func readStringArray(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		a[i] = sc.Text()
	}
	return a
}
func max(ns ...int) int {
	max := ns[0]
	for _, n := range ns {
		if n > max {
			max = n
		}
	}
	return max
}
func min(ns ...int) int {
	min := ns[0]
	for _, n := range ns {
		if n < min {
			min = n
		}
	}
	return min
}
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	n, w := readInt2()
	wvs := make([][]int, n)
	for i := range wvs {
		tmpw, tmpv := readInt2()
		wvs[i] = []int{tmpw, tmpv}
	}

	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, w+1)
	}

	for i := 0; i < n; i++ {
		for weight := 0; weight <= w; weight++ {
			iw, iv := wvs[i][0], wvs[i][1]
			var sel int
			// 選ぶ場合の価値を計算する
			if iw <= weight {
				if i == 0 {
					sel = iv
				} else {
					// i 番目が入ってくる前で、i の重さを除いた時の一番価値が高い状態に足し合せる
					sel = dp[i-1][weight-iw] + iv
				}
			}
			// 選ばない場合は一個前の価値を引き継ぐ
			var nosel int
			if i == 0 {
				nosel = 0
			} else {
				nosel = dp[i-1][weight]
			}

			//fmt.Printf("i: %d, w: %d, sel: %d, nosel: %d\n", i, weight, sel, nosel)
			dp[i][weight] = max(sel, nosel)
		}
	}

	fmt.Println(dp[n-1][w])
}


Measured memory_bytes: 82560
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <map>

using namespace std;



int main(){
	string s[10];
	while(cin>>s[0]){
		s[0]+="0";
		for(int i=1; i<10; i++){
			for(int j=0; j<10; j++){
				s[i][j]=(s[i-1][j]-'0')%10+(s[i-1][j+1]-'0')%10;
				s[i][j]%=10;
				s[i][j]+='0';
			}
		}
		cout<<s[9][0]<<endl;
	}
}

Measured memory_bytes: 1176
N = int(input())
A = list(map(int,input().split()))

def show_step(A):
    ans = str(A[0])
    for a in A[1:]:
        ans += " "+str(a)
    print(ans)

show_step(A)
for i in range(1,N):
    v = A[i]
    j = i-1
    while j >= 0  and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    show_step(A)



Measured memory_bytes: 5600
#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    (;;$n:expr) => {
        {
            (0..$n).map(|_| scan!()).collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let (h, _) = scan!(usize, usize);
    let map = scan!(String;h);
    for line in map {
        println!("{}", line);
        println!("{}", line);
    }
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a[3]; rep(i, 3) cin >> a[i];
    int c = 0;
    int sum = 0;
    int ta[3] = {0}; rep(i, 3) if (a[i] % 2 != 0) {ta[i] = 1; c++;}
    //cout << c << endl;
    if (c == 1) {
        rep(i, 3) {
            if (ta[i] == 0) {
                a[i]++;
            }
        }
        sum++;
    } else if (c == 2) {
        rep(i, 3) {
            if (ta[i] == 1) {
                a[i]++;
            }
        }
        sum++;
    }
    //rep(i, 3) cout << a[i] << " "; cout << endl;
    sort(a, a + 3);
    cout << sum + (a[2] - a[0]) / 2 + (a[2] - a[1]) / 2 << endl;
}


Measured memory_bytes: 256
N = int(input())
xy = [map(int,input().split()) for i in range(N)]
x, y =[list(i)  for i in  zip(*xy)]

for i in range(N-2):
    if x[i] == y[i] and x[i+1] == y[i+1] and x[i+2] == y[i+2]:
        print('Yes')
        break

    elif i == N-3:
        print('No')

    else:
        continue

Measured memory_bytes: 9188
N, M = map(int, input().split())

adj = [ [] for i in range(N+1)]
distance = [-1 for i in range(N+1)]
visited = [1] + [0 for i in range(N)]
ans = True

def dfs(node):
	stack = [node]
	visited[node] = 1
	if(distance[node] == -1):
		distance[node] = 0
	while(len(stack)):
		v = stack.pop()
		p = distance[v]
		for n, d in adj[v]:
			if(visited[n] == 0):
				distance[n] = p + d
				visited[n] = 1
				stack.append(n)
			else:
				if(distance[n] != p + d):
					return False
	return True


for i in range(M):
	l, r, d = map(int, input().split())
	adj[l].append((r, d))
	adj[r].append((l, -d))

for v in range(1, N+1):
	if(visited[v] == 1):
		continue
	if(not dfs(v)):
		ans = False
		break


print("Yes" if(ans) else "No")

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

int main() {
    int A, B;
    cin >> A >> B;

    if (B == 1) cout << 0 << endl;
    else {
        if (A >= B) cout << 1 << endl;
        else {
            B -= A;
            cout << 1 + (B + A - 2) / (A - 1) << endl;
        }
    }
}

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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)


typedef long long ll;
typedef unsigned long long int llt;

const int N = 5e5 + 10;

vector<int> g[N];
bool viss[N];
int vis[N];

void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0)
      dfs2(x, curr, num);
}

ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

llt factdp[N];
llt fact(llt x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != -1) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}

string ans ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ans += to_string(x);
     return;
}

llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}
ll dp[51][2505][51];
vector<int> v;
int n, a;

ll findans(int ind, int sum, int co)
{
  if(ind < 0) return 0;
  if(ind == 0
  )
  {
    if(co == 0) return 0;
    if(sum%co != 0) return 0;
    int avg = sum /co;
    if(avg == a) return 1;
  }
  if(dp[ind][sum][co] != -1) return dp[ind][sum][co];
  ll x = findans(ind-1, sum, co);
  ll y = findans(ind-1, sum+v[ind], co+1);
  dp[ind][sum][co] = x + y;
  return dp[ind][sum][co];
}

int main()
{
  int x;
  cin>>n>>a;
  memset(dp, -1, sizeof(dp));
  v.pb(0);
  rep(i, 0, n){
    cin>>x;
    v.pb(x);
  }
  cout<<findans(n, 0, 0)<<endl;
}


Measured memory_bytes: 65152
#include <bits/stdc++.h>
using namespace std;
int n,k,l = 0;
long long ans;
int main(){
	//freopen("readin.txt","r",stdin);
	cin >> n >> k;
	for(int i = 1;i <= n;i++){
		ans+=n/i*max(0,i - k);
		ans+=max(0,n%i - k + 1);
	}
	cout << ans - (k ? 0 : n) << endl;
}  

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

using namespace std;

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

typedef long long int ll;

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

	int n;
	cin >> n;
	bool is[1001] = {false};
	
	is[1] = 1;
	for(int i=2 ; i<=1000 ; i++)
	{
	    for(int j=2 ; pow(i,j)<=1000 ; j++)
	        is[(int)pow(i,j)] = 1;
	}

	for(int i=n ; i>=1 ; i--)
	{
		if(is[i])
		 {
		     cout << i;
		     break;
		 }
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

double dist(VEC<int> a, VEC<int> b) {
  LL sum = 0;
  REP(i, 0, a.size()) { sum += abs(a[i] - b[i])*abs(a[i]-b[i]); }
  return sum;
}
bool isPow(double a){
  static VEC<int> v(1e6+1,-1);
  if(v[a]!=-1)return v[a];
  int p = 0;
  REP(i,1,sqrt(a)+1){
    p=i*i;
    if(p==a){v[a]=1;return 1;}

  }
  v[a]=0;
  return 0;
}
int main() {
  int N, D;
  cin >> N >> D;
  VEC<int> X[N];
  REP(i, 0, N) {
    X[i] = VEC<int>(D, 0);
    REP(j, 0, D) cin >> X[i][j];
  }
  double eps = 1e-9;
  int cnt = 0;
  REP(i, 0, N) {
    REP(j, i + 1, N) {
      double d = dist(X[i], X[j]);
      // if (abs(ld - d) <= eps) {
        if(isPow(d)){
        cnt++;
      }
    }
  }
  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i,n) for (int i = 0; i< (n); i++)
#define Rep(i,n,m) for (int i = (n); i< (m); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
using namespace std;



int main() {
    ll n, sum = 0;
    
    cin>>n;
    
    rep(i, n+1){
        if(i%3==0 || i%5==0) sum+=0;
        else sum+= i;
    }
    
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n,0);

  rep(i,n) {
    cin >> a[i];
  }

  sorti(a);
  vector<ll> b(n,0);

  ll tmp = -1;
  pair<ll,ll> ans;

  ll tar = a.back();
  ll half = tar / 2;
  for (int i = n-2; i >= 0; --i) {
    ll t = tar - a[i];
    if (t > half) {
      t = tar - t;
    }
    if (t > tmp) {
      tmp = t;
      ans = make_pair(tar, a[i]);
    }
  }

  cout << ans.first << " " << ans.second << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL);

int main() {
  FAST;
  string S, T;
  cin >> S >> T;
  string ans = "Yes";
  for (int i = 0; i < S.size(); i++) {
    if (S.at(i) != T.at(i)) {
      ans = "No";
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3644
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);

void chmin(int &a, int b) {
	a = min(a, b);
}
void chmax(int &a, int b) {
	a = max(a, b);
}
ll mod_pow(ll a, ll n, ll m = mod) {
	a %= m;
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void solve() {
	int n, m; cin >> n >> m;
	int k; cin >> k;
	modint ans = 0;
	rep(x, k + 1) {
		modint csum = m;
		csum *= (modint)(m - 1) ^ (n - 1 - x);
		csum *= comb(n - 1, x);
		ans += csum;
	}
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	init_f();
	//init();
	solve();
	stop
		return 0;
}


Measured memory_bytes: 7752
#include <bits/stdc++.h>
    #define rep(i,n) for(int i = 0; i < (n); i++)
     
    using namespace std;
    
    int main() {
   
    int n;
    scanf("%d",&n);
    int ans = 0;
    int second = 0;
    for(int i = 0; i <= n; i++){
    	if(i == 0 || i == 1){	ans = 1;
    	} else{
    		if(i == 2){
    			second = 1;
    		    ans = 1;
    		}
    		int t = second;
    		second = ans;
    		ans = ans + t;
    	}
    }
    	printf("%d\n",ans);
    
     return 0;
    }
    


Measured memory_bytes: 3212
import sys
from heapq import heappop, heappush
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M, S, T = list(map(int, input().split()))
graph = [[] for _ in range(N+1)] #0使わず
for _ in range(M):
    u, v, a, b = list(map(int, input().split()))
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(start, mode):
    # 各地点への最小コストを返す
    INF = 10 ** 15
    dist = [INF] * (N+1) #0使わず
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, src = heappop(que)
        if dist[src] < d:
            continue
        for next_city, *cost in graph[src]:
            d1 = d + cost[mode]
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

d_en = np.array(dijkstra(S, 0))
d_snuke = np.array(dijkstra(T, 1))
d_cost = d_en + d_snuke
answer = 10 ** 15 - np.minimum.accumulate(d_cost[::-1])[::-1][1:]
print('\n'.join(answer.astype(str)))
# 21

Measured memory_bytes: 82992
#include <bits/stdc++.h>
 
using namespace std;
 
#define f0r(a, b) for (long long a = 0; a < (b); a++)
#define f1r(a, b, c) for (long long a = (b); a < (c); a++)
#define f0rd(a, b) for (long long a = (b); a >= 0; a--)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define mp make_pair
#define f first
#define s second
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
 
void fio() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 

 
const long double pi = 3.14159265358979323846;
const ll mod = 1000000007;

namespace modop {
	ll madd(ll a, ll b) {
	  return (a + b) % mod;
	}
	ll msub(ll a, ll b) {
	  return (((a - b) % mod) + mod) % mod;
	}
	ll mmul(ll a, ll b) {
	  return ((a % mod) * (b % mod)) % mod;
	}
	ll mpow(ll base, ll exp) {
	  ll res = 1;
	  while (exp) {
		if (exp % 2 == 1){
			res = (res * base) % mod;
		}
		exp >>= 1;
		base = (base * base) % mod;
	  }
	  return res;
	}
	ll minv(ll base) {
	  return mpow(base, mod - 2);
	}
	ll mdiv(ll a, ll b) {
	  return mmul(a, minv(b));
	}
}

using namespace modop;



pll reduce(ll x, ll y) {
  if (x == 0) return mp(0, 1);
  if (y == 0) return mp(1, 0);
  if (x < 0 && y < 0) {
    x = -x; y = -y;
  }
  if (x < 0) {
    x = -x; y = -y;
  }
  ll g = __gcd(abs(x), abs(y));
  return mp(x / g, y / g);
}

pll comp(pll frac) {
  pll r = mp(frac.s, frac.f);
  if (r.f < 0) r.f = -r.f;
  else r.s = -r.s;
  return r;
}

void solve() {
  ll c00 = 0, r = 1;

  ll n; cin >> n;
  pll fracs[n];
  map<pll, ll> cnt;
  f0r(i, n) {
    ll x, y; cin >> x >> y;
    if (x == 0 && y == 0) {
      ++c00;
      continue;
    }
    fracs[i] = reduce(x, y);
    ++cnt[fracs[i]];
  }

  for (auto x: cnt) {
    if (x.s == 0) continue;
    // cout << x.f.f << " " << x.f.s << " " << x.s << endl;
    pll y = comp(x.f);
    ll v = mpow(2, x.s);
    if (cnt.find(y) != cnt.end()) {
      v = (v + mpow(2, cnt[y])) % mod;
      v = (v + mod - 1) % mod;
      cnt[y] = 0;
    }
    cnt[x.f] = 0;

    r = (r * v) % mod;
  }

  cout << (msub(r, 1) + c00) % mod << '\n';
}
 
int main() {
  fio();
  
  int T = 1;
  // cin >> T;
  while (T--) solve();
} 

Measured memory_bytes: 19200
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 1000000007
#define bitcnt(a) (ll) __builtin_popcount((a))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main() {
    ll n,all=0;
    vector<ll>v;
    cin>>n;
    REP(i,n){
        ll p;
        cin>>p;
        all+=p;
        v.pb(p);
    }

    ll oneCnt=(1+n)*n/2;
    if(all%oneCnt){
        cout<<"NO"<<endl;
        return 0;
    }
    ll times = all/oneCnt;
    REP(i,n){
        ll dif=v[(i+1)%n]-v[i];
        if(dif>times||(dif-times)%(n)){
            cout<<"NO"<<endl;
            return 0;
        }
    }  
    cout<<"YES"<<endl;

}


Measured memory_bytes: 1400
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>



using namespace std;
typedef long long ll;
int gcd( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}
int abs(int x){
  if(x>=0){
    return x;
  }else{
    return -x;
  }
}

int moji(char in)
{
    int ans = (int)in-(int)'a'+1;
    if((in < 1) || (in > 26)){
        ans = 100;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}









int main() {
  int N;
  cin>>N;
  int d[101];
  for(int i=0;i<101;i++){
    d[i]=0;
  }
  for(int i=0;i<N;i++){
    int x;
    cin>>x;
    d[x]++;
  }
  int sum=0;
  for(int i=0;i<101;i++){
    if(d[i]>0){
      sum++;
    }
  }
  cout<<sum<<endl;


  
  
  

  





  

  


  

    


  

  
  
  
  
}


  

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

int main(void)
{
    // 入力
    int n; cin >> n;


    int c0=0,c1=0,c2=0,c3=0;

    rep(i,n){
        string s;
        cin >> s;
        if (s == "AC") c0++;
        else if (s=="WA") c1++;
        else if (s=="TLE") c2++;
        else c3++;
    }

    cout << "AC " << "x " << c0 << endl;
    cout << "WA " << "x " << c1 << endl;
    cout << "TLE " << "x " << c2 << endl;
    cout << "RE " << "x " << c3 << endl;

    return 0;

}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin,(a).rend()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;
const int inf = 1001001001;
const int mod = 1000000007;

struct mint {
	ll x;
	mint(ll x = 0) :x(x% mod) {}
	mint& operator+=(const mint a) {
		(x += a.x) %= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		(x += mod - a.x) %= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res *= a;
	}
};

mint c[4005][4005];
void init() {
	c[0][0] = 1;
	for (int i = 0; i <= 4000; i++) {
		for (int j = 0; j <= i; j++) {
			c[i + 1][j] += c[i][j];
			c[i + 1][j + 1] += c[i][j];
		}
	}
}
mint comb(int n, int k) {
	return c[n][k];
}
mint f2(int n, int k) {
	return comb(n + k - 1, k - 1);
}
mint f(int n, int k) {
	if (n < k) return 0;
	if (n == 0 && k == 0) return 1;
	if (k < 1) return 0;
	return f2(n - k, k);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	init();
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= k; ++i) {
		mint ans = f(k, i);
		ans *= f2(n - k - (i - 1), i + 1);
		printf("%lld\n", ans.x);
	}
	return 0;
}

Measured memory_bytes: 125568
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<string> vstring;
typedef vector<pint> vpint;

struct Edge{int to,from,cost;};

#define debug cout

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) debug << *i << " "; debug << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

#define rep(i,n) for(int i=0;i<(n);++i)
#define repn(i,m,n) for(int i=(m);i<=(n);++i)
#define repd(i,n) for(int i=(n)-1;i>=0;--i)
#define repnd(i,m,n) for(int i=(n);i>=(m);--i)
#define rep0(i,n) for(i=0;i<(n);++i)
#define repn0(i,m,n) for(i=(m);i<=(n);++i)
#define repd0(i,n) for(i=(n)-1;i>=0;--i)
#define repnd0(i,m,n) for(i=(n);i>=(m);--i)
#define all(n) n.begin(),n.end()
#define sz(n) ((int)(n).size())
#define IL for(;;)
#define MP make_pair
#define PB push_back
#define SS stringstream
#define X second
#define Y first
#define PUTLINE debug<<"LINE:"<<__LINE__<<endl;

const int INF = 2147483647/3;
const double EPS = 1e-10;
const double PI = acos(-1.0);

const int dx[]={1,-1,0,0,1,-1,1,-1,0};
const int dy[]={0,0,1,-1,1,-1,-1,1,0};

vint prime;
int mem[1121][15][305];

int f(int n,int k,int m){
	if(mem[n][k][m]>=0)return mem[n][k][m];
	if(k==0){
		if(n==0){
			return 1;
		}else{
			return 0;
		}
	}
	Int res=0;
	for(int i=0;i<m&&prime[i]<=n;++i){
		res+=f(n-prime[i],k-1,i);
	}
	mem[n][k][m]=res;
	return res;
}

int main() {
	repn(i,2,2000){
		int j;
		repn0(j,2,i-1)if(i%j==0)break;
		if(i==j)prime.PB(i);
	}
	memset(mem,-1,sizeof(mem));
	int n,k;
	IL{
		cin>>n>>k;
		if(n==0&&k==0)break;
		int m;
		rep0(m,305)if(prime[m]>n)break;
		cout<<f(n,k,m)<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string.h>
using namespace std;

int N;
int a[210];

int main(){
  cin >> N;

  for(int i=0;i <N;i++)cin >> a[i];

  int res =0;

  while(true){
    bool odd= false;
  for(int i=0;i<N;i++){
    if(a[i]%2 != 0) odd = true;
  }

  if(odd)break;

  for(int i=0;i<N;i++){
    a[i] = a[i]/2;
  }
  res++;
  }
  cout << res <<endl;
}


Measured memory_bytes: 256