#include using namespace std; template struct MInt { long long val; MInt(long long val) : val(val % MOD) {} MInt operator+(const MInt& n) const { return MInt(val) += n; } MInt operator*(const MInt& n) const { return MInt(val) *= n; } MInt& operator+=(const MInt& n) { val = (val + n.val) % MOD; return *this; } MInt& operator*=(const MInt& n) { val = (val * n.val) % MOD; return *this; } friend ostream& operator<<(ostream& os, const MInt& n) { os<; int main() { long long N; cin >> N; N -= 4; long long n = N / 6; mint ans = mint(n+1) * mint(3 * n + (N % 6)); cout << ans + (N % 6 == 0) << endl; return 0; }