#include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,m,n) for(ll i=m;i<(ll)(n);i++) typedef pair pint; typedef long long ll; const ll mod= 1e9+7; const int inf=1e9+7; const ll longinf = 1LL<<60; int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1}; int main(){ int n; cin>>n; cout<