#include #define rep(i,n) for(int i = 0; i < n; ++i) #define all(x) (x).begin(), (x).end() using namespace std; const int INF = 1145141919, MOD = 1e9 + 7; const int64_t LINF = 8931145141919364364, LMOD = 998244353; // const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; // const int dy[] = {0, -1, 0, 1, 1, -1, -1, 1}; int main() { int64_t n; cin>>n; cout<