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

using ll = long long;
constexpr int INF = 1e9;

using pdd = pair<double, double>;
using pii = pair<int, int>;

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

// (M, xsum);
pdd solve(int y, int x, vector<string> const& v, vector<vector<bool>>& visited, bool& res) {
    queue<pii> que;
    que.push(make_pair(y, x));
    visited[y][x] = true;
    const char color = v[y][x];
    const int H = v.size();
    const int W = v[0].size();
    double minx = 1e9, maxx = -1e9;
    double aboveM = 0, aboveX = 0;
    double nowM = 0, nowX = 0;
    while(!que.empty()) {
        pii p = que.front();
        que.pop();
        if(p.first == 0 || v[p.first-1][p.second] != '.' && v[p.first-1][p.second] != color) {
            minx = min(minx, (double)p.second);
            maxx = max(maxx, (double)p.second+1);
        }
        nowM += 1;
        nowX += p.second + 0.5;
        for(int i=0; i<4; ++i) {
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || v[ny][nx] == '.' || visited[ny][nx]) {
                continue;
            }
            if(ny < H && ny == p.first+1 && !visited[ny][nx] && v[ny][nx] != color) {
                auto t = solve(ny, nx, v, visited, res);
                aboveM += t.first;
                aboveX += t.second;
            }
            if(v[ny][nx] == color) {
                que.push(make_pair(ny, nx));
                visited[ny][nx] = true;
            }
        }
    }
    double totalX = aboveX + nowX;
    double totalM = aboveM + nowM;
    double g = totalX / totalM;
    res &= (minx < g && g < maxx);
    return make_pair(totalM, totalX);
}


int main() {
    int W, H;
    while(cin >> W >> H, W) {
        vector<string> v(H);
        for(int i=0; i<H; ++i) {
            cin >> v[H-i-1];
        }
        bool res = true;
        vector<vector<bool>> visited(H, vector<bool>(W));
        for(int i=0; i<H; ++i) {
            for(int j=0; j<W; ++j) {
                if(v[i][j] != '.' && !visited[i][j]) {
                    solve(i, j, v, visited, res);
                }
            }
        }
        if(res) {
            cout << "STABLE" << endl;
        } else {
            cout << "UNSTABLE" << endl;
        }
    }
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set

using namespace std;

const ll MOD = 1000000007;

int main() {
  ll n, a, b;
  scanf("%lld %lld %lld", &n, &a, &b);

  ll x = n / (a + b);
  ll y = n % (a + b);

  ll ans = 0;
  ans += x * a;

  if (y <= a) {
    ans += y;
  } else {
    ans += a;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, n) for(ll i = 0; i < n; i++)
#define FORR(i, n) for(ll i = n; i >= 0; i--)
#define FORS(i, m, n) for(int i = m;i < n;i++)
#define ALL(v) accumulate(v.begin(),v.end(),0)
#define SORT(v) sort(v.begin(),v.end())
#define OUT(n) (cout << n << endl)
#define IN1(a) (cin >> a)
#define IN2(a,b) (cin >> a >> b)
#define IN3(a,b,c) (cin >> a >> b >> c)
#define IN4(a,b,c,d) (cin >> a >> b >> c >> d)
#define REVS(v) reverse(v.begin(),v.end())
#define PI 3.14159265359
using namespace std;
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll n,m,x,anscount,ncount,ans;
  ncount = 0;
  anscount = 0;
  ans = pow(10,7);
  cin >> n >> m >> x;
  vector<vector<int>> avec(n,vector<int>(m));
  vector<int> c(n);
  FOR(i,n){
    cin >> c[i];
    FOR(j,m){
      cin >> avec[i][j];
    }
  }
  bitset<13> bit;
  FOR(i,pow(2,n)){
    bit = i;
    FOR(j,m){
      FOR(k,n){
        if (bit.test(k) == true){
          ncount += avec[k][j];
        }
      }
      if (ncount < x){
        goto ENDD;
      }
      ncount = 0;
    }
    FOR(i,n){
      if (bit.test(i) == true){
        anscount += c[i];
      }
    }
    ans = min(ans,anscount);
    anscount = 0;
    ENDD:
    ncount = 0;
  }
  if (ans == 10000000){
    OUT("-1");
  }
  else
  {
    OUT(ans);
  }
  
  

}

Measured memory_bytes: 4056
//Abhinav ---IIIT_A
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define f(i,x,n) for(int i=x;i<(int)n;++i)
#define vpii vector<pair<int,int>> 
#define vi vector<int>
#define vpii vector<pair<int,int>> 
#define mpii map<pair<int,int>,int>
#define mpivpii map<int,vector<pair<int,int>>> 
#define pii pair<int,int> 
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define mpi map<int,int>
#define vvi vector<vector<int>>
#define vvvi vector<vvi>

ld pie=3.141592653589793238462643383279;
int mod=1e9+7;

vvi mat_mul(vvi mat1,vvi mat2){
  vvi ret;
  f(i,0,2){
    vi xx;
    f(j,0,2){
      int r=0;
      f(k,0,2) r=(r+(mat1[i][k]*mat2[k][j])%mod)%mod;
      xx.pb(r%mod);
    }
    ret.pb(xx);\
  }
  return ret;
}

vvi mat_exp(vvi mat,int p){
  vvi iden={{1,0},{0,1}};
  while(p!=0){
    if(p&1) iden=mat_mul(iden,mat);
    p/=2; 
    mat=mat_mul(mat,mat);
  }
  return iden;
}


int32_t main(){ 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
  int n; cin>>n;
  int ans=-1;
  if(n>=400 && n<=599){
    ans=8;
  }else if(n>=600 && n<=799){
    ans=7;
  }else if(n>=800 && n<=999){
    ans=6;
  }else if(n>=1000 && n<=1199){
    ans=5;
  }else if(n>=1200 && n<=1399){
    ans=4;
  }else if(n>=1400 && n<=1599){
    ans=3;
  }else if(n>=1600 && n<=1799){
    ans=2;
  }else {
    ans=1;
  }

  cout<<ans;
  return 0; 
}

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

char swi(char al){
  switch(al){
    case 'a':return 'A';
    case 'b':return 'B';
    case 'c':return 'C';
    case 'd':return 'D';
    case 'e':return 'E';
    case 'f':return 'F';
    case 'g':return 'G';
    case 'h':return 'H';
    case 'i':return 'I';
    case 'j':return 'J';
    case 'k':return 'K';
    case 'l':return 'L';
    case 'm':return 'M';
    case 'n':return 'N';
    case 'o':return 'O';
    case 'p':return 'P';
    case 'r':return 'R';
    case 's':return 'S';
    case 't':return 'T';
    case 'u':return 'U';
    case 'v':return 'V';
    case 'w':return 'W';
    case 'x':return 'X';
    case 'y':return 'Y';
    case 'z':return 'Z';
  }
}
int main(){
  string a,b,c;
  cin >> a >> b >> c;
  cout << swi(a.at(0)) << swi(b.at(0)) << swi(c.at(0)) << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        while (true) {
            int n = scanner.nextInt();
            if (n == 0) {
                break;
            }
            
            int[] input = new int[n];
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                input[i] = scanner.nextInt();
            }
            
            for (int i = 0; i < n; i++) {
                int sum = 0;
                for (int j = i; j < n; j++) {
                    sum += input[j];
                    if (sum > max) {
                        max = sum;
                    }
                }
            }
            System.out.println(max);
        }
    }
}

Measured memory_bytes: 26380
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
char s[1001];
int b[1001];
int memo[1001][8];
int dfs(int jun,int bit){
  int ret = 0;
  
  if(jun == n) return 1;
  if(memo[jun][bit] != -1) return memo[jun][bit];

  for(int i=1;i<=7;i++){
    if( (bit&i) != 0 && (b[jun]&i) != 0){
      ret += dfs(jun+1,i);
    }
  }
  
  return memo[jun][bit] = ret%10007;
}

int main(){
  
  fill_n(*memo,1001*8,-1);
  
  scanf("%d",&n);
  scanf("%s",&s);
  for(int i=0;i<n;i++){
    if(s[i] == 'J') b[i] = 4;
    if(s[i] == 'O') b[i] = 2;
    if(s[i] == 'I') b[i] = 1;
  }
  
  printf("%d\n",dfs(0,4));
 
  return (0);
}

Measured memory_bytes: 2808
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<functional>
#include<iostream>
#include<vector>
#include<cmath>
using namespace __gnu_pbds;
using namespace std;
typedef  tree<int, null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
  PBDS;
int main()
{  int n ;
 cin>>n;
   int activ[n][3];
    for(int a=0;a<n;a++) // getting the data...
    { for(int b=0;b<3;b++)
       { cin>>activ[a][b];
	   }
	}
	long long int dp[n][3];
	 dp[0][0]=activ[0][0];  dp[0][1]= activ[0][1];  dp[0][2]=  activ[0][2];
	   for(int a=1;a<n;a++)
	   {   dp[a][0]=  max(dp[a-1][1]+activ[a][0], dp[a-1][2]+activ[a][0] );
	       dp[a][1]=  max(dp[a-1][0]+ activ[a][1],  dp[a-1][2]+activ[a][1]);
	         dp[a][2]=  max(dp[a-1][1]+activ[a][2],  dp[a-1][0]+ activ[a][2]);
	   }
	    int maxim = max(max(dp[n-1][0],dp[n-1][1]), dp[n-1][2]);
	      cout<<maxim<<endl;
	      
return 0;
}


Measured memory_bytes: 3712
#include <cstdio>
#include <cstring>

long double solve(int n,long double a,long double d){
	if(!n) return 0;
	long double res=a+d*(2*n-1)/2;
	long double a1=(a*(n-1)*2+(a+2*d)+(3*a+3*d))/(2*n);
	long double a2=((a+d)*(2*(n-1)-1)+(a+3*d)*2+(3*a+6*d))/(2*n);
	return res+solve(n-1,a1,a2-a1);
}

int main(){
	int n;
	double a,d;
	scanf("%d%lf%lf",&n,&a,&d);
	printf("%.20lf\n",(double)solve(n,a,d));
}


Measured memory_bytes: 15744
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
  string s; cin >> s;
  if(s[0] == '9' || s[1] == '9') cout << "Yes";
  else cout << "No";
  return 0;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define boost ios::sync_with_stdio(false); cin.tie(0)
#define ll              long long int
#define ld              long double
#define mk              make_pair
#define pb              push_back
#define f               first
#define s               second
#define fo(i,a,b)       for(i=a;i<b;i++)
#define foe(i,a,b)      for(i=a;i<=b;i++)
#define all(x)          x.begin(),x.end()
#define vi              vector<int>
#define vl              vector <long long int>
#define pii             pair <int,int>
#define pll             pair <long long int, long long int>
#define vpii            vector< pair<int,int> >
#define vpll            vector < pair <long long int,long long int> >
#define MOD             1000000007
using namespace std;
const int inf = INT_MAX;
const ll inf64 = LLONG_MAX;


int main()
{
    boost;
    ll i,j;
    ll x;
    cin >> x;
    foe(i,-1000,1000)
    {
    	foe(j,-1000,1000)
    	if((i*i*i*i*i) - (j*j*j*j*j) == x)
    	{
    		cout << i << ' ' << j;
    		return 0;
    	}
    }
    
    return 0;
}

Measured memory_bytes: 3652
#148e
N = int(input())

if N%2 == 0:
    ans = 0
    
    for i in range(1,28):
        a = (5**i)*2
        b = N//a
        #print(i,a,b)

        if a > N:
            break

        ans += b
else:
    ans = 0
    
print(ans)

Measured memory_bytes: 2940
S = input()
T = input()
start = [-1] * 26
goal = [-1] * 26

for i in range(len(S)):
    start_index = ord(S[i]) - ord("a")
    goal_index = ord(T[i]) - ord("a")
    if start[start_index] != -1 or goal[goal_index] != -1:
        if start[start_index] != goal_index or goal[goal_index] != start_index:
            print("No")
            exit()
        else:
            continue
    start[start_index] = goal_index
    goal[goal_index] = start_index
print("Yes")
exit()
print(start, "\n", goal)


def transform_char(s):
    return chr(s+ord("a"))


print(list(map(transform_char, start)))


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

// # DEFINES # //
#define ll long long
#define M (ll)(1e9+7)
#define EPS 1e-9

using namespace std;

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


    ll a, b;

    cin >> a >> b;

    if(a == 1 && b == 1) {
        cout << "Yes" << endl;
    } else if(a == 2 && b == 2) {
        cout << "No" << endl;
    } else if(a == 1 && b == 3 || a == 3 && b == 1) {
        cout << "Yes" << endl;
    } else if(a == 3 && b == 3) {
        cout << "Yes" << endl;
    } else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
namespace mp = boost::multiprecision;

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


    if (abs(n - m) > 1) {
        cout << 0 << endl;
        return 0;
    }

    int higher = max(n, m);
    int lower = min(n, m);
    mp::cpp_int higher_sum = 1;
    mp::cpp_int lower_sum = 1;

    int limit = (int)pow(10, 9) + 7;

    for (int i = 1; i <= lower; i++) {
        lower_sum = lower_sum * i % limit;
    }

    if (n == m) {
        higher_sum = lower_sum;
    } else {
        higher_sum = higher * lower_sum;
    }

    mp::cpp_int result = higher_sum * lower_sum;

    if (n == m) {
        result *= 2;
    }

    result %= limit;

    cout << result << endl;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
w=pow(10,18)
p=1
a.sort()
if a[0]==0:
  print(0)
else:
  for k in range(n):
    p*=a[k]
    if p>w:
      print(-1)
      break
  if p<=w:
    print(p)

Measured memory_bytes: 21780
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
set<int>st;
int main() {
	int q;
	cin >> q;
	while (q--) {
		int Q, k;
		cin >> Q >> k;
		if (Q == 0) {
			st.insert(k);
			cout << st.size() << endl;
		}
		else if (Q == 1) {
			cout << st.count(k) << endl;
		}
		else if (Q == 2) {
			st.erase(k);
		}
		else {
			int y;
			cin >> y;
			auto nowitr = st.lower_bound(k);
			auto enditr = st.upper_bound(y);
			while (nowitr != enditr) {
				cout << *nowitr << endl;
				nowitr++;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 12436
#include <bits/stdc++.h>
#include <stdio.h>
#include <cmath>

using namespace std;

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

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

//階乗
int factorial(int k){
    int result=1;
    for (int i=1;i<=k;++i){
        result*=i;
    }
    return result;
}


int main() {
    int n;
    cin>>n;

    vector<int>a(n+1);
    rep(i,n-1){
        int A;
        cin>>A;

        a[A]++;
    }

    rep2(i,1,n){
        cout<<a[i]<<endl;
    }
}



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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, b, c, x;
	cin >> a >> b >> c >> x;
	int res = 0;
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				int total = 500 * i + 100 * j + 50 * k;
				if (total == x) {
					res++;
				}
			}
		}
	}
	cout << res << '\n';	
	
	return 0;
}


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

#define pout(n)  printf ("%d\n", n)

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)

const int d4x[4] = {1, 0, -1, 0};
const int d4y[4] = {0, 1, 0, -1};
const int d8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const int d8y[8] = { 0,1,1,1,0,-1,-1,-1 };

#define MAX_N (int)2e5+20

typedef long long ll;
using namespace std;

int a[3][3];
int main() {
	rep(i,0,3){
        rep(j,0,3){
			cin >> a[i][j];
		}
	}
	if (a[1][0] - a[0][0] == a[1][1] - a[0][1] &&
		a[1][1] - a[0][1] == a[1][2] - a[0][2] &&
		a[2][0] - a[1][0] == a[2][1] - a[1][1] && 
		a[2][1] -a[1][1]==a[2][2]-a[1][2]){
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
    return 0;
}

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 200010;
int N;
int a[MC],b[MC];

int BS(int x , int y , int t , int i){
	if(x-y<2) return x;
	int z = (x+y)/2;
	return (b[z] & (1<<i+1)-1) < t ? BS(x,z,t,i) : BS(z,y,t,i);
}

int solve(int x , int i){
	int p = (1<<i) - (x & (1<<i+1)-1);
	int q = p + (1<<i);
	return p < 0 ? N - BS(N,-1,p+(1<<i+1),i) + BS(N,-1,q,i) : BS(N,-1,q,i) - BS(N,-1,p,i);
}

int main(){
	cin >> N;
	repp(i,0,N) cin >> a[i];
	repp(i,0,N) cin >> b[i];
	int ans = 0;
	repp(i,0,29){
		sort(b,b+N,[&](const int &x , const int &y){return (x&(1<<i+1)-1) < (y&(1<<i+1)-1);});
		repp(k,0,N) if(solve(a[k],i)&1) ans ^= 1<<i;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define ld long double
#define pii pair<int, int>
using namespace std;    
const int N = int(3e5), mod = int(1e9)  + 7;
int n,a[N];

int main () {
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++){
		if(a[a[i]] == i) ans++;
	}
	cout << ans/2;

return 0;
}

Measured memory_bytes: 640
n, k = map(int, input().split())
dp = {}

dp[(0, 0, 0)] = 1

def perm(i, j, k):
  if (i, j, k) in dp:
    return dp[(i, j, k)]
  
  if i == 0 and (j is not 0 or k is not 0):
    return 0
  
  if i < 0 or j < 0 or k < 0 or i < j:
    return 0
  
  dp[(i, j, k)] = ((j+j+1)*perm(i-1, j, k-2*j)\
                + (j+1)*(j+1)*perm(i-1, j+1, k-2*j)\
                +  1*perm(i-1, j-1, k-2*j))%(10**9+7)
  return dp[(i, j, k)]

print(perm(n, 0, k))

Measured memory_bytes: 23788
import math

# 素因数分解
def prime_factorization(n):
    # s * s <= n
    s = math.floor(math.sqrt(n)) # 平方根を小数点切り捨て
    ans = [] # [素数, 指数]のリスト

    # 2からsまでの素因数を求める
    for i in [2] + list(range(3, s + 1, 2)):
        if n < i:
            break
        if n % i == 0:
            r = 0 # 指数カウンタクリア
            while n % i == 0:
                r += 1
                n //= i
            ans.append([i, r])

    # 残った素数を追加
    if n > s:
        ans.append([n, 1])

    return(ans)

def binomial_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: n choose k mod p
    '''
    k = min(k, n-k)

    if k == 0:
        retval = 1
    elif k == 1:
        retval = n
    else:
        numer = n  # n * (n - 1) * ... * (n - k + 1)
        inv = [0, 1]    # inv[i] : inverse of i mod p
        inv_denom = 1 # factorial of inverse of k mod p = 1^(-1) * 2^(-1) * ... * k^(-1) mod p
        for i in range(2, k + 1):
            numer = numer * (n - i + 1) % p
            inv.append(( inv[p % i] * (p - p//i) ) % p ) # inverse of i
            inv_denom = inv_denom * inv[-1] % p
        retval = numer * inv_denom % p

    return retval

###########################

N, M = [int(x) for x in input().split()]
q = 10 ** 9 + 7

if M == 1:
    ans = 1
else:
    pfact = prime_factorization(M)
    ans = 1
    for pr in pfact:
        ans = ans * binomial_p(N - 1 + pr[1], pr[1], q) % q

print(ans)


Measured memory_bytes: 3700
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int H, W;
    int i, j;

    cin >> H >> W;

    vector<vector<int>> dp(H, vector <int> (W, 0));

    vector <string> s(H);

    for(auto &a: s) cin >> a;

    for(i=0; i<H; i++) {
        for(j=0; j<W; j++) {
            if(i==0 && j==0) {
                dp[i][j] = (s[i][j] == '#');
            } else if(i==0) {
                dp[i][j] = dp[i][j-1] + (s[i][j] == '#' && s[i][j-1] != '#');
            } else if(j==0) {
                dp[i][j] = dp[i-1][j] + (s[i][j] == '#' && s[i-1][j] != '#');
            } else {
                dp[i][j] = min(dp[i][j-1] + (s[i][j] == '#' && s[i][j-1] != '#'), dp[i-1][j] + (s[i][j] == '#' && s[i-1][j] != '#'));
            }
        }
    }

    
    cout << dp[H-1][W-1] << endl;

    return 0;    

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
     int A, B;

     cin >> A >> B;

     if(A>B){
     	cout << (A*2)-1 << "\n";
     }
     else if(B>A){
     	cout << (B*2)-1 << "\n";
     }
     else{
     	cout << A+B << "\n";
     }
  
	return 0;
}

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

int main(void) {
    int N; cin >> N;
    vector<int> L(2*N);
    for (int i = 0; i < 2*N; i++) cin >> L[i];

    sort(L.begin(), L.end());
    int ans = 0;
    for (int i = 0; i < 2*N; i+=2) {
        ans += L[i];
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int vis[100005]={0};
int main()
{
    //int vis[100005]={0};
    int M=0,i=0,N=0;
    int a=0,b=0;
    scanf("%d",&N);
    scanf("%d",&M);
    while(i<M)
    {
        scanf("%d%d",&a,&b);
        vis[a]++;
        vis[b]++;
        i++;
    }
   for(i=0;i<=N;i++)
    {

    if(vis[i]%2!=0){
        printf("NO");
       break;
    }
    else if(i==N-1&&vis[N-1]%2==0)
    printf("YES");
    }

    return 0;
}


Measured memory_bytes: 512
#pragma region Macros

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

using ll = long long;
#define int ll
using vi = vector<int>;
using vvi = vector<vi>;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

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;
}

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

#pragma endregion

void Main() {
    string S, T;
    cin >> S >> T;

    int count = 0;
    REP(i, SIZE(S)) {
        if (S[i] != T[i]) {
            count++;
        }
    }

    cout << count;
}

#pragma region main
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main();
    cout << flush;
}
#pragma endregion


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

int main()
{
	int n;
	std::string s;
	int ans = 0;
	std::cin >> n;
	std::cin  >> s;
	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')
			ans++;
	}
	std::cout << ans << '\n';
}

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

typedef long long LL;

const int M=18,mod=1000000007;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}
int Power(int a,int k,int p=mod){int res=1;for (;k;k>>=1,smul(a,a,p)) if (k&1) smul(res,a,p);return res;}

int n,m,a[3];

void into(){
  scanf("%d%d%d%d",&n,&a[0],&a[1],&a[2]);
  a[1]+=a[0];m=max(a[2]+=a[1],10);
}

int dp[2][(1<<M)+9],old,now,ans;

void Get_dp(){
  old=1;now=0;
  dp[now][0]=1;
  for (int i=1;i<=n;++i){
	old^=1;now^=1;
	for (int g=0;g<1<<m;++g) dp[now][g]=0;
	for (int g=0;g<1<<m;++g)
	  for (int j=1;j<=10;++j){
		int t=(g&(1<<m-j)-1)<<j|1<<j-1;
		if (t>>a[0]-1&1&&t>>a[1]-1&1&&t>>a[2]-1&1) continue;
		sadd(dp[now][t],dp[old][g]);
	  }
  }
  for (int g=0;g<1<<m;++g) sadd(ans,dp[now][g]);
}

void work(){
  Get_dp();
}

void outo(){
  printf("%d\n",sub(Power(10,n),ans));
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 1280
#include<stdio.h>

#include<algorithm>


using namespace std ;



int main()
{
	int n ,k ;

	while( 1 )
	{
		scanf( "%d %d" ,&n ,&k ) ;


		if( !( n | k ) )
		{
			return 0 ;
		}


		int if_k = k - 1 ;

		int ans = -10001 ,other[ 100000 ] ;
		
		int sum = 0 ;

		int i ;
		for( i = 0 ; i < n ; ++i )
		{
			scanf( "%d" ,&other[ i ] ) ;

			sum += other[ i ] ;


			if( i > if_k )
			{
				sum -= other[ i - k ] ;
			}

			if( i >= if_k )
			{
				ans = max( ans ,sum ) ;
			}
		}


		printf( "%d\n" ,ans ) ;
	}
}

Measured memory_bytes: 3000
from itertools import accumulate

N = int(input())
A = list(map(int,input().split()))

mod = 10 ** 9 + 7

ruiseki = list(accumulate(A))
ans = 0
for i in range(N-1):
    ans += A[i] * (ruiseki[-1] - ruiseki[i])
    ans %= mod

print(ans)

Measured memory_bytes: 31224
import sys
import math
from collections import deque
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s, t = SL()

print(t + s)

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

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define INTMAX 1e9
using namespace std;
typedef long long ll;

string s;

int main(){
  std::cin >> s;
  int res = 700;
  rep(i,0,s.size()){
    if(s[i]=='o')res+=100;
  }
  std::cout << res << '\n';
}


Measured memory_bytes: 256
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    K, T = ZZ()
    A = ZZ()
    output = 0
    for a in A: output += max(0, a - (K - a + 2) + 1)
    print(output)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
using namespace std;

#define ll long long

void dfs(int key, vector<int> &u, vector<vector<int>> &c){
    for(int i=0; i<c[key].size(); ++i){
        if(u[c[key][i]]<1){
            u[c[key][i]]=u[key]+1;
            dfs(c[key][i], u, c);
        }
    }
}
int main() {
	int N; cin >> N;
	vector<vector<int>> v(N+1);
	for(int i=1; i<N; ++i){
	    int a, b;
	    cin >> a >> b;
	    v[a].push_back(b);
	    v[b].push_back(a);
	}
	vector<int> t(N+1, 0);
	t[1]=1;
	dfs(1, t, v);
	int now=1;
	for(int i=2; i<=N; ++i){
	    if(t[now]<t[i]) now=i;
	}
	for(int i=1; i<=N; ++i){
	    if(i==now) t[i]=1;
	    else t[i]=0;
	}
	dfs(now, t, v);
	int mx=0;
	for(int i=1; i<=N; ++i) mx=max(mx, t[i]);
	cout << (mx%3!=2 ? "First" : "Second") << endl;
	return 0;
}


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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N; cin>>N;
  vector<ll> height(N+10);
  rep(i,N) cin >> height[i+1];
  
  vector<ll> cost(N+10);
  cost[1]=0;
  cost[2]=abs(height[2]-height[1]);
  
  for(int i=1; i<=N; ++i) {
    cost[i+2] = min(cost[i]+abs(height[i+2]-height[i]) ,cost[i+1]+abs(height[i+2]-height[i+1]));
  }
  
  cout << cost[N] <<endl;
}

Measured memory_bytes: 1792
open System
open System.Collections.Generic

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f

    let readChars() = read string |> Seq.toArray
    let readInts() =
        readChars()
        |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

[<AutoOpen>]
module Cout =
    let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
    let print (s: string) = writer.Write s
    let println (s: string) = writer.WriteLine s
    let inline puts (s: ^a) = s |> string |> println

[<AutoOpen>]
module Util =
    let strRev (s: string): string =
        s
        |> Seq.rev
        |> Seq.map string
        |> String.concat ""

    let inline roundup (x: ^a) (y: ^a): ^a =
        let one = LanguagePrimitives.GenericOne
        (x + y - one) / y

    let inline sameParity (x: ^a) (y: ^a): bool =
        let one = LanguagePrimitives.GenericOne
        (x &&& one) = (y &&& one)

let f n = n * (n+1) / 2

let solve() =
    let s = readChars()

    let len = Array.length s
    let left = Array.zeroCreate (len+1)
    for i in 0..len-1 do
        if s.[i] = '<' then
            left.[i+1] <- left.[i] + 1L
        else
            left.[i+1] <- 0L
    let right = Array.zeroCreate (len+1)
    for i in len-1..-1..0 do
        if s.[i] = '>' then
            right.[i] <- right.[i+1] + 1L
        else
            right.[i] <- 0L

    seq {
        for i in 0..len do
            yield max left.[i] right.[i]
    }
    |> Seq.sum
    |> puts
    ()

[<EntryPoint>]
let main _ =
    try
        solve()
    with
    | e -> failwithf "%s" (e.ToString())
    writer.Close()
    0 // return an integer exit code


Measured memory_bytes: 25440
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define SW(x) setw(x) // 桁数指定
#define SF(c) setfill(c) // 埋め文字指定('0')
#define ALL(v) v.begin(), v.end()

int main(int argc, char const *argv[])
{
    ll n, c, k;
    cin >> n >> c >> k;
    map<ll, ll> m;
    for (ll i = 0; i < n; i++)
    {
        ll t;
        cin >> t;
        m[t]++;
    }
    vector<pair<ll, ll> > v;
    for (auto t : m)
    {
        v.push_back(t);
    }
    ll ans = 0;
    ll cnt = 0;
    ll lt = -1;
    for (ll t = 0; t < v.size(); t++)
    {   
        if(cnt > 0 && v[t].first > lt + k)
        {
            ans++;
            cnt = 0;
            lt = -1;
        }

        if (cnt + v[t].second < c)
        {
            cnt += v[t].second;
            if (lt < 0)
            {
                lt = v[t].first;
            }
            // continue;
        }
        else if(cnt + v[t].second == c)
        {
            ans++;
            cnt = 0;
            lt = -1;
            // continue;
        }
        else
        {
            v[t].second -= c - cnt;
            ans++;
            t--;
            cnt = 0;
        }
        // cout << ans << endl;
    }
    if (cnt > 0)
    {
        ans++;
    }
    cout << ans << endl;
}

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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

int main()
{
    int n;
    cin >> n;
    n=n*2;
    int ans = 0;
    vector<int> a(n);
    rep(i, n)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    for (int i = 1; i < n; i += 2)
    {
        ans += a[i];
    }
    cout << ans << endl;
    return 0;
}


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

int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}

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

ll lcm(ll a,ll b){
    a / gcd(a,b) * b;
}
const ll mod = 1e9 + 7;
const ll INF = 1e9 + 7;

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


/////////////////////////////////////////////////////////////////////////////////////////

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int sum = a + b + c;
    int m = max(a,max(b,c));
    int ans;
    if (3*m % 2 == sum % 2){
        ans = m;
    }
    else{
        ans = m + 1;
    }

    cout << (3*ans - sum) / 2 << endl;

}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int m1 = 10000, m2 = 5000, m3 = 1000;
    int N, Y;
    scanf("%d %d", &N, &Y);
    if (N * m1 < Y || N * m3 > Y) {
        printf("-1 -1 -1\n");
        return 0;
    }
    int c1 = Y / m1;
    for (int i = c1; i >= 0; --i) {
        for (int j = (Y - (i*m1)) / m2; j >= 0; --j) {
            if (i + j <= N && (i*m1 + j*m2 + (N-i-j)*m3 == Y)) {
                printf("%d %d %d\n", i, j, N - i - j);
                return 0;
            }
        }
    }
    printf("-1 -1 -1\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
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;}
const ll INF = 1LL << 60;

int main() {
    ll n, k; cin >> n >> k;
    vector<ll> a(n); rep(i, n) cin >> a[i];
    rep(i, n-k) {
        if(a[i] < a[i+k]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}


Measured memory_bytes: 4820
#include <iostream>

int main()
{
  std::string s;
  std::cin >> s;
  std::string ans;
  for (auto string : s)
  {
    if (string != 'B')
    {
      ans.push_back(string);
    }
    else
    {
      if (ans != "")
      {
        ans.pop_back();
      }
    }
  }
  std::cout << ans << std::endl;
  
  return 0;
}

Measured memory_bytes: 256
//HovalHaq!
#include <bits/stdc++.h>
using namespace std;
#define CTZ(i) __builtin_ctz(i)
typedef long long ll;

int main() {
	int n, m, k = -2; cin >> n >> m;
	ll l = 1, a;
	for(int i = 0; i < n; i++) {
		ll x; cin >> x;
		if(k == -2) k = CTZ(x);
		if(CTZ(x) != k) return cout << 0, 0;
		x = x >> CTZ(x);
		l = (l * x) / __gcd(l, x);
		if(l > m) return cout << 0, 0;
	}
	k--;
	if(k < 0) return cout << 0, 0;
	a = l << k;
	int c = m / a;
	cout << ((c / 2) + (c & 1));
}


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


class SaleData {
	private int price;
	private int amount;

	SaleData(int price, int amount){
		this.price = price;
		this.amount = amount;
	}

	public int getPrice() {
		return price;
	}

	public int getAmount() {
		return amount;
	}


}

public class Main {

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

	private static void sum_and_average() {
		ArrayList<SaleData> saledatas = new ArrayList<SaleData>();
		int sum = 0;
		double average = 0;

		while (sc.hasNext()) {
			String[] dat = sc.nextLine().split(",");
			saledatas.add( new SaleData(Integer.parseInt(dat[0]),
										Integer.parseInt(dat[1]) ) );
		}

		for (int i = 0; i < saledatas.size(); i++) {
			sum += saledatas.get(i).getAmount() * saledatas.get(i).getPrice();
			average += saledatas.get(i).getAmount();
		}

		System.out.printf("%d\n%d\n",sum, (int)Math.round( average / saledatas.size() ) );

	}

}



Measured memory_bytes: 26284
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#endif

using namespace std;


typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()) {
  v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t) {
  stringstream ss;
  ss << f;
  ss >> t;
}


#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back


#define MOD 1000000007LL
#define EPS 1e-8


int main() {
  int N;
  cin >> N;
  vint T(N);
  rep(i, N) {
    cin >> T[i];
  }
  int M;
  cin >> M;
  vint P(M), X(M);
  rep(i, M) {
    cin >> P[i] >> X[i];
    vint t(T);
    t[P[i] - 1] = X[i];
    int res = 0;
    rep(j, N) {
      res += t[j];
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Threading.Tasks;

namespace Insertion_Sort
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            var input = Console.ReadLine().Split(' ');
            int[] array = new int[input.Length];
            for (int i = 0; i < array.Length; ++i) array[i] = int.Parse(input[i]);
            for (int k = 0; k < array.Length - 1; ++k) Console.Write("{0} ", array[k]);
            Console.WriteLine(array[array.Length - 1]);
            Program.Insertion_Sort(ref array);
        }

        static void Insertion_Sort(ref int[] array)
        {
            for (int i = 1; i < array.Length; ++i)
            {
                int v = array[i];
                int j = i - 1;
                while (j >= 0 && array[j] > v)
                {
                    array[j + 1] = array[j];
                    --j;
                }
                array[j + 1] = v;
                for (int k = 0; k < array.Length - 1; ++k) Console.Write("{0} ",array[k]);
                Console.WriteLine(array[array.Length - 1]);
            }
        }
    }
}


Measured memory_bytes: 9196
#include <iostream>

int main () {
    int n;
    std::cin >> n;
    if(n < 10) {
        std::cout << n << std::endl;
    }
    else if (n < 100){
        std::cout << 9 << std::endl;
    }
    else if (n < 1000) {
        std::cout << n - 90 << std::endl;
    }
    else if (n < 10000) {
        std::cout << 909 << std::endl;
    }
    else if (n < 100000) {
        std::cout << n - 9090 << std::endl;
    }
    else{
        std::cout << 90909 << std::endl;
    }
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

ll mod(ll a){
  return (a % 1000000007);
}

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


int main(){
  string t; cin >> t;
  ll k = t.size();
  
  rep(i,k){
    if(t[i] == 'P') cout << 'P';
    else cout << 'D';
  }
  
  cout << endl;
}

Measured memory_bytes: 3760
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
const int mod=1e9+7;
int n,m;
long long X,T=0;
struct edge{int u,v,w;}e[maxn<<1];
vector<int>G[maxn];
int fa[maxn];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool cmp(const edge &a,const edge &b){return a.w<b.w;}
int vis[maxn];
int mx[maxn][12],up[maxn][12];
int ew[maxn][maxn],dep[maxn];
int Pow(int a,long long k)
{
    int ret=1;
    while(k)
    {
        if(k&1)ret=ret*1LL*a%mod;
        k>>=1,a=a*1LL*a%mod;
    }
    return ret;
}
void dfs(int u,int pre)
{
    up[u][0]=pre,dep[u]=dep[pre]+1;
    for(int i=1;i<=11;i++)up[u][i]=up[up[u][i-1]][i-1],mx[u][i]=max(mx[u][i-1],mx[up[u][i-1]][i-1]);
    for(auto v:G[u])
    {
        if(v==pre)continue;
        mx[v][0]=ew[u][v];
        dfs(v,u);
    }
}
int getmx(int u,int v)
{
    int ans=0;
    while(dep[u]<dep[v])swap(u,v);
    for(int i=11;i>=0;i--)if(dep[up[u][i]]>=dep[v])ans=max(ans,mx[u][i]),u=up[u][i];
    if(u==v)return ans;
    for(int i=11;i>=0;i--)
    if(up[u][i]!=up[v][i])
    {
        ans=max(ans,mx[u][i]),u=up[u][i];
        ans=max(ans,mx[v][i]),v=up[v][i];
    }
    ans=max(ans,mx[u][0]);
    ans=max(ans,mx[v][0]);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%lld",&X);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u=e[i].u,v=e[i].v;
        if(find(u)==find(v))continue;
        fa[find(u)]=find(v);
        G[u].push_back(v);
        G[v].push_back(u);
        ew[u][v]=ew[v][u]=e[i].w;
        vis[i]=1;
        T+=e[i].w;
    }
    dfs(1,0);
    if(T>X){printf("0\n");return 0;}
    if(T<X)
    {
        int C=0,W=0,A=0;
        for(int i=1;i<=m;i++)
        {
            int u=e[i].u,v=e[i].v,w=getmx(u,v);
            if(T+e[i].w-w<X)C++;
            if(T+e[i].w-w==X)W++;
            if(T+e[i].w-w>X)A++;
        }
        printf("%lld\n",2*1LL*(Pow(2,W)-1)%mod*Pow(2,A)%mod);
    }
    else 
    {
        int C=0,W=0,A=0;
        for(int i=1;i<=m;i++)
        {
            if(vis[i])continue;
            int u=e[i].u,v=e[i].v,w=getmx(u,v);
            if(T+e[i].w-w<X)C++;
            if(T+e[i].w-w==X)W++;
            if(T+e[i].w-w>X)A++;
        }
        printf("%lld\n",(2*1LL*(Pow(2,W)-1)%mod*Pow(2,A)%mod+(Pow(2,n-1)-2)*1LL*Pow(2,m-n+1)%mod)%mod);
    }
}

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

using namespace std;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const int LINF = 1e18;

using ll = long long;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T N){cout << N << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	int len = v.size();
    cout << '[';
	for (int i = 0; i < len; ++i) {
		s << v[i]; if (i < len-1) s << ", ";
	}
    cout << ']';
	return s;
}

int N, M, R;
bool used[10];
vector<int> r(10);
int d[210][210];


int main(){

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

	cin >> N >> M >> R;

	r.resize(R);
	rep(i, R) cin >> r[i];
	sort(r.begin(), r.end());
	fill_n(*d, 210*210, 1<<29);


	rep(i, M){
	    int a, b, c;
		cin >> a >> b >> c;
		if(d[a][b] > c) d[a][b] = d[b][a] = c;
	}

	for(int k = 1; k <= N; ++k){
	    for(int i = 1; i <= N; ++i){
	        for(int j = 1; j <= N; ++j){
	            if(d[i][j] > d[i][k]+d[k][j]){
					d[i][j] = d[i][k] + d[k][j];
				}
	        }
	    }
	}


	ll res = INF;
	do{
		ll tmp = 0LL;
		for(int i = 0; i < R-1; ++i){
			tmp += d[r[i]][r[i+1]];
		}
		res = min(res, tmp);

	}while(next_permutation(r.begin(), r.end()));
	ppp(res);

    return 0;
}


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

int main()
{
    ll a, b;
    cin >> a >> b;
    if ((a + b) % 2 == 1)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << (a + b) / 2 << endl;
    return 0;
}

Measured memory_bytes: 3636
// khodaya khodet komak kon
#include <bits/stdc++.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;

const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll N = 2e5 + 10;
const ll INF = 1e18;
const ll LOG = 20;
vl g[N];
ll n, v, u;

int main(){
	IOS;
	for (int i = 0; i < 3; i++){
		cin >> v >> u;
		g[v].pb(u), g[u].pb(v);
	}
	vl d;
	for (int i = 1; i <= 4; i++){
		d.pb(g[i].size());
	}
	sort(all(d));
	if (d[0] == 1 && d[1] == 1 && d[2] == 2 && d[3] == 2) kill("YES");
	kill("NO");
	
	
	
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




Measured memory_bytes: 4992