#include <iostream>
using namespace std;
int dp[100] = {};
int main() {
int n = 3, m = 2, k = 1;
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1] * m + dp[i - k - 1];
}
cout << dp[n];
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgZHBbMTAwXSA9IHt9OwppbnQgbWFpbigpIHsKCWludCBuID0gMywgbSA9IDIsIGsgPSAxOwoJZHBbMF0gPSAxOwoJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CgkJZHBbaV0gPSBkcFtpIC0gMV0gKiBtICsgZHBbaSAtIGsgLSAxXTsKCX0KCWNvdXQgPDwgZHBbbl07CglyZXR1cm4gMDsKfQ==