stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 3.415373402245047x):
#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;

}
// Slower C++ solution:
#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];

}

// Faster C++ solution for the same problem (measured speedup: 5.231227223667895x):
#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]);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.238553856245049x):
#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]);

}
// Slower C++ solution:
#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];

}

// Faster C++ solution for the same problem (measured speedup: 5.191250965617116x):
#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]);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.80228040735427x):
#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;

}
// Slower C++ solution:


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

}

// Faster C++ solution for the same problem (measured speedup: 5.25158969279823x):
#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]);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.250277835683456x):
#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]);

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.188257477346881x):
#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]);

}
// Slower C++ solution:
#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];

}


// Faster C++ solution for the same problem (measured speedup: 5.238216891303509x):
#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]);

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.248754607479347x):
#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]);

}
// Slower C++ solution:


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

}

// Faster C++ solution for the same problem (measured speedup: 5.249828169475205x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.248516752392316x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.186517197338956x):
#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;

}
// Slower C++ solution:
#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];

}


// Faster C++ solution for the same problem (measured speedup: 5.236459853574963x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.2469940351195925x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 31.204533680965113x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 6.013810660577377x):
#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#define ll long long

using namespace std;

int main() 

{

	int n;

	scanf("%d",&n);

	ll a[100];

	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]);

	return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 6.013946229857596x):
#include<iostream>

#include<algorithm>

#include<stdio.h>

#include<string.h> 

using namespace std;

long long a[100];

int main()

{

	 a[0]=2;

	 a[1]=1;

	int n;

	scanf("%d",&n);

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

	{

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

	}

	

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

	return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.868408746025551x):
#include<bits/stdc++.h>

using namespace std;



#define NL '\n'

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

#define async() ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)



int main(){

	async(); int n; 

	cin >> n;

	long long a[n+1];

	a[0] = 2, a[1] = 1;

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

	cout << a[n] << NL;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.242919568478695x):
#include <cstdio>

typedef unsigned long long ULL;



int n;

ULL f[100];



int main(){

	scanf("%d",&n);

	f[0]=2LLU,f[1]=1LLU;

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

	return printf("%llu\n",f[n])&0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.256745245212096x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.25420831615517x):
#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;

}
// Slower C++ solution:
#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];}

// Faster C++ solution for the same problem (measured speedup: 5.246709230146616x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 3.8898293495768392x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.5067453823349244x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.7595984125742412x):
#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 a=l;a<r;a+=2)

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

					ll sum=0;

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

						for(int y=b;y<=r;y++) if(s[x][y]=='1') sum+=f[l][a][x]*f[b][r][y];

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

				}

		}

	ll ans=0;

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

	cout<<ans;

	return 0;

}