//#include #include using namespace std; //using namespace atcoder; using ll = long long; #define all(A) A.begin(),A.end() using vll = vector; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) using Graph = vector>; vector fact, factinv, inv; int main() { ll N; cin>>N; cout<