#include <vector>
#include <iostream>
#include <bitset>
typedef unsigned int			u32;
typedef unsigned long long int	u64;
using namespace std;

typedef u64 T;
#define M		1000
#define L		100000000
#define MOD(x)	((x)%L)
#define W		120
#define H		12
T c[M][M];			// 変換行列
T q[M][2];			// 変換行列計算のための一時的なキャッシュ
vector<bitset<M>> v;

void EnumerateState(bitset<M> &a, u32 n) {
	if (n == H+1) {
		v.push_back(a);
	} else {
		bool b1 = n==0;
		if (!b1) b1 = a[n-1];
		if (b1) {
			a[n] = false;
			EnumerateState(a, n + 1);
		}
		a[n] = true;
		EnumerateState(a, n + 1);
	}
}

T GetNext(bitset<M> &a, bitset<M> &b, u32 i, bool f) {
	u32 j = f?1:0;
	if (q[i][j] != 0) return q[i][j];
	T r = 0;
	if (i == H+1) return j;
	if (a[i]) {
		if (b[i]) {
			if (f) {
				r = MOD(2 * GetNext(a, b, i+1, true) + 2 * GetNext(a, b, i+1, false));
			} else {
				r = MOD(GetNext(a, b, i+1, true) + 2 * GetNext(a, b, i+1, false));
			}
		} else {
			if (f) {
				// do nothing.
			} else {
				r = MOD(GetNext(a, b, i+1, true));
			}
		}
	} else {
		if (b[i]) {
			if (f) {
				r = MOD(GetNext(a, b, i+1, true) + GetNext(a, b, i+1, false));
			} else {
				r = MOD(GetNext(a, b, i+1, false));
			}
		} else {
			if (f) {
				// do nothing.
			} else {
				r = MOD(GetNext(a, b, i+1, true));
			}
		}
	}
	q[i][j] = r;
	return r;
}

int main(int argc, char* argv[])
{
	bitset<M> a, b;

	// ステップ１：可能な状態を列挙する.
	EnumerateState(a, 0);
	
	// ステップ２：W-1 に対する各状態のパターン数から
	// W に対する各状態のパターン数を得る変換行列を計算する.
	for (u32 i=0; i<v.size(); i++) {
		for (u32 j=0; j<v.size(); j++) {
			for (u32 k=0; k<=H; k++) q[k][0] = q[k][1] = 0;
			c[i][j] = GetNext(v[i], v[j], 0, false);
		}
	}

	// ステップ３：W=0 に対する各状態のパターン数を計算する.
	T g[M];
	for (u32 k=0; k<v.size(); k++) g[k] = 0;
	bitset<M> h;
	for (u32 i=0; i<1<<H; i++) {
		u32 t = i;
		h.reset();
		for (u32 k=0; k<H; k++) {
			if (t&1) h[k+1] = true;
			else h[k] = true;
			t >>= 1;
		}
		for (u32 j=0; j<v.size(); j++) {
			if (v[j] == h) {
				g[j] += 1;
				break;
			}
		}
	}

	// ステップ４：３に２の行列を W 回作用させる.
	T g_new[M];
	for (u32 i=0; i<W; i++) {
		for (u32 k=0; k<v.size(); k++) g_new[k] = 0;
		for (u32 j=0; j<v.size(); j++) {
			for (u32 k=0; k<v.size(); k++) {
				g_new[j] = MOD(g_new[j] + MOD(c[k][j] * g[k]));
			}
		}
		for (u32 k=0; k<v.size(); k++) g[k] = g_new[k];
	}

	// 出力
	cout << "N(" << W << "," << H << ")=" << g[v.size()-1] << endl;
}