1643
121756168 279654794 820768655 334230472 276244673 702050335 906565912 273375857 318597438 3835992 246760910 473310053 138654466 242857455 184825585 612220661 673145770 906890212 993682654 926162254 270774875 779100365 594952607 233461836 920015545 754865373 343380119 880420943 48457737 426508593 569770458 238213944 233814758 932767520 404712993 870545895 822897020 523797631 776259966 360321447 242798081 122783270 880224960 214733588 558951824 100956521 242685050 979957537 283603271 154908490 353617118 382850901 70582142 397022813 22875056 44949815 166895834 94197041 706554961 116257199 404179617 182357973 749821986 263502733 682241605 923270379 671517090 296065402 192342535 95444636 819127514 642041064 19562420 6339546 351658217 304052646 37551689 16758445 602600736 453280846 56798799 264629966 504094653 71733660 425951304 3554786 49544710 412860102 982583589 643790047 991653210 273159840 420683031 17751354 799358930 626383446 544701903 419279543 524570524 455284818 155637907 521351399 881886950 20131427 418088240 375325681 268984503 892426587 16887104 408008124 110649329 860475684 112187330 505148560 228857904 404991521 291153635 580265850 299048877 783600137 99086281 470842086 396946018 298554819 489240970 340961248 268609007 228334077 275107907 156337909 511280369 607599269 605154261 741550115 463726520 205855082 341222283 773257285 533451280 67276551 362743870 271787332 412372665 886427428 635805817 165609694 899400537 969054999 974611935 955742783 635311992 423210906 872474759 896636535 303033248 20028325 367400146 862353217 932624694 104415963 288425190 492519551 563230719 57523612 447873450 376265121 293169634 53576579 815368854 818897478 452252958 642504787 439741775 35947471 895909731 528184715 844074445 630784591 900208413 265542876 509229117 412324251 733067560 664496381 364135837 451218359 557751979 660418643 63323115 544252320 292986782 894250199 940987773 782841180 95409238 136280282 298467527 354033129 655877322 926827997 544952964 647534692 642026525 586850382 673292047 970023169 687240638 274854516 305088571 404302990 569609992 597223923 352821831 818372829 100072430 32550445 547945715 850274971 654119686 979825152 202677382 990670158 957792889 584623513 631250162 710958705 936824238 787792467 422786693 757520758 610263120 698481274 585867382 160462053 67761339 375824376 337788433 102486393 215880601 152404182 212177804 953429802 625432152 678343530 992947780 428907318 929064323 916343862 799726956 910236135 729372994 35775589 242890954 874116426 615134329 151441731 48425972 98064307 384498037 121037853 376819885 660899236 283542774 744752601 771836166 343883781 95189991 2384191 109009901 442882624 742022424 612203086 170236193 477013581 493913383 642935165 550763006 263826582 816473071 602861707 90407166 681183336 161052857 568501691 223230505 713471942 82857939 880550704 228027491 451652030 18764439 198273368 396985100 357927247 149020855 869552363 871747763 910809955 736243715 115962836 473685462 818590275 369746020 930676225 581864098 204898817 840077198 441839836 927630034 107888308 470855605 93542827 164400307 734408225 416583070 313252415 996158527 799824740 188806828 224454842 722640744 928865110 625981175 613795431 677737358 217599197 257200905 423389904 669350189 544638046 734756887 268184851 171178139 527490662 480882981 98473150 550735529 102580185 173159765 536363841 593243792 679994267 689706677 142130429 932521337 900313159 253982743 262249393 36947914 10821306 584225410 265599523 805282162 793392130 403366056 50325514 675111650 660729846 378409452 44355801 333001215 400942431 863695930 814737857 523906715 90457060 257740486 727084685 416394026 92781023 536073904 917064416 275807346 24849090 571553791 333373894 447337154 219532593 936584061 337426185 981525740 453348075 141023619 358690619 654552967 375776644 91830612 784703928 728332976 281800706 78762043 141806625 135912869 486593017 670024122 395712002 555002270 554005029 133997538 554204353 165659074 850287822 731522857 251618714 788740698 528938210 464462072 675597622 55996355 335153485 243993841 225396610 377123258 340957333 769933887 352896546 162028806 694781575 109889154 863071507 389943013 401918375 397793182 521315534 105305754 534668899 710776350 151391759 273851640 665527382 485311914 399342568 984483883 359967309 769636700 634855543 800095268 752582030 862103441 299729587 625484513 479014225 826202831 927812009 932422643 640693654 351531007 852417771 428034498 218478624 363216298 478038440 638177197 209137129 160074440 555180552 961459195 312966831 152052929 425805231 899998048 400794443 480289751 778463711 72678093 240355135 650408927 756202407 195408975 762293780 40592461 826671530 536829263 215469094 352770927 671892978 138429262 524169345 845784885 438345957 78913571 228578150 417895203 493724580 887388807 115420792 281815960 892873822 573480414 234261577 239370672 498699199 422692903 389125186 301387961 682018778 787004861 29087840 6621356 919099471 350323244 668740531 778863010 134875036 179298305 739785461 336878298 237452221 751607663 171292362 93189461 773174918 129287143 111882738 545815005 104638051 552134869 398138644 614483767 257557622 186663876 762639828 227903191 634005441 452953106 385273262 650515399 246325201 480020719 704687164 405654897 466350033 645414663 138571791 931455958 457896672 714470865 988267231 613709460 170000116 404103781 845470401 234220952 289217326 764611718 954207088 345746804 985089475 711606239 304656158 933759261 903575668 275079746 426546825 842825893 168834304 270943149 817054088 861141352 386966293 283500887 760179094 405254308 5768493 228876936 972507101 824681583 228594076 967111602 837585798 814441146 695069138 706993468 21561512 617579539 413165888 719462154 438233748 244565974 336202408 860510447 686778654 916677825 568966063 771576788 156691424 679680725 983759083 307718045 592945463 74205829 640680223 630834481 636418529 590775426 200254917 289878677 253496636 477775228 910290124 853784424 865752111 874196304 694097313 414380313 767605108 297171002 851489365 27402906 143287231 621316047 13578087 627242789 4022825 619310247 735184068 286606201 839699022 606822089 991024629 994063278 630950585 71865044 893535450 34226228 524035315 81046520 326308617 951522887 221452112 412364623 988556175 128820927 208375205 930460787 547241624 111094970 787528601 126751558 47973375 808917840 329644099 52193190 83707875 339846956 83961700 401797800 257614549 520268853 690822467 558795851 662142413 794590740 978820274 76477965 108958003 392396552 156929373 136094231 348187706 530974941 609339496 584052681 649036637 931343879 754064117 892633315 490915840 161323512 586053783 22096363 337545829 885219108 102348861 495543421 106596048 69276698 106753997 409184907 846299420 870343310 21723077 356984922 157926825 813594705 631944509 195478225 972210853 206318199 248368520 853700859 695714555 92801663 325031013 528419769 178240227 312324736 681306740 454856395 901296211 923407473 776150799 755938990 430329057 663935624 635973795 469447980 34881578 324778243 319144607 35005441 697940647 50411829 11975813 779756542 175547212 110741997 542972820 528957879 991742890 49843214 519069206 503832404 45103996 473109407 769194956 255056241 826254121 235313482 723251183 692716685 219838156 375455153 219501679 547179305 418781179 97631675 88311726 436321492 27563569 96629194 308500938 464635966 379524696 258575681 300673756 151266730 797941531 470445409 627808548 260494157 511823010 333256274 432732030 403665897 937258531 480827227 38685185 122986150 201920492 663833778 42682931 176177617 216637269 856505896 271184473 56419326 359733753 623550739 595037177 677641737 329328541 612054060 735254767 99288951 495100674 486677440 273306417 84944549 756981229 38019848 470132244 124612760 451496940 841061683 463261487 720463828 186601446 997995878 323936619 271254240 723251540 234812319 371193507 555642337 999348434 72997507 925163644 788703126 89591996 178202608 275412275 238172480 298487981 200963313 510025303 519566346 702014946 22001327 718465334 571033552 13070184 376991844 639750293 464073729 589585218 786526079 132055228 458885232 851132633 234427947 690054613 861187991 846322284 84101674 269857578 667758813 10105083 677884650 71751971 638970627 982462258 651136583 333380462 971779876 845631971 280044645 918379649 394769171 322967280 264169007 293271337 521280897 194542015 144969502 531938782 849083466 898601679 479072716 439428325 868529609 311990567 522340582 256633332 976315259 928734808 657419859 554368355 972075621 379328708 943489032 473313027 839403754 18833188 38336983 800177827 599435867 595190186 365710847 812124532 159796541 786923676 177225630 386041335 128891972 224098017 130736845 183792961 481960509 665247523 272119280 502549826 769464736 160884985 320267607 31568931 207351099 606636273 178390423 950474972 939246896 467577840 327239318 205810408 90084510 769369217 498324967 775183952 67925859 698688920 724372703 935106511 961454959 110166836 511576245 104753242 574567318 973526465 577303244 407490144 303852223 264948216 907975475 46298844 307880468 571766471 347272026 22390132 191491313 999146047 596856887 135651947 330663820 196032274 866641981 436875315 55695247 628674841 425884092 926902883 597461037 436171782 713882396 109194066 501323840 216355482 903435722 560365797 586239856 220241446 378254823 278444683 790933885 30151255 714314466 348478728 512178848 816585007 769795872 381526953 765804682 878708460 609581382 767033332 335420958 802649112 430088705 33204814 179323914 516068252 44694655 205311560 423193092 485553932 969006222 915461594 151362033 772781368 196057340 778173838 5355605 590986942 520874267 191828308 302223170 634888470 51321633 459072938 252431164 32392576 257932647 127678230 322233898 872957658 88520083 236418169 437032973 57997065 491381449 282678415 624016005 999163198 740922095 56093097 475125435 312753206 734815366 742678212 677396833 321004481 178339569 186707550 721041601 190141459 420246225 383973514 572229829 116914953 699564295 359601931 72693390 114057566 157909557 90064992 15382438 322523798 378386466 894937514 783832018 651966406 979071069 726274549 511397101 221793042 220592037 831776556 778441032 780261695 754242250 218917153 182693306 361905839 651478765 154117466 216781211 839690428 309944771 975976244 936995011 74299647 931318656 232557983 320279771 361371577 481507070 107039853 962063366 512028452 416318763 699180901 589837440 42066912 350235287 178308925 288215614 978249130 166521584 649317998 699572970 389823865 237400082 881718055 401204696 680879660 118683774 596027038 561634854 749370433 699571880 39345841 300949635 788371904 408581862 231722581 482939238 505908766 301122279 831943539 206624980 776286907 491021396 464347131 594051914 304677909 417152299 863549748 226341794 605955811 222509888 765706964 611573417 671268708 155483431 158305775 287234007 486942030 359408711 671591372 551724923 576206232 962099434 904689572 905439067 796206822 259315727 485510760 884334965 232579611 740877853 731187380 210769353 169380681 255075779 709440155 20062571 355783480 114614974 236022637 138812174 105003513 77637224 342644082 732278199 46301429 561251874 278750903 462945842 592301933 519875196 842617483 952949191 380167629 214953974 71882724 822992173 779917854 192307233 45014241 95045511 507108752 724515032 972606578 13580098 645058444 414186279 181458212 784100954 867158384 88218174 923032794 858734249 347177080 467299663 160707886 84164109 226521458 243551357 297402558 284094323 298421620 904268358 838655342 798615918 543645876 815779023 937301235 270417267 118627151 822666596 92521448 481811691 767237318 392680840 772096992 665560623 236518675 529844739 13779536 729285216 806329475 221190561 744073463 101809909 992410866 603042741 130019444 886899552 128642486 574877573 590056523 338551001 290328343 76069903 225534267 224680713 199540553 127015942 855026912 427693081 334246554 764094684 696671132 124920281 393782239 612583995 692018839 372903161 135518535 6485991 740955649 103713724 524396095 119287094 1113987 524778877 740832589 585423873 983933507 311661985 865890500 188654538 886495655 283414650 515334088 181858270 596062027 885670163 385773272 932909245 212744472 275095043 803177407 426715604 647554982 548954652 936316531 181154663 505983511 909989470 85227310 590208134 778912137 592461149 948590394 703401578 337633076 672028342 936540222 518980374 19795518 35780989 712045106 475006062 85503221 317987268 865022682 305283884 881327633 926473742 651415711 59547867 590260651 77842664 433049651 989311108 49803568 765412527 554017363 111160359 635443195 970491990 968031240 938348919 868631049 233498853 690983020 177348082 418588910 146447215 560151787 969522900 482043138 276775191 168112060 888693128 1564846 178680396 137683219 380397233 84908977 40621401 332087613 228705079 44699411 109195334 978164168 18321501 263195242 520548866 534094659 289066450 232674639 739806198 14510158 512280947 847101494 535272574 820865985 31717031 191245359 612685256 342517955 548917209 748338052 155301821 269766161 212815285 249898796 456114303 44124795 90596554 798281007 563359657 997903292 415902216 134053457 492923975 577942726 151154836 461252640 782382313 641146131 740261951 344340849 186656267 933741924 24351757 958170223 668079454 728980776 606167584 785884055 126909251 690376953 114102535 92332824 379739685 724249423 612893145 330348155 308511901 792011847 176553359 764859679 830913554 727203499 455873645 542952173 352367119 157131396 714462351 299496685 809980762 178484321 796921663 862018228 760526527 118910672 114713147 177042063 887459396 930081679 207693925 23659362 986368506 557519288 133717704 343539137 288882822 62396536 41275904 953441836 766142753 538155274 316166139 658781960 646309889 487665652 554400764 232659176 265106056 413765761 587998881 267081175 153507648 515309581 390446136 898598567 259920929 461686597 304400799 837894175 743811389 420557096 529967390 137092452 967315609 724827693 150240522 316722289 666310356 961470206 207029761 377566317 509352262 86668377 15840971 860257280 223683074 996161326 58184341 508039994 643258371 929349461 266302011 202288572 504111035 256661358 645774479 19522880 583795097 206030258 493021749 645057760 930184897 467966769 378562588 195097199 678378745 207183326 891604116 348866606 419946684 93373375 142583076 555426550 695646274 443727082 284508729 805362238 84422588 870733248 20814544 121178632 823579970 116605173 447077532 768559306 943816339 552833162 221926069 239889058 7553199 245388461 639104200 228430122 890217882 970029378 666114837 68228943 495233736 206581455 808317612 698299019 692472208 89292235 577568644 131647704 221282203 324509555 343928564 189680945 502861701 836295949 995190542 550185414 40928194 597529984 679357004 917648377 308186433 948061169 904064558 387168308 594519091 311142702 138269377 2194652 470010075 433748571 709644693 923209828 134918896 44323210 590116288 219685265 101488761 442100533 126582605 631547187 41057522 271013310 109778037 16388869 11937677 53185580 230880710 21812600 106082079 76081498 6438530 254872372 541434324 663349736 571529684 960976035 893845841 7889815 667160794 587987875 363594056 31340254 759119904 46258525 251244240 209589548 123872756 236644583 939096473 321887836 32992948 374103446 596741798 405753904 924485293 713258609 105284575 799528305 335833139 21431375 683900637 231580800 102617571 336724479 433795178 523358169 755038367 155018731 52033004 187974663 592571426 260913295 23179903 788578254 485363450 289454694 304215435 95169732 800361475 839176593 180401273 391661906 895186492 142930600 955128610 655423277 391548367 100227139 587115455 663356445 785787539 974262125 798621890 55066182 669985006 633472776 709267267 748442467 577880596 913774599 260487733 734913518 635492107 230906608 526632353 765403141 70499679 773645082 165030534 645080264 485025366 652415232 175013604 982477714 662849660 805633726 126956331 181960428 194842907 281844969 156856408 487117707 201045002 610763823 406433316 47279177 407957237 359962346 666133073 618837189 677813359 514682636 934944245 978426019 950152623 37054072 605057984 852415538 304265223 539972864 303671365 132581278 206831801 715392054 675352769 838602209 831249051 483941599 5262667 962237575 111968457 401402316 914471345 
463491594 276982352 489991836 52397243 864733766 579168105 222362742 757481207 902823220 271720459 77965183 117827620 582331507 592726635 336457648 656179277 313571711 257257482 714319817 358022117 731632113 883777044 289999864 795746810 213322268 340478655 981973179 191046334 891141707 601280147 198390667 407359483 802986119 844860398 566065686 183501588 890515615 774541344 852448301 438815307 58146353 170530579 157190705 652201678 358057079 753740737 871937033 283477540 180055646 999548960 31287353 197333086 305180769 570525450 113816515 388266047 333228797 786734312 231428937 851097884 162865167 213411753 674328637 900713323 801195083 136499055 451827150 136286471 249094263 674470584 304147327 511777272 361472687 349452440 486862800 908004727 939933359 68523321 120553872 943860070 330802533 97849649 609424866 432068475 234659111 240083445 559557890 368501033 140855171 95384756 289254639 275378506 94904873 432075390 402150007 156108807 113472017 372091138 885383830 33946594 267450672 158059317 45306770 213069807 151571131 512813132 534520555 76717526 318768186 201785809 945868889 921548124 255598473 686212102 193403765 36653574 657797394 445202513 221413832 45017596 784114748 133070345 672995061 391114086 187545906 815741160 167352260 91411522 156495675 972210950 795429713 293383888 440084065 225992537 104097119 321138419 924328516 972576013 414959332 462641156 917316527 488025725 981392611 915021707 535572796 619040128 269434275 877643384 8937625 36852182 477515110 396306255 665398444 196009783 572375436 183233306 301284516 108379229 402805229 357357909 823857097 554632819 202163512 677966026 382858179 207541017 476437247 651113914 732878445 753589822 161422645 729441508 102108529 620917092 586887172 624055679 835870914 191156757 584870879 299528439 449520281 755449090 470319475 910180175 596016366 973592636 566434343 37576611 497948156 391585251 535502744 267013992 408769232 397268667 774987464 965906193 160149909 599311602 476340673 513884491 238660421 827824228 947420600 298281536 553365345 957085984 297349596 916246918 175592747 516399262 843994311 974516474 567167214 253605625 102500299 590567141 213893782 14956824 768921479 187626434 532850762 542248395 943682340 484412678 319115460 36137099 29139028 341970916 404150129 836580185 807775764 643872414 26801516 34716251 40171740 136823698 30704080 608380722 249209449 429083522 219432667 485762112 71231014 325684814 927249136 648960941 153257099 671829051 549495608 567895481 17653409 131583367 492185577 127428514 498782170 431990076 827900765 118544470 870561823 425962421 977657200 241258167 741676409 386682023 153332244 76148528 743505873 38910810 982981925 305040911 602728404 733512081 518548586 150654346 929293817 378825116 752794444 154772507 830299988 684462084 188149032 256767654 491173619 212132364 748317470 87310132 174340105 238170459 457061899 75928348 501552516 979142594 125904552 356148870 717970094 782282365 788986943 368617138 686551664 612334793 353813972 51240079 371938660 45944604 733829809 153051322 952046519 187534214 739395330 372191407 443572230 373994980 166233671 138458377 292901821 437895874 329461401 255287365 361074569 379104265 178132545 841345326 398101873 16329583 813433667 695883528 531356633 508287435 592540111 605722912 811166173 501243944 223315520 752586366 666082707 111761355 851386446 273006744 683115652 732819506 939104731 568950367 972807760 778585743 189219779 242433508 48474935 609993187 163322221 658485559 376583220 239360905 724928727 860574015 813042643 717104416 400860743 931906595 940226688 409416651 464338838 554323828 330958869 496108877 238846338 628698920 944181384 27181862 4088215 181806457 541083616 38390373 760568787 212812985 494355870 94578487 614004273 158369337 937409122 37716366 523382416 38889776 273511981 876310747 109856867 486521257 227386824 481390310 1198198 155396090 352403544 144228974 527195301 894374817 640175849 200682242 254495927 864747412 94755946 136756491 89665465 15920481 264994158 673610056 796587374 206761701 307054504 667204231 148472174 964253764 596917452 23826786 275147392 608770543 261165541 544310004 110169140 861259103 782023527 204411500 13789717 30001764 278139369 256877557 587294913 133730416 340918247 331746140 840881022 437563343 216795247 554406028 173236979 669017447 104863080 831969499 957904162 528303004 947857257 126012146 401659278 252453885 678652820 848451808 714189336 96644280 308468473 794451647 591561610 575109333 665146465 795608851 293404665 545565049 604451632 622499146 219688532 319331117 238595095 372245644 907236155 301115070 789806372 16304092 957716089 10521371 927390718 457084421 886223768 166956480 560047703 219806605 951597925 266588320 400018519 437028928 525358087 629111145 563314240 864294853 312096213 15695023 825818182 250721630 216506955 192786342 103500813 669084549 14326825 12326968 557228010 281698578 832495615 896166990 190454578 471801856 521531965 979476342 490294706 546578588 212493450 651156877 976372045 634442458 528562950 390777757 299699429 505819752 119629338 465444024 422731448 113881474 160802326 498374791 983906909 116792280 125314460 635244579 638635605 688237159 699027090 860241825 709912588 279330115 623769522 556991256 74401754 798283804 325097623 798878999 929231976 267105019 687870669 446709337 212459965 770252494 479932637 79539993 242350671 221266991 571251091 121956279 147592270 716633773 779968994 163357914 665415778 259098734 806358896 120345693 514797573 769714044 794664418 521849759 30065601 797152562 537285764 596426893 948135358 194721079 583035049 599420142 227057436 657110206 477984509 99921786 323290284 801753301 559211140 126042095 199501288 92841089 153961077 270701501 220432868 817766065 926926526 238860631 225649164 237407657 171278030 192307151 899384355 942134479 119273249 456989007 126290921 576319440 772682141 763128868 317970563 891945193 720880580 832855335 948661625 839288125 321516089 165661056 443778335 8905724 816969649 399533331 977860986 175526002 179140678 120753571 373519588 126576585 742242100 637549433 490293860 672309094 707063779 237092100 860770153 586938882 601078163 867914784 363937758 801303320 175463461 604730243 323304757 675208628 153150775 337419813 597632180 389107132 34568645 325683346 845155695 673770250 196466258 851953386 755791622 118551302 97288053 573573794 31810924 837128485 962620521 93216480 268648771 788243291 321163284 742317601 44585955 764789061 92310268 445119675 91553372 518061640 829981631 813041206 813456716 59668532 302379136 334854071 409057994 772734162 355805828 778491318 219195625 14657014 393608885 269394633 142554437 863354507 635344131 48155308 167582193 387121641 619448592 702421117 86107268 727555803 405940700 186066000 325523350 702463093 603232621 44313670 819329828 27411887 531381584 414561359 264167854 747629255 290836633 591325408 803466068 19335108 266906363 35868306 259089801 691200971 689355653 314190038 230320029 470892322 612397696 958206516 46707947 456079047 216096736 162181989 444697387 77978337 19291655 359531827 339660929 228417018 602214881 250522458 900431994 102716238 278822938 870844825 230550068 551082469 169645212 116691990 323722558 310258237 313383052 993135215 99172501 444390232 650233420 72895194 644651205 532470428 336896736 754051453 227070904 4533145 216943894 630938832 205231100 440200603 832096604 352010075 447774444 319810988 396091711 947623194 291792509 771839249 486567126 357280223 916961588 307185580 313971016 318579911 484258910 489757230 678609775 461621889 33458530 319854220 220387369 688565392 158363919 958568209 636876042 615380821 223367656 900918153 177544119 14029723 79477112 284314139 502951815 27597030 4720035 630993884 708048110 165529828 784100159 622701132 76577651 575802803 273266193 984592886 161137659 518242002 300679281 828762334 770223607 255008148 894470083 668011946 508619059 411438148 396091563 544107543 137717995 2257911 70047658 161092156 912183311 27226496 238230203 650009275 497644853 324102362 668689361 992104480 628881423 807275323 931695132 458224822 846313615 530510035 158757873 355188530 921959708 386600222 582298547 303423486 827769222 599202455 481035582 785417538 264659423 743346633 717182185 807659542 68601090 68998391 82178717 42351106 484821427 65136784 848912967 289242611 295088928 794619567 785919424 176662398 479526989 359928613 524375315 233585878 612895860 79476335 838278872 567491330 185403699 588070406 992838329 126376906 286236632 723060999 633661078 923295384 994682738 107681756 303321852 602838308 290633250 37176775 239418134 89213430 941748672 637963204 860638537 128063315 51737977 59183205 790637473 294587847 961983748 848365886 473656262 469076877 906127319 149089647 143900594 109912277 616377296 792806949 92732087 882735865 903628392 549621171 156863474 612539640 140189906 870211054 572022993 688569487 488194779 108932189 976474123 759718757 966967048 323321806 520657221 434433228 694673017 390502482 655907291 533946559 610632711 979122145 148121270 58169230 36517755 72425107 584122927 522554120 290772941 262828916 353717069 149836099 414000492 807202871 452850583 526674763 891956773 541603484 728478021 215989386 430410393 219666308 17154340 434222235 387454649 895667831 681318521 799218308 120871389 128920138 894623103 534869873 402833170 238617604 912921136 280481351 601229947 584836306 645641358 897844230 623357482 992648648 213088660 3252911 186295962 125538410 210611063 361175005 773669975 233948272 841488214 205715382 375827674 212424991 443271512 48740934 898129641 194768771 489760021 438584221 951284466 978360677 585636482 52995909 153019955 870157045 184817229 998548063 221690675 885112039 153066553 93380300 361050632 149267177 489115855 292023305 7919656 966724086 192104793 269597340 608376348 488028546 292563431 966144430 262312881 997043973 453549877 953303728 891931457 620965333 403206858 831399187 853697239 973147689 62310332 151064798 343134368 469354395 946682222 995430760 35120810 657227987 635558862 695429021 485255751 965724500 470560201 300000033 75984234 731070647 567378175 447338043 478962107 255639642 615222326 190359260 481458960 838366996 907347613 521209617 565915374 335516040 552143916 90513934 224355350 594113091 113646055 925134515 290827130 287794863 126071313 635485771 59436701 637474157 120005758 978842248 373762299 887855515 339875028 157845100 398453917 550045548 387820988 43606606 744613449 688434207 826584279 162383269 267659954 76202988 879468760 482393754 924589745 919191771 984681148 158331328 565719207 860658545 84295124 297239569 640645997 827506727 848260515 509269653 470910981 542080504 71068196 860687348 518031271 842659147 239182098 569851272 780574496 13524568 417832775 497818364 124883159 818879388 279622840 878980056 45891315 431262721 888467047 995649796 701335002 977888724 439797201 548816514 893572679 841939857 940668423 9061425 431740780 671149191 83336644 785959611 831649742 745769606 573366569 302954697 989518846 479828181 997859211 931317683 643420775 44929555 633086673 73273417 880507542 377945561 396087376 117224937 258443344 51119985 938591519 793348100 758121220 547876452 281300392 873833495 77039219 830699147 870943970 840681497 219153170 603267442 996575077 124230086 15230068 345120896 599482459 943464105 479684038 371191137 336549407 3332603 123450778 734387269 753795986 495840543 130434983 164210984 417713371 900630559 834961512 212727763 345098362 497662759 499465360 377444630 349512740 171849080 824581393 235558032 92646162 282908580 215969348 690723685 441494500 274732220 741501674 80777044 312391840 163715550 932110051 527794281 668750571 326536313 310605557 184655169 987116417 884939479 150653619 993062586 168175329 987178032 428228435 621253439 587011926 624459170 832586672 492569750 597523088 240162460 678273166 910190141 106706311 29694010 237711743 263862085 919112831 230910089 331751189 553196540 714434581 161732551 778490362 683324949 814716027 462519310 532029623 227892641 369515949 357020010 206109687 888873309 396626550 748167706 331992114 328020689 68942449 457866308 603857460 928901870 60865656 210244417 872749437 559830231 158021788 585954576 904880058 977996356 168728552 988798007 493002598 259961968 264188223 891719905 770809168 676403524 137252187 817016920 144698971 809257442 95387192 538614775 749119746 76750198 536832463 957603624 497726705 153240294 925625678 957577502 61849005 780242319 721744531 955337943 976599699 700888578 742283029 217873684 426892910 127671606 72811253 841484655 728302487 920915678 66828285 970946394 43214178 270553798 402582083 500921881 127874718 749723893 971185711 88710493 886177936 952056079 946918389 19426305 2552888 627821657 213127701 172836091 491837611 71406522 98058637 291707952 145152367 989101596 16743446 811430790 948786791 90655940 951932254 119373895 503439974 485455297 149564345 869146642 681560894 918699548 891669718 768043033 913343284 776123695 550532477 24301639 961584316 446473046 181823713 754713856 270692813 998954955 293410323 28049303 436543747 569998905 625084595 270688644 123261051 990362494 164924226 3987958 343074913 333919264 281633703 696293920 406859964 730437368 356624468 452580035 524549972 530288428 129880855 848820429 746690587 722111039 554538549 961055279 138897125 803430437 201834914 770287011 242701104 584329108 752132876 564559213 573186429 499583985 362233753 947752138 573644372 941369142 159021374 759573857 971203631 496315606 751879298 412545625 115133742 405809529 851890910 59329827 785789735 299046351 968447484 767162456 180999161 282455380 206616153 921635167 822242946 243194778 263682782 805432720 783314178 85612906 479439516 972436142 485377909 150804927 6928115 825875654 827915910 745376289 779082764 152779639 195430980 351618639 58984941 72143373 966026119 2825124 732750061 41635558 338615536 214580310 331442853 449023252 157672512 323278156 792056587 898253797 963699167 349507824 597532907 174267866 931062973 319916476 906832756 519693841 573764890 911308799 5738213 335930968 616429695 43662552 757544857 194002920 148844352 286498553 291218044 163539639 77596565 196939588 686252261 822184629 33691335 947466709 737596956 588345428 291065157 28537198 850504989 220397832 535673802 178724129 52180053 838591118 161720819 982923713 185525556 631902932 812595786 894060644 64609646 776904940 751904598 279979186 202509995 180095716 781104055 157084448 89361267 904866430 674196286 361368905 589800337 543839704 956740770 281559368 150925051 427592660 507003360 379084199 362669012 407966341 573299571 423243431 683479242 401988034 573659555 394991347 871830907 9604893 713742674 556161357 478787752 77434308 602721598 2369536 952785585 109293847 992843657 126003586 201495178 259916179 280357758 5954683 873396890 871585844 42407539 423557513 974770863 774699029 551728183 261152544 400700032 662568872 847427250 198185565 485412156 209781060 512574775 800754113 484103451 267090254 896780014 8177293 987491292 374819504 543864178 546858109 49520003 619084361 677925941 156185094 183163062 533771632 47132308 526260449 210060869 301754124 425665356 853179343 697615319 402532908 27939284 197051231 528315915 936482527 793077553 705877906 908594696 298810382 969282764 666647557 739921956 449713538 437675708 311961228 944391116 396407301 487547241 125983154 291452325 94017022 605805268 154620566 794691241 272500805 117401667 367220175 988488836 921447223 863152998 375058309 288726351 332288208 167025312 903240131 358588101 754802318 776748472 606371366 323748292 830326731 930910542 441690933 501055912 499150017 167481164 745547627 777545249 33362201 577981603 117144295 673831833 161854491 138516196 289503658 898427658 115324009 950773286 539650765 552454514 768852890 829101576 758336661 590834435 353339616 414315549 429532992 742218483 82942542 615635593 224563218 979662188 497300981 971203256 261480061 233163774 87270867 805131642 644612033 504530281 963155364 550258264 140380821 57956743 997482763 302472344 463002272 111871560 470442889 218364213 477199659 773943061 277303944 225348107 62930683 536890169 393043139 666161840 212503245 354656631 115681001 497239945 899217627 777651879 268813603 517202715 575456296 432235000 693816305 217201792 247023458 232393545 653185190 687953056 197276361 792739717 787296493 246246693 611683540 694357511