using System;
class Program
{
int[] masks = { 0, 3, 6 };
int CountTilings(int n, int m, int s = 0)
{
if (n == 1) { return 1; }
int result = 0;
foreach (int mask in masks)
{
if ((mask & s) == 0)
{
result += CountTilings(n - 1, m, mask);
}
}
return result;
}
public static void Main()
{
Program p = new Program();
int result = p.CountTilings(4, 3);
Console.WriteLine(result);
}
}
dXNpbmcgU3lzdGVtOwoKY2xhc3MgUHJvZ3JhbQp7CiAgICBpbnRbXSBtYXNrcyA9IHsgMCwgMywgNiB9OwoKICAgIGludCBDb3VudFRpbGluZ3MoaW50IG4sIGludCBtLCBpbnQgcyA9IDApCiAgICB7CiAgICAgICAgaWYgKG4gPT0gMSkgeyByZXR1cm4gMTsgfQoKICAgICAgICBpbnQgcmVzdWx0ID0gMDsKICAgICAgICBmb3JlYWNoIChpbnQgbWFzayBpbiBtYXNrcykKICAgICAgICB7CiAgICAgICAgICAgIGlmICgobWFzayAmIHMpID09IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJlc3VsdCArPSBDb3VudFRpbGluZ3MobiAtIDEsIG0sIG1hc2spOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIE1haW4oKQogICAgewogICAgICAgIFByb2dyYW0gcCA9IG5ldyBQcm9ncmFtKCk7CiAgICAgICAgaW50IHJlc3VsdCA9IHAuQ291bnRUaWxpbmdzKDQsIDMpOwogICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKHJlc3VsdCk7CiAgICB9Cn0=