#if 1 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define in std::cin #define out std::cout template std::enable_if_t< std::is_unsigned::value, Arithmetic> ipow(Arithmetic bace, Integral n) { //繰り返し二条法 auto res = (Arithmetic)(1); while (n > 0) { if (n & 1) res *= bace; bace *= bace; n >>= 1; } return res; } constexpr bool is_prime(uint32_t N) { if (N <= 1) { return false; } for (size_t i = 2; i*i <= N; ++i) { if (N%i == 0) { return false; } } return true; } template class mint_base; //mint_base_base型用の累乗関数 template constexpr mint_base m_pow(mint_base x, uint64_t n)noexcept; //mod計算を自動で行う整数テンプレートクラス template class mint_base { public: static constexpr auto MOD = MOD_; static_assert(!(MOD <= 2), "MOD cannot be below 2."); static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない constexpr mint_base operator+(const mint_base &other)const noexcept { auto v = *this; return v += other; } constexpr mint_base operator-(const mint_base &other)const noexcept { auto v = *this; return v -= other; } constexpr mint_base operator*(const mint_base &other)const noexcept { auto v = *this; return v *= other; } constexpr auto operator/(const mint_base &other)const noexcept { auto v = *this; return v /= other; } constexpr mint_base& operator+=(const mint_base &other) noexcept { a += other.a; if (MOD <= a) { a -= MOD; }; return *this; } constexpr mint_base& operator-=(const mint_base &other) noexcept { if (a >= other.a) { a -= other.a; } else { a = (a + MOD) - other.a; } return *this; } constexpr mint_base& operator*=(const mint_base &other) noexcept { #if 1 a *= other.a; a %= MOD; #else //MOD <= (MAXUINT64 / 2)条件下 uint64_t b = other.a, v = 0; while (b > 0) { if (b & 1) { v += a; if (v >= MOD)v -= MOD; } a += a; if (MOD <= a)a -= MOD; b >>= 1; } a = v; #endif return *this; } constexpr std::enable_if_t&> operator/=(const mint_base &other) noexcept { return *this *= ipow(other, MOD - 2); } constexpr mint_base operator+()const noexcept { return *this; } constexpr mint_base operator-()const noexcept { return{ MOD - a, mod_value_tag{} }; } constexpr mint_base& operator++() noexcept { if (MOD <= ++a) { a = 0; }; return *this; } constexpr mint_base& operator--() noexcept { if (a <= 0) { a = MOD; }; --a; return *this; } constexpr mint_base operator++(int) noexcept { auto tmp = *this; ++*this; return tmp; } constexpr mint_base operator--(int) noexcept { auto tmp = *this; --*this; return tmp; } constexpr mint_base operator~()const noexcept { return ipow(*this, e_phi - 1); } constexpr mint_base& operator=(const mint_base &other) noexcept { a = other.a; return *this; } constexpr explicit operator uint64_t()const noexcept { return a; } constexpr explicit operator unsigned()const noexcept { return (unsigned)a; } static constexpr uint64_t getmod() noexcept { return MOD; } constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {} constexpr mint_base()noexcept : a(0) {} struct mod_value_tag {}; constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {} private: static constexpr uint64_t get_e_phi()noexcept { //オイラー値の導出 uint64_t temp = MOD; uint64_t m_ = MOD; for (uint64_t i = 2; i * i <= m_; ++i) { if (m_ % i == 0) { temp = temp / i * (i - 1); for (; m_ % i == 0; m_ /= i); } } if (m_ == 1)temp = temp / m_ * (m_ - 1); return temp; } static constexpr uint64_t e_phi = get_e_phi();//オイラー値 public:uint64_t a; }; //mint_base型用の累乗関数 templateconstexpr mint_base m_pow(mint_base x, uint64_t n)noexcept { mint_base res = 1; while (n > 0) { if (n & 1)res *= x; x *= x; n >>= 1; } return res; } //mint_baseの階乗計算 //O(x)時間が必要のため、fact_set関数を推奨する。 templateconstexpr mint_base fact(mint_base x)noexcept { mint_base res(1); for (uint64_t i = 1; i <= (uint64_t)x; ++i) { res *= i; } return res; } //mint_baseの階乗計算 //0からxまでの階乗を返す //O(x)時間が必要 templatestd::vector> fact_set(mint_base x = mint_base(-1)) { mint_base res(1); std::vector> set((uint64_t)(x)+1); set[0] = 1; for (uint64_t i = 1; i <= (uint64_t)x; ++i) { res *= i; set[i] = res; } return res; } //mint_base型のstreamへの出力 template std::ostream& operator<<(std::ostream& os, mint_base i) { os << (uint64_t)i; return os; } //mint_base型のstreamからの入力 template std::istream& operator >> (std::istream& is, mint_base& i) { uint64_t tmp; is >> tmp; i = tmp; return is; } typedef mint_base<1000000007> mint; namespace mint_literal { constexpr mint operator""_mi(unsigned long long x)noexcept { return mint(x); } } using namespace mint_literal; //mint_baseの階乗計算 //0からxまでの階乗を返す //O(N) //O(1) template /*constexpr*/ std::array, X + 1> fact_set_c() { mint_base res(1); std::array, X + 1> set; set[0] = 1; for (uint64_t i = 1; i <= X; ++i) { res *= i; set[i] = res; } return set; } uint64_t N; constexpr uint64_t UMEKOMI[] = { 682498929, 491101308, 76479948, 723816384, 67347853, 27368307, 625544428, 199888908, 888050723, 927880474, 281863274, 661224977, 623534362, 970055531, 261384175, 195888993, 66404266, 547665832, 109838563, 933245637, 724691727, 368925948, 268838846, 136026497, 112390913, 135498044, 217544623, 419363534, 500780548, 668123525, 128487469, 30977140, 522049725, 309058615, 386027524, 189239124, 148528617, 940567523, 917084264, 429277690, 996164327, 358655417, 568392357, 780072518, 462639908, 275105629, 909210595, 99199382, 703397904, 733333339, 97830135, 608823837, 256141983, 141827977, 696628828, 637939935, 811575797, 848924691, 131772368, 724464507, 272814771, 326159309, 456152084, 903466878, 92255682, 769795511, 373745190, 606241871, 825871994, 957939114, 435887178, 852304035, 663307737, 375297772, 217598709, 624148346, 671734977, 624500515, 748510389, 203191898, 423951674, 629786193, 672850561, 814362881, 823845496, 116667533, 256473217, 627655552, 245795606, 586445753, 172114298, 193781724, 778983779, 83868974, 315103615, 965785236, 492741665, 377329025, 847549272, 698611116, }; int main() { #if 1 using std::endl; std::scanf("%llu",&N); if (N >= mint::MOD) { puts("0"); return 0; } mint res(1); auto iter = UMEKOMI; uint64_t i = (mint::MOD / 100); for (; i <= N; i+= (mint::MOD / 100)) { res = *iter++; } for (i-= (mint::MOD / 100)-1; i <= N; ++i) { res *= i; } printf("%llu\n", (res.a)); #else std::ofstream of("out.txt"); using std::endl; mint res(1); uint64_t count = 0; for (uint64_t i = 1; i < mint::MOD; ++i) { res *= i; if (++count == (mint::MOD/100)) { of << res << ',' << endl; count = 0; } } #endif return 0; } #endif