akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, a = 0; cin >> n;
  while(n--){
    int x; cin >> x; a += x&1;
  }
  if(a) cout << "first" << endl;
  else cout << "second" << endl;
  return 0;
}

Measured memory_bytes: 256
import os
import sys

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')


Measured memory_bytes: 129252
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int X,Y,Z; cin >> X >> Y >> Z;
  int tmp;
  tmp = Y; Y = X; X = tmp;
  tmp = Z; Z = X; X = tmp;
  printf("%d %d %d",X,Y,Z);
}

Measured memory_bytes: 3772
fun main(args: Array<String>) {
    abc133d()
}

fun abc133d() {
    val n = readLine()!!.toInt()
    val dams = readLine()!!.split(" ").map { it.toLong() }.toLongArray()

    val rains = LongArray(n) { 0 }

    val loop = fun(i: Int): Int {
        return when {
            i > n - 1 -> i - n
            i < 0 -> i + n
            else -> i
        }
    }

    rains[0] = 0
    var index = 2
    while (index != 0) {
        rains[loop(index)] = dams[loop(index - 1)] * 2 - dams[loop(index - 2)] * 2 + rains[loop(index - 2)]
        index = loop(index + 2)
    }

    index = 1
    while (index != n - 2) {
        rains[loop(index)] = dams[loop(index - 1)] * 2 - dams[loop(index - 2)] * 2 + rains[loop(index - 2)]
        index = loop(index + 2)
    }

    val add = (dams.sum() - rains.sum()) / n

    (0 until n).forEach { rains[it] += add }

    println(rains.joinToString(" "))
}


Measured memory_bytes: 78884
#include <bits/stdc++.h>    //super header :標準ライブラリ,STLを全てインクルード
using namespace std;

#define CIN2(a,b) long long a,b;cin >> a >> b; 
#define rep(i,n) for(int i=0,i##_len=(n); i<i##_len; ++i)

struct twin{
    long long a;
    long long b;
};

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1){}  //コントラクタ

    bool unionSet(int x, int y) {   //併合
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;    //統合後のroot(data[x])さえ更新すれば，findSetで後々更新できる
        }
        return x != y;
    }
    bool findSet(int x, int y) {    //同じグループか判定
        return root(x) == root(y);
    }
    int root(int x) {   
        return data[x] < 0 ? x : data[x] = root(data[x]);   //値を更新しつつハッシュを手繰る
    }
    int size(int x) {
        return -data[root(x)];
    }
};


int main(){
    CIN2(n,m)

    vector<twin> v;
    for(int i = 0;i < m;i++){
        CIN2(a,b)
        v.push_back({a-1,b-1}); 
    }

    vector<long long> dp(m+1,0);
    dp[0] = n*(n-1)/2;

    UnionFind h(n);

    reverse(v.begin(),v.end());
    for(int i=1;i<=m;++i){
        int a = v[i-1].a, b = v[i-1].b;
        if(h.findSet(a,b)){
            dp[i] = dp[i-1];
            //cout << dp[i] << "," << dp[i-1] << endl;
        }else{
            dp[i] = dp[i-1] - (long long)(h.size(a) * h.size(b));
            h.unionSet(a,b);
        }
    }

    for(int i=m-1;i>=0;--i){
        cout << dp[i] << endl;
    }
}


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

namespace ABC
{
    class ProgramB
    {
        static void Main(string[] args)
        {
            var a = long.Parse(Console.ReadLine());
            var b = long.Parse(Console.ReadLine());
            var c = long.Parse(Console.ReadLine());
            var x = long.Parse(Console.ReadLine());

            var result = 0;
            for (var i = 0; i <= a; i++)
            {
                for (var j = 0; j <= b; j++)
                {
                    for (var k = 0; k <= c; k++)
                    {
                        if (i * 500 + j * 100 + k * 50 == x)
                        {
                            result++;
                        }
                    }
                }
            }
            Console.WriteLine(result);
        }
    }
}


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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)

using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvb = vector<vb>;

constexpr int MOD = 1000000007;

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

    int r;
    cin >> r;
    cout << r * r << endl;

    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import collections


YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, Q: int, A: "List[int]"):
    cc = collections.Counter(A)
    for i in range(N):
        if Q - cc[i+1] < K:
            print(YES)
        else:
            print(NO)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, K, Q, A)


if __name__ == '__main__':
    main()


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

using namespace std;

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

	string A,B,C;

	cin >> A >> B >> C;

	if(A[A.length()-1]==B[0] && B[B.length()-1]==C[0])
	{
		cout << "YES" << '\n';
	}
	else
	{
		cout << "NO" << '\n';
	}

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
using namespace std;
typedef long long ll;
template <typename Monoid>
struct SegmentTree
{
    using F = function<Monoid(Monoid, Monoid)>;

    int sz;
    vector<Monoid> seg;

    const F f;
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1)
    {
        sz = 1;
        while (sz < n)
            sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid &x)
    {
        seg[k + sz] = x;
    }

    void build()
    {
        for (int k = sz - 1; k > 0; k--)
        {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    void update(int k, const Monoid &x)
    {
        k += sz;
        seg[k] = x;
        while (k >>= 1)
        {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    Monoid query(int a, int b)
    {
        Monoid L = M1, R = M1;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1)
        {
            if (a & 1)
                L = f(L, seg[a++]);
            if (b & 1)
                R = f(seg[--b], R);
        }
        return f(L, R);
    }

    Monoid operator[](const int &k) const
    {
        return seg[k + sz];
    }
};

ll f(ll a, ll b)
{
    return min(a, b);
}
int main()
{
    ll n, q;
    cin >> n >> q;
    SegmentTree<ll> seg(n + 1, f, (1LL<<31)-1);
    seg.build();
    for (ll i = 0; i < q; i++)
    {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0)
        {
            seg.update(x, y);
        }
        else
        {
            cout << seg.query(x, y+1) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4872
#include<iostream>
using namespace std;
int N;
string S;
int COUNT = 0;
int main() {
	cin >> N >> S;
	for (int i = 0; i < N - 2; i++) {
		if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') {
			COUNT++;
		}
	}
	cout << COUNT << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define REP(i,s,N) for (int i=s;i<(N); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

int main(){
	ll N;
	cin >> N;
	ll A[N],ans[N]={};
	REP(i,0,N){
		cin >> A[i];
        ans[A[i]-1] = i+1;
	}

    REP(i,0,N){
      cout << ans[i] << " ";
    }
  
	return 0;
}

Measured memory_bytes: 2432
#[allow(unused_imports)]
use std::io::{self, BufRead};
#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(dead_code)]
fn readln_to_vec<T>(buf: &mut BufRead) -> Vec<T> 
where T: std::str::FromStr,
      <T as std::str::FromStr>::Err: std::fmt::Debug
{
    let mut s = String::new();
    buf.read_line(&mut s).unwrap();
    s.split(" ")
        .map(|x| x.trim())
        .filter(|x| !x.is_empty())
        .filter_map(|x| x.parse().ok())
        .collect()
}

#[allow(dead_code)]
fn readln_to<T>(buf: &mut BufRead) -> T
where T: std::str::FromStr + std::clone::Clone,
      <T as std::str::FromStr>::Err: std::fmt::Debug
{
    readln_to_vec::<T>(buf)[0].clone()
}

#[allow(unused_macros)]
macro_rules! readln_to_tuple {
    (
        $bufRead: expr, ( $( $t: ty ),* )
    ) => (
        {
            let buf: &mut BufRead = $bufRead;
            let ln = readln_to_vec::<String>(buf);
            let mut i = ln.into_iter();
            ( $( i.next().unwrap().parse::<$t>().unwrap() ),* )
        }
        )
}

fn solve(t: i64, k: usize, n: usize, c: &Vec<i64>, s: &Vec<i64>, f: &Vec<i64>) -> i64 {
    if k == n-1 {
        t
    } else {
        if t < s[k] {
            solve(s[k] + c[k], k+1, n, c, s, f)
        } else {
            solve(((t + f[k]-1) / f[k]) * f[k] + c[k], k+1, n, c, s, f)
        }
    }
}


fn main() {
    let stdin = io::stdin();
    let mut stdin = stdin.lock();
    let stdin = &mut stdin;

    let n: usize = readln_to(stdin);

    let mut c = Vec::new();
    let mut s = Vec::new();
    let mut f = Vec::new();

    for _ in 0..n-1 {
        let (ci, si, fi) = readln_to_tuple!(stdin, (i64, i64, i64));
        c.push(ci);
        s.push(si);
        f.push(fi);
    }

    for i in 0..n {
        println!("{}", solve(0, i, n, &c, &s, &f));
    }
}





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

static const int MAX = 100000;

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

Node node[MAX];

void print_preorder(int i){
        cout<<" "<<i;
        if(node[i].left!=-1) print_preorder(node[i].left);
        if(node[i].right!=-1) print_preorder(node[i].right);

}

void print_inorder(int i){
        if(node[i].left!=-1) print_inorder(node[i].left);
        cout<<" "<<i;
        if(node[i].right!=-1) print_inorder(node[i].right);

}

void print_postorder(int i){
        if(node[i].left!=-1) print_postorder(node[i].left);
        if(node[i].right!=-1) print_postorder(node[i].right);
        cout<<" "<<i;

}

int main(){
        int n,a,tmp;
        cin>>n;
        for(int i=0;i<n;i++){
                node[i].parent = -1;
                node[i].left = -1;
                node[i].right = -1;
        }
        for(int i=0;i<n;i++){
                cin>>a;
                cin>>node[a].left;
                if(node[a].left!=-1) node[node[a].left].parent = a;
                cin>>node[a].right;
                if(node[a].right!=-1) node[node[a].right].parent = a;
        }
        tmp = 0;
        while(node[tmp].parent!=-1)
                tmp = node[tmp].parent;

        cout<<"Preorder"<<endl;
        print_preorder(tmp);
        cout<<endl;
        cout<<"Inorder"<<endl;
        print_inorder(tmp);
        cout<<endl;
        cout<<"Postorder"<<endl;
        print_postorder(tmp);
        cout<<endl;

        return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         cout<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define pw(b,p)         pow(b,p) + 0.1
#define endl            "\n"


 
void fastIO()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}


void solve()
{
    int n,k;
    cin>>k>>n;

    int ar[n];

    for(int i=0;i<n;i++)
        cin>>ar[i];

    sort(ar,ar+n);

    int m=-inf;

    for(int i=1;i<n;i++)
    {
        m=max(m,ar[i]-ar[i-1]);
    }
    m=max(m,k-ar[n-1]+ar[0]);

    cout<<k-m;
}
 
 
 
int32_t main()
{
    fastIO();
    //w(t)
    {
        solve();
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
"""
Created on Thu May  7 23:19:34 2020

@author: Kanaru Sato
"""
def dfs(v):
    global t
    d[v] = t
    t += 1
    if conlist[v]:
        for connectedv in conlist[v]:
            if d[connectedv] == -1:
                dfs(connectedv)
    f[v] = t
    t += 1

n = int(input())
conlist = [[] for i in range(n)]
for i in range(n):
    _ = list(map(int,input().split()))
    [conlist[i].append(_[k]-1) for k in range(2,_[1]+2)]

d = [-1 for i in range(n)]
f = [-1 for i in range(n)]
t = 1

for i in range(n):
    if d[i] == -1:
        dfs(i)    

for i in range(n):
    print(i+1,d[i],f[i])


Measured memory_bytes: 5672
using System;
using System.Collections.Generic;

namespace ProgramingTest
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string lines = System.Console.ReadLine();
            string costs = System.Console.ReadLine();

            string[] sn = lines.Split(' ');

            int N = int.Parse(sn[0]);
            int K = int.Parse(sn[1]);


            string[] sp = costs.Split(' ');

            //int[] n = new int[N];
            List<int> n = new List<int>();

            for (int i=0; i<N; i++)
            {
                n.Add(int.Parse(sp[i]));
                //Console.WriteLine(n[i]);
                //Console.WriteLine(sp[i]);

            }

            int minnumber = n[0];

            int sumnumber = 0;

            n.Sort();

            //for (int j=0; j<K; j++)
            //{
                for (int i = 0; i < K; i++)
                {
                //if (minnumber > n[i])
                //{
                //    minnumber = n[i];
                //    minBango = i;
                //}
                sumnumber += n[i];
                }

                //Console.WriteLine(sumnumber);

                //sumnumber += minnumber;
                //n.RemoveAt(minBango);
                //N -= 1;
                //Console.WriteLine(sumnumber);

            //}

            Console.WriteLine(sumnumber);






        }
    }
}


Measured memory_bytes: 27812
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>


using namespace std;
using ll = long long int;

#define rep(i, n) for(ll i = 0; i < (n); i++)
#define MOD 1000000007LL


ll pow(ll n, ll k) {
  ll r = 1;

  while (k > 0) {
    if (k % 2 == 1) {
      r = r * n % MOD;
    }
    n = n * n % MOD;
    k /= 2;
  }
  return r;
}

ll fac[3000000];

ll inv(ll x) {
  return pow(x, MOD - 2);
}


ll C(ll n, ll k) {
  if (k > 0) {
    return fac[n] * inv(fac[n - k]) % MOD * inv(fac[k]) % MOD;
  } else {
    return 1;
  }
}

void solve2(ll n, ll k) {
  ll sum = 0;
  vector<ll> a(k+1, -1);

  for (ll i = k; i >= 1; i--) {
    // i の倍数の数列は ceil(k/i)^n 個ある
    ll term = pow(k / i, n);

    // そのうち、gcd(A) = 2i, 3i ... となる場合の数を引く
    for (ll x = 2 * i; x <= k; x += i) {
      term = (term + MOD - a[x]) % MOD;
    }

    a[i] = term;
    sum = (sum + term * i) % MOD;
  }

  cout << sum << endl;
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  ll N, K;
  cin >> N >> K;

  fac[0] = 1;
  ll f = 1;
  for (ll i = 1; i < 3000000; i++) {
    f *= i;
    f %= MOD;
    fac[i] = f;
  }
  solve2(N, K);
  return 0;
}

Measured memory_bytes: 27456
main :: IO ()                                                                                                              
main = readLn >>= print . lucas 2 1                                                                                        
                                                                                                                           
lucas :: (Integral a) => a -> a -> a -> a                                                                                  
lucas a _ 0 = a                                                                                                            
lucas _ b 1 = b                                                                                                            
lucas a b n = lucas b (a+b) (n-1)

Measured memory_bytes: 508
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys
from collections import defaultdict


def solve(values, _nb, max_capacity):
    dp = {}
    dp[0] = 0
    for w, v in values:
        keys = sorted(dp.keys(), reverse=True)
        for vk in keys:
            if vk + v in dp:
                dp[vk + v] = min(dp[vk + v], dp[vk] + w)
            else:
                dp[vk + v] = dp[vk] + w
    result = 0
    for v, w in dp.items():
        if w <= max_capacity and v > result:
            result = v
    return result


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


INF = pow(10, 9) * 100


def solve_errichto(values, _nb, max_capacity):
    sum_values = sum(v for _w, v in values)
    # dp[i] min total weight of items with total value exactly i
    dp = [INF] * (sum_values + 1)
    dp[0] = 0
    for w, v in values:
        for value_already in range(sum_values - v, -1, -1):
            tmp = dp[value_already] + w
            if dp[value_already + v] > tmp:
                dp[value_already + v] = tmp
    result = 0
    for v, w in enumerate(dp):
        if w <= max_capacity:
            result = max(result, v)
    return result


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve_errichto(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


Measured memory_bytes: 9720
N=int(input())
A=list(map(int,input().split()))
c=0
m=A[0]
for i in range(len(A)-1):
  if m<A[i+1]:
    m=A[i+1]
  if m>A[i+1]:
    d=m-A[i+1]
    c+=d
print(c)

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

using namespace std;

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

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

vi mul(vi &b, vi &a){
	int x=a.size();
	vi c(x);
	iota(ALL(c), 0);
	REP(i, x){
		c[i]=b[a[i]];
	}
	return c;
}

vi power(vi &a, ll k){
	int x=a.size();
	vi b(x);
	iota(ALL(b), 0);
	while(k>0){
		if(k&1){
			b=mul(b, a);
		}
		a=mul(a, a);
		k>>=1;
	}
	return b;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	int n, x[125252], m, a[125252], d[125252];
	ll k;
	cin>>n;
	cin>>x[0];
	REP(i, n-1){
		cin>>x[i+1];
		d[i]=x[i+1]-x[i];
	}
	cin>>m>>k;
	vi nxt(n-1);
	iota(ALL(nxt), 0);
	REP(i, m){
		cin>>a[i];
		--a[i];
		swap(nxt[a[i]-1], nxt[a[i]]);
	}
	vi res=power(nxt, k);
	ll ans[125252];
	ans[0]=x[0];
	REP(i, n-1){
		ans[i+1]=ans[i]+d[res[i]];
	}
	REP(i, n){
		cout<<ans[i]<<'\n';
	}
	return 0;
}


Measured memory_bytes: 4456
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
for i in range(N):
  ans+=min(A[i]+A[i+1],B[i])
  if A[i]+A[i+1]>=B[i]:
    A[i+1]=min(A[i+1],A[i]+A[i+1]-B[i])
  else:
    A[i+1]=0
print(ans)


Measured memory_bytes: 24320
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PA;
typedef priority_queue<int, vector<int>, greater<int> > PQG;
#define REP(i, a, n) for(ll i = (ll) a;i < (ll) n;i++)
#define fi first
#define se second
#define pb push_back
#define INF 1000000009
#define MOD 1000000007
#define MAXN 502
#define MAXC 100000000000014
#define MAXV 1000000009

ll n, s[MAXN], c[MAXN], t[MAXN], f[MAXN];

int main()
{
    cin >> n;
    REP(i, 0, n - 1){
        cin >> c[i] >> s[i] >> f[i];
    }
    REP(i, 0, n - 1){
        t[i + 1] = s[i] + c[i];
        REP(j, i + 1, n - 1){
            if(t[j] > s[j]){
                t[j + 1] = ((t[j] - s[j] + f[j] - 1) / f[j]) * f[j] + s[j] + c[j];
            }
            else{
                t[j + 1] = s[j] + c[j];
            }
        }
        cout << t[n - 1] << endl;
    }
    cout << "0" << endl;

    return 0;
}
















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


int main(){
 
  
  string S,T;
  cin >> S >> T;
  T.pop_back();
  if(S.size()==T.size() && S==T){
    cout << "Yes" << endl;
    
  }else{
    cout << "No" << endl;
  }
  
  
}

Measured memory_bytes: 3628
#include <iostream>
using namespace std;
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(false)
int main()
{   string s;
cin>>s;
int ans=0;
string t;
cin>>t;
if(s[0]==t[0])
ans++;
if(s[1]==t[1])
ans++;
if(s[2]==t[2])
ans++;
 cout<<ans;
}

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

int main() {
  string s;
  cin >> s;

  string ans ="";

  for (int i = 0; i < s.length(); i++) {
    if(s[i] == '0'){
      ans += "0";
    }else if(s[i] == '1'){
      ans += "1";
    }else if(s[i] == 'B' && ans.length() != 0){
      ans.erase(ans.length() - 1);
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <queue>
using namespace std;
const int N=1000;
char maze[N][N];
int h,w,n;
int sx,sy,gx,gy;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int d[N][N];
const int INF=INT_MAX;
int ans;
struct node
{
    node(int xx=0,int yy=0,int tt=0,char ss=0):x(xx),y(yy),t(tt),s(ss){}
    int x;
    int y;
    int t;
    char s;
};
bool read()
{
    memset(maze,0,sizeof(maze));
    scanf("%d%d%d",&h,&w,&n);
    getchar();
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            scanf("%c",&maze[i][j]);
            if(maze[i][j]=='S') sx=j,sy=i;
            if(maze[i][j]=='0'+n) gy=i,gx=j;
        }
        getchar();
    }
    for(int i=0;i<h;i++)
       for(int j=0;j<w;j++) d[i][j]=INF;
    return 1;
}
void show()
{
    //printf("h:%d w:%d\n",h,w);
    //printf("maze[%d][%d]=%d\n",0,2,maze[0][2]);
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(d[i][j]!=INF) printf("%d ",d[i][j]);
            else printf("- ");
        }
        printf("\n");
    }
    //printf("sy:%d sx:%d\n",sy,sx);
}
void init(int h,int w)
{
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++) d[i][j]=INF;
}
int bfs()
{
   queue<node> que;
   que.push(node(sx,sy,0,'1'));
   d[sy][sx]=0;
   while(!que.empty())
   {

       node t=que.front();que.pop();
       //printf("%c\n",t.s);
       for(int i=0;i<4;i++)
       {
           int nx=t.x+dir[i][0];
           int ny=t.y+dir[i][1];
           if(0<=nx&&nx<w&&0<=ny&&ny<h&&d[ny][nx]==INF&&maze[ny][nx]!='X'/*(maze[ny][nx]=='.'||maze[ny][nx]==t.s)*/)
           {
               if(maze[ny][nx]=='0'+n&&maze[ny][nx]==t.s)
               {
                   //printf("%c in return",maze[ny][nx]);
                   return ans+=d[t.y][t.x]+1;
               }
               if(maze[ny][nx]==t.s)
               {
                   //printf("%c d\n",maze[ny][nx]);
                   maze[ny][nx]='.';
                    d[ny][nx]=d[t.y][t.x]+1;
                    ans+=d[ny][nx];
                    //show();
                    while(!que.empty()) que.pop();
                    init(h,w);
                    d[ny][nx]=0;
                   que.push(node(nx,ny,0,t.s+1));
                   break;
               }
               else
               {
                   que.push(node(nx,ny,0,t.s));
                    d[ny][nx]=d[t.y][t.x]+1;
               }
           }
       }
       //int size=que.size();
        //printf("size:%d\n",size);
   }
   return 1/*d[gy][gx]*/;
}
int main()
{
    while(~scanf("%d%d%d",&h,&w,&n))
    {
        getchar();
        memset(maze,0,sizeof(maze));
        ans=0;
        for(int i=0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                scanf("%c",&maze[i][j]);
                if(maze[i][j]=='S') sx=j,sy=i;
                if(maze[i][j]=='0'+n) gy=i,gx=j;
            }
            getchar();
        }
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++) d[i][j]=INF;
        bfs();
        printf("%d\n",ans);
    }
    return 0;
}

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

#define print2(a, b) cerr << "(" << a << "," << b << ")" << endl
#define print3(a, b, c) cerr << "(" << a << "," << b << "," << c << ")" << endl

const long long MOD = 1000000007;

ll dp[51][51][2501];
// dp[i][j][l]
// j:保留数
// l:確定距離(保留しているやつを使わずに一段進むごとに2*j増える感じ)

void ADD(ll& a, ll b) {
    a += (b % MOD);
    a %= MOD;
}

void solve(long long n, long long k){
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int l = 0; l <= k; l++) {
                ll& v = dp[i][j][l];
                // 1. つながない => 保留数++, 距離+=j*2
                if (j >= 1 && l >= j * 2)
                    ADD(v, dp[i-1][j-1][l-j*2]);
                // 2. お互いつなぐ => 保留数維持, 距離+=j*2
                if (l >= j * 2)
                    ADD(v, dp[i-1][j][l-j*2]);
                // 3. 左を保留とつなぐ => 保留数維持, 距離+=j*2
                // 4. 右 => 同様
                if (l >= j * 2)
                    ADD(v, 2 * j * dp[i-1][j][l-j*2]);
                // 5. 両方保留とつなぐ => 保留数--, 距離+=j*2
                if (j + 1 <= n && l >= j * 2)
                    ADD(v, (j+1) * (j+1) * dp[i-1][j+1][l-j*2]);
            }
        }
    }
    cout << dp[n][0][k] << endl;
}

int main(){
    long long n;
    scanf("%lld",&n);
    long long k;
    scanf("%lld",&k);
    solve(n, k);
    return 0;
}


Measured memory_bytes: 51200
n=int(input())
N=list(map(int,input().split()))
N_another=sorted(N)
count=0
if N==N_another:print("YES")
else:
    for i,j in enumerate(N):
        if j!=N_another[i]:
            count +=1
    if count>2:
        print("NO")
    else:
        print("YES")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(){
    cout << "Yes" << endl;
}

void no (){
    cout << "No" << endl;
}

ll cel (ll a, ll b){
    if (a % b == 0) return a / b;
    else return a / b + 1;
}

ll gcds(ll a, ll b){
    ll c = a % b;
    while (c != 0){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

int main() {
    int n; cin >> n;
    vector<vector<ll>> ar(n,vector<ll>(3));
    ll spa = 0LL;
    ll spb = 0LL;
    ll spc = 0LL;
    rep(i,n){
        cin >> ar[i][0] >> ar[i][1] >> ar[i][2];
        if (ar[i][2] > 0){
            spa = ar[i][0];
            spb = ar[i][1];
            spc = ar[i][2];
        }
    }
    ll ans = 0LL;
    rep(i,101){
        rep(j,101){
            bool t = true;
            ll h = spc + abs(spa-i) + abs(spb-j);
            rep(k,n){
                if (ar[k][2] != max(h-abs(ar[k][0]-i)-abs(ar[k][1]-j),0LL)){
                    t = false;
                    break;
                }
            }
            if (t){
                cout << i << " " << j << " " << h << endl;
                return 0;
            }
        }
    }
}

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

typedef long long ll;

const ll INF = 1e18;

ll n, a, ans;

ll get(ll k) {
	ll l = 0, r = n, res = INF;
	while (l <= r) {
		ll mid = l + r >> 1, cur = 1;
		if (mid < k) {
			l = mid + 1;
			continue;
		}
		for (ll i = 0; i < mid % k; i++) {
			if (mid / k + 1 > INF / cur) {
				cur = INF;
				break;
			}
			cur *= (mid / k + 1);
		}
		for (ll i = mid % k; i < k; i++) {
			if (mid / k > INF / cur) {
				cur = INF;
				break;
			}
			cur *= (mid / k);
		}
		if (cur >= n) {
			res = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	return res + (k - 1) * a;
}

int main() {
	cin >> n >> a;
	ans = INF;
	for (ll i = 1; i < 42; i++)
		ans = min(ans, get(i));
	cout << ans;
}


Measured memory_bytes: 3588
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String mozi = sc.next();
		StringBuilder ret = new StringBuilder();
		for (int i = 0; i < mozi.length(); i++){
			ret.append("x");
		}
		System.out.println(ret.toString());
	}
}	

Measured memory_bytes: 21716
#![allow(dead_code, unused_imports, non_snake_case)]

use std::io::*;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::str::FromStr;

const MOD: i32 = 1_000_000_007;

mod util {
    use std::fmt::Debug;
    use std::io::{stdin, stdout, BufWriter, StdoutLock};
    use std::str::FromStr;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn chars() -> Vec<char> {
        line().chars().collect()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
        where
            <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn with_bufwriter<F: FnOnce(BufWriter<StdoutLock>) -> ()>(f: F) {
        let out = stdout();
        let writer = BufWriter::new(out.lock());
        f(writer)
    }
}

macro_rules! max {($x:expr)=>{$x};($x:expr,$($xs:tt)+)=>{max($x,max!($($xs)+))};}
macro_rules! min {($x:expr)=>{$x};($x:expr,$($xs:tt)+)=>{min($x,min!($($xs)+))};}
macro_rules! get {($t:ty)=>{{let mut line:String=String::new();stdin().read_line(&mut line).unwrap();line.trim().parse::<$t>().unwrap()}};($($t:ty),*)=>{{let mut line:String=String::new();stdin().read_line(&mut line).unwrap();let mut iter=line.split_whitespace();($(iter.next().unwrap().parse::<$t>().unwrap(),)*)}};($t:ty;$n:expr)=>{(0..$n).map(|_|get!($t)).collect::<Vec<_>>()};($($t:ty),*;$n:expr)=>{(0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()};($t:ty;;)=>{{let mut line:String=String::new();stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()}};($t:ty;;$n:expr)=>{(0..$n).map(|_|get!($t;;)).collect::<Vec<_>>()};}
macro_rules! debug {($($a:expr),*)=>{eprintln!(concat!($(stringify!($a),"={:?},"),*),$($a),*);}}

fn main() {
    let (n, t) = get!(usize, usize);
    let ts = util::gets::<usize>();
    let mut ans = t;
    for i in 1..n {
        ans += min(t, ts[i] - ts[i - 1]);
    }
    println!("{}", ans);
}


Measured memory_bytes: 10492
# -*- coding: utf-8 -*-

import sys

for line in sys.stdin.readlines():
    List = map(int, line.strip().split())
    if len(List) == 1: continue
    List.sort()
    if(List[2]**2 == List[0]**2 + List[1]**2):
        print "YES"
    else:
        print "NO"

Measured memory_bytes: 4232
import qualified Data.ByteString.Char8 as BC
import Data.Maybe
import Data.List
import Data.Ord

readIntsLine :: IO [Int]
readIntsLine = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

readIntsLines :: IO [[Int]]
readIntsLines = map (map (fst . fromJust . BC.readInt) . BC.words) . BC.lines <$> BC.getContents

solve :: [Int] -> [(Int, Int)] -> [Int]
solve as [] = as
solve [] _ = []
solve (a:as) (bc:bcs) = res : solve as (nextbc ++ bcs)
  where (res, nextbc) = proc a bc

proc :: Int -> (Int, Int) -> (Int, [(Int, Int)])
proc a (b, c)
  | a >= c = (a, [(b, c)])
  | b == 1 = (c, [])
  | otherwise = (c, [(b - 1, c)])

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine :: IO [Int]
  as <- sort <$> readIntsLine
  let toTuple [a, b] = (a, b)
  bcs <- sortOn (Down . snd) . map toTuple <$> readIntsLines
  print . sum $ solve as bcs


Measured memory_bytes: 63356
import java.io.PrintWriter

val pw = PrintWriter(System.out)

fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    val n = nextInt()

    var min = Int.MAX_VALUE
    var sum = 0

    repeat(n) {
        val score = nextInt()
        if (score < min && score % 10 != 0) min = score
        sum += score
    }

    if (sum % 10 == 0) {
        println(if (min == Int.MAX_VALUE) 0 else sum-min)
    } else {
        println(sum)
    }
}

fun next() = readLine()!!
fun nextInt() = next().toInt()

fun println(value : Any) {
    pw.println(value)
}

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

int main(){
  int X,ans=0;
  cin >> X;
  rep(i,100){
    int num = 0;
    for(int j=2;j<=100;++j){
      num = pow(i,j);
      if(num<=X){
        ans = max(num,ans);
      }
    }
  }
  cout << ans << endl;
}


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

#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)

int main() {
	int sub = 0;
	string s, t,g;
	cin >> s >> t;
	int count = t.size();
	REP(i, s.size() - t.size() + 1) {
		g = s.substr(i, t.size());
		int target = 0;
		REP(i, count) {
			if (g[i] == t[i]) {
				target++;
			}
		}
		if (sub < target) {
			sub = target;
		}
	}
	cout << count - sub << endl;
	
}



Measured memory_bytes: 3612
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

	int N=in();
  vector<int> p(N);
	for(auto& x:p){
      x=in();
    }
  sort(ALL(p),greater<int>());
  p[0]/=2;
  
  cout << accumulate(ALL(p),0) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <cmath>
#include <cstdio>
#include <string>
#include <sstream>
#include <iomanip>

using namespace std;

double heron(double a, double b, double c) {
    double s = (a + b + c) / 2.0;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

int main() {
    double a, l, x;
    cout << setprecision(20);
    while(cin >> a >> l >> x) {
        cout << heron(l, l, a) + 2 * heron(l, (l + x) / 2.0, (l + x) / 2.0) << endl;
    }
    return 0;
}

Measured memory_bytes: 1284
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
using namespace std;


typedef long long ll;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)

const int mod = 1000000007;

int main(){
    int n, k;
    cin >> n >> k;
    vector<ll> v(n);
    rep(i, n){
        cin >> v[i];
    }

    ll ans = 0;
    for(int i = 0; i <= min(k, n); ++i){
        for(int j = 0; i + j <= min(k, n); ++j){
            vector<ll> value(n, 0);
            int cur = 0;
            ll sum = 0;


            for(int l = 0; l < i; ++l){
                value[cur] = v[l];
                cur++;
            }

            for(int l = 0; l < j; l++){
                value[cur] = v[n - l - 1];
                cur++;
            }

            cur = 0;
            if(i + j < k){
                sort(value.begin(), value.end());
                for(int l = i + j; l < k; ++l){
                    if(value[cur] >= 0) break;
                    value[cur] = 0;
                    cur++;
                }
            }


            rep(l, n)   sum += value[l];

            ans = max(ans, sum);

        }
    }

    cout << ans << endl;


}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sstream>

using namespace std;

int main(){
    unsigned int N;
    cin >> N;
    vector<int> a(N), b(N);
    for(int k = 0; k < N; k++){
        cin >> b[k];
    }
    bool isOK = true;

    int i, j;

    for(i = N - 1; i >= 0; i--){
        for(j = i; j >= 0; j--){
            if(b[j] == j + 1){
                a[i] = j + 1;
              	b.erase(b.begin() + j);
            	break;
            }
          	if(j == 0){
            	isOK = false;
            	break;
        	}
        }
        
    }
    if(isOK){
        for(i = 0; i < N; i++){
            cout << a[i] << endl;
        }
    }else{
        cout << -1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()
#define mat(type, row, col, init) vector<vector<type>>(row, vector<type>(col, init));

int main() {
	int a, b, c, x;
	cin >> a >> b >> c >> x;
	int cnt = 0;
	rep(i, a+1) {
		rep(j, b+1) {
			rep(k, c+1) {
				int v = i * 500 + j * 100 + k * 50;
				if (v == x)cnt++;
			}
		}
	}
	cout << cnt;

	return 0;
}





Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define For(i,n) rep(i,0,n)
#define int long long
const int INF=1e18;
const int MOD=1000000007;
typedef pair<int,int> P;
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int h,w;
    cin>>h>>w;
    char g[h][w];
    int dp[h][w];
    For(i,h){
        For(j,w){
            cin>>g[i][j];
            dp[i][j]=0;
        }
    }
    int x=0,y=0;
    while(x<h){
        if(g[x][0]=='.'){
            dp[x][0]=1;
            x++;
            }
        else{
            break;
            }
        }
    while(y<w){
        if(g[0][y]=='.'){
            dp[0][y]=1;
            y++;
            }
        else{
            break;
            }
    }
    rep(i,1,h){
        rep(j,1,w){
            if(g[i][j]!='#'){
                dp[i][j]+=(g[i-1][j]=='.'?dp[i-1][j]:0)+(g[i][j-1]=='.'?dp[i][j-1]:0);
                dp[i][j]%=MOD;
            }
        }
    }
    cout<<dp[h-1][w-1]<<endl;
    /*
    For(i,h){
        For(j,w){
            cout<<dp[i][j]<<' ';
        }
        cout<<endl;
    }
    */
    return 0;
}

Measured memory_bytes: 9088
#include<deque>
#include<stdint.h>
#include<set>
#include<stack>
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
vector<long long> g[100005],dd[100005];
long long n,m,i,j,dis[100005],x,y,z,k;
void dfs(long long x,long long fa)
{
	long long i;
	for (i=0;i<g[x].size();i++)
	{
		if (g[x][i]==fa) continue;
		dis[g[x][i]]= dis[x]+dd[x][i];
		dfs(g[x][i],x);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	 cin>>n;
	 for (i=1;i<n;i++) 
	 {
	 	cin>>x>>y>>z;
	 	g[x].push_back(y);
	 	g[y].push_back(x);
	 	dd[x].push_back(z);
	 	dd[y].push_back(z);
	 }
	 cin>>m>>k;
	 dfs(k,0);
	 while (m--)
	 {
	 	cin>>x>>y;
		 cout<<dis[x]+dis[y]<<endl;
	}
	return 0;
}

Measured memory_bytes: 20480
N, Y = map(int, input().split())
 
for x in range(N+1):
    for y in range(N+1):
        if 10000*x + 5000*y + 1000*(N-(x+y)) == Y and N-(x+y) >= 0:
            print(x, y, N-(x+y))
            exit()
 
print(-1,-1,-1)

Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;

int main() {

int i,j,k,x,y,z,n;

cin >> n;

vector<vector<int> > a(n,vector<int>(4));

for(i=0;i<=n-1;++i){
for(j=0;j<=3;++j){
cin >> a.at(i).at(j);
}
}

for(k=1;k<=4;++k){

for(x=1;x<=3;++x){
for(y=1;y<=10;++y){

z=0;
for(i=0;i<=n-1;++i){
if(a.at(i).at(0)==k && a.at(i).at(1)==x && a.at(i).at(2)==y){
z+=a.at(i).at(3);
}
}

cout << " " << z ;

}

cout << endl;

if(x==3){
if(k<4){
cout << "####################" << endl;
}
}

}

}

}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
static const int INF (1<<30);

int main() {
  int x[5], y[5], vx, vy;
  cin >> x[1] >> y[1] >> x[2] >> y[2];

  vx = x[2] - x[1];
  vy = y[2] - y[1];

  x[3] = -vy + x[2];
  y[3] = vx + y[2];
  
  x[4] = -vy + x[1];
  y[4] = vx + y[1];

  cout << x[3] << " " << y[3] << " ";
  cout << x[4] << " " << y[4] << endl;

  return 0;
}

Measured memory_bytes: 256
//14:07:00 

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin>>n;
	vector<int> v(n);
	for(auto &i:v) {cin>>i; i--;}
	set<int> app;
	int now=0,cnt=0;
	while(now!=1)
	{
		if(app.count(now))
		{
			cout<<"-1\n";
			return 0;
		}
		app.insert(now);
		now=v[now];
		cnt++;
	}
	cout<<cnt<<"\n";
	return 0;
}











Measured memory_bytes: 5760
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
using ll = long long;

int main(){
    int n;
    cin >> n;
    cout << (int)pow(2,(int)log2(n)) << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

n = input()
A = map(int, raw_input().split())

for i in range(len(A)):
    A[i] -= i + 1

A.sort()
mid = A[n / 2]
print sum(abs(num - mid) for num in A)


Measured memory_bytes: 20264
def mod_inv(a, MOD):
    """ 前提: aとMODが互いに素であること """
    b = MOD
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        u -= t * v
        a, b = b, a
        u, v = v, u
    u %= MOD
    return u


def prime_factorize(n):
    i = 2
    res = {}
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        res[i] = 0
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res


def solve(n):
    pf = prime_factorize(n)
    l = len(pf)
    pfk = []
    for i, p in enumerate(pf):
        pfk.append(p ** pf[p])

    ans = 10 ** 18

    for bit in range(1 << l):
        a = 1
        for d in range(l):
            if bit & (1 << d):
                a *= pfk[d]
        b = n // a

        if a == 1:
            k = n - 1
        elif b == 1:
            k = n
        else:
            m = mod_inv(b, a)
            k = b * m - 1
        # print(a, b, m, k)

        if k > 0 and k * (k + 1) // 2 % n == 0:
            ans = min(ans, k)
        else:
            ans = min(ans, k + n)

    return ans


n = int(input())
ans = solve(n)
print(ans)

# import random
#
# for n in range(1, 10000):
#     a = solve(n)
#     i = -1
#     for i in range(1, 2 * n + 1):
#         if i * (i + 1) // 2 % n == 0:
#             break
#     # print(n, a, i)
#     assert a == i


Measured memory_bytes: 68300