public static int solution(int n) {
final int MOD = 1000000007;
int index = n / 2;
if (n % 2 != 0)
return 0;
long[] dp = new long[n + 1];
dp[1] = 3;
dp[2] = 11;
for (int i = 3; i <= index; i++) {
dp[i] = (4 * dp[i - 1] % MOD - dp[i - 2] + MOD) % MOD;
}
return (int) dp[index];
}점화식에 - 연산이 포함되어 있어
(4 * dp[i - 1] % MOD - dp[i - 2] + MOD) % MOD와 같이 모듈러 연산의 분배법칙을 활용하였음
출처:https://school.programmers.co.kr/learn/courses/30/lessons/12902
