akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int gcd(int a, int b){
    while(a != b){
        if(a > b) a = a - b; else b = b - a;
    }
    return a;
}

int lcm(int a, int b){
    return ((a / gcd(a, b)) * b);
}

int main(){
    int h, w;
    while(true){
char torus[10][20];
        string str[2048];
        bool ok[2048];
        int num = 0;

        for(int i=0; i<2048; ++i){
            str[i] = "";
            ok[i] = true;
        }

        cin >> h >> w;
        if(h==0 && w==0) break;

        int cml = lcm(w, h);

        for(int i=0; i<h; ++i){
            for(int j=0; j<w; ++j){
                cin >> torus[i][j];
            }
        }

        //一番長い文字列をつくる

        for(int y=0; y<h; ++y){
            for(int x=0; x<w; ++x){
                for(int i=0; i<h; ++i){
                    str[num] += torus[(y+i)%h][x];
                    str[num+1] += torus[h-(y+i)%h-1][x];
                }
                num += 2;
            }
        }
        for(int y=0; y<h; ++y){
            for(int x=0; x<w; ++x){
                for(int i=0; i<w; ++i){
                    str[num] += torus[y][(x+i)%w];
                    str[num+1] += torus[y][w-(x+i)%w-1];
                }
                num += 2;
            }
        }
        for(int y=0; y<h; ++y){
            for(int x=0; x<w; ++x){
                for(int i=0; i<cml; ++i){
                    str[num] += torus[(y+i)%h][(x+i)%w];
                    str[num+1] += torus[(y+i)%h][w-(x+i)%w-1];
                    str[num+2] += torus[h-(y+i)%h-1][(x+i)%w];
                    str[num+3] += torus[h-(y+i)%h-1][w-(x+i)%w-1];
                }
                num += 4;
            }
        }


        string result = "";

        sort(str, str+num);

        for(int i=0; i<num-1; ++i){
            int length = 0;
            for(int j=0; j<min(str[i].length(), str[i+1].length()); ++j){
                if(str[i][j] == str[i+1][j]) ++length; else break;
            }
            if(length == result.length()){
                result = min(result, str[i].substr(0, length));
            }else if(length > result.length()){
                result = str[i].substr(0, length);
            }
        }

        cout << ((result.length() == 1) ? "0" : result) << endl;

    }

    return 0;
}

Measured memory_bytes: 1516
#include <stdio.h>

int mex(int a,int b){
	int s=0;
	while(((1<<a|1<<b)>>s)&1)s++;
	return s;
}

int main(){
	int k;
	scanf("%d",&k);
	int ans=0;
	while(k--){
		long long a,r;
		scanf("%lld%lld",&a,&r);
		int g[2]={r%2,1^r%2};
		while(!(r/2<a&&a<=r)){
			long long nr=r/2;
			int ng[2];
			ng[nr%2]=mex(g[0],g[(nr+1)%2]);
			ng[(nr%2)^1]=mex(g[0],ng[nr%2]);
			r=nr;
			g[0]=ng[0];
			g[1]=ng[1];
		}
		ans^=g[a%2];
	}
	puts(ans?"mo3tthi":"tubuann");
}


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

// Template for atcoder
public class Main {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    private static final int[] dx = {0, -1, 0, 1};
    private static final int[] dy = {1, 0, -1, 0};

    void solve() throws IOException {
        int n = nextInt();
        double[] prob = new double[n];
        for (int i = 0; i < n; i++) {
            prob[i] = nextDouble();
        }
        int LIMIT = 3000;
        double[] dp = new double[LIMIT];
        dp[0] = 1.0;
        for (int i = 0; i < n; i++) {
            double[] nxt = new double[LIMIT];
            for (int j = 0; j < LIMIT; j++) {
                if (dp[j] == 0) {
                    continue;
                }
                nxt[j + 1] += dp[j] * prob[i];
                nxt[j] += dp[j] * (1 - prob[i]);
            }

            dp = nxt;
        }

        double res = 0;
        for (int i = 0; i < LIMIT; i++) {
            if (2 * i > n) {
                res += dp[i];
            }
        }
        outln(res);
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public Main() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new Main();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}


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

int main(void)
{
    int N;
    cin >> N;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin >> A.at(i);
    }
    vector<ll> d(2*N+30, 0);  // [-N, N], i = i+N
    ll count = 0;
    for(int i=0;i<N;i++){
        if(A[i] >= N) continue;
        int ind = A[i] - i + 1;
        count += ll(d[ind+N]);
        
        ll ind2 = ll(A[i]) * -1ll + 1ll - ll(i);
        if(ind2+ll(N) < 0) continue;
        d[ind2+N]++;
    }
    cout << count << endl;
    return 0;
}


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

int main(){
  int n, f=0;
  cin >> n;

  int a, m=n;
  while(n>0){
    a=n%10;
    f+=a;
    n/=10;
//   cout << f << endl;
  }
//  cout << n%f << endl;

  if(m%f==0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
long long f(int x){
    if(x <= 1) return 1;
    return (1<<(x-1));
}
int main(void){
    string s;
    cin >> s;
    int len = s.length();
    long long ans = 0;
    for(int i=0;i<len;i++){
        for(int j=1;j<=len-i;j++){
            long long t = stoll(s.substr(i, j));
            ans += t * f(i) * f(len-i-j);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define sz(x) x.size()
#define printarray(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define rep(n) for (ll i = 0; i < n; i++)
#define repc(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define DEC(i, x, y) for (int i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define alla(a, n) a, a + n
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b)/gcd(a, b)
#define int long long int
#define ull unsigned long long

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 5;

int fastexpo(int b, int exp){
    if(exp == 0) return 1;
    if(exp == 1) return b;
    int ans = (fastexpo(b,exp/2) % MOD);
    ans *= ans;
    ans %= MOD;
    if(exp % 2 == 1){
        ans *= b;
    }
    ans %= MOD;
    return ans;
}

vector<int> adj[MAXN];
int deg[MAXN];
int depth[MAXN] = {0};

void dfs(int s){
	for(int u: adj[s]){
		dfs(u);
		depth[s] = max(depth[s], depth[u]+1);
	}
	return;
}

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

    string s;
    cin>>s;
    int n = s.length() + 1;
    for(int i = 1;i<n;i++){
    	if(s[i-1] == '<'){
    		adj[i+1].pb(i);
    		deg[i]++;
    	} else {
    		adj[i].pb(i+1);
    		deg[i+1]++;
    	}
    }    
    for(int i = 1;i<=n;i++){
    	if(deg[i] == 0){
    		dfs(i);
    	}
    }
    int sum = 0;
    for(int i = 1;i<=n;i++){
    	sum += depth[i];
    }
    cout<<sum<<endl;

    return 0;
}


Measured memory_bytes: 59292
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;

ll len = 0;
vector<ll> vec(2e6,0);

void insert(ll k){
  vec[len] = k;
  ll t1,t2;
  t1 = len;
  while(t1 != 0){
    t2 = (t1-1)/2;
    if(vec[t2] < vec[t1]){
      swap(vec[t2],vec[t1]);
    }else{
      break;
    }
    t1 = t2;
  }
  len++;
}
ll extract(){
  ll ret = vec[0];
  ll piv = 0;
  ll t1,t2;
  while(1){
    t1 = piv*2+1;
    t2 = piv*2+2;
    if(t1 >= len){
      break;
    }else if(t2 == len){
      vec[piv] = vec[t1];
      piv = t1;
      break;
    }else{
      if(vec[t1] < vec[t2]){
        vec[piv] = vec[t2];
        piv = t2;
      }else{
        vec[piv] = vec[t1];
        piv = t1;
      }
    }
  }

  vec[piv] = vec[len-1];
  t1 = piv;
  while(t1 != 0){
    t2 = (t1-1)/2;
    if(vec[t2] < vec[t1]){
      swap(vec[t2],vec[t1]);
    }else{
      break;
    }
    t1 = t2;
  }

  len--;
  return ret;
}
int main(){
  string str;
  ll ret;
  while(1){
    cin >> str;
    if(str == "insert"){
      cin >> t1;
      insert(t1);
    }else if(str == "extract"){
      ret = extract();
      cout << ret << endl;
    }else if(str == "end"){
      break;
    }
//    rep(i,len){
//      cout << vec[i] << " ";
//    }
//    cout << endl;
  }
  return 0;
}


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

#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

vector<int> h;
int water(int head, int tail)
{
    int mn = INF;
    for (int i = head; i < tail+1; i++)
    {
        mn = min(h[i], mn);
    }
    for (int j = head; j < tail + 1; j++)
    {
       h[j] -= mn;
    }

    return mn;
} 
int main()
{
    int n;
    cin >> n;

    h.resize(n);

    rep(i,n)
    {
        cin >> h[i];
    }
    int ans = 0;
    int flag = 0;
    while (flag == 0)
    {
        int head ,tail;
        int temp = 0;
        rep(i,n)
        {
            if (h[i]!= 0 && temp ==0)
            {
                head = i;
                temp++;
            }
            
            if (h[i] == 0&& temp == 1)
            {
                tail = i-1;
                temp++;
            }
        }
        if (temp == 0)
        {
            flag = 1;
        }else if (temp == 1)
        {
            
            ans+=water(head,n-1);

        }else
        {
            ans+=water(head,tail);
        }
    }

    cout << ans << endl;  
}

Measured memory_bytes: 256
f=lambda:map(int,input().split())
n,k,l=f()
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def g(x):
  global p
  p=[-1]*n
  for _ in range(x):
    a,b=f()
    unite(a-1,b-1)
  return [root(i) for i in range(n)]
H,R=g(k),g(l)
from collections import *
z=[*zip(H,R)]
C=Counter(z)
print(*[C[t] for t in z])

Measured memory_bytes: 56612
use v5.18; # strict say state
use warnings;

my ($n, $k) = split / /, <STDIN>;
my @a = split / /, <STDIN>;
@a = sort { $a <=> $b } @a;
my $MOD = 1e9 + 7;
sub modpow {
  my ($a, $n) = @_;
  my $r = 1;
  while ($n > 0) {
    $r = $r * $a % $ MOD if $n & 1;
    $a = $a * $a % $MOD;
    $n >>= 1;
  }
  return $r;
}
sub modinv {
  my $a = shift;
  modpow($a, $MOD - 2);
}
my (@fac, @finv);
$fac[0] = 1;
$finv[0] = 1;
for my $i (1..$n) {
  $fac[$i] = $fac[$i-1] * $i % $MOD;
  $finv[$i] = modinv($fac[$i]);
}
sub combi {
  my ($n, $k) = @_;
  $fac[$n] * ($finv[$n-$k] * $finv[$k] % $MOD) % $MOD;
}
my $ans = 0;
for (my $i=0; $i<=$n-$k; $i++) {
  my $c = combi($n-$i-1, $k-1);
  $ans += ($MOD + $a[$n-$i-1]) * $c;
  $ans %= $MOD;
  $ans += ($MOD - $a[$i]) * $c;
  $ans %= $MOD;
}
say $ans;

Measured memory_bytes: 22676
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define fi first
#define sc second
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define ANS cout << ans << endl
#define RETURN(x)    \
  cout << x << endl; \
  return 0
clock_t CLOCK;
#define START_TIMER CLOCK = clock()
#define SHOW_TIMER cerr << "time: " << (ld)(clock() - CLOCK) / 1000000 << endl
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define debug(x) cerr << "[debug] " << #x << ": " << x << endl;
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << endl;
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using mll = map<ll, ll>;
using qll = queue<ll>;
using P = pair<ll, ll>;

constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ld PI = 3.141592653589793238462643383279;
ll get_digit(ll x) {
  return to_string(x).size();
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

signed main() {
  init();
  string S;
  cin >> S;
  S[3] = '8';
  COUT(S);
  return 0;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main(){
	string s;
	cin >> s;
	long long ans = 0;
	for (int i = 0;i < (1 << (s.size()-1));i++){
		int last = -1;
		long long res = 0;
		for (int j = 0;j+1 < s.size();++j){
			if((i&(1<<j)) != 0){
				long long cur = 0;
				for (int z = last +1;z <= j;++z){
					cur = cur * 10+s[z] - '0';
				}
				res += cur;
				last = j;
			}
		}
		long long cur = 0;
		for (int j = last + 1;j < s.size();++j){
			cur = cur*10+s[j] - '0';
		}
		res += cur;
		ans += res;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        int count, n, x, i, j, k;
        while(true){
            count = 0;
            n = scan.nextInt();
            x = scan.nextInt();
            if(n == 0 && x ==0) break;
            for(i = 1; i <= n; i++){
                for(j = i + 1; j <= n; j++){
                    for(k = j + 1; k <= n; k++){
                        if(i != j && i != k && j != k){
                        	if(x == i + j + k) count++;
                        }
                    }
                }
            }
            System.out.printf("%d\n", count);
        }
        scan.close();
    }
}



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

int main(void){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> d;
    long long max_1 = 0, max_2 = 0;
    rep(i, n){
        cin >> a.at(i);
        d[a.at(i)];
        d.at(a.at(i))++;
        if(d.at(a.at(i))==2){
            if(a.at(i)>max_1){
                max_2 = max_1;
                max_1 = a.at(i);
            }
            else if(a.at(i)>max_2){
                max_2 = a.at(i);
            }
        }
        else if(d.at(a.at(i))==4){
            if(a.at(i)>max_2){
                max_2 = a.at(i);
            }
        }
    }
    cout << max_1*max_2 << endl;
    return 0;
}

Measured memory_bytes: 5376
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define RREP(i, n) for(int i = n - 1; i >= 0; i--)
#define REP2(i, n, k) for(int i = 0; i < n; i += k)

int main() {
    ll n, p[1000] = {};
    
    cin >> n;
    for(ll i = 2; i <= n; i++){
        ll t = i;
        for(ll j = 2; t != 1; j++){
            while(t % j == 0 && t != 1){
                t /= j;
                p[j]++;
            }
        }
    }
    
    ll ans = 1;
    REP(i, 1000){
        if(p[i]){
            ans *= p[i] + 1;
            ans %= MOD;
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M,Q;
vector<vint> a(50,vint(4));

int score=0;

void search(vint v){
  if(N == (int)v.size()){
    int total = 0;
    REP(i,Q){
      if(a[i][2] == v[a[i][1]] - v[a[i][0]])total += a[i][3];
    }
    chmax(score,total);
    return;
  }
  int st;
  if(0 == v.size())st = 0;
  else st = v.back();
  for(int i=st; i<M; i++){
    v.pb(i);
    search(v);
    v.pop_back();
  }
}

int main()
{
  cin >> N >> M >> Q;
  REP(i,Q){
    cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    a[i][0]--;
    a[i][1]--;
  }
  vint v;
  search(v);
  cout << score << endl;
}

Measured memory_bytes: 3608
#include<cstdio>
using namespace std;
int a,b;
int main() {
	scanf("%d%d",&a,&b);
	if(a>0)puts("Positive");
	else if(b>=0)puts("Zero"); 
	else if((a&1)^(b&1))puts("Positive"); 
	else puts("Negative");
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<iomanip>
#include<unordered_map>
#include<unordered_set>
using namespace std;

int main()
{
    int count = 0, i, len;
    string S, T;
    cin>>S>>T;
    len = S.length();
    for(i=0;i<len;i+=1)
    {
        if(S[i]!=T[i])
        {
            count+=1;
        }
    }
    cout<<count<<endl;
}


Measured memory_bytes: 3916
import java.util.Scanner;

public interface Main {
	static int a = 1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		System.out.printf("%d %d\n", a*b,(a+b)*2);
	}
}


Measured memory_bytes: 26128
N = int(input())
H = list(map(int,input().split()))

ans = 1
for i in range(1,N):
  cnt = 0
  for j in range(i):
    if i != j:
      if H[j] <= H[i]:
        cnt += 1
  if cnt == i:
    ans += 1
print(ans)

Measured memory_bytes: 3060
//{{{
#pragma GCC diagnostic ignored "-Wunknown-pragmas"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef LOCAL
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}

const int N = 2e5 + 10;
const int mod = 1e9 + 7;

string s;
int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif

    while (cin >> s)
    {
        int sum = 0;
        for (auto ch : s)
        {
            int d = ch - '0';
            sum += d;
        }
        if (sum % 9 == 0)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3748
#include <stdio.h>

int main(){
    int omori[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
    int flag[10];
    int g, i, s;

    while(scanf("%d", &g) != EOF){
        for(i = 0; i < 10; i++) flag[i] = 0;

        for(i = 9; i >= 0; i--){
            if(g >= omori[i]){
                flag[i] = 1;
                g -= omori[i];
            }
        }

        s = 0;
        for(i = 0; i < 10; i++){
            if(flag[i] == 1){
                if(s == 1) printf(" ");
                printf("%d", omori[i]);
                if(s == 0) s = 1;
            }
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/





int N, A;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A;
    
    if ((N % 500) <= A) printf("Yes\n");
    else printf("No\n");
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N, K;
	in >> N >> K;
	out << (1 + 2 * (K - 1) <= N ? "YES" : "NO") << std::endl;
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

h, w = map(int, readline().split())
memo_graph = [list(map(int, readline().split())) for _ in range(10)]
cost = floyd_warshall(csr_matrix(memo_graph))
ans = 0
for i in range(h):
    for a in list(map(int, readline().split())):
        if a != -1:
            ans += cost[a][1]
print(int(ans))


Measured memory_bytes: 13760
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
ll gcd(int a,int b)
{
if(a>b)
swap(a,b);
 
if(a==0)
  return b;
return gcd(b%a,a);
 
}
int main()
{ 
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);

ll n;
cin>>n;
string s;
cin>>s;
ll ans=0;
ll zer=0;
for(ll i=0;i<n;i++)
{ ll blue=0;
  ll red=0;
  ll green=0;

  for(ll j=i+1;j<n;j++)
  {
    if(s[i]=='R')
    {if(s[j]=='B')
     {if((i+j)%2==0&&s[(i+j)/2]=='G')
       ans+=max(zer,green-1);
     else ans+=green;
      }
     if(s[j]=='G')
     {
     if((i+j)%2==0&&s[(i+j)/2]=='B')
     ans+=max(zer,blue-1);
     else ans+=blue;
     
     }
    }



    if(s[i]=='G')
    {if(s[j]=='B')
     {if((i+j)%2==0&&s[(i+j)/2]=='R')
     ans+=max(zer,red-1);
     else ans+=red;
      }
     if(s[j]=='R')
     {
     if((i+j)%2==0&&s[(i+j)/2]=='B')
     ans+=max(zer,blue-1);
     else ans+=blue;
     
     }
    }



    if(s[i]=='B')
    {if(s[j]=='R')
     {if((i+j)%2==0&&s[(i+j)/2]=='G')
     ans+=max(zer,green-1);
     else ans+=green;
     }
     if(s[j]=='G')
     {
     if((i+j)%2==0&&s[(i+j)/2]=='R')
     ans+=max(zer,red-1);
     else ans+=red;
     
     }
     }
     

    if(s[j]=='R')
    red++;
    if(s[j]=='B')
    blue++;
    if(s[j]=='G')
    green++;
   
  }

}cout<<ans<<endl;

}
 
 

Measured memory_bytes: 3648
#142_D
from fractions import gcd
a, b = map(int, input().split())
ab = gcd(a, b)

def factorization(n):
    arr = [1]
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            while tmp % i == 0:
                tmp //= i
            arr.append(i)

    if tmp != 1:
        arr.append(tmp)

    if arr == []:
        arr.append(n)

    return arr

print(len(factorization(ab)))

Measured memory_bytes: 5048
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ACC ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mod 1000000007
#define MAXN 10000001
//string alpha="abcdefghijklmnopqrstuvwxyz";
//int dx[]={1,-1,0,0};
//int dy[]={0,0,1,-1};
//int dx8[]={1,-1,0,0,1,1,-1,-1};
//int dy8[]={0,0,1,-1,1,-1,1,-1};
/*int spf[MAXN];
void sieve()
{
	int i,j;
	for(i=0;i<MAXN;i++)
	spf[i]=i;
	for(i=4;i<MAXN;i+=2)
	spf[i]=2;
	for(i=3;i*i<MAXN;i++)
	{
		if(spf[i]==i)
		{
			for(j=i*i;j<MAXN;j+=i)
			{
				if(spf[j]==j)spf[j]=i;
			}
		}
	}
}*/
bool isvowel(char c)
{
    switch(c)
    {
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u':return true;
        default : return false;
    }
}
/*bool isValid(int x,int y,int n,int m)
{
    if(x<0||x>n-1||y<0||y>m-1)return false;
    return true;
}*/
/*
bool comp(pair<int,int> x,pair<int,int> y)
{
    if(y.second==x.second)
        return y.first<x.first;
    return y.second<x.second;
}*/
int32_t main()
{
    ACC
    int T;
    T=1;
    //cin>>T;
    while(T--)
    {
        int i,n;
        cin>>n;
        vector<pair<int,int>> v;
        for(i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            v.pb({x,y});
        }
        bool f=false;
        for(i=0;i<n-2;i++)
        {
            if(v[i].first==v[i].second&&v[i+1].first==v[i+1].second&&v[i+2].first==v[i+2].second)
            {

                f=true;
                break;
            }
        }
        if(f)cout<<"Yes\n";
        else cout<<"No\n";
    }

    return 0;
}


Measured memory_bytes: 3656
while(True):
    a = input()
    if a == '-':
        break
    if a.isdecimal():
        stimes = int(a)
        for i in range(stimes):
            b = int(input())
            char = char[b:] + char[:b]
        else:
            print(char)
    else:
        char = a
        


Measured memory_bytes: 5592
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

/**
 * Baton Relay Game
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		while ((line = br.readLine()) != null && !line.isEmpty()) {
			StringTokenizer st = new StringTokenizer(line);
			int N = Integer.parseInt(st.nextToken());

			Deque<Integer> relays = new ArrayDeque<Integer>();
			Deque<Integer> duties = new ArrayDeque<Integer>();

			for (int i = 0; i < N; i++) {
				relays.offer(i);
			}

			st = new StringTokenizer(br.readLine());
			while (st.hasMoreTokens()) {
				int a = Integer.parseInt(st.nextToken());
				if (a % 2 == 0) {
					for (int i = 0; i < a; i++) {
						relays.offer(relays.poll());
					}
				} else {
					for (int i = 0; i < a; i++) {
						relays.offerFirst(relays.pollLast());
					}
				}
				duties.offer(relays.pollFirst());
			}

			st = new StringTokenizer(br.readLine());
			while (st.hasMoreTokens()) {
				int q = Integer.parseInt(st.nextToken());
				System.out.println(duties.contains(q) ? 0 : 1);
			}

		} // end while
	} // end main
}

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

struct Edge {
	long long cost;
	int from, to;
	Edge() {}
	Edge(int from, int to, long long cost) : from(from), to(to), cost(cost) {}
};

static const int MAX = 1000;
static const long long INF = 1000000000000000LL;
int N, M;
Edge e[2 * MAX];
long long d[MAX];

bool bellman_ford() {
	for (int i = 0; i < MAX; i++) {
		d[i] = INF;
	}
	// 頂点 0 からスタート
	d[0] = 0;
	for (int i = 0; i < 2 * N; i++) {
		for (int j = 0; j < M; j++) {
			if (d[e[j].from] != INF && d[e[j].to] > d[e[j].from] + e[j].cost) {
				d[e[j].to] = d[e[j].from] + e[j].cost;
				if (i >= N - 1 && e[j].to == N - 1) return true;
			}
		}
	}
	return false;
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		long long c;
		cin >> a >> b >> c;
		e[i] = Edge(a - 1, b - 1, -c);
	}
	if (bellman_ford()) {
		cout << "inf" << endl;
	}
	else {
		cout << -d[N - 1] << endl;
	}
	return 0;
}


Measured memory_bytes: 3660
#include<iostream>
// 配列出力関数
void OutputArray(int A[], int N)
{
    for (int x=0; x<N-1; x++) {
        std::cout << A[x] << " ";
    }
    std::cout << A[N-1] << std::endl;
}
// 挿入ソート実行関数
void InsertionSort(int A[], int N)
{
    OutputArray(A, N);
    for (int i=1; i<N; i++) {
        int v = A[i];
        int j = i-1;
        while(j>=0 && A[j] > v) {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        OutputArray(A, N);    
    }
}

int main()
{
    static const int MAX = 100;
    int n, R[MAX];
    std::cin >> n;
    
    for (int i=0; i<n; i++) std::cin >> R[i];
    
    InsertionSort(R, n);
    return 0;
}


Measured memory_bytes: 3084
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;

struct Node{
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;

Node * find(Node *u, int k){
    while(u != NIL && k != u->key){
        if(k < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void insert(int k){
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while(x != NIL){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }

    z->parent = y;
    if(y == NIL){
        root = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}

void inorder(Node *u){
    if(u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}
void preorder(Node *u){
    if(u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main(){
    int n, i, x;
    string com;

    scanf("%d", &n);

    for(i=0; i<n; i++){
        cin >> com;
        if(com[0] == 'f'){
            scanf("%d", &x);
            Node *t = find(root, x);
            if(t != NIL) printf("yes\n");
            else printf("no\n");
        }else if(com == "insert"){
            scanf("%d", &x);
            insert(x);
        }else if(com == "print"){
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


Measured memory_bytes: 22008
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
A = LIST()
print(sum(A)-max(A))


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

void solve() {
  int n, k;
  cin >> n >> k;
  double ans = 0;
  for(int i = 1; i <= n; i++) {
    int temp = i;
    int count = 0;
    while(temp < k) temp *= 2, count++;
    ans += (1.0/n * pow(0.5, count));
  }
  cout << fixed << setprecision(10) << ans << endl;
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 256
import sys
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Co = Counter(A)
Q = int(input())
BC = [list(map(int, sys.stdin.readline().split())) for i in range(Q)]
ans = sum(A)
for i in range(Q):
    B, C = BC[i]
    ans += ((C - B) * Co[B])
    print(ans)
    Co[C] += Co[B]
    Co[B] = 0

Measured memory_bytes: 39568
from collections import defaultdict as dd

n,m=map(int,input().split())
*a,=map(int,input().split())
dp=[-1]*(n+1)
ans = [0] * (n + 1)

cost={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

d={i:cost[i] for i in a}

dp[0] = 0
for i in range(1,n+1):
    for j in range(10)[::-1]:
        if not j in d:
            continue
        if cost[j] > i:
            continue
        if dp[i] < dp[i - cost[j]] + 1:
            dp[i] = dp[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = n

while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print(S)


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

int main(){
  double x[4], y[4];
  double xa, ya, xb, yb;
  char c;
  int checkConvex;
  int i;

  while(cin>>x[0]>>c>>y[0]){
    for(i=1; i<4; i++) cin>>c>>x[i]>>c>>y[i];

    checkConvex=0;
    for(i=1; i<=4; i++){
      xa=x[i-1]-x[i%4]; ya=y[i-1]-y[i%4];
      xb=x[(i+1)%4]-x[i%4]; yb=y[(i+1)%4]-y[i%4];
      if(xa*yb-ya*xb>0) checkConvex++;
      else checkConvex--;
    }
    if(checkConvex==4 || checkConvex==-4) printf("YES\n");
    else printf("NO\n");
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <array>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <utility>
#include <iomanip>
#include <numeric>
#include <climits>
#include <algorithm>
#include <cstdint>
using namespace std;

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

    if (d == 25)
        cout << "Christmas";
    else if (d == 24)
        cout << "Christmas Eve";
    else if (d == 23)
        cout << "Christmas Eve Eve";
    else cout << "Christmas Eve Eve Eve";
}

Measured memory_bytes: 3612
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]C - GeT AC
            var line = ReadLine();
            int n = line[0];
            int q = line[1];

            var s = Console.ReadLine();

            //1文字ごとに、その文字までに何個の"AC"があったかカウント
            var acs = CountAc(s, n).ToArray();

            //問題の数だけ繰り返し
            for(int i = 0; i < q; i++)
            {
                line = ReadLine();
                int left = line[0] - 2;
                int right = line[1] - 2;
                int count;

                if (left < 0)
                {
                    count = acs[right];
                }
                else
                {
                    count = acs[right] - acs[left];
                }

                Console.WriteLine(count);
            }
        }

        static IEnumerable<int> CountAc(string source, int n)
        {
            int count = 0;

            for (int i = 0; i < n - 1; i++)
            {
                string s = source.Substring(i, 2);

                if (s == "AC")
                {
                    count++;
                }

                yield return count;
            }
        }

        static List<int> ReadLine()
        {
            var line = Console.ReadLine();
            var array = line.Split(' ');

            return array.Select(x => int.Parse(x)).ToList();
        }
    }
}

Measured memory_bytes: 17592
N = gets.to_i
S = gets.chomp
Extend = lambda{|s| # ４種類チェックする必要があるかどうか。
	s << { # => 'xo'
		'SS'=>'WS',
		'SW'=>'SW',
		'WW'=>'WS',
		'WS'=>'SW'
	}[s[-2,2]][S[s.length-1].ord&1]
}
S << S[0]
puts (%w(SS SW WW WS).find{|s|
	N.times{
		Extend[s]
	}
	next s.chomp!(s[1]) && s.chomp!(s[0])
}||"-1")


Measured memory_bytes: 2684
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long



using namespace std;

void file(){
	#ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
	#endif
}
int tc;
const int N=2e5+5,M=2e6+5,MOD=1e9+7,OO=1e9;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//file();	
 	
 	string a,b;
 	int A,B;
 	cin>>a>>b;
 	cin>>A>>B;
 	string u;
 	cin>>u;

 	if(u==a){
 		cout<<A-1<<" "<<B<<"\n";
 	}
 	else	cout<<A<<" "<<B-1<<"\n";
 	
}		


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  for(int i=N;i<1000;i++){
    string s=to_string(i);
    if(s.at(0)==s.at(1) && s.at(1)==s.at(2)){
      int M=stoi(s);
      cout << M << endl;
      break;
    }
  }
  
}
    

Measured memory_bytes: 256
#include <bits/stdc++.h>  
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define forn(i,a,b)        for( i = a ; i < b  ; i++ )
#define debug(x)           cout << #x << " " << x << " -- "
#define I__O               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll                 long long  
#define p(x)               cout << x << "\n" ; 
#define MOD                100000007
#define pi                 pair<int,int>
#define vi                 vector <int>
#define pb                 push_back
#define vp                 vector <pair<ll,ll>>
#define endl               cout << "\n"
#define mi                 map <int,int> 
#define f1                 first 
#define s1                 second    
#define in                 insert
#define all(x)             (x).begin(),(x).end() 
/* 
  date | time : 3/22/2020 9:57:02 AM 
*/    
using namespace std ; 
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set ; 
const int N = 2e5+7;
bool ok(string S){
	// cout << S << ' ' ; 
	int N = S.size();
	int i = 0 ; 
	while( i < N/2){
		if(S[i] != S[N-i-1])
			return false ;
		i++;  
	}
	return true ; 		 
}  
int tests(){ 
	int i,n ;
	cin >> n ;
	map <int,int> m ; 
	vector <int> v(n,0) ;
	forn(i,0,n){
		cin >> v[i] ;
		m[v[i]]++ ; 
	}
	ll ans = 0 ;
	for(auto &x : m){
		int T = x.s1; 
		ans += (ll)T*(T-1)/2;
	} 
	forn(i,0,n){
		cout << ans-(ll)m[v[i]]+1 << '\n' ; 
	}
	return 0; 
} 
int main(){
    I__O ;          
    int cases = 1 ; 
    // cin >> cases ; 
    for(int i = 1 ; i <= cases ; i++ ){
      // cout << "Case #" << i << ": " ;  	
      tests(); 
    }
    return 0 ; 
}


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

#define   vt       vector
#define   ff       first
#define   ss       second
#define   int      long long
#define   db       long double
#define   pii      pair<int,int>
#define   Maxpq(x) priority_queue<x>
#define   Minpq(x) priority_queue<x,vt<x>,greater<x>>

#define   pb       push_back
#define   si(x)    (int)x.size()
#define   all(x)   x.begin(),x.end()
#define   mem(a,x) memset(a,x,sizeof(a))
#define   rep(n)    for(int i =0 ; i<n ; i++)
#define   forr(i,n) for(int i=0;i<n;i++)
#define   FOR(a)   for(auto& x :  a )

#define   pi       2*acos(0.0)
#define   inf      (int)1e18
const int mod =    1e9 + 7;
const int mxn =    2e5 + 5;

#define deb(x)   cout<<"> "<<#x<<" : "<<x<<endl;
#define deb2(x,y)cout<<"> "<<#x<<"->"<<x<<"  "<<#y<<"->"<<y<<endl;
#define LINE   cout << "--- LINE NO : " << __LINE__ <<"  ---"<< endl;
#define pnr(a)   FOR(a){cout<<x<<" ";}cout<<endl;
#define pnr2(a)  FOR(a){cout<<x.first<<" "<<x.second<<endl;}

const int dx4[4] = { -1, 0, 1, 0}, dy4[4] = {0, 1, 0, -1};
const int dx[2] = {1 , 0}, dy[2] = {0 , 1};

int mainx() {
    int n , m;
    cin >> n >> m;

    int in[n][m] , dp[n][m];
    mem(dp , 0);
    rep(n)
    {
        forr(j , m)
        {
            char c ; cin >> c;
            if (c == '.')in[i][j] = 0;
            else
                in[i][j] = 1;
        }
    }

    mem(dp , 0);
    int srt_x = 0 , str_y = 0;
    int bx = 0;
    forr(i , m)
    {
        if (in[0][i] == 1)
        {
            bx = 1;
        }
        if (bx)
            dp[0][i] = 0;
        else
            dp[0][i] = 1;
    }
    bx = 0;
    // deb(in[1][0]);
    forr(i , n)
    {
        if (in[i][0] == 1)
        {
            bx = 1;
        }
        if (bx)
            dp[i][0] = 0;
        else
            dp[i][0] = 1;
    }

    forr(i , n)
    {
        forr(j , m)
        {
            if (i == 0 or j == 0)
            {
                continue;
            }
            if (in[i][j]  == 0)
            {
                dp[i][j] = (dp[i - 1][j] ) % mod + (dp[i][j - 1]) % mod;
                dp[i][j] %= mod;
            }
            else
            {
                dp[i][j] = 0;
            }
        }
    }
    // forr(i , n)
    // {
    //     pnr(dp[i]);
    // }
    cout << (dp[n - 1][m - 1]) % mod << endl;





    return 0;
}


bool cmp(pii &a , pii &b) {
    if (a.ff < b.ff)return true;
    if (a.ff == b.ff )return a.ss < b.ss;
    return false;
}
inline void INCLUDE() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
//freopen("out.txt","w",stdout);
#endif
}
int32_t main() {

    // INCLUDE();

    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    //cout << fixed << setprecision(20);

    int tt = 1;
    //cin>>tt;
    for (int t = 1 ; t <= tt ; t++ )
    {
        // cout<<"Case #"<<t<<": ";
        mainx();
    }
    return 0 ;
}



Measured memory_bytes: 19188
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
if n==1:
    print(0)
    exit()

# N: 素因数分解する数
#リストで返す
res = []
x = n

y = 2
while y*y <= x:
    while x % y == 0:
        res.append(y)
        x //= y
    y += 1
if x > 1:
    res.append(x)



dic=Counter(res)
ans=0
#print(dic)
for i in dic:
    p=dic[i]
    #print(p)
    chk=0
    cnt=0
    for q in range(1,24):
        if chk+q<=p:
            cnt+=1
            chk+=q
        
        
    ans+=cnt
    #print(i,cnt,chk)
print(ans)


Measured memory_bytes: 10616
N, K = map(int, input().split())
S=input()
LS = [(S[i]) for i in range(N)]
if LS[K-1]== "A":
  LS[K-1]="a"
elif LS[K-1]=="B":
  LS[K-1]="b"
else:
  LS[K-1]="c"
S=''.join(LS)
print(S)

Measured memory_bytes: 3060
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    k = ni()
    s = ns()
    n = len(s)
    mod = 1000000007
    ans = 0
    inv25 = pow(25, mod-2, mod)
    tmp1 = 1
    tmp2 = pow(25,n+k,mod)
    for m in range(n):
        ans += (tmp1*tmp2)%mod
        ans %= mod
        tmp1 *= (n+k-m)*pow(m+1,mod-2,mod)
        tmp2 *= inv25
        tmp1 %= mod
        tmp2 %= mod
    ans = pow(26,n+k,mod) - ans
    ans %= mod
    print(ans)
    return


if __name__ == '__main__':
    main()

Measured memory_bytes: 75152