akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

bool isPrime(int x) {
    // x > 0
    if (x == 1) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

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

    int a, d, n;
    while (cin >> a >> d >> n, n) {
        while (true) {
            n -= isPrime(a);
            if (n == 0) break;
            a += d;
        }
        cout << a << endl;
    }
}

Measured memory_bytes: 3136
#include <iostream>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

const int kFacMax = 2 * 100000;

long long fac[kFacMax];
long long finv[kFacMax];
long long inv[kFacMax];

void combi_prepare(int mod) {
  fac[0] = 1;
  fac[1] = 1;
  finv[0] = 1;
  finv[1] = 1;
  inv[1] = 1;

  for (int i = 2; i < kFacMax; 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 combi(int n, int k, long long mod) {
  if (n < 0 || k < 0 || n < k) return 0;

  return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main() {
  const int MOD = 998244353;
  int N, M, K;
  cin >> N >> M >> K;

  // i == 0, always M patterns
  // choose 1..K pairs in N-1
  long long num = M;
  rep(i, N-1-K) {
    num *= M-1;
    num %= MOD;
  }

  combi_prepare(MOD);

  long long sum = 0;
  for(int i=K; i >= 0; i--) {
    long long tmp = num * combi(N-1, i, MOD);
    tmp %= MOD;
    sum += tmp;
    sum %= MOD;

    num *= M-1;
    num %= MOD;
  }

  cout << sum << endl;

  return 0;
}


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

int main()
{
    ll a , b;
    double c;
    cin >> a;
    b = (a+1)/2;
    c = (double)b/(double)a;
    cout << c << endl;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#define rep2r(i, l, r) for (int i = (r) - 1; i >= (l); i--)
#define range(a) a.begin(), a.end()

using namespace std;
using ll = long long;

void amin(int &a, int b) {
  a = min(a, b);
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int N, M; cin >> N >> M;
  constexpr int INF = 1e9;
  vector<int> dp(1 << N, INF);
  dp[0] = 0;
  rep(_, M) {
    int a, b; cin >> a >> b;
    int mask = 0;
    rep(_, b) {
      int c; cin >> c; c--;
      mask |= 1 << c;
    }
    repr(i, 1 << N) {
      amin(dp[i | mask], dp[i] + a);
    }
  }
  if (dp[(1 << N) - 1] == INF) {
    cout << -1 << endl;
  } else {
    cout << dp[(1 << N) - 1] << endl;
  }
}

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

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

#define rep(i, n) FOR(i, 0, n)
#define FOR(i, x, n) for (int i = (x); i < (n); ++i)
#define all(v) (v).begin(), (v).end()

using ll = long long;

template<class T> void chmax(T& a, T b){ a>b?:a=b; }
template<class T> void chmin(T& a, T b){ a<b?:a=b; }

int main() {
    string s;
    int ans = 0;
    cin >> s;
    if (s == "RRR")
        ans = 3;
    else if (s.find("RR") != string::npos)
        ans = 2;
    else if (s.find("R") != string::npos)
        ans = 1;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>

using namespace std;

int main()
{
    string s;
    string comp = "abcdefghijklmnopqrstuvwxyz";
    bool check[26] = {false};
    cin >> s;
    for (char c: s) {
        for (int i=0; i<26; i++) {
            if (c == comp[i]) check[i] = true;
        }
    }
    string ans = "None";
    for (int i=0; i<26; i++) {
        if (!check[i]) {
            ans = comp[i];
            break;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

Measured memory_bytes: 3720
s = str(input())
forward = int((len(s)-1)/2)
back = int((len(s)+3)/2 -1)
if s == ''.join(list(reversed(s))):
    if s[:forward] == ''.join(list(reversed(s[:forward]))):
        if s[back:] == ''.join(list(reversed(s[back:]))):
            print("Yes")
            exit()
print("No")


Measured memory_bytes: 38396
import sys
from operator import add, sub

A, B, C, D = map(int, list(input()))

for i in range(2):
    if i == 0:
        op1 = add
    else:
        op1 = sub
    for j in range(2):
        if j == 0:
            op2 = add
        else:
            op2 = sub
        for k in range(3):
            if k == 0:
                op3 = add
            else:
                op3 = sub

            if op3(op2(op1(A, B), C), D) == 7:
                op1 = "+" if i == 0 else "-"
                op2 = "+" if j == 0 else "-"
                op3 = "+" if k == 0 else "-"
                print(str(A) + op1 + str(B) + op2 + str(C) + op3 + str(D) + "=7")
                sys.exit()

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;

#define INIT std::cin.tie(0);std::ios::sync_with_stdio(false);
#define ALL(c) (c).begin(), (c).end()
#define CALL(c) (c).cbegin(), (c).cend()
#define RALL(c) (c).rbegin(), (c).rend()
#define CRALL(c) (c).crbegin(), (c).crend()
#define REP(i, n) for (int i = 0; i < static_cast<int>(n); i++)
#define FOR(i, s, n) for (int i = s; i < static_cast<int>(n); i++)
#define ASC(t) [](t& x, t& y){ return x < y; }
#define DESC(t) [](t& x, t& y){ return x > y; }
#define PSORT(s,p,e) partial_sort((s), next((s), (p)), (e))
#define VIEW(v,t) for_each((v).begin(), (v).end(), [](t& a) { cout << a << " "; }); cout << endl;

#define IN(a, x, b) (a<=x && x<b)
template<class T> inline T CHMAX(T& x, const T y){return x=(x<y)?y:x;}
template<class T> inline T CHMIN(T& x, const T y){return x=(x>y)?y:x;}
#define OUT(dist) std::cout<<(dist);
#define WS std::cout<<" ";
#define NL std::cout<<"\n"

using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using LL = long long;
using ULL = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using V2 = vector<vector<T>>;
template<class T, int W=255> using A = array<T, W>;
template<class T, int W=255, int H=255> using A2 = array<array<T, W>, W>;

string s1, s2, s3;

int main(){
    INIT;
    cin >> s1 >> s2 >> s3;
    cout << (char)(s1[0]-'a'+'A') << (char)(s2[0]-'a'+'A') << (char)(s3[0]-'a'+'A');
}

Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let s = iterator.next().unwrap();

    if s.starts_with("YAKI") {
        return "Yes".to_string();
    }

    return "No".to_string();
}


Measured memory_bytes: 2108
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

int G[110][110];

int main(){
    memset(G,0,sizeof(G));
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int u,k;
        scanf("%d%d",&u,&k);
        for(int j=0;j<k;j++){
            int v;
            scanf("%d",&v);
            G[u][v]=1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j==1)
                printf("%d",G[i][j]);
            else
                printf(" %d",G[i][j]);
        }
        printf("\n");
    }
    return 0;
}





Measured memory_bytes: 3256
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		double x1 = scan.nextDouble();
		double y1 = scan.nextDouble();
		double x2 = scan.nextDouble();
		double y2 = scan.nextDouble();
		double a = (x2 - x1) * (x2 - x1);
		double b = (y2 - y1) * (y2 - y1);
		double c = a + b;
		double d = Math.sqrt(c);
		System.out.println(d);
	}
}



		

	

Measured memory_bytes: 28016
/**OOO**/
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long ull;
using namespace std;

#define LL                      ll
#define mems(arr,VAL)           memset(arr,VAL,sizeof(arr))
#define pii                     pair<int,int>
#define mk                      make_pair
#define pb                      push_back
#define ff                      first
#define ss                      second
#define PI                      acos(-1.0)

#define pf                      printf
#define sc                      scanf
#define Mod                     1000000007
#define hiii                    1e9//1000000000
#define looo                   -1e9//-1000000000
#define NMAX                    100005



string s , t ;
LL len , sum ;


//ll bigmod(ll N,ll P,ll Mod)//N=base P=power
//{
//    if(P==0) return 1;
//    if(P%2==0)
//    {
//        ll ret=bigmod(N,P/2,Mod);
//        return ((ret%Mod)*(ret%Mod))%Mod;
//    }
//    else return ((N%Mod)*(bigmod(N,P-1,Mod)%Mod))%Mod;
//
//}

LL cnt ;
vector<LL>v ;

LL fun(LL n)
{
    return (n*(n+1))/2 ;
}

void solve()
{

    for(int i = 0 ; i<len ; i++){
        cnt = 1 ;
        if(s[i] == s[i]){
            while(s[i] == s[i+1] && i<len ){
                cnt ++ , i++ ;
            }
            v.pb(cnt) ;
        }
    }

    for(int i = 0 ; i<v.size() ; i+=2){
        if(i+1 == v.size())sum+=fun(v[i]);
        else{
            sum+=fun(max(v[i], v[i+1]));
            sum+=fun(min(v[i], v[i+1])-1);
        }
    }
    cout << sum <<endl ;
}

int main()
{

        cin >> s ;

        cnt = 0 ;
        while(s.back() == '<'){
            cnt ++ ;
            s.pop_back();
        }
        sum+=fun(cnt) ;

        reverse(s.begin() , s.end());

        cnt = 0 ;
        while(s.back() == '>'){
            cnt++;
            s.pop_back();
        }
        sum+=fun(cnt) ;

        reverse(s.begin() , s.end());


        len = s.size() ;
        solve() ;


//cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;
return 0;
}




Measured memory_bytes: 3068
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

#[allow(unused_macros)]
macro_rules ! vec_md { ( $ init : expr ; $ ( $ dim : expr ) ;* ) => { vec_md ! ( $ ( $ dim ) ;* => $ init ) } ; ( $ head : expr ; $ ( $ tail : expr ) ;* => $ init : expr ) => { vec ! [ vec_md ! ( $ ( $ tail ) ;* => $ init ) ; $ head ] } ; ( $ head : expr => $ init : expr ) => { vec ! [ $ init ; $ head ] } ; }

fn main() {
    input! {
        n: usize, m: usize,
        ab: [(usize1, usize1); m]
    }

    let mut g = vec![vec![];n];
    for i in 0..ab.len() {
        let (a, b) = ab[i];
        g[a].push(b);
        g[b].push(a);
    }

    let mut dp = vec_md![None;1<<n;n];
    println!("{}", rec(&mut dp, &g, 1, 0, n));
}

fn rec(dp: &mut Vec<Vec<Option<u64>>>, g: &[Vec<usize>], mask: usize, cur: usize, n: usize) -> u64 {
    if let Some(src) = dp[mask][cur] {
        return src;
    }
    if mask == (1 << n) - 1 {
        return 1;
    }

    let mut ret = 0u64;
    for &v in &g[cur] {
        if mask >> v & 1 == 0 {
            ret += rec(dp, g, mask | (1 << v), v, n);
        }
    }
    dp[mask][cur] = Some(ret);
    ret
}

Measured memory_bytes: 4352
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int K = scan.nextInt();
		int A = scan.nextInt();
		int B = scan.nextInt();
		int num = 0;

		for (int i = A; i <= B; i++){
			if (i % K == 0){
				num += 1;
			}
		}
		if (num > 0){
			System.out.println("OK");
		}else if (num == 0){
			System.out.println("NG");
		}
	}
}

Measured memory_bytes: 35856
# DP
mod = 10 ** 9 + 7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

if N == 1:
    print(1)
    exit()
if N == 2:
    if M == 0:
        print(2)
    if M == 1:
        print(1)
    exit()

safe = [True] * (N+1)
for i in range(M):
    safe[A[i]] = False 

dp = [0] * (N+1)
dp[0] = 0
dp[1] = 1
dp[2] = 2

if 1 in A:
    dp[1] = 0
    dp[2] = 1
if 2 in A:
    dp[2] = 0

for i in range(3, N+1):
    if safe[i]:
        dp[i] = dp[i-1] + dp[i-2]

##print(dp)
print((dp[N]+mod)%mod)

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

int f(const int64_t& a, const int64_t& b)
{
  int64_t larger = a > b ? a : b;
  int count = 0;
  while (larger != 0)
  {
    ++count;
    larger /= 10;
  }
  return count;
}
int main()
{
  int64_t n;
  std::cin >> n;
  int minF = 10;
  for (int64_t a = 1; a <= n && a <= 100000; ++a)
  {
    if (n % a != 0) continue;
    int64_t b = n / a;
    minF = std::min(minF, f(a, b));
  }
  std::cout << minF << std::endl;
  return 0;
}

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 ll long long
#define pii pair<int,int>
#define pll pair<ll int,ll int>
#define pb push_back
#define sbit __builtin_popcount
#define vec vector <int>
#define vecp vector <pii>
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define bg begin()
#define en end()
#define endl "\n"
#define ff first
#define ss second
#define sz(a) (int)a.size()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define sp(x) setprecision(x)
#define fill(a,b) memset(a,b,sizeof(a))
#define fr(i,n) for(int i=0;i<n;i++)
#define rp(i,a,b) for(int i=a;i<b;i++)
#define rr(i,a,b) for(int i=a;i>=b;i--)
#define ft(it,x) for(auto it : x)
#define dbg(x) cerr<<#x<<" "<<x<<endl;
#define dbga(arr,n) cerr<<#arr<<": "; rep(tt,0,n)cerr<<arr[tt]<<" "; cerr<<endl;
#define mapi map<int,int>
#define mapl map<ll int,ll int>
#define val_at(x) find_by_order(x)
#define idx_of(x) order_of_key(x)
#define scni(x) scanf("%d",&x)
#define prt(x) printf("%d\n",x)
#define test(t) int t;cin>>t;while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int mod=1e9+7;
const int mex=1e6+1;
inline ll power(ll a,ll b)
{
    ll ans=1,temp=a;
    while(b!=0)
    {
        if(b&1)
        ans=ans*temp;
        ans=ans%mod;
        temp=temp*temp;
        temp=temp%mod;
        b/=2;
    }
    return ans;
}
int pr[mex];
vec prime;
inline void seive()
{
    rp(i,2,mex) pr[i]=1;
    for(int i=2;i*i<mex;i++)
    {
        if(pr[i])
        for(int j=i*i;j<mex;j+=i)
        pr[j]=0;
    }
    vec prime;
    rp(i,2,mex)
    {
        if(pr[i]) prime.pb(i);
    }
}
ll int xx,xy,d1;
void exeu(ll int a1,ll int b1)
{
    if(b1==0)
    {
        xx=1;
        xy=0;
        d1=a1;
    }
    else
    {
        exeu(b1,a1%b1);
        ll int temp=xx;
        xx=xy;
        xy=temp-(a1/b1)*xy;
    }
}
ll int modinv(ll int A,ll int M)
{
    exeu(A,M);
    return (xx%M+M)%M;
}
int main()
{
    fast
    string s1,s2;
    cin>>s1>>s2;
    int x,y;
    cin>>x>>y;
    string s3;
    cin>>s3;
    if(s1==s3) x--;
    else y--;
    cout<<max(0,x)<<" "<<max(0,y);
    return 0;
}

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

using namespace std;

#define arr array
#define ll long long
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#define dump(x) cerr << #x " = " << x << endl

bool is_lowercase(char c) {
  return c>='a'&&c<='z';
}
bool is_uppercase(char c) {
  return c>='A'&&c<='Z';
}

char to_lowercase(char c) {
//  assert(is_uppercase(c));
  if (is_lowercase(c))
    return c;
  return c-'A'+'a';
}

char to_uppercase(char c) {
//  assert(is_lowercase(c));
  if (is_uppercase(c))
    return c;
  return c-'a'+'A';
}

char switch_case(char c) {
  if (is_uppercase(c)) {
    return to_lowercase(c);
  } else {
    return to_uppercase(c);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  constexpr char endl = '\n';

  int money;
  cin >> money;

  ll b=money/500;
  money%=500;
  ll s=money/5;
  ll ans=b*1000+s*5;

  cout << ans << endl;


  return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define rep(i, n) REP(i, 0, n)
const int INF=1e9;
const int MAX=100005;
const int MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define ALL(v) v.begin(), v.end()
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbgmap(mp) for (auto i = mp.begin(); i != mp.end(); ++i) { cout << i->first <<":"<<i->second << endl;}
#define fi first
#define se second
#define sum(v) accumulate(ALL(v),0)


template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

struct UnionFind{
    Vec par;
    Vec sz;
    Vec rank;
    UnionFind(ll n):par(n),sz(n),rank(n){
        rep(i,n){
            par[i]=i;
            sz[i]=1;
            rank[i]=0;
        }
    }
    ll root(ll x){
        if(par[x]==x){
            return x;
        }else{
            return root(par[x]);
        }
    }

    void unite(ll x, ll y){
        x = root(x);
        y = root(y);
        if(rank[x]<rank[y]){
            par[x]=y;
            sz[y]+=sz[x];
        }else{
            par[y]=x;
            sz[x]+=sz[y];
            if(rank[x]==rank[y]){
                rank[x]++;
            }
        }
    }

    bool same(ll x, ll y){
        return root(x)==root(y);
    }

    ll size(ll x){
        return sz[root(x)];
    }
};

ll dp[2004][2004];
ll sum[2004][2004];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;

    cin>>n>>m;
    Vec s(n+1);
    Vec t(m+1);
    rep(i,n){
        cin>>s[i+1];
    }
    rep(i,m){
        cin>>t[i+1];
    }
    ll ans=0;



    dp[0][0]=0;
    sum[0][0]=0;
    sum[1][0]=0;
    sum[0][1]=0;

//    dbg(s);
//    dbg(t);
    rep(i,n){
        rep(j,m){
            if(s[i+1]==t[j+1]){
                dp[i+1][j+1]= sum[i][j]+1;
                dp[i+1][j+1] %= MOD;
            }else{
                dp[i+1][j+1]=0;
            }
            sum[i+1][j+1] = (sum[i][j+1]+sum[i+1][j]+dp[i+1][j+1]-sum[i][j]+MOD);
            sum[i+1][j+1] %= MOD;
//            dbg(i);
//            dbg(j);
//            dbg(dp[i+1][j+1]);
//            dbg(sum[i+1][j+1]);
        }
    }
   // dbg(sum[n][m]);

    cout<<(sum[n][m]+1)%MOD<<endl;
    return  0;
}


Measured memory_bytes: 62976
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define REP(i,x,n) for(int i = (x); i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);

int main(void)
{
    ll n;
    cin >> n;
    vector<ll> x(n), s;
    rep(i,n) cin >> x[i];
    s = x;
    sort(all(s));
    rep(i,n){
        ll b;
        if(x[i] < s[n/2]) b = s[n/2];
        else b = s[n/2-1]; 
        cout << b << endl;
    }
    return 0;
}


Measured memory_bytes: 6380
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
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;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int n; cin >> n;
    map<ll, ll> m;
    ll ans = 0;
    rep(i,n) {
        int a; cin >> a;
        m[a]++;
        ans += a;
    }
    int q; cin >> q;
    vector<int> b(q), c(q);
    rep(i,q) {
        cin >> b[i] >> c[i];
    }
    rep(i,q) {
        ans = ans - m[b[i]]*b[i] + m[b[i]]*c[i];
        m[c[i]] += m[b[i]];
        m[b[i]] = 0;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 10088
Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

composite_number = [False] * (100001)
for i in range(2, 100001):
    if not composite_number[i]:
        for j in range(i+i, 100001, i):
            composite_number[j] = True
    
similar_number = [0] * 100001
for i in range(3, 100001, 2):
    if not composite_number[i] and not composite_number[(i+1)/2]:
        similar_number[i] += 1

for i in range(3, 100001):
    similar_number[i] += similar_number[i-1]

for l, r in query:
    print similar_number[r] - similar_number[l-1]




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

long long table[16][1024];
const int MARGIN = 1;

int main(void) {
	int n, s;

	for(int i = 0; i < 16; i++)
		for(int j = 0; j < 1024; j++)
			table[i][j] = 0;

	for(int i = 0; i < 101; i++) {
		for(int j = 10; j > 1; j--) {
			for(int k = 1000; k >= 0; k--) {
				if(k - i >= 0)
					table[MARGIN + j][MARGIN + k] += table[MARGIN + j - 1][MARGIN + k - i];
			}
		}
		table[MARGIN + 1][MARGIN + i] = 1;
	}
/*
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < 10; j++)
			printf("% 3lld", table[MARGIN + i][MARGIN + j]);
		cout << endl;
	}
// */

	while(cin >> n >> s, n || s)
		cout << table[n + MARGIN][s + MARGIN] << endl;

	return 0;
}

Measured memory_bytes: 1288
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>

using namespace std;

/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
*/

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll h, w, k;
    cin >> h >> w >> k;
    vector<string> c(h);
    rep(i, h) cin >> c[i];
    ll ans = 0;
    for(ll i = 0; i < (1 << h); i++) {
        for(ll j = 0; j < (1 << w); j++) {
            ll cnt = 0;
            for(ll i2 = 0; i2 < h; i2++) {
                for(ll j2 = 0; j2 < w; j2++) {
                    if(!(i & (1 << i2))) continue;
                    if(!(j & (1 << j2))) continue;
                    if(c[i2][j2] == '.') continue;
                    cnt++;
                }
            }
            if(cnt == k) ans++;
        }
    }
    cout << ans << endl;
    return;
}

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

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

using namespace std;

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

    vector<int> R(N);

    for(int i=0; i<M; i++){
        int a,b; cin >> a >> b;
        R.at(a-1)++;
        R.at(b-1)++;
    }

    for(int i=0; i<N; i++){
        cout << R.at(i) << endl;
    }
    }

Measured memory_bytes: 3628
function main(input) {
    s = input[0];
    var i,k,count,ans=0;
    for(i=0; i<s.length; i++) {
        count=0
        for(k=i; k<s.length; k++) {
            if(s[k]=='A'||s[k]=='C'||s[k]=='G'||s[k]=='T')count++;
            else break;
        }
        ans=Math.max(ans,count);
    }
    console.log(ans);
}
main(require("fs").readFileSync("/dev/stdin", "utf8").split('\n'));

Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using Lint=long long;

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

    const int MAX=1e5;
    vector<bool> dp(MAX+1);
    dp[0]=true;
    for(int i=0;i<=5;i++){
        int a=100+i;
        for(int i=0;i+a<=MAX;i++) if(dp[i]) dp[i+a]=true;
    }

    int X; cin>>X;
    cout<<dp[X]<<endl;
    return 0;
}

Measured memory_bytes: 256
import heapq
x, y, z, w = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

q = []
ans = []
flag = []
first = [A[0] + B[0] + C[0], [0, 0, 0]]
heapq.heappush(q, first)
flag.append(first[1])
for h in range(w):
    max_ans = heapq.heappop(q)
    ans.append(abs(max_ans[0]))
    i, j, k = max_ans[1]

    if i == x-1:
        lst1 =  [-A[i]-B[j]-C[k], [i, j, k]]
    else:
        lst1 =  [-A[i+1]-B[j]-C[k], [i+1, j, k]]
    if lst1[1] not in flag:
        heapq.heappush(q, lst1)
        flag.append(lst1[1])

    if j == y-1:
        lst2 = [-A[i]-B[j]-C[k], [i, j, k]]
    else:
        lst2 = [-A[i]-B[j+1]-C[k], [i, j+1, k]]
    if lst2[1] not in flag: 
        heapq.heappush(q, lst2)
        flag.append(lst2[1])

    if k == z-1:
        lst3 = [-A[i]-B[j]-C[k], [i, j, k]]
    else:
        lst3 = [-A[i]-B[j]-C[k+1], [i, j, k+1]]
    if lst3[1] not in flag:
        heapq.heappush(q, lst3)
        flag.append(lst3[1])
    
    print(ans[h])

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

int main() {
  int A, B;
  cin >> A >> B;
  
  if (A != 1 && B != 1 && A > B) {
    cout << "Alice" << endl;
  } else if (A != 1 && B != 1 && A < B) {
    cout << "Bob" << endl;
  } else if (B == 1 && A > B) {
    cout << "Bob" << endl;
  } else if (B == 1 && A < B) {
    cout << "Bob" << endl;
  } else if (A == 1 && A > B) {
    cout << "Alice" << endl;
  } else if (A == 1 && A < B) {
    cout << "Alice" << endl;
  } else if (A == B) {
    cout << "Draw" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, Y;
  cin >> N >> Y;
  
  int num10000 = -1, num5000 = -1, num1000 = -1;
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N - i; j++) {
      int sum = 10000 * i + 5000 * j + 1000 * (N - i - j);
      if (sum == Y) {
        num10000 = i;
        num5000 = j;
        num1000 = N - i - j;
        break;
      }
    }
  }
  cout << num10000 << ' ' << num5000 << ' ' << num1000;
}


Measured memory_bytes: 256
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

alias sread = () => readln.chomp();
ulong MOD = 1_000_000_007;
ulong INF = 1_000_000_000_000;
alias SugarWater = Tuple!(long, "swater", long, "sugar");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void main()
{
    long n, a, b, c;
    scan(n, a, b, c);
    auto takematsu = only(n, a, b, c);
    auto l = new long[](n);
    foreach (ref e; l)
        e = lread();
    long mincost = INF;
    foreach (i; 0 .. (1 << n * 2))
    {
        auto len = new long[](4);
        auto cost = new long[](4);
        auto fbits = i.fourbitary(n);
        foreach (j, e; fbits)
        {
            len[e] += l[j];
            cost[e] += 10;
        }
        if (!(len[1] * len[2] * len[3]))
            continue;

        cost[] -= 10;
        foreach(j; iota(len.length))
            cost[j] += abs(len[j] - takematsu[j]);

        mincost = min(cost.sum - cost[0], mincost);
    }
    mincost.writeln();
}

auto fourbitary(long n, long disit)
{
    auto fbits = new long[](disit);
    long tmp;
    while (n > 0)
    {
        fbits[tmp++] = n % 4;
        n = n >> 2;
    }
    return fbits;
}

Measured memory_bytes: 1276
import java.util.Scanner;
import java.util.Arrays;
public class Main{
	
	public static void main(String[] args){
		
		Scanner scan = new Scanner (System.in);
		
		long[] a = new long[3];
		
		a[0] = scan.nextInt();
		a[1] = scan.nextInt();
		a[2] = scan.nextInt();
		
		if((a[0]%2==0)||(a[1]%2==0)||(a[2]%2==0)){
			System.out.println("0");
		} else {
			Arrays.sort(a);
			System.out.println(a[0]*a[1]);
		}
	}
}

Measured memory_bytes: 9552
#include<bits/stdc++.h>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll INF = 1LL << 30;

int main(void){
    ll N, K , Q; cin >> N >> K >> Q;
    vector<ll> A(Q);
    map<ll,ll> mp;
    for(int i = 1; i <= N; i++){
        mp[i] = 0;
    }
    for(int i = 0; i < Q; i++){
        ll A; cin >> A;
        mp[A]++;
    }
    
    for(int i = 1; i <= N; i++){
        ll now = K - Q + mp[i];
        if(now <= 0) cout << "No" << "\n";
        else cout << "Yes" << "\n";
    }
}


Measured memory_bytes: 7680
n = int(input())
A = list(map(int, input().split()))

cnt = 0
money = 1000
b = 0
for i in range(n-1):
    if cnt == 0 and A[i] < A[i+1]:
        cnt += money//A[i]
        money %= A[i]
        b = A[i]
    else:
        money += cnt * A[i]
        cnt = 0
        if A[i] < A[i+1]:
            cnt += money//A[i]
            money %= A[i]
            b = A[i]
if cnt > 0:
    money += cnt * max(b, A[-1])
print(money)

Measured memory_bytes: 9096
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int ans = 1;
    int f = 0; // 0:不確定，1:非減少，2:非増加
    REP(i, N-1){
        if(A[i]==A[i+1]) continue;
        
        if(f == 0){
            if(A[i] < A[i+1]) f = 1;
            if(A[i] > A[i+1]) f = 2;
        }else if(f == 1){
            if(A[i] > A[i+1]){
                f = 0;
                ans++;
            }
        }else if(f == 2){
            if(A[i] < A[i+1]){
                f = 0;
                ans++;
            }
        }
    }

    pr(ans);
}

Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>//辞書順はnext_permutation
#include<set>
#include<string>
#include<string.h>
#include<time.h>
#include<random>
#include<cmath>
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<utility>//swap(数値交換)
#define rt "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define sort(s) sort(s.begin(),s.end())
#define reve(s) reverse(s.begin(),s.end())
#define asas int ans=0
#define cncn int cnt=0
#define please return
#define AC 0

using namespace std;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vcha;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;

//最大公約数（GCD）を求めるよ
//最小公倍数（LCM）は＜＜　（A＋B）÷ GCD　 ＞＞で求まるよ

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}


int main(void) {
	int a, b;
	cin >> a >> b;
	cncn;
	cnt = b * 2 + 1;//一人が監視する木の本数
	if (a % cnt == 0)cout << a / cnt << rt;
	else cout << a / cnt + 1 << rt;
	please AC;
}

// abc : 141 , aoj : ITP1_6_D
//sort, abs, swap, reverse, max, min
//__gcd, sbstring, erase, push_back,stoll、stoi

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,s=0,m;cin>>n;m=n;
  while(true){
    s+=m%10;
    m=m/10;
    if(m==0)break;
  }
  if(n%s==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}
  
      


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int dp[1001],N,v[1001],w[1001],W;
signed main(){
    for(int num=1;;num++){
        cin>>W;
        if(W==0)break;
        cin>>N;
        for(int i=0;i<N;i++){
            scanf("%lld,%lld",&v[i],&w[i]);
        }
        fill(dp,dp+1001,0);
        for(int i=0;i<N;i++){
            for(int j=W;j>=w[i];j--){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        for(int i=W;i>=0;i--){
            if(dp[W]!=dp[i]){
                cout<<"Case "<<num<<":"<<endl<<dp[W]<<endl<<i+1<<endl;
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1268
#include<bits/stdc++.h>                                                                                               
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;

signed main(){
    int h,w;
    cin >> h >> w;
    string s;
    rep(i,h){
        cin >> s;
        cout << s << '\n' << s << '\n';
    }   
    return 0;
}


Measured memory_bytes: 256
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        a: usize,
        b: usize,
    }

    println!("{}", if a>= 13 {b} else if a>= 6 {b/ 2} else {0});
}


Measured memory_bytes: 4352
s=input()
s1=int(s[0]+s[1])
s2=int(s[2]+s[3])
if (0<s1<13)and(0<s2<13):
    print("AMBIGUOUS")
elif (0<s1<13):
    print("MMYY")
elif (0<s2<13):
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 9184
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <sstream>
#include <deque>
#include <memory.h>
#include <cassert>
#include <ctime>
#include <time.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
#define FILE "file"
#define lc v << 1
#define rc (v << 1) + 1
#define inf 1e+9
#define linf ll(1e+18)
#define classname SubtreeSumHash

const ll mod = 1e+9 + 7;
const int maxn = 1000000 + 5;
ll f[maxn];

void solve()
{
    ll n;
    cin >> n;
    ll s = 0;
    f[1] = n;
    f[2] = n * n;
    for(int i = 3; i <= n; i++)
    {
        if(i > 3)
        {
            s += f[i - 3];
            s %= mod;
        }
        f[i] = f[i - 1] + (n - 1) * (n - 1) + s + (n - i + 2);
        f[i] %= mod;
    }
    cout << f[n] << "\n";
}

void gcj()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        cout << "Case #" << i + 1 << ": ";
        solve();
        cout << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);
    //freopen(FILE ".in", "r", stdin);freopen(FILE ".out", "w", stdout);
    //gcj();
    solve();
    return 0;
}


Measured memory_bytes: 8064
#include <iostream>
#include <vector>
using namespace std;
using Int = long long;
template <typename T1, typename T2>
inline void chmin(T1 &a, T2 b)
{
    if (a > b)
        a = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &a, T2 b)
{
    if (a < b)
        a = b;
}

//INSERT ABOVE HERE
signed main()
{
    Int n, m;
    cin >> n >> m;
    vector<Int> cnt(n + 1, 0);
    for (Int i = 0; i < m; i++)
    {
        Int l, r;
        cin >> l >> r;
        l--;
        cnt[l]++;
        cnt[r]--;
    }
    for (Int i = 0; i < n; i++)
        cnt[i + 1] += cnt[i];

    Int ans = 0;
    for (Int i = 0; i < n; i++)
        ans += cnt[i] == m;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

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

double dp[305][305][305] = {0.0};

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

    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    vector<int> x(N);
    vector<int> y(M);
    REP(i, N) { cin >> x.at(i); }
    REP(i, M) { cin >> y.at(i); }

    FOR(z, *max_element(ALL(x)) + 1, *min_element(ALL(y)) + 1) {
        if (X < z && z <= Y) {
            cout << "No War" << endl;
            return 0;
        }
    }

    cout << "War" << endl;

    return 0;
}


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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const int maxd = 1010;

int cnt[maxd][maxd];
int r[3][maxd * 2][maxd * 2];

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

	rep(i, N) {
		int x, y;
		cin >> x >> y;
		++cnt[x % D][y % D];
	}

	int mx = 0;

	rep(i, D) {
		rep(j, D) {
			chmax(mx, cnt[i][j]);
		}
	}

	int p = 0;
	while ((p + 1) * (p + 1) < mx) ++p;

	for (int i = 0; i < maxd * 2 - 1; ++i) {
		for (int j = 0; j < maxd * 2 - 1; ++j) {
			int x = cnt[i % D][j % D];
			rep(k, 3) {
				r[k][i+1][j+1] = r[k][i+1][j] + r[k][i][j+1] - r[k][i][j];
			}
			if (x <= p * p) {
				++r[0][i+1][j+1];
			}
			if (x <= p * (p+1)) {
				++r[1][i+1][j+1];
			}
			if (x <= (p+1) * (p+1)) {
				++r[2][i+1][j+1];
			}
		}
	}

	auto valid = [&](int a, int b, int c, int d, int k) {
		if (!(a <= c && b <= d)) return true;
		int num = r[k][c+1][d+1] - r[k][c+1][b] - r[k][a][d+1] + r[k][a][b];
		return num == (c - a + 1) * (d - b + 1);
	};

	int ans = TEN(9);

	rep(i, D) {
		rep(j, D) {
			auto ok = [&](int x) {
				int t = p * D + x;
				if (!valid(i, j, i + x, j + x, 2)) {
					return 0;
				}
				if (!valid(i + x + 1, j, i + D - 1, j + x, 1)) {
					return 0;
				}
				if (!valid(i, j + x + 1, i + x, j + D - 1, 1)) {
					return 0;
				}
				if (!valid(i + x + 1, j + x + 1, i + D - 1, j + D - 1, 0)) {
					return 0;
				}
				return 1;
			};

			int lo = 0, hi = D;
			if (ok(lo)) {
				hi = 0;
			}

			while (hi - lo > 1) {
				int m = (lo + hi) / 2;
				if (ok(m)) {
					hi = m;
				} else {
					lo = m;
				}
			}
			chmin(ans, p * D + hi);
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 51968
#include <iostream>
#define ll long long
#include <vector>
#include <algorithm>
using namespace std;

ll n;
vector<ll> a;

int main(){
  int inp;
  ll result;
  
  cin >> n;
  for(ll i=0;i<n*3;i++){
    cin >> inp;
    a.push_back(inp);
  }
  sort(a.begin(),a.end());


  result =0;
  for(ll i = 0;i<n;i++){
    result+=a[a.size()-2*(i+1)];
  }

  cout << result <<  endl;
  return 0;
}


Measured memory_bytes: 6512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		char[] marks = {'S', 'H', 'C', 'D'};
		for(char mark : marks) {
			for (int i = 1; i <= 13; i++) {
				Card.allCards.add(new Card(mark, i));
			}
		}

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			String[] str = br.readLine().split(" ");
			Iterator<Card> itr = Card.allCards.iterator();
			while (itr.hasNext()) {
				Card tmp = itr.next();
				if (tmp.mark != str[0].charAt(0)) {
					continue;
				}
				if (tmp.rank == Integer.parseInt(str[1])) {
					itr.remove();
				}
			}
		}

		for (Card card : Card.allCards) {
				System.out.println(card.mark + " " + card.rank);
		}
	}
}

class Card {
	char mark;
	int rank;
	static List<Card> allCards = new ArrayList<Card>();

	Card(char mark, int rank) {
		this.mark = mark;
		this.rank = rank;
	}
}

Measured memory_bytes: 16948