#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;
}