akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
using P = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef vector<ll> vi;
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
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; }

int main(){
  ll x, a, b;
  cin >> x >> a >> b;
  print((x - a) % b);
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            long n = in.nextLong(), k = in.nextLong();
            long ans = 0;
            if (k == 0) {
                out.println(n * n);
                return;
            }
            for (long i = k + 1; i < n; i++) {
                ans += (i - k) * ((n - 1) / i);
                long tm = i * ((n + i - 1) / i) - n;
                if (tm <= (i - k)) {
                    ans += (i - k) - tm + 1;
                    if (tm == 0) {
                        ans--;
                    }
                }
            }
            out.println((ans + n - k));
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 19540
H, W = map(int, raw_input().split())
c = [map(int, raw_input().split()) for _ in range(10)]
A = [map(int, raw_input().split()) for _ in range(H)]

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k]+c[k][j])

print sum(sum(c[a][1] if a >= 0 else 0 for a in aa) for aa in A)


Measured memory_bytes: 2948
color = input()

even = color[::2]
odd = color[1::2]

# 0 start
count1 = even.count('0') + odd.count('1')

# 1 start
count2 = even.count('1') + odd.count('0')

if (count1 < count2):
    print(count1)
else:
    print(count2)

Measured memory_bytes: 3188
from collections import deque
N=int(input())
A=[0 for i in range(N-1)]
B=[0 for i in range(N-1)]
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[i],B[i]=a,b
    G[a].append(b)
    G[b].append(a)
j=0
for i in range(N):
    if len(G[i])>len(G[j]):
        j=i
c=sorted([int(i) for i in input().split()])
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.appendleft(p)
M=0
for i in range(N-1):
    M+=min(d[A[i]],d[B[i]])
print(M)
print(" ".join([str(i) for i in d]))


Measured memory_bytes: 50520
#include <iostream>
#include <string>

using namespace std;

int main(){
    int n;
    string s;
    cin>>n;
    cin>>s;
    int i;
    int x=0;
    int max=0;

    for(i=0;i<n;i++){
        if(s[i]=='I') x++;
        else x--;

        if(max<x) max=x;
    }
    cout<<max<<endl;
    return 0;
}

Measured memory_bytes: 256
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	N := getInt()
	a := getInts(N)

	sum := 1
	odd := 1
	for i := 0; i < N; i++ {
		sum *= 3
		if a[i]%2 == 0 {
			odd *= 2
		} else {
			odd *= 1
		}
	}
	out(sum - odd)
}


Measured memory_bytes: 1776
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin>>s;
    cin>>t;
    long long int n=s.length(),i,c=0;
    for(i=0;i<n;i++)
    {
        if(s[i]!=t[i])
        c++;
    }
    cout<<c<<endl;
}

Measured memory_bytes: 3888
#include<iostream>
#include<string>
 
using namespace std;
 
int main(){
    int n,m;
	int a[11000],b[11000];
	int c[1000],d[1000];
	while(true){
	int count=0;
	cin>>n>>m;
	if(n==0&&m==0)
		break;
	for(int i=1;i<n+1;i++){
		c[i]=0;
		d[i]=0;
	}
	for(int i=0;i<m;i++){
		cin>>a[i]>>b[i];
		if(a[i]==1)
			c[b[i]]=1;
	}
	for(int i=0;i<m;i++){
		if(c[a[i]]==1)
			d[b[i]]=1;
		if(c[b[i]]==1)
			d[a[i]]=1;
	}
	d[1]=0;
	for(int i=1;i<n+1;i++){
		if(c[i]==1)
			d[i]=1;
		count+=d[i];
	}
	cout<<count<<endl;
	}
    return 0;
}

Measured memory_bytes: 1252
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 5
cnt = [0 for _ in range(M)]

for i in A:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    
    j = i
    while j < M:
        cnt[j] += 1
        j += i
ans = 0
for i in A:
    if cnt[i] == 1:
        ans += 1
print(ans)


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

int main(){
  ll K,N;
  cin >> K >> N;
  vector<ll> A(N);
  for(ll i=0;i<N;i++){
    cin >> A.at(i);
  }
  
  ll max_diff=0;
  
  for(int i=0;i<N;i++){
    ll tmp = ( A.at( (i+1)%N) - A.at(i) ) % K;
    if(tmp < 0){
      tmp += K;
    }
    if(tmp > max_diff){
      max_diff = tmp;
    }
  }
  
  cout << K - max_diff << endl;
  
  return(0);
}


Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
using namespace std;

const double pi = acos(-1);

typedef long long ll;
const int maxn = 2005;
struct pp{
    ll v;
    int id;
    bool operator<( const pp &o )const{
        if( v != o.v )return v > o.v;
        return id < o.id;
    }
};
pp A[maxn];
int mark[maxn];
ll dp[maxn][maxn];

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    #ifdef acm
    freopen("a.in","r",stdin);
    #endif // acm

    int n;
    cin >> n;

    for( int i = 1; i <= n; i++ )
        cin >> A[i].v, A[i].id = i;

    sort(A+1, A+n+1);

    for( int i = 0; i <= n; i++ )
        for( int j = 0; j <= n; j++ )
            dp[i][j] = -1;

    dp[0][0] = 0;

    ll sol = 0;
    for( int i = 0; i <= n; i++ ){
        for( int j = 0; j <= n; j++ ){
            if( i + j > n )continue;
            if( dp[i][j] == -1 )continue;
            int t = i+j+1;
            int ini = i+1;
            int fin = n-j;
            dp[i+1][j] = max( dp[i+1][j], dp[i][j] + abs(A[t].id - ini) * A[t].v );
            dp[i][j+1] = max( dp[i][j+1], dp[i][j] + abs(A[t].id - fin) * A[t].v );
        }
    }

    for( int i = 0; i <= n; i++ )
        sol = max(sol, dp[i][n-i]);

    cout << sol << "\n";

    return 0;
}


Measured memory_bytes: 35000
#include <iostream>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;

void solve(std::string S){
    bool ans = true;
    string tmp;
    if (S.size() == 4) tmp = S.substr(2, 1);
    else tmp = S.substr(2, S.size() - 3);
    int countC = 0;
    REP(i, tmp.size())
        if (tmp[i] == 'C') countC++;
    if (S[0] != 'A') ans = false;
    else if (countC != 1) ans = false;
    else {
        S.erase(0, 1);
        S.erase(S.find("C"), 1);
        REP(i, S.size())
            if (!(islower(S[i]))) ans = false;
    }

    if (ans) cout << "AC" << '\n';
    else cout << "WA" << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
# -*- coding:utf-8 -*-
h , w = map(int, input().split())
pic = []

for i in range(h):
    temp = input()
    pic.append(temp)

li = '#' * (w+2)

print(li)

for j in range(h):
    temp = '#' + pic[j] + '#'
    print(temp)

print(li)


if __name__ == '__main__':
    pass

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#include<vector>
int main()
{
    ll a,b,i,k,l;
    cin>>a>>b>>k;
   l=b-a+1;
   ll kk=k;
   if(k<=(l/2))
   {
       while(kk--)
       {
           cout<<a++<<endl;
       }
       a+=(l- 2*k);
       while(k--)
       {
           cout<<a++<<endl;
       }
   }
   else
   {
       for(i=a;i<=b;i++)
       {
           cout<<i<<endl;
       }
   }
    return 0;
}


Measured memory_bytes: 256
time = input()
judge = [''] * 1000

for i in range(time):
	data = map(int, raw_input().split())
	[a, b, c] = sorted(data)
	if a ** 2 + b ** 2 == c ** 2:
		judge[i] = 'YES'
	else:
		judge[i] = 'NO'
	
for j in range(i+1):
	print judge[j]


Measured memory_bytes: 4252
import sys
input = sys.stdin.readline

N = int(input())
X = [int(x) for x in input().split()]
X.sort()
ans = 10 ** 10

for i in range(X[0], X[-1] + 1):
    tmp = 0
    for j in X:
        tmp += (i - j) ** 2
    ans = min(ans, tmp)

print(ans)

Measured memory_bytes: 38896
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    auto a = vector<int>(n);

    auto denied = false;
    for (auto &a_i : a) {
        cin >> a_i;
        if (a_i % 2 != 0)
            continue;
        if (a_i % 3 == 0)
            continue;
        if (a_i % 5 == 0)
            continue;
        denied = true;
    }

    cout << (denied ? "DENIED" : "APPROVED");
    return 0;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappop, heappush

n, m = li()
a = list(li())

heap = []

for ai in a:
    heappush(heap, -ai)

for _ in range(m):
    bi = -heappop(heap)
    heappush(heap, -(bi//2))

print(-sum(heap))


Measured memory_bytes: 14380
def gcd(x, y):
    if x<y:x,y=y,x
    while x % y != 0:
        x, y = y, x % y
    return y
n=int(input())
l=[int(input()) for i in range(n)]
ans=l[0]
for i in l[1:]:
    ans=ans*i//gcd(ans,i)
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
                     
#define int             long long
#define ld              long double
#define mp              make_pair
#define ff              first
#define ss              second
#define pb              push_back
#define fo(i,n)         for(i=0;i<n;i++)
#define fo1(i,n)        for(i=1;i<=n;i++)
#define FO(i,k,n)       for(i=k;k<=n?i<=n:i>=n;k<=n?i++:i--)
#define all(c)          c.begin(),c.end()
#define rall(c)         c.rbegin(),c.rend()
#define si              set<int>
#define vi              vector<int>
#define mii             map<int,int>
#define pii             pair<int,int>
#define vpii            vector<pii>
#define vvi             vector<vi>
#define usi             unordered_set<int>
#define umii            unordered_map<int,int>
#define pqmx            priority_queue<int>
#define pqmn            priority_queue<int,vi,greater<int> >
#define sp(x)           cout<<setprecision(x)<<fixed;
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)     __builtin_ctzll(x)
#define in(a,n)         vi a(n);fo(i,n)cin>>a[i];
#define in1(a,n)        vi a(n+1);fo1(i,n)cin>>a[i];
#define w(t)            int t;cin>>t;while(t--)
#define sz(v)           (int)v.size()
#define gcd             __gcd
#define lcm(x,y)        x*(y/gcd(x,y))
#define endl            '\n'
#define PI              3.14159265358979323846
const int inf =         1e18;
const int mod =         1e9+7;
void __p(int x) {cout<<x;}
void __p(int32_t x){cout<<x;}
void __p(float x){cout<<x;}
void __p(double x){cout<<x;}
void __p(ld x) {cout<<x;}
void __p(char x){cout <<'\''<<x<<'\'';}
void __p(const char *x){cout <<'\"' <<x<<'\"';}
void __p(const string &x) {cout<<'\"'<<x<<'\"';}
void __p(bool x) {cout<<(x?"true":"false");}
void _p() {cout << "]\n";}
template<typename T,typename V>     void __p(const pair<T,V> &x) {cout<<'{';__p(x.first);cout<<',';__p(x.second);cout<<'}';}
template<typename T>                void __p(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __p(i); cout << "}";}
template <typename T,typename... V> void _p(T t, V... v) {__p(t);if(sizeof...(v))cout<<", ";_p(v...);}
int po(int x,int p,int m = inf) {int ans=1;x%=m;while(p>0){if(p&1)ans=(ans*x)%m;p=p>>1;x=(x*x)%m;}return ans;}
int inv(int x,int m=mod){return po(x,m-2,m)%m;}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout<<"["<<#x<<"]=[";_p(x)
#else 
#define dbg(x...)
#endif
//=================================================================================




const int N=1e6+6;
int n,m,k,x,y,z,a,b,c,d,i,j,l,r,f;








void sol()
{   
    cin>>n;
    x=log2(n);
    y=po(2,x+1);
    
    
    
    
    cout<<y -1 <<endl;
}





int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //sp(10);
    // w(t)
    sol();
    return 0;
}

Measured memory_bytes: 3816
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
	ll N,K;
	string s;
	cin>>N>>K;
	cin>>s;
	for(ll i=0;i<N;i++){
		if(i==K-1) printf("%c",tolower(s[i]));
		else cout<<s[i];
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){

int x=0,y=0,z=0;
int A[2001] = {};
int i=0,j=0;

scanf("%d", &x);

for(i=0;i<x;i++){

scanf("%d", &y);

A[0] =1;

for(j=2000; j >=0; j--){
if(A[j] && j+y < 2001){
A[j+y] =1;

}

}

}

scanf("%d", &z);

for(i=0;i<z; i++){
scanf("%d", &y);
if(A[y]){
printf("yes\n");
}
else
printf("no\n");
}
return 0;
}

Measured memory_bytes: 1812
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 5;
const ll MOD = 1e9 + 7;
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pis pair<ll,string>
#define F first
#define S second
#define LCM(a,b) ((a*b)/__gcd(a,b))
#define inf 1e15
#define test ll cse;cin>>cse;for(ll _i=1;_i<=cse;_i++)
#define PI 3.14159265
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const double EPS = 1E-9;
typedef vector< vector<double> > matrix;
typedef vector<int> vi;


int main() {
    fast;
    string s;

    cin >> s;

    ll sum = 0;
    for(char &ch: s) sum += (ch - '0');


    if(sum % 9 == 0)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

Measured memory_bytes: 3676
#include<bits/stdc++.h>
using namespace std;
#define int long long int

int a1[1000001]={0};
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout<<setprecision(9)<<fixed;
	
	int n;
	cin>>n;
	int a[n];
	map<int,int> m;
	set<int> s;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		m[a[i]]++;
		s.insert(a[i]);
	}
	while(!s.empty())
	{
		int t1=*s.begin();
		s.erase(s.begin());
		for(int i=2*t1;i<=1000000;i+=t1)
			a1[i]=1;
	}
	int c=0;
	for(int i=0;i<n;i++)
	{
		if(m[a[i]]==1 && a1[a[i]]==0)
			c++;
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 34704
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define y1 y1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;

template<class Abel> struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<Abel> diff_weight;

  UnionFind(int n = 1, Abel SUM_UNITY = 0) {
    init(n, SUM_UNITY);
  }

  void init(int n = 1, Abel SUM_UNITY = 0) {
    par.resize(n); rank.resize(n); diff_weight.resize(n);
    for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
  }

  int root(int x) {
    if (par[x] == x) {
      return x;
    }
    else {
      int r = root(par[x]);
      diff_weight[x] += diff_weight[par[x]];
      return par[x] = r;
    }
  }

  Abel weight(int x) {
    root(x);
    return diff_weight[x];
  }

  bool issame(int x, int y) {
    return root(x) == root(y);
  }

  bool merge(int x, int y, Abel w) {
    w += weight(x); w -= weight(y);
    x = root(x); y = root(y);
    if (x == y) return false;
    if (rank[x] < rank[y]) swap(x, y), w = -w;
    if (rank[x] == rank[y]) ++rank[x];
    par[y] = x;
    diff_weight[y] = w;
    return true;
  }

  Abel diff(int x, int y) {
    return weight(y) - weight(x);
  }
};


// Driver program
void Main(){

  int N,M;

  cin>>N>>M;

  UnionFind<int> uf(N);

  bool ok=true;

  rep(i,M){
    int l,r,d;
    cin>>l>>r>>d;
    --l; --r;

    if(uf.issame(l,r)){
      if(uf.diff(l,r)!=d) ok=false;
    }
    else{
      uf.merge(l,r,d);
    }
  }

  cout<< ( ok ? "Yes" : "No" )<<"\n";
}


//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


Measured memory_bytes: 1408
///   ***   ---   |||		 In the name of ALLAH		|||   ---   ***   ///



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


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {			cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}

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


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

ll mypow ( int a, int b )
{
	ll ret = 1;
	for ( int i = 0; i < b; i++ ) {
		ret *= a;
	}

	return ret;
}

int main()
{
	optimize();

	#ifndef ONLINE_JUDGE
		file()
	#endif

	ll n;
	cin >> n;

	int cnt = 1e5, c;

	for ( int i = 1; i < cnt; i++ ) {
		if ( n - mypow ( 26, i ) > 0 ) n -= ( mypow ( 26, i ) );
		else {
			c = i;
			break;
		}
	}

n--;
	dbg(n);
	string s;
	while ( n > 0 ) {
		int d = n % 26;
		s += ( d + 'a' );
		n /= 26;
	}


	reverse ( all ( s ) );

	while ( sz(s) < c ) s = 'a' + s;

	cout << s << endl;

	return 0;
}



















Measured memory_bytes: 3628
#include <iostream>
#include <vector>
using namespace std;
int main()
{
  int N;
  cin >> N;
  vector <int> V(N), C(N);
  for (int i = 0; i < N; i++) cin >> V[i];
  for (int i = 0; i < N; i++) cin >> C[i];
  
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (V[i]>C[i]) ans += (V[i]-C[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
use proconio::*;
use std::cmp::max;
use std::collections::BinaryHeap;

#[fastout]
fn main() {
    input! {
        d: usize,
        c: [i64; 26],
        s: [[i64; 26]; d],
    };

    let mut lasts = [-1; 26];
    let mut t = vec![26; d];
    let depth = 28;
    for i in 0..d {
        let mut max_score = -10000000;
        for j in 0..26 {
            let tmp = search(i, j, &c, &s, &mut lasts, depth, d, 0, 6);
            if tmp > max_score {
                max_score = tmp;
                t[i] = j;
            }
        }
        lasts[t[i]] = i as i64;
    }

    for &a in &t {
        println!("{}", a + 1);
    }
}

fn calc_score(i: usize, j: usize, c: &Vec<i64>, s: &Vec<Vec<i64>>, lasts: &mut [i64; 26]) -> i64 {
    let mut res = s[i][j];
    let tmp = lasts[j];
    lasts[j] = i as i64;

    for j in 0..26 {
        let i = i as i64;
        let last = lasts[j];
        res -= c[j] * (i - last);
    }

    lasts[j] = tmp;
    res
}

fn search(
    i: usize,
    t: usize,
    c: &Vec<i64>,
    s: &Vec<Vec<i64>>,
    lasts: &mut [i64; 26],
    depth: usize,
    d: usize,
    cscore: i64,
    l: usize,
) -> i64 {
    if depth == 0 || i == d - 1 {
        return calc_score(i, t, &c, &s, lasts) + cscore;
    }

    let l = max(1, l - 1);
    let mut max_score = -1000000;
    let tmp_last = lasts[t];
    lasts[t] = i as i64;
    let tmp_score = calc_score(i, t, &c, &s, lasts);
    let mut cands = BinaryHeap::new();
    cands.reserve(26);
    for j in 0..26 {
        let tmp_score = calc_score(i + 1, j, &c, &s, lasts);
        cands.push((tmp_score, j));
    }
    let w = if l > 1 { 2 } else { 1 };
    for &(_, j) in cands.iter().take(w) {
        let tmp = search(i + 1, j, &c, &s, lasts, depth - 1, d, cscore + tmp_score, l);

        if tmp > max_score {
            max_score = tmp;
        }
    }

    lasts[t] = tmp_last;
    max_score + cscore
}


Measured memory_bytes: 2268
# -*- coding: utf-8 -*-
# abc143/abc143_b
import sys
from itertools import combinations

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    d = i2nn()
    print(sum(a*b for a, b in combinations(d, 2)))
main()


Measured memory_bytes: 3064
n = int(input())
spans = []

for _ in range(n):
    x, l = map(int, input().split())
    spans.append((x-l, x+l))
spans = sorted(spans, key=lambda x:x[1])

ans = 0
cur_end_time = -float("inf")

for st, en in spans:
    if cur_end_time > st:
        continue
    ans += 1
    cur_end_time = en
print(ans)




Measured memory_bytes: 19016
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector<long long >where;
int n, k, a, b;
long long solve(long long start , long long end){
    long long  r = upper_bound(where.begin(), where.end(), end)-where.begin();
    long long l = lower_bound(where.begin(), where.end(), start)-where.begin();
    
    long long  aveng = r - l;
   
    if(start == end){
        if(aveng)return 1 * aveng * b;
        return a;
    }
    
    
    long long ch1 ;
    if(aveng)
    ch1 = (end - start + 1) * aveng * b;
    else return  a;
   
    long long ch2 = solve(start, (end + start)/ 2) + (solve((end + start)/ 2 + 1, end));
    

    return min(ch1, ch2);
    
}
int main(void){
 double n,c;
 cin >> n >> c;
 double x,y;
 int cnt = 0;
 while(n--){
     cin >> x >> y;
     double dis = x * x + y * y;
     dis = sqrt(dis);
     if(dis <= c)cnt++;
 }
 cout << cnt;
}

Measured memory_bytes: 3840
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;
constexpr ll INV2 = (MOD + 1) / 2;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

struct State {
    ll a, b, c;
    State(ll x, ll y, ll z) : a(x), b(y), c(z) {}
    State operator+(const State &x) const { 
        return { a * x.a % MOD,
            (a * x.b + b * x.a) % MOD,
            (a * x.c + b * x.b + b * x.c + c * x.a + c * x.b + c * x.c) % MOD };
    }
    void operator+=(const State &x) { *this = *this + x; }
    void adjust() { 
        (a += c) % MOD;
        c = 0; 
    }
};

ll N;
vector<vector<ll>> edges;
vector<deque<State>> deques;
void dp(ll u) {
    ll max_size = 0;
    for (ll i : edges[u]) {
        dp(i);
        if (deques[i].size() > deques[u].size()) {
            swap(deques[i], deques[u]);
        }
        max_size = max(max_size, (ll)deques[i].size());
        for (ll j = 0; j < (ll)deques[i].size(); j++) {
            deques[u][j] += deques[i][j];
        }
        deques[i].clear();
    }
    deques[u].push_front({ INV2, INV2, 0 });
    for (ll i = 0; i <= max_size; i++) {
        deques[u][i].adjust();
    }
}

int main()
{
    cin >> N;
    edges.resize(N + 1);
    deques.resize(N + 1);
    for (ll i = 1; i <= N; i++) {
        ll p;
        cin >> p;
        edges[p].push_back(i);
    }
    dp(0);
    ll ans = 0;
    for (auto i : deques[0]) {
        (ans += i.b) %= MOD;
    }
    printf("%lld\n", ans * MODpow(2, N + 1) % MOD);
}

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

int main(){

  int X,k,ans=1;
  cin >> X;
  bool judge=false;

  for(int i=X; i>2; i--){
    for(int j=2; j<i; j++){
      if(i%j==0){
        k = i;
        while(k%j==0){
          k /= j;
          if(k==1){
            judge = true;
            ans = i;
            break;
          }else if(k==0){
            break;
          }
        }
      }
      if(judge) break;
    }
    if(judge) break;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int X = sc.nextInt();
		int count = 0;
		for (int i = 0; i <= A; i++) {
			for (int j = 0; j <= B; j++) {
				for (int k = 0; k <= C; k++) {
					if (X == (500 * i + 100 * j + 50 * k)) {
						count++;
					}
				}
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 23764
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;
use itertools::Itertools;

fn main() {
    let a: String = read!();
    let v = a.chars().collect_vec();
    let mut b:usize=0;
    for i in 0..v.len() {
        if i==0 {
            if v[i]=='A' {
                b+=1;
            }
        }
        else {
            if v[i]=='C' {
                if i==1 || i==v.len()-1{
                    println!("WA");
                    exit(0);
                }
                b+=2;
            }
            else if v[i]==v[i].to_ascii_uppercase() {
                println!("WA");
                exit(0);
            }
        }
    }
    if b==3 {
        println!("AC");
    }
    else {
        println!("WA")
    }
}

Measured memory_bytes: 2136
n = int(input())

list_w = list(map(int,input().split()))

def didived(list_w):
    result = 99999
    for i in range(len(list_w)-1):
        S1 = list_w[0:i+1]
        S2 = list_w[i+1:]
        sum_s1 = sum(S1)
        sum_s2 = sum(S2)
        tmp = abs(sum_s1-sum_s2)
        if result > tmp:
            result = tmp

    return result


answer = didived(list_w)
print(answer)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int n, m;
  cin >> n >> m;
  ll ans = m*(m-1)/2 + n*(n-1)/2;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define all(a) begin(a),end(a)
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define sz(x) ((int)x.size())
#define ins insert
#define rep(i,l,u) for(int i=l;i<=u;++i)
#define reb(i,l,u) for(int i=l;i>=u;--i)
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
const int inf=1e18;
main(){
    int n,m;
    cin>>m>>n;
    map<int,int>ma;
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        ma[x]=1;
    }
    for(int i=0;i<=100;++i){
        if(ma[m-i]==0){
            cout<<m-i<<endl;
            break;
        }else if(ma[m+i]==0){
            cout<<m+i<<endl;
            break;
        }
    }
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b)
{
	ll res=1;
	a%=mod;
	assert(b>=0);
	for(;b;b>>=1)
	{
	if(b&1)
	    res=res*a%mod;
	a=a*a%mod;
	}return res;
}
// head
 
const int N=101000;
int n,x[N],l,q,p[N][22],u,v;
int main() {
	scanf("%d",&n);
	rep(i,0,n) scanf("%d",x+i);
	scanf("%d",&l);
	for(int i=0;i<n;i++)
	{
		p[i][0]=upper_bound(x,x+n,x[i]+l)-x-1;
	} 
	rep(j,1,20) rep(i,0,n) p[i][j]=p[p[i][j-1]][j-1];
	scanf("%d",&q);
	rep(i,0,q) {
		scanf("%d%d",&u,&v);
		--u; --v; if (u>v) swap(u,v);
		int r=0;
		per(j,0,20) if (p[u][j]<v) {
			u=p[u][j],r+=(1<<j);
		}
		printf("%d\n",r+1);
	}
}

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

int main() {
  int N;
  cin >> N;
  int ans;
  if (1<=N&&N<=9){
    ans = N;
  } else if(10<=N&&N<=99){
    ans = 9;
  } else if(100<=N&&N<=999){
    ans = N-99+9;
  } else if(1000<=N&&N<=9999){
    ans = 909;
  } else if(10000<=N&&N<=99999){
    ans = N-9999+909;
  } else if(N>=100000){
    ans = 90909;
  }
  cout << ans << endl;
    
  return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> H(N);
  for(int i = 0; i < N; i++) {
    cin >> H.at(i);
  }
  sort(H.begin(), H.end());
  if(K >= N) {
    cout << 0 << endl;
  }
  else {
    int64_t ans = 0;
    for(int i = 0; i < N - K; i++) {
      ans += H.at(i);
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) c.begin(),c.end()
#define tr(c,i) for(i = c.begin(); i != c.end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e;++i)
#define forsn(i,s,e) for(int i = s; i < e;++i)
#define rforn(i,s) for(int i = s; i >= 0;--i)
#define rforsn(i,s,e) for(int i = s; i >= e;--i)
# define INF 0x3f3f3f3f 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM=1e5+5,MOD=1e9+7;

int main()
{
    ll i,j,k,m,n;
    cin>>n;
    v64 h(n);
    forn(i,n)
        cin>>h[i];
    ll dp[n+5];
    forn(i,n)
    {
        if(i==0)
            dp[i]=0;
        else if(i==1)
            dp[i]=dp[i-1]+abs(h[i]-h[i-1]);
        else
        {
            dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
        }
    }
    cout<<dp[n-1];
}

Measured memory_bytes: 4724
#include <bits/stdc++.h>
#define LOWBIT(x) (x&(-x))
#define MOD(x) (((x)%Mod+Mod)%Mod)
#define sp putchar(' ')
#define en putchar('\n')
const int MAXN = 2000005 ;
using namespace std ;
using VI = vector<int64_t> ;
int64_t n, m, T, u, v, a, b ,phi, Mod = 998244353;

int64_t powEx(int64_t base ,int64_t n, int64_t Mod) {
    int64_t ret = 1 ;
    while(n) {
        if(n & 1) {
            ret = ret * base % Mod ;
        }
        base = base * base % Mod ;
        n >>= 1 ;
    }
    return ret % Mod ;
}

int64_t euler(int64_t n)
{
       int64_t ret(n),x(n);
       for(int64_t i(2);i*i<=x;i++){
           if(x%i==0){
               ret=ret/i*(i-1);
               while(x%i==0) x/=i;
           }
       }
      if(x>1) ret=ret/x*(x-1);
      return ret;
}

int64_t f(int64_t a,int64_t i) {
    if (__gcd(a, m) == 1) {
        return powEx(a, powEx(2, i, phi), m) ;
    } else {
        if (pow(2.0, i) < phi) {
            return powEx(a, 1LL << i, m) ;
        } else {
            return powEx(a, powEx(2, i, phi) + phi, m) ;
        }
    }
}

int64_t solve(int64_t x, int64_t n)
{
    if(n == 1) return (x*x)%m ;
    int64_t mid = n >> 1 ;
    return (solve(x, mid) + solve(f(x, mid) , n - mid)) ;
}

class BIT
{
static const int MAXN = 2000005 ;
public:
    int64_t T[MAXN] ;

    void clear(int n) {
        memset(T,0,sizeof(T)) ;
    }

    void add(int pos, int64_t d) {
        for(int i = pos; i < MAXN; i+=LOWBIT(i)) {
            T[i] = (T[i] + d)%Mod ;
        }
    }

    int64_t Q(int pos) {
        if(pos == 0) return 0 ;
        int64_t ans = 0 ;
        for(int i = pos;i > 0; i -= LOWBIT(i)) {
            ans = (ans + T[i])%Mod ;
        }
        return ans ;
    }

    int64_t Q(int l, int r) {
        int64_t ans = Q(r);
        ans = MOD(ans - Q(l - 1)) ;
        return ans ;
    }

}bit;

int L[20],R[20] ;

int main()
{

    ios::sync_with_stdio(false) ;
//    while(cin >> n >> a >> m) {
//        phi = euler(m) ;
//        cout << f(a, n) << endl;
//    }
    while(cin >> n >> m) {
       bit.clear(n + 5) ;
       for(int i = 1;i <= m; ++ i) {
            cin >> L[i] >> R[i] ;
       }
       bit.add(1,1) ;
       for(int i = 1;i <= n; ++ i) {
//            cout << "i == "<< i << endl;
            for(int j = 1;j <= m; ++j) {
                int l = i - R[j], r = i - L[j] ;
                l = max(1, l) ;
//                cout <<"\t l == " << l <<", r == "<< r << endl ;
                if(r < 1) continue ;
                int64_t sum = bit.Q(l,r) ;
//                cout << "\tsum["<<l<<","<<r<<"] == " << sum << endl ;
                bit.add(i,sum) ;
            }
       }
       cout << bit.Q(n,n) << endl ;
    }
}


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

using namespace std;

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

    return 0;
}


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

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

template<class T> inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
struct Unionfind {
    vector<int> par;

    Unionfind(int n) : par(n) {
        for(int i = 0; i < n; ++i) par[i] = i;
    }

    int root(int x) {
        if(par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if(rx == ry) return;
        par[rx] =ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

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

    int n;
    cin >> n;

    const int num = 1000000;
    vector<int> cnt(num+1, 0);
    vector<int> a(n);

    rep(i, n) {
        cin >> a[i];
        if(cnt[a[i]] != 0) {
            cnt[a[i]] = 10;
            continue;
        }
        for(int j = a[i]; j <= num; j += a[i]) ++cnt[j];
    }

    int ans = 0;
    rep(i, n) {
        if(cnt[a[i]] == 1) ++ans;
    }
    cout << ans << endl;
    return 0;
}

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

vector<vector<char>> v_input_mine(int h, int w) {
  vector<vector<char>> v(h + 2, vector<char>(w + 2));
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> v.at(i).at(j);
      char dot = '.';
    }
  }
  return v;
}

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> V = v_input_mine(H, W); 
  vector<vector<int>> NUM(H + 2, vector<int>(W + 2, 0));
  char mine = '#';
  
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (V.at(i).at(j) == mine) {
        NUM.at(i).at(j) = -1;
        for (int m = i - 1; m <= i + 1; m++) {
          for (int n = j - 1; n <= j + 1; n++) {
            if (V.at(m).at(n) != mine) {
              NUM.at(m).at(n)++;
            }
          }
        }
      }
    }
  }
  
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (NUM.at(i).at(j) == -1) {
        cout << '#';
      }
      else {
        cout << NUM.at(i).at(j);
      }
    }
    cout << endl;
  }
}


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

#define pb push_back
#define F first
#define S second

#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define int long long
#define ll long long

const int N = 2e3 + 5, M = 1e9 + 7;
int dp[N][N];
	
void solve(){
	int n, m;
	cin >> n >> m;
	string s[n];
	for(int i = 0 ; i < n ; i++){
		cin >> s[i];		
	}
	dp[1][0] = 1;	
	for(int i = 1 ; i <= n ; i++){	
		for(int j = 1 ; j <= m ; j++){
			if(s[i - 1][j - 1] == '#')
				continue;
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % M;
		}
	}
	cout << dp[n][m] ;
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	//cin >> t;
	while(t--)
		solve();
	return 0;
}

Measured memory_bytes: 17152
r, c = map(int, input().split())
listA = []
for i in range(r):
	listA.append(list(map(int, input().split())))
	listA[i].append(sum(listA[i]))
temp = []
for  i in range(c+1):
    number = 0
    for j in range(r):
        number += listA[j][i]
    temp.append(number)
# s = 0
# for i in range(r):
#     for j in range(c):
#         s += listA[i][j]
# temp.append(s)
listA.append(temp)

for line in listA:
    print(*line)


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

int main() {
  string S;
  cin >> S;
  if (S.at(0)==S.at(1) && S.at(1)!=S.at(2) && S.at(2)==S.at(3)) {
    cout << "Yes" << endl;
  }
  else if (S.at(0)!=S.at(1) && S.at(0)==S.at(2) && S.at(1)==S.at(3)) {
    cout << "Yes" << endl;
  }
  else if (S.at(0)!=S.at(1) && S.at(0)==S.at(3) && S.at(1)==S.at(2)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; i++) cin >> A[i];
  
  int 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[j] == A[k] || A[i] == A[k]) continue;
        vector<int> B = {A[i], A[j], A[k]};
        sort(B.begin(), B.end());
        if (B[0] + B[1] > B[2]) {
          ans++;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define Rep(n) for (ll _ = 0; _ < (ll)(n); _++) 
#define fs first
#define sc second
#define _GLIBCXX_DEBUG

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min(a,(ll)b);}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

const double PI = 3.1415926535897932384;

// 1次元vectorの出力
template <class S>
void print(vector<S> &v){for(ll i=0; i<(ll)v.size(); i++){
		cerr << v[i] << ' ';
	}
	cerr << endl;
}

// 2次元vectorの出力
template <class S>
void print(vector<vector<S>> &v) {
  	for (ll i = 0; i < (ll)v.size(); i++) {
    	for (ll j = 0; j < (ll)v[i].size(); j++) {
      		cerr << v[i][j] << ' ';
    	}
    	cerr << endl;
  	}
}

int main(void){
	int a,b,c,d; cin >> a >> b >> c >> d;
	int tak = ceil(c/(double)b);
	int aok = ceil(a/(double)d);
	cout << ((tak > aok) ? "No" : "Yes") << endl;
}

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

int main()
{
    int x,a,b;
    cin>>x>>a>>b;
    if(b<=a)
        cout<<"delicious"<<endl;
    if(b>a && b<=x+a)
        cout<<"safe"<<endl;
    if(b>x+a)
        cout<<"dangerous"<<endl;

    return 0;
}

Measured memory_bytes: 3596
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;

char z[3]={'r','b','g'};

int Unzip(string s){
  int ans=0;
  for(int i=0;i<s.size();i++){
    ans*=3;
    for(int j=0;j<3;j++){
      if(s[i]==z[j])ans+=j;
    }
  }
  return ans;
}
char Other(char a,char b){
  for(int i=0;i<3;i++){
    if(z[i]!=a&&z[i]!=b)return z[i];
  }
  return '#';
}

int dis[60000];
queue<pair<string,int> >Q;
int main(){
  string s;
  while(cin>>s&&s!="0"){
    lol(i,60000)dis[i]=mod;
    Q.push(make_pair(s,0));
    while(!Q.empty()){
      string x=Q.front().first;
      int len=Q.front().second;
      Q.pop();
      int index=Unzip(x);
      if(dis[index]<=len)continue;
      dis[index]=len;
      for(int i=0;i<x.size()-1;i++){
	if(x[i]!=x[i+1]){
	  string news=x;
	  news[i]=Other(x[i],x[i+1]);
	  news[i+1]=Other(x[i],x[i+1]);
	  Q.push(make_pair(news,len+1));
	}
      }
    }
    int ans=mod;
    for(int i=0;i<3;i++){
      for(int j=0;j<s.size();j++)s[j]=z[i];
      int index=Unzip(s);
      ans=min(ans,dis[index]);
    }
    if(ans==mod)cout<<"NA"<<endl;
    else cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 4268
n,a,b,k=map(int,input().split())
mod=998244353
factorial=[1]
for i in range(1,n+1):
    factorial.append(factorial[i-1]*i%mod)
inverse=[0]*(n+1)
inverse[-1]=pow(factorial[-1],mod-2,mod)
for i in range(n-1,-1,-1):
    inverse[i]=inverse[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod
ans=0
for i in range(n+1):
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
        ans+=comb(n,i)*comb(n,j)
        ans%=mod
print(ans)

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

using namespace	std;

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

    char a[100][100];
    for( int i = 0; i <	H; ++i ){
        for( int j = 0;	j < W; ++j ){
            cin >> a[i][j];
	}
    }

    for( int i = 0; i < H+2; ++i ){
        for( int j = 0;	j < W+2; ++j ){
            if(	i == 0 || i == H+1 || j == 0 || j == W+1 ) cout	<< "#";
            else cout << a[i-1][j-1];
        }
        cout <<	endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		int N = sc.nextInt();

		int a = N;
		int fx = 0;
		while(a>=10) {
			fx += a % 10;
			a /= 10;
		}
		fx += a;

		System.out.print(N%fx==0 ? "Yes" : "No");

	}
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
const ll MOD =1e9+7;
///modulo version
ll binpow(ll a,ll b) {
if (b == 0)return 1;ll res = binpow(a, b / 2)%MOD;
if (b % 2)return ((res%MOD * res%MOD)%MOD * a%MOD)%MOD;else return (res%MOD * res%MOD)%MOD;}

ll inv(ll A)
{
    return binpow(A,MOD-2);
}
//modulo arithmetic
inline ll add(ll a, ll b)
{
	ll res = a + b;
	if(res >= MOD)
		return res - MOD;
	return res;
}

inline ll mult(ll a, ll b)
{
	ll  res = a;
	res *= b;
	if(res >= MOD)
		return res % MOD;
	return res;
}

inline ll sub(ll a, ll b)
{
	return (a%MOD-b%MOD+MOD)%MOD;
}
ll f[200001];

ll ncr(ll n,ll r)
{

	return mult(f[n],mult(inv(f[n-r]),inv(f[r])));
}

int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
 	f[0]=1;
 	for(ll i=1;i<=200000;i++)
 	{
 		f[i]=mult(f[i-1],i);
 	}
 	ll n,k;
 	cin>>n>>k;
 	ll ans=0;
 	//no of zeros
 	for(ll i=0;i<n;i++)
 	{
 		ll moves = i;
 		if(moves>k)continue;
 		ans=add(ans,mult(ncr(n,i), max(1LL,ncr(i+n-i-1,i) )   ));
 	}
 	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792