stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

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

#define INF (1ll<<58)



	

int main(){

	long long n,m;

	while(cin >> n >> m && n){

		long long land[200][200] , ship[200][200] ;

		rep(i,200)rep(j,200)land[i][j] = ship[i][j] = INF;

		rep(i,200)land[i][i] = ship[i][i] = 0;

		

		rep(i,m){

			string l;

			long long a,b,c; cin >> a >> b >> c >> l;

			a--,b--;

			if(l=="L")land[a][b] = land[b][a] = min(c,land[a][b]);

			else      ship[a][b] = ship[b][a] = min(c,ship[a][b]);

		}

		rep(k,n)rep(i,n)rep(j,n)land[i][j] = min(land[i][j],land[i][k]+land[k][j]);

		rep(k,n)rep(i,n)rep(j,n)ship[i][j] = min(ship[i][j],ship[i][k]+ship[k][j]);

		

		long long r; cin >> r;

		long long R[1000];	

		rep(i,r)cin >> R[i] , R[i]--;

		

		long long dp[2][200];

		rep(j,2)rep(k,200)dp[j][k] = INF;

		dp[0][R[0]] = 0;

		

		rep(bit,r-1){

			rep(cur,n){

				rep(next,n){

					long long newCost = dp[bit%2][cur] + land[R[bit]][cur] + ship[cur][next] + land[next][R[bit+1]];

					dp[(bit+1)%2][next] = min( dp[(bit+1)%2][next],newCost);

				}

				dp[(bit+1)%2][cur] = min(dp[(bit+1)%2][cur],dp[bit%2][cur]+land[R[bit]][R[bit+1]]);

			}

			rep(j,200)dp[bit%2][j] = INF;

		}

		long long ret = INF;

		rep(i,n){

			ret = min(dp[(r-1)%2][i],ret);

		}

		cout << ret << endl;

		

	}

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

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

#define INF 100000000



	

int main(){

	int n,m;

	while(cin >> n >> m && n){

		int land[200][200] , ship[200][200] ;

		rep(i,200)rep(j,200)land[i][j] = ship[i][j] = INF;

		rep(i,200)land[i][i] = ship[i][i] = 0;

		

		rep(i,m){

			string l;

			int a,b,c; cin >> a >> b >> c >> l;

			a--,b--;

			if(l=="L")land[a][b] = land[b][a] = min(c,land[a][b]);

			else      ship[a][b] = ship[b][a] = min(c,ship[a][b]);

		}

		rep(k,n)rep(i,n)rep(j,n)land[i][j] = min(land[i][j],land[i][k]+land[k][j]);

		rep(k,n)rep(i,n)rep(j,n)ship[i][j] = min(ship[i][j],ship[i][k]+ship[k][j]);

		

		int r; cin >> r;

		int R[1000];	

		rep(i,r)cin >> R[i] , R[i]--;

		

		int dp[2][200];

		rep(j,2)rep(k,200)dp[j][k] = INF;

		dp[0][R[0]] = 0;

		

		rep(bit,r-1){

			rep(cur,n){

				rep(next,n){

					int newCost = dp[bit%2][cur] + land[R[bit]][cur] + ship[cur][next] + land[next][R[bit+1]];

					dp[(bit+1)%2][next] = min( dp[(bit+1)%2][next],newCost);

				}

				dp[(bit+1)%2][cur] = min(dp[(bit+1)%2][cur],dp[bit%2][cur]+land[R[bit]][R[bit+1]]);

			}

			rep(j,200)dp[bit%2][j] = INF;

		}

		int ret = INF;

		rep(i,n){

			ret = min(dp[(r-1)%2][i],ret);

		}

		cout << ret << endl;

		

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<string.h>

#include<math.h>

#include<iostream>

#include<string>

#include<sstream>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<vector>

#define ll  long long 

using namespace std;

ll a[100005], f[100005] = {1}, mod = 1000000007, n, k;

ll quick_pow(ll a, ll b, ll mod)

{

	ll ans = 1;

	while (b)

	{

		if (b & 1)	ans = ans * a % mod;

		a = a * a % mod;

		b >>= 1;

	}

	return ans;

}

ll vim(ll a, ll b)

{

	return quick_pow(a, b - 2, b);

}

inline ll C(ll a, ll b)

{

	return f[b] * vim(f[a], mod) % mod * vim(f[b - a], mod) % mod;

}

ll solve()

{

	ll mx = 0, mn = 0;

	sort(a, a + n);

	for (int i = n - 1; i >= k - 1; i--)

		mx = (mx + C(k - 1, i) * a[i]) % mod;

	for (int i = n - 1, j = 0; i >= k - 1; i--, j++)

		mn = (mn + C(k - 1, i) * a[j]) % mod;

	return ((mx - mn) % mod + mod) % mod;

}

signed main()

{

	for (int i = 1; i <= 100000; i++)	f[i] = f[i - 1] * i % mod;

	//cout << vim(1, mod) << endl;

	while (~scanf("%lld%lld", &n, &k))

	{

		for (int i = 0; i < n; i++)	scanf("%lld", &a[i]);

		printf("%lld\n", solve());

	}

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm>

#include<vector>

using namespace std ;

typedef long long ll ;

const ll maxx = 1e5+5,mod=1e9+7 ;

ll fact[maxx];

ll power(ll b,ll p,ll m)

{

    if(p==0){return 1;}

    //if(p==1){return b;}

    ll half = power(b,p/2,m);

    ll ans,full=(half*half)%m;

    if(p%2==0)

    {

        return full;

    }

    else { return  (full*b)%m ;}

}

ll mulv(ll b,ll p)

{

    // since p is prime ;

    // b*x=1 mod p , p is prime so gcd(p,b)=1

    ll x  = power(b,p-2,p);

    return x ;

}

ll ncr(ll n,ll r)

{

    //cout << n << "  " << r << endl;

    if(n<r){return 0;}

    if(r==0 || n==r){return 1;}

    if(r==1 ){return n%mod;}

    ll a,b,c;

    a = fact[n];

    b = mulv(fact[n-r],mod);

    c = mulv(fact[r],mod);

    ll ans = (a*b)%mod;

    ans = (ans*c)%mod;

    return ans ;

}

int main()

{

    fact[0]=1;

    for(int i=1;i<=100002;i++)

    {

       fact[i]=(fact[i-1]*i)%mod;

    }

    ll n , k ;

    cin >> n >> k ;

    ll arr[n+5];

    for(int i=1;i<=n;i++)

    {

       ll  x ;

       cin >> x ;

       arr[i-1]=x;

    }

    sort(arr,arr+n,greater<ll>());

    ll sum=0,sum1=0,sum2=0;

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

    {

        sum1+= (arr[i]*ncr(n-i-1,k-1))%mod ;



        sum2+= (arr[i]*ncr(i,k-1))%mod ;

    }

    sum=sum1-sum2;

    cout << sum%mod << endl;

    return 0 ;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

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

#define MAX 100001

#define Mod 1000000007

typedef long long ll;

using namespace std;

ll ans, cnt;

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

void comInit() {

  fac[0] = fac[1] = 1;

  finv[0] = finv[1] = 1;

  inv[1] = 1;

  for (int i = 2; i < MAX; i++) {

    fac[i] = fac[i - 1] * i % Mod;

    inv[i] = Mod - inv[Mod % i] * (Mod / i) % Mod;

    finv[i] = finv[i - 1] * inv[i] % Mod;

  }

}



ll com(ll n, ll r) {

  if (n < r)

    return 0;

  if (n < 0 || r < 0)

    return 0;

  return fac[n] * (finv[r] * finv[n - r] % Mod) % Mod;

}



int main() {

  ll n, k;

  cin >> n >> k;

  vector<ll> a(n);

  rep(i, n)

  {

    cin >> a[i];

  }

  comInit();



  sort(a.begin(), a.end());



  ll maxsum = 0;

  rep(i, n)

  {

    maxsum += (com(i, k - 1) * a[i]) % Mod;

    maxsum %= Mod;

  }



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

  ll minsum = 0;

  rep(i, n)

  {

    minsum += (com(i, k - 1) * a[i]) % Mod;

    minsum %= Mod;

  }



  cout << (maxsum - minsum) % Mod << endl;



  return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

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

#define MAX 100010

#define Mod 1000000007

typedef long long ll;



using namespace std;



ll ans, cnt;

ll n;



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



void comInit() {

  fac[0] = fac[1] = 1;

  finv[0] = finv[1] = 1;

  inv[1] = 1;

  for (int i = 2; i < n; 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;

  }

}



ll com(ll n, ll r) {

  if (n < r)

    return 0;

  if (n < 0 || r < 0)

    return 0;

  return fac[n] * (finv[r] * finv[n - r] % Mod) % Mod;

}



int main() {

  ll k;

  cin >> n >> k;

  vector<ll> a(n);

  rep(i, n)

  {

    cin >> a[i];

  }

  comInit();



  sort(a.begin(), a.end());



  ll maxsum = 0;

  rep(i, n)

  {

    maxsum += (com(i, k - 1) * a[i]) % Mod;

    maxsum %= Mod;

  }



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

  ll minsum = 0;

  rep(i, n)

  {

    minsum += (com(i, k - 1) * a[i]) % Mod;

    minsum %= Mod;

  }



  cout << (maxsum - minsum) % Mod << endl;



  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

long long a[90];

int main()

{

	a[0]=2;

	a[1]=1;

	int n;cin>>n;

	for(int i=2;i<=n;i++)

		a[i]=a[i-1]+a[i-2];

	cout<<a[n];

}

// Optimized solution to the same problem (faster):
#include <cstdio>

int main(){

    static long long f[81]={2,1};

    int n; scanf("%d",&n);

    for(int i=2;i<=n;i++) f[i]=f[i-1]+f[i-2];

    printf("%lld\n",f[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

long long n,s[233]={2,1};

int main(){

	for (int i=2;i<=87;i++) s[i]=s[i-1]+s[i-2];

	cin>>n;

	cout<<s[n]<<endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

int main(){

    static long long f[81]={2,1};

    int n; scanf("%d",&n);

    for(int i=2;i<=n;i++) f[i]=f[i-1]+f[i-2];

    printf("%lld\n",f[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int n;

long long f[87];

int main()

{

    cin>>n;

    f[0]=2;

    f[1]=1;

    for(int i=2;i<=n;i++)

        f[i]=f[i-1]+f[i-2];

    cout<<f[n];

}

// Optimized solution to the same problem (faster):
#include <cstdio>

int main(){

    static long long f[81]={2,1};

    int n; scanf("%d",&n);

    for(int i=2;i<=n;i++) f[i]=f[i-1]+f[i-2];

    printf("%lld\n",f[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define vi vector<int>

#define vvi vector<vector<int> >

#define vl vector<ll>

#define vvl vector<vector<ll>>

#define vb vector<bool>

#define vc vector<char>

#define vs vector<string>

using ll = long long;

using ld =long double;

#define int ll

#define INF 1e9

#define EPS 0.0000000001

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

#define loop(i,s,n) for(int i=s;i<n;i++)

#define all(in) in.begin(), in.end()

template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }

template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

#define MAX 9999999

using namespace std;

typedef pair<int, int> pii;

typedef pair<int,pii> piii;

#define mp make_pair

signed main(){

    int n; cin>>n;

    int dp[100000]={0};

    dp[0]=2;

    dp[1]=1;

    for(int i=2;i<=n;i++)

        dp[i]=dp[i-1]+dp[i-2];

    cout<<dp[n]<<endl;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using ll  = long long;

#define int ll

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

#define loop(i,s,n) for(int i=s;i<n;i++)

#define erep(e,v) for(auto && e :v)

#define all(in) in.begin(), in.end()

#define MP make_pair

#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)

#define EPS 0.0000000001

using namespace std;

template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }

template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }

template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }

template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }

using ld  = long double;

using pii = pair<int,int>;

using piii = pair<int,pii>;

int W,H;

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

bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}

signed main(){

    int n; cin >> n;

    vector<int>dp(100,0);

    dp[0] = 2;

    dp[1] = 1;

    rep(i,dp.size()){

        if(i>=2)dp[i] = dp[i-1] + dp[i-2];

    }

    cout << dp[n] << endl;

}






// Fastest known solution for this problem:
// Original C++ solution (slower):


#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <string>

using namespace std;

const int maxn = 1e3;

long long ch[87];

int main()

{

    ch[0] = 2;

    ch[1] = 1;

    for(int i = 2;i < 87;i++)

        ch[i] = ch[i-1]+ch[i-2];

    int n;

    while(cin >> n)

    {

        cout << ch[n] << endl;

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

	int n;

	long long a[100];

	scanf("%d",&n);

	a[0]=2;

	a[1]=1;

	for(int i=2;i<=n;i++)a[i]=a[i-1]+a[i-2];

	printf("%lld\n",a[n]);

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <cstdio>

#include <queue>

#include <map>

#include <string>

const int INF = 99999999;

const int MIN = -0xffffff0;

using namespace std;



long long num[100];



int main(){

    num[0] = 2;

    num[1] = 1;

    for(int i=2;i<=86;i++) num[i] = num[i-1] + num[i-2];

    int n;

    while(cin >> n) cout << num[n] << endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

	int n;

	long long a[100];

	scanf("%d",&n);

	a[0]=2;

	a[1]=1;

	for(int i=2;i<=n;i++)a[i]=a[i-1]+a[i-2];

	printf("%lld\n",a[n]);

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>



int main(int argc, char *argv[]) {

	int n;

	scanf("%d",&n);

	long long lucas[100];

	lucas[0]=2;

	lucas[1]=1;

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

		lucas[i]=lucas[i-2]+lucas[i-1];

	}

	printf("%lld",lucas[n]); 

	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

	int n;

	long long a[100];

	scanf("%d",&n);

	a[0]=2;

	a[1]=1;

	for(int i=2;i<=n;i++)a[i]=a[i-1]+a[i-2];

	printf("%lld\n",a[n]);

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <map>

#include <queue>

#include <cmath>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define Max 1001

#define INF 0x3f3f3f3f

using namespace std;

int main()

{

    long long n,a[100] = {2,1};

    cin>>n;

    for(int i = 2;i <= n;i ++)

        a[i] = a[i - 1] + a[i - 2];

    cout<<a[n];

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

	int n;

	long long a[100];

	scanf("%d",&n);

	a[0]=2;

	a[1]=1;

	for(int i=2;i<=n;i++)a[i]=a[i-1]+a[i-2];

	printf("%lld\n",a[n]);

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

	int n;

        cin>>n;

		if(n>=2)

		{

			long long a=2,b=1,t;

			for(int i=2;i<=n;i++)

			{

				t=a+b;

				a=b;

				b=t;

			}

			cout<<t<<endl;	

		}

		else if(n==1)printf("1\n");  

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

	int n;

	long long a[100];

	scanf("%d",&n);

	a[0]=2;

	a[1]=1;

	for(int i=2;i<=n;i++)a[i]=a[i-1]+a[i-2];

	printf("%lld\n",a[n]);

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <string.h>

#define ll long long 

using namespace std;

struct node 

{

	int a[1000]={0};

	int num;

	

 }s[1005]; 

int main()

{	

	s[0].a[0]=2;s[0].num=0;

	s[1].a[0]=1;s[1].num=0;

	for(int i=2;i<=1000;i++)

	{

		for(int k=0;k<=s[i-1].num;k++)

		{

			s[i].a[k]+=s[i-1].a[k]+s[i-2].a[k];

			if(s[i].a[k]>=10)

			{

				s[i].a[k+1]++;

				s[i].a[k]-=10;

			}			

		}

		if(s[i].a[s[i-1].num+1]!=0)

		s[i].num=s[i-1].num+1;

		else

		s[i].num=s[i-1].num;

	}

		int n;

		scanf("%d",&n);

		for(int i=s[n].num;i>=0;i--)

		printf("%d",s[n].a[i]);

		puts("");

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



long long f[100] = {2, 1}, x;



int main() {

    scanf("%lld", &x);

    for(int i = 2; i <= x; ++i)

        f[i] = f[i - 1] + f[i - 2];

    printf("%lld\n", f[x]);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

long long f[100];

int main()

{

	long long n;

	cin>>n;

	f[0]=2;

	f[1]=1;

	for(int i=2;i<=100;i++)

	f[i]=f[i-1]+f[i-2];

	cout<<f[n]<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>



long long int dp[87];

int main()

{

	int n;

	scanf("%d",&n);

	dp[0] = 2;

	dp[1] = 1;

	for (int i = 2; i <= n; i++)

	{

		dp[i] = dp[i-1] + dp[i-2];

	}

	printf("%lld",dp[n]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long n,a=2,b=1,ans;

    cin>>n;

    if(n==0) cout<<"2"<<endl;

    if(n==1) cout<<"1"<<endl;

    if(n>=2)

    {

        n=n-1;

        for(int i=1;i<=n;i++)

        {

            ans=a+b;

            a=b;

            b=ans;

        }

        cout<<ans<<endl;

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>



long long int dp[87];

int main()

{

	int n;

	scanf("%d",&n);

	dp[0] = 2;

	dp[1] = 1;

	for (int i = 2; i <= n; i++)

	{

		dp[i] = dp[i-1] + dp[i-2];

	}

	printf("%lld",dp[n]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

long long f[87],n;

int main(){

cin>>n;

f[0]=2;

f[1]=1;

for(int i=2;i<=n;i++)

f[i]=f[i-1]+f[i-2];

cout<<f[n];}

// Optimized solution to the same problem (faster):
#include<stdio.h>



long long int dp[87];

int main()

{

	int n;

	scanf("%d",&n);

	dp[0] = 2;

	dp[1] = 1;

	for (int i = 2; i <= n; i++)

	{

		dp[i] = dp[i-1] + dp[i-2];

	}

	printf("%lld",dp[n]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<string.h>

#include<algorithm>

#define mem(a) memset(a,0,sizeof(a))

using namespace std;

int F[1005][500];

void Fib()

{

	int i,j;

	mem(F);

	F[0][0]=2;

	F[1][0]=1;

	for(i=2;i<1005;i++)

	{

		for(j=0;j<500;j++)

		F[i][j]=F[i-1][j]+F[i-2][j];

		for(j=0;j<500;j++)

		{

			if(F[i][j]>9)

			{

				F[i][j+1]+=F[i][j]/10;

				F[i][j]=F[i][j]%10;

			}

		}

	}

}

int main()

{

	int i,j,flag,N,n;

	Fib();

	

		scanf("%d",&n);

		flag=0;

		for(j=499;j>=0;j--)

		{

			if(flag==1||F[n][j])

			{

				flag=1;

				printf("%d",F[n][j]);

			}

		}

		printf("\n");

	 return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

using namespace std;

int main()

{

	int N,i;

	cin>>N;

	long long str[N];

	str[0]=2;str[1]=1;

	for(i=2;i<=N;i++){

		str[i]=str[i-1]+str[i-2];

	}

	cout<<str[N]<<endl;

	return 0;

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int N=42;

typedef long long ll;



int gi() {

	int x=0,o=1;char ch=getchar();

	while(!isdigit(ch)&&ch!='-') ch=getchar();

	if(ch=='-') o=-1,ch=getchar();

	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();

	return x*o;

}



int n;

char s[N][N];

ll f[N][N][N];



ll dp(int l,int r,int m) {

	if(~f[l][r][m]) return f[l][r][m];

	if(l==r) return 1;

	if(l==m||r==m) return 0;

	ll &ret=f[l][r][m];ret=0;

	for(int i=l;i<m;i++)

		for(int j=m+1;j<=r;j++)

			if(s[i][j]=='1')

				for(int u=i;u<m;u++)

					for(int v=m+1;v<=j;v++) ret+=dp(l,u,i)*dp(u+1,v-1,m)*dp(v,r,j);

	return ret;

}



int main() {

	n=gi();

	for(int i=1;i<=n+n;i++) scanf("%s",s[i]+1);

	memset(f,-1,sizeof(f));

	ll ans=0;

	for(int i=2;i<=n+n;i++) if(s[1][i]=='1') ans+=dp(2,n+n,i);

	cout<<ans;

	return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pii;

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define sz(a) int(a.size())

const int N=50;



int gi() {

	int x=0,o=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if(ch=='-') o=-1,ch=getchar();

	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

	return x*o;

}



int n;

ll f[N][N][N],g[N][N][N];

char s[N][N];



int main() {

	cin>>n;n<<=1;

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

		scanf("%s",s[i]+1),f[i][i][i]=1;

		for(int x=1;x<i;x++) if(s[x][i]=='1') g[i][i][x]=1;

	}

	for(int len=3;len<=n;len+=2)

		for(int l=1;l<=n-len+1;l++) {

			int r=l+len-1;

			for(int a=l;a<r;a+=2)

				for(int b=r;b>a;b-=2) {

					ll sum=0;

					for(int x=l;x<=a;x++) sum+=f[l][a][x]*g[b][r][x];

					for(int t=a+1;t<b;t++) f[l][r][t]+=f[a+1][b-1][t]*sum;

				}

			for(int x=1;x<l;x++)

				for(int y=l;y<=r;y++) if(s[x][y]=='1') g[l][r][x]+=f[l][r][y];

		}

	ll ans=0;

	for(int i=2;i<=n;i++) if(s[1][i]=='1') ans+=f[2][n][i];

	cout<<ans;

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pii;

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define sz(a) int(a.size())

const int N=50;



int gi() {

	int x=0,o=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if(ch=='-') o=-1,ch=getchar();

	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

	return x*o;

}



int n;

ll f[N][N][N];

char s[N][N];



int main() {

	cin>>n;n<<=1;

	for(int i=1;i<=n;i++) scanf("%s",s[i]+1),f[i][i][i]=1;

	for(int len=3;len<=n;len+=2)

		for(int l=1;l<=n-len+1;l++) {

			int r=l+len-1;

			for(int t=l+1;t<r;t++)

				for(int a=l;a<r;a+=2)

					for(int b=r;b>t;b-=2)

						for(int x=l;x<=a;x++)

							for(int y=b;y<=r;y++)

								if(s[x][y]=='1') f[l][r][t]+=f[l][a][x]*f[b][r][y]*f[a+1][b-1][t];

		}

	ll ans=0;

	for(int i=2;i<=n;i++) if(s[1][i]=='1') ans+=f[2][n][i];

	cout<<ans;

	return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pii;

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define sz(a) int(a.size())

const int N=50;



int gi() {

	int x=0,o=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if(ch=='-') o=-1,ch=getchar();

	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

	return x*o;

}



int n;

ll f[N][N][N],g[N][N][N];

char s[N][N];



int main() {

	cin>>n;n<<=1;

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

		scanf("%s",s[i]+1),f[i][i][i]=1;

		for(int x=1;x<i;x++) if(s[x][i]=='1') g[i][i][x]=1;

	}

	for(int len=3;len<=n;len+=2)

		for(int l=1;l<=n-len+1;l++) {

			int r=l+len-1;

			for(int a=l;a<r;a+=2)

				for(int b=r;b>a;b-=2) {

					ll sum=0;

					for(int x=l;x<=a;x++) sum+=f[l][a][x]*g[b][r][x];

					for(int t=a+1;t<b;t++) f[l][r][t]+=f[a+1][b-1][t]*sum;

				}

			for(int x=1;x<l;x++)

				for(int y=l;y<=r;y++) if(s[x][y]=='1') g[l][r][x]+=f[l][r][y];

		}

	ll ans=0;

	for(int i=2;i<=n;i++) if(s[1][i]=='1') ans+=f[2][n][i];

	cout<<ans;

	return 0;

}


// Fastest known solution for this problem: