901
241151291 9130157 487767935 227825943 102375468 550426892 975472913 942452779 35216745 647588905 56782515 80830427 496366240 465976585 702471584 420719311 575076861 137873681 411947147 748966931 917180780 54977486 303924619 185978056 513430578 55355656 113444270 771374098 732963662 612701179 829045039 750651436 341746170 704935973 225586518 306837136 710148210 526508249 61859156 774637613 49062720 85605474 681011577 97794912 55201181 99077006 239937982 660197198 546538967 642868245 462413165 506094637 972483609 84525520 106787657 824838153 285701357 493574599 95402410 492352110 242454486 311538239 155850894 119006015 565696557 360728320 815916703 678421325 432417806 601040237 619046770 951117925 592655632 728446158 548318064 128174106 708635264 338114602 541862205 746614875 482226527 998952977 573480368 438107932 738528876 280763257 397296510 65391534 440268361 377063088 523937798 36665181 431332483 746716777 280598719 284829562 983802623 421981413 909220921 775910769 188182354 536255152 859819393 255308756 189782514 410374905 94138756 128719983 356378781 73336276 885993811 232369985 68174960 626157531 568232213 376100268 637092576 803849989 842937356 653682647 552981342 997315778 541011782 649564115 194875398 873776928 613167580 359478136 76204163 134650104 764141375 462923353 386410708 793385120 64212360 599060564 442628844 682914696 975794526 399454141 376469936 908455463 39045616 210055471 126515387 830050453 417289997 164773322 235586764 143780387 373906885 133110442 267622134 516877118 109914197 396861585 880141753 637687198 916046875 649639712 670430284 332214424 786548698 933388684 407872824 959726613 993672213 599971338 960007188 177802496 520134336 437058410 286011209 320645955 48698922 442380266 28692397 832400828 482774284 586096580 645831568 275212060 662826070 919307293 279926526 383406611 513114504 134204106 882719407 386668039 373924720 644108403 284648042 655851502 516161964 330359395 478628279 217837450 2505882 108131756 940954766 560090497 529774527 171968927 532111104 830508500 230585138 801712935 471508446 613776157 675364670 894608723 231546976 887940048 101449198 794604464 459766217 272899063 518119464 724975647 999101959 972189317 980402433 495128942 406803348 74017808 455909906 125076851 861092475 128136500 963691131 787640466 743703534 610097970 988444060 982537233 641872756 484536913 29716785 192628196 632188797 97019754 233213989 639040119 348216076 209942624 851665118 651129275 849134894 923152904 442436785 760274652 176253051 292307781 464979784 152852163 580168368 877079564 841867294 256742839 796950937 503059780 269430759 344178786 556419291 581471613 240926332 158117431 966308590 167687789 845795492 765457471 244047940 565367423 901830160 226473957 833893211 200138176 882774157 128325283 180431403 100264101 241149135 887712634 246091617 197831175 149951216 486517747 78132056 136778672 730768980 32094084 209876435 950126259 121356114 816665012 537910809 195995862 375480561 719845505 697035269 699054881 424912845 571824689 419772782 532310455 371899163 821349235 334347057 335519695 289048499 286623656 639594841 491759211 552779087 485267263 440205194 588775826 208721270 497644940 183580926 696659972 806760746 186890278 652646440 986079438 807401484 421365540 225589562 909828774 708088531 993718287 679614127 752568912 795301778 423113236 395307309 40411023 307254308 946436352 52021626 209322340 437904082 355858335 39065178 152580482 414515351 929964653 128989909 408123875 357247409 12954354 48213481 617121396 989873734 822754640 498660899 436898452 757156609 668786317 602521753 419060099 418345887 773367156 605008972 703828596 539284568 564648876 601527554 526510452 639644506 861782874 895964900 764586231 430515672 519380797 18037180 600910160 220033007 405477682 962661263 756476404 679016369 980073685 819556820 779049469 532636267 988719173 621597399 523983071 518667482 687726740 16587375 806645888 577519544 191855877 500454230 219018700 258842496 653919549 823749573 797620743 961096596 358619335 626891043 888120857 959224624 772918614 611973830 577318415 743199647 364641650 583340684 383920787 740516599 920925607 357677941 683953063 43720020 401833174 402856625 513459738 713106515 525340260 413888797 282817547 516976684 903101405 104985068 244795763 400683960 365332524 56269201 587652924 380661629 346130743 749407803 952999365 468983509 745956255 711464653 481678864 755707548 677692238 489294569 758108311 305319639 904961205 472643741 250529110 400027933 867486440 383260940 576373477 744111038 803873204 124164582 917296298 575239072 147505087 208844527 527780381 643530481 249132918 689375030 957338202 322187883 617405801 334606428 504347423 903868907 113262183 317673163 948244184 22371653 145588005 654744791 256951078 477509133 486270397 267981367 472644811 682747254 856963065 67808596 599215990 503158529 467605251 139870421 974291544 485059160 430580440 918118674 484690069 455722518 276044541 843379346 426475108 524121839 998638001 529277065 258026857 537195857 798830085 397747983 729441511 545510798 113747171 347983802 324292756 346788020 667929298 4887262 413516461 619707312 794470996 107642166 187172263 918134637 591049269 625724358 713689526 69215990 681311968 514200963 915664918 948004287 451576384 11820461 116600989 252001351 838303084 530862849 643821394 417957044 889747412 274015521 86424156 579344378 95813494 304756853 132335624 758205010 317698673 270473086 264871017 557795444 685051094 961296476 617251787 114446175 744234533 234150599 150081311 278093765 303582305 830225524 657265240 532715084 38642752 391290504 454075043 966474871 243953269 806362744 675057969 721897639 508354860 396424526 806612241 790955422 995974755 729997831 110562276 561160555 529375678 238527552 949255038 984050004 594988474 768638700 477593675 402062727 583771347 375290852 535710486 175338730 307026046 630588745 388524845 541271538 996655328 109014424 593752896 563299603 829999110 832434649 473145362 760384067 150144532 3432384 608208607 80853897 207085331 738673768 940396004 323699935 895437612 326111430 4433390 926337239 252668148 384915668 468685299 652861682 895661975 846062533 723851504 883161703 787169414 14887560 518799672 643825041 788971562 484155184 389983518 562321133 760218780 622778146 165152080 201964950 57809287 613446585 424750173 951765524 810162594 141288633 646100504 153258279 347433268 343424413 853464862 931085230 818847342 300817897 79481870 563538441 877885350 883486474 803218395 227355314 627571559 549049258 629427998 715587361 439877908 301516688 888806418 540853362 615744373 315873441 666046242 242913509 416989359 345071376 8140122 384628475 529454787 598646620 584785531 69862424 663929253 662502620 117813394 279436865 114260189 630854537 876522569 167599857 850974674 282094209 5153765 719411007 860211370 221938299 938001030 892546588 429631341 796077211 589712691 866468783 137949158 362176051 65074119 759814306 808153789 255733480 521679164 119337490 609465126 799225812 827619159 715980969 582594957 117790518 795599230 181215829 122879331 585634367 397636917 692412172 766595218 589858807 794678427 786364539 855977855 424573538 491179758 686636104 608387876 572060313 435049178 217971550 354586712 977658926 66908797 285820701 388382847 422846433 525658143 798202865 903764917 134450283 48247931 439413574 847276617 234954739 643232769 996185892 873746479 368867865 509583528 43237877 651111213 959043021 362508676 799488497 81609742 690051417 665780010 4184488 888552850 762231115 846238004 903467605 400961832 538381297 193504818 601715178 210407388 480500998 809923201 440527926 60497566 198987640 383951893 547403250 725944554 587645348 13026069 349281655 593833322 953501559 568767190 15367253 274934124 502900595 163437379 267323336 147131165 889446808 282854059 432067591 57123927 131942700 215973761 777438957 862301718 900737149 566338063 799759921 440302572 156818855 236865255 78648441 261242595 281497214 466216283 730165296 863933867 956883881 617387120 946908743 649988404 738734618 111562526 497152139 813224746 773273465 633892768 407277384 977511411 755052582 113881994 454223132 735955256 767799082 399729244 877054770 559015583 445171799 177686169 353345168 999451094 298992091 472399662 140685630 577051164 869582339 139283444 729719737 60044496 370486818 384626879 475039329 554511994 257630590 493619117 151867615 846571662 186718835 200501252 362834706 961686108 997996792 695231307 184682654 326942552 693352520 254528141 841587105 302882828 747282631 225536954 545684443 902441342 166476435 372766345 17611373 914232673 513789494 306652198 749907650 681759926 538322224 983619649 632195966 653181463 884489261 27065038 183175359 238376965 317130905 748802851 530543083 907533347 458231285 649824357 998806280 640957075 700821203 969228712 562234615 46254137 469171513 684490854 575825789 336601036 847900641 351567969 906421912 776252556 950000167 349556144 13877040 225115196 634031972 232730229 202761541 430448185 754459100