1000
424796472 133614812 353655725 866497398 965642645 50978070 972836861 214302178 79483331 178701589 143811100 390778236 927095567 285713911 926195191 777973758 597383172 43961881 549442747 969343591 378217586 840780568 243536597 857646835 908885860 958688209 227301874 65767712 692431143 496404577 760632063 32365481 106014538 242829348 736034858 163675278 270710935 765693368 823975646 865934601 651282206 846785274 60503498 240039833 419234346 217561351 803033817 398750714 497635400 528745532 61502266 883423018 457455430 746074165 76537177 494300516 594589745 813020625 128032483 622101031 399503189 518006571 872134852 565140016 946601536 810706849 404541227 828729211 583705534 804441039 574066052 442483525 135071709 2100628 27022973 975599115 761226730 132966924 162592257 902783883 614631537 376483731 568590654 574000321 447998784 817719751 490222753 352366570 202813283 996444037 322459096 300874884 325700904 843778794 537564110 270596427 337358363 276911954 776053938 694478397 821060874 602734940 953066992 71420565 884255234 758022371 243994676 371464914 704078415 479160581 609167213 831010481 252135039 323332127 51941575 324585262 394252894 839907790 561941167 510601862 917579002 655172334 984489682 879501878 281214112 814056350 636053021 211746044 896157916 541790009 819015358 444781268 997997691 516979293 850126880 918340347 950364043 131176167 722542321 153592815 224849241 986998772 427008799 998078316 853854322 386496480 886428629 335355503 249234594 123574346 572151170 146996022 670096630 739492877 611882450 443418429 945799612 218464583 129460657 440238913 874587777 713166165 84653390 502039872 545674769 250693332 955828757 403189878 781035642 313401248 716538035 922034528 122202888 417763543 249679125 883925436 320594505 307026647 893763176 786011270 928389130 578293563 585528090 939388923 620101975 220883168 907725014 501660057 84391550 762194917 713654922 154115611 633882891 157149606 173876324 513676673 381575116 861632703 463800271 32926981 319638734 683390734 792988538 881167654 64198493 908934064 628488529 185028001 340965894 344817410 693403777 31803761 18731671 437988512 333330294 13227221 62055965 82562921 427198431 360365385 949225189 973710200 794001576 209003915 167553658 235894827 28817406 487910807 477942188 577878559 581291343 101623978 758097542 947874097 3962694 457839938 598424662 937625214 248105937 26110746 409049512 956117602 973899806 880016690 148719690 417795707 334112408 667275204 102034760 347703718 689252590 102165071 820540656 580642304 118571531 23698831 461333199 217700582 143926302 591771522 791460785 330122485 982512275 872939364 363525028 618168841 908775959 467271602 555010548 599462720 38234263 691264041 450072879 724717303 454823744 251793351 835087137 931181771 356101247 855572680 949274328 614107545 127375361 844587690 284570785 410853245 382728371 228432937 776571400 424836566 178088131 445655362 690987995 281826111 673543580 656529202 714034214 142325142 49923053 309083767 812119607 857951224 149986721 681392333 287304859 284097217 533535207 873202482 565281054 850299280 632806187 908626914 242360013 312612672 81650969 500415578 538642423 984972271 857816736 100138839 745340966 169249530 660752364 591727319 138518570 647435518 189870698 789561366 50534926 481093592 834557128 414611345 28572959 608835236 353491697 595074310 373791723 867789249 171179027 782803313 362885183 764392650 705334427 425435920 951793959 441842333 586229303 439511902 473613041 532555094 961104850 454472475 602617130 874782804 519079835 249757761 366075038 397891123 777349374 153318415 329044314 264789711 471702183 32866049 298763948 122893126 262540933 160404180 973322529 812422645 919388612 916651142 989673606 929060985 778706641 794610259 569998310 246601134 533721945 166329784 115158417 363462579 453319241 102163827 208462098 897784291 493623247 328762752 482420535 62272732 149548886 864263452 525788172 19448443 913097100 318110917 815991519 126867420 638184543 816365623 622805052 287953758 387180794 871665775 407986673 439691932 893784524 166849451 534527243 627530357 534086785 234530151 210284502 704150788 329161733 920909408 207902175 785512359 895670407 802901652 989042677 385107706 348142963 76572479 535249442 139300572 403318 215239390 583108022 335749736 99378813 574729007 788067644 185170428 712369589 670506286 90351233 512462133 817787788 514784024 713037460 904476400 429724589 155574379 169058751 760525642 155549446 426821091 514391954 50048415 223882181 269369213 617062616 56600718 410762069 558102135 321007518 972221938 290950757 371999565 358769458 863323369 398848737 6084540 265983009 782037967 32979958 434561217 502944823 710491715 647375376 806409370 891271298 166781217 612630750 13855940 176285518 217976453 56141644 705613306 645041705 217594829 794487175 268559931 68896223 330778006 906290941 736675011 447404159 6724029 370370649 955083280 495231827 899672414 755921801 632309214 360914666 404638936 928535483 974360362 701145361 395676102 113746778 355376177 774152917 70408454 875748373 469302897 582466690 623917749 964607703 795144871 272484261 272775216 10231759 51955406 869607180 640619027 452977769 472485925 900770500 699206205 363173202 687373608 863513113 937336265 752451191 331703189 535999897 934738197 172882693 552055911 911524113 180517822 549980521 648242654 761207181 449443488 914508112 252892532 41084250 648588762 600116135 690415080 341956615 276778695 414196892 372606262 389091422 10724358 143152538 48653980 141737583 589530994 659964752 979202197 460993413 47791144 529463209 577194720 589596205 715362951 368904660 467315322 478095925 649318443 527873085 865596319 955187370 237355504 648498832 464221132 424724440 617338356 519645116 12035006 597559629 388038036 198869485 547099507 622014933 908049773 471401616 798404647 205748606 132795228 508478546 304246872 681871253 103085693 173599009 546509249 232755366 583531310 111410728 679097185 153863807 759683340 253418453 364011893 792269868 94179572 72820694 177597817 671911931 762386691 593915158 775621162 88316792 934122134 190669252 212282757 461282673 154130505 340182860 587027656 916275699 916446715 805562970 52391023 570431562 642257095 743817949 514636343 535030020 160290571 278681089 267408158 417970669 669773923 909567027 42023776 513467923 77381550 340521760 228007546 442911682 512863495 34092469 885803818 75260552 542993357 42964512 536974700 383966514 921039515 706589644 247139453 434561484 236251982 208856935 875495131 690474404 643737349 152876767 100185154 165691207 208539164 983235935 909854640 656664704 789111855 37261142 502396768 596881503 144016924 362666608 358937809 457968943 898438144 593842585 255433920 318457982 915413816 122070272 127545128 951957784 853607009 429185041 342051656 691868939 612899159 412652409 588457884 689232291 255583033 74415909 376440802 266169710 59251298 123702338 552507670 779937337 560023152 71619902 268355445 519559440 851721792 676258756 388280957 156742721 588960750 395076290 633722602 557462360 585301209 273629286 535479993 804912931 120224668 34382875 230132008 851857326 439381013 370149008 141692595 116471879 977946977 803350449 993583895 6441851 982855645 322026666 617981778 397969686 135147302 39030250 744897439 122852902 660801560 924692253 139521406 541508343 177587922 595801904 562148265 973689111 657490095 144282704 858956319 930709843 450093133 72763371 763401756 350842295 311084424 89961132 903014942 108028305 679237503 923722369 960134625 830765933 905908365 929089688 974898786 403125529 787979857 383780188 930947551 129637281 740394918 760319100 743824340 178253651 656096426 24838883 476475134 226156988 568087737 353597632 613777242 422791080 739315826 81005439 488082982 655139109 753626544 261793741 887429086 746639743 548393874 989222295 659112000 445221700 867443827 636825610 26349640 206649920 295414256 904383891 465643059 116169601 575454952 140512735 651676030 932933972 382840695 245291483 987753703 199793477 87076601 349939125 595269226 511386146 383113740 113552600 541140805 112415735 394163341 384687091 255654900 947945490 500022681 900593393 35024436 468993280 795899789 244603137 700446466 859382413 643251717 729958031 824362140 98600390 892530144 978950983 713814142 737853178 77823801 874094104 629119846 644667315 544468846 228065582 839595343 184668353 416120604 628611062 397082488 663227951 772072479 991664925 664418398 68086090 527700886 616279185 494930877 140498080 375533532 536185725 817182354 958843390 53523599 726864463 620812570 128523376 162810508 662837941 628540627 54039620 249809392 640966042 342271609 979139847 256530968 324678445 630876681 206420357 605363616 185240794 54948033 447732171 547032166 812624205 798736669 494734119 553822599 640406645 795945178 514921510 268057440 460696958 69945590 411096212 185926030 290698453 319185837 896056703 76553966 504116775 662913661 47692596 843704732 497961569 959427105 591334719 302708982 35130288 812318872 336163438 586039705 539348866 63507231 957412045 554344290 65879682 367876145 443601322 992897390 477630623 480498573 799444369 508737561 899001604 572248624 56422992 89208066 932800544 384377429 210294515 126585604 231084446 319093627 335475145 770720317 756752493 334581855 749855836 122684426 225473721 682754300 722243452 758057736 631228911 989660817 10567475 226640147 588802236 752735643 74632913 651724105 830668557 409511893 665875681 308925960 796469263 928733246 802088240 217330923 875806256 189692179 876267213 509358799 84385051 16371151 762945538 761229267 735392190 389794097 340929631 686795603 374262855 448473909 562151598 913220587 835816481 593380633 530746111 631127929 704854011 681230169 979990685 716311322 152167361 141924786 956781590 671192363 853421215 662282530 102790454 787289929 986339588 127900645 751770891 620469840 129642652 167578488 234822113 155249246 785018964 37334169 475117894 383541968 612813401 889573187 864386566 401127491 735714329 864957110
504320238 453034436 502717938 52087126 886428296 958200072 64762551 428131976 263487095 475415737 204481588 313848369 978067791 561108922 708609693 859735252 872120038 608481330 92503399 994542137 104490577 222140804 746263879 589671778 285655012 686809174 442555443 421843094 325093685 308287630 994912607 652428634 759232793 946594127 558586688 201373810 311220132 980465919 965947787 164646884 54216236 789932867 411904821 34572532 901201222 135353600 349283444 981070887 765513927 782955099 671896764 691326275 205233603 753142457 770482369 48502092 176144016 303623359 980319355 383247496 618054851 210395730 35824924 972995707 862940976 284799127 613497115 773196779 599599597 25934834 788766763 619193052 673115215 190267914 340507459 210986131 173040874 12022723 981557400 751446423 947880340 268025153 7304093 59076522 987729250 720883691 801930505 198217171 547199657 934979685 43567823 559624278 314031357 364922515 248642598 524952249 276749620 328338843 698508163 296484288 210808163 615570403 310320281 960873841 495054558 16143630 773644895 617232 312017979 159366146 281549065 597757731 277987663 697009893 831481356 161955182 96608559 881379610 810038301 528343799 14727727 204243783 16524081 996721666 579589093 298782545 594409086 187445268 223938341 446442589 617654392 321864179 403812870 803756240 478039764 811671971 723962331 333401679 105153671 373637738 649145145 682597311 669877190 701712077 126286327 757504837 478814215 257647247 676846376 500956230 14504958 879232184 977987874 923790695 513438624 330371466 801919865 878422156 294280226 140789388 508863235 949129436 70165498 405571715 315843029 472853179 73639643 666029939 442122052 638625229 285601724 296841377 770810340 867165945 497146065 93427859 633314699 71355490 233214864 621600013 655649102 885522799 549251244 125590293 104564098 177441475 169690140 44275952 388980155 447989317 302444308 880500769 501483727 638456088 139955721 172923247 811618002 595505058 237251760 984449759 69536027 492346248 274120190 327687093 418331708 939113904 486739497 280122999 600216077 318383165 868825765 175711465 717943714 368998549 845848615 249882640 499279695 341141341 414191780 985723442 447887529 593321082 136386898 126508755 345441415 30771473 195178661 588153529 288004860 600611207 302209106 168362984 562966366 104051073 599308110 973627302 361905218 668156387 334889422 160732791 551593340 630358228 92813640 667789345 189363234 393355704 383330927 393134504 137953417 356428596 954361658 627894097 769447493 1715500 440189149 272862370 258642476 186362567 352109518 103748704 352414803 446725224 182993856 393408143 854210062 815644598 601956266 265063028 35318260 252173716 773530560 744089237 19522008 185043497 889634679 5272246 965927631 792013528 241567620 671640029 101085488 599244359 654589405 735318606 31713422 180110939 934409654 725083022 40822718 119109690 318966660 823336035 106816215 400486471 214540028 823534802 625517868 430652456 590405395 776022047 8869715 236348098 315593215 199725263 793805600 30433850 945752884 994497192 678439849 143760373 620879207 608593070 994057027 613793944 286047885 61856551 579924355 714998280 658808283 455931287 763107133 869885289 99915207 706750148 162387592 326658338 227138565 755817650 607164086 808264407 138115978 556852391 678929503 521791341 953600651 619736871 5031254 213888264 703456893 349327351 15662769 192334095 305919510 480477725 860241604 587860517 730253130 990547934 249238310 996006449 652867918 719067325 962532010 365438550 509276311 168595330 168170853 996242171 399296730 253663792 762930862 722218947 449021709 749353996 822199064 104812436 838065508 744493979 533606009 760631444 684036948 336409763 884196325 410339366 659240338 453731881 640368562 835382000 382694419 842614385 875309941 569824471 638709773 502388993 25474051 63653120 101208052 82354332 210182512 26702288 738189693 881561418 352962834 540706028 320968093 979864654 255144830 846311225 582591113 595847725 699316360 438628572 113460663 532518573 26621766 417940794 516327387 986870994 516788237 510998776 403089642 645965537 767210610 529655802 265942553 737616993 402373449 90829671 937592798 874875412 190323880 864986531 882192876 633254401 208742372 68682322 704491834 188905837 777235857 690401371 402660348 626463451 169920901 947082209 514910120 374915603 386855125 402443339 718772465 185297432 317102037 544872508 123534286 700003631 841698331 369584027 525217651 184786654 611223676 327135115 457465941 945065449 366197517 587046002 870894633 482102869 86392610 444413429 123020261 895613800 224760657 898715385 173971388 929405863 5929327 70284196 838532901 705066710 787656336 947050841 389248724 395343866 478488330 45697214 687733951 823485273 997609074 772042168 407662617 445394552 311589276 235361132 927341401 997611034 474214047 316528191 469160499 873585223 121521870 315920341 85539228 425400385 446316222 149410581 652566985 370902672 718938181 177649187 720735280 562755318 556305016 479685220 604500868 648573562 741780908 415387260 365143484 435451745 250126710 739070034 548632588 436824879 149314730 964449034 248262890 658110121 803609949 874553608 950702601 925845461 152400614 212358131 76526176 195472375 515405784 131212462 848338467 410952597 965709321 206735199 772714183 764443763 177389710 952889196 745016578 585436055 205285819 157634936 574657735 132703045 379053350 114942313 12166989 747158787 14930340 609401956 50909960 785704853 331604809 198408911 322727853 2648320 614997355 505948237 809837105 753585290 800824991 582168516 733548234 795897528 477850810 902954841 744853228 423507789 572302032 497234545 948983628 639245137 989621047 727757233 365063135 903901959 618368900 410408189 549395418 327746548 652758667 434426748 245339571 643502813 686839906 560169874 789820190 333029833 571188318 347684580 427747600 526348794 789395219 989751894 628384190 23811063 235250776 678459919 285572253 138733445 148534591 704716147 367064163 185511848 290646048 311127334 456804100 825158821 325589646 46921487 528218549 428913666 620721503 488065617 138686699 121718915 92615848 596417362 341958747 340499502 463088061 116152760 114578171 909194823 310611764 588325990 708524799 712864596 220408034 501152130 400690652 243066137 818852828 139948658 874548807 426436251 109072502 387091929 683270709 177113120 864753734 206487453 837381852 912593709 78428192 705833699 924653744 147330694 927797275 431963152 110833510 391345712 567893898 200480457 106828275 654944625 846264066 729635827 165016205 989894349 877795418 83179955 537370279 597724170 209373861 21575534 752765688 203983916 940023865 968682440 173270388 370714489 466812074 33716392 439848784 542366581 777108687 465985842 873513730 137416421 93672635 253692362 791551037 794225615 505450947 255730711 461063672 203010936 3355774 926080765 522930279 785845860 111943359 491551392 102843648 417325656 669700507 203783271 746528886 819606618 245955433 21308149 686255296 679846062 698029500 502239792 477831954 381950682 27571050 577056062 894521313 268992418 865307271 95639170 123086050 894652172 923292778 161202594 128821515 192988252 229271462 535136131 280597135 133962775 418078224 755734090 133772517 552395267 326738111 378355037 208333505 398089509 466788358 796477279 640531993 436465601 398703483 761988150 830685216 439573340 65554930 42732295 46490445 277645500 403627393 916904502 87322452 942916581 840906621 24540010 330114346 635074077 340429947 703209863 189099268 663176168 679248463 311955634 755611224 664304395 668193807 279736912 928620505 772042893 728432144 151961349 722367870 49158320 517947878 609098424 890322556 797102843 344782439 655899788 271036742 521893938 880652200 520792808 497071506 679093851 443227902 96349551 107690582 47351483 485722877 169681160 310607302 673628629 672383355 63045590 61073239 584599409 617481612 654501695 203150271 790016145 997255559 749329897 486059761 767124348 902668543 195055543 149236260 883517367 436512969 447460303 1683916 347034630 978021116 404658838 301173150 106955375 629494507 753221041 16594063 361369142 811354412 711200774 67677909 30203872 400507795 981516728 424270308 63307059 87095607 369392684 838617713 521563955 708156011 194245641 681629809 279628326 735838404 685506867 689986329 354877840 373808409 80305359 618708191 473710135 901646717 93628738 813663095 237755423 643441477 23368241 187018710 59021 334788872 470893184 642364977 825860103 658165913 549346390 720841725 3239506 203258126 675754774 245633008 825682546 855146684 550054759 444828670 599603884 466178359 798572332 469213532 907404422 794840917 374069644 71801471 528068292 324952363 209479914 121921820 154592108 695964173 313845997 659535913 552232898 79020689 856405112 380736986 86252620 265107084 121823665 715015076 324285134 334129426 859311101 983056956 590520910 878860921 751961090 320826263 133420816 87651414 390737315 666423531 532869785 987671934 88081414 185172652 464974255 338754053 889334160 871131279 400974422 680284993 580971494 638981513 892676564 50457031 120392173 231152080 979318958 469916011 786433994 630436055 522806951 99941700 962861281 97747285 686275270 326872996 385457625 843192126 538882384 462639651 28920470 23733191 865876937 534003604 686237245 121429862 187661047 574367245 665630514 578414031 255178462 525256419 518821148 647688694 588792515 359631018 143469278 23752211 798299436 619371320 132252831 788513688 539565021 286110626 956702658 307030331 785797084 847262780 856747758 53510898 465380206 991302813 786361862 959052273 644728854 708289943 341110832 465523373 180936859 738904386 745000402 57551579 549968130 210013937 3530895 533361 532300943 253930298 168959309 704149154 346672584 292715506 968124977 17456613 554717297 593047085 111515296 914825198 796842895 67082305 735504191 644690099 797237096 715722179 139784179 556016487 353673600 301357448 7351777 443987585 506256029 708255652 486325614 136544693 865610947