696 696
919360278 134735924 932026072 346925435 36520247 714516687 772437231 352627637 98944879 145051303 811874141 558171539 81912079 165752924 376480018 147743575 682322086 204296655 964000319 443837570 923558918 129226786 143382102 807280085 645155392 887138229 454668296 716469584 255072678 844530217 341080902 77434422 956586951 687962720 48522047 303203078 615929206 60844666 820730471 918763906 578975427 610811864 93422189 198181035 538919166 889490204 984512579 359161025 615674554 136931366 488257049 610365255 550475719 771376151 522956641 640976636 310803766 404377937 420262603 520561123 317470040 657132404 119906889 631183675 901797310 176125281 69825804 124458373 795350329 711879994 452555140 853959300 619600859 577023583 53328738 832205112 638010611 725329265 486506393 310488033 688409363 356741714 243148376 678538753 787495949 849361953 33196816 511609433 768314609 921857858 537362035 60302570 179461135 155481939 44828274 740236020 70206714 303736119 89878077 736576762 742613634 929782543 762081349 641484475 241003704 748264506 638083645 796030777 694237933 377880923 976500500 484995253 68192690 420887634 617615099 131694256 950031576 920213057 915494244 50096619 890452336 996770696 900103936 114062950 861294027 896574920 799687615 35476835 482161531 480602595 55398099 475509091 625418063 566581240 843282604 59806759 905948506 681727339 89209596 15576240 580594923 699337946 548566708 808666431 627985557 34045480 705794564 600913748 58265128 836056693 116502621 182225329 845178037 38694435 750010994 17793111 678315149 437669586 36204082 147824263 452877121 558786403 355293902 119624386 611659170 327050743 85099704 592393417 339814337 229539312 648262049 121825180 759649519 246827502 444162169 617419645 830421437 753342419 454045553 864500717 427444733 6634687 25129980 244077485 947608766 47272723 181023945 549862078 650805331 483343984 290671049 708130912 2667083 95381944 83538990 299775254 868970361 768318219 286604393 164998815 5267437 948794827 261698090 598048253 104362744 577509527 757358691 837042033 695748395 283454802 251472708 405824123 77949527 284139805 588095551 161440222 218058125 579763800 434796549 341187993 946496286 885823652 657291398 494831342 151812251 942647522 334270707 794363486 565148886 447510836 984352191 261057450 70072286 396784890 318589592 222778323 929851654 543511253 729613426 98550041 391861981 328993447 192115068 150834942 324962102 225535376 46692647 417748035 971774240 193163762 605171237 170139881 880636142 54621036 82489447 991327281 363011632 362611937 201397021 86856348 720508343 216690290 124865721 511520234 554608020 278087551 912877292 626802461 403979032 554508969 455030950 885214326 86395604 594634705 517429784 582902134 41312410 535596057 642542261 643853534 229005177 739665377 933801771 667635887 326054851 694576330 955337070 975987753 656611594 355082678 74088109 103073742 650329630 780631237 949634905 694821727 626606351 444830040 138698532 588555229 546992944 462629905 175068415 975600521 94728465 490087632 174037786 332878307 689666691 771449014 322199783 618224046 157646487 629043237 367243542 464561385 745484190 510169277 222324121 79730902 200376617 477055839 898768289 31482870 522344457 548944429 405149598 441749001 453798991 306688647 90059586 591503890 674108749 972517646 983797629 430160 142108562 14864803 403396225 31812677 290404081 785221480 474704318 971712178 925397113 565777086 146888166 44252568 159204989 58658116 125071594 933442104 14554765 433273309 916927482 92969234 356931961 226240681 28030856 235736553 203983188 568274186 155934020 266435516 953254766 493848480 975192096 590785229 838816856 431191628 447027788 605394076 11321828 986655280 193963834 335236076 700021537 402092460 661807515 332758717 735014497 192104545 52421983 168039503 562008885 780895024 222703032 475901732 321725551 664745531 617252118 2702589 44988958 81713890 282877227 539333851 257064341 878749639 243356392 377387262 57552228 738678986 399069821 389704425 872569692 227779340 574050140 339648347 649284237 547698415 711138869 960866902 493160778 467734034 803578106 561924891 715339555 76949849 57486555 106133034 732038889 421553378 414336074 226114374 144482478 109265936 712411896 746018670 48367553 684348291 177231317 138769125 113726644 494486813 500848403 163079978 189559640 65753597 709035042 615932670 940982463 854591111 683757492 264527972 896441144 590124633 619931577 745950876 642475094 321212502 662931811 467163174 608185577 53824158 808223523 536758980 670260994 797992082 538544297 812408183 494896113 615353556 870855911 505685120 175006281 255807812 699017229 556340576 129990618 205287172 987990413 942425303 742815158 880028788 673735192 317078247 817587244 116436277 890587038 203584722 658598094 923228200 985495888 337328407 117930093 266168687 598084513 713038199 642736411 410084970 2797119 74518773 469512743 228859834 418269214 109217232 261639204 727285569 382549869 348019083 861561569 203507231 209791389 950044389 75194225 328687798 922660193 454501344 424429092 603927205 414517927 713195452 931505803 440287951 119152291 347579644 576553335 910779733 172892611 385968479 376993017 797671830 51660219 605588456 434850914 377059893 913510266 580086998 541553731 613498131 498034482 21451691 404717165 912606544 911026259 122191655 253335026 757597005 376924046 602649933 32182049 52077227 728345302 53119324 333995405 871937100 600522074 128736727 856754181 249849936 774137739 38820477 40860828 517879832 221754651 741633616 263806114 616982598 598101755 549343632 329801383 619154618 434411867 354974656 74607230 889613973 38250413 237203359 297485623 18981945 278213281 97409327 808610595 723210054 630944297 559372721 328798675 480269981 228611446 311848870 273879065 282859103 200826104 597512399 654718980 275352558 312021089 113474092 419142886 653435371 713533601 647774208 646859601 153898549 138237418 979604426 891512596 691754991 832986540 73546828 522926914 522551674 15370393 12181383 774061099 616805493 511452322 157775547 83745631 265061315 244844791 675088491 143176113 567163780 989545994 545478742 533684529 774799130 711531403 646995326 773527344 43479845 206328428 653878820 660361791 217340806 851066589 378677193 23296047 23673183 241724496 114656557 97357841 120302352 387532662 535367763 96298039 142638138 463810111 479278714 471567920 635856318 38392285 849504804 189926095 807309246 86787265 661154066 698103843 573346714 514291866 825697349 642404223 344341492 318074460 198411774 538203506 219255980 814454838 478045629 785140175 590110435 800954266 138836036 893739430 221975803 783771960 740337556 90536776 5253267 729638658 154702062 807546438 444880527 408129064 318466771 24409969 412971789 734105372 427841795 315774170 375606128 814308751 280367233 193374162 555565656 290196081 912422284 448018155 864123815 974793716 908693414 197293044 95513724 309747592 629519760
98856151 418143962 178285242 502494028 935269667 531907507 99842994 445205700 695367766 454525898 107250133 847267622 829848137 120741578 776868765 763052733 860319252 40021403 837390018 197683474 131514385 491024998 363941949 38951149 6218712 716531859 563442760 514923096 501828164 265524429 821126746 831025819 633382764 335107324 453085998 69546047 870026922 818245704 786001084 416845070 67518614 498037020 761609277 30769168 957959946 832507167 426598954 120150927 459363615 411791676 422143549 581925140 607867181 890317210 736115566 16219494 900012751 739212195 192882678 952913552 44731612 882931201 942874446 46959067 600722285 747058843 214927407 829971407 23566301 305360027 953171603 348066358 8040643 11404394 12023218 355869720 682455032 404115889 203234821 511870398 98710167 301946201 933175109 424913586 131864311 587474315 954813547 292103100 969700018 255046576 857647537 92810982 865167520 309884529 409687182 636514168 363271388 405888951 47349693 609385980 758513853 187395243 37509431 359354426 436945116 41387446 442130483 90734396 513246484 587556480 543062316 468794186 435755644 462309876 659254233 699617261 65869678 481837626 161387318 134636015 282742658 15958202 698957689 55264089 473212818 298274847 657785372 277888883 578590647 505906256 91769817 233274566 732266314 68823672 622816936 276325148 159079651 44974846 340635074 913331581 665345628 429555596 882203552 111636531 832995022 792355084 889084923 379135686 919894673 472715685 939475405 369368575 644119359 68804801 153164622 518274024 83714993 42377993 123323895 91633610 314011136 651386470 79178881 674769453 12220292 144019457 850281701 72110810 389586647 363860547 143822941 796859099 796149201 829389013 361977185 413365881 505374093 338775712 206338474 436568379 761401442 459482573 725330993 969433069 121193962 17894853 951292208 602423957 354169085 146567985 947588638 50847870 227093429 36670969 298477494 907035697 403420011 17192776 156058608 572228982 490830008 749869446 287848966 714383702 120635764 686529115 713505391 52081691 962871481 853494962 899751654 549982030 247885023 341446834 807690851 612928951 224010625 205086150 87142687 985878879 647135606 510284437 861701779 686180240 680201432 266232073 185755001 755525330 973294847 882783308 123982792 602361070 120239237 102473925 61482683 343873775 1333059 752768030 225524938 949019 715433042 383272256 405544879 839992573 889225738 17982549 622677089 272922974 462515205 234719940 144452891 789156422 177429276 327639351 6981973 265566462 35928423 386730903 29715400 193370640 231757888 492517645 895176301 282959172 345276480 320818689 48395390 953592740 95670592 74865182 186805362 380452728 978004568 679965260 159938564 132084810 752951266 535849140 606575661 69965538 199202678 6104766 706828580 690388809 455159791 203105045 967002211 467237065 656605540 445090721 266677412 46220267 688853294 745835402 53310431 292253815 823502312 304441659 684676429 74025334 471077737 699743835 180952424 868790578 260597451 790431701 599087591 252005683 496589414 499453392 48057797 682123331 796436948 713582006 915555642 810093674 990141934 330990129 30630335 411676914 52342477 45620008 480214029 287075427 706977737 542077893 34671134 750664326 769796988 952520305 111775530 825689189 932533183 231778005 644252074 291381833 73092011 614045658 11761495 320240057 482438552 103038377 678343978 82594177 616712992 961492907 206920029 973952424 144870683 315635849 781406568 777083767 585404836 382758444 811676676 741551992 501175314 780488125 275478826 483937651 841655550 164527013 913265683 34364017 547531843 717628812 717891897 916489916 630532344 902566493 981598804 14920157 73026422 98592832 491203677 244412060 22558552 649211549 16978317 7482626 134455669 351383583 508198749 683909721 618418663 208167085 844638343 382815018 728842759 507989362 64404739 317558588 106441837 987122901 525367306 820403611 825954035 56834176 133092373 274632333 442831538 702884701 797467358 309079965 778331650 385359763 217726300 140610964 671435901 971013772 929500106 31300218 616129788 42607345 499612576 810319769 513747863 568736427 15450519 183800184 752376745 476340963 690120105 224692195 369265609 172329474 236817165 714620385 277843920 296120753 31041086 486359483 19968217 914243289 747907316 175851771 960783675 10196899 146714153 301872233 778192527 531273592 85804052 723537423 805002672 583550209 339352112 276864309 928953013 68971558 465268021 970221668 786919672 584982546 883910940 30823270 697523473 619324205 483802910 984982852 118114523 39797023 847925684 377254470 429404525 436114643 416688280 588269557 835393824 724896368 566838466 143713563 852839823 376783201 69430379 57162688 211052945 726102605 463768844 909224750 931332415 50435358 925180255 567564269 489769972 880607998 786997596 856633287 748644935 375095892 849963067 162008516 4162578 482302666 167548536 920482350 476086382 20258121 240030665 224432781 59591603 576348667 61836072 49234346 110389115 406949447 316632271 5341071 344095390 369573079 13919286 532853124 178544951 970149268 684087830 948993043 75906205 115173287 835469416 380123397 737575786 191338360 476681830 513960801 151097718 375397042 278548104 941593458 227475931 861015101 506638471 57506497 995839218 316378690 920476508 434017814 60819028 521048105 116244800 541106555 419272409 560819357 721122221 120881720 32888987 22454662 30563674 87574742 55405299 335503372 613194306 721975071 26876538 115007642 947564958 866226203 68800264 765872343 617177573 266105364 341068214 710243246 652699345 207975571 859180767 991778630 578849116 828647007 213977114 618420489 756840894 342591363 946366017 51699105 873950576 646410056 709441389 106529013 548442924 808859702 790631158 440841263 261294313 560156695 273943926 897863096 551316450 897068019 972248774 258233657 472140943 14699539 179259902 319701915 114466473 354004993 306947449 354438919 473207082 353737861 932391117 598440678 969641033 382862249 140453078 741586401 761304961 935021237 865566123 974361057 526298506 85947443 791496870 183142927 510957149 867898859 841240160 439246036 724189492 727003879 518872753 46691288 427109510 12926319 104578739 883830790 180643854 468628748 554117823 451184518 39770820 834840712 578523246 360417216 895898337 782535148 806512280 529691487 819209183 812396672 863790935 525226570 400449141 744519373 273112067 609135020 503468702 618137245 943678263 933530604 49855378 181551352 923683530 30488244 918336458 233852456 331970517 154421998 434935552 377429941 110703283 33840321 567244331 97538664 514868475 803691415 971931526 72160332 11907463 462904857 631531145 398955687 919028847 953499696 607082478 757478404 745291533 470707973 675049388 784102443 91335162 984959745 669468926 233908262 696594191 961678797 87009372 355544638 666348388 30816850 166045567 201024506 486649683 296714937 491913568 114964006