akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<int,int> P;
const ll mod=1e9+7;

int n;
vector<int> g[10010];
vector<int> d(10010);

void dfs(int dep,vector<bool>& used,priority_queue<int>& c){
  if(used[dep]) return;
  used[dep]=true;
  for(auto itr:g[dep]){
    if(used[itr]) continue;
    d[itr]=c.top();
    c.pop();
    dfs(itr,used,c);
  }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    rep(i,n-1){
      int a,b;
      cin>>a>>b;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    priority_queue<int> c;
    ll ans=0;
    rep(i,n){
      int x;
      cin>>x;
      ans+=x;
      c.push(x);
    }
    ans-=c.top();
    vector<bool> used1(n+1,false);
    d[1]=c.top();
    c.pop();
    dfs(1,used1,c);
    cout<<ans<<endl;
    FOR(i,1,n+1){
      cout<<d[i]<<' ';
    }
    cout<<endl;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
int n,flag,x;
int main(){
	cin >> n ;
	flag = 0;
	for ( int i = 1 ; i <=  n; i ++ ){
		cin >> x ;
		if (x%2 == 0)
		if (x%3!=0&&x%5!=0) flag = 1;
	}
	if(flag) cout<<"DENIED"<<endl;
	else cout<<"APPROVED"<<endl;
	return 0;
}

Measured memory_bytes: 3608
import math

x = input()
x = x.split()

l = int(x[0])
r = int(x[1])

if l % 2019 > r % 2019 or r-l >= 2018:
  print("0")
  exit()


else:
  min = 2019
  for i in range(l,r+1):
    for j in range(i+1,r+1):
    	if (i*j)%2019 < min:
          min = (i*j)%2019
  print(min)

Measured memory_bytes: 3060
# abc142_c.py
# https://atcoder.jp/contests/abc142/tasks/abc142_c

# C - Go to School /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 高橋くんは N人の生徒たちのいるクラスの担当教師です。
# 生徒たちには 1から Nまでの出席番号が重複なく割り当てられています。
# 今日は全ての生徒たちが相異なるタイミングで登校しました。
# 高橋くんは、出席番号 iの生徒が登校した時点で、教室に Ai 人の生徒たちがいたことを記録しています(出席番号 iの生徒を含む)。
# 記録された情報を元に、生徒たちの登校した順番を復元してください。

# 制約
#     1≤N≤105
#     1≤Ai≤N
#     Ai≠Aj
#     (i≠j)
#     入力はすべて整数

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N
# A1 A2 … AN

# 出力
# 生徒たちの出席番号を登校した順に出力せよ。

# 入力例 1
# 3
# 2 3 1

# 出力例 1
# 3 1 2

# 最初に出席番号 3の生徒が登校しました。
# 続いて出席番号 1の生徒が登校しました。
# 最後に出席番号 2の生徒が登校しました。

# 入力例 2
# 5
# 1 2 3 4 5

# 出力例 2
# 1 2 3 4 5

# 入力例 3
# 8
# 8 2 7 3 4 5 6 1

# 出力例 3
# 8 2 4 5 6 7 3 1


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    N = int(lines[0])
    # N, M = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    lst = [0] * N

    for n in range(N):
        lst[values[n]-1] = str(n+1)

    return [' '.join(lst)]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3', '2 3 1']
        lines_export = ['3 1 2']
    if pattern == 2:
        lines_input = ['5', '1 2 3 4 5']
        lines_export = ['1 2 3 4 5']
    if pattern == 3:
        lines_input = ['8', '8 2 7 3 4 5 6 1']
        lines_export = ['8 2 4 5 6 7 3 1']
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 21152
fun main(args: Array<String>) = println(run {
    val n = readLine()!!.toInt()
    val s = (1..n).map { readLine()!! }
    val m = readLine()!!.toInt()
    val t = (1..m).map { readLine()!! }

    val b = s.groupBy { it }.mapValues { it.value.size }
    val r = t.groupBy { it }.mapValues { it.value.size }

    b.map { it.value - r.getOrElse(it.key) { 0 } }.filter { it>0 }.max()?:0

})


Measured memory_bytes: 33792
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(abs(a - b) <= d && abs(b - c) <= d || abs(a - c) <= d) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int K;
    cin >> K;
    ++K;

    ll ans = 0;

    FOR(a, 1, K) FOR(b, 1, K) FOR(c, 1, K) {
        ans += gcd(gcd(a, b), c);
    }

    cout << ans << endl;
    
}


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


n, d, a = map(int, input().split())
fox = [list(map(int, input().split())) for _ in range(n)]

fox.sort()

sub = [0]*(n+1)

def bisect(x):
    l, r = 0, n
    while r-l > 1:
        k = (r+l)//2
        if fox[k][0] <= x:
            l = k
        else:
            r = k
    if fox[l][0] <= x:
        return l
    return r


def main():
    ans = 0
    
    for i in range(n):
        if i != 0:
            sub[i] += sub[i-1]
        if fox[i][1]-a*sub[i] <= 0:
            continue
        count = (fox[i][1]-sub[i]*a-1)//a+1
        ans += count
        sub[i] += count
        sub[bisect(fox[i][0]+2*d)+1] -= count

    print(ans)

    
if __name__ == "__main__":
    main()


Measured memory_bytes: 53448
#include<iostream>
using namespace std;
int main(){
  	int i,n;
  	cin >> n;
  	string s,t;
  	cin >> s;
  	cin >> t;
  	for(i=0;i<n;i++){
    	cout << s[i] << t[i];
    }
  	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int n,hx,hy,dx,dy;
int cx[20],cy[20],flag[20];

int check(int c,double rsum,int hx,int hy){
    int i;
    double r;
    if(c==n)return 1;
    for(i=0;i<n;i++){
        if(flag[i]==0){
            r=rsum+sqrt((hx-cx[i])*(hx-cx[i])+(hy-cy[i])*(hy-cy[i]));
            if(r+1e-8>sqrt((dx-cx[i])*(dx-cx[i])+(dy-cy[i])*(dy-cy[i])))return 0;
        }
    }
    for(i=0;i<n;i++){
        if(flag[i]==0){
            flag[i]=1;
            r=rsum+sqrt((hx-cx[i])*(hx-cx[i])+(hy-cy[i])*(hy-cy[i]));
            if(check(c+1,r,cx[i],cy[i])==0)flag[i]=0;
            else return 2;
        }
    }
    return 0;
}

int main(void){
    int i;
    while(1){
        scanf("%d %d %d %d %d",&n,&hx,&hy,&dx,&dy);
        if(n==0 && hx==0 && hy==0 && dx==0 && dy==0)break;
        for(i=0;i<n;i++){
            scanf("%d %d",&cx[i],&cy[i]);
            flag[i]=0;
        }
        if(check(0,0.0,hx,hy)==2)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 584
//Code by Mukul Totla
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void sublime(){  
    freopen ("input.txt", "r", stdin);
    freopen ("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); }

int main()
{   
   // sublime();
    ll n;
    cin>>n;
    ll ans=0,i=0;

    while(n>0)
    {
        if(n==1)
        {
            n--;
            ans+=1LL<<i;
        }
        else if(n!=1)
        {
            n/=2;
            ans+=1LL<<i;
            i++;
        }
    }
    cout<<ans;
    
    return 0;
}

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

typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> ii;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll, ll>> vii;
typedef long double ld;
typedef vector<ld> vld;
typedef vector<vector<ld>> vvld;
typedef vector<bool> vbl;
typedef vector<vbl> mbl;
const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    __uint128_t a = 1;
    long long temp;
    int n;
    cin >> n;
    bool flag = false;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        if (temp == 0)
        {
            cout << 0 << endl;
            return 0;
        }
        a *= temp;
        if (a > 1000000000000000000)
        {
            flag = true;
        }
    }
    a = (a<<64)>>64;
    if (flag)
        cout << -1 << endl;
    else
        cout << (long long)a << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
int main(){
	std::vector<int> a(5);
	int k;
	for(int i=0;i<5;i++)
		scanf("%d", &a[i]);
	scanf("%d", &k);
	bool flag=false;
	for(int i=0;i<5;i++){
		for(int j=i+1;j<5;j++){
			if(abs(a[j]-a[i])>k){
				flag=true;
				break;
			}
		}
	}
	if(!flag)
		std::cout<<"Yay!\n";
	else std::cout<<":(\n";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int n,m;
  scanf("%d %d",&n,&m);
  int ans=0;
  
  int max;
  
  ans=n+m;
  max=ans;
  
  ans=n-m;
  if(max<ans){
    max=ans;
  }
  ans=n*m;
  
  if(max<ans){
    max=ans;
  }
  
  printf("%d\n",max);
  
  return 0;
}

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

const int N = 3007;
double a[N], dp[N][N];

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lf", &a[i]);
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        dp[i][0] = dp[i - 1][0] * (1 - a[i]);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i < j) break;
            dp[i][j] = (dp[i - 1][j - 1] * a[i] + dp[i - 1][j] * (1 - a[i]));
        }
    }
    double ans = 0.0;
    for(int i = 1; i <= n; i++){
        if(i * 2 > n ){
            ans += dp[n][i];
        }
    }
    printf("%.10lf\n", ans);
}

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

typedef long long ll;
typedef unsigned long long ull;
#define endl "\n";
#define FASTER ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define POSITIVE_INFINITY 9223372036854775807
#define NEGATIVE_INFINITY -9223372036854775807
const ll MOD = 1000000007;
const int N = 1005;
string ar[N + 2];
ll dp[N][N];

ll F(int x, int y){
  if (x == 0 && y == 0){
    return 1;
  }
  if (x < 0 || y < 0)
    return 0;
  if (ar[x][y] == '#')
    return 0;
  if (dp[x][y] != -1)
    return dp[x][y];
  ll r1 = F(x - 1, y);
  ll r2 = F(x, y - 1);
  return dp[x][y] = (r1 % MOD + r2 % MOD) % MOD;
}

int main()
{
  FASTER;
  memset(dp, -1, sizeof dp);
  int x, y;
  cin >> x >> y;
  for (int i = 0; i < x; i++){
    cin >> ar[i];
  }
  cout << F(x - 1, y - 1) << endl;
  return 0;
}


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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int k,a,b,hoge,ans;

main() {
    cin >> k >> a >> b;
    hoge = b-a;
    if (hoge > 1) ct(((k-a+1)/2)*hoge+(k-a+1)%2+a)
    else ct(k+1)
}


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

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

ll N;
vector<ll> A;
// vectorのリサイズ
// A.resize(N);

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

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

  set<int> s;
  rep(i, 3){
    int a;
    std::cin >> a;
    s.insert(a);
  }
  if (s.size()==2) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
package main

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

var sc *bufio.Scanner

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

func main() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	for {
		a, b := nextInt(), nextInt()
		if a == 0 && b == 0 {
			break
		}
		for i := 0; i < a; i++ {
			for j := 0; j < b; j++ {
				if (i+j)%2 == 0 {
					fmt.Print("#")
				} else {
					fmt.Print(".")
				}
			}
			fmt.Print("\n")
		}
		fmt.Print("\n")
	}
}



Measured memory_bytes: 1092
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
ll opt=INT_MIN;
int q;
vector<vector<ll> > cost;
void fun(int taken,vector<int> a,int n,int m,int curr)
{
	if(taken==n)
	{
		ll mycost=0;
		for(int i=0;i<q;i++)
		{
			if(a[cost[i][1]]-a[cost[i][0]]==cost[i][2])
				mycost+=cost[i][3];

		}

		opt=max(opt,mycost);
		return;
	}

	for(int i=curr;i<=m;i++)
	{
		a.push_back(i);
		fun(taken+1,a,n,m,i);
		a.pop_back();
	}

}



int main()
{
	int n,m;
	cin>>n>>m>>q;

	cost.resize(q,vector<ll>(4));

	for(int i=0;i<q;i++)
	{
		cin>>cost[i][0]>>cost[i][1]>>cost[i][2]>>cost[i][3];
		cost[i][0]--;
		cost[i][1]--;
	}


	 vector<int> a;

	fun(0,a,n,m,1);


	 cout<<opt<<endl;

	return 0;
}

Measured memory_bytes: 3640
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();
        long K = sc.nextLong();

        if (A >= K) {
            A = A - K;
            K = 0;
        } else {
            K = K - A;
            A = 0;
        }
        if (B >= K) {
            B = B - K;
        } else {
            K = K - B;
            B = 0;
        }

        System.out.println(A + " " + B);
    }
}

Measured memory_bytes: 22996
N = gets.chomp.to_i
nums = gets.chomp.split(" ").map(&:to_i)
output_str = ""
nums.length.times do |i|
    if i >= 1
        i.times do |j|
            if nums[j] > nums[i]
                nums[i],nums[j] = nums[j],nums[i]
            end
        end
    end

    nums.each_with_index do |num, o_i|
        if o_i == nums.length-1
            output_str = output_str + "#{num}" + "\n"
        else
            output_str = output_str + "#{num} "
        end
    end
end
puts output_str


Measured memory_bytes: 83496
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const long double PI = acos(-1.0L);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  s[3] = '8';
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N = int(readline())
    K = int(1e9) + 7
    ans = pow(10, N, K) - pow(9, N, K) - pow(9, N, K) + pow(8, N, K)
    print(ans%K)
if __name__ == '__main__':
    main()


Measured memory_bytes: 9196
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;

int n,m,k;
pair<int,int> point[4][N];
int c[4];
bool judge(int x,int y)
{
    if(x==0||y==0||x==m||y==n)
        return true;
    return false;
}
void func(int x,int y,int t)
{
    if(y==0)
        point[0][c[0]++]=make_pair(x,t);
    else if(x==m)
        point[1][c[1]++]=make_pair(y,t);
    else if(y==n)
        point[2][c[2]++]=make_pair(x,t);
    else if(x==0)
        point[3][c[3]++]=make_pair(y,t);
}
bool cmp(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.first>b.first;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    int flag=1;
    memset(c, 0, sizeof c);
    for(int i=1;i<=k;i++)
    {
        int x1,y1,x2,y2;
        cin >> y1 >> x1 >> y2 >> x2;
        if(judge(x1,y1)&&judge(x2,y2))
        {
            func(x1,y1,i);
            func(x2,y2,i);
        }
    }
    sort(point[0],point[0]+c[0]);
    sort(point[1],point[1]+c[1]);
    sort(point[2],point[2]+c[2],cmp);
    sort(point[3],point[3]+c[3],cmp);
    stack<int> S;
    for(int i=0;i<4;i++)
        for(int j=0;j<c[i];j++)
        {
            if(S.empty())
                S.push(point[i][j].second);
            else
            {
                if(S.top()==point[i][j].second)
                    S.pop();
                else S.push(point[i][j].second);
            }
        }
    if(!S.empty()) flag=0;
    if(flag) cout << "YES";
    else cout << "NO";

    return 0;
}


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

namespace debug
{
    public static partial class Program
    {
        public static void Main()
        {
            var str = Console.ReadLine();

            // dp[i][j] -> 先頭i文字のうち、13で割った余りがjであるものの数
            // 0 <= j <= 12
            var dp = new long[str.Length + 1][];
            for (int i = 0; i < str.Length + 1; i++)
            {
                dp[i] = new long[13];
            }

            dp[0][0] = 1;

            for (int i = 0; i < str.Length; i++)
            {
                var c = str[i] == '?' ? -1 : str[i].ToLong();
                for (int j = 0; j < 10; j++)
                {
                    if (c != -1 && c != j) continue;

                    for (int k = 0; k < 13; k++)
                    {
                        dp[i + 1][(k * 10 + j) % 13] += dp[i][k];
                    }
                }

                for (int j = 0; j < 13; j++)
                {
                    dp[i + 1][j] %= MOD;
                }
            }

            Console.WriteLine(dp[str.Length][5]);
        }
    }

    public static partial class Program
    {
        //テンプレここから
        private static long GCD(long aaa, long bbb) => bbb == 0 ? aaa : GCD(bbb, aaa % bbb);
        private static long LCM(long aaa, long bbb) => aaa * bbb / GCD(aaa, bbb);
        private static long ToLong(this double ddd) => (long) ddd;
        private static long ToLong(this string str) => long.Parse(str);
        private static long[] ToLong(this IEnumerable<string> strs) => strs.Select(x => x.ToLong()).ToArray();
        private static long[] ToLongArray(this string str, char opr = ' ') => str.Split(opr).ToLong();
        private static long Diff(long aaa, long bbb) => Math.Abs(Math.Max(aaa, bbb) - Math.Min(aaa, bbb));
        private static long Sign(this long iii) => Math.Sign(iii);
        private static bool IsEven(this long iii) => iii % 2 == 0;
        private static readonly int[] Dx = {0, -1, 0, 1};
        private static readonly int[] Dy = {-1, 0, 1, 0};
        public const int MOD = 1000000007;
        public const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        public const string alphabet = "abcdefghijklmnopqrstuvwxyz";
        public static long ToLong(this char ccc) => ccc.ToString().ToLong();
        public static string Join(this IEnumerable<string> array, string sep = "") => string.Join(sep, array);
        public static string Join(this IEnumerable<char> array, string sep = "") => string.Join(sep, array);

        public static string JoinToStr(this IEnumerable<long> array, string sep = "")
            => array.Select(xxx => xxx.ToString()).Join(sep);

        public static string JoinToStr(this IEnumerable<int> array, string sep = "")
            => array.Select(xxx => xxx.ToString()).Join(sep);

        //テンプレここまで
    }
}

Measured memory_bytes: 32980
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 8e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

pii A[MAXN];
ll bi[MAXN];
char S[MAXN];
int tree[MAXN][3];
int B[MAXN];
int C[MAXN];
vector<int> xpos;
vector<int> ypos;

void update(int tmp,int j)
{

    tree[tmp][j]++;
    tmp>>=1;

    while(tmp){
        tree[tmp][j] = tree[tmp*2][j]+tree[tmp*2+1][j];
        tmp>>=1;
    }
    return;
}

int getans(int L,int R,int j)
{
    ll res = 0;

    while(L<=R){
        if(L&1){res+=tree[L][j]; L++;}
        if(!(R&1)){res+=tree[R][j]; R--;}
        L>>=1; R>>=1;
    }

    return res;
}

int main()
{
    int n,m,k,x,y;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int idx = -1,idy = -1;

    cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>A[i].f>>A[i].s;
        xpos.push_back(A[i].f);
        ypos.push_back(A[i].s);
    }

    sort(xpos.begin(),xpos.end());
    sort(ypos.begin(),ypos.end());

    sort(A,A+n);

    bi[0] = 1;

    for(int i=1;i<=n;i++){
        bi[i] = bi[i-1]*2;
        bi[i]%=PMOD;
    }

    int base = 1;

    for(base;base<n;base*=2);

    for(int i=0;i<n;i++){

        idy = lower_bound(ypos.begin(),ypos.end(),A[i].s)-ypos.begin();

        C[i] = getans(base,base+idy,0);
        update(base+idy,0);
    }

    for(int i=n-1;i>=0;i--){

        idy = lower_bound(ypos.begin(),ypos.end(),A[i].s)-ypos.begin();

        B[i] = getans(base+idy,base*2-1,1);
        update(base+idy,1);
    }
    ll res = 0;
    ll a,b,c,d;
    ll cur = 0;
    for(int i=0;i<n;i++){
        idx = lower_bound(xpos.begin(),xpos.end(),A[i].f)-xpos.begin();
        idy = lower_bound(ypos.begin(),ypos.end(),A[i].s)-ypos.begin();

        a = idx-C[i];
        b = B[i];
        c = C[i];
        d = (n-1-idx)-B[i];
        //cout<<a<<" "<<b<<" "<<c<<" "<<d<<"\n";
        cur = bi[a+b]+bi[a+c]+bi[b+d]+bi[c+d];
        cur %= PMOD;
        cur -= (bi[a]+bi[b]+bi[c]+bi[d])%PMOD;
        cur = (bi[n]-1)-cur;
        //cout<<cur<<"\n";
        res = (res+cur+PMOD)%PMOD;
    }

    cout<<res<<"\n";

    return 0;
}


Measured memory_bytes: 15084
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	for (;;){
		int a[10];
		int b[10];
		for (int i = 0; i < 10; i++){
			cin >> a[i];
		}
		if (cin.eof()) break;
		sort(a, a + 10);
		cout << a[9] + a[8] + a[7] << " ";
		for (int i = 0; i < 10; i++){
			cin >> b[i];
		}
		sort(b, b + 10);
		cout << b[9] + b[8] + b[7] << endl;
	}
}

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

using namespace std;

int main() {
    int N, C;
    cin >> N >> C;

    vector<vector<unsigned char>> usePerCh(C + 1, vector<unsigned char>(100001, 0));
    for (int i = 0; i < N; i++) {
        int s, t, c;
        cin >> s >> t >> c;
        if (usePerCh[c][s - 1] == 0) {
            usePerCh[c][s - 1] = 1;
        }
        for (int ct = s; ct < t; ct++) {
            usePerCh[c][ct] = 1;
        }
    }

    int maxParUseCount = 0;
    for (int t = 0; t <= 100001; t++) {
        int parUseCount = 0;
        for (int c = 1; c <= C; c++) {
            parUseCount += usePerCh[c][t];
        }
        maxParUseCount = max(parUseCount, maxParUseCount);
    }

    cout << maxParUseCount << endl;
    return 0;
};


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

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

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;


int main(){
    int N;
    cin >> N;
    char c[N];
    REP(i,N){
        cin >> c[i];
    }
    int cnt;
    int ans=0;
    bool flag[26];
    REP(i,26){
        flag[i] = true;
    }
    FOR(i,1,N-1){
        cnt = 0;
        FOR(j,0,i){
            FOR(k,i,N){
                if(c[j]==c[k]){
                    if(flag[int(c[j]-'a')]){
                        cnt++;
                        flag[int(c[j]-'a')] = false;
                    }
                }
            }
        }
        ans = max(ans,cnt);
        REP(i,26){
            flag[i] = true;
        }
    }
    cout << ans;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int INF = (int)1e9;
		int n=sc.nextInt(),m=sc.nextInt();
		int[][] g=new int[n+1][n+1];
		int[][] c=new int[n+1][n+1];
		
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				g[i][j] = INF;
			}
			g[i][i] = 0;
		}
		
		for(int i=0;i<m;i++){
			int u=sc.nextInt(),v=sc.nextInt(),w=sc.nextInt();
			g[u][v] = w;
			g[v][u] = w;
			c[u][v] = w;
			c[v][u] = w;
		}
		
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					g[i][j] = Math.min(g[i][j],g[i][k]+g[k][j]);
		
		int ans = 0;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(c[i][j]>g[i][j])
					ans++;
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 25732
/**
 *    author:  zjsdut
 *    created: 2020/01/20 06:28:00       
**/
#include <bits/stdc++.h>

using namespace std;

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

template<typename A, typename B>
bool chkmin(A &a, const B &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}

template<typename A, typename B>
bool chkmax(A &a, const B &b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}

template<typename T>
istream &operator>>(istream &stream, vector<T> &vec) {
  for (auto &x : vec) stream >> x;
  return stream;
}

void scan() {}

template<class T, class ...Args>
void scan(T &a, Args &...rest) {
  cin >> a;
  scan(rest...);
}

using ll = long long;
using vl = vector<ll>;
using vb = vector<bool>;
using vi = vector<int>;
using pii = pair<int, int>;
template<typename T> using vv = vector<vector<T>>;
#define rng(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define up(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define down(i, b, a) for (int i = int(b); i >= int(a); i--)
#define rep(n) for(int _iter_##n = 0, _num_##n = (int)n; _iter_##n < _num_##n; ++_iter_##n)
#define FOR(x, cont) for (const auto &x: cont)
#define For(x, cont) for (auto &x: cont)
#define all(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define SZ(x) (int)(x).size()
#define UNIQ(vec) (vec).erase(unique(all(vec)), end(vec))
#define LB(cont, x) int(lower_bound(all(cont), x) - begin(cont))
#define UB(cont, x) int(upper_bound(all(cont), x) - begin(cont))

template<typename T>
ostream &operator<<(ostream &stream, const vector<T> &vec) {
  if (!vec.empty()) {
    stream << vec[0];
    for (size_t i = 1; i != vec.size(); ++i)
      stream << ' ' << vec[i];
  }
  return stream;
}

template<typename T>
void print(const vector<T> &t) { cout << t << '\n'; }

template<typename T>
void print(const vector<vector<T>> &t) {
  for (const auto &row : t) {
    print(row);
  }
}

template<typename T>
void print(const T &t) { cout << t << ' '; }

template<typename T, typename ...Args>
void print(const T &t, const Args &...rest) {
  print(t);
  print(rest...);
}

template<typename T>
void println(const T &t) { cout << t << '\n'; }

template<typename T, typename ...Args>
void println(const T &t, const Args &...rest) {
  print(t);
  println(rest...);
}

int main() {
#if defined LOCAL
  ifstream in("in.txt");
  cin.rdbuf(in.rdbuf());
#endif
  int a, b;
  scan(a, b);
  int x = min(a, b);
  int y = a + b - x;
  rep (y) {
    cout << x;
  }
  cout << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int n;
    cin >> n;
    vvi a(2, vi(n));
    rep(i, 2) {
        rep(j, n) {
            cin >> a[i][j];
        }
    }
    vi down(n,0);
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if(i < j) sum += a[1][j];
            else if(i == j) sum += a[0][j] + a[1][j];
            else sum += a[0][j];
        }
        down[i] = sum;
    }
    sort(down.rbegin(), down.rend());
    cout << down[0] << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef long long int ll;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
#define MAX_NUM 50
long long comb[MAX_NUM + 1][MAX_NUM + 1];

ll par[100000], depth[100000];
static void calc_comb()
{
	for (uint32_t i = 0; i <= MAX_NUM; i++) {
		for (uint32_t j = 0; j <= i; j++) {
			if ((j == 0) || (i == j)) {
				comb[i][j] = 1;
			}
			else {
				comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
			}
		}
	}
}


//------------------変数-----------------------//
ll h, w, a, b;
//-------------------関数----------------------//
const int MAX_N = 200005;
long long fact[MAX_N];
long long fact_inv[MAX_N];
long long bin_pow_mod(long long x, long long y) {
	if (x == 0) return 0;
	long long prod = 1;
	while (y>0) {
		if (y & 1) {
			prod = (prod*x) % mod;
		}
		x = (x*x) % mod;
		y >>= 1;
	}
	return prod%mod;
}
struct init_fact {
	init_fact() {
		fact[0] = 1, fact_inv[0] = 1;
		for (int i = 1; i<MAX_N; ++i) {
			fact[i] = (fact[i - 1] * i) % mod;
			fact_inv[i] = bin_pow_mod(fact[i], mod - 2);
		}
	}
} init_fact;

int main() {
	init_fact;
	cin >> h >> w >> a >> b;
	ll cnt = 0;
	for (ll i = b+1; i <= w; i++)
	{
		//cout << mod_comb(i - 1 + h - a, h - a, mod)*mod_comb(a - 2 + w - i, w - i, mod) << endl;
		cnt += fact[i-1+h-a-1]*fact_inv[h-a-1]%mod*fact_inv[i-1]%mod*(fact[a-1+w-i]*fact_inv[w-i]%mod*fact_inv[a-1]%mod);
		cnt %= mod;
	}
	cout << cnt%mod << endl;
	return 0;
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a)  (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

int main(){
  int n,k; cin >> n >> k;
  int ans = 0;
  rep(i, n){
    int h; cin >> h;
    if(h >= k) ans++;
  }
  std::cout << ans << '\n';
}


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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

ans = 0
for i in range(1, n+1, 2):
    if len(make_divisors(i)) == 8:
        ans += 1

print(ans)


Measured memory_bytes: 3188
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Code author: Saurabh Singhal
Code copy karne vaale tera muh kaala
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ppb pop_back
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef vector<int> vi_t;
typedef vector<ll> vll_t;
int t=1;
vll_t a,b;
int  main(){
	// #ifndef ONLINE_JUDGE
 //    // for getting input from input.txt
 //    freopen("input.txt", "r", stdin);
 //    // for writing output to output.txt
 //    freopen("output.txt", "w", stdout);
	// #endif
	int n,m;
	cin>>n>>m;
	vector<int>ans(n+1,0);
	bool broke[n+1];
	memset(broke,false,sizeof(broke));
	for(int i=0;i<m;i++){
		int a;
		cin>>a;
		broke[a]=true;
	}
	ans[0]=1;
	ans[1]=1;
	if(broke[1]){
		ans[1]=0;
	}
	for(int i=2;i<=n;i++){
		if(broke[i]){
			ans[i]=0;
		}
		else{
			ans[i]=(ans[i-1]+ans[i-2])%MOD;
		}
	}
	cout<<ans[n]<<endl;
}

Measured memory_bytes: 768
#include<stdio.h>

int main(void){
  int i, n;
  int rcou = 0, bcou = 0;
  
  scanf("%d", &n);
  char s[n];
  
  scanf("%s", s);
  
  for(i = 0;i < n;i++){
    if(s[i] == 'R'){
      rcou++;
    }
    else{
      bcou++;
    }
  }
  if(rcou > bcou){
    printf("Yes");
  }
  else{
    printf("No");
  }
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
const int N = 15;
using namespace std;

int main()
{

int n, s[N] ={0}, h[N]={0}, c[N]={0}, d[N]={0};

scanf("%d", &n);

for(int i = 0; i<n; i++)
{
	char k;
	int p;
	
	scanf(" %c %d", &k, &p);
	if(k == 'S')
	{
		s[p]++;
	}
	else if(k == 'H')
	{
		h[p]++;
	}
	else if(k == 'C')
	{
		c[p]++;
	}
	else if(k == 'D')
	{
		d[p]++;
	}
	}
	for(int i = 1; i<=13; i++)
	{
		if(s[i] != 1)
		{
			printf("S %d\n", i);
		}			
	}
	
	for(int i = 1; i<=13; i++)
	{
		if(h[i] != 1)
		{
			printf("H %d\n", i);
		}			
	}
	
	for(int i = 1; i<=13; i++)
	{
		if(c[i] != 1)
		{
			printf("C %d\n", i);
		}			
	}
	
	for(int i = 1; i<=13; i++)
	{
		if(d[i] != 1)
		{
			printf("D %d\n", i);
		}			
	}

	return 0;
}


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

using namespace std;

#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for (long long a = b; a < c; a++)
#define f0rd(a, b) for (long long a = b; a >= 0; a--)
#define f1rd(a, b, c) for (long long a = b; a >= c; a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define f first
#define s second

#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << endl;}

typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const ll inf = 1e12;
const ll mod = 1e9 + 7;

ll ans[100001];
vpl adj[100001];

set<ll> st;

ll dfs(ll u, ll p) {
  ll ret = 0;
  for (auto v: adj[u]) {
    if (v.s != p) {
      ans[v.f] = *st.begin();
      ret = max(ret, *st.begin());
      st.erase(*st.begin());
    }
  }

  for (auto v: adj[u]) {
    st.insert(ans[v.f]);
  }

  for (auto v: adj[u]) {
    if (v.s != p) {
      st.erase(ans[v.f]);
      ret = max(ret, dfs(v.s, u));
      st.insert(ans[v.f]);
    }
  }

  return ret;

}

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

  int n; cin >> n;

  f0r(i, n-1) {
    ll a, b;

    cin >> a >> b;
    a--; b--;

    adj[a].pb(mp(i, b));
    adj[b].pb(mp(i, a));

  }

  f0r(i, n) {
    st.insert(i+1);
  }


  cout << dfs(0, -1) << endl;

  f0r(i, n-1) {
    cout << ans[i] << endl;
  }

}

Measured memory_bytes: 17532
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
    int h, w;
    while(true){
        scanf("%d %d", &h ,&w);
        if(h == 0 && w == 0) break;
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}


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



int main() {
  int64_t N;
  cin>>N;
  
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec.at(i);
  }
  int64_t sum=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(vec.at(i)==vec.at(j)||vec.at(i)==vec.at(k)||
           vec.at(j)==vec.at(k)){
          continue;
        }
        if(vec.at(i)+vec.at(j)>vec.at(k)&&
           vec.at(i)+vec.at(k)>vec.at(j)&&
           vec.at(j)+vec.at(k)>vec.at(i)){
          sum++;
        }
      }
    }
  }
  cout<<sum<<endl;
    
  
}

Measured memory_bytes: 3628
#include <stdio.h>
 
int main() {
 
  int n,c;
  int a[101] = {0};
  int d,i,j;
  int flag;
 
 
  scanf("%d",&n);
 
  c = 0;
 
  for(i = 0;i<n;i++) {
 
    scanf("%d" ,&a[i]);
 
  }
 
  flag = 1;
 
  while(flag) { 
    flag = 0;
 
    for(j=n-1;j>=1;j--) {
       
      if(a[j] < a[j-1]) {
    d = a[j];
    a[j] = a[j-1];
    a[j-1] = d;
    c++;
    flag = 1;
      } 
    }
     
  }
 
  for(i=0;i<n;i++) {
    printf("%d",a[i]);
    if(i != n-1) printf(" ");
 
}
  printf("\n%d\n",c);
 
  return 0;
 
}


Measured memory_bytes: 2140
#include <cstdio>
#include <cstring>
using namespace std;
const int N=10010,MOD=1e9+7;
int d[N];
int f[N][2][2];
inline int max(int x,int y){
    return x>y?x:y;
}
void readData(){
    static char str[N];
    scanf("%s",str+1);
    d[0]=strlen(str+1);
    for(int i=1;i<=d[0];i++) d[d[0]-i+1]=str[i]-'0';
}
int dp(int n){
    int m=n>>1;
    for(int i=0;i<=m;i++) 
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                f[i][j][k]=0;
    f[0][0][0]=1;
    for(int i=0;i<m;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                if(f[i][j][k]){
                    for(int x=0,y,j1,k1;x<10;x++){
                        k1=x+d[i+1]+k;
                        y=k1%10;
                        k1/=10;
                        j1=10*j+x-y-d[n-i];
                        if(j1<0||j1>1) continue;
                        if(!i&&(!x||!y)) continue;
                        (f[i+1][j1][k1]+=f[i][j][k])%=MOD;
                    }
                }
    int res=0;
    if(n&1){
        int mid=(n+1)>>1;
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                if(f[m][j][k])
                    for(int x=0,y;x<10;x++){
                        y=x+d[mid]+k;
                        if((x==y%10)&&(y/10==j))
                            (res+=f[m][j][k])%=MOD;
                    }
    }
    else{
        for(int j=0;j<2;j++)
            (res+=f[m][j][j])%=MOD;
    }
    return res;
}
void solve(){
    int ans=0,maxlen=d[0]<<1;
    for(int i=max(2,d[0]);i<=maxlen;i++)
        (ans+=dp(i))%=MOD;
    printf("%d\n",ans<0?ans+MOD:ans);
}
int main(){
    readData();
    solve();
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N,M = [int(i) for i in input().split()]
nes = [0] * (N+1)
for i in range(M) :
    a,b = [int(j) for j in input().split()]
    nes[a] +=1
    nes[b] +=1
for i in range(1,N+1) :
    print(nes[i])

Measured memory_bytes: 3060
#include <stdio.h>
int main(){

  int m, f, r;
  char grad;
  while(1){
    scanf("%d %d %d", &m, &f, &r);

    if(m == -1 && f == -1 && r == -1)break;
    
    if((0 <= m+f && m+f < 30) || m == -1 || f == -1){ 
      grad = 'F';
    }else if(80 <= m+f && m+f <= 100){
      grad = 'A';
    }else if(65 <= m+f && m+f < 80){
      grad = 'B';
    }else if((50 <= m+f && m+f < 65) || (50 <= r && r <= 100)){
      grad = 'C';
    }else if(30 <= m+f && m+f < 50){
      grad = 'D';
    }
    printf("%c\n", grad);
  } 
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MOD 1000000007
#define MAX 100

int main(){
  ll H,W;
  cin>>H>>W;
  if(H==1||W==1){
    cout<<1<<endl;
  }else{
    cout<<(H*W-1)/2+1<<endl;
  }
}


Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

L = int(input())

Lstr = bin(L)[2:]

N = len(Lstr)
M = (N - 1) * 2 + (Lstr.count("1") - 1)

print(N, M)
c = 1
for i in range(1, N):
    print(i, i + 1, c)
    print(i, i + 1, 0)
    c *= 2

c = 2 ** (N - 1)
for i, v in enumerate(Lstr[::-1]):
    if i == N - 1:
        continue
    if v == "1":
        print(i + 1, N, c)
        c += 2 ** i

Measured memory_bytes: 83660
import numpy as np

n,k= map(int,input().split())
a = list(map(int,input().split()))
target = a[0:k]
p = sum(target)
for i in range(n-k):
    ans = p - a[i] + a[i+k]
    # print(ans)
    if ans > p:
        print("Yes")
    else:
        print("No")
    p = ans


Measured memory_bytes: 50000
def transport(n,a,b,c,d,e):
    s = [a,b,c,d,e]
    x = min(s)
    return 5+int(1/x*(n-1))
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
print(transport(n,a,b,c,d,e))  

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main(){
	
	int N;
	
	cin >> N;
	
	int upper[100001];
	
	for(int i = 0; i <= N; i++){
		upper[i] = 0;
	}
	
	int count = 0;
	
	for(int i = 0; i < N; i++){
		int num;
		cin >> num;
		upper[N - count]++;
		if(num <= (i - count) * 2 && i != 0){
			count++;
		}
	}
	
	long long int ans = 1;
	int rest = 0;
	
	for(int i = 1; i <= N; i++){
		for(int j = 0; j < upper[i]; j++){
			//cout << ans << " ";
			ans *= (i - rest);
			rest++;
			ans = ans % 1000000007;
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 768
/*
 *    FileName:
 *      Source:
 *        Date:
 *      Author: Mew
 *	  Function:
 */
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iomanip>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<iterator>
#include<ctime>
using namespace std;
int n;
long long a[100008];
int main()
{
	cin>>n;
	long long ans = 0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[0] = 0;
	int h = 0, now = 1;
	while(h<n){
		while(a[h]+1 == a[now] && h<n){
			h = now;
			now++;
			while(now<=n&&a[now]<=a[h])
				now++;
			if(now>n)break;
		}
		if(h >= n || now > n)break;
		int t = (a[now]-1)/(a[h]+1);
		ans+=t;
		a[now] =1;
		while(now<=n&&a[now]<=a[h])
			now++;
		if(now>n)break;
	}
	cout<<ans<<endl;
	return 0;
}



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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int H,W;
int A[202][202];
ll ma[402][202][202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	ma[0][0][0]=A[0][0];
	
	FOR(i,H+W-2) {
		int y1,y2,x1,x2;
		FOR(y1,H) FOR(y2,H) {
			x1=i-y1;
			x2=i-y2;
			if(x1<0 || x1>=W || x2<0 || x2>=W) continue;
			ll v=ma[i][y1][y2];
			if(x1<W-1 && x2<W-1) { //RR
				if(y1==y2) ma[i+1][y1][y2] = max(ma[i+1][y1][y2],v+A[y1][x1+1]);
				else ma[i+1][y1][y2] = max(ma[i+1][y1][y2],v+A[y1][x1+1]+A[y2][x2+1]);
			}
			if(x1<W-1 && y2<H-1) { // RD
				if(x1+1==x2) ma[i+1][y1][y2+1] = max(ma[i+1][y1][y2+1],v+A[y1][x1+1]);
				else ma[i+1][y1][y2+1] = max(ma[i+1][y1][y2+1],v+A[y1][x1+1]+A[y2+1][x2]);
			}
			if(y1<H-1 && x2<W-1) { // DR
				if(y1+1==y2) ma[i+1][y1+1][y2] = max(ma[i+1][y1+1][y2],v+A[y1+1][x1]);
				else ma[i+1][y1+1][y2] = max(ma[i+1][y1+1][y2],v+A[y1+1][x1]+A[y2][x2+1]);
			}
			if(y1<H-1 && y2<H-1) { //DD
				if(y1==y2) ma[i+1][y1+1][y2+1] = max(ma[i+1][y1+1][y2+1],v+A[y1+1][x1]);
				else ma[i+1][y1+1][y2+1] = max(ma[i+1][y1+1][y2+1],v+A[y1+1][x1]+A[y2+1][x2]);
			}
			
		}
	}
	cout<<ma[H+W-2][H-1][H-1]<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 64768
#include<stdio.h>

int main(){
  char s[7];
  scanf("%s", s);
  switch(s[0]){
    case 'S':
      puts("Cloudy");
      break;
    case 'C':
      puts("Rainy");
      break;
    case 'R':
      puts("Sunny");
      break;
  }
  return 0;
}

Measured memory_bytes: 128
package main

import (
	"fmt"
	"sort"
)

var n int

func main() {
	fmt.Scan(&n)

	var arr []int
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		arr = append(arr, a)
	}

	var lis []int
	lis = append(lis, arr[0])
	for i := 1; i < len(arr); i++ {
		if val, last := arr[i], lis[len(lis)-1]; val == last {
		} else if last < val {
			lis = append(lis, val)
		} else {
			f := func(j int) bool {
				return val < lis[j]
			}
			index := sort.Search(len(lis), f)
			if index == 0 || lis[index-1] != val {
				lis[index] = val
			}
		}
	}
	fmt.Println(len(lis))
}



Measured memory_bytes: 7120
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		@SuppressWarnings("resource")
		Scanner scan = new Scanner(System.in);

		String N = scan.nextLine();
		
		char a = N.charAt(0);
		int a2 = Integer.parseInt(""+a);
		char b = N.charAt(1);
		int b2 = Integer.parseInt(""+b);
		
		if(a2 == 9){
			System.out.println("Yes");
		} else if(b2 == 9 ) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		

	}
}

Measured memory_bytes: 23636