#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair p_ii; const int INF = 1e9; const double PI = acos(-1.0); const ll MOD = 1e9 + 7; ll dp[2][2][1000010]; int main() { int n; cin>>n; if(n==1){ cout<<1<