#include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define INF 1<<30 #define ALEN(ARR) (sizeof(ARR) / sizeof((ARR)[0])) #define MP make_pair #define mp make_pair #define pb push_back #define PB push_back #define DEBUG(x) cout<<#x<<": "<> n; if(n == 1) { cout << 1 << endl; } else if(n == 2 || n == 3) { cout << 2 << endl; } else { ll a = 0, b = 1, c = 2, d = 2; FOR(i, 4, n+1) { a = (b + c) % MOD; b = c; c = d; d = a; } cout << a << endl; } }