// to fill a 3xn board with 2x1 dominoes.
#include <iostream>
using namespace std;
int countWays(int n)
{
int A[n + 1], B[n + 1];
A[2] = 3, A[1] = 0, B[2] = 1, B[1] = 0;
for (int i = 3; i <= n; i++) {
B[i] = A[i-2] + B[i-2];
A[i] = A[i - 2] + 2 * B[i];
}
return A[n];
}
int main()
{
int n = 4;
cout << countWays(n);
return 0;
}
Ly8gdG8gZmlsbCBhIDN4biBib2FyZCB3aXRoIDJ4MSBkb21pbm9lcy4KI2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGNvdW50V2F5cyhpbnQgbikKewoJaW50IEFbbiArIDFdLCBCW24gKyAxXTsKCUFbMl0gPSAzLCBBWzFdID0gMCwgQlsyXSA9IDEsIEJbMV0gPSAwOwoJZm9yIChpbnQgaSA9IDM7IGkgPD0gbjsgaSsrKSB7CkJbaV0gPSBBW2ktMl0gKyBCW2ktMl07CgkJQVtpXSA9IEFbaSAtIDJdICsgMiAqIEJbaV07CgkJCgl9CgoJcmV0dXJuIEFbbl07Cn0KCmludCBtYWluKCkKewoJaW50IG4gPSA0OwoJY291dCA8PCBjb3VudFdheXMobik7CglyZXR1cm4gMDsKfQ==