akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var s string
	fmt.Scan(&s)

	iFirst, _ := strconv.Atoi(s[0:2])
	iLast, _ := strconv.Atoi(s[2:4])

	if 1 <= iFirst && iFirst <= 12 {
		if 1 <= iLast && iLast <= 12 {
			fmt.Print("AMBIGUOUS")
			return
		} else {
			fmt.Print("MMYY")
			return
		}
	} else {
		if 1 <= iLast && iLast <= 12 {
			fmt.Print("YYMM")
			return
		} else {
			fmt.Print("NA")
			return
		}
	}
}


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

M = 0
temp = K
while temp>0:
    M += 1
    temp>>=1

nexts = [[-1]*N for _ in range(M)]
for i in range(N):
    nexts[0][i] = A[i]-1

for t in range(1,M):
    for i in range(N):
        nexts[t][i] = nexts[t-1][nexts[t-1][i]]

Kb = [0]*M
temp = K
for i in range(M):
    Kb[i] = temp&1
    temp >>= 1

ans = 0
for i in reversed(range(M)):
    if Kb[i]:
        ans = nexts[i][ans]
print(ans+1)






Measured memory_bytes: 174284
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] in = sc.nextLine().split(" ");
        Integer a = Integer.parseInt(in[0]);
        Integer b = Integer.parseInt(in[1]);
        Integer i;
        if(a<=b){
            i = a;
        }else {
            i = a-1;
        }
        System.out.println(i.toString());
    }
 
}

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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#define all(x) (x).begin(), (x).end()
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n, e) for (int i = (int)(n); i >= (int)(e); --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
#define RETURN(x) do{cout << (x) << '\n'; return 0;}while(0)

const int MOD = 998244353; //1e9+7;
const int MAXN = 1e6+1;

int main(int argc, char **argv) {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    vector<int> a(n), c(n+1);
    fori(i,n) {
        cin >> a[i];
        c[a[i]]++;
    }

    LL total = 0;
    fori(i,n+1) {
        total += 1LL*c[i]*(c[i]-1)/2;
    }

    fori(i,n) {
        cout << total-c[a[i]]+1 << '\n';
    }
    return 0;
}


Measured memory_bytes: 4224
// in the name of Allah

#include <bits/stdc++.h>

#define endl '\n'
#define ll long long
#define pb push_back
#define ld long double
#define sz(x) ((int) (x.size()))

#define max_n 123456
#define mod 1000000007
// #define mod 998244353
#define myPrime 97654321
#define inf 1e9
#define eps 1e-9

#define fr first
#define se second

using namespace std;

ll add(ll a, ll b) {
	a += b;
	if(a >= mod) return a - mod;
	return a;
}

ll mul(ll a, ll b) {
	a *= b;
	if(a >= mod) return a % mod;
	return a;
}

ll power(ll x, ll y) {
	if(y == 0) return 1;
	ll foo = power(x, y/2);
	foo = mul(foo, foo);
	if(y&1) return mul(x, foo);
	return foo;
}

int n;
ll x[123];
ll y[123];
ll h[123];

int main() {
	// ll start_time = clock();
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// cout << fixed << setprecision(12);
	int n, T, c, t;
	cin >> n >> T;
	int ans = 1e9;
	while(n--) {
		cin >> c >> t;
		if(t <= T) ans = min(ans, c);
	}
	if(ans > 1e6) cout << "TLE" << endl;
	else cout << ans << endl;
	return 0;
}

// sorted or not
// mutiset vs set
// clear when it's multi-testcase

Measured memory_bytes: 256
import Control.Applicative
import Data.Function
import Control.Monad

main :: IO ()
main = fix $ \loop -> do
    [h,w] <- map read . words <$> getLine
    unless (h == 0) $ do
        putStrLn $ replicate w '#'
        replicateM_ (h-2) $ putStrLn $ "#" ++ (replicate (w-2) '.') ++ "#"
        putStrLn $ replicate w '#'
        putStrLn ""
        loop



Measured memory_bytes: 4088
#include <iostream>

using namespace std;

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

	string S;
	cin >> S;

	for (int i = 0; i < (A + B + 1); i++) {
		if (i < A) {
			if ('0' <= S[i] && S[i] <= '9') {
			}
			else {
				cout << "No" << endl;
				return 0;
			}
		}
		else if (i == A) {
			if (S[i] != '-') {
				cout << "No" << endl;
				return 0;
			}
		}
		else if (i < A + B + 1) {
			if ('0' <= S[i] && S[i] <= '9') {
			}
			else {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int m=1000000;
  for(int i=1;i<s.size();i++){
    if(s[i]!=s[i-1]) m=min(m,max(i,(int)s.size()-i));
  }
  cout<<(m==1000000?(int)s.size():m);
}

Measured memory_bytes: 512
import numpy as np
n,d=map(int,input().split())
xlis=[list(map(int,input().split())) for i in range(n)]
def dis(x,y):
	dlis=[]
	for i in range(d):
		t=(xlis[x][i]-xlis[y][i])**2
		dlis.append(t)
	return (sum(dlis))**(1/2)
counter=0
for i in range(n):
	for j in range(n):
		if i<j and int(dis(i,j))==dis(i,j):
			counter+=1
print(counter)

Measured memory_bytes: 12496
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int comper(int a, int b) {
	if(a == b) return 1;
	return 0;
}

int main() {
	int a, b, c;
	while(cin >> a >> b >> c) {
		if(comper(a, b)) cout << c << endl;
		else if(comper(a, c)) cout << b << endl;
		else cout << a << endl;
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
s = [list(input()) for _ in range(n)]

min_len = float('inf')
short_s =[]
for i in range(n):
  if min_len>len(s[i]):
    min_len = len(s[i])
    for j in range(len(s[i])):
      short_s.append(s[i][j])

c = []
for i in range(len(short_s)):
  if all(short_s[i] in s[j] for j in range(n)):
    for k in range(n):
      s[k].remove(short_s[i])
    c.append(short_s[i])

ans = "".join(sorted(c))
print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		int N = stdIn.nextInt();
		int D= stdIn.nextInt();
		int ans = 0;
		int cnt = 0;
		cnt = D * 2 + 1;
		ans = N / cnt;
		if(N % cnt == 0){
			System.out.println(ans);
		}
		else{
			System.out.println(ans + 1);
		}
		stdIn.close();
	}
}

Measured memory_bytes: 35796
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;

int main()
{
	int a, b;
	cin >> a >> b;
	if(b >= a) printf("%d\n", a);
	else printf("%d\n", a - 1);
	return 0;
}

Measured memory_bytes: 256
n,a,b,c = map(int, input().split())
l=[]
for i in range(n):
    li=int(input())
    l.append(li)

bit = 1<<n
ans = 10**10

def chs(L,x):
    L2 = []
    for i in range(len(L)):
        if not 1&(x>>i):###not
            L2.append(L[i])
    return L2

def calc(L,x,ai):
    res = 0
    la = 0
    for i in range(len(L)):
        if 1&(x>>i):
            la+=L[i]
            res += 10
    if x:
        res -= 10
    res += abs(la-ai)
    return res

for ind in range(1,bit):##1から
    cost = 0
    cost += calc(l,ind,a)
    l2 = chs(l,ind)

    bit2 = 1<<len(l2)
    

    for ind2 in range(1,bit2):
        cost2 = cost
        cost2 += calc(l2,ind2,b)
        l3 = chs(l2,ind2)
        
        bit3 = 1<<len(l3)
       
        
        for ind3 in range(1,bit3):
            cost3 = cost2
            cost3 += calc(l3,ind3,c)
            if ans>cost3:
                #print(l2,l3,ind3)
                ans = cost3

print(ans)

Measured memory_bytes: 47708
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < n; i++)
        {
            var result = "";
            var line = Console.ReadLine().Trim();
            var number = "";
            for (int j = 0; j < line.Length; j++)
            {
                var aa = line.Substring(j, 1);
                if (aa != "0") number += aa;
                else
                {
                    if (number != "")
                    {
                        result += Kakutei(int.Parse(number.Substring(0, 1)), number.Length);
                        number = "";
                    }
                }
            }
            Console.WriteLine(result);
        }
    }
    public static string Kakutei(int button, int times)
    {
        var btn = new string[] { ".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        var p = times % btn[button - 1].Length - 1;
        if (p < 0) p += btn[button - 1].Length;
        return btn[button - 1].Substring(p, 1);
    }
}

Measured memory_bytes: 9600
#include <cstdio>
#include <map>
typedef long long ll;
inline int gcd(int x, int y)
{
	while (y)
	{
		int r = x % y;
		x = y;
		y = r;
	}
	return x;
}
char a[100005], b[100005];
std::map<ll, char> app;
int main()
{
	// freopen("AGC028-A.in", "r", stdin);
	int n, m;
	scanf("%d%d%s%s", &n, &m, a, b);
	ll len = (ll)n * m / gcd(n, m);
	for (int i = 0; i < n; i++)
		app[len / n * i] = a[i];
	for (int i = 0; i < m; i++)
	{
		if (app.count(len / m * i) && app[len / m * i] != b[i])
		{
			puts("-1");
			return 0;
		}
	}
	printf("%lld\n", len);
	return 0;
}


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

int main(){
    int N;
    cin >> N;
    string S;
    unordered_map<string, int> mp;

    int imax=0;

    for(int i=0; i<N; i++){
        cin >> S;
        mp[S] += 1;
        if( mp[S] > imax ){
            imax = mp[S];
        }
    }

    vector <string> Sv;

    for(auto x: mp){
        if(x.second==imax){
            Sv.push_back(x.first);
        }
    }

    sort(Sv.begin(),Sv.end());
    for(auto x: Sv){
        cout << x << endl;
    }

    return 0;
}

Measured memory_bytes: 26948
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <regex>
#include <iomanip>
#include <climits>
#include <utility>
#include <queue>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;
const dd PI = 3.1415926435;

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return b;
    }
    return gcd(b, a % b);
}

ll fact(ll n)
{
    if (n == 0)
    {
        return 1;
    }
    if (n == 1)
    {
        return 1;
    }
    return n * fact(n - 1) % MOD;
}

ll pow_fast(ll n, ll k)
{
    if (k == 0)
    {
        return 1;
    }
    if (k == 1)
    {
        return n;
    }

    if (k % 2 == 0)
    {
        ll tmp = pow_fast(n, k / 2LL);
        return tmp * tmp % MOD;
    }
    else
    {
        ll tmp = pow_fast(n, k / 2LL);
        tmp *= tmp;
        tmp %= MOD;
        return tmp * n % MOD;
    }
}

map<ll, ll> sosuu(ll n)
{
    map<ll, ll> res;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            res[i] += 1;
            n /= i;
        }
    }
    if (n != 1)
    {
        res[n] += 1;
    }
    return res;
}

int main()
{
    string S;
    cin >> S;
    cout << S[0] << S[1] << S[2] << endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <array>
#include <bitset>
#include <assert.h>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++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(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

VL a, ans;
void push(int x){
    ans.push_back(x);
    if (x == 0 || x == a.size() - 1) a.erase(a.begin() + x);
    else{
        a[x] = a[x-1] + a[x+1];
        a.erase(a.begin() + x + 1);
        a.erase(a.begin() + x - 1);
    }
}

int main() {
    int n;
    cin >> n;
    a.resize(n);
    REP(i,n) a[i] = lin();

    ll even = 0, odd = 0;
    REP(i,n){
        if (a[i] < 0) continue;
        if (i % 2 == 0) even += a[i];
        else odd += a[i];
    }

    ll ma = max(even, odd);



    if (ma == 0){
        ll m = -1e18, pos;
        REP(i,n){
            if (a[i] > m){
                m = a[i];
                pos = i;
            }
        }
        cout << m << endl << n - 1 << endl;
        int p = n;
        REP(_,pos){
            cout << 1 << endl;
            n--;
        }
        REP(_,p-1-pos){
            cout << n << endl;
            n--;
        }
        return 0;
    }

    cout << ma << endl;

    if (odd > even){
        push(0);
    }

    if (a.size() % 2 == 0) push(a.size() - 1);
    while (a[0] < 0){
        push(0);
        push(0);
    }
    while (a.back() < 0){
        push(a.size() - 1);
        push(a.size() - 1);
    }
    while (1) {
        bool ok = true;
        REP(i,a.size()){
            if (i % 2 == 0 && a[i] < 0){
                push(i);
                ok = false;
                // for (int x : a) cout << x << " ";
                //     cout << endl;
                break;
            }
        }
        if (ok) break;
    }
    int hoge = a.size() / 2;
    REP(i,hoge){
        push(1);
    }

    cout << ans.size() << endl;
    for (int x : ans) cout << x + 1 << endl;

    assert(a[0] == ma && a.size() == 1);


    return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;




int main()
{
  int a,b,c; //かっている数//最大100
  string s;
  cin >> s;

  for (int i = 0; i < s.size(); ++i){
    if (s[i]=='1'){
      s[i] ='9';
    }else{
      s[i] ='1';
    }
  }

  cout << atoi(s.c_str());
  return 0;
}



























Measured memory_bytes: 256
#include <stdio.h>
#include<vector>
#include<iostream>
#include<string>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<cmath>
using namespace std;


int main() {
	int n;
	string s;
	int ans=0;
	int pre = 0;//0=比較対象なし 1=〇 2=×

	cin >> n;
	cin >> s;
	for (int i = 0; i < n; i++)
	{
		if (pre ==0)
		{
			if (s[i] == 'O')pre = 1;
			else pre = 2;
		}
		else if (pre == 1)
		{
			if (s[i] == 'X')
			{
				ans++;
				pre = 0;
			}
		}
		else
		{
			if (s[i] == 'O')
			{
				ans++;
				pre = 0;
			}
		}
	}

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


Measured memory_bytes: 3332
#include<stdio.h>

int main(){
    int n,a,b,i,p,q;
    while(1){
        scanf("%d",&n);
		if(n==0)break;
		p=0;
		q=0;
		for(i=0;i<n;i++){
			scanf("%d%d",&a,&b);
			if(a>b)p=p+a+b;
			else if(a<b)q=q+a+b;
			else if(a==b){p=p+a;q=q+a;}
		}
		printf("%d %d\n",p,q);
    }
    return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)()
#define all(a) a.begin(),a.end()
#define vec vector
typedef long long ll;
typedef pair<int,int> p;
//const ll big=998244353;
const ll big=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
if(x<y)return x;
else return y;
}
ll expm(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1)*x)%big;
    ll t=expm(x,y/2);
    return (t*t)%big;
}
ll exp(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||y==0)return x;
    if(y%2==1)return exp(x,y-1)*x;
    ll t=exp(x,y/2);
    return t*t;
}
ll inv(ll x){
    return expm(x,big-2);
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    /*--------------------------------*/

    int n,k;cin >> n >> k;
    int l=n-k;
    /*
    k個の青をi箇所に配置する
    l:=n-k個の赤で壁をつくる
    i+1箇所に赤を分ける:
    端は0個でもかまわないが他は1つ以上
    →i-1個は確実に使う
    →l-i+1個をi+1箇所に分ける重複組み合わせ

    青:
    k-i個をi箇所に分ける重複組み合わせ

    ∴C(l-i+1+i,i)*C(k-1,i-1)
    */

    vec<ll> fac(2001),facin(2001);
    fac[0]=1;facin[0]=1;
    rep(i,fac.size()-1){
        fac[i+1]=fac[i]*(i+1) %big;
        facin[i+1]=facin[i]*inv(i+1)%big;
    }

    auto com = [&](int a,int b){
        if(a<b)return (ll)0;
        return (ll)fac[a]*facin[b]%big *facin[a-b]%big;
    };

    rep2(i,1,k+1){
        cout << com(l+1,i)*com(k-1,i-1)%big << endl;
    }
}

Measured memory_bytes: 3668
#include <stdio.h>
#define MAX 100000

int partition(int *,int,int);
void swap(int *,int,int);

int main()
{
    int a,res;
    int i;
    int A[MAX];
    
    scanf("%d",&a);
    for(i=0;i<a;i++)
    {
        scanf("%d",&A[i]);
    }
     res=partition(A,0,a-1);
     for(i=0;i<a;i++)
     {
         if(i!=0) printf(" ");
         if(i==res) printf("[");
         printf("%d",A[i]);
         if(i==res) printf("]");
     }
     printf("\n");
     return 0;
}

int partition(int *A,int p,int r)
{
    int x,temp;
    int i,j;

    x=A[r];
    i=p-1;
    for(j=p;j<=r-1;j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            swap(A,i,j);
        }
    }
    swap(A,i+1,r);
    return i+1;
}

void swap(int *A,int i,int j)
{
    int temp;
    temp=A[i];
    A[i]=A[j];
    A[j]=temp;
    return;
}


Measured memory_bytes: 2100
# include<bits/stdc++.h>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 1000000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(register int i=a; i<=n; ++i)
# define FDR(i,a,n) for(register int i=a; i>=n; --i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline LL Scan() {
    LL x=0;int 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;
}
const int N=50005;
//Code begin....

char s[55], a[55]="AKIHABARA";
int vis[55];

int main ()
{
    scanf("%s",s);
    int len=strlen(s);
    int now=0;
    for (int i=0; i<9; ++i) {
        if (now<len&&s[now]==a[i]) ++now, vis[i]=true;
    }
    if (now<len) {puts("NO"); return 0;}
    for (int i=0; i<9; ++i) if (vis[i]==false && a[i]!='A') {puts("NO");  return 0;}
    puts("YES");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Edge = pair<int, ll>;
using Graph = vector<vector<int>>;
using WeightedGraph = vector<vector<Edge>>;
const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

const int CASES = 3;

void solve() {
    string s; cin >> s;
    string ans = "Yes";
    if(s[2] != s[3]) ans = "No";
    if(s[4] != s[5]) ans = "No";
    cout << ans << endl;
}

int main() {
#ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt", "input5.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
#else

    solve();

#endif
    return 0;
}


Measured memory_bytes: 256
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N,X,Y=map(int,input().split())
    V, E= N,N
    g = [[] for i in range(V)]

    for i in range(N-1):
        g[i].append((1, i+1))
        g[i+1].append((1, i))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
    g[X-1].append((1, Y-1))
    g[Y-1].append((1, X-1))

    INF = 10 ** 10
    ans = [0] * N

    for r in range(N):
        for i in dijkstra(V, g, r):
            if i<INF:
                ans[i]+=1

    for j in range(1, N):
        print(ans[j] // 2)


resolve()

Measured memory_bytes: 56028
#include <bits/stdc++.h>
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define deb(x) cout<<#x<<"="<<x<<endl;
#define endl '\n'
#define M 1000000007
#define int long long
#define INF 1e18
#define max_n 1000000

using namespace std;

void solve()
{
	ll n;
	cin >> n;
	ll a[n];
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i + 1; j < n; ++j)
		{
			for (int k = j + 1; k < n; ++k)
			{
				if (a[i] == a[j] || a[i] == a[k] || a[j] == a[k])continue;
				if (a[i] + a[j] > a[k] && a[i] + a[k] > a[j] && a[j] + a[k] > a[i])
				{
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
}

int32_t main()
{
	IOS
	ll T = 1;
	// cin >> T;
	for (ll i = 1; i <= T; ++i)
	{
		// cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;

ll N;
ll A[100000], B[100000];
ll diff[100000];

int main(){
    cin>>N;
    rep(i,N) cin>>A[i];
    rep(i,N) cin>>B[i];

    ll sumA=0, sumB=0;
    rep(i,N){
        sumA+=A[i];
        sumB+=B[i];
    }
    if(sumA<sumB){
        cout<<-1<<endl;
        return 0;
    }

    rep(i,N){
        diff[i]=A[i]-B[i];
    }
    sort(diff,diff+N);

    ll d=sumA-sumB;
    ll ans=N;
    rep(i,N){
        if(diff[i]<0) continue;
        if(diff[i]<=d){
            d-=diff[i];
            ans--;
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 2560
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#define ps(arr) \
    debug("size %ld: ", arr.size()); \
    for(auto e: arr) cout << e << " "; \
    cout << endl;
#else
#define debug(fmt, ...)
#define ps(arr)
#endif

int main(void) {
    int num, ops;
    cin >> num >> ops;
    vector<int> map(num+1, 1);
    set<int> reds;
    reds.insert(0);
    for(int i = 0; i < ops; i++) {
        int src, dst;
        cin >> src >> dst;
        src--; dst--;
        map[src]--;
        map[dst]++;
        if(reds.count(src)) {
            reds.insert(dst);
            if(!map[src]) {
                reds.erase(src);
            }
        }
        ps(reds);
    }
    cout << reds.size() << endl;
    return 0;
}

Measured memory_bytes: 8248
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef double ld;
//typedef tree <int,null_type,less <int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(g, i, n) for (ll g = i; g < n; g++)
#define rev(g, n, i) for (ll g = n - 1; g >= i; g--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define ve vector
#define rem 1000000007
#define PI 3.141592653589793238462643383279502
ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;      // Initialize result 
    x = x % p;  // Update x if it is more than or 
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; // y = y/2 
        x = (x*x) % p; 
    } 
    return res; 
} 
ll modInverse(ll n, ll p) 
{ 
    return power(n, p-2, p); 
} 
struct point
{
    ll x,y;
};
int main()
{
    FAST
    // freopen("input1.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    /*ll tests;
    cin>>tests;
    rep (gg,0,tests)
    {}*/
    ll l;
    cin>>l;
    ll x=l*l*l;
    ld ans=(ld)x/(27);
    cout<<fixed<<setprecision(15)<<ans<<"\n";
}


Measured memory_bytes: 256
#include <utility>
#include <iostream>

using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;
	pair<int, int> p[50];
	for (int i = 0; i < N; i++)
		cin >> p[i].first >> p[i].second;
	long long a = 0;
	for (int x = 0; x < N; x++) {
		for (int X = 0; X < N; X++) {
			if (p[x].first >= p[X].first)
				continue;
			for (int y = 0; y < N; y++) {
				for (int Y = 0; Y < N; Y++) {
					if (p[y].second >= p[Y].second)
						continue;
					int n = 0;
					for (int i = 0; i < N; i++)
						if (p[i].first >= p[x].first&&
							p[i].first <= p[X].first&&
							p[i].second >= p[y].second&&
							p[i].second <= p[Y].second)
							n++;
					if (n < K)
						continue;
					auto b = (long long)(p[X].first - p[x].first)*(p[Y].second - p[y].second);
					if (!a || a > b)
						a = b;
				}
			}
		}
	}
	cout << a << endl;
	return 0;
}


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

typedef long long ll;
using namespace std;
int main()
{

  ll a,b,h;
  cin>>a>>b>>h;
  cout<<(a+b)*h/2<<endl;
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>

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

template <class T> inline void chmod(T &a, const T &b, int mod) {
  a = (a + b) % mod;
}

int main() {
  int H, W;
  std::cin >> H >> W;
  std::vector<std::vector<char>> a(H + 7, std::vector<char>(W + 7, '!'));
  for (int i = 0; i < H; ++i)
    for (int j = 0; j < W; ++j)
      std::cin >> a[i][j];

  int mod = 1000000007;
  std::vector<std::vector<long long>> dp(H + 7,
                                         std::vector<long long>(W + 7, 0));
  dp[0][0] = 1;
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      if (a[i + 1][j] == '.')
        dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
      if (a[i][j + 1] == '.')
        dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
    }
  }
  std::cout << dp[H - 1][W - 1] << std::endl;
}


Measured memory_bytes: 9216
n, w = map(int, input().split())
dp = [[0] * (w+1) for _ in range(n)]
weight, value = map(int, input().split())
for i in range(weight, w+1):
    dp[0][i] = value
for i in range(n-1):
    weight, value = map(int, input().split())
    for j in range(0, w+1):
        if j < weight:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - weight] + value)

print(dp[-1][-1])

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

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

void insertionSort(int A[], int n, int g){
    for (int i=g; i<n; i++){
        int v = A[i];
        int j = i - g;
        while (j >= 0 && A[j] > v){
            A[j+g] = A[j];
            j -= g;
            cnt++;
        }
        A[j+g] = v;
    }
}

void shellSort(int A[], int n){
    for (int h=1; ;){
        if (h > n){
            break;
        }
        G.push_back(h);
        h = 3*h + 1;
    }
    for (int i=G.size()-1; i >= 0; i--){
        insertionSort(A, n, G[i]);
    }
}
int main(){
    cin >> n;
    for (int i=0; i<n; i++){
        scanf("%d", &A[i]);
    }
    cnt = 0;
    
    shellSort(A, n);
    
    cout << G.size() << endl;
    for (int i=G.size()-1; i>=0; i--){
        printf("%d", G[i]);
        if (i){
            printf(" ");
        }
    }
    printf("\n");
    printf("%d\n", cnt);
    for (int i=0; i<n; i++){
        printf("%d\n", A[i]);
    }
    return 0;
}


Measured memory_bytes: 7184
MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = 0
    for i in range(1,c2+2):
        ans += f(r2, i)
        ans %= MOD

    for i in range(1,c2+2):
        ans -= f(r1-1, i)
        ans %= MOD

    for i in range(1,c1+1):
        ans -= f(r2, i)
        ans %= MOD

    for i in range(1,c1+1):
        ans += f(r1-1, i)
        ans %= MOD

    print(ans % MOD)


if __name__ == "__main__":
    main()


Measured memory_bytes: 132916
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;

int main(){
    int n , k ; 
    cin >> n >> k ; 
    string s ; 
    cin >> s ; 
    k--; 
    if ( s[k] >= 'A' && s[k] <= 'Z' ){
    	s[k] += 32 ; 
    }
    cout << s << endl;
    return 0 ;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
  unsigned long n, a, b;
  cin >> n >> a >> b;
  unsigned long c = 0, cc = 0;

  c = n / ( a + b );
  cc = c * a;
  if (n - (a + b) * c < a) {
    cc += n - (a + b) * c;
  } else {
    cc += a;
  }

  cout << cc << endl;
}


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

using namespace std;

using ll = long long;

static const ll MAX_P = 1000000000;

int main(){
  ll s;
  cin >> s;
  cin.ignore();

  // まず何桁


  // 10^9以下なら、X3=Y3=0, X2=Y1=0, Y2=1, X1=Sとでもすればよい
  if(s <= MAX_P){
    cout << s << " 0 0 1 0 0" << endl;
    return 0;
  }

  // それ以上なら、とりあえず10^9で割ってみる

  ll a, b;
  a = s / MAX_P;
  b = s % MAX_P;

  if(b == 0){ // X1 = 10^9, Y1 = X2 = 0, Y2 = a
    cout << MAX_P << " 0 0 " << a << " 0 0" << endl;
    return 0;
  }

  ll x1 = MAX_P;
  ll x3 = 0;
  ll y3 = 0;
  ll y2 = a + 1;

  ll y1, x2; // こいつらだけ未定
  ll sub_s = MAX_P - b;
  
  x2 = 1; // 勝手に仮定
  y1 = sub_s;

  // x1 y1 x2 y2 x3 y3
  cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << x3 << " " << y3 << endl;
  
  
  
  return 0;
}


Measured memory_bytes: 256
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]

d = []
for x, l in XL:
    d.append([x + l, l])

d.sort()

inf = float('inf')

pre = - inf
ans = N
for dd in d:
    if dd[0] - 2 * dd[1] < pre:
        ans -= 1
    else:
        pre = dd[0]

print(ans)


Measured memory_bytes: 38240
import java.util.Arrays;
import java.util.Scanner;

public class Main {
//	static int[] min = new int[1000000 + 1];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int[][] min = new int[2][1000000 + 1];
		Arrays.fill(min[0], 20000);
		Arrays.fill(min[1], 20000);
		min[0][1] = 1;
		min[1][1] = 1;
		for(int i = 2; i <= 1000000; i++){
			for(int j = 1; j < i; j++){
				int tmp = j * (j + 1) * (j + 2) / 6;
				if(i == tmp){
					min[0][i] = 1;
				}else if(i > tmp){
					min[0][i] = Math.min(min[0][i], min[0][i - tmp] + 1);
				}else{
					break;
				}
			}
		}
		for(int i = 2; i <= 1000000; i++){
			for(int j = 1; j < i; j += 2){
				int tmp = j * (j + 1) * (j + 2) / 6;
				if(tmp % 2 != 0){
					if(i == tmp){
						min[1][i] = 1;
					}else if(i > tmp){
						min[1][i] = Math.min(min[1][i], min[1][i - tmp] + 1);
					}else{
						break;
					}
				}
			}
		}
		while(n != 0){
/*
			int[] test = new int[n + 1];
			Arrays.fill(test, 20000);
			test[1] = 1;
			for(int i = 2; i <= n; i++){
				for(int j = 1; j < i; j++){
					int tmp = j * (j + 1) * (j + 2) / 6;
					if(i == tmp){
						test[i] = 1;
					}else if(i > tmp){
						test[i] = Math.min(test[i], test[i - tmp] + 1);
					}else{
						break;
					}
				}
			}
			System.out.print(test[n]);
			Arrays.fill(test, 20000);
			test[1] = 1;
			for(int i = 2; i <= n; i++){
				for(int j = 1; j < i; j += 2){
					int tmp = j * (j + 1) * (j + 2) / 6;
					if(tmp % 2 != 0){
						if(i == tmp){
							test[i] = 1;
						}else if(i > tmp){
							test[i] = Math.min(test[i], test[i - tmp] + 1);
						}else{
							break;
						}
					}
				}
			}
			System.out.println(" " + test[n]);*/
			System.out.println(min[0][n] + " " + min[1][n]);
			n = sc.nextInt();
		}
		
		sc.close();
	}
/*	static int func(int n){
		if(min[n] > 0){
			return min[n];
		}
		int res = 20000;
		int tmp = n;
		for(int i = 1; i < n; i++){
			tmp = i * (i + 1) * (i + 2) / 6;
			if(n == tmp){
				min[n] = 1;
				return min[n];
			}else if(n > tmp){
				res = Math.min(res, func(n - tmp) + 1);
			}else if(n < tmp){
				break;
			}
		}
		min[n] = res;
		return res;
	}
	static int oddfunc(int n){
		if(min[n] > 0){
			return min[n];
		}
		int res = 20000;
		int tmp = n;
		for(int i = 1; i < n; i += 2){
			tmp = i * (i + 1) * (i + 2) / 6;
			if(tmp % 2 != 0){
				if(n == tmp){
					min[n] = 1;
					return min[n];
				}else if(n > tmp){
					res = Math.min(res, oddfunc(n - tmp) + 1);
				}else if(n < tmp){
					break;
				}
			}
		}
		min[n] = res;
		return res;
	}*/

}

Measured memory_bytes: 34648
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18

ll mod = 1e9+7;
  
int main() {
	// 入力
	ll N;cin>>N;
    ll H[N];REP(i,N)cin>>H[i];
    
    
	// 解法
    ll tmp = 0;
    ll count = 0;
	ll ans = 0;
    REP(i,N){
        if (i==0){
            count = 0;
        }
        else if (H[i-1]>=H[i]){
            count++;
        }
        else{
            count = 0;
        }
        if (count>ans) ans = count;
    }
    
	//出力
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30;
int MOD = 1e9+7;
main(){
    int N;
    cin >> N;
    vector<ll> A(N),sum(N+1);
    for(int i = 0;i < N;i++)cin >> A[i];
    sort(A.begin(),A.end());
    int cnt = 1;
    for(int i = 1;i < N;i++){
        sum[i] = sum[i-1] + A[i-1];
        if(sum[i]*2 >= A[i])cnt++;
        else cnt = 1;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 1792
#include <stdio.h>

int main(){
	int n, c[510], s[510], f[510];
	scanf("%d", &n);
	for(int i = 0, *pc = c, *ps = s, *pf = f; i < n - 1; ++i, ++pc, ++ps, ++pf) scanf("%d%d%d", pc, ps, pf);
	s[n - 1] = c[n - 1] = 0;
	f[n - 1] = 1;
	for(int i = 0; i < n; i++){
		int ans = 0;
		for(int j = i; j < n; j++) ans = (ans < s[j] ? s[j] + c[j] : (ans / f[j] + (ans % f[j] != 0)) * f[j] + c[j]);
		printf("%d\n", ans);
	}
}

Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
	long long a,b,x;
	long long ans=0;
	scanf("%lld %lld %lld",&a,&b,&x);
		if(a==0){
	ans=(b/x)+1;
	printf("%lld",ans);}
	else
	{
	
	ans=(b/x)-((a-1)/x);
	printf("%lld",ans);}

	return 0;
	
}

Measured memory_bytes: 256
package main

//B - Resale

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

//エラーが発生したときは勝手にpanicしろって関数にはmustって名前を付ける慣例
func mustParseInt(text string) int {
	num, err := strconv.Atoi(text)
	if err != nil {
		panic(err)
	}
	return num
}

func mustParseFloat(text string) float64 {
	num, err := strconv.ParseFloat(text, 64)
	if err != nil {
		panic(err)
	}
	return num
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	var line string
	scanner.Scan()

	line = scanner.Text()
	n := mustParseInt(line)

	scanner.Scan()
	line = scanner.Text()
	v_str_array := strings.Split(line, " ")
	//	v_int_array := make([]int, len(v_str_array))

	scanner.Scan()
	line = scanner.Text()
	c_str_array := strings.Split(line, " ")
	//	c_int_array := make([]int, len(c_str_array))

	//	xmy_int_array := make([]int, n)
	ans := 0
	for i := 0; i < n; i++ {
		xmy := mustParseInt(v_str_array[i]) - mustParseInt(c_str_array[i])
		if xmy > 0 {
			ans = ans + xmy
		}

	}

	fmt.Println(ans)
}


Measured memory_bytes: 640
n = int(input())
a = list(map(int, input().split()))

max_a = max(a)
min_a = min(a)
count = 0
ans = []
if abs(min_a) <= abs(max_a):
    max_i = 0
    for i in range(n):
        if a[i] == max_a:
            max_i = i
    for i in range(n):
        ans.append([max_i+1, i+1])
        count += 1
    for i in range(n-1):
        ans.append([i+1, i+2])
        count += 1
else:
    min_i = 0
    for i in range(n):
        if a[i] == min_a:
            min_i = i
    for i in range(n):
        ans.append([min_i+1, i+1])
        count += 1
    for i in range(n-1, 0, -1):
        ans.append([i+1, i])
        count += 1

print(count)
for i in ans:
    print(*i)


Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]
    n = int(input())
    s = input()
    cnt = defaultdict(int)
    for e in s:
        cnt[e] += 1
    ans = 0
    for i in range(n):
        e = s[i]
        x = n - i - cnt[e]
        xd = 1
        cnt[e] -= 1
        for c in cnt:
            if cnt[c] and c != e:
                xd *= (cnt[c]+1)
        ans += xd
        ans %= MOD
    
    print(ans%MOD)

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

azyxwvutsrqponmlkjihgfedcb

"""


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

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

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

void solve(long long N, long long M, std::vector<long long> L,
           std::vector<long long> R) {

  long long s = *min_element(R.begin(), R.end()) - *max_element(L.begin(), L.end());
  if( s >= 0 ){
    cout << s + 1 << endl;
  }else{
    cout << 0 << endl;
  }
}

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


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

int main() {
  int H, W;
  cin >> H >> W;

  for (int i = 0; i < W + 2; i++) {
    cout << '#';
  }
  cout << endl;

  for (int i = 0; i < H; i++) {
    string s;
    cin >> s;
    cout << '#' << s << '#' << endl;
  }

  for (int i = 0; i < W + 2; i++) {
    cout << '#';
  }
  cout << endl;
}

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

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

    if (n %2 == 0)
        printf("%0.10f", (double((double)(n/2)) / n));
    else
        printf("%0.10f", (double)((double)(n+1) /2) / n);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
class Display
{
	string msg[2] = { "Yes","No" };
public:
	void disp(bool result) { 
		cout << msg[result] << endl;
	}
};
class Rect
{
	int W, H;
	bool under(int b, int r){return (b - r < 0) ? true : false;}
	bool over(int b, int r, int m){	return (b + r > m) ? true : false;}
public :
	Rect(int w, int h) :W(w), H(h) {}
	bool error(int x, int y, int r)
	{if (!under(x, r) && !under(y, r) && !over(x, r, W) && !over(y, r, H)) return false;
		return true;
	}
};
class Circle
{
	int x, y,r;
public:
	Circle(int x, int y ,int r) :x(x), y(y),r(r) {}
	bool over(Rect& rect) {return rect.error(x, y, r);}
};

int main()
{
	int w,h,x,y,r;
	cin >> w>>h>>x>>y>>r;
	Display dsp;
	Rect rect(w, h);
	Circle circle(x, y, r);
	dsp.disp(circle.over(rect));
	return 0;

}

Measured memory_bytes: 3180
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<iso646.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

#define FOR(counter,initial_value,condition) for(int counter = initial_value; counter < condition;counter++)


int main()
{
	string ans = "";
	string o, e;
	cin >> o >> e;
	int countO=0, countE=0;
	FOR(i, 0, o.length() + e.length()) {
		if (i % 2 == 0) {
			ans += o[countO];
			countO++;
		}
		else {
			ans += e[countE];
			countE++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


    class Program
    {
        static void Main(string[] args)
        {
            int num = int.Parse(Console.ReadLine());
            var input = Console.ReadLine().Split(' ');
            int count = 0;
            for(int i = 0; i < num; i++){
                if(i % 2 == 0){
                    int n = int.Parse(input[i]);
                    if(n % 2 == 1){
                        count++;
                    }
                }
            }
            Console.WriteLine(count);
        }
    }

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

using namespace std;
#define FOR(i,s,e) for (int i=(s); i<(e); i++)
#define FOE(i,s,e) for (int i=(s); i<=(e); i++)
#define FOD(i,s,e) for (int i=(s); i>=(e); i--)
#define pb(x) push_back(x)
#define ppb() pop_back()
#define mp(x,y) make_pair(x,y)
#define LL long long
#define ULL unsigned long long
#define pi acos(-1.0)
LL max(LL a,LL b){if (a>b){return a;} else {return b;}}
LL min(LL a,LL b){if (a<b){return a;} else {return b;}}

#define time AHAHa
#define eps 1e-6

int n, k;

string x;

int time[200001];

int ptr;

int main(){
    cin >> x;
    n = x.length();
    
    scanf("%d", &k);
    
    FOE(i, 0, n - 1){
        time[i + 1] = (x[i] == 'a'? 0: (int)('z') - (int)x[i] + 1);
    }
    
   // FOE(i, 1, n) printf("time[%d] = %d\n", i, time[i]);
    
   // cout << x << endl;
    
    FOE(i, 0, n - 2){
        if (k >= time[i + 1]){
            x[i] = 'a';
            k -= time[i + 1];
        }
    }
    
 //   cout << x << endl;
    int cyc = k % 26;
    FOE(i, 1, cyc){
        if (x[n - 1] == 'z') x[n - 1] = 'a';
        else x[n - 1] = (char)((int)x[n - 1] + 1);
    }
    
    cout << x << endl;
        
    return 0;
}

Measured memory_bytes: 1024
/*
 * atcoder/abc149/d.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

/*
 * 8 7 6
 *
 *   0 1  0  2  0
 *   0 1  2  3  4
 * 0 0 14 14 14 21
 * 1 0 6  14 21 21
 * 2 6 6  14 14 27
 */
int N, K;
int S[3];
vector<int> A;
// dp[n][t] := n番目にtを出した時の最大スコア
ll dp[100100][3] = {0};

int score(int a, int b) {
  if (a == 0 and b == 1) return S[a];
  if (a == 1 and b == 2) return S[a];
  if (a == 2 and b == 0) return S[a];
  return 0;
}

void print() {
  loop(t,0,3) {
    loop(n,0,N) {
      cout << dp[n][t] << "\t";
    }
    cout << endl;
  }
}

void solve() {
  string T;
  cin >> N >> K >> S[0] >> S[1] >> S[2] >> T;
  A.resize(N);
  loop(n,0,N) {
    char c = T[n];
    if (c == 'r') A[n] = 0;
    else if (c == 's') A[n] = 1;
    else A[n] = 2;
  }

  for (int n=0; n<K; n++) {
    for (int k=n; k<N; k += K) {
      for (int t=0; t<3; t++) {
        if (k<K) { dp[k][t] = score(t, A[k]); continue; }
        for (int prev_t=0; prev_t<3; prev_t++) {
          if (prev_t == t) continue;
          chmax(dp[k][t], dp[k-K][prev_t] + score(t, A[k]));
        }
      }
    }
  }
  // print();

  ll total = 0;
  for (int i=0; i<K; i++) total += max(dp[N-i-1][0], max(dp[N-i-1][1], dp[N-i-1][2]));
  cout << total << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


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

int main(){
  long long N;
  cin >> N;
  vector<string> S(N);
  for(int i = 0; i < N; i++){
    cin >> S.at(i);
  }
  sort(S.begin(), S.end());
  long long cnt;
  cnt = 1;
  for(int i = 1; i < N; i++){
    if(S.at(i) != S.at(i - 1)) cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 9588
#include <bits/stdc++.h>
using namespace std;
int main() {
  cout<<fixed<<setprecision(10);
  int N;
  cin >> N;
  double A[N];
  for (int i=0;i<N;i++) cin >> A[i];
  double m=0;
  for (int i=0;i<N;i++) m += 1.0/A[i];
  cout << 1/m << "\n";
}

Measured memory_bytes: 256