#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define N (1000000000+7) //#define N 998244353 #define INF 1e16 typedef long long ll; typedef pair P; typedef pair Q; ll dp[1000010][3]; int main() { int n; cin>>n; dp[0][0]=1; for(int i=0;i