結果
| 問題 | No.502 階乗を計算するだけ |
| ユーザー |
 m_tsubasa
|
| 提出日時 | 2020-08-11 23:35:25 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 45,126 bytes |
| コンパイル時間 | 30,243 ms |
| コンパイル使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2025-01-12 20:32:54 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
コンパイルが30秒の制限時間を超えました
ソースコード
#include <bits/stdc++.h>
using namespace std;
template <int mod = (int)(1e9 + 7)>
struct ModInt {
int x;
constexpr ModInt() : x(0) {}
constexpr ModInt(int64_t y)
: x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
constexpr ModInt &operator+=(const ModInt &p) noexcept {
if ((x += p.x) >= mod) x -= mod;
return *this;
}
constexpr ModInt &operator-=(const ModInt &p) noexcept {
if ((x += mod - p.x) >= mod) x -= mod;
return *this;
}
constexpr ModInt &operator*=(const ModInt &p) noexcept {
x = (int)(1LL * x * p.x % mod);
return *this;
}
constexpr ModInt &operator/=(const ModInt &p) noexcept {
*this *= p.inverse();
return *this;
}
constexpr ModInt operator-() const { return ModInt(-x); }
constexpr ModInt operator+(const ModInt &p) const noexcept {
return ModInt(*this) += p;
}
constexpr ModInt operator-(const ModInt &p) const noexcept {
return ModInt(*this) -= p;
}
constexpr ModInt operator*(const ModInt &p) const noexcept {
return ModInt(*this) *= p;
}
constexpr ModInt operator/(const ModInt &p) const noexcept {
return ModInt(*this) /= p;
}
constexpr bool operator==(const ModInt &p) const noexcept { return x == p.x; }
constexpr bool operator!=(const ModInt &p) const noexcept { return x != p.x; }
constexpr ModInt inverse() const noexcept {
int a = x, b = mod, u = 1, v = 0, t = 0;
while (b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
constexpr ModInt pow(int64_t n) const {
ModInt res(1), mul(x);
while (n) {
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
friend constexpr ostream &operator<<(ostream &os, const ModInt &p) noexcept {
return os << p.x;
}
friend constexpr istream &operator>>(istream &is, ModInt &a) noexcept {
int64_t t = 0;
is >> t;
a = ModInt<mod>(t);
return (is);
}
constexpr int get_mod() { return mod; }
};
using P = pair<int, int>;
vector<P> memo = {P(0, 1),
P(1000000, 641102369),
P(2000000, 578095319),
P(3000000, 5832229),
P(4000000, 259081142),
P(5000000, 974067448),
P(6000000, 316220877),
P(7000000, 690120224),
P(8000000, 251368199),
P(9000000, 980250487),
P(10000000, 682498929),
P(11000000, 134623568),
P(12000000, 95936601),
P(13000000, 933097914),
P(14000000, 167332441),
P(15000000, 598816162),
P(16000000, 336060741),
P(17000000, 248744620),
P(18000000, 626497524),
P(19000000, 288843364),
P(20000000, 491101308),
P(21000000, 245341950),
P(22000000, 565768255),
P(23000000, 246899319),
P(24000000, 968999),
P(25000000, 586350670),
P(26000000, 638587686),
P(27000000, 881746146),
P(28000000, 19426633),
P(29000000, 850500036),
P(30000000, 76479948),
P(31000000, 268124147),
P(32000000, 842267748),
P(33000000, 886294336),
P(34000000, 485348706),
P(35000000, 463847391),
P(36000000, 544075857),
P(37000000, 898187927),
P(38000000, 798967520),
P(39000000, 82926604),
P(40000000, 723816384),
P(41000000, 156530778),
P(42000000, 721996174),
P(43000000, 299085602),
P(44000000, 323604647),
P(45000000, 172827403),
P(46000000, 398699886),
P(47000000, 530389102),
P(48000000, 294587621),
P(49000000, 813805606),
P(50000000, 67347853),
P(51000000, 497478507),
P(52000000, 196447201),
P(53000000, 722054885),
P(54000000, 228338256),
P(55000000, 407719831),
P(56000000, 762479457),
P(57000000, 746536789),
P(58000000, 811667359),
P(59000000, 778773518),
P(60000000, 27368307),
P(61000000, 438371670),
P(62000000, 59469516),
P(63000000, 5974669),
P(64000000, 766196482),
P(65000000, 606322308),
P(66000000, 86609485),
P(67000000, 889750731),
P(68000000, 340941507),
P(69000000, 371263376),
P(70000000, 625544428),
P(71000000, 788878910),
P(72000000, 808412394),
P(73000000, 996952918),
P(74000000, 585237443),
P(75000000, 1669644),
P(76000000, 361786913),
P(77000000, 480748381),
P(78000000, 595143852),
P(79000000, 837229828),
P(80000000, 199888908),
P(81000000, 526807168),
P(82000000, 579691190),
P(83000000, 145404005),
P(84000000, 459188207),
P(85000000, 534491822),
P(86000000, 439729802),
P(87000000, 840398449),
P(88000000, 899297830),
P(89000000, 235861787),
P(90000000, 888050723),
P(91000000, 656116726),
P(92000000, 736550105),
P(93000000, 440902696),
P(94000000, 85990869),
P(95000000, 884343068),
P(96000000, 56305184),
P(97000000, 973478770),
P(98000000, 168891766),
P(99000000, 804805577),
P(100000000, 927880474),
P(101000000, 876297919),
P(102000000, 934814019),
P(103000000, 676405347),
P(104000000, 567277637),
P(105000000, 112249297),
P(106000000, 44930135),
P(107000000, 39417871),
P(108000000, 47401357),
P(109000000, 108819476),
P(110000000, 281863274),
P(111000000, 60168088),
P(112000000, 692636218),
P(113000000, 432775082),
P(114000000, 14235602),
P(115000000, 770511792),
P(116000000, 400295761),
P(117000000, 697066277),
P(118000000, 421835306),
P(119000000, 220108638),
P(120000000, 661224977),
P(121000000, 261799937),
P(122000000, 168203998),
P(123000000, 802214249),
P(124000000, 544064410),
P(125000000, 935080803),
P(126000000, 583967898),
P(127000000, 211768084),
P(128000000, 751231582),
P(129000000, 972424306),
P(130000000, 623534362),
P(131000000, 335160196),
P(132000000, 243276029),
P(133000000, 554749550),
P(134000000, 60050552),
P(135000000, 797848181),
P(136000000, 395891998),
P(137000000, 172428290),
P(138000000, 159554990),
P(139000000, 887420150),
P(140000000, 970055531),
P(141000000, 250388809),
P(142000000, 487998999),
P(143000000, 856259313),
P(144000000, 82104855),
P(145000000, 232253360),
P(146000000, 513365505),
P(147000000, 244109365),
P(148000000, 1559745),
P(149000000, 695345956),
P(150000000, 261384175),
P(151000000, 849009131),
P(152000000, 323214113),
P(153000000, 747664143),
P(154000000, 444090941),
P(155000000, 659224434),
P(156000000, 80729842),
P(157000000, 570033864),
P(158000000, 664989237),
P(159000000, 827348878),
P(160000000, 195888993),
P(161000000, 576798521),
P(162000000, 457882808),
P(163000000, 731551699),
P(164000000, 212938473),
P(165000000, 509096183),
P(166000000, 827544702),
P(167000000, 678320208),
P(168000000, 677711203),
P(169000000, 289752035),
P(170000000, 66404266),
P(171000000, 555972231),
P(172000000, 195290384),
P(173000000, 97136305),
P(174000000, 349551356),
P(175000000, 785113347),
P(176000000, 83489485),
P(177000000, 66247239),
P(178000000, 52167191),
P(179000000, 307390891),
P(180000000, 547665832),
P(181000000, 143066173),
P(182000000, 350016754),
P(183000000, 917404120),
P(184000000, 296269301),
P(185000000, 996122673),
P(186000000, 23015220),
P(187000000, 602139210),
P(188000000, 748566338),
P(189000000, 187348575),
P(190000000, 109838563),
P(191000000, 574053420),
P(192000000, 105574531),
P(193000000, 304173654),
P(194000000, 542432219),
P(195000000, 34538816),
P(196000000, 325636655),
P(197000000, 437843114),
P(198000000, 630621321),
P(199000000, 26853683),
P(200000000, 933245637),
P(201000000, 616368450),
P(202000000, 238971581),
P(203000000, 511371690),
P(204000000, 557301633),
P(205000000, 911398531),
P(206000000, 848952161),
P(207000000, 958992544),
P(208000000, 925152039),
P(209000000, 914456118),
P(210000000, 724691727),
P(211000000, 636817583),
P(212000000, 238087006),
P(213000000, 946237212),
P(214000000, 910291942),
P(215000000, 114985663),
P(216000000, 492237273),
P(217000000, 450387329),
P(218000000, 834860913),
P(219000000, 763017204),
P(220000000, 368925948),
P(221000000, 475812562),
P(222000000, 740594930),
P(223000000, 45060610),
P(224000000, 806047532),
P(225000000, 464456846),
P(226000000, 172115341),
P(227000000, 75307702),
P(228000000, 116261993),
P(229000000, 562519302),
P(230000000, 268838846),
P(231000000, 173784895),
P(232000000, 243624360),
P(233000000, 61570384),
P(234000000, 481661251),
P(235000000, 938269070),
P(236000000, 95182730),
P(237000000, 91068149),
P(238000000, 115435332),
P(239000000, 495022305),
P(240000000, 136026497),
P(241000000, 506496856),
P(242000000, 710729672),
P(243000000, 113570024),
P(244000000, 366384665),
P(245000000, 564758715),
P(246000000, 270239666),
P(247000000, 277118392),
P(248000000, 79874094),
P(249000000, 702807165),
P(250000000, 112390913),
P(251000000, 730341625),
P(252000000, 103056890),
P(253000000, 677948390),
P(254000000, 339464594),
P(255000000, 167240465),
P(256000000, 108312174),
P(257000000, 839079953),
P(258000000, 479334442),
P(259000000, 271788964),
P(260000000, 135498044),
P(261000000, 277717575),
P(262000000, 591048681),
P(263000000, 811637561),
P(264000000, 353339603),
P(265000000, 889410460),
P(266000000, 839849206),
P(267000000, 192345193),
P(268000000, 736265527),
P(269000000, 316439118),
P(270000000, 217544623),
P(271000000, 788132977),
P(272000000, 618898635),
P(273000000, 183011467),
P(274000000, 380858207),
P(275000000, 996097969),
P(276000000, 898554793),
P(277000000, 335353644),
P(278000000, 54062950),
P(279000000, 611251733),
P(280000000, 419363534),
P(281000000, 965429853),
P(282000000, 160398980),
P(283000000, 151319402),
P(284000000, 990918946),
P(285000000, 607730875),
P(286000000, 450718279),
P(287000000, 173539388),
P(288000000, 648991369),
P(289000000, 970937898),
P(290000000, 500780548),
P(291000000, 780122909),
P(292000000, 39052406),
P(293000000, 276894233),
P(294000000, 460373282),
P(295000000, 651081062),
P(296000000, 461415770),
P(297000000, 358700839),
P(298000000, 643638805),
P(299000000, 560006119),
P(300000000, 668123525),
P(301000000, 686692315),
P(302000000, 673464765),
P(303000000, 957633609),
P(304000000, 199866123),
P(305000000, 563432246),
P(306000000, 841799766),
P(307000000, 385330357),
P(308000000, 504962686),
P(309000000, 954061253),
P(310000000, 128487469),
P(311000000, 685707545),
P(312000000, 299172297),
P(313000000, 717975101),
P(314000000, 577786541),
P(315000000, 318951960),
P(316000000, 773206631),
P(317000000, 306832604),
P(318000000, 204355779),
P(319000000, 573592106),
P(320000000, 30977140),
P(321000000, 450398100),
P(322000000, 363172638),
P(323000000, 258379324),
P(324000000, 472935553),
P(325000000, 93940075),
P(326000000, 587220627),
P(327000000, 776264326),
P(328000000, 793270300),
P(329000000, 291733496),
P(330000000, 522049725),
P(331000000, 579995261),
P(332000000, 335416359),
P(333000000, 142946099),
P(334000000, 472012302),
P(335000000, 559947225),
P(336000000, 332139472),
P(337000000, 499377092),
P(338000000, 464599136),
P(339000000, 164752359),
P(340000000, 309058615),
P(341000000, 86117128),
P(342000000, 580204973),
P(343000000, 563781682),
P(344000000, 954840109),
P(345000000, 624577416),
P(346000000, 895609896),
P(347000000, 888287558),
P(348000000, 836813268),
P(349000000, 926036911),
P(350000000, 386027524),
P(351000000, 184419613),
P(352000000, 724205533),
P(353000000, 403351886),
P(354000000, 715247054),
P(355000000, 716986954),
P(356000000, 830567832),
P(357000000, 383388563),
P(358000000, 68409439),
P(359000000, 6734065),
P(360000000, 189239124),
P(361000000, 68322490),
P(362000000, 943653305),
P(363000000, 405755338),
P(364000000, 811056092),
P(365000000, 179518046),
P(366000000, 825132993),
P(367000000, 343807435),
P(368000000, 985084650),
P(369000000, 868553027),
P(370000000, 148528617),
P(371000000, 160684257),
P(372000000, 882148737),
P(373000000, 591915968),
P(374000000, 701445829),
P(375000000, 529726489),
P(376000000, 302177126),
P(377000000, 974886682),
P(378000000, 241107368),
P(379000000, 798830099),
P(380000000, 940567523),
P(381000000, 11633075),
P(382000000, 325334066),
P(383000000, 346091869),
P(384000000, 115312728),
P(385000000, 473718967),
P(386000000, 218129285),
P(387000000, 878471898),
P(388000000, 180002392),
P(389000000, 699739374),
P(390000000, 917084264),
P(391000000, 856859395),
P(392000000, 435327356),
P(393000000, 808651347),
P(394000000, 421623838),
P(395000000, 105419548),
P(396000000, 59883031),
P(397000000, 322487421),
P(398000000, 79716267),
P(399000000, 715317963),
P(400000000, 429277690),
P(401000000, 398078032),
P(402000000, 316486674),
P(403000000, 384843585),
P(404000000, 940338439),
P(405000000, 937409008),
P(406000000, 940524812),
P(407000000, 947549662),
P(408000000, 833550543),
P(409000000, 593524514),
P(410000000, 996164327),
P(411000000, 987314628),
P(412000000, 697611981),
P(413000000, 636177449),
P(414000000, 274192146),
P(415000000, 418537348),
P(416000000, 925347821),
P(417000000, 952831975),
P(418000000, 893732627),
P(419000000, 1277567),
P(420000000, 358655417),
P(421000000, 141866945),
P(422000000, 581830879),
P(423000000, 987597705),
P(424000000, 347046911),
P(425000000, 775305697),
P(426000000, 125354499),
P(427000000, 951540811),
P(428000000, 247662371),
P(429000000, 343043237),
P(430000000, 568392357),
P(431000000, 997474832),
P(432000000, 209244402),
P(433000000, 380480118),
P(434000000, 149586983),
P(435000000, 392838702),
P(436000000, 309134554),
P(437000000, 990779998),
P(438000000, 263053337),
P(439000000, 325362513),
P(440000000, 780072518),
P(441000000, 551028176),
P(442000000, 990826116),
P(443000000, 989944961),
P(444000000, 155569943),
P(445000000, 596737944),
P(446000000, 711553356),
P(447000000, 268844715),
P(448000000, 451373308),
P(449000000, 379404150),
P(450000000, 462639908),
P(451000000, 961812918),
P(452000000, 654611901),
P(453000000, 382776490),
P(454000000, 41815820),
P(455000000, 843321396),
P(456000000, 675258797),
P(457000000, 845583555),
P(458000000, 934281721),
P(459000000, 741114145),
P(460000000, 275105629),
P(461000000, 666247477),
P(462000000, 325912072),
P(463000000, 526131620),
P(464000000, 252551589),
P(465000000, 432030917),
P(466000000, 554917439),
P(467000000, 818036959),
P(468000000, 754363835),
P(469000000, 795190182),
P(470000000, 909210595),
P(471000000, 278704903),
P(472000000, 719566487),
P(473000000, 628514947),
P(474000000, 424989675),
P(475000000, 321685608),
P(476000000, 50590510),
P(477000000, 832069712),
P(478000000, 198768464),
P(479000000, 702004730),
P(480000000, 99199382),
P(481000000, 707469729),
P(482000000, 747407118),
P(483000000, 302020341),
P(484000000, 497196934),
P(485000000, 5003231),
P(486000000, 726997875),
P(487000000, 382617671),
P(488000000, 296229203),
P(489000000, 183888367),
P(490000000, 703397904),
P(491000000, 552133875),
P(492000000, 732868367),
P(493000000, 350095207),
P(494000000, 26031303),
P(495000000, 863250534),
P(496000000, 216665960),
P(497000000, 561745549),
P(498000000, 352946234),
P(499000000, 784139777),
P(500000000, 733333339),
P(501000000, 503105966),
P(502000000, 459878625),
P(503000000, 803187381),
P(504000000, 16634739),
P(505000000, 180898306),
P(506000000, 68718097),
P(507000000, 985594252),
P(508000000, 404206040),
P(509000000, 749724532),
P(510000000, 97830135),
P(511000000, 611751357),
P(512000000, 31131935),
P(513000000, 662741752),
P(514000000, 864326453),
P(515000000, 864869025),
P(516000000, 167831173),
P(517000000, 559214642),
P(518000000, 718498895),
P(519000000, 91352335),
P(520000000, 608823837),
P(521000000, 473379392),
P(522000000, 385388084),
P(523000000, 152267158),
P(524000000, 681756977),
P(525000000, 46819124),
P(526000000, 313132653),
P(527000000, 56547945),
P(528000000, 442795120),
P(529000000, 796616594),
P(530000000, 256141983),
P(531000000, 152028387),
P(532000000, 636578562),
P(533000000, 385377759),
P(534000000, 553033642),
P(535000000, 491415383),
P(536000000, 919273670),
P(537000000, 996049638),
P(538000000, 326686486),
P(539000000, 160150665),
P(540000000, 141827977),
P(541000000, 540818053),
P(542000000, 693305776),
P(543000000, 593938674),
P(544000000, 186576440),
P(545000000, 688809790),
P(546000000, 565456578),
P(547000000, 749296077),
P(548000000, 519397500),
P(549000000, 551096742),
P(550000000, 696628828),
P(551000000, 775025061),
P(552000000, 370732451),
P(553000000, 164246193),
P(554000000, 915265013),
P(555000000, 457469634),
P(556000000, 923043932),
P(557000000, 912368644),
P(558000000, 777901604),
P(559000000, 464118005),
P(560000000, 637939935),
P(561000000, 956856710),
P(562000000, 490676632),
P(563000000, 453019482),
P(564000000, 462528877),
P(565000000, 502297454),
P(566000000, 798895521),
P(567000000, 100498586),
P(568000000, 699767918),
P(569000000, 849974789),
P(570000000, 811575797),
P(571000000, 438952959),
P(572000000, 606870929),
P(573000000, 907720182),
P(574000000, 179111720),
P(575000000, 48053248),
P(576000000, 508038818),
P(577000000, 811944661),
P(578000000, 752550134),
P(579000000, 401382061),
P(580000000, 848924691),
P(581000000, 764368449),
P(582000000, 34629406),
P(583000000, 529840945),
P(584000000, 435904287),
P(585000000, 26011548),
P(586000000, 208184231),
P(587000000, 446477394),
P(588000000, 206330671),
P(589000000, 366033520),
P(590000000, 131772368),
P(591000000, 185646898),
P(592000000, 648711554),
P(593000000, 472759660),
P(594000000, 523696723),
P(595000000, 271198437),
P(596000000, 25058942),
P(597000000, 859369491),
P(598000000, 817928963),
P(599000000, 330711333),
P(600000000, 724464507),
P(601000000, 437605233),
P(602000000, 701453022),
P(603000000, 626663115),
P(604000000, 281230685),
P(605000000, 510650790),
P(606000000, 596949867),
P(607000000, 295726547),
P(608000000, 303076380),
P(609000000, 465070856),
P(610000000, 272814771),
P(611000000, 538771609),
P(612000000, 48824684),
P(613000000, 951279549),
P(614000000, 939889684),
P(615000000, 564188856),
P(616000000, 48527183),
P(617000000, 201307702),
P(618000000, 484458461),
P(619000000, 861754542),
P(620000000, 326159309),
P(621000000, 181594759),
P(622000000, 668422905),
P(623000000, 286273596),
P(624000000, 965656187),
P(625000000, 44135644),
P(626000000, 359960756),
P(627000000, 936229527),
P(628000000, 407934361),
P(629000000, 267193060),
P(630000000, 456152084),
P(631000000, 459116722),
P(632000000, 124804049),
P(633000000, 262322489),
P(634000000, 920251227),
P(635000000, 816929577),
P(636000000, 483924582),
P(637000000, 151834896),
P(638000000, 167087470),
P(639000000, 490222511),
P(640000000, 903466878),
P(641000000, 361583925),
P(642000000, 368114731),
P(643000000, 339383292),
P(644000000, 388728584),
P(645000000, 218107212),
P(646000000, 249153339),
P(647000000, 909458706),
P(648000000, 322908524),
P(649000000, 202649964),
P(650000000, 92255682),
P(651000000, 573074791),
P(652000000, 15570863),
P(653000000, 94331513),
P(654000000, 744158074),
P(655000000, 196345098),
P(656000000, 334326205),
P(657000000, 9416035),
P(658000000, 98349682),
P(659000000, 882121662),
P(660000000, 769795511),
P(661000000, 231988936),
P(662000000, 888146074),
P(663000000, 137603545),
P(664000000, 582627184),
P(665000000, 407518072),
P(666000000, 919419361),
P(667000000, 909433461),
P(668000000, 986708498),
P(669000000, 310317874),
P(670000000, 373745190),
P(671000000, 263645931),
P(672000000, 256853930),
P(673000000, 876379959),
P(674000000, 702823274),
P(675000000, 147050765),
P(676000000, 308186532),
P(677000000, 175504139),
P(678000000, 180350107),
P(679000000, 797736554),
P(680000000, 606241871),
P(681000000, 384547635),
P(682000000, 273712630),
P(683000000, 586444655),
P(684000000, 682189174),
P(685000000, 666493603),
P(686000000, 946867127),
P(687000000, 819114541),
P(688000000, 502371023),
P(689000000, 261970285),
P(690000000, 825871994),
P(691000000, 126925175),
P(692000000, 701506133),
P(693000000, 314738056),
P(694000000, 341779962),
P(695000000, 561011609),
P(696000000, 815463367),
P(697000000, 46765164),
P(698000000, 49187570),
P(699000000, 188054995),
P(700000000, 957939114),
P(701000000, 64814326),
P(702000000, 933376898),
P(703000000, 329837066),
P(704000000, 338121343),
P(705000000, 765215899),
P(706000000, 869630152),
P(707000000, 978119194),
P(708000000, 632627667),
P(709000000, 975266085),
P(710000000, 435887178),
P(711000000, 282092463),
P(712000000, 129621197),
P(713000000, 758245605),
P(714000000, 827722926),
P(715000000, 201339230),
P(716000000, 918513230),
P(717000000, 322096036),
P(718000000, 547838438),
P(719000000, 985546115),
P(720000000, 852304035),
P(721000000, 593090119),
P(722000000, 689189630),
P(723000000, 555842733),
P(724000000, 567033437),
P(725000000, 469928208),
P(726000000, 212842957),
P(727000000, 117842065),
P(728000000, 404149413),
P(729000000, 155133422),
P(730000000, 663307737),
P(731000000, 208761293),
P(732000000, 206282795),
P(733000000, 717946122),
P(734000000, 488906585),
P(735000000, 414236650),
P(736000000, 280700600),
P(737000000, 962670136),
P(738000000, 534279149),
P(739000000, 214569244),
P(740000000, 375297772),
P(741000000, 811053196),
P(742000000, 922377372),
P(743000000, 289594327),
P(744000000, 219932130),
P(745000000, 211487466),
P(746000000, 701050258),
P(747000000, 398782410),
P(748000000, 863002719),
P(749000000, 27236531),
P(750000000, 217598709),
P(751000000, 375472836),
P(752000000, 810551911),
P(753000000, 178598958),
P(754000000, 247844667),
P(755000000, 676526196),
P(756000000, 812283640),
P(757000000, 863066876),
P(758000000, 857241854),
P(759000000, 113917835),
P(760000000, 624148346),
P(761000000, 726089763),
P(762000000, 564827277),
P(763000000, 826300950),
P(764000000, 478982047),
P(765000000, 439411911),
P(766000000, 454039189),
P(767000000, 633292726),
P(768000000, 48562889),
P(769000000, 802100365),
P(770000000, 671734977),
P(771000000, 945204804),
P(772000000, 508831870),
P(773000000, 398781902),
P(774000000, 897162044),
P(775000000, 644050694),
P(776000000, 892168027),
P(777000000, 828883117),
P(778000000, 277714559),
P(779000000, 713448377),
P(780000000, 624500515),
P(781000000, 590098114),
P(782000000, 808691930),
P(783000000, 514359662),
P(784000000, 895205045),
P(785000000, 715264908),
P(786000000, 628829100),
P(787000000, 484492064),
P(788000000, 919717789),
P(789000000, 513196123),
P(790000000, 748510389),
P(791000000, 403652653),
P(792000000, 574455974),
P(793000000, 77123823),
P(794000000, 172096141),
P(795000000, 819801784),
P(796000000, 581418893),
P(797000000, 15655126),
P(798000000, 15391652),
P(799000000, 875641535),
P(800000000, 203191898),
P(801000000, 264582598),
P(802000000, 880691101),
P(803000000, 907800444),
P(804000000, 986598821),
P(805000000, 340030191),
P(806000000, 264688936),
P(807000000, 369832433),
P(808000000, 785804644),
P(809000000, 842065079),
P(810000000, 423951674),
P(811000000, 663560047),
P(812000000, 696623384),
P(813000000, 496709826),
P(814000000, 161960209),
P(815000000, 331910086),
P(816000000, 541120825),
P(817000000, 951524114),
P(818000000, 841656666),
P(819000000, 162683802),
P(820000000, 629786193),
P(821000000, 190395535),
P(822000000, 269571439),
P(823000000, 832671304),
P(824000000, 76770272),
P(825000000, 341080135),
P(826000000, 421943723),
P(827000000, 494210290),
P(828000000, 751040886),
P(829000000, 317076664),
P(830000000, 672850561),
P(831000000, 72482816),
P(832000000, 493689107),
P(833000000, 135625240),
P(834000000, 100228913),
P(835000000, 684748812),
P(836000000, 639655136),
P(837000000, 906233141),
P(838000000, 929893103),
P(839000000, 277813439),
P(840000000, 814362881),
P(841000000, 562608724),
P(842000000, 406024012),
P(843000000, 885537778),
P(844000000, 10065330),
P(845000000, 60625018),
P(846000000, 983737173),
P(847000000, 60517502),
P(848000000, 551060742),
P(849000000, 804930491),
P(850000000, 823845496),
P(851000000, 727416538),
P(852000000, 946421040),
P(853000000, 678171399),
P(854000000, 842203531),
P(855000000, 175638827),
P(856000000, 894247956),
P(857000000, 538609927),
P(858000000, 885362182),
P(859000000, 946464959),
P(860000000, 116667533),
P(861000000, 749816133),
P(862000000, 241427979),
P(863000000, 871117927),
P(864000000, 281804989),
P(865000000, 163928347),
P(866000000, 563796647),
P(867000000, 640266394),
P(868000000, 774625892),
P(869000000, 59342705),
P(870000000, 256473217),
P(871000000, 674115061),
P(872000000, 918860977),
P(873000000, 322633051),
P(874000000, 753513874),
P(875000000, 393556719),
P(876000000, 304644842),
P(877000000, 767372800),
P(878000000, 161362528),
P(879000000, 754787150),
P(880000000, 627655552),
P(881000000, 677395736),
P(882000000, 799289297),
P(883000000, 846650652),
P(884000000, 816701166),
P(885000000, 687265514),
P(886000000, 787113234),
P(887000000, 358757251),
P(888000000, 701220427),
P(889000000, 607715125),
P(890000000, 245795606),
P(891000000, 600624983),
P(892000000, 10475577),
P(893000000, 728620948),
P(894000000, 759404319),
P(895000000, 36292292),
P(896000000, 491466901),
P(897000000, 22556579),
P(898000000, 114495791),
P(899000000, 647630109),
P(900000000, 586445753),
P(901000000, 482254337),
P(902000000, 718623833),
P(903000000, 763514207),
P(904000000, 66547751),
P(905000000, 953634340),
P(906000000, 351472920),
P(907000000, 308474522),
P(908000000, 494166907),
P(909000000, 634359666),
P(910000000, 172114298),
P(911000000, 865440961),
P(912000000, 364380585),
P(913000000, 921648059),
P(914000000, 965683742),
P(915000000, 260466949),
P(916000000, 117483873),
P(917000000, 962540888),
P(918000000, 237120480),
P(919000000, 620531822),
P(920000000, 193781724),
P(921000000, 213092254),
P(922000000, 107141741),
P(923000000, 602742426),
P(924000000, 793307102),
P(925000000, 756154604),
P(926000000, 236455213),
P(927000000, 362928234),
P(928000000, 14162538),
P(929000000, 753042874),
P(930000000, 778983779),
P(931000000, 25977209),
P(932000000, 49389215),
P(933000000, 698308420),
P(934000000, 859637374),
P(935000000, 49031023),
P(936000000, 713258160),
P(937000000, 737331920),
P(938000000, 923333660),
P(939000000, 804861409),
P(940000000, 83868974),
P(941000000, 682873215),
P(942000000, 217298111),
P(943000000, 883278906),
P(944000000, 176966527),
P(945000000, 954913),
P(946000000, 105359006),
P(947000000, 390019735),
P(948000000, 10430738),
P(949000000, 706334445),
P(950000000, 315103615),
P(951000000, 567473423),
P(952000000, 708233401),
P(953000000, 48160594),
P(954000000, 946149627),
P(955000000, 346966053),
P(956000000, 281329488),
P(957000000, 462880311),
P(958000000, 31503476),
P(959000000, 185438078),
P(960000000, 965785236),
P(961000000, 992656683),
P(962000000, 916291845),
P(963000000, 881482632),
P(964000000, 899946391),
P(965000000, 321900901),
P(966000000, 512634493),
P(967000000, 303338827),
P(968000000, 121000338),
P(969000000, 967284733),
P(970000000, 492741665),
P(971000000, 152233223),
P(972000000, 165393390),
P(973000000, 680128316),
P(974000000, 917041303),
P(975000000, 532702135),
P(976000000, 741626808),
P(977000000, 496442755),
P(978000000, 536841269),
P(979000000, 131384366),
P(980000000, 377329025),
P(981000000, 301196854),
P(982000000, 859917803),
P(983000000, 676511002),
P(984000000, 373451745),
P(985000000, 847645126),
P(986000000, 823495900),
P(987000000, 576368335),
P(988000000, 73146164),
P(989000000, 954958912),
P(990000000, 847549272),
P(991000000, 241289571),
P(992000000, 646654592),
P(993000000, 216046746),
P(994000000, 205951465),
P(995000000, 3258987),
P(996000000, 780882948),
P(997000000, 822439091),
P(998000000, 598245292),
P(999000000, 869544707),
P(1000000000, 698611116)};
long long n;
int main() {
cin >> n;
if (n >= (long long)(1e9 + 7))
cout << 0 << endl;
else {
auto p = *(--lower_bound(memo.begin(), memo.end(), P(n, 2e9)));
ModInt<> res = p.second;
for (int i = p.first + 1; i <= n; ++i) res *= i;
cout << res << endl;
}
return 0;
}