lista = [764019106, 162641905, 823902025, 667852204, 295302864, 483862792, 777528709, 988393385, 487111875, 428192921, 856374601, 746561301, 406899334, 453397375, 988658970, 613738503, 782994311, 511777521, 595763303, 997021914, 724156404, 796964868, 821406581, 659271860, 480206403, 128650123, 883598091, 195645214, 347419386, 800243837, 989992762, 495721881, 758546512, 274671657, 549236855, 564196163, 684204581, 924971575, 791864288, 129319057, 243695831, 585873609, 288811723, 603706748, 383101055, 380628058, 700706062, 469363210, 304182078, 751322042, 968899159, 673113185, 439373182, 845630021, 234208745, 217511291, 858198833, 786966180, 435068915, 958874149, 814673747, 890447224, 667474400, 217966128, 170778667, 842144360, 393414038, 404566050, 491610074, 890178775, 552391883, 705856732, 790578185, 582512309, 670673029, 842852298, 561754805, 141314462, 667854202, 441548793, 926642449, 364058685, 264352190, 405274466, 171098555, 531081974, 632247856, 893058162, 150486286, 661978427, 849547946, 236119839, 871853738, 239099109, 258120664, 629783134, 830824919, 409371006, 850131692, 757062401, 266113564, 585309039, 557491175, 468058031, 334698885, 985597902, 987815439, 425240308, 215225966, 594404467, 896675582, 312486855, 167874799, 605844411, 927729549, 461666498, 181571054, 912252684, 220023038, 465063160, 882184215, 642512939, 188143376, 404865442, 959460055, 461237982, 675939102, 269042970, 165548552, 138192521, 201615368, 625590754, 831071442, 430380291, 320202594, 150247396, 689010843, 264710582, 779112437, 610191236, 908477249, 850406257, 661837948, 121876463, 589055219, 931345773, 387796468, 302583918, 482239399, 883744368, 897945746, 323667069, 452261637, 431237255, 218360648, 464986338, 611007663, 643804379, 422740741, 392062901, 852491821, 368884840, 227831622, 694130721, 977972579, 232684681, 946359856, 327337496, 725227163, 923600423, 713383294, 186039353, 967084857, 622364780, 597492183, 558320309, 950579909, 498842075, 389200506, 920285526, 744775557, 487129849, 787053807, 588167277, 356376614, 414291774, 686312908, 626780689, 935278709, 229352347, 749028463, 744014110, 783563387, 114546550, 298105147, 976973434, 692868180, 152748793, 569000862, 552578478, 128844332, 135576226, 339642783, 636576517, 223778001, 509159349, 258990030, 631233103, 974201596, 367288585, 550211192, 463649265, 254140574, 133782845, 141866321, 867616948, 336530159, 320245570, 289022711, 836270692, 253498501, 440859275, 610804815, 496865052, 570057156, 644915652, 722811524, 385679400, 863898726, 453644301, 858079706, 558864140, 350871007, 253943790, 815757346, 743101784, 392976947, 410150343, 176929604, 872613449, 705070359, 246776606, 475049886, 808195988, 410760753, 824669306, 892508095, 755305287, 703721165, 773041294, 825807580, 680629938, 638054575, 585991128, 300740717, 375319234, 230551127, 631959484, 127673789, 493360628, 471288261, 358335848, 494040361, 835188438, 957865824, 257615971, 398642131, 310279122, 822527133, 915524889, 415792000, 910989036, 636518340, 465572593, 108381244, 314841257, 596467692, 772296968, 683674887, 199236311, 251387832, 207831744, 522667931, 480904522, 265223411, 604744598, 410923121, 940827318, 853383839, 907986620, 801849642, 938317274, 907792128, 165252510, 103346327, 270527323, 953367451, 319800204, 167798377, 583394537, 592962213, 826823131, 599136282, 544257163, 745045640, 830551991, 222721487, 729209366, 790047793, 559853171, 862939107, 885126027, 930095872, 555330536, 844574990, 183552328, 421811736, 526027911, 494773872, 631303880, 265196504, 692260067, 973411828, 892475933, 558807005, 489736992, 194045241, 391314964, 752239882, 521589270, 637676273, 310767847, 572193886, 280619382, 330528919, 525948106, 548351956, 188061636, 232598938, 444289655, 408425689, 824278662, 388685244, 511173167, 275754115, 293485277, 184735901, 622127015, 147842335, 322074864, 883431972, 151542943, 580117116, 411718312, 352584163, 330755777, 725979191, 491345646, 513838916, 306756524, 103948806, 491061287, 929442936, 126184783, 973256713, 601333433, 847950700, 108332333, 262236979, 928527248, 807302049, 690340883, 835895473, 725891159, 933277207, 441523124, 256076096, 420222539, 303131384, 263107870, 668337692, 110747476, 655155728, 827836297, 625730080, 327367078, 251340084, 645613322, 842719733, 537695439, 451153647, 376342735, 295450258, 401022512, 408169741, 152626871, 912198037, 220469144, 632640642, 118173151, 700838275, 586893516, 105535453, 345632386, 302029547, 597348232, 818157813, 528900357, 929563045, 327030982, 833726636, 257879750, 789978765, 425334166, 225408161, 948710490, 820663141, 384724646, 243381871, 866847401, 528572655, 519031532, 467207426, 348072333, 908241150, 422634747, 995049401, 611980755, 772596227, 237365805, 108023284, 957749508, 100255086, 296450361, 310011261, 744312743, 598287310, 551941965, 360693486, 132998184, 477851078, 926641211, 533898209, 416011372, 162134462, 819856047, 452380112, 280628296, 468146208, 304862661, 637264238, 811353229, 947378829, 369157989, 999828623, 796314289, 212131276, 376892172, 627356920, 373847123, 488557748, 349778179, 252634820, 260040298, 209946779, 928206321, 705662527, 248122421, 372974715, 935260375, 406210590, 158451609, 259721377, 686926412, 547784768, 413722490, 568453880, 968017071, 436810256, 248506557, 587159476, 879592967, 751281957, 638373082, 735663784, 257020332, 644866949, 730634695, 562407338, 191321590, 324326454, 153404054, 331452460, 677874721, 517198109, 951331934, 451434719, 334748397, 872853467, 393585985, 626349482, 742922577, 768300028, 735988298, 838848979, 955869555, 264349008, 173970982, 470992998, 181184975, 585412352, 117357317, 208413581, 564556441, 536485539, 930617807, 569311975, 338068114, 605045449, 925461229, 194440972, 155905507, 188766871, 120485098, 645256724, 745682244, 129935335, 250592334, 441228255, 233729675, 650680377, 483420989, 261239511, 483707705, 229821149, 574779408, 275308918, 288462892, 419810348, 537090346, 495221174, 963024205, 269940869, 748631001, 157984758, 462844546, 895014113, 994002648, 426177138, 582785875, 618551152, 657449555, 103475058, 379260964, 205171009, 388005365, 539776248, 861073362, 155422029, 424714978, 268731883, 717091782, 381380365, 721982535, 766708411, 696605821, 612892914, 649857040, 673862845, 903589047, 430867475, 346718362, 162423527, 837285664, 526542106, 473500121, 162328371, 173189800, 730293408, 812329729, 365559365, 498123623, 302704454, 102600313, 213062772, 551370796, 404767477, 454491147, 737101913, 389789799, 495156600, 811469388, 298042118, 474356956, 650809345, 799791682, 438590209, 832565239, 996635974, 884124685, 756273684, 696465626, 864632367, 297935578, 986827757, 473500096, 895511352, 580024686, 457515515, 461491140, 668334824, 997115057, 522663791, 669061202, 938603843, 382278312, 839276917, 360631161, 345008290, 399887270, 316893070, 811581500, 386758147, 503810040, 582324832, 480490165, 440016855, 126812439, 771300312, 776782860, 358957668, 927070541, 457700639, 202924658, 839970914, 941644615, 888839184, 852088598, 883219325, 860262176, 770100771, 178626329, 518165383, 438300165, 504344507, 774741580, 820226308, 571440047, 431551191, 501911792, 439993097, 874724402, 621809118, 863336666, 926484749, 690263458, 498831685, 550982220, 982975996, 423092699, 814604041, 379249964, 157492367, 428894317, 972226937, 529646883, 972001382, 367099678, 206818225, 587402595, 578081954, 780344846, 343913774, 286797679, 933744982, 222086514, 150973316, 429896117, 607574792, 744571360, 677937316, 817560993, 985949194, 941334059, 894475370, 610098221, 506627152, 873682793, 149377667, 676912077, 131456068, 513013415, 929125782, 546491863, 323416894, 782974688, 836801122, 120762667, 869924840, 374177114, 243422320, 308994720, 130426754, 939052161, 702980287, 253609827, 624444126, 155258925, 368832433, 855341474, 912410513, 297550471, 768282131, 147348039, 803801301, 898560688, 935419858, 771617509, 250492960, 999711199, 801288525, 803504370, 967563166, 354387616, 180505601, 689422501, 632792831, 443315654, 627833080, 663035743, 334188844, 327467676, 859558679, 709172123, 365008067, 866111746, 285157125, 624611753, 841790683, 503226409, 491656570, 408439729, 960497839, 180105399, 295243640, 195324755, 609478868, 438820480, 248850371, 924772232, 655729536, 404103456, 185158323, 493137241, 438242785, 430162451, 956395769, 467310029, 845914495, 139082326, 451948117, 944636995, 300773699, 172137238, 399826120, 282994008, 393494224, 203978604, 874052307, 903902281, 482638649, 745284496, 703225557, 317170035, 663778221, 758808534, 424132049, 138627680, 601654649, 825822444, 608041852, 867057696, 797754260, 694466442, 901018195, 690569273, 139437294, 981368581, 176449033, 346503576, 174809639, 412192354, 497176951, 973571755, 458922177, 222852724, 853865363, 334240715, 236218780, 969985414, 258833675, 631284937, 707851968, 788812977, 715938934, 806169007, 446629187, 322935276, 938125614, 251265527, 165312040, 730155735, 798912307, 673796186, 904131505, 366351120, 232909181, 293603760, 263749458, 735393722, 135003748, 578043630, 390522635, 804936028, 144161229, 979598411, 243404069, 655204518, 606501587, 886664108, 621270820, 867492479, 592379672, 159730206, 585994642, 186281386, 961728536, 964536312, 621363442, 605796559, 294408462, 297520663, 468826877, 214658564, 629473637, 577924715, 913788062, 271024957, 943716698, 121363818, 977112648, 632245481, 611676926, 850724901, 824643259, 701089745, 635566825, 133038587, 637213588, 599133309, 641250078, 684619637, 728035375, 857469389, 540099473, 584411289, 255320282, 759758660, 790261275, 939675894, 675625719, 803502624, 689780401, 568648672, 106777945, 801293331, 203000839, 699099183, 418541521, 701168415, 600663954, 449271951, 480703763, 484128089, 613411968, 985527389, 814273189, 675804526, 353888106, 925175670, 606048242, 971401216, 582288430, 236680617, 383392552, 280252605, 963600491, 858071983, 219081144, 739413979, 496423587, 707198457, 810546996, 254620310, 376981584, 580399813, 196407808, 602126011, 628788920, 148937119, 553861547, 689424795, 206647611, 906331379, 539542160, 209996739, 237880086, 620069602, 126735476, 335883460, 800777738, 907624957, 716508363, 454334663, 635413878, 150902263, 925779908, 793072007, 722389243, 879661628, 559374940, 317842288, 619323340, 583854864, 584205738, 853194693, 282156939, 160120228, 383472999, 764108580, 635712814, 198728113, 884623380, 566358089, 618023755, 800592637, 662573545, 465615526, 402973032, 141670988, 327436476, 338586189, 765258671, 893293740, 565612777, 626983574, 738741390, 657365584, 166790700, 335729136, 741232893, 376861182, 673027929, 163554643, 376241366, 627057243, 222024267, 601502166, 356446985, 532975092, 460660925, 463533998, 167044047, 371440835, 458852575, 625268340, 174358520, 690484271, 372701476, 880387563, 509744995, 421032659, 967936463, 993713904, 304802056, 126841151, 714172751, 437065852, 241616535, 723529545, 212448054, 127975853, 185932733, 417296031, 922149484, 678761032, 392818505, 475157041, 680493626, 704006069]