// Algorithms from Theorem 2
// including the prefix sums but not the memory optimization
// no big integers used, everything will overflow at 2^63
// Runtime O(n^4), Memory O(n^4) 

// Just compile and run it to get a quick demo or look at the main function for some examples.
// g++ motzkin.cpp -o m -std=c++11 -O2; ./m

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;
using in = long long int;
using PII = pair<in,in>;
using VI = vector<in>;

#define sz(v) (v).size()
#define forn(i,n) for(in i=0; i<(n); ++i)
#define forv(i,v) forn(i,sz(v))
#define DEB(x)  // Replace by "DEB(x) x" to get debug output
using namespace std;

map<VI, in> LFMemo;
map<VI, in> PSLFMemo; // Prefix sums
in LFcount(in A, in w, in l);

in SumLFcount(in A, in w, in la, in lb) { // sum for l in [la,lb]
	if(la > lb) return 0;
	if(la < 0) return 0;
	if(la==lb) return LFcount(A,w,la);
	if(PSLFMemo.find({A,w,lb}) == PSLFMemo.end()) {
		PSLFMemo[{A,w,lb}] = SumLFcount(A,w,0,lb-1) + LFcount(A,w,lb);
	}
	return PSLFMemo[{A,w,lb}] - SumLFcount(A,w,0,la-1);
}

in LFcount(in A, in w, in l) {
	if(A==0 && w == 0 && l==0 ) {
		return 1;
	}
	if(A < 0 || w <= 0 || l < 0) return 0;
	if(LFMemo.find({A,w,l}) != LFMemo.end()) {
		return LFMemo[{A,w,l}];
	}
	in res = 0;
	res += SumLFcount(A-l, w-1, l, w/2);
	// for(in ll = l; ll<=w/2; ll++) {
	// 	res += LFcount(A-l, w-1, ll);
	// }
	if(l>0) {
		res += SumLFcount(A-(2*l-1), w-2, l-1, w/2);
	    //	for(in ll = l-1; ll<=w/2; ll++) {
		// 	res += LFcount(A-(2*l-1), w-2, ll);
		// }
	}
	LFMemo[{A,w,l}] = res;
	// cout << " computed " << "LFcount(" << A << "," << w << "," << l << ") = " << res << endl;
	return res;
}
in LFcount(in A, in w) {
	in res = 0;
	for(in l = 0; l < w; l++) {
		in x =  LFcount(A,w,l);
		// cout << "add " << "LFcount(" << A << "," << w << "," << l << ") =... " << x <<  endl;
		res += x;
	}
	return res;
}
in LFcount(in w) {
	in res = 0;
	for(in A = 0; A < w*w; A++) {
		res += LFcount(A,w);
	}
	return res;
}

// Weighted Version
map<VI, in> WLFMemo;
map<VI, in> PSWLFMemo; // Prefix sums
in WLFcount(in A, in w, in l);

in SumWLFcount(in A, in w, in la, in lb) { // sum for l in [la,lb]
	if(la > lb) return 0;
	if(la < 0) return 0;
	if(la==lb) return WLFcount(A,w,la);
	if(PSWLFMemo.find({A,w,lb}) == PSWLFMemo.end()) {
		PSWLFMemo[{A,w,lb}] = SumWLFcount(A,w,0,lb-1) + WLFcount(A,w,lb);
	}
	return PSWLFMemo[{A,w,lb}] - SumWLFcount(A,w,0,la-1);
}

in WLFcount(in A, in w, in l) {
	if(A==0 && w == 0 && l==0 ) {
		return 1;
	}
	if(A < 0 || w <= 0 || l < 0) return 0;
	if(WLFMemo.find({A,w,l}) != WLFMemo.end()) {
		return WLFMemo[{A,w,l}];
	}
	in res = 0;
	res += (2*l+1)*SumWLFcount(A-l, w-1, l, w/2);
	if(l>0) {
		res += l*l*SumWLFcount(A-(2*l-1), w-2, l-1, w/2);
	}
	WLFMemo[{A,w,l}] = res;
	return res;
}
in WLFcount(in A, in w) {
	in res = 0;
	for(in l = 0; l < w; l++) {
		in x =  WLFcount(A,w,l);
		res += x;
	}
	return res;
}
in WLFcount(in w) {
	in res = 0;
	for(in A = 0; A < w*w; A++) {
		res += WLFcount(A,w);
	}
	return res;
}

int main() {
	in A,w,h;

	cout << "\nMotzkin Path Counting Demo\n\n";

	cout << "Motzkin Numbers from 1 to 10\n";
	cout << "see: https://en.wikipedia.org/wiki/Motzkin_number\n";
	for(in w = 1; w<=10; w++) {
		in res = LFcount(w);
		cout << "M(" << w << ") = " << res << endl;
	}

	cout << "\n\nM(n,A): Print Motzkin Path Counts by width and area using the last fall DP\n";
	cout << "see: http://oeis.org/A129181\n";
	for(w = 1; w<=10; w++) {
		for(A = 0; A <= w*w; A++) {
			in res = LFcount(A,w);
			// assert(res == weighted_count(A,w));
			if(res>0) cout << res << "\t";
		}
		cout << endl;
	}

	cout << "\n\nD(n,A): Print Weighted Motzkin Path Counts by width and area using the last fall DP\n";
	for(w = 1; w<=10; w++) {
		for(A = 0; A <= w*w; A++) {
			in res = WLFcount(A,w);
			// assert(res == weighted_count(A,w));
			if(res>0) cout << res << "\t";
		}
		cout << endl;
	}

	cout << "\n\nPrint Weighted Motzkin Path Counts by width for a fixed w = w!\n";
	for(w = 1; w<10; w++) {
		in res = WLFcount(w);
		cout << w << "! = " << res << endl;
	}
}