// #pragma GCC optimize("Ofast") #include #include using namespace atcoder; using namespace std; using ll = long long; using ull = unsigned long long; using vecint = std::vector; using vecll = std::vector; using vecstr = std::vector; using vecbool = std::vector; using vecdou = std::vector; using vecpl = std::vector>; using vec2d = std::vector; using vec2di = std::vector; using vec2dd = std::vector; using vec2db = std::vector; using pl = pair; using mint998 = modint998244353; using mint107 = modint1000000007; using mint = modint; using vecmint = std::vector; using vecmint998 = std::vector; using vecmint107 = std::vector; using vec2dmint = std::vector; using vec2dmint998 = std::vector; using vec2dmint107 = std::vector; #define rep(i,n) for (ll i = 0; i < (ll)(n); i++) #define rep1(i,n) for (ll i = 1; i <= (ll)(n); i++) #define REP(i,l,r) for (ll i = (ll)(l); i < (ll)(r); i++) #define rrep(i,n) for (ll i = (ll)(n)-1; i >= 0; i--) #define rrep1(i,n) for (ll i = (ll)(n); i > 0; i--) #define RREP(i,l,r) for (ll i = (ll)(r)-1; i >= (ll)(l); i--) #define all(a) (a).begin(), (a).end() #define INF ((1LL<<62)-(1LL<<31)) #define inr(a,x,b) ((a) <= (x) && (x) < (b)) template bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } void ynout(bool x,string Tru="Yes",string Wro="No"){ if(x){ cout << Tru << '\n'; }else{ cout << Wro << '\n'; } } ll power(ll a,ll b,ll mod=INF){ long long x=1,y=a%mod; while(b>0){ if(b&1ll){ x=(x*y)%mod; } y=(y*y)%mod; b>>=1; } return x%mod; } ll Pdist2(pair a,pair b){ return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second); } double Pdist(pair a,pair b){ return sqrt(Pdist2(a,b)); } ll PdistM(pair a,pair b){ return abs(a.first-b.first)+abs(a.second-b.second); } ll gcd(ll a,ll b){ if(b==0){ return a; }else{ return gcd(b,a%b); } } ll lcm(ll a,ll b){ return a/gcd(a,b)*b; } void solve(); int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); ll t=1; //std::cin >> t; rep(i,t)solve(); } vecll dx = {1,0,-1,0}; vecll dy = {0,1,0,-1}; void solve(){ ll n; cin>>n; cout<