题目描述
思路
代码
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define pr make_pair #define ms(x, y) memset(x, y, sizeof(x)) typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; const int MAX_N = 1e5 + 5; const ll MOD = 1e9 + 7; const ll X = 1e6; const ll L[1005] = {1, 102701088, 981992119, 649506278, 627764250, 645138131, 564166077, 806340002, 832288921, 136850473, 824182295, 485486901, 362408075, 230615570, 207753791, 746724534, 218498984, 781396008, 329051776, 323681136, 933713113, 55283981, 981439786, 825501686, 138007547, 342331196, 289391657, 825412508, 187428012, 141252153, 474482547, 469345798, 143251826, 921539885, 480488466, 371921930, 231080468, 854891028, 745269989, 838798600, 930651136, 166822045, 373911211, 895972398, 171482268, 451712763, 958587080, 752005616, 988795902, 572897149, 251064654, 321585864, 511830767, 631659409, 144463808, 390942798, 102930668, 688993450, 106803430, 736094471, 637937211, 67539869, 144102058, 272682427, 403369349, 888623609, 858619719, 775950042, 15647887, 791153158, 229643390, 418285941, 386152375, 926363365, 39644216, 774661798, 40160713, 396825904, 995555017, 857467965, 307311871, 322363308, 558471991, 849546729, 702107511, 610253183, 836510216, 371849840, 951720735, 611938075, 448853213, 916443128, 719396272, 62461078, 829557374, 360973550, 28257290, 54217657, 360608813, 40750050, 322273426, 994158933, 169297167, 816619563, 578752871, 360557868, 348588664, 773488558, 383760456, 253636234, 398890147, 995241802, 479632402, 110532161, 700282646, 282610478, 140824426, 295951236, 857609436, 760044280, 194914852, 443829327, 876081218, 524150684, 964703318, 503814959, 3721180, 438887824, 780454157, 618807385, 884947442, 765009239, 49016763, 277882991, 686914924, 394281833, 9292295, 180115281, 827376728, 884535605, 154199209, 244167252, 56875341, 100252189, 949590677, 930382776, 186095009, 915325731, 487153268, 999188962, 881788023, 26750235, 843660084, 825675146, 480858823, 814808681, 562764753, 388965635, 868321452, 793774212, 389699639, 696033877, 824165623, 729212269, 903496758, 13694466, 125127133, 802590026, 78636716, 991813302, 733217502, 340792204, 163694105, 729692726, 66435775, 124648772, 579867155, 90056478, 540654765, 368988366, 601739182, 416701437, 445350912, 616246755, 591423736, 392220359, 536341336, 964430099, 531887312, 559587397, 372305477, 718309972, 926423310, 42000939, 639265371, 28855165, 677697221, 103286437, 484351515, 607563402, 213823357, 872307731, 372467702, 126282642, 345280228, 984769112, 717461814, 487124435, 757943584, 562591933, 713959988, 970592690, 854865267, 918201995, 777177924, 466044211, 718369887, 595693165, 48090102, 581617266, 498202615, 215303046, 391636760, 679592087, 66223098, 332910243, 554427583, 437417932, 759812013, 129290794, 196342945, 383628392, 474049070, 499347791, 729105951, 715068952, 708424167, 417690245, 981761551, 100358731, 324300550, 448815874, 976802967, 355804045, 868183507, 299712064, 548578229, 311019993, 739059075, 589778521, 154001751, 348119666, 539751867, 574158273, 788685196, 791279153, 624440017, 961214770, 231405777, 245724014, 974475946, 275533551, 845138374, 157087033, 736460202, 470540891, 871607895, 745317906, 387858087, 242782878, 540773759, 747935865, 859460625, 228821922, 723487306, 468917247, 724324069, 476378557, 770600635, 250470252, 467881322, 300357120, 676487052, 462154550, 311697536, 428812399, 450648083, 778076329, 786255939, 765849472, 257531902, 721767280, 176563389, 175749454, 732296574, 298120095, 155448833, 898525679, 85049317, 968406065, 598680559, 395844987, 900957536, 579095485, 429212998, 509837298, 853242300, 922588922, 68856856, 283770130, 367927849, 522655659, 690757326, 912348796, 30049334, 131745858, 137674199, 142648551, 600945940, 449239819, 971346692, 670051193, 737038504, 865244796, 723942192, 610008278, 752447580, 905516484, 656581760, 91825933, 94577421, 283622038, 849585022, 102547070, 323875198, 420318614, 779228990, 786063302, 988963335, 164868451, 617165552, 905989955, 6391586, 421243975, 739350754, 362563274, 347053973, 576876354, 394564599, 99117090, 128327758, 435476476, 728083087, 600210704, 507934245, 259790921, 404690060, 506558658, 328287279, 237225611, 503709458, 465806023, 631623755, 594216496, 370047171, 737911496, 151018717, 113095146, 128457419, 880656919, 253566817, 184922743, 223563582, 252228570, 266519182, 876803028, 194040840, 997525075, 847784903, 464959842, 820144401, 163870432, 885252811, 688921891, 193947871, 21626547, 958041818, 727618041, 842250, 378454511, 13965056, 409131285, 863668228, 688461155, 117468217, 29814411, 531114442, 25589724, 254857335, 305168698, 82358069, 445751007, 411378564, 381536877, 933633977, 702145011, 687788151, 558820531, 829116226, 956393708, 805941568, 178263460, 900513582, 928732556, 122675017, 699849090, 47406175, 823318492, 754665638, 211464760, 533047638, 354855600, 56228475, 889527707, 89342482, 925349438, 352847983, 184575152, 162590565, 402474435, 69430220, 53717597, 499227545, 727117226, 389321885, 505427812, 689377848, 739141890, 851692242, 36961625, 686678173, 898151821, 341673172, 603840769, 314510027, 988116160, 292613275, 643463284, 987869224, 86904847, 297170813, 210607265, 125056557, 522472396, 56762503, 268825217, 657107621, 541102843, 405700172, 597167891, 34546238, 219235406, 288417029, 32306949, 6461506, 75810449, 187271994, 958412125, 923423574, 174329621, 323435423, 134419822, 86333313, 623634963, 819270744, 708774997, 864549168, 184708668, 808590464, 146071060, 499126069, 957779045, 733872556, 966196700, 801414729, 725378301, 475620410, 387306873, 921714578, 242623264, 487532712, 808421122, 796370648, 958262856, 56469791, 969427220, 906919416, 154436480, 771008169, 213577806, 468899710, 432769540, 870216603, 51442776, 12237969, 675843097, 34760677, 396204835, 176554723, 414179745, 790590914, 225772745, 567888121, 233151084, 152099332, 751227942, 46458325, 674788795, 790702570, 489845612, 581347156, 369818845, 15615037, 545967596, 103309552, 389860753, 719815661, 91664918, 301486883, 791845156, 955359050, 779856088, 44321908, 489350942, 644787192, 55206524, 633954632, 598404606, 901413642, 149686777, 700529992, 579052159, 565835015, 118847032, 867926968, 97589652, 729449902, 6064412, 401641163, 221211052, 518280890, 609694504, 63376104, 428801015, 700687934, 839096293, 114480112, 98459976, 876598556, 693812577, 98592091, 74920668, 224533248, 721549085, 970958369, 117610907, 347169727, 961003451, 478317111, 306883443, 64544225, 131097347, 11349170, 278833977, 412976440, 72910913, 191951439, 443412274, 570830448, 149888564, 988209678, 265614314, 152910522, 327272434, 752186716, 718262387, 133171332, 618790917, 53007885, 650106860, 422603955, 660805266, 503088446, 947525042, 635064394, 781322580, 447596506, 461800272, 848471668, 994245679, 40661679, 298018995, 657681727, 690493596, 651688259, 263114315, 625223306, 676841440, 338387319, 196183571, 174468756, 736236357, 307800572, 232333370, 680437177, 135268337, 94262259, 770243628, 584612051, 457097995, 573631136, 676573626, 577189995, 357633724, 491460743, 183599737, 710075282, 650365986, 746259674, 604986809, 757555557, 422575560, 51985410, 521611328, 59618475, 551225407, 521615404, 187849667, 486159922, 34760970, 710709955, 68171314, 939418137, 95539701, 729618083, 669334209, 91219418, 557643173, 582111925, 687457420, 775098981, 898616827, 603014921, 576780933, 893649850, 278152475, 203936502, 158338523, 977791269, 446417809, 499158883, 632455012, 596308186, 941696136, 698436253, 417623410, 894434290, 88077857, 914667320, 174322412, 969149294, 488979053, 19360531, 551406263, 73316989, 119956407, 847556159, 152414193, 15968687, 103264601, 880429710, 963452539, 316525653, 363527941, 565064060, 950456028, 875759441, 715221164, 333793105, 401872114, 42564126, 757147276, 585211132, 442500985, 949069261, 480460278, 447188779, 95227949, 994464164, 991942192, 333697951, 954980943, 178264106, 915367944, 150152513, 159044774, 181427295, 574673435, 164721975, 713579760, 522067888, 820113517, 404395270, 459838540, 175975086, 139109834, 531733674, 414553797, 17880902, 333986091, 579797877, 473169256, 788793995, 820866545, 948934214, 702467776, 314706865, 200780118, 211722873, 818674597, 528967798, 962265651, 515626105, 517981574, 768844703, 208784939, 664133726, 950847823, 177984668, 618427638, 717694718, 803357822, 751009820, 376612251, 691294576, 756271819, 211958024, 543942422, 197601451, 947893174, 309384913, 234460299, 452161730, 934679817, 650662942, 815852027, 812802047, 356180431, 780228545, 435897276, 31308092, 440411884, 218696216, 960164158, 154837346, 38316616, 962683091, 10606516, 552913767, 606494944, 316850320, 364888293, 94513584, 294155313, 501476310, 567610607, 822846632, 345872164, 516729942, 86574506, 220854491, 306148897, 929299169, 423969930, 125383915, 782132070, 667142092, 184842982, 481533802, 770543419, 878646494, 831895011, 575605965, 258561151, 39657326, 430961569, 849881078, 746427504, 480064563, 889303958, 963974981, 898310091, 746327924, 259305179, 267660342, 677796098, 560277115, 821037552, 72328802, 987119561, 377654637, 943684790, 632757568, 205829180, 3053655, 972289649, 395572519, 686813938, 609494839, 670784224, 705101053, 125163116, 202791269, 973029224, 28732033, 671770693, 630644805, 159448906, 192678133, 109528400, 542246848, 655276546, 350104791, 339661876, 811164546, 523433471, 913806489, 681290582, 320368010, 184855330, 466289530, 539681423, 790812019, 439374936, 461375205, 209088494, 867942331, 476008696, 18780215, 520734953, 750036412, 738072355, 952000246, 218649908, 160577387, 619720649, 562085462, 705486526, 22383103, 435748056, 819636314, 443829864, 351469219, 609164310, 111175592, 458416215, 63207979, 361128966, 817329481, 102726115, 688721174, 890414414, 99411932, 154717014, 44860063, 594743835, 900253101, 909158470, 817994577, 933285383, 464087273, 753073278, 999122550, 47465597, 951314008, 645783065, 316910697, 132946886, 383979285, 877774703, 517164631, 915986682, 331585939, 797408571, 624813671, 280636995, 170701415, 241387050, 696417434, 877840727, 256789690, 280434105, 927498321, 737288545, 520988669, 56826112, 685369539, 131583290, 719116784, 880238527, 482685016, 605351713, 993736121, 206881884, 811177899, 141317021, 3335944, 585698084, 682073860, 531426532, 276682441, 663644092, 689352730, 727852213, 746814819, 184143102, 428872926, 481695945, 218798350, 773608829, 473333947, 116103680, 655473387, 968076915, 86359458, 334781593, 717843074, 37035206, 134224352, 615288312, 340221393, 901599799, 264410783, 458906778, 806163165, 144415001, 56614453, 868868442, 454860259, 357904502, 762927538, 930045611, 768284771, 349135872, 375939507, 726718378, 896128453, 285627228, 668118735, 198917702, 624766601, 425203890, 855319974, 767663944, 540515728, 317375305, 348158328, 809965487, 392140412, 661597068, 984537252, 670848732, 400577109, 640781611, 437555867, 116644591, 178175499, 738119236, 6174353, 123815837, 977632075, 118428592, 215737742, 626057315, 535141995, 511506338, 204569608, 676562680, 681205105, 252631325, 34192646, 396906487, 914120126, 14839562, 611781105, 176769488, 320106189, 532057908, 152225254, 960210904, 402182971}; int main() { ll n; cin >> n; ll ans = L[n / X]; for (ll i = n / X * X + 1; i <= n; i++) { // printf("i = %lld, ans = %lld\n", i, ans); ans = ans * i % MOD; if (i % 2 == 0) ans = (ans + 1) % MOD; else ans = (ans + MOD - 1) % MOD; } cout << ans << endl; return 0; }
- 第二种有点长，这边建议拉滑动条
#include<iostream> #include<cstring> #include<vector> #include<map> using namespace std; using LL = long long; int main(){ #ifdef LOCAL freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); map<int, int> mp; mp[0] = 1; mp[1] = 0; mp[1000000] = 102701088; mp[1000001] = 189982180; mp[2000000] = 981992119; mp[2000001] = 206244223; mp[3000000] = 649506278; mp[3000001] = 469866644; mp[4000000] = 627764250; mp[4000001] = 610186850; mp[5000000] = 645138131; mp[5000001] = 277558293; mp[6000000] = 564166077; mp[6000001] = 2471097; mp[7000000] = 806340002; mp[7000001] = 780829341; mp[8000000] = 832288921; mp[8000001] = 153680736; mp[9000000] = 136850473; mp[9000001] = 385228894; mp[10000000] = 824182295; mp[10000001] = 716489533; mp[11000000] = 485486901; mp[11000001] = 359104408; mp[12000000] = 362408075; mp[12000001] = 231965795; mp[13000000] = 230615570; mp[13000001] = 619629555; mp[14000000] = 207753791; mp[14000001] = 261393919; mp[15000000] = 746724534; mp[15000001] = 678318457; mp[16000000] = 218498984; mp[16000001] = 938027102; mp[17000000] = 781396008; mp[17000001] = 824409883; mp[18000000] = 329051776; mp[18000001] = 255591251; mp[19000000] = 323681136; mp[19000001] = 864631548; mp[20000000] = 933713113; mp[20000001] = 62993271; mp[21000000] = 55283981; mp[21000001] = 648157239; mp[22000000] = 981439786; mp[22000001] = 122298053; mp[23000000] = 825501686; mp[23000001] = 470595912; mp[24000000] = 138007547; mp[24000001] = 242822279; mp[25000000] = 342331196; mp[25000001] = 182423235; mp[26000000] = 289391657; mp[26000001] = 318722375; mp[27000000] = 825412508; mp[27000001] = 385409541; mp[28000000] = 187428012; mp[28000001] = 486692123; mp[29000000] = 141252153; mp[29000001] = 549577968; mp[30000000] = 474482547; mp[30000001] = 784841214; mp[31000000] = 469345798; mp[31000001] = 105497757; mp[32000000] = 143251826; mp[32000001] = 543163419; mp[33000000] = 921539885; mp[33000001] = 913664172; mp[34000000] = 480488466; mp[34000001] = 210132209; mp[35000000] = 371921930; mp[35000001] = 830801060; mp[36000000] = 231080468; mp[36000001] = 20848188; mp[37000000] = 854891028; mp[37000001] = 669474251; mp[38000000] = 745269989; mp[38000001] = 129028168; mp[39000000] = 838798600; mp[39000001] = 9806577; mp[40000000] = 930651136; mp[40000001] = 110068813; mp[41000000] = 166822045; mp[41000001] = 963944123; mp[42000000] = 373911211; mp[42000001] = 125981313; mp[43000000] = 895972398; mp[43000001] = 740284706; mp[44000000] = 171482268; mp[44000001] = 910665734; mp[45000000] = 451712763; mp[45000001] = 644423244; mp[46000000] = 958587080; mp[46000001] = 329922037; mp[47000000] = 752005616; mp[47000001] = 456595767; mp[48000000] = 988795902; mp[48000001] = 952560480; mp[49000000] = 572897149; mp[49000001] = 677393428; mp[50000000] = 251064654; mp[50000001] = 863192029; mp[51000000] = 321585864; mp[51000001] = 270779710; mp[52000000] = 511830767; mp[52000001] = 209524366; mp[53000000] = 631659409; mp[53000001] = 74313765; mp[54000000] = 144463808; mp[54000001] = 721856492; mp[55000000] = 390942798; mp[55000001] = 130429819; mp[56000000] = 102930668; mp[56000001] = 470581848; mp[57000000] = 688993450; mp[57000001] = 64085060; mp[58000000] = 106803430; mp[58000001] = 3441236; mp[59000000] = 736094471; mp[59000001] = 221087452; mp[60000000] = 637937211; mp[60000001] = 30003579; mp[61000000] = 67539869; mp[61000001] = 47700344; mp[62000000] = 144102058; mp[62000001] = 677561768; mp[63000000] = 272682427; mp[63000001] = 53429475; mp[64000000] = 403369349; mp[64000001] = 558659882; mp[65000000] = 888623609; mp[65000001] = 69299863; mp[66000000] = 858619719; mp[66000001] = 915937411; mp[67000000] = 775950042; mp[67000001] = 226029470; mp[68000000] = 15647887; mp[68000001] = 324199494; mp[69000000] = 791153158; mp[69000001] = 311026181; mp[70000000] = 229643390; mp[70000001] = 417118130; mp[71000000] = 418285941; mp[71000001] = 21397826; mp[72000000] = 386152375; mp[72000001] = 191531577; mp[73000000] = 926363365; mp[73000001] = 97991682; mp[74000000] = 39644216; mp[74000001] = 3108511; mp[75000000] = 774661798; mp[75000001] = 217964352; mp[76000000] = 40160713; mp[76000001] = 206795214; mp[77000000] = 396825904; mp[77000001] = 790936745; mp[78000000] = 995555017; mp[78000001] = 777981979; mp[79000000] = 857467965; mp[79000001] = 618288181; mp[80000000] = 307311871; mp[80000001] = 815217227; mp[81000000] = 322363308; mp[81000001] = 87583311; mp[82000000] = 558471991; mp[82000001] = 499909069; mp[83000000] = 849546729; mp[83000001] = 862960082; mp[84000000] = 702107511; mp[84000001] = 213268293; mp[85000000] = 610253183; mp[85000001] = 802152542; mp[86000000] = 836510216; mp[86000001] = 908931069; mp[87000000] = 371849840; mp[87000001] = 225393287; mp[88000000] = 951720735; mp[88000001] = 45460759; mp[89000000] = 611938075; mp[89000001] = 905700658; mp[90000000] = 448853213; mp[90000001] = 336075689; mp[91000000] = 916443128; mp[91000001] = 980668859; mp[92000000] = 719396272; mp[92000001] = 280105072; mp[93000000] = 62461078; mp[93000001] = 275798917; mp[94000000] = 829557374; mp[94000001] = 439708622; mp[95000000] = 360973550; mp[95000001] = 370926140; mp[96000000] = 28257290; mp[96000001] = 849268396; mp[97000000] = 54217657; mp[97000001] = 746403872; mp[98000000] = 360608813; mp[98000001] = 787231171; mp[99000000] = 40750050; mp[99000001] = 962510271; mp[100000000] = 322273426; mp[100000001] = 696682031; mp[101000000] = 994158933; mp[101000001] = 524288568; mp[102000000] = 169297167; mp[102000001] = 82418989; mp[103000000] = 816619563; mp[103000001] = 216836857; mp[104000000] = 578752871; mp[104000001] = 741420784; mp[105000000] = 360557868; mp[105000001] = 235547835; mp[106000000] = 348588664; mp[106000001] = 473935877; mp[107000000] = 773488558; mp[107000001] = 900145632; mp[108000000] = 383760456; mp[108000001] = 341637552; mp[109000000] = 253636234; mp[109000001] = 566111790; mp[110000000] = 398890147; mp[110000001] = 261744734; mp[111000000] = 995241802; mp[111000001] = 243938921; mp[112000000] = 479632402; mp[112000001] = 127600598; mp[113000000] = 110532161; mp[113000001] = 216101222; mp[114000000] = 700282646; mp[114000001] = 785457098; mp[115000000] = 282610478; mp[115000001] = 25109042; mp[116000000] = 140824426; mp[116000001] = 442474994; mp[117000000] = 295951236; mp[117000001] = 665567177; mp[118000000] = 857609436; mp[118000001] = 597224044; mp[119000000] = 760044280; mp[119000001] = 446927396; mp[120000000] = 194914852; mp[120000001] = 271186377; mp[121000000] = 443829327; mp[121000001] = 634905890; mp[122000000] = 876081218; mp[122000001] = 723907861; mp[123000000] = 524150684; mp[123000001] = 204856945; mp[124000000] = 964703318; mp[124000001] = 559340840; mp[125000000] = 503814959; mp[125000001] = 937976875; mp[126000000] = 3721180; mp[126000001] = 680439103; mp[127000000] = 438887824; mp[127000001] = 696716552; mp[128000000] = 780454157; mp[128000001] = 177167232; mp[129000000] = 618807385; mp[129000001] = 725024320; mp[130000000] = 884947442; mp[130000001] = 539645272; mp[131000000] = 765009239; mp[131000001] = 372495768; mp[132000000] = 49016763; mp[132000001] = 719725278; mp[133000000] = 277882991; mp[133000001] = 822173931; mp[134000000] = 686914924; mp[134000001] = 858588730; mp[135000000] = 394281833; mp[135000001] = 476685503; mp[136000000] = 9292295; mp[136000001] = 120446030; mp[137000000] = 180115281; mp[137000001] = 504384729; mp[138000000] = 827376728; mp[138000001] = 492130811; mp[139000000] = 884535605; mp[139000001] = 118882461; mp[140000000] = 154199209; mp[140000001] = 263083985; mp[141000000] = 244167252; mp[141000001] = 535174177; mp[142000000] = 56875341; mp[142000001] = 422341254; mp[143000000] = 100252189; mp[143000001] = 26899747; mp[144000000] = 949590677; mp[144000001] = 480403277; mp[145000000] = 930382776; mp[145000001] = 506044261; mp[146000000] = 186095009; mp[146000001] = 309905911; mp[147000000] = 915325731; mp[147000001] = 430455556; mp[148000000] = 487153268; mp[148000001] = 646462486; mp[149000000] = 999188962; mp[149000001] = 295034876; mp[150000000] = 881788023; mp[150000001] = 405910601; mp[151000000] = 26750235; mp[151000001] = 483475239; mp[152000000] = 843660084; mp[152000001] = 714005759; mp[153000000] = 825675146; mp[153000001] = 279377066; mp[154000000] = 480858823; mp[154000001] = 704493016; mp[155000000] = 814808681; mp[155000001] = 485741265; mp[156000000] = 562764753; mp[156000001] = 416225645; mp[157000000] = 388965635; mp[157000001] = 656492406; mp[158000000] = 868321452; mp[158000001] = 323957928; mp[159000000] = 793774212; mp[159000001] = 618303518; mp[160000000] = 389699639; mp[160000001] = 193236044; mp[161000000] = 696033877; mp[161000001] = 108603698; mp[162000000] = 824165623; mp[162000001] = 815561812; mp[163000000] = 729212269; mp[163000001] = 744181075; mp[164000000] = 903496758; mp[164000001] = 178282481; mp[165000000] = 13694466; mp[165000001] = 887877363; mp[166000000] = 125127133; mp[166000001] = 57729404; mp[167000000] = 802590026; mp[167000001] = 206362287; mp[168000000] = 78636716; mp[168000001] = 274159939; mp[169000000] = 991813302; mp[169000001] = 856498172; mp[170000000] = 733217502; mp[170000001] = 200688676; mp[171000000] = 340792204; mp[171000001] = 816863941; mp[172000000] = 163694105; mp[172000001] = 26606402; mp[173000000] = 729692726; mp[173000001] = 444034838; mp[174000000] = 66435775; mp[174000001] = 835517006; mp[175000000] = 124648772; mp[175000001] = 71954026; mp[176000000] = 579867155; mp[176000001] = 145470821; mp[177000000] = 90056478; mp[177000001] = 584476505; mp[178000000] = 540654765; mp[178000001] = 36998928; mp[179000000] = 368988366; mp[179000001] = 420645946; mp[180000000] = 601739182; mp[180000001] = 603547817; mp[181000000] = 416701437; mp[181000001] = 985740723; mp[182000000] = 445350912; mp[182000001] = 861973856; mp[183000000] = 616246755; mp[183000001] = 991834669; mp[184000000] = 591423736; mp[184000001] = 253669966; mp[185000000] = 392220359; mp[185000001] = 299294996; mp[186000000] = 536341336; mp[186000001] = 334024919; mp[187000000] = 964430099; mp[187000001] = 214991102; mp[188000000] = 531887312; mp[188000001] = 487923613; mp[189000000] = 559587397; mp[189000001] = 852253277; mp[190000000] = 372305477; mp[190000001] = 507139196; mp[191000000] = 718309972; mp[191000001] = 409929543; mp[192000000] = 926423310; mp[192000001] = 201310384; mp[193000000] = 42000939; mp[193000001] = 212257671; mp[194000000] = 639265371; mp[194000001] = 745143003; mp[195000000] = 28855165; mp[195000001] = 164467865; mp[196000000] = 677697221; mp[196000001] = 63896635; mp[197000000] = 103286437; mp[197000001] = 49854440; mp[198000000] = 484351515; mp[198000001] = 783040321; mp[199000000] = 607563402; mp[199000001] = 759227589; mp[200000000] = 213823357; mp[200000001] = 314470659; mp[201000000] = 872307731; mp[201000001] = 575970759; mp[202000000] = 372467702; mp[202000001] = 649798376; mp[203000000] = 126282642; mp[203000001] = 272835009; mp[204000000] = 345280228; mp[204000001] = 364220065; mp[205000000] = 984769112; mp[205000001] = 531625442; mp[206000000] = 717461814; mp[206000001] = 366881882; mp[207000000] = 487124435; mp[207000001] = 826281135; mp[208000000] = 757943584; mp[208000001] = 126377728; mp[209000000] = 562591933; mp[209000001] = 736519941; mp[210000000] = 713959988; mp[210000001] = 144438808; mp[211000000] = 970592690; mp[211000001] = 127027290; mp[212000000] = 854865267; mp[212000001] = 190245214; mp[213000000] = 918201995; mp[213000001] = 484162826; mp[214000000] = 777177924; mp[214000001] = 348965398; mp[215000000] = 466044211; mp[215000001] = 129647675; mp[216000000] = 718369887; mp[216000001] = 224194621; mp[217000000] = 595693165; mp[217000001] = 495835252; mp[218000000] = 48090102; mp[218000001] = 210704607; mp[219000000] = 581617266; mp[219000001] = 943998005; mp[220000000] = 498202615; mp[220000001] = 30970589; mp[221000000] = 215303046; mp[221000001] = 48229234; mp[222000000] = 391636760; mp[222000001] = 503033239; mp[223000000] = 679592087; mp[223000001] = 19748841; mp[224000000] = 66223098; mp[224000001] = 914385286; mp[225000000] = 332910243; mp[225000001] = 483576614; mp[226000000] = 554427583; mp[226000001] = 435323151; mp[227000000] = 437417932; mp[227000001] = 306360841; mp[228000000] = 759812013; mp[228000001] = 511152046; mp[229000000] = 129290794; mp[229000001] = 748037656; mp[230000000] = 196342945; mp[230000001] = 230230805; mp[231000000] = 383628392; mp[231000001] = 315301285; mp[232000000] = 474049070; mp[232000001] = 944193388; mp[233000000] = 499347791; mp[233000001] = 987911552; mp[234000000] = 729105951; mp[234000001] = 68830406; mp[235000000] = 715068952; mp[235000001] = 258780530; mp[236000000] = 708424167; mp[236000001] = 950107452; mp[237000000] = 417690245; mp[237000001] = 789742135; mp[238000000] = 981761551; mp[238000001] = 484146814; mp[239000000] = 100358731; mp[239000001] = 641458578; mp[240000000] = 324300550; mp[240000001] = 779475632; mp[241000000] = 448815874; mp[241000001] = 325663498; mp[242000000] = 976802967; mp[242000001] = 336098747; mp[243000000] = 355804045; mp[243000001] = 685581370; mp[244000000] = 868183507; mp[244000001] = 93326081; mp[245000000] = 299712064; mp[245000001] = 465705878; mp[246000000] = 548578229; mp[246000001] = 937926527; mp[247000000] = 311019993; mp[247000001] = 44266426; mp[248000000] = 739059075; mp[248000001] = 56052524; mp[249000000] = 589778521; mp[249000001] = 290794563; mp[250000000] = 154001751; mp[250000001] = 634498691; mp[251000000] = 348119666; mp[251000001] = 902473420; mp[252000000] = 539751867; mp[252000001] = 71629576; mp[253000000] = 574158273; mp[253000001] = 626323978; mp[254000000] = 788685196; mp[254000001] = 170402922; mp[255000000] = 791279153; mp[255000001] = 393845871; mp[256000000] = 624440017; mp[256000001] = 857443515; mp[257000000] = 961214770; mp[257000001] = 121989404; mp[258000000] = 231405777; mp[258000001] = 279486946; mp[259000000] = 245724014; mp[259000001] = 426226380; mp[260000000] = 974475946; mp[260000001] = 160929730; mp[261000000] = 275533551; mp[261000001] = 583133758; mp[262000000] = 845138374; mp[262000001] = 283154602; mp[263000000] = 157087033; mp[263000001] = 546889809; mp[264000000] = 736460202; mp[264000001] = 703481757; mp[265000000] = 470540891; mp[265000001] = 712687545; mp[266000000] = 871607895; mp[266000001] = 318674001; mp[267000000] = 745317906; mp[267000001] = 254318745; mp[268000000] = 387858087; mp[268000001] = 976236324; mp[269000000] = 242782878; mp[269000001] = 967622726; mp[270000000] = 540773759; mp[270000001] = 448711360; mp[271000000] = 747935865; mp[271000001] = 744101538; mp[272000000] = 859460625; mp[272000001] = 223047601; mp[273000000] = 228821922; mp[273000001] = 497543233; mp[274000000] = 723487306; mp[274000001] = 179838658; mp[275000000] = 468917247; mp[275000001] = 491251552; mp[276000000] = 724324069; mp[276000001] = 368929974; mp[277000000] = 476378557; mp[277000001] = 841680543; mp[278000000] = 770600635; mp[278000001] = 801011809; mp[279000000] = 250470252; mp[279000001] = 69301851; mp[280000000] = 467881322; mp[280000001] = 710833938; mp[281000000] = 300357120; mp[281000001] = 429554669; mp[282000000] = 676487052; mp[282000001] = 5101615; mp[283000000] = 462154550; mp[283000001] = 196626390; mp[284000000] = 311697536; mp[284000001] = 916042842; mp[285000000] = 428812399; mp[285000001] = 288331667; mp[286000000] = 450648083; mp[286000001] = 286450625; mp[287000000] = 778076329; mp[287000001] = 637920993; mp[288000000] = 786255939; mp[288000001] = 633163975; mp[289000000] = 765849472; mp[289000001] = 624535999; mp[290000000] = 257531902; mp[290000001] = 314742144; mp[291000000] = 721767280; mp[291000001] = 731527340; mp[292000000] = 176563389; mp[292000001] = 403667825; mp[293000000] = 175749454; mp[293000001] = 837287330; mp[294000000] = 732296574; mp[294000001] = 981230236; mp[295000000] = 298120095; mp[295000001] = 707502105; mp[296000000] = 155448833; mp[296000001] = 401358854; mp[297000000] = 898525679; mp[297000001] = 693490803; mp[298000000] = 85049317; mp[298000001] = 373636444; mp[299000000] = 968406065; mp[299000001] = 376532180; mp[300000000] = 598680559; mp[300000001] = 41451389; mp[301000000] = 395844987; mp[301000001] = 648799606; mp[302000000] = 900957536; mp[302000001] = 868333317; mp[303000000] = 579095485; mp[303000001] = 305833967; mp[304000000] = 429212998; mp[304000001] = 907847747; mp[305000000] = 509837298; mp[305000001] = 311334672; mp[306000000] = 853242300; mp[306000001] = 825597305; mp[307000000] = 922588922; mp[307000001] = 993945342; mp[308000000] = 68856856; mp[308000001] = 568401478; mp[309000000] = 283770130; mp[309000001] = 839975346; mp[310000000] = 367927849; mp[310000001] = 759524424; mp[311000000] = 522655659; mp[311000001] = 333834295; mp[312000000] = 690757326; mp[312000001] = 894143337; mp[313000000] = 912348796; mp[313000001] = 61392591; mp[314000000] = 30049334; mp[314000001] = 840000903; mp[315000000] = 131745858; mp[315000001] = 111246242; mp[316000000] = 137674199; mp[316000001] = 717138876; mp[317000000] = 142648551; mp[317000001] = 493111420; mp[318000000] = 600945940; mp[318000001] = 183240283; mp[319000000] = 449239819; mp[319000001] = 707087311; mp[320000000] = 971346692; mp[320000001] = 235530111; mp[321000000] = 670051193; mp[321000001] = 117446168; mp[322000000] = 737038504; mp[322000001] = 363753724; mp[323000000] = 865244796; mp[323000001] = 16926319; mp[324000000] = 723942192; mp[324000001] = 290041308; mp[325000000] = 610008278; mp[325000001] = 572239454; mp[326000000] = 752447580; mp[326000001] = 115362209; mp[327000000] = 905516484; mp[327000001] = 100789260; mp[328000000] = 656581760; mp[328000001] = 429070047; mp[329000000] = 91825933; mp[329000001] = 837350815; mp[330000000] = 94577421; mp[330000001] = 806103584; mp[331000000] = 283622038; mp[331000001] = 204469779; mp[332000000] = 849585022; mp[332000001] = 179149439; mp[333000000] = 102547070; mp[333000001] = 173509851; mp[334000000] = 323875198; mp[334000001] = 698654992; mp[335000000] = 420318614; mp[335000001] = 124671468; mp[336000000] = 779228990; mp[336000001] = 586482416; mp[337000000] = 786063302; mp[337000001] = 705739984; mp[338000000] = 988963335; mp[338000001] = 879076099; mp[339000000] = 164868451; mp[339000001] = 662635622; mp[340000000] = 617165552; mp[340000001] = 828311549; mp[341000000] = 905989955; mp[341000001] = 398391943; mp[342000000] = 6391586; mp[342000001] = 403090131; mp[343000000] = 421243975; mp[343000001] = 834837200; mp[344000000] = 739350754; mp[344000001] = 334994147; mp[345000000] = 362563274; mp[345000001] = 16972970; mp[346000000] = 347053973; mp[346000001] = 164489254; mp[347000000] = 576876354; mp[347000001] = 13643695; mp[348000000] = 394564599; mp[348000001] = 885405245; mp[349000000] = 99117090; mp[349000001] = 266974041; mp[350000000] = 128327758; mp[350000001] = 113924752; mp[351000000] = 435476476; mp[351000001] = 441510781; mp[352000000] = 728083087; mp[352000001] = 558086371; mp[353000000] = 600210704; mp[353000001] = 629090064; mp[354000000] = 507934245; mp[354000001] = 979273197; mp[355000000] = 259790921; mp[355000001] = 569210488; mp[356000000] = 404690060; mp[356000001] = 756202439; mp[357000000] = 506558658; mp[357000001] = 146668577; mp[358000000] = 328287279; mp[358000001] = 387599363; mp[359000000] = 237225611; mp[359000001] = 990077659; mp[360000000] = 503709458; mp[360000001] = 114361629; mp[361000000] = 465806023; mp[361000001] = 591714211; mp[362000000] = 631623755; mp[362000001] = 341089168; mp[363000000] = 594216496; mp[363000001] = 132312386; mp[364000000] = 370047171; mp[364000001] = 671166987; mp[365000000] = 737911496; mp[365000001] = 892547637; mp[366000000] = 151018717; mp[366000001] = 186108766; mp[367000000] = 113095146; mp[367000001] = 404553719; mp[368000000] = 128457419; mp[368000001] = 989551115; mp[369000000] = 880656919; mp[369000001] = 716920111; mp[370000000] = 253566817; mp[370000001] = 886828769; mp[371000000] = 184922743; mp[371000001] = 357678383; mp[372000000] = 223563582; mp[372000001] = 145404017; mp[373000000] = 252228570; mp[373000001] = 203659777; mp[374000000] = 266519182; mp[374000001] = 636771970; mp[375000000] = 876803028; mp[375000001] = 75195089; mp[376000000] = 194040840; mp[376000001] = 523325354; mp[377000000] = 997525075; mp[377000001] = 640056417; mp[378000000] = 847784903; mp[378000001] = 938546065; mp[379000000] = 464959842; mp[379000001] = 349421388; mp[380000000] = 820144401; mp[380000001] = 18560303; mp[381000000] = 163870432; mp[381000001] = 318827993; mp[382000000] = 885252811; mp[382000001] = 320086806; mp[383000000] = 688921891; mp[383000001] = 94922309; mp[384000000] = 193947871; mp[384000001] = 136615996; mp[385000000] = 21626547; mp[385000001] = 558343006; mp[386000000] = 958041818; mp[386000001] = 117412837; mp[387000000] = 727618041; mp[387000001] = 623500780; mp[388000000] = 842250; mp[388000001] = 998554705; mp[389000000] = 378454511; mp[389000001] = 126922882; mp[390000000] = 13965056; mp[390000001] = 815840458; mp[391000000] = 409131285; mp[391000001] = 724338967; mp[392000000] = 863668228; mp[392000001] = 869762626; mp[393000000] = 688461155; mp[393000001] = 709504530; mp[394000000] = 117468217; mp[394000001] = 291490877; mp[395000000] = 29814411; mp[395000001] = 292377566; mp[396000000] = 531114442; mp[396000001] = 90865215; mp[397000000] = 25589724; mp[397000001] = 382475883; mp[398000000] = 254857335; mp[398000001] = 874824808; mp[399000000] = 305168698; mp[399000001] = 954832534; mp[400000000] = 82358069; mp[400000001] = 451755479; mp[401000000] = 445751007; mp[401000001] = 1527935; mp[402000000] = 411378564; mp[402000001] = 981759296; mp[403000000] = 381536877; mp[403000001] = 736221356; mp[404000000] = 933633977; mp[404000001] = 1317101; mp[405000000] = 702145011; mp[405000001] = 166563914; mp[406000000] = 687788151; mp[406000001] = 39094234; mp[407000000] = 558820531; mp[407000001] = 83740845; mp[408000000] = 829116226; mp[408000001] = 669160299; mp[409000000] = 956393708; mp[409000001] = 790238539; mp[410000000] = 805941568; mp[410000001] = 372889280; mp[411000000] = 178263460; mp[411000001] = 725399492; mp[412000000] = 900513582; mp[412000001] = 87432423; mp[413000000] = 928732556; mp[413000001] = 871766754; mp[414000000] = 122675017; mp[414000001] = 805162824; mp[415000000] = 699849090; mp[415000001] = 16787492; mp[416000000] = 47406175; mp[416000001] = 709359398; mp[417000000] = 823318492; mp[417000001] = 584051828; mp[418000000] = 754665638; mp[418000001] = 230513992; mp[419000000] = 211464760; mp[419000001] = 31238621; mp[420000000] = 533047638; mp[420000001] = 925887595; mp[421000000] = 354855600; mp[421000001] = 909096157; mp[422000000] = 56228475; mp[422000001] = 340129562; mp[423000000] = 889527707; mp[423000001] = 316636180; mp[424000000] = 89342482; mp[424000001] = 192173997; mp[425000000] = 925349438; mp[425000001] = 322434874; mp[426000000] = 352847983; mp[426000001] = 58655302; mp[427000000] = 184575152; mp[427000001] = 536880028; mp[428000000] = 162590565; mp[428000001] = 495469237; mp[429000000] = 402474435; mp[429000001] = 808843717; mp[430000000] = 69430220; mp[430000001] = 460445261; mp[431000000] = 53717597; mp[431000001] = 198651608; mp[432000000] = 499227545; mp[432000001] = 429563458; mp[433000000] = 727117226; mp[433000001] = 381224926; mp[434000000] = 389321885; mp[434000001] = 296562005; mp[435000000] = 505427812; mp[435000001] = 186400132; mp[436000000] = 689377848; mp[436000001] = 313396667; mp[437000000] = 739141890; mp[437000001] = 408106861; mp[438000000] = 851692242; mp[438000001] = 236403841; mp[439000000] = 36961625; mp[439000001] = 298378553; mp[440000000] = 686678173; mp[440000001] = 691709414; mp[441000000] = 898151821; mp[441000001] = 186557163; mp[442000000] = 341673172; mp[442000001] = 308536384; mp[443000000] = 603840769; mp[443000001] = 398330555; mp[444000000] = 314510027; mp[444000001] = 325012869; mp[445000000] = 988116160; mp[445000001] = 110134336; mp[446000000] = 292613275; mp[446000001] = 29074634; mp[447000000] = 643463284; mp[447000001] = 578066681; mp[448000000] = 987869224; mp[448000001] = 241911353; mp[449000000] = 86904847; mp[449000001] = 116762914; mp[450000000] = 297170813; mp[450000001] = 211082757; mp[451000000] = 210607265; mp[451000001] = 60720132; mp[452000000] = 125056557; mp[452000001] = 493377615; mp[453000000] = 522472396; mp[453000001] = 253712437; mp[454000000] = 56762503; mp[454000001] = 238371270; mp[455000000] = 268825217; mp[455000001] = 147616905; mp[456000000] = 657107621; mp[456000001] = 735620109; mp[457000000] = 541102843; mp[457000001] = 61114856; mp[458000000] = 405700172; mp[458000001] = 881025432; mp[459000000] = 597167891; mp[459000001] = 647467470; mp[460000000] = 34546238; mp[460000001] = 403307354; mp[461000000] = 219235406; mp[461000001] = 677762758; mp[462000000] = 288417029; mp[462000001] = 753676366; mp[463000000] = 32306949; mp[463000001] = 314600129; mp[464000000] = 6461506; mp[464000001] = 769474539; mp[465000000] = 75810449; mp[465000001] = 614047442; mp[466000000] = 187271994; mp[466000001] = 780390757; mp[467000000] = 958412125; mp[467000001] = 200362904; mp[468000000] = 923423574; mp[468000001] = 530287963; mp[469000000] = 174329621; mp[469000001] = 851005483; mp[470000000] = 323435423; mp[470000001] = 69332886; mp[471000000] = 134419822; mp[471000001] = 853237676; mp[472000000] = 86333313; mp[472000001] = 537088051; mp[473000000] = 623634963; mp[473000001] = 57779610; mp[474000000] = 819270744; mp[474000001] = 756930433; mp[475000000] = 708774997; mp[475000001] = 927098149; mp[476000000] = 864549168; mp[476000001] = 951871360; mp[477000000] = 184708668; mp[477000001] = 203966429; mp[478000000] = 808590464; mp[478000001] = 895046790; mp[479000000] = 146071060; mp[479000001] = 396294800; mp[480000000] = 499126069; mp[480000001] = 942062491; mp[481000000] = 957779045; mp[481000001] = 377937018; mp[482000000] = 733872556; mp[482000001] = 249786565; mp[483000000] = 966196700; mp[483000001] = 799485678; mp[484000000] = 801414729; mp[484000001] = 922221646; mp[485000000] = 725378301; mp[485000001] = 247718982; mp[486000000] = 475620410; mp[486000001] = 117559783; mp[487000000] = 387306873; mp[487000001] = 217977750; mp[488000000] = 921714578; mp[488000001] = 837137600; mp[489000000] = 242623264; mp[489000001] = 508123838; mp[490000000] = 487532712; mp[490000001] = 695295522; mp[491000000] = 808421122; mp[491000001] = 931877745; mp[492000000] = 796370648; mp[492000001] = 869670155; mp[493000000] = 958262856; mp[493000001] = 659297760; mp[494000000] = 56469791; mp[494000001] = 615197258; mp[495000000] = 969427220; mp[495000001] = 510361922; mp[496000000] = 906919416; mp[496000001] = 94095219; mp[497000000] = 154436480; mp[497000001] = 177151969; mp[498000000] = 771008169; mp[498000001] = 245273706; mp[499000000] = 213577806; mp[499000001] = 661550537; mp[500000000] = 468899710; mp[500000001] = 827750738; mp[501000000] = 432769540; mp[501000001] = 455046773; mp[502000000] = 870216603; mp[502000001] = 518275478; mp[503000000] = 51442776; mp[503000001] = 198312763; mp[504000000] = 12237969; mp[504000001] = 345062416; mp[505000000] = 675843097; mp[505000001] = 271737762; mp[506000000] = 34760677; mp[506000001] = 473638362; mp[507000000] = 396204835; mp[507000001] = 335073884; mp[508000000] = 176554723; mp[508000001] = 832726136; mp[509000000] = 414179745; mp[509000001] = 143457321; mp[510000000] = 790590914; mp[510000001] = 108181365; mp[511000000] = 225772745; mp[511000001] = 113183640; mp[512000000] = 567888121; mp[512000001] = 484577108; mp[513000000] = 233151084; mp[513000001] = 487905548; mp[514000000] = 152099332; mp[514000001] = 252845939; mp[515000000] = 751227942; mp[515000001] = 173051225; mp[516000000] = 46458325; mp[516000001] = 578650859; mp[517000000] = 674788795; mp[517000001] = 247728159; mp[518000000] = 790702570; mp[518000001] = 183615066; mp[519000000] = 489845612; mp[519000001] = 338236514; mp[520000000] = 581347156; mp[520000001] = 585243522; mp[521000000] = 369818845; mp[521000001] = 266089525; mp[522000000] = 15615037; mp[522000001] = 272557693; mp[523000000] = 545967596; mp[523000001] = 255180238; mp[524000000] = 103309552; mp[524000001] = 972370123; mp[525000000] = 389860753; mp[525000001] = 282122494; mp[526000000] = 719815661; mp[526000001] = 755454415; mp[527000000] = 91664918; mp[527000001] = 539513040; mp[528000000] = 301486883; mp[528000001] = 411191371; mp[529000000] = 791845156; mp[529000001] = 383642560; mp[530000000] = 955359050; mp[530000001] = 910976998; mp[531000000] = 779856088; mp[531000001] = 609131027; mp[532000000] = 44321908; mp[532000001] = 935267129; mp[533000000] = 489350942; mp[533000001] = 749582591; mp[534000000] = 644787192; mp[534000001] = 762572685; mp[535000000] = 55206524; mp[535000001] = 188458093; mp[536000000] = 633954632; mp[536000001] = 7356864; mp[537000000] = 598404606; mp[537000001] = 771001708; mp[538000000] = 901413642; mp[538000001] = 902689889; mp[539000000] = 149686777; mp[539000001] = 387918572; mp[540000000] = 700529992; mp[540000001] = 732526640; mp[541000000] = 579052159; mp[541000001] = 405181646; mp[542000000] = 565835015; mp[542000001] = 549056982; mp[543000000] = 118847032; mp[543000001] = 43109465; mp[544000000] = 867926968; mp[544000001] = 154861091; mp[545000000] = 97589652; mp[545000001] = 65285131; mp[546000000] = 729449902; mp[546000001] = 433492393; mp[547000000] = 6064412; mp[547000001] = 346843780; mp[548000000] = 401641163; mp[548000001] = 184945670; mp[549000000] = 221211052; mp[549000001] = 919096989; mp[550000000] = 518280890; mp[550000001] = 22899473; mp[551000000] = 609694504; mp[551000001] = 962102820; mp[552000000] = 63376104; mp[552000001] = 226490840; mp[553000000] = 428801015; mp[553000001] = 63912294; mp[554000000] = 700687934; mp[554000001] = 419420142; mp[555000000] = 839096293; mp[555000001] = 194207212; mp[556000000] = 114480112; mp[556000001] = 940923524; mp[557000000] = 98459976; mp[557000001] = 346564533; mp[558000000] = 876598556; mp[558000001] = 700604618; mp[559000000] = 693812577; mp[559000001] = 521923980; mp[560000000] = 98592091; mp[560000001] = 672111100; mp[561000000] = 74920668; mp[561000001] = 528707209; mp[562000000] = 224533248; mp[562000001] = 717219459; mp[563000000] = 721549085; mp[563000001] = 732924160; mp[564000000] = 970958369; mp[564000001] = 253614749; mp[565000000] = 117610907; mp[565000001] = 107459772; mp[566000000] = 347169727; mp[566000001] = 453683278; mp[567000000] = 961003451; mp[567000001] = 863780779; mp[568000000] = 478317111; mp[568000001] = 624528291; mp[569000000] = 306883443; mp[569000001] = 151566696; mp[570000000] = 64544225; mp[570000001] = 57012768; mp[571000000] = 131097347; mp[571000001] = 744101258; mp[572000000] = 11349170; mp[572000001] = 205907094; mp[573000000] = 278833977; mp[573000001] = 981430907; mp[574000000] = 412976440; mp[574000001] = 313637114; mp[575000000] = 72910913; mp[575000001] = 754444494; mp[576000000] = 191951439; mp[576000001] = 282003242; mp[577000000] = 443412274; mp[577000001] = 750470113; mp[578000000] = 570830448; mp[578000001] = 205250468; mp[579000000] = 149888564; mp[579000001] = 98390217; mp[580000000] = 988209678; mp[580000001] = 216078407; mp[581000000] = 265614314; mp[581000001] = 619360908; mp[582000000] = 152910522; mp[582000001] = 333953060; mp[583000000] = 327272434; mp[583000001] = 13673637; mp[584000000] = 752186716; mp[584000001] = 821247442; mp[585000000] = 718262387; mp[585000001] = 171977928; mp[586000000] = 133171332; mp[586000001] = 138902531; mp[587000000] = 618790917; mp[587000001] = 355179054; mp[588000000] = 53007885; mp[588000001] = 214827432; mp[589000000] = 650106860; mp[589000001] = 509716293; mp[590000000] = 422603955; mp[590000001] = 127249630; mp[591000000] = 660805266; mp[591000001] = 133053895; mp[592000000] = 503088446; mp[592000001] = 450289939; mp[593000000] = 947525042; mp[593000001] = 920348619; mp[594000000] = 635064394; mp[594000001] = 30466657; mp[595000000] = 781322580; mp[595000001] = 627114055; mp[596000000] = 447596506; mp[596000001] = 156223893; mp[597000000] = 461800272; mp[597000001] = 915936951; mp[598000000] = 848471668; mp[598000001] = 760769289; mp[599000000] = 994245679; mp[599000001] = 546373572; mp[600000000] = 40661679; mp[600000001] = 269882629; mp[601000000] = 298018995; mp[601000001] = 39253089; mp[602000000] = 657681727; mp[602000001] = 540210947; mp[603000000] = 690493596; mp[603000001] = 163920143; mp[604000000] = 651688259; mp[604000001] = 332350316; mp[605000000] = 263114315; mp[605000001] = 723825201; mp[606000000] = 625223306; mp[606000001] = 409026058; mp[607000000] = 676841440; mp[607000001] = 880942182; mp[608000000] = 338387319; mp[608000001] = 850210902; mp[609000000] = 196183571; mp[609000001] = 98853012; mp[610000000] = 174468756; mp[610000001] = 589487175; mp[611000000] = 736236357; mp[611000001] = 714353479; mp[612000000] = 307800572; mp[612000001] = 53182928; mp[613000000] = 232333370; mp[613000001] = 45390884; mp[614000000] = 680437177; mp[614000001] = 433918208; mp[615000000] = 135268337; mp[615000001] = 807938154; mp[616000000] = 94262259; mp[616000001] = 231803401; mp[617000000] = 770243628; mp[617000001] = 919561422; mp[618000000] = 584612051; mp[618000001] = 573580335; mp[619000000] = 457097995; mp[619000001] = 381492395; mp[620000000] = 573631136; mp[620000001] = 404072021; mp[621000000] = 676573626; mp[621000001] = 481508092; mp[622000000] = 577189995; mp[622000001] = 954104776; mp[623000000] = 357633724; mp[623000001] = 849993067; mp[624000000] = 491460743; mp[624000001] = 976760235; mp[625000000] = 183599737; mp[625000001] = 5350891; mp[626000000] = 710075282; mp[626000001] = 130525413; mp[627000000] = 650365986; mp[627000001] = 17909688; mp[628000000] = 746259674; mp[628000001] = 737702169; mp[629000000] = 604986809; mp[629000001] = 802229908; mp[630000000] = 757555557; mp[630000001] = 326735570; mp[631000000] = 422575560; mp[631000001] = 916059327; mp[632000000] = 51985410; mp[632000001] = 942001963; mp[633000000] = 521611328; mp[633000001] = 834351551; mp[634000000] = 59618475; mp[634000001] = 945031690; mp[635000000] = 551225407; mp[635000001] = 546028489; mp[636000000] = 521615404; mp[636000001] = 143383638; mp[637000000] = 187849667; mp[637000001] = 229228007; mp[638000000] = 486159922; mp[638000001] = 550969725; mp[639000000] = 34760970; mp[639000001] = 709275156; mp[640000000] = 710709955; mp[640000001] = 726729378; mp[641000000] = 68171314; mp[641000001] = 36286629; mp[642000000] = 939418137; mp[642000001] = 671673056; mp[643000000] = 95539701; mp[643000001] = 408515511; mp[644000000] = 729618083; mp[644000001] = 892499788; mp[645000000] = 669334209; mp[645000001] = 452290274; mp[646000000] = 91219418; mp[646000001] = 706725216; mp[647000000] = 557643173; mp[647000001] = 963077262; mp[648000000] = 582111925; mp[648000001] = 341652249; mp[649000000] = 687457420; mp[649000001] = 144338378; mp[650000000] = 775098981; mp[650000001] = 898398642; mp[651000000] = 898616827; mp[651000001] = 180619969; mp[652000000] = 603014921; mp[652000001] = 342854838; mp[653000000] = 576780933; mp[653000001] = 189315303; mp[654000000] = 893649850; mp[654000001] = 702520863; mp[655000000] = 278152475; mp[655000001] = 127823384; mp[656000000] = 203936502; mp[656000001] = 579460093; mp[657000000] = 158338523; mp[657000001] = 41139659; mp[658000000] = 977791269; mp[658000001] = 476084711; mp[659000000] = 446417809; mp[659000001] = 518092470; mp[660000000] = 499158883; mp[660000001] = 973044862; mp[661000000] = 632455012; mp[661000001] = 638085691; mp[662000000] = 596308186; mp[662000001] = 965016073; mp[663000000] = 941696136; mp[663000001] = 739284397; mp[664000000] = 698436253; mp[664000001] = 444104569; mp[665000000] = 417623410; mp[665000001] = 123586447; mp[666000000] = 894434290; mp[666000001] = 864581658; mp[667000000] = 88077857; mp[667000001] = 295842346; mp[668000000] = 914667320; mp[668000001] = 397682957; mp[669000000] = 174322412; mp[669000001] = 985970567; mp[670000000] = 969149294; mp[670000001] = 403839132; mp[671000000] = 488979053; mp[671000001] = 755244458; mp[672000000] = 19360531; mp[672000001] = 760288598; mp[673000000] = 551406263; mp[673000001] = 952731378; mp[674000000] = 73316989; mp[674000001] = 313407438; mp[675000000] = 119956407; mp[675000001] = 278162388; mp[676000000] = 847556159; mp[676000001] = 320920438; mp[677000000] = 152414193; mp[677000001] = 91123336; mp[678000000] = 15968687; mp[678000001] = 726181303; mp[679000000] = 103264601; mp[679000001] = 691447959; mp[680000000] = 880429710; mp[680000001] = 489584316; mp[681000000] = 963452539; mp[681000001] = 429674313; mp[682000000] = 316525653; mp[682000001] = 151432194; mp[683000000] = 363527941; mp[683000001] = 328500866; mp[684000000] = 565064060; mp[684000001] = 899537361; mp[685000000] = 950456028; mp[685000001] = 573019402; mp[686000000] = 875759441; mp[686000001] = 196362629; mp[687000000] = 715221164; mp[687000001] = 943722611; mp[688000000] = 333793105; mp[688000001] = 966245526; mp[689000000] = 401872114; mp[689000001] = 9642918; mp[690000000] = 42564126; mp[690000001] = 776979403; mp[691000000] = 757147276; mp[691000001] = 810825927; mp[692000000] = 585211132; mp[692000001] = 94448424; mp[693000000] = 442500985; mp[693000001] = 900928724; mp[694000000] = 949069261; mp[694000001] = 472490819; mp[695000000] = 480460278; mp[695000001] = 353021040; mp[696000000] = 447188779; mp[696000001] = 452485062; mp[697000000] = 95227949; mp[697000001] = 83610788; mp[698000000] = 994464164; mp[698000001] = 607512289; mp[699000000] = 991942192; mp[699000001] = 346369075; mp[700000000] = 333697951; mp[700000001] = 398578002; mp[701000000] = 954980943; mp[701000001] = 311889483; mp[702000000] = 178264106; mp[702000001] = 714274298; mp[703000000] = 915367944; mp[703000001] = 42842316; mp[704000000] = 150152513; mp[704000001] = 562200936; mp[705000000] = 159044774; mp[705000001] = 44158818; mp[706000000] = 181427295; mp[706000001] = 554813611; mp[707000000] = 574673435; mp[707000001] = 275614622; mp[708000000] = 164721975; mp[708000001] = 648359875; mp[709000000] = 713579760; mp[709000001] = 12083430; mp[710000000] = 522067888; mp[710000001] = 407390501; mp[711000000] = 820113517; mp[711000001] = 325408567; mp[712000000] = 404395270; mp[712000001] = 628889259; mp[713000000] = 459838540; mp[713000001] = 184784400; mp[714000000] = 175975086; mp[714000001] = 700451615; mp[715000000] = 139109834; mp[715000001] = 752865123; mp[716000000] = 531733674; mp[716000001] = 450684517; mp[717000000] = 414553797; mp[717000001] = 782908306; mp[718000000] = 17880902; mp[718000001] = 564011492; mp[719000000] = 333986091; mp[719000001] = 82034104; mp[720000000] = 579797877; mp[720000001] = 97616593; mp[721000000] = 473169256; mp[721000001] = 661084038; mp[722000000] = 788793995; mp[722000001] = 192229167; mp[723000000] = 820866545; mp[723000001] = 701460988; mp[724000000] = 948934214; mp[724000001] = 75735644; mp[725000000] = 702467776; mp[725000001] = 737443837; mp[726000000] = 314706865; mp[726000001] = 705366590; mp[727000000] = 200780118; mp[727000001] = 965010109; mp[728000000] = 211722873; mp[728000001] = 676783122; mp[729000000] = 818674597; mp[729000001] = 853978157; mp[730000000] = 528967798; mp[730000001] = 365942367; mp[731000000] = 962265651; mp[731000001] = 919352348; mp[732000000] = 515626105; mp[732000001] = 733557962; mp[733000000] = 517981574; mp[733000001] = 602218136; mp[734000000] = 768844703; mp[734000001] = 820520646; mp[735000000] = 208784939; mp[735000001] = 299586435; mp[736000000] = 664133726; mp[736000001] = 578516792; mp[737000000] = 950847823; mp[737000001] = 596423935; mp[738000000] = 177984668; mp[738000001] = 242515879; mp[739000000] = 618427638; mp[739000001] = 901301490; mp[740000000] = 717694718; mp[740000001] = 320036101; mp[741000000] = 803357822; mp[741000001] = 738340827; mp[742000000] = 751009820; mp[742000001] = 290264838; mp[743000000] = 376612251; mp[743000001] = 910851950; mp[744000000] = 691294576; mp[744000001] = 635032448; mp[745000000] = 756271819; mp[745000001] = 967314311; mp[746000000] = 211958024; mp[746000001] = 9113228; mp[747000000] = 543942422; mp[747000001] = 933667519; mp[748000000] = 197601451; mp[748000001] = 510960262; mp[749000000] = 947893174; mp[749000001] = 304089292; mp[750000000] = 309384913; mp[750000001] = 435114131; mp[751000000] = 234460299; mp[751000001] = 550902517; mp[752000000] = 452161730; mp[752000001] = 31982396; mp[753000000] = 934679817; mp[753000001] = 208982530; mp[754000000] = 650662942; mp[754000001] = 484463956; mp[755000000] = 815852027; mp[755000001] = 889074094; mp[756000000] = 812802047; mp[756000001] = 43453638; mp[757000000] = 356180431; mp[757000001] = 735780342; mp[758000000] = 780228545; mp[758000001] = 750335913; mp[759000000] = 435897276; mp[759000001] = 603975065; mp[760000000] = 31308092; mp[760000001] = 784749048; mp[761000000] = 440411884; mp[761000001] = 818337796; mp[762000000] = 218696216; mp[762000001] = 644170610; mp[763000000] = 960164158; mp[763000001] = 385927421; mp[764000000] = 154837346; mp[764000001] = 670767228; mp[765000000] = 38316616; mp[765000001] = 73131138; mp[766000000] = 962683091; mp[766000001] = 506776389; mp[767000000] = 10606516; mp[767000001] = 725660136; mp[768000000] = 552913767; mp[768000001] = 636449376; mp[769000000] = 606494944; mp[769000001] = 277732680; mp[770000000] = 316850320; mp[770000001] = 9027104; mp[771000000] = 364888293; mp[771000001] = 298586188; mp[772000000] = 94513584; mp[772000001] = 431762181; mp[773000000] = 294155313; mp[773000001] = 651480927; mp[774000000] = 501476310; mp[774000001] = 724477682; mp[775000000] = 567610607; mp[775000001] = 913323087; mp[776000000] = 822846632; mp[776000001] = 785143757; mp[777000000] = 345872164; mp[777000001] = 892673480; mp[778000000] = 516729942; mp[778000001] = 578618697; mp[779000000] = 86574506; mp[779000001] = 788483732; mp[780000000] = 220854491; mp[780000001] = 994988983; mp[781000000] = 306148897; mp[781000001] = 189432887; mp[782000000] = 929299169; mp[782000001] = 315546; mp[783000000] = 423969930; mp[783000001] = 290190758; mp[784000000] = 125383915; mp[784000001] = 797276998; mp[785000000] = 782132070; mp[785000001] = 434316372; mp[786000000] = 667142092; mp[786000001] = 308526324; mp[787000000] = 184842982; mp[787000001] = 542999; mp[788000000] = 481533802; mp[788000001] = 801393370; mp[789000000] = 770543419; mp[789000001] = 105832140; mp[790000000] = 878646494; mp[790000001] = 279731411; mp[791000000] = 831895011; mp[791000001] = 926692367; mp[792000000] = 575605965; mp[792000001] = 664446517; mp[793000000] = 258561151; mp[793000001] = 566288213; mp[794000000] = 39657326; mp[794000001] = 663241913; mp[795000000] = 430961569; mp[795000001] = 387660453; mp[796000000] = 849881078; mp[796000001] = 202343739; mp[797000000] = 746427504; mp[797000001] = 270108484; mp[798000000] = 480064563; mp[798000001] = 72423929; mp[799000000] = 889303958; mp[799000001] = 357426951; mp[800000000] = 963974981; mp[800000001] = 365715120; mp[801000000] = 898310091; mp[801000001] = 752485444; mp[802000000] = 746327924; mp[802000001] = 604442986; mp[803000000] = 259305179; mp[803000001] = 538750779; mp[804000000] = 267660342; mp[804000001] = 729267950; mp[805000000] = 677796098; mp[805000001] = 748415112; mp[806000000] = 560277115; mp[806000001] = 89193650; mp[807000000] = 821037552; mp[807000001] = 646996451; mp[808000000] = 72328802; mp[808000001] = 679237104; mp[809000000] = 987119561; mp[809000001] = 246061520; mp[810000000] = 377654637; mp[810000001] = 206352858; mp[811000000] = 943684790; mp[811000001] = 276386269; mp[812000000] = 632757568; mp[812000001] = 252163573; mp[813000000] = 205829180; mp[813000001] = 374455325; mp[814000000] = 3053655; mp[814000001] = 155653929; mp[815000000] = 972289649; mp[815000001] = 360377235; mp[816000000] = 395572519; mp[816000001] = 640062307; mp[817000000] = 686813938; mp[817000001] = 104925049; mp[818000000] = 609494839; mp[818000001] = 421527413; mp[819000000] = 670784224; mp[819000001] = 281178291; mp[820000000] = 705101053; mp[820000001] = 117821032; mp[821000000] = 125163116; mp[821000001] = 641850696; mp[822000000] = 202791269; mp[822000001] = 153930314; mp[823000000] = 973029224; mp[823000001] = 719407901; mp[824000000] = 28732033; mp[824000001] = 55005667; mp[825000000] = 671770693; mp[825000001] = 517294966; mp[826000000] = 630644805; mp[826000001] = 914256569; mp[827000000] = 159448906; mp[827000001] = 498399197; mp[828000000] = 192678133; mp[828000001] = 199915681; mp[829000000] = 109528400; mp[829000001] = 73935098; mp[830000000] = 542246848; mp[830000001] = 231792680; mp[831000000] = 655276546; mp[831000001] = 569532903; mp[832000000] = 350104791; mp[832000001] = 423094502; mp[833000000] = 339661876; mp[833000001] = 67093488; mp[834000000] = 811164546; mp[834000001] = 439585956; mp[835000000] = 523433471; mp[835000001] = 748964855; mp[836000000] = 913806489; mp[836000001] = 370210948; mp[837000000] = 681290582; mp[837000001] = 823609090; mp[838000000] = 320368010; mp[838000001] = 821089279; mp[839000000] = 184855330; mp[839000001] = 969199989; mp[840000000] = 466289530; mp[840000001] = 924507115; mp[841000000] = 539681423; mp[841000001] = 105576904; mp[842000000] = 790812019; mp[842000001] = 127766006; mp[843000000] = 439374936; mp[843000001] = 894623459; mp[844000000] = 461375205; mp[844000001] = 755570514; mp[845000000] = 209088494; mp[845000001] = 402330061; mp[846000000] = 867942331; mp[846000001] = 753987881; mp[847000000] = 476008696; mp[847000001] = 165753154; mp[848000000] = 18780215; mp[848000001] = 227300860; mp[849000000] = 520734953; mp[849000001] = 523007148; mp[850000000] = 750036412; mp[850000001] = 487319789; mp[851000000] = 738072355; mp[851000001] = 446375364; mp[852000000] = 952000246; mp[852000001] = 866270817; mp[853000000] = 218649908; mp[853000001] = 437091317; mp[854000000] = 160577387; mp[854000001] = 698645777; mp[855000000] = 619720649; mp[855000001] = 805692591; mp[856000000] = 562085462; mp[856000001] = 666069397; mp[857000000] = 705486526; mp[857000001] = 255272882; mp[858000000] = 22383103; mp[858000001] = 261950188; mp[859000000] = 435748056; mp[859000001] = 919595016; mp[860000000] = 819636314; mp[860000001] = 925425738; mp[861000000] = 443829864; mp[861000001] = 672867293; mp[862000000] = 351469219; mp[862000001] = 8703963; mp[863000000] = 609164310; mp[863000001] = 459202737; mp[864000000] = 111175592; mp[864000001] = 926785621; mp[865000000] = 458416215; mp[865000001] = 657706053; mp[866000000] = 63207979; mp[866000001] = 494041215; mp[867000000] = 361128966; mp[867000001] = 691437288; mp[868000000] = 817329481; mp[868000001] = 359235585; mp[869000000] = 102726115; mp[869000001] = 412843163; mp[870000000] = 688721174; mp[870000001] = 874409254; mp[871000000] = 890414414; mp[871000001] = 55557763; mp[872000000] = 99411932; mp[872000001] = 196601503; mp[873000000] = 154717014; mp[873000001] = 431241349; mp[874000000] = 44860063; mp[874000001] = 832406204; mp[875000000] = 594743835; mp[875000001] = 576937870; mp[876000000] = 900253101; mp[876000001] = 855901123; mp[877000000] = 909158470; mp[877000001] = 517834658; mp[878000000] = 817994577; mp[878000001] = 396599938; mp[879000000] = 933285383; mp[879000001] = 847780460; mp[880000000] = 464087273; mp[880000001] = 845309693; mp[881000000] = 753073278; mp[881000001] = 26870399; mp[882000000] = 999122550; mp[882000001] = 930539968; mp[883000000] = 47465597; mp[883000001] = 905080749; mp[884000000] = 951314008; mp[884000001] = 136582961; mp[885000000] = 645783065; mp[885000001] = 170157001; mp[886000000] = 316910697; mp[886000001] = 893430571; mp[887000000] = 132946886; mp[887000001] = 189479676; mp[888000000] = 383979285; mp[888000001] = 77164063; mp[889000000] = 877774703; mp[889000001] = 382382760; mp[890000000] = 517164631; mp[890000001] = 885229004; mp[891000000] = 915986682; mp[891000001] = 864977785; mp[892000000] = 331585939; mp[892000001] = 849163353; mp[893000000] = 797408571; mp[893000001] = 715807627; mp[894000000] = 624813671; mp[894000001] = 588729744; mp[895000000] = 280636995; mp[895000001] = 47446231; mp[896000000] = 170701415; mp[896000001] = 940062152; mp[897000000] = 241387050; mp[897000001] = 575717775; mp[898000000] = 696417434; mp[898000001] = 50737469; mp[899000000] = 877840727; mp[899000001] = 926589070; mp[900000000] = 256789690; mp[900000001] = 639014656; mp[901000000] = 280434105; mp[901000001] = 116736215; mp[902000000] = 927498321; mp[902000001] = 613273960; mp[903000000] = 737288545; mp[903000001] = 211887680; mp[904000000] = 520988669; mp[904000001] = 172390; mp[905000000] = 56826112; mp[905000001] = 56832694; mp[906000000] = 685369539; mp[906000001] = 672755952; mp[907000000] = 131583290; mp[907000001] = 326160988; mp[908000000] = 719116784; mp[908000001] = 20410531; mp[909000000] = 880238527; mp[909000001] = 322280814; mp[910000000] = 482685016; mp[910000001] = 967981488; mp[911000000] = 605351713; mp[911000001] = 288023863; mp[912000000] = 993736121; mp[912000001] = 1724761; mp[913000000] = 206881884; mp[913000001] = 976699777; mp[914000000] = 811177899; mp[914000001] = 307261733; mp[915000000] = 141317021; mp[915000001] = 451181509; mp[916000000] = 3335944; mp[916000001] = 685945875; mp[917000000] = 585698084; mp[917000001] = 854102110; mp[918000000] = 682073860; mp[918000001] = 779067266; mp[919000000] = 531426532; mp[919000001] = 20759671; mp[920000000] = 276682441; mp[920000001] = 214847532; mp[921000000] = 663644092; mp[921000001] = 117130656; mp[922000000] = 689352730; mp[922000001] = 300270238; mp[923000000] = 727852213; mp[923000001] = 624199096; mp[924000000] = 746814819; mp[924000001] = 672416602; mp[925000000] = 184143102; mp[925000001] = 341816525; mp[926000000] = 428872926; mp[926000001] = 124918636; mp[927000000] = 481695945; mp[927000001] = 370970978; mp[928000000] = 218798350; mp[928000001] = 597484280; mp[929000000] = 773608829; mp[929000001] = 883830649; mp[930000000] = 473333947; mp[930000001] = 101929970; mp[931000000] = 116103680; mp[931000001] = 439456004; mp[932000000] = 655473387; mp[932000001] = 63165035; mp[933000000] = 968076915; mp[933000001] = 340566622; mp[934000000] = 86359458; mp[934000001] = 293741326; mp[935000000] = 334781593; mp[935000001] = 598636083; mp[936000000] = 717843074; mp[936000001] = 278535282; mp[937000000] = 37035206; mp[937000001] = 816121296; mp[938000000] = 134224352; mp[938000001] = 428907264; mp[939000000] = 615288312; mp[939000001] = 538998264; mp[940000000] = 340221393; mp[940000001] = 521564643; mp[941000000] = 901599799; mp[941000001] = 821761963; mp[942000000] = 264410783; mp[942000001] = 106886090; mp[943000000] = 458906778; mp[943000001] = 83663154; mp[944000000] = 806163165; mp[944000001] = 239037003; mp[945000000] = 144415001; mp[945000001] = 134109775; mp[946000000] = 56614453; mp[946000001] = 219713548; mp[947000000] = 868868442; mp[947000001] = 683139578; mp[948000000] = 454860259; mp[948000001] = 968407604; mp[949000000] = 357904502; mp[949000001] = 378344911; mp[950000000] = 762927538; mp[950000001] = 789459445; mp[951000000] = 930045611; mp[951000001] = 799732020; mp[952000000] = 768284771; mp[952000001] = 640435091; mp[953000000] = 349135872; mp[953000001] = 36050483; mp[954000000] = 375939507; mp[954000001] = 543415497; mp[955000000] = 726718378; mp[955000001] = 858606055; mp[956000000] = 896128453; mp[956000001] = 967236887; mp[957000000] = 285627228; mp[957000001] = 568210442; mp[958000000] = 668118735; mp[958000001] = 317714526; mp[959000000] = 198917702; mp[959000001] = 81583176; mp[960000000] = 624766601; mp[960000001] = 386335069; mp[961000000] = 425203890; mp[961000001] = 854857344; mp[962000000] = 855319974; mp[962000001] = 83595303; mp[963000000] = 767663944; mp[963000001] = 664841332; mp[964000000] = 540515728; mp[964000001] = 685115621; mp[965000000] = 317375305; mp[965000001] = 498505135; mp[966000000] = 348158328; mp[966000001] = 841911733; mp[967000000] = 809965487; mp[967000001] = 256309139; mp[968000000] = 392140412; mp[968000001] = 550996999; mp[969000000] = 661597068; mp[969000001] = 65984182; mp[970000000] = 984537252; mp[970000001] = 739529355; mp[971000000] = 670848732; mp[971000001] = 883089933; mp[972000000] = 400577109; mp[972000001] = 623050479; mp[973000000] = 640781611; mp[973000001] = 779418089; mp[974000000] = 437555867; mp[974000001] = 912299989; mp[975000000] = 116644591; mp[975000001] = 545545265; mp[976000000] = 178175499; mp[976000001] = 984880503; mp[977000000] = 738119236; mp[977000001] = 262121812; mp[978000000] = 6174353; mp[978000001] = 197904733; mp[979000000] = 123815837; mp[979000001] = 698305915; mp[980000000] = 977632075; mp[980000001] = 771076085; mp[981000000] = 118428592; mp[981000001] = 57179455; mp[982000000] = 215737742; mp[982000001] = 376756514; mp[983000000] = 626057315; mp[983000001] = 963156962; mp[984000000] = 535141995; mp[984000001] = 929083961; mp[985000000] = 511506338; mp[985000001] = 914670164; mp[986000000] = 204569608; mp[986000001] = 280630183; mp[987000000] = 676562680; mp[987000001] = 162191152; mp[988000000] = 681205105; mp[988000001] = 709990631; mp[989000000] = 252631325; mp[989000001] = 928664678; mp[990000000] = 34192646; mp[990000001] = 337237612; mp[991000000] = 396906487; mp[991000001] = 260566204; mp[992000000] = 914120126; mp[992000001] = 558470012; mp[993000000] = 14839562; mp[993000001] = 977689773; mp[994000000] = 611781105; mp[994000001] = 725008206; mp[995000000] = 176769488; mp[995000001] = 505570014; mp[996000000] = 320106189; mp[996000001] = 332325854; mp[997000000] = 532057908; mp[997000001] = 94825790; mp[998000000] = 152225254; mp[998000001] = 580779639; mp[999000000] = 960210904; mp[999000001] = 341456094; mp[1000000000] = 402182971; mp[1000000001] = 586902194; int n; cin >> n; if (mp.count(n)){ cout << mp[n] << '\n'; return 0; } const int mod = 1e9 + 7; int t = n / 1000000 * 1000000; int f1 = mp[t], f2 = mp[t + 1]; for(int i = t + 2; ; i++){ int t = 1LL * (i - 1) * (f1 + f2) % mod; f1 = f2, f2 = t; if (i == n){ cout << t << '\n'; return 0; } } }
