akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leadinz zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
ll bin_pow(ll a,ll b,ll m)
{
    ll res=1;
    a%=m;
    while(b>0){
        if(b&1)res=res*a%m;
        b>>=1;
        a=a*a%m;
    }
    return res;
}
bool miller_rabin(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=bin_pow(a,d,n);
    if(x==1 || x==n-1)return true;
    while(d!=n-1){
        x=(x*x)%n;
        d*=2;
        if(x==1)return false;
        if(x==n-1)return true;
    }
    return false;
}
bool prime(ll n,ll k)
{
    if(n==1 || n==4)return false;
    if(n<=3)return true;
    ll d=n-1;
    while(d%2==0)d/=2;
    for(int i=0;i<k;i++){
        if(!miller_rabin(d,n))return false;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll mod=1e9+7;
    ll n;
    cin>>n;
    vector<ll>v;
    for(int i=2;i<=n;i++){
        if(prime(i,3))v.push_back(i);
    }
    ll ans=1;
    for(auto x: v){
        ll res=n;
        ll cnt=0;
        while(res>=x){
            cnt+=(res/=x);
        }
        ans=ans*(cnt+1)%mod;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>

using ll = long long;

int main() {
    std::vector<int> a(3);
    for (int i = 0; i < 3; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());
    std::cout << std::abs(a[1] - a[0]) + std::abs(a[2] - a[1]) << std::endl;
    return 0;
}


Measured memory_bytes: 256
# coding: UTF8

#input = "30 30 30"
#l = map(int, input.split())
l = list(map(int, input().split()))
l.sort()
a = l[0]
b = l[1]
c = l[2]

if a == b == c:
	print("1")
elif a == b or b == c:
	print("2")
else:
	print("3")

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

int main() {
    int N, ans=0;
    bool flag = true;
    cin >> N;
    int i = N;
    
    while(flag){
        if(i%111==0){
            ans = i;
            flag = false;
        }else{
            i += 1;
        }
    }cout << ans << endl;
}

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

int BFS(int s, int t, const vector<vector<int> >& G){
    vector<int> stock1;
    vector<int> stock2;
    stock1.push_back(s);
    vector<int> check(101, 0);
    int d = 0;
    while (1) {
        for (int i = 0; i < stock1.size(); i++) {
            if (stock1[i] == t) return d;
            for (int j = 0; j < G[stock1[i]].size(); j++) {
                if (check[G[stock1[i]][j]] == 0) {
                    check[G[stock1[i]][j]] = 1;
                    stock2.push_back(G[stock1[i]][j]);
                }
            }
        }
        if (stock2.empty()) return -1;
        stock1.clear();
        stock1.swap(stock2);
        d++;
    }
}

int main(){
    int n;
    cin >> n;
    vector<vector<int> > G(n + 1);
    for (int i = 0; i < n; i++) {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            int v;
            cin >> v;
            G[u].push_back(v);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << i << " " << BFS(1, i, G) << endl;
    }
    return 0;
}

Measured memory_bytes: 3160
import java.io.*;

class Main{
 public static void main(String[] args)throws IOException{

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String str = br.readLine();
  String[] strAry = str.split(" ");
  int W = Integer.parseInt(strAry[0]);
  int H = Integer.parseInt(strAry[1]);
  int x = Integer.parseInt(strAry[2]); 
  int y = Integer.parseInt(strAry[3]);
  int r = Integer.parseInt(strAry[4]);  

  if(x+r<=W&&x-r>=0&&y-r>=0&&y+r<=H){
    System.out.println("Yes");
  }else{
    System.out.println("No");
  }
  
  
 }
}

Measured memory_bytes: 24300
#include<bits/stdc++.h>
using namespace std;
int t[100005];
int fun(int h[], int i, int n)
{
  if(i == n-1)
    return 0;
  if(t[i]!=-1)
    return t[i];

  if(i<=n-3)
    return t[i] = min(fun(h,i+1,n)+abs(h[i]-h[i+1]), fun(h,i+2,n)+abs(h[i]-h[i+2]));
  return t[i] = fun(h,i+1,n)+abs(h[i]-h[i+1]);

}

int main()
{
  int n;
  cin>>n;
  int h[n];
  for(int i = 0; i < n; i++)
    	cin>>h[i];
  memset(t,-1,sizeof(t));
  cout<<fun(h,0,n)<<"\n";
}



Measured memory_bytes: 8280
q = int(input())
list_A = []
for q in range(q):
    query = list(input().split())
    if int(query[0]) == 0:
        list_A.append(query[1])
    elif int(query[0]) == 1:
        print(list_A[int(query[1])])
    else:
        list_A.pop(len(list_A)-1)


Measured memory_bytes: 19800
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define fill( x, y ) memset( x, y, sizeof x )
#define copy( x, y ) memcpy( x, y, sizeof x )
using namespace std;

typedef long long LL;
typedef pair < int, int > pa;

inline int read()
{
	int sc = 0, f = 1; char ch = getchar();
	while( ch < '0' || ch > '9' ) { if( ch == '-' ) f = -1; ch = getchar(); }
	while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar();
	return sc * f;
}

int main()
{
#ifdef wxh010910
	freopen( "data.in", "r", stdin );
#endif
	int a = read(), b = read(), c = read(), t = 0;
	if( a == b && a == c && a % 2 == 0 ) return printf( "-1\n" ), 0;
	while( true )
	{
		if( a % 2 || b % 2 || c % 2 ) return printf( "%d\n", t ), 0;
		int ta = a, tb = b, tc = c;
		a = tb + tc >> 1, b = ta + tc >> 1, c = ta + tb >> 1;
		t++;
	}
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

//前提:解は必ず存在する
int main() {
  int N, K;
  cin >> N >> K;

  vector<int> D;

  //配列D、嫌いな数字を入れていく。
  for (int i = 0; i < K; i++) {
    int d;
    cin >> d;
    D.push_back(d);
  }

  // 嫌いな数字が出現した際に立つフラグ
  bool flag;

  for (int ans = N; ans <= 99999; ans++) {
    // ansを文字列に変換
    string str = to_string(ans);
    flag = false;

    for (int i = 0; i < K; i++) {
      // 嫌いな数字を文字に変換
      char judge = '0' + D[i];

      // ans中にD[i]が出現したらフラグを立てる
      if (str.find(judge) != string::npos) {
        flag = true;
        break;
      }
    }

    // 嫌いな数字が出現してなかったら表記して終了
    if (flag == false) {
      cout << ans << endl;
      return 0;
    }
  }
}


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

using namespace std;

int main(void) {

	int a[3],num=0;

	for (int k = 0; k < 3; k++) cin >> a[k];

	sort(a, a + 3, greater<int>());

	for (int k = 1; k < 3; k++) {
		num += a[k - 1] - a[k];
	}

	cout << num << "\n";

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,m=0,a=0,r=0,c=0,h=0;
    string s;
    long long ans;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        if(s[0]=='M'){m++;}
        else if(s[0]=='A'){a++;}
        else if(s[0]=='R'){r++;}
        else if(s[0]=='C'){c++;}
        else if(s[0]=='H'){h++;}
    }
    ans=m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h;
    cout<<ans;
}


Measured memory_bytes: 256
from sys import stdin
h = int(stdin.readline().rstrip())

waru = True
warucount = 0
while waru:
    if h == 1:
        break
    h = h // 2
    warucount += 1
ones = 2 ** warucount

ans = 0
for i in range(warucount):
    ans += 2 ** i
print(ans + ones)


Measured memory_bytes: 2940
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    p = LI_()
    q = LI_()
    l = itertools.permutations(range(n), n)
    l = list(l)
    l.sort()
    print(abs(l.index(tuple(p)) - l.index(tuple(q))))
    
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 45168
# ABC134-A

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  r=I()
  return 3*r*r

# main()
print(main())


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

using namespace std;

#define int long long
#define double long double

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

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

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

template <typename T>
T gcd(T m, T n) { return n == 0 ? m : gcd(n, m % n); }
template <typename T>
T lcm(T m, T n) { return n * m / gcd(n, m); }

signed main(void)
{
  //  double a, b, x;
  int a, b, x;
  cin >> a >> b >> x;
  //  cin >> a >> b >> x;
  cout << setprecision(10);
  if (a * a * b == x)
  {
    cout << 0 << endl;
  }
  else
  {
    if (a * a * b / 2. > x)
    {
      double val = 2. * x / (a * b * b);
      double rad = atan(val);
      double r = (M_PI / 2. - rad) * 180. / M_PI;
      cout << r << endl;
    }
    else
    {
      double val = (2. * a * a * b - 2. * x) / (a * a * a);
      double rad = atan(val);
      double r = rad * 180. / M_PI;
      cout << r << endl;
    }
  }
}


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

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		boolean[] search = new boolean[10000000];
        Arrays.fill(search, true);
        for(int i = 2; i < 10000000; i++){
            // ?´???°????????°?????????????????????
            if(!search[i]){
                continue;
            }

            // ?´???°????????°?????????????????¨???
            for(int j = i * 2; j < 10000000; j += i){
                search[j] = false;
            }
        }

        int num;
        while(sc.hasNext()) {
        	num = sc.nextInt();
        	for(int $ = num - 1; $ > 0; $--) {
        		if(search[$]) {
        			System.out.print($ + " ");
        			break;
        		}
        	}
        	for(int $ = num + 1; $ < 10000000; $++) {
        		if(search[$]) {
        			System.out.println($);
        			break;
        		}
        	}
        }

	}

}

Measured memory_bytes: 36972
h,w=map(int,input().split())
a={}
for i in range(26):
  a[chr(i+97)]=0
for i in range(h):
  s=input()
  for j in s:
    a[j]+=1
if h==1 and w==1:print("Yes")
elif h%2==0 and w%2==0:
  for i in a.values():
    if i%4!=0:print("No");exit()
  print("Yes")
elif h%2==1 and w%2==0:
  cnt=0
  for i in a.values():
    if i%4==1 or i%4==3:
      print("No");exit()
    if i%4==2:cnt+=1
  if cnt>w//2:
    print("No")
  else:print("Yes")
elif h%2==0 and w%2==1:
  cnt=0
  for i in a.values():
    if i%4==1 or i%4==3:
      print("No");exit()
    if i%4==2:cnt+=1
  if cnt>h//2:
    print("No")
  else:print("Yes")
else:
  cnt3=0;cnt2=0;cnt1=0
  for i in a.values():
    if i%4==1:cnt1+=1
    elif i%4==2:cnt2+=1
    elif i%4==3:cnt3+=1
  if cnt1+cnt3!=1:print("No")
  elif cnt2+cnt3>(h-1)//2+(w-1)//2:print("No")
  else:
    print("Yes")


Measured memory_bytes: 3064
/**
*    created: 10.07.2020 16:28:01
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}
const long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, m; cin >> n >> m;
    string a[n];
    string b[m];
    rep(i,n) cin >> a[i];
    rep(i,m) cin >> b[i];
    rep(i,n-m+1) rep(j,n-m+1) {
        bool ok = true;
        rep(k,m) {
            string tmp = a[i+k].substr(j,m);
            if (tmp != b[k]) ok = false;
        }
        if (ok) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

signed main() {
    int N;
    cin >> N;

    vector<int> A(N), B(N);
    int sum_a = 0, sum_b = 0;
    for (int& x : A) cin >> x, sum_a += x;
    for (int& x : B) cin >> x, sum_b += x;

    if (sum_b > sum_a) return cout << -1 << endl, 0;

    vector<pair<int, int>> diff(N);
    for (int i = 0; i < N; i++) {
        diff[i] = {A[i] - B[i], i};
    }
    sort(diff.rbegin(), diff.rend());

    set<int> ans;
    int idx = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] >= B[i]) continue;

        int req = abs(A[i] - B[i]);
        while (req > 0) {
            int t = min(req, diff[idx].first);
            req -= t;
            diff[idx].first -= t;
            ans.insert(diff[idx].second);
            ans.insert(i);
            idx += !diff[idx].first;
        }
    }
    cout << ans.size() << endl;

    return 0;
}


Measured memory_bytes: 6656
#include<iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
	int dp[111];
	for (int i = 0; i < 111; i++)dp[i] = 0;
	dp[4] = 1;
	for (int i = 0; i < 111; i++) {
		if (i - 4 >= 0 && dp[i - 4] != 0)dp[i]++;
	}
	dp[7] = 1;
	for (int i = 0; i < 111; i++) {
		if (i - 7 >= 0 && dp[i - 7] != 0)dp[i]++;
	}
	if (dp[n] != 0)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FT first
#define SC second

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;
const int INF = 1e9;
const double EPS = 1e-9;



int main()
{
  int n ;
  cin >> n ;
  
  int k = 0 ;
  while(k*k<=n){
    k++ ;
  }
  
  cout << (k-1)*(k-1) <<endl ;
    

  return 0 ;
}



Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
su = 1
for i in range(n):
    su = su* a[i]
b = []
for i in range(n):
    b.append(su/a[i])

hoge = 0
for i in range(n):
    hoge += b[i]

print(su/hoge)

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

int main() {
    int ans = 0;
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    for(int i = 0; i < N; i++) {
        cin >> p[i];
    }
    sort(p.begin(), p.end());
    ans = accumulate(p.begin(), p.begin() + K, 0);

    cout << ans << endl;
}

Measured memory_bytes: 3632
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

S = input()

w = 0
b = 0
for i, s in enumerate(S):
    if i % 2 == 0:
        if s == "0":
            b += 1
        else:
            w += 1
    else:
        if s == "1":
            b += 1
        else:
            w += 1

print(min(w, b))

Measured memory_bytes: 39664
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace D
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var nm = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var n = nm[0];
            var m = nm[1];
            var war = new Tuple<int, int>[m];
            for (var i = 0; i < war.Length; i++)
            {
                var ab = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
                war[i] = new Tuple<int, int>(ab[0], ab[1]);
            }
            war = war.OrderBy(x => x.Item2).ToArray();
            var answer = 0;
            var right = -1;
            for (var i = 0; i < war.Length; i++)
            {
                if (right <= war[i].Item1)
                {
                    answer++;
                    right = war[i].Item2;
                }
            }
            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 26680
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author dilip
 */

/*
*   author : dilip
*   time : 23-06-2019 22:11
*/

#include <iostream>
#include <fstream>

#include <iostream>
#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;

class ATenki {
public:
	void solve(std::istream& in, std::ostream& out) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

		string s,t;
		in >> s;
		in >> t;
		int c = 0;
		for(int i=0;s[i];i++){
			if(s[i]==t[i])c++;
		}
        out << c;

	}
};


int main() {
	ATenki solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#include <cstring>
#include <queue>
#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;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uld = unsigned long long;
const ll mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
template<class T> inline bool chmax(T &a,T& b){if(a < b){a = b; return true;} else return false;}
template<class T> inline bool chmin(T &a,T& b){if(a > b){a = b; return true;} else return false;}
int main(){
    string s;
    cin >> s;
    int n = s.size();
    int a1=0,a2=0;
    rep(i,n){
        int k = s[i] - '0';
        if(k==i%2) a1++;
        else a2++;
    }
    cout << min(a1,a2) << endl;
}

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

using namespace std;

const int inf = 2e9;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    vector<int> dp(n, inf);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= i - k && j >= 0; j--) {
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
        }
    }

    cout << dp[n - 1] << '\n';
}


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

signed main(){

    string s; cin >> s;
    int n = (int)s.size();
    int ans = 1000000007;
    for(int i = 0; i < n - 2; i++){
        string t = s.substr(i, 3);
        ans = min(ans, (int)abs(753 - stoi(t)));
    }
    cout << ans << endl;
    return 0;
}

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

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount

using namespace std;

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

template <typename T> T id(T b) {return b;};
template <class It> bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It> bool any(It f,It l){return std::any_of(f,l,id<bool>);}
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}

int main()
{
#ifdef FASTIO
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif

  string s;
  cin >> s;

  if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3])
    cout << "Bad\n";
  else
    cout << "Good\n";

  return 0;
}


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

// write-and-erase.cpp
// author: Seong Yong-ju ( @sei40kr )
// Copyright (c) 2017 Seong Yong-ju

#define DEBUG(x) cout << #x << ": " << x << endl

#define MIN(a, b) (a > b ? b : a)
#define MAX(a, b) (a > b ? a : b)

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); --i)

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

#define ALL(a) (a).begin(), (a).end()

using namespace std;

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

  int n;
  cin >> n;
  set<int> nums;
  REP(i, n) {
    int a;
    cin >> a;
    if (nums.erase(a) == 0) {
      nums.insert(a);
    }
  }

  cout << nums.size() << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

#define SIZE 10000000
bool p[SIZE];

int main(){
    int n,m;
    while(1){
        cin>>m>>n;
        if(n==0)break;
        for(int i=0;i<SIZE;i++)p[i]=true;
        int cnt=0;
        for(int i=m;i<SIZE;i++){
            if(!p[i])continue;
            cnt++;
            for(int j=2*i;j<SIZE;j+=i)p[j]=false;
            if(cnt==n+1){
                cout<<i<<endl;
                break;
            }
        }
    }
}


Measured memory_bytes: 12856
#include <iostream>
using namespace std;
#define MAX 100
#define INFINITY (1<<30)
enum{
	white=0,
	gray=1,
	black=2,
};

int n,m[MAX][MAX];

int prim(){
	int u,minv;
	int d[MAX],p[MAX],color[MAX];
	for(int i=0;i<n;i++){
		d[i]=INFINITY;
		p[i]=-1;
		color[i]=white;
	}
	d[0]=0;
	while(1){
		minv=INFINITY;
		u=-1;
		for(int i=0;i<n;i++){
			if(minv>d[i]&&color[i]!=black){
				u=i;
				minv=d[i];
			}
		}
		if(u==-1)	break;
		color[u]=black;
		for(int v=0;v<n;v++){
			if(color[v]!=black&&m[u][v]!=INFINITY){
				if(d[v]>m[u][v]){
					d[v]=m[u][v];
					p[v]=u;
					color[v]=gray;
				}
			}
		}
	}
	int sum=0;
	for(int i=0;i<n;i++){
		if(p[i]!=-1)	sum+=m[i][p[i]];
	}
	return sum;
}

int main(){
	cin>>n;
	int e;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>e;
			if(e==-1)	m[i][j]=INFINITY;
			else	m[i][j]=e;
		}
	}
	cout<<prim()<<endl;
	return 0;
}

Measured memory_bytes: 1200
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define all(a) (a).begin(), (a).end()
 
 
int main() {
  string s;
  cin >> s;
  int count = 0;
  if(s[0]=='o') count++;
  if(s[1]=='o')count++;
  if(s[2]=='o') count++;
  cout << 700 + 100 * count << endl;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int modpow(int x, int n, const int mo) {
	int res = 1;
	while (n > 0) {
		if (n & 1) (res *= x) %= mo;
		(x *= x) %= mo;
		n >>= 1;
	}
	return res;
}

int inverse(int x, const int mo) {
	return modpow(x, mo - 2, mo);
}

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

	int N;
	cin >> N;
	string ans;
	while (N > 0)
	{
		N--;
		ans += (char)('a' + N % 26);
		N /=26;
	}

	reverse(all(ans));
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3652
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

    int D = sc.nextInt();
    int G = sc.nextInt();
    int[] p = new int[D];
    int[] c = new int[D];

    for (int i = 0; i < D; i++) {
      p[i] = sc.nextInt();
      c[i] = sc.nextInt();
    }

    sc.close();

    int ans = Integer.MAX_VALUE;

    for (int i = 0; i < (1 << D); i++) {

      List<Integer> list = new ArrayList<>();

      for (int j = 0; j < D; j++) {
      
        if ((i >> j & 1) == 1) {
          list.add(c[j]);
        } else {
          list.add(0);
        }
      
      }

      int current = 0;
      int score = 0;
      int line = G;

      for(int j = 0; j < list.size(); j++) {

        int v = list.get(j);

        if (v != 0) {
          int score_ = (j+1) * 100;
          score += p[j] * score_ + v;
          current += p[j];
        }

      }
      line -= score;

      boolean canFinish = true;

      if (line < 0){
        ans = Math.min(ans, current);
      } else {
        int count2_ = D - 1;
        int score2_ = D * 100;
        int limit_ = 0;
        if(list.get(count2_) == 0) {
          limit_ = p[count2_];
        }
        while (0 < line) {
          if (0 < limit_) {
            line -= score2_;
            limit_--;
            current++;
          } else {
            count2_--;
            if (count2_ < 0) {
              line = 0;
              canFinish = false;
            }else {
              if(list.get(count2_) == 0) {
                limit_ = p[count2_];
              }
            }
            score2_ = (count2_+1) * 100;
          }
        }
        if (canFinish == true) {
          ans = Math.min(ans, current);
        }
      }

    }

    System.out.println(ans);

  }

}

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

bool f[10000001];

int main() {
  for ( int i = 0; i < 10000001; i++ ) f[i] = false;
  int s; cin >> s;
  int n = s;
  f[s] = true;
  int cnt = 1;
  int ans;
  while(1){
    if ( n % 2 == 0 ) {
      cnt++;
      n /= 2;
      if ( f[n] == true ) {
	cout << cnt << endl;
	return 0;
      }
      f[n] = true;
    } else {
      cnt++;
      n = 3 * n + 1;
      if ( f[n] == true ) {
	cout << cnt << endl;
	return 0;
      }
      f[n] = true;
    }
  }
  return 0;
}


Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

long long INF=numeric_limits<long long>::max();

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    string s;
    cin >> s;
    ll n = s.length();
    ll dp[n];
    memset(dp,0,sizeof(dp));
    ll ans = 0;
    for(ll i = 0; i < n; i++)
    {
        if(i)dp[i]+=dp[i-1];
        if(s[i]=='B')dp[i]++;
        else ans += dp[i];
    }
    cout << ans << endl;
}


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

int main()
{
  int n;

  cin >> n;

  vector<int> p(n);

  int ans = 0;

  rep(i, n)
  {
    cin >> p.at(i);
  }

  for (int i = 1; i < n - 1; i++)
  {
    if ((p.at(i - 1) > p.at(i) && p.at(i) > p.at(i + 1)) || (p.at(i - 1) < p.at(i) && p.at(i) < p.at(i + 1)))
    {
      ans++;
    }
  }

  cout << ans;
}


Measured memory_bytes: 3596
/* ex9_2:
    Jun_JPN*/

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100000 // 10^5
typedef struct node{
    char color;
    struct node *next;
}node;

void push(node **top, char color);
void pop(node **top);

int main(void){
    node *top = NULL;   // 最初のノードは空
    char str[SIZE];
    int i, cnt=0;

    scanf("%s", str);   // 文字列を受け取る

    for(i=0; str[i] != '\0'; i++){
        if(top == NULL || top->color == str[i]){ // ノードtopが空もしくはstr[i]と同じ色だったら
            push(&top, str[i]);
        }else{          // 違う色だったら
            pop(&top);
            cnt += 2;   // 1回のポップで取り出すキューブは2個
        }
    }

    printf("%d\n", cnt);    // 結果を出力

    return 0;
}

void push(node **top, char color){
    node *new = calloc(1, sizeof(node));    // 追加するノード分のメモリを動的確保
    if(new == NULL) exit(1);    // メモリが確保できなかったら終了
    new->color = color;
    new->next = *top;   // ノードtopは1つ下のノードになる
    *top = new;         // ノードnewが新しくtopになる
}

void pop(node **top){
    node *tmp = *top;
    if(top == NULL) exit(1);    // ノードtopが空だったらポップできないので終了
    *top = tmp->next;   // ノードtopの1つ下のノードを新しくtopに
    free(tmp);          // 要らなくなったメモリを解放
}

Measured memory_bytes: 4892
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe

readInt = fst . fromJust . BS.readInt
getInt = readInt <$> BS.getLine

main = do
  [h, w, n] <- replicateM 3 getInt
  let m = max h w
      ans = (n + m - 1) `div` m
  print ans

Measured memory_bytes: 380
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define N 100010
int n,x0,bd;
ll x[N],p[N];
int q[N],nq;
int main(){
	scanf("%d%lld",&n,&x[0]);
	for (int i=1;i<=n;++i){
		scanf("%lld%lld",&x[i],&p[i]);
		if (x[i]<x[0])
			bd=i;
	}
	int l=1,r=n;
	while (l<=bd && r>bd)
		if (p[l]>=p[r]){
			p[l]+=p[r];
			q[++nq]=r--;			
		}
		else{
			p[r]+=p[l];
			q[++nq]=l++;
		}
	for (;l<=bd;++l)
		q[++nq]=l;
	for (;r>bd;--r)
		q[++nq]=r;
	ll ans=0;
	for (int i=nq;i>=1;--i)
		ans+=abs(x[q[i+1]]-x[q[i]]);	
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3680
import java.util.Scanner;

public class Main {
	public static void main(String[] arg) {
		int a = 0, b = 0;
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			a = scan.nextInt();
			b = scan.nextInt();
			System.out.println(String.valueOf(a + b).length());
		}
	}
}

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

int main() {
  int n, x, m[101];
  cin >> n >> x;
  
  int s = 0;
  int M = 1000;
  for(int i = 0; i < n; i++) {
    cin >> m[i];
    s += m[i];
    if(m[i] < M) M = m[i]; 
  }
  cout << n + (x - s) / M << endl;
}  


Measured memory_bytes: 256
#include <stdio.h>
 
 	int i,j,k;
	int n,num[4000];
	long long int tanka,sale_num,sale_sum[4000],sale_all[4001];
	bool judge[4001];

 
int main(void){

	
	while(scanf("%d",&n),n){
		
		//初期化


		
		for(i=0;i<n;i++){
			scanf("%d %lld %lld",&num[i],&tanka,&sale_num);
			sale_sum[i]=tanka*sale_num;
		}

		k=0;
		for(j=0;j<4001;j++){
			judge[j]=0;
			sale_all[j]=0;
		}
		
		
		//idに対応したsaleに+
		for(i=0;i<n;i++){
			sale_all[num[i]] = sale_all[num[i]] + sale_sum[i];
		}
		
		for(i=0;i<n;i++){
			if((sale_all[num[i]] >= 1000000)&&(judge[num[i]]==0)){
				printf("%d\n",num[i]);
				judge[num[i]]=1;
				k=1;
			}
		}
		
		if(k!=1)printf("NA\n");
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define make_unique(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define Sort(vec) sort(vec.begin(),vec.end())
#define RSort(vec) sort(vec.rbegin(),vec.rend())
#define endl "\n"
#define tr1(i) cout<<i<<endl;
#define tr2(i,j) cout<<i<<" "<<j<<endl;
#define tr3(i,j,k) cout<<i<<" "<<j<<" "<<k<<endl;
#define vvi vector<vector<int> > 
#define vvl vector<vector<ll> >
#define all(st) st.begin(),st.end()
#define vpl vector<pair<ll,ll> >
#define vpi vector<pair<int,int> >
#define pi pair<int,int>
#define pl pair<ll,ll>
#define al vector<list<int> >
#define vs vector<string>
#define vi vector<int>
#define vb vector<bool>
#define vl vector<ll>
#define vc vector<char>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define repit(st) for(auto it=st.begin();it!=st.end();it++)
#define ull unsigned long long int
#define eb emplace_back
#define pb push_back
#define ll long long int
#define minf -(1e18)
#define inf 1e18
#define f first
#define se second
#define mod 1000000007
#define mx 500001
using namespace std;
ll mi(ll n,ll m){ll pw=n%m;ll ex=m-2;ll ans=1;while(ex){if(ex&1) ans = ans*pw%m;pw = pw*pw%m;ex>>=1;}return ans%mod;}
ll pw(ll a,ll n){ll pw=a%mod;ll ex=n;ll ans=1;while(ex){if(ex&1) ans = ans*pw%mod;pw = pw*pw%mod;ex>>=1;}return ans%mod;}
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }
void show(ll x){cout<<x<<" ";}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll Abs(ll x){return x>0?x:(-x);}
ll Ceil(ll a,ll b){return a/b+(a%b!=0);}
#define bs binary_search
#define lb lower_bound
#define mkp make_pair
//#define d double
void dfs(vvi&adj,int v,vb&vis,vi&d){
	vis[v]=true;
	for(int nbs:adj[v]){
		if(!vis[nbs]){
			d[nbs]=d[v]+1;
			dfs(adj,nbs,vis,d);
		}
	}
	
}
void solve(){
	int n,u,v;
	cin>>n>>u>>v;
	vvi adj(n);
	for(int i=0;i<n-1;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	u--;v--;
	vi d1(n),d2(n);
	vb vis(n);
	dfs(adj,u,vis,d1);
	vis.clear();vis.resize(n);
	dfs(adj,v,vis,d2);
	for(int i=0;i<n;i++){
	//	cout<<d1[i]<<" "<<d2[i]<<endl;
	}
	int ans=d1[v]-1;
	for(int i=0;i<n;i++){
		if(i==u || i==v || d1[i]>=d2[i]) continue;
		ans=max(ans,d2[i]-1);
	}
	
	cout<<ans;
}
int32_t main(){
FIO;
int t=1;
//cin>>t;
while(t--){
	solve();
}
}

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

long mod = 998244353;
vector<vector<int>> tree;
vector<long> dp;

long rec(int r)
{
    if(dp[r] != 0) return dp[r];
    if(tree[r].empty()){
        dp[r] = 2;
        return dp[r];
    }else{
        long sum = 1;
        for(auto i: tree[r])
        {
            sum = sum * rec(i) % mod;
        }
        dp[r] = (sum + 1)  % mod;
        return dp[r];
    } 
}

void Main()
{
    int n;
    cin >> n;
    // vector<int> x(n), d(n);
    vector<pair<int, int>> robot(n);
    for (int i = 0; i < n; i++)
    {
        cin >> robot[i].first >> robot[i].second;
    }
    sort(robot.begin(), robot.end());
    
    dp.resize(n);
    tree.resize(n);
    vector<int> working;
    vector<int> takahashi;
    working.push_back(0);
    takahashi.push_back(0);
    for (int i = 1; i < n; i++)
    {
        int kido = 0;
        while(!working.empty()){
            if(robot[working.back()].first
                +robot[working.back()].second
                 > robot[i].first){
                tree[working.back()].push_back(i);
                kido = 1;
                break;
            }else{
                working.pop_back();
            }
        }
        if(! kido) takahashi.push_back(i);
        working.push_back(i);
    }

    long sum = 1;
    for(auto i: takahashi)
    {
        sum = sum * rec(i) % mod;
    }
    cout << sum << endl;
    
}

int main(int argc, char **argv)
{
    Main();
    return 0;
}


Measured memory_bytes: 27452
import math

def main():
  N, D = map(int, input().split())
  ans = 0
  
  for _ in range(N):
    X, Y = list(map(int, input().split()))
    if math.sqrt(X**2 + Y**2) <= D:
      ans += 1
  print(ans)
  
  
main()

Measured memory_bytes: 8940
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

typedef long long ll;
typedef long double ld;

const int inf = (int) 1.01e9;
const ld eps = 1e-11;
const ld pi = acos(-1.0L);

mt19937 mrand(random_device{} ());
int rnd(int x) {
  return mrand() % x;
}

const int mod = (int) 1e9 + 7;

void add(int & x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int sum(int x, int y) {
  add(x, y);
  return x;
}

int mult(int x, int y) {
  return (ll) x * y % mod;
}

int power(int x, ll p) {
  int res = 1;
  while (p) {
    if (p & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
    p >>= 1;
  }
  return res;
}

int inv(int x) {
  return power(x, mod - 2);
}

const int k = 4;
const int maxl = 30;
int a[maxl][k][k];

void precalc() {
  a[0][0][1] = 1;
  a[0][1][2] = 1;
  a[0][2][3] = 1;
  a[0][3][1] = 1;
  a[0][3][2] = mod - 2;
  a[0][3][3] = 4;
  for (int it = 0; it + 1 < maxl; it++) {
    for (int i = 0; i < k; i++) {
      for (int j = 0; j < k; j++) {
        for (int r = 0; r < k; r++) {
          add(a[it + 1][i][j], mult(a[it][i][r], a[it][r][j]));
        }
      }
    }
  }
}

const int maxn = 1e5 + 100;
int n, m;
int x[maxn];

bool read() {
  if (scanf("%d%d", &n, &m) < 2) {
    return false;
  }
  for (int i = 0; i < m; i++) {
    scanf("%d", x + i);
  }
  return true;
}

int cur[4];
int tmp[4];

void makestep(int n) {
  for (int i = 0; i < maxl; i++) {
    if (n & (1 << i)) {
      memset(tmp, 0, sizeof(tmp));
      for (int j = 0; j < k; j++) {
        for (int r = 0; r < k; r++) {
          add(tmp[j], mult(cur[r], a[i][j][r]));
        }
      }
      swap(cur, tmp);
    }
  }
}

void solve() {
  cur[0] = 1;
  cur[1] = 1;
  cur[2] = 5;
  cur[3] = 18;
  int prev = 0;
  for (int i = 0; i < m; i++) {
    makestep(x[i] - prev);
    prev = x[i];
    int a = cur[0];
    a = mod - a;
    add(cur[0], mult(a, 1));
    add(cur[1], mult(a, 1));
    add(cur[2], mult(a, 5));
    add(cur[3], mult(a, 18));
  }
  makestep(n - prev);
  printf("%d\n", cur[0]);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen("text.in", "r", stdin));
  assert(freopen("text.out", "w", stdout));
#endif

  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time: %.3f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}



Measured memory_bytes: 640
/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.08.12 00:56:42
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

int MOD = 1e9 + 7;
struct mint {
private:
    long long x;
public:
    mint(long long x = 0) :x((MOD+x)%MOD) {}
    mint(std::string &s) {
        long long z = 0;
        for (int i = 0; i < s.size(); i++) {
            z *= 10;
            z += s[i] - '0';
            z %= MOD;
        }
        this->x = z;
    }
    mint& operator+=(const mint &a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint &a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint &a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint& operator/=(const mint &a) {
        long long n = MOD - 2;
        mint u = 1, b = a;
        while (n > 0) {
            if (n & 1) {
                u *= b;
            }
            b *= b;
            n >>= 1;
        }
        return *this *= u;
    }
    mint operator+(const mint &a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint &a) const {
        mint res(*this);
        return res *= a;
    }
    mint operator/(const mint &a) const {
        mint res(*this);
        return res /= a;
    }
    friend std::ostream& operator<<(std::ostream &os, const mint &n) {
        return os << n.x;
    }
    bool operator==(const mint &a) const {
        return this->x == a.x;
    }
};

struct Combination {
private:
    int N;
    
    mint pow(mint k, long long n) {
        mint res = 1;
        while (n > 0) {
            if (n & 1) {
                res *= k;
            }
            k *= k;
            n >>= 1;
        }
        return res;
    }
public:
    std::vector< mint > FACT, IFACT;
    
    Combination(int n) : N(n) {
        FACT.resize(n + 1);
        IFACT.resize(n + 1);
        FACT[0] = 1;
        IFACT[0] = 1;
        for (int i = 1; i <= n; i++) {
            FACT[i] = FACT[i - 1] * i;
            IFACT[i] = pow(FACT[i], MOD - 2);
        }
    }
    mint comb(int n, int r) {
        if (n < 0 || r < 0 || r > n) return 0;
        if (r > n / 2) r = n - r;
        return FACT[n] * IFACT[n - r] * IFACT[r];
    }
};
int main() {
    int h,w;cin >> h >> w;
    int a,b;cin >> a >> b;
    mint ans = 0;
    Combination cb(h+w);
    for (int i = 0; i < h-a-1; i++) {
        ans += cb.comb(h-1-i+w-b-2,w-2-b) * cb.comb(b+i,i);
    }
    ans += cb.comb(h-1-(h-a-1)+w-b-1,w-1-b) * cb.comb(b+h-a-1,h-a-1);
    cout << ans << endl;
    return 0;
}


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

int main() {

  int q;
  cin >> q;

  for(int i=0;i<q;i++) {
    
    int b;
    cin >> b;
    cout <<"Case "<<i+1<<":"<<endl;
    for(int j=0;j<10;j++) {
      int a[8] = {};  
      b *= b;
      for(int k=7;k>=0;k--) {
	a[k] = b % 10;
	b /= 10;
      }
      int t = 1;
      b = 0;
      for(int k=5;k>=2;k--) {
	b += a[k]*t;
	t*=10;
      }
      cout << b << endl;
    }


  }

  return 0;
}

Measured memory_bytes: 1160
#include<stdio.h>
int main(){
  int h,w,i,j;
  scanf("%d%d",&h,&w);
  char s[h+2][w+2];
  for(j=0;j<w+2;j++){
    s[0][j]='.';
    s[h+1][j]='.';
  }
  for(i=1;i<h+1;i++){
    for(j=0;j<w+1;j++)
      scanf("%c",&s[i][j]);
    s[i][0]='.';
    s[i][w+1]='.';
  }
  for(i=1;i<h+1;i++)
    for(j=1;j<w+1;j++)
      if(s[i][j]=='#' && s[i-1][j]=='.' && s[i+1][j]=='.' && s[i][j-1]=='.' && s[i][j+1]=='.'){
        puts("No");
        return 0;
      }
  puts("Yes");
  return 0;
}


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

using namespace std;

int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);

  int n; cin >> n;
  int a, b, c; cin >> a >> b >> c;
  // 5 0 5, AC AC AC AC AC BC BC BC
  //
  // 1 1 0, AB (AC or BC)
  string ret = "";
  string w[n];
  for(int i = 0; i<n; ++i) {
    cin >> w[i];
  }

  for(int i = 0; i<n; ++i) {
    string which = w[i];
    if(which == "AB") {
      if(a<b)      {ret += "A"; a++; b--;}
      else if(a>b) {ret += "B"; b++; a--;}
      else         {
        if(i != n-1) {
          if(w[i+1] == "AC") {ret += "A"; a++; b--;}
          else {ret += "B"; b++; a--;}
        }
        else {
          ret += "A"; a++; b--;
        }
      }
    }
    if(which == "AC") {
      if(a<c)      {ret += "A"; a++; c--;}
      else if(a>c) {ret += "C"; c++; a--;}
      else         {
        if(i != n-1) {
          if(w[i+1] == "AB") {ret += "A"; a++; c--;}
          else {ret += "C"; c++; a--;}
        }
        else {
          ret += "A"; a++; c--;
        }
      }
    }
    if(which == "BC") {
      if(b<c)      {ret += "B"; b++; c--;}
      else if(b>c) {ret += "C"; c++; b--;}
      else         {
        if(i != n-1) {
          if(w[i+1] == "AC") {ret += "C"; c++; b--;}
          else {ret += "B"; b++; c--;}
        }
        else {
          ret += "C"; c++; b--;
        }
      }
    }
    if(a < 0 || b < 0 || c < 0) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  for(int i = 0; i<ret.size(); ++i) {
    cout << ret[i] << "\n";
  }
}


Measured memory_bytes: 6920