#include <stdio.h>
int hoge(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int x[n + 1];
x[0] = 0;
x[1] = 1;
for (int i = 2; i <= n; i++) {
x[i] = 4 * x[i - 1] + 3 * x[i - 2];
}
return x[n];
}
int main() {
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgaG9nZShpbnQgbikgewogICAgaWYgKG4gPT0gMCkgcmV0dXJuIDA7CiAgICBpZiAobiA9PSAxKSByZXR1cm4gMTsKCiAgICBpbnQgeFtuICsgMV07ICAgICAgIAogICAgeFswXSA9IDA7CiAgICB4WzFdID0gMTsKCiAgICBmb3IgKGludCBpID0gMjsgaSA8PSBuOyBpKyspIHsKICAgICAgICB4W2ldID0gNCAqIHhbaSAtIDFdICsgMyAqIHhbaSAtIDJdOwogICAgfQoKICAgIHJldHVybiB4W25dOwp9CgppbnQgbWFpbigpIHsKICAgIHByaW50ZigiJWQiLCBob2dlKDMpKTsKICAgIHJldHVybiAwOwp9