#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pair P; typedef tuple T; const ll MOD=1e9+7; const ll INF=1e18; const double pi=acos(-1); const double eps=1e-10; int dx[]={1, 0, -1, 0}; int dy[]={0, -1, 0, 1}; int main(){ int n; cin>>n; vector dp(n+10, 0); dp[1] = 1; dp[2] = 2; for(int i=2; i