2088 606988603 519705931 357209841 130560604 101877035 304596197 600165395 986956913 173746414 226131931 652945585 610547992 267107502 829337104 432738326 653182558 369329496 73873864 280605828 495432024 661108758 472490842 648913892 255751344 876051317 961658175 626504577 716729106 557027907 15468931 513597304 287322910 366147050 318055800 473794101 535549913 468076395 628101868 228527211 38487510 632107161 196033179 793329415 19044978 744868891 83719015 574813765 391823359 534107170 247085608 535693017 693731144 339330401 960416791 879940636 305024510 410360172 400506444 62484790 78254983 367635770 115682276 520708856 771464666 81786045 952972955 61660733 674155776 864341418 83160527 394135422 823545305 575208289 482910936 52656776 917902388 200455361 751661998 720377787 364214083 209840809 123960346 855612234 847880578 479063930 561494775 847656246 382940473 907588028 707254599 485277801 680921006 219058294 125169655 262398963 458378741 652975589 740009384 786954286 456838133 64262601 499757727 828376390 211744857 94377733 554611570 478936405 753938960 793600323 213859369 58418935 571360550 34809290 712603803 313522284 154628978 112358918 361428326 794905840 980292383 566838516 229207664 366318232 158224775 727452467 188548275 255721411 294338037 340333660 656273019 681217280 226317770 529725639 397814816 713950654 726756819 691696829 12656375 608239687 208497840 506453710 805523587 975908161 150677821 700507329 976882349 840483696 659175200 669300707 739993037 243393360 151698547 151055294 617452003 582312693 921932065 251473595 19173004 459713320 419439958 619547449 549376308 246869956 767497534 686223321 842827640 193220800 843845043 977195318 31411668 418878828 96518727 696390063 720532538 630711147 104232628 651579767 556326510 148957987 964168178 711084818 639185460 366536333 659830842 657647378 311928230 329185170 754877751 195352908 269505926 901658046 732620539 907394820 440088713 369608853 885555086 487035266 379332973 895459576 104168520 948920969 774861440 642237982 217923694 621163279 734727984 173130720 258974177 597413933 866170830 33380531 653464862 104289386 624827090 689828697 971780788 501503036 479065485 515947486 262271616 713567359 749574535 661062886 915794883 717215245 823000563 749850782 642908740 848182983 812507045 695849688 678587871 856299182 540741101 407541367 834401091 956709811 563178532 862085797 381138293 163756883 510871876 980840571 186881867 436483020 206894979 64597642 92687708 813518152 633658586 803055166 540474562 22599843 732740661 10775650 811094084 4706438 900595322 472688954 396182357 241132827 863213983 47680268 669579806 894961584 85896279 386322968 206450324 214754344 674334048 953110571 870999962 180567015 16766808 108168470 877596923 235106682 676019367 162151206 770569216 972174283 710083384 770300453 670833862 782978131 293874286 1488093 671250386 368793766 442223801 226808649 715102325 439979543 858257647 144851308 608639302 607716917 235601153 850374719 882791984 268020052 52602009 330579413 650475301 811654691 863144404 755910907 947956332 772080093 738360348 512160193 657010329 746499086 477679440 128027722 274539581 686407354 712583971 229154984 275798125 250317431 576247900 190131231 580514315 352824176 308100189 948593899 414202531 948395335 783707323 289492644 98837251 813731914 51287863 236130096 556089809 738268411 809116428 522170668 770574824 540176425 78387170 157211450 324366208 726372098 421121587 944470432 79832321 939573738 68478225 602716380 49022403 877253485 392576742 948491353 163275612 229812754 316189951 263358358 383767994 542670637 665616950 86800708 293391229 677341226 910479483 341346909 449369574 591704569 877398990 612246242 321606806 332172255 544753833 467338199 874747866 500130258 817455191 505048433 448134912 699676606 228442009 329811403 139932469 959050262 295209152 952225430 46606705 543164231 220163337 153378952 636896842 488077879 771932618 434625588 455581271 681917054 271995408 286805949 433519308 816310736 908828240 563977072 533420838 275038071 165324513 223271366 681543787 545537978 811410953 978455570 100823809 615266093 119066108 283419295 310086040 228945077 269222489 894130195 719497218 813914333 908997650 658027652 310040620 749570586 167542445 829286798 846247196 322351324 269465302 219033137 796418900 719795719 865896346 852930650 436883906 405900027 918529680 112194918 999617006 202396609 363733260 92336737 936744441 90224656 846367304 946014651 944794521 916611828 458882341 115827227 833606973 251269520 880024451 239560740 504049115 64209378 710863348 260698042 597385604 459447544 891348669 838979594 48537866 626467955 116127075 51355942 20233493 859310849 212706451 519322138 301453425 541385929 162324754 260056578 925150598 972305287 902398009 167223305 478093562 640593713 246359569 420701830 195273575 836545682 392661944 519206859 312851419 454445344 403894633 395587678 459074196 267338387 499516599 341152517 14355750 331405757 46915662 40008554 879664473 512039260 494074271 424494606 705379102 620107952 798020994 525669501 469284638 585949042 272071676 648399011 619874585 162162953 576062772 246936804 818311866 91078572 868753782 612836819 179603731 200820489 725138771 533984347 33938050 26170118 222012448 128645298 289768951 10758249 598895660 19929788 937104824 211117325 812156326 71422436 863333688 21671670 482251979 938933650 895570669 727645828 461416569 439635240 537909569 833814318 161238927 616009856 852726854 573996311 493815428 645504445 510974726 531642864 483458035 591376494 101138223 709795494 190829003 387105955 786007329 731978241 577458819 864825283 188139227 104378124 923804415 44609861 589104621 488897837 520232600 738355893 693940649 424874608 66134968 132129769 850471794 699776205 873648426 767807689 703964738 805317690 711867126 788803623 333397862 17044390 771541008 905395565 490848008 253191661 260003259 261178816 720910555 850819520 760638029 274954868 203651465 254265910 219867506 868571666 544397109 62741238 601005912 843837714 485681969 288936147 402578300 113079078 951283003 416358277 131884261 201678744 984149156 721846537 765662834 267285403 474759021 72961568 138114822 491646209 434705972 129237813 823516232 149859897 773469955 159509111 30592069 837103482 329822860 536184318 966446781 757844673 203938849 216056676 402737381 230483742 866679978 49495758 4005077 483896424 696633597 437542658 987675135 901581111 232712645 725301020 913765467 332353571 115327147 3494545 536591056 813325004 409046613 480353696 213767860 27002687 219463366 180399992 619909135 290664249 112424505 179324764 806090958 689332549 220565140 292407134 229965411 556156090 428713984 338919679 521958683 547180591 479906023 481452571 925523564 325246121 397414374 315788776 66969467 477643790 42005486 970083043 956847457 310707743 778988228 579452331 375745560 322004720 320783816 511289797 463851866 952966046 801561374 75272189 313604935 884192332 787706201 943596501 357355886 78859625 986969140 267163700 716584768 92815349 917196523 535075475 867019937 64967058 50592289 161945419 272786334 424228305 244784863 37093088 393382461 616438598 157268157 508360889 115592208 487960895 925606929 415159613 939501428 614505405 503866564 444391015 152664434 33935641 534762182 281589608 292297360 490195536 200606631 904311468 514206534 901455839 47324585 511106379 369758939 897937734 172506287 726068301 381575340 152210295 957107887 963911373 708220893 469369376 507316754 108986512 257340649 211775936 996399498 632477870 618653500 170414539 643431223 277320298 612779606 607051084 286225320 356139813 887261840 180367365 441138954 92431453 388252828 382886631 348466478 548203897 105006445 293772422 736659076 929381373 730942216 556283478 864832240 176682732 814514215 502442507 124971283 258491209 896250864 369503605 379553471 614449644 4825836 605840282 569194339 294743355 876926195 804107475 254682514 385942993 10003199 35822754 12481593 437244565 52665960 864120628 111542156 638259278 959485923 746648987 572655954 251336310 596351360 632238765 280940785 167043321 137469851 647445598 237947687 637461201 991124398 421190883 311956331 895124635 123703860 763447867 912099553 477989005 157174400 757288107 907374387 103190497 685600379 532529913 20387405 390737189 272041350 652891264 783760868 895752131 392958287 25529227 797520246 879795414 727583899 583746365 981057782 544679797 588406115 256016985 88617590 618096838 825134132 732526481 545575838 563251155 758704736 315542790 898020039 255098906 287214508 436681095 392567821 282927561 856170895 491960525 811982058 20380330 759049228 100963979 188750881 820187363 722081073 767988662 915202627 660244009 636314860 632111485 268761373 134646072 936457547 115773754 949263854 569630081 955619100 483486495 553063270 328252852 578557053 845524922 707898711 403312918 230526905 181478333 443709883 352368040 261988530 734787306 481451384 302587116 198304695 658382047 272103644 180101667 729234159 838297179 582373477 514367224 780419543 796085962 842894681 796958351 494601360 534961009 939080185 335164092 141685892 5057865 147108183 315737287 400155090 146803455 871331730 640029378 134441639 287298100 615709481 8322646 967098228 600922261 390404075 344926916 467922852 760873760 735413621 147505510 741197678 620985322 527317948 959738401 622693503 723687647 48515250 827494463 890869620 560608917 229684911 918250648 624896930 135294731 991822287 173819123 812832125 549234087 607165306 686510461 551291317 264108226 830508210 164427943 128770058 518219404 938921584 890269076 154844898 630153098 94820139 877048491 860318187 791794399 652901862 539820450 243510353 586245916 235027580 877836344 67874633 831476030 918981933 618293667 382374861 731949838 59616112 501261662 901887814 87841371 490778077 683584277 866057778 159400713 29485735 745813235 370856336 5938982 704311320 742354621 446849053 13316166 31697919 609911404 357590805 736182381 464363392 679414520 89767163 589799457 799283273 765126988 627380794 406936591 162743007 856043785 507393120 587004543 648137416 18711751 82720772 418995861 158839251 560755392 198263925 867642764 689448559 556369045 230044326 165460970 739379916 351546312 895769479 709785047 643020257 364754884 985125700 175716509 390066546 809735189 226621360 938990515 596002375 128366715 599829194 50251909 9813030 689567666 392593510 930811972 508878516 498189056 13776917 300737630 939932911 628977872 201702683 981694663 640632938 410120 913124708 769079023 360765322 762516741 612239240 397486170 84454788 919535430 562248518 356409751 701352522 35730850 47637440 495311514 76248835 926711631 574475542 285167636 194399212 841206408 888401578 239184364 360197627 776611555 239135854 716110100 307815118 512146067 833087156 415192697 35249390 169304393 689981173 695432262 856805930 266211797 328316350 166368371 249059204 498711442 559036923 172407384 600485875 877521362 347991065 18595751 288425349 431290565 735166144 80399926 152407859 118056859 946330616 499574615 744124961 493026350 488174593 47135476 397289224 921040647 846787982 378405676 616683533 865589091 414627429 866649410 883603424 767461416 781140950 523047105 929394404 155224843 470543235 101266521 823025418 304494378 771568989 652791235 305893744 294042879 752362625 814302946 594682302 488309615 267672993 514393126 665290790 938483026 557502535 372554639 460984706 657168334 45660692 121067069 984445700 209702626 140476097 342226843 523265908 301555200 492951679 805735674 795900742 347687688 360659006 76303906 483348333 903210289 314395179 671337669 490750753 692340408 836843773 395491773 228341514 358164227 513438908 490237536 528223805 276084069 73419241 111573697 196117548 2485724 153328117 793656874 38233370 656130535 312600095 187963832 330202317 551992302 796011019 574628134 224098136 924430717 890050225 425567666 448704201 204566125 578360111 67604907 77604831 664472097 16477952 404080900 477409172 423824944 229680500 144521102 986279535 70685895 645497053 940764440 333149941 703184074 743736160 166069335 47897565 92122481 149065140 969901207 621120232 442682655 303302212 892188888 281547000 920620335 495868147 128272935 712127288 795204306 982473096 543581695 602577516 283722040 966542498 114728806 440470794 645145674 247056578 890945163 721278752 565371024 128100573 52245661 195348460 126123276 812417313 152156818 820983071 308761908 295729299 538586145 199816482 718331119 589736191 258033888 997329442 83277873 76254107 737924465 567584814 436308119 842520680 798866820 158791434 367577324 376439396 71657123 697165080 704110408 911348451 99156442 315756539 320300783 564479658 943950184 955861682 811085327 14823830 129379041 592986547 397565381 285351564 921284206 429496487 921070062 426351902 605216648 379255579 412162085 985429525 988376682 485550649 896892687 2291814 774657472 915337571 225481619 526243059 699923436 824567197 766407442 521975909 414518340 756669963 701747112 274211485 27006268 173659972 756900109 525192281 749021735 674233360 759880272 426715644 607682483 854042299 120281821 64722161 915213870 245422335 630499342 549335940 523823701 983529777 613440999 536336948 883704224 918092491 156345135 746091113 421320468 36900846 664854996 108190330 483802535 933994522 32402515 217024341 463868716 53985856 132223844 826092773 921619126 213517498 918958566 706657376 830569679 928042594 739068016 276931295 476078410 512363888 812373629 702874292 921314828 231977162 161371216 587265113 68084344 800904682 482802761 714808399 613727581 553243549 830894156 550079865 477596985 394365761 686375198 128322964 907497932 672707739 407982366 388136759 339777767 204109742 123264063 295172290 787973856 513130303 843582195 193056241 493102160 962490258 216768288 646573256 988320028 835715507 80332818 944079000 727741657 393644096 995381092 526532229 7635332 553294881 351341197 145535405 560464887 15793033 273435452 130021537 60604195 124753771 960744523 452867499 451000923 810162199 889347904 793717711 667447828 657834779 923268335 485112437 140259917 267023951 408257170 701973183 961885587 713893463 976372492 969735062 498250209 583510560 222379090 78696105 118396592 204864609 981252856 101087911 57086757 367125290 644551996 780465733 238650833 676345977 38164354 631390301 921631634 716323265 323571535 418004652 137007359 591021922 685459711 500348111 354261769 178238716 206219442 83440854 400928529 421899241 691307063 393713376 562671020 646403772 71280589 848302361 46470947 806485018 663045124 377623693 301351799 748567067 44949868 228353251 940206475 768790284 577004298 285177028 436812378 490733857 598189805 656879633 178608453 498256671 853734967 560487659 241559452 556179542 167181114 434044784 194531616 945101465 865515007 922611245 852103428 140834815 833352236 750935085 631591228 344455934 178623007 637993246 184410190 290608128 975192107 517469928 862851199 128250264 717181913 683526558 84451985 922371687 620098795 477743959 713419422 31320777 742458897 638320809 311042162 865692701 952602645 705451369 972025638 396063013 352501669 227873927 970973138 355219743 311679031 384072296 263415569 630292086 961107231 880376491 936638233 729029318 599780187 86824447 993651715 129689691 671058622 796860569 735645860 637102315 244659726 601022812 318725359 701823022 74534751 30433881 480392778 983503927 45513079 135501854 543587297 46195457 486403793 202475324 732020953 940705579 783848145 588830423 725380339 62426064 623926655 64441758 713266198 123297414 636966249 600743669 540291820 984399880 876930797 985921595 272873687 90798446 190265959 971230713 707134483 232368875 539378245 233882613 530296746 605183495 202485410 709864477 831930774 587245638 514083810 189970456 999407951 831164684 801409238 378183754 100470822 666431757 311480054 26301735 863110879 377288197 375952751 690567324 196538587 552646855 315847646 853310878 803780736 533765649 685249009 871521600 320780944 658514420 730855065 482451749 604608437 366178286 508049807 461559185 671521559 810490070 993765192 127634476 346218853 323720506 987661480 945867915 936982786 994065334 672793941 491575826 969769128 386461068 433223703 932552705 986630508 143992098 194937099 203048950 734858724 375186029 535024301 481811429 231979000 984892598 900683363 593268612 705183029 814018717 892095341 45710405 583930382 844040797 344037866 292515602 413450815 84341465 737503217 834537734 586566940 850459581 125187769 875240359 77675615 724562426 930858762 480303405 574379256 50607701 673647604 1843815 767534049 477639489 550058700 324439361 288425084 303875924 768911922 270770253 163422045 157518067 197486184 239714921 406750587 360639748 830436933 366131058 37841828 489932335 457350694 252035278 62333110 48058070 288020042 605125592 503068437 981411786 896035963 609022548 724819375 555238529 938378797 321375746 303532843 980909982 557023375 935072506 12342959 798152649 408130053 409389988 477455906 90587221 256256275 868413132 737213397 635390967 866746684 215508836 928865019 303416039 616413344 103364793 263598337 69103504 245296060 96903456 247650667 369323116 532910420 480100221 258457417 864122070 668054882 760208756 641598006 501879713 935035693 606257122 983240159 157948746 361202225 495701892 523250809 374000917 18324223 662803740 919514114 69854369 377353050 815683076 844977133 26059770 620466101 99890845 825624165 777523630 734200280 140796821 877575809 129726779 374009430 558047185 751859377 78573549 849258848 237721007 295713389 497614446 503120457 57242782 555920244 259703738 899409142 473078586 608138598 116124298 828965773 526183293 542614107 750888744 548008475 9598267 668663816 521609161 141508960 84865479 811564181 895180833 229389003 934679024 288116274 316024528 23578203 951468973 389094654 547239972 327331969 417825805 838797510 843931965 114920750 124130642 583540025 382062939 114634461 788405521 134107253 278297364 481345475 158505146 296754837 889052390 936466437 219511073 544826542 945208062 41429820 778220907 405869373 419279177 781220174 604128442 329385217 441689982 750217604 709662645 115332359 422088146 109953482 626360411 282305587 465658828 390014653 562760417 354991771 840211267 30376236 665479073 845515054 180029588 962927546 364650559 694271434 506644353 364188506 555518502 470324239 744054874 961007315 120552742 168043787 228369560 905695229 558670548 887699469 395068459 806661433 714016095 642592827 930194056 515775179 163503891 249746655 156665743 694150299 391157184 798415992 111997192 914127682 917408321 459314740 661675516 490740781 800754910 147930450 539885810 911077420 410940067 773758612 847619896 369902443 319633370 685107098 298569127 224118621 318021609 546158931 497971992 148725941 536825384 541446238 811447831 834130190 774324258 352599350 811117408 421926441 584849654 312840471 352804523 491283805 928257854 97034412 815166472 818913458 116902909 588799848 226914145 503609288 814887729 993148039 513940532 231377612 181419675 748343019 853696272 490005489 872934015 445385571 643509857 380138212 83187867 810636364 335072850 644105770 642654010 785234473 676981568 335348389 866858046 164594857 949657262 173133526 729944055 227867465 532532980 154484716 524447328 302862120 314510658 762073609 94438287 702867349 781808168 548272116 236003691 498015992 399327500 823185788 250235097 250809003 582060409 431365258 488412370 420244367 473308272 927253528 652167740 732833873 536320091 650802862 20248943 604682991 522321596 43603555 594040572 520224013 309768076 549581035 158429134 686689196 658671650 312452721 54344067 861501860 548635326 266283478 790531057 720684806 64624004 502905132 420884242 450295434 295888599 237566412 248171175 239952262 408397079 613808932 201436867 943298232 857127324 891101800 696793445 116584231 784932185 870649522 640909906 223182288 560314337 323283988 975679987 233716138 761552185 894983848 182503859 217355556 294361804 61010338 51563679 502287210 528638441 329112800 534523256 18157537 791509285 678402316 735400809 124779161 499733089 685556972 270033210 146846475 128609251 202961675 142274342 969870130 572459225 760456715 799822494 100776816 638556673 676623023 970399644 574036775 664269865 118085616 420423224 305512737 149216342 856612354 701629031 661665120 344265999 444899181 144837770 902333778 649213724 395587231 173584108 836959963 569462468 719161770 104188496 604459188 505557007 109045759 199315225 385291930 951904200 675432192 258768819 681950546 879187297 420667883 805115880 785151932 62770589 784947953 600362577 641911087 480135268 530359690 319285426 838464450 149241157 209535128 40185910 170592250 347939489 256396391 881279101 149239539 337254749 383660423 979534868 200673309 745288255 432541421 171069138 655090735 602158259 267885463 388378493 115370130 831862541 350230345 209370345 770137534 906307224 97016601 88173308 87455139 797735825 555186181 479321983 683995900 512597753 354091816 526209264 746301606 770135407 9367218 241754791 803125491 207132329 778185230 191330922 821738761 731755884 473383412 345492853 16834141 255829320 577979550 54622157 499487250 112028701 827155184 13286278 875195888 210495292 34760554 349866948 991723408 191331100 256752430 67661317 902214897 109093646 863435217 690882955 751405669 140684644 799563385 119486928 633627649 55500261 590607868 214768015 727350911 579033930 415373918 591534294 199615001 638089057 772348360 277986927 299068052 674689065 128022975 653071062 2624555 984615795 361263490 785353203 515563540 446284357 229830610 788265359 767544962 894295939 339801764 340345288 519403268 875408335 50197890 888962378 129944490 877479550 474838922 701604274 784813131 378115047 967403372 202396770 622572450 864589040 392895124 903369894 774670892 295967575 864060377 378720409 530040990 963708447 807928360 75420666 474759279 640153203 413218574 560763199 22998762 736038463 207514011 724825361 223640060 733263419 184262297 953801968 504700595 664442620 411930157 546542219 381606199 825469078 715726577 990720044 198903528 702068740 440749417 674424096 331877561 144894190 495967435 753504391 371612206 549345410 495186825 300821537 587629732 855086555 552782631 146217805 894494218 478402950 676683164 797671473 914591307 853024120 44963711 285272187 273913069 555274484 5419148 328151311 132276403 205547633 441863112 111055942 77586609 179372147 724732785 791079686 497729368 668634845 320657002 228139715 122243906 791012695 339788343 613922106 560899656 387093609 291123350 757413720 666887510 448964100 192028734 522520533 572392121 575599662 655723210 982604897 365376259 832228490 968678225 74779430 559452887 767015991 518752837 47224303 624132590 117084733 199226370 809555003 93726379 555524497 282535856 666825926 917460693 378216850 540180734 525977554 460403171 210952140 656445055 72689339 548552619 74200570 625139745 760446112 39778796 837995125 573491198 496223036 723575593 522204762 692810534 987512674 542161959 996249354 41279803 395847708 392158282 496551660 959151687 522978581 342797364 369889980 314322769 953740931 762671659 839465475 869899536 374662565 312326094 534175771 303361905 634642873 801639985 128266468 724514540 398998295 914993473 62609479 222933214 218813891 386773141 162380322 410688884 832694709 755438388 180533478 421579795 438519895 348449176 327072562 807591113 142292796 197508704 471334293 11737754 620557399 755938591 25802732 908114780 720515611 910256096 4072243 650296230 297001831 345952671 837914889 80025868 266609862 951009311 298558551 671385477 983164032 418559579 278419173 961401888 46474916 106020914 608145792 98339351 191656323 672306718 598897508 122311678 490516009 63046386 197482719 873622394 738445856 213499278 515154131 61206946 728292271 528003185 582222495 281399610 505039084 516203003 671068890 529408548 582238538 904282496 568837740 574320517 383011412 180575096 462092099 356649365 691853096 973041675 142154837 675660874 32792267 789578564 933444811 388185092 404573515 522224938 949355080 890524711 500037106 901116400 625588936 101199711 314460821 579091550 920619222 862228084 262000931 624838238 795061616 341507646 937739351 609757107 933125555 115167737 600592868 738388562 192202225 369939347 15273076 40068735 68611477 290371375 750882306 362814867 221725978 204077014 800241768 235722460 167545232 876924022 326614027 588602142 363472392 229115263 140241583 230115487 495322342 911351498 984361265 776078780 732531499 92041827 531483478 340900585 615404909 785950355 401365792 462800907 535366324 910193808 966600033 61056180 423696403 678438225 165644061 396536630 496450444 360797245 508544212 131845987 907843429 844610771 810197016 507487821 892711009 64911650 482912087 47696128 813004443 281109881 487293564 726232884 763709537 147779915 137277709 566360149 329617272 217703617 554034449 694129751 86845351 390831855 563342003 354979026 581612339 238618467 955474929 272917465 11553153 537375959 90205499 241254085 86072492 670901194 331593017 181401675 312057120 97993142 808361220 913370791 591157530 977392442 209002852 37717733 837861259 506645395 535396882 988177306 644492177 804706396 483389860 822432019 302301371 819442108 276995728 523413829 953596373 420749793 298706227 485230441 589399277 732504970 847130814 247704523 782219363 472144569 25629428 436455348 806418281 192673072 360277232 491152473 131266056 288796927 481988878 305566746 624736361 666239884 624926542 654359367 817459194 6570813 680434570 502910187 415067330 750625558 167152771 334145351 904481209 567470217 310507583 308172271 456938147 18650487 123207901 745408218 973083789 812348801 240611795 877342039 311896775 395861742 42887016 262452364 219833828 194588466 798777920 728314929 302642039 928017644 283955575 985592273 852907078 986673280 702143094 296801768 124178258 351842944 328456016 984894688 419070885 881758602 898707976 777510514 800336534 633189145 619226362 577364845 344258827 261287367 920280375 57545357 426180249 577501746 490201803 915212155 41659135 665846146 301279106 861616553 953012622 442408144 153957338 964245143 955790603 48154660 151523888 800684937 614907280 683317349 563028595 728353759 248102260 163077677 705750351 777754917 908662645 411934462 831049789 287171874 748357414 447833228 997821323 886143758 626712624 146517622 940633166 221426716 883174977 641393133 15519030 952758044 102244301 512108041 779023646 623180255 992598890 150974657 8575907 740158964 195358880 709100889 288883135 215561516 594113804 91973986 722294884 201047607 779844931 328177946 270854550 643264324 23700906 917585852 8885379 246994370 388905222 906724817 105047608 405179908 340493840 349307037 26890104 272622982 497296782 802664951 215651431 44380320 627575641 708623155 411805337 420374113 687874589 573283071 822166337 395833967 872046728 953653716 248743024 858091264 110112844 609986108 564559684 145650360 285857300 789876416 499006314 465845703 230927495 917118721 167960501 121250782 308834916 322522964 789953924 377149213 996861084 158194678 41958874 525205489 793588523 193620671 115170039 278471269 144673397 884584980 505875151 797547599 643622470 616084024 54816420 105117658 556607153 935157308 528732531 15037798 178769171 961121585 308746949 889791264 760111073 650680556 740404635 837124865 95011295 989316057 68272571 436809387 436629386 952727259 171797455 328840288 563290908 66707323 870490249 608028064 48531080 671927626 149307614 881187130 97907868 418500466 94084643 7053943 748009421 586394394 640936282 584908677 443017657 81425052 675319498 437315133 490332408 917005479 697889107 973729750 112370855 938264864 370700678 400647752 886730998 260698541 932622792 972286652 705858447 982982128 531995958 909267809 496388084 383292825 15448631 416037156 840231156 938500191 571221894 332349672 112303736 473153651 826571711 463825328 733931778 772559083 906450440 386601729 896350137 330921799 532581222 615661960 455170427 998752651 770842523 45257243 225487724 831098904 990093699 896179649 343705537 731239405 111493701 275080827 271286391 750763594 466690037 893423593 569721906 504588074 322729106 4774180 952256546 245636880 409218627 76694513 87067264 570881923 963409259 626729223 867231938 278221922 377679886 254643438 224915237 292352679 310631621 445611221 139393086 163382719 571181308 251060632 748263639 319760205 46105952 573776684 848555970 615283684 935159754 645362000 39497765 58942654 100802226 443399334 75332787 872385317 373930150 640726857 12797220 895719873 991610635 387136036 142769584 427933312 221536007 171223830 936526627 695744927 892938229 42902794 782814052 429474596 546652533 291518534 470647501 401136630 83247431 129178528 310086764 54272230 890213137 233768058 915943551 871531832 947802963 970382123 129984192 839957590 757295457 63892792 969408961 850106672 477218829 714786228 853919402 562225935 871625406 64567064 479521991 665442283 928456397 789035279 29170072 825101529 312447951 853805513 444822528 592478160 528306134 672225357 946653733 566558485 852964192 784014933 80839203 723669545 469353038 400342594 803846155 841885906 228054177 971514766 753154114 320207192 170354055 863067056 233279688 616974296 991473654 922078568 67171878 378450196 742047097 500955525 956904024 782519139 214826467 108801682 576733845 721020257 539499750 701220090 863607741 369679365 277113547 421580619 95385546 413179885 982990176 914679688 385829850 699136828 580141687 823447950 649662200 911030786 501551026 75398337 90412679 496544905 831724007 363984112 272047035 612609157 532858048 305411168 102802853 492882671 230489570 579311569 772425491 158853102 608109138 113552714 795011233 427755518 541225423 499848937 209641228 705532838 557531525 164393256 478174329 153743273 761703621 841835169 22242837 317833718 278992597 287567495 823862084 5646056 540949811 830652352 341941176 439519832 811990018 305175553 89159855 798521042 630115150 367874699 603595583 40450637 775663550 252691105 157326150 562704651 254678703 772633001 910146891 632660986 810123797 724312358 869397635 550557737 860214455 805999718 726493743 827910491 46121737 35057589 885093588 763434144 733154308 131295134 290418140 251293018 964262658 23501572 115920096 435301830 529724418 355016028 312851855 27741166 385445090 639351580 284193397 407916745 810329197 346172149 239911932 675189379 66979261 133358884 439896186 97912646 806836861 882399882 757363747 884394361 404808461 810855120 416362822 82746742 475572144 329240959 867648417 37647388 85205489 615454688 838076547 523699545 118465720 325433583 457126321 975351403 676209873 398514709 25152345 67282312 519927819 866403629 59842432 648442841 833370494 838692696 548839911 641705577 523004126 86238584 611243515 185985504 405012660 97615556 555891124 680427002 89212491 446157172 268088790 649527331 28049629 741897329 945008514 596002432 154498716 332320946 501565491 25355815 561821232 978591448 34213126 467492333 155114416 809113317 298118378 245946687 414440021 978136827 111830628 308642186 869345297 921893517 743385494 706272650 536045156 516942338 509934854 500494990 273200468 656826992 961059342 886566084 477044860 795627097 402249050 52419427 488380754 308094507 525968621 207641853 640964161 422278761 911809028 275072488 403502474 834733275 575165496 884454650 239855401 530152522 372067719 202496084 342985889 468338921 877799942 5146385 373165418 952536797 612276476 18034744 412820512 272808390 844818029 698506391 797627414 726443025 212136978 387862688 508955035 763714212 319006588 996026942 878639890 790047745 765046552 169475418 301103467 419949471 183518563 502753087 927453507 119961790 884253694 925089325 768785746 447117404 522270651 654183235 439496085 968558674 223746002 581175045 27701543 239194750 101909545 98786633 360616010 167147165 840774158 547151264 90077664 528849526 75800839 985879431 430439943 399788788 180251148 744743695 871675360 961991390 236221708 424498381 607995239 593143580 674377118 278275262 448381314 662801881 828467872 715698365 107456458 981007548 431259735 796509399 279026475 272922853 272240821 215321788 622208405 472315460 168986966 952258203 902179135 516288116 48705613 552085958 890441170 687754228 273130628 129548038 343616087 5406524 483440459 157782611 742969105 60241800 812621929 708530428 892839105 665004499 218282863 898984114 363594010 550572215 686406585 287031641 965819752 328190092 919643330 45462618 412317360 125450069 226813707 232892859 244873352 118939368 340504986 72820522 318193583 451147838 555575509 579096024 150401231 593816480 610136304 735927618 946744556 226740260 877294374 168025572 917321779 582998770 632411020 880256746 165645793 305713644 810395191 556482707 928328374 693537912 202071464 243448249 701027661 956776351 679433353 675132313 163230703 581933215 893164698 547369917 216901625 828380333 771289383 950241439 98194809 12975327 387265074 915147414 410772996 513907669 255766185 472500210 351605168 224218536 867233335 306136993 133803819 111251918 109796654 624641143 777238701 504478912 237722815 621281580 424354085 856841444 821854147 364894380 446082567 58188468 116949078 564253347 285232370 198507513 707482855 791772360 34417562 753106708 297492761 192121116 813235706 895819728 88135423 56076067 27984692 843464593 855960472 433227535 421029098 942057407 908342520 349637071 991393655 74128995 453826783 444902179 691041642 240853396 428398197 601225645 189836181 26420547 744460076 184478589 673140726 983520745 649660415 122540619 165359392 358923861 507675965 562510775 681785133 646170582 105892247 131116280 250947536 324548178 109091129 334682117 377532336 884423417 4843197 990906630 722186611 84833152 162851020 35167379 16606814 69429610 35285581 383747046 207066035 946787938 5982690 154692 808127973 560870219 285405696 733093073 19108133 841776264 149161579 868221343 753808260 176806978 238959759 350190233 55441734 659023687 492961832 547453328 480122612 660179556 961454193 240653213 83149414 466204860 233797907 808991315 828369811 436417582 300706117 819268399 529716969 912091834 90000749 724590664 546058601 373928826 51217476 495495632 741023781 138713242 745969715 621414415 361008356 344971505 893744195 20663992 125189045 156877923 634552843 453342497 568453886 504814797 18906537 891025467 312659580 550075893 887835681 335496348 19418565 477824239 575647615 331497686 294058911 49940203 874539624 608288548 327793877 48206735 732717644 239722260 782852259 112523733 42449044 460995820 616666710 149687241 610652317 534998300 962765664 857672818 568248372 155751222 244011511 615786124 426534159 137408612 88920475 71682899 158635935 776199956 327681653 94709202 658989502 757549582 54175356 963252965 602266292 231353750 232169042 366251022 472822125 852032499 146201378 852947739 103447285 190621940 248839710 908990489 215050739 388518901 255942321 755939608 205902475 818469169 350748470 831617458 85901063 608267427 964332317 475914518 614686388 99773940 479523253 582404264 777466303 910458361 647482341 874473163 569024765 680277543 801163365 983852086 682060626 216389052 701878919 140838255 574798050 181027065 575135598 90461264 842740373 486972836 140314234 443461839 452639394 919863206 886851251 789795941 366167093 124986041 228747152 204376433 503135436 433082488 5243951 418645637 906062383 863514859 737593752 54550175 687769781 310448265 57401924 649324054 189836025 220740429 565701098 878373660 7804063 494592410 339499871 39207402 156977186 245270281 583054542 158531252 102607478 930804031 62210034 262105438 689408124 52916318 127313063 241518724 251907988 206415621 809308381 406158343 595492334 407084419 493039373 614127886 211888533 113261149 427981217 765175951 533877056 719038929 777674670 980583203 539513522 780512814 716182906 321382949 517967993 417836450 73783272 487094591 184761386 842277956 670885449 632373548 990305737 449641648 991292696 208522548 502910490 979105048 230425888 354528244 256774215 90958658 222728916 539401477 195665063 644920928 876037253 937030804 261439651 562393812 250017978 129993592 717554024 988190325 904125268 489841900 379342531 548363862 867900544 952488491 607771469 173922148 32856228 859683305 246781379 607081311 288324229 355168089 521128295 28223097 122995614 257374932 646375657 855978645 69366050 434591671 474744531 688019347 387773724 684537571 693629981 979167231 151190303 990589940 409512246 840664732 29510244 910127443 237784093 468404278 552349381 172328714 697552762 466435529 347140446 964747954 215464641 129345988 516130167 732454806 504850440 602615753 770281243 288165713 554363508 511683613 159538734 255153092 751946311 138415614 125182365 940157784 126776219 543427510 214054982 219194083 577591125 397404599 382097641 749662903 957015615 30694300 304177846 361685949 856789381 613770168 789918745 615952426 13314787 316813337 813890068 263113973 843624132 252654482 663758191 396503005 617879953 223492769 223248176 282453564 260910940 735329530 76726088 246316588 179402352 737613500 282720047 937205570 559005732 652005929 915641286 549560026 478771876 687010771 515981861 775299333 308783268 147244511 970995173 554860928 172468647 794948920 145040427 426828155 132889520 856270299 602524321 492236576 624405745 465887883 671591208 165765153 510080101 596879053 401209629 929860742 933633270 845259062 751579850 449357540 775371276 290048647 830511322 46263485 513505685 588051266 489188415 918835632 301272685 170518172 984045713 898581129 697583169 847503530 42571344 4878373 465758631 820546869 329741899 550031035 505370103 435133961 108153851 641544530 77818572 628621317 135849051 808287865 89765817 929422179 509602942 208542703 325045208 155447137 320637399 991742015 900375867 670593035 134170952 644338926 552289090 898494726 554922186 332337788 939575046 767983804 640205420 933657304 986627013 905845973 701130528 252569652 628283373 35095432 883522114 964554524 464154382 701100124 115076099 702610115 606328087 830123637 366749804 412941427 518556877 146769260 114707347 778064240 800646255 644147105 415469623 817915719 157142374 741743867 963609891 122337897 967721151 696058344 380439314 22939341 123998621 697588144 308765590 296720484 349816072 760462507 597959832 179569309 972202782 742932692 770993049 815269707 521706354 83324680 911814418 92278117 995556042 941037455 828728293 12317579 232847564 791671281 135435702 654112757 172679789 548538440 57532809 678438202 648753480 839692664 143188237 723907628 367809038 24399552 998240417 45547849 502213877 408486581 510690723 156643735 660585391 887829830 149488877 989623891 572539289 892419021 807210584 67786451 261791639 21700494 687148767 332400192 26446174 696915121 525689099 211305684 287843082 736533778 408757767 305339090 528753260 688210733 562453120 852129882 726359643 631552270 699490237 541665319 965950035 459492424 194715659 709854026 91104166 9677758 801588488 130534637 932286296 400488710 711233660 823255620 545157013 975617885 140754619 155866829 261513401 426036104 877565016 679383404 894703549 815503578 181825260 669962979 855709769 180831138 754372437 978637300 81563820 149790373 557850157 379137224 240921796 484544849 851681977 582077842 170943852 512662583 124684269 883479600 107230695 425091977 695721053 276627024 739031358 974365115 867392413 518197239 523638052 90697091 606793547 96131040 838354642 824134167 910719639 128173313 101801468 949842439 807156362 743965165 360064731 335753656 927543464 256741471 793632635 527558551 93437555 605826637 767936898 912243991 964722320 95304725 473966303 719050513 143819822 174068383 769180341 131369257 818079909 529581988 384470428 862089832 424983931 808691129 236354567 356200404 579475087 381359211 910260335 712893184 18582142 287783524 57564853 468080029 170055655 428309510 133480785 411673165 134341703 213883623 614358878 273291635 298502247 834531161 330335559 558676296 142964193 118877056 746840052 612331956 352424493 774713558 433496949 258596333 551607619 547194358 310218821 225408191 479421815 315089363 934114919 271260128 314379152 43855528 716771371 383342416 174241508 226603894 107377563 355042354 910987318 265858500 567207322 828189338 27825446 453055057 986670554 692366092 898226444 722734959 474537522 556636758 888066816 719430619 907237943 819414119 759052216 658590812 266196949 686729715 478007025 931437261 375190443 476812682 897646191 700246314 782174209 619610128 664837928 389959208 62367837 799328518 712245145 269679229 332242825 315421582 694329968 587969338 233775684 350808107 509688889 104108029 908508223 215740368 839630249 42616344 347806478 385002906 597812707 896046861 801722359 13868265 633648409 263927825 300104467 403693640 893519887 888174080 766487597 139979041 961500817 604758467 841580779 963218932 581526214 362819885 483277417 984141836 828088338 423404717 854616905 173307457 32859634 266805250 791481845 962764242 929838525 513543575 508646474 525377723 983746199 895650870 418204893 34196972 227249467 805231595 941534327 867196698 544358327 406019178 64339097 218947705 100411819 190518444 550721342 440265258 720645756 767775799 161807277 573817891 34219461 290663073 478703057 536438493 418269110 99076519 685731713 678879079 846121188 853333825 284650469 971602808 683495018 636170184 388731018 723922248 512496700 265026206 706780653 309509047 751322971 261774065 38779625 358896872 925648600 550315338 343827785 400380019 974520502 654539304 948216766 425843661 790867709 156694622 155542585 186557250 512425622 358114547 73646248 747041535 205066260 73310486 717430140 161038076 257899273 404817626 341534856 268031552 51896034 534484650 423280307 345130614 137996165 409055314 51805933 465206357 913402520 507245848 873540333 178731367 709172861 626403263 356931373 507854960 260966540 353311883 541126597 769150122 439395079 646585263 52073342 430570850 120023311 414892852 727895471 54460090 448353008 175609027 796006395 563592407 418550978 412621387 232724579 713509909 442181799 74187711 508688666 990218267 691231748 479052281 848046264 512514306 381749430 682170088 317881238 160347842 56792087 636426083 803298157 394243799 478728356 573641147 762389242 814057245 741464752 991698881 131144120 471090944 968595702 228844456 276177619 751831509 199475950 682250234 937199411 860401429 400390584 375372235 78005686 715604495 538542128 484105397 994350929 831800641 945400838 970584108 293488389 591935808 132505479 349476321 347516350 975369940 978853662 773052678 898462004 54620640 555994809 973612766 479127525 445497882 694311500 27622909 620462834 736238349 444168966 569528576 478593936 968660137 710555452 968929317 561165120 942106805 52815100 120395617 866142788 167024366 616988767 689216327 13873564 288812800 475768290 367814162 431632034 790952490 22523371 7090313 462765566 322296598 607629249 239397353 383563242 156534315 176102194 589805394 640598180 650525555 642574040 913288402 235490836 139073912 926217060 870157213 47637649 579012790 45453584 173934821 572451114 5578411 133849554 680610745 297786731 993017623 924867383 836031337 186274616 543247275 97112644 454855296 555162849 879602257 720434153 562318982 235531237 307698392 353364245 526251369 777523454 511628842 79624353 431297137 7797623 807000794 107827611 875582208 765486709 108381217 980927197 467441892 63252198 48556994 461023797 990189068 476154792 761858083 400600416 967657076 737669593 787729276 752914004 263309027 57223409 825634893 290593416 503965110 436092651 956011797 706612878 830315242 690937181 963974447 169080704 727024334 316972767 843420733 703452093 635135388 10443875 346349165 856360524 937890131 195054608 430832944 273505621 993097249 415465828 307155595 742564453 179728490 29880556 12231975 93912431 386849060 705634374 346637842 140209459 40117423 213226484 69412433 399880268 48981041 274309655 304324865 807029118 718611803 327981296 237203676 314855734 358681156 218834365 824495173 694990870 104504006 576552452 596166625 636590918 161983885 784317151 272280364 275184621 493218355 207519746 516033507 354887746 443759162 346436594 535727184 662840467 535164076 941350123 115004636 40294664 480046544 228186200 136261084 679855379 80759698 482572981 731365815 852163417 96721505 789584296 893515035 44456668 808961998 611273109 17076432 687600675 621873102 821845001 245361388 104609339 509973532 417303131 830508159 480773093 104383145 463647759 669914773 114619596 629711081 574336420 272968158 847522417 829628353 272619766 821451942 364333135 851766815 860243366 808856116 900802985 456013297 255499328 584765936 346958030 544317744 81599926 183101700 951471396 477433198 330985003 918769193 59408380 241159071 310894869 211624671 729484615 267064671 360169860 654595472 103018734 503462350 718420780 952637433 222241932 908334015 962227325 987396883 185371716 979876013 898537775 451305828 613391614 690193492 435654522 695796186 466769124 989913867 83480911 991035074 653073727 751202667 557079330 431568920 327148852 520449897 631959257 823734947 778409940 17697886 599874743 5812010 101760826 618561760 650062662 340694884 907939926 51134234 387360298 330968967 412343581 831597244 59078885 489876484 491889160 422862376 693003169 329724489 931229718 194986426 770244279 965169817 301615614 769361116 413290818 957119596 670124375 178126088 39166639 652178979 275843698 975283700 886257612 461831970 600315302 96688898 506320860 69100954 80134220 975785932 167944622 187956710 861927890 560142412 565469425 711468849 244982627 350772549 766658422 566846421 410451236 406082706 372157234 573100225 375943614 511660671 666412589 608946027 308251213 959871980 756409737 249011441 561588464 242915871 206365169 8860274 125324628 737226258 97944550 68405838 964639661 515688180 635154791 479579989 567182823 134398465 566843096 818284329 634203965 372586952 397171216 336153966 293175827 177163118 174279701 467386805 500040312 945067632 596900842 980869186 590506614 275202377 499601616 710477903 219931451 692669157 158273699 287123831 934321977 877123411 891270830 780543789 305231128 749869120 791418636 87788729 127974012 252404220 219267674 688510740 158221761 22832816 921137785 446531204 698439158 397913586 154322146 365900848 430838888 900378048 366131692 726644195 982632465 759000520 53549258 841568882 181687871 627483327 509359452 745263966 17635010 447424900 319331653 893412356 782348034 396542507 514606151 267441503 764129501 423424212 550218817 483107572 67615103 362555510 740387495 385854441 922274950 53963260 835927920 203293997 749244162 49914210 91208766 398217570 796251310 352527201 348535812 817135646 512523041 36324841 664780873 568997645 35561810 148584474 317519165 61977776 463760585 40111155 807425754 278984032 523201711 752770605 781290274 899480370 200818519 683304934 361830168 600854590 615728887 975807551 322542609 116807433 64774935 996268428 732218470 334396463 319846999 629573428 779880824 142656198 112994259 490471176 309448863 513111695 52984548 815074042 98785087 425741573 983691543 358029930 729653974 302674712 210538185 833489880 816386721 769932321 407749295 348593172 889936438 961578261 112596334 524355400 853454243 166299244 388994477 348707662 884314275 8835008 603720823 711834084 533853759 443694059 888861548 640265049 938094519 370585933 13069819 524871540 635451740 853536112 525102938 910951991 551364878 657809582 667616469 560319328 193795295 313555006 251222597 39028985 767310370 757252968 792480779 847546344 509236556 396285024 972010194 780816689 349156677 776465470 775357501 769400392 212195729 629691311 358772213 947183092 220836109 690638486 944727191 64329626 559259366 655920789 57698420 732629338 593421866 648538812 577910726 327137548 76614447 448320028 513772592 854828724 223037086 487154486 294718520 905410966 949504880 572757065 471656456 786125340 237736631 511644459 190980179 443114152 108201071 551954166 510047820 645802407 873395074 447581257 151159527 351071079 889929816 492261396 791073475 279433755 174967780 384875339 887937742 435618242 162118646 287174076 27907603 815399128 285837453 684783248 752983430 417071094 994596106 461297707 174399138 412207189 75440173 392343400 540378005 888355272 109231143 509649467 521605057 204052840 869149690 203554708 385973389 581936021 192255980 833261570 859986999 862199494 571272442 8505125 38931464 508122408 550234627 206153746 99823120 212591086 519441863 487439285 145891749 883382575 479318342 886275243 559352256 999933835 931350839 619483411 106584762 524622099 417125460 393506855 716925240 528858240 61475658 571863912 612542948 886492407 406663443 304987178 483234280 412377193 241814645 746296025 790508315 187596294 658566711 244739981 828430128 872377100 196191097 314146664 898525155 158622480 765491625 826306404 927067819 650092350 833144601 152271139 907745857 702183395 948086393 952561266 467238490 389308762 870184052 940191356 981511863 191919143 720041450 824962866 357192806 495212042 183519789 154947626 626237455 484570653 636362378 432806559 869406084 986594615 923905569 791723339 149577406 376006945 652909 302939901 843374998 57007249 366230037 655582382 839153943 56402070 70992495 799406756 676301417 137014238 852208116 760060726 313365558 70498701 111780032 606683922 84486573 239925347 590902204 942503681 216894854 967825941 174373800 781137297 442688213 520754706 934313890 585223769 172679082 932656593 331694982 772886939 231115158 269568142 182299989 340888148 283547187 552965351 53508157 932807625 249490393 54254835 164094776 344267028 523367910 67811570 267191884 510417383 193424663 572859706 333093909 759782274 455059772 60094886 738656583 521434289 610000320 493401730 468022935 615873005 666845800 797254752 668339596 44247179 131022961 348629614 243554840 878896246 863503999 893874422 582621935 901451434 955904251 869082845 252295730 53041063 919085678 434168854 702343880 881039324 697984050 374939274 275417085 355843781 625515064 186037627 749320585 716154377 712695695 796975355 56153117 483111399 253609715 303719915 262844159 575912956 442950033 612179187 274693220 981095318 5231781 487234246 807139930 671371219 538347160 571479543 773859797 590355654 443346473 488339082 815556882 925155724 316195674 677432275 804923505 592392918 23885541 326834262 410496018 405088383 737776001 290820711 744986368 271982394 726958360 45157351 801671150 126603896 165693484 613367052 434298101 833795917 568518665 61027930 785082867 314726303 738398987 362448191 70320897 160819970 320670284 331844226 99883408 433148110 29365062 665893304 793314803 939477304 207963577 380049991 162474618 806555395 398098099 843410008 765720667 77100810 963655542 918809539 570655079 207067218 952840833 428267700 398170225 793200766 337624084 589675365 474102940 645265575 739960377 613252977 715712676 275481038 316365244 32333882 670839051 375288516 556306124 110034766 89598567 14106441 886900453 237909289 32573425 577975527 771962818 176300502 916467631 552260004 49793474 4955307 591959076 404232124 571388292 139574755 209235905 498614502 164284723 330398018 756713019 507100842 800300227 9167713 374636073 871465437 158472668 18538511 266883340 182419696 285850233 617363204 52361035 392728530 122518570 465639969 547531197 747177477 611019783 696167947 248376502 689826473 66408305 652623995 220896587 819395108 745254201 472067049 600152883 164829872 452827048 584131933 433448976 632099396 408066632 663509045 626436148 200056668 528341762 995613988 447501141 622508122 419561245 13584648 823121517 664261867 805246987 214223152 285060177 264735935 933686747 927922758 628166047 99539993 294897028 412097583 887971599 66539571 164861606 231426079 212505813 595539858 217019847 425788471 289987266 624733452 676791431 375251036 910234524 218220702 970416823 571280733 788857761 513717397 617136846 556427482 31524563 923786770 282657596 219497896 4993096 379324707 90744732 125834978 606291573 341374999 359125497 458986395 83464782 999784957 658936690 504149556 508335869 896605833 176038704 373818604 256634275 930235974 464199529 107143745 5333709 706956727 190469168 695156286 425023678 872720590 894732964 292834284 485916482 689631379 396116227 44555915 506199822 97872249 548791001 852263059 564537371 451219819 882476921 656055437 199084835 690777090 416432294 453741373 612261570 603929763 769895827 858354622 634209110 306615171 541192770 769379232 555559841 184883414 84288755 608112833 676443229 861827581 711038754 304496465 824329621 214408311 116002246 410264776 512952496 798268495 172338594 294457050 247627776 655925627 751327375 334284787 832374591 132740848 321173627 756651033 39024751 467932128 696720356 864093863 63173834 82647495 808592634 329554914 388927615 813754698 44177763 533812038 983367301 320530536 778611900 225929998 625739066 675154369 987596072 209096810 659927535 672008521 207933883 408009609 645881433 63514447 480797305 346455485 243140572 62343189 87817922 396381491 951342216 491175967 900776469 965505319 705239685 135462119 146974000 937984735 574211216 611776209 198170306 614736388 779334566 521428435 710113587 673198759 167809492 109609646 168452342 55713598 442337382 533854740 452135831 846571627 298066738 316579370 157579270 764169344 343936595 533595730 804953597 463761329 600857283 790540158 976655779 998212979 952366374 125706658 41757669 109357628 350979313 333249938 305890117 846696706 831148768 721233958 436859250 160733305 965874208 917908482 820609690 464714750 419914075 397205416 903848809 582484191 32727663 467924695 387889968 688633865 594779756 155462576 173227409 610996664 236260258 549163276 833324336 253805769 847805972 527906604 84530397 336435185 830395892 113061690 810880069 806546557 448751346 546698220 58973194 293911090 824035062 738585431 80866571 487502421 970964703 317753403 842523361 274497260 562817801 714876329 167977937 216991087 341886256 604771566 790377396 289983130 240038516 141650716 803859128 751970884 110574646 120111630 49033749 74530396 699144619 250813772 153579859 127024951 441939115 81591381 620838331 563265771 283826123 599290192 58802607 466850946 227229221 502732686 499484850 215717897 664449180 921026831 830762304 584048483 453323790 378913457 742340284 520816787 267295307 813710217 337011681 832591849 465816401 213678933 708156659 707530183 437752065 253639223 646758943 388296353 909044981 95846587 547567184 322322142 636779379 793913422 128853948 48973483 502424853 702706232 442905379 676003200 737472307 667435775 812356172 534674264 40440667 592973899 777291314 631544576 310480638 347102087 89846741 961284920 91187419 983734434 352626671 387469804 329672902 508592752 290458504 555285769 178292185 856965281 309301536 545658711 675132004 38016246 614487601 181971494 252624514 154855164 775328293 105637015 782936739 209268748 414064497 234968475 471751634 414107483 984343294 645066225 85895032 690217709 14866129 776226610 243590881 700996395 544916292 409747532 770023635 644890112 678413338 378992551 133939377 766431605 335203717 124362044 818966632 878833623 762959781 436299688 926904869 254188338 546264793 949614957 93143465 558060450 894084181 950091747 250030412 129152221 620903623 356964810 918274539 260942796 224553176 470625920 918845723 120267776 95859870 257248321 572403017 333100171 256615053 265294621 802147630 281621014 550079072 293496144 133326695 489640953 69263273 8380686 810858824 513456825 469723080 95409379 244007040 610227448 290855262 332503618 308518467 778068596 18087369 863047312 510653711 963038737 420103528 862514033 424251342 151403471 236915213 13898651 890333713 520009723 365698521 657448515 761031534 233598286 169563576 688977491 903817981 766209996 855049712 184995934 203991115 879475452 906238856 596527745 108500787 498317257 571137747 67861699 296865237 437720823 130318820 454437414 47459867 217875394 783477509 347902928 251887688 952713285 954355071 377516168 535424226 761746735 891019127 6094034 44959317 803979379 454241754 50062482 283343954 641244331 583523569 701201812 533007392 47726424 367758309 728138960 915217603 199236471 673386611 514091965 938454829 699809158 166220781 805449251 813389991 927255952 734596823 799627371 156501205 234052293 480687800 869919075 271942128 848339635 608039428 323630853 190051786 256831115 845385527 576614102 722788194 723034415 316051750 981571030 589522044 691557716 138565841 294310246 708811454 646724851 506946293 457460510 948884068 261726678 293229641 727850092 374194270 225723371 440997164 395148545 898493981 3220487 493601539 920184955 356505146 759022416 134476722 640957911 863007631 221634178 496086644 953229309 796034053 837835576 941102400 938501454 401528300 528375813 240312226 219395405 399150620 265511128 468035980 579503485 233148519 838274320 291873002 309179947 426152961 59664495 54180105 58211728 693650121 956724871 712307268 186572739 66341181 282735978 499150218 682588862 806245266 905624028 232305076 489997562 54432221 780567562 921559029 968191409 745142012 936138474 874393582 41823474 964068246 176900764 611551755 258759794 293133118 759787823 249517019 609561368 551943671 208554187 487378911 366086043 483216078 804315954 45178035 760050791 709870807 473981526 168508701 106036769 882119250 299771621 355902939 794725904 409566212 113563954 933774499 157877858 422998919 780541992 674639138 412322212 701497992 70159043 345991713 538919090 525439806 308558227 258150581 215292656 951830785 41482764 383234851 131006359 492771568 756206758 489575368 299664489 913676726 155420334 247097625 20520707 612915992 520420573 914014167 678123551 172722198 28543169 109275727 168304447 171549205 937952742 901825059 409249706 379316961 248464294 913671241 401440487 866359603 564515429 103421357 160350420 564304223 968867317 783809581 766435681 831281480 336461154 956011765 420815693 830422343 344374604 377630777 494945410 830096442 576498252 709280353 316874159 843909305 681706685 914888329 692103246 831369884 558795206 34961731 568053133 765689385 862272620 599024893 692570088 760735475 117703644 251142006 108834223 168895414 322680053 381699596 916214040 970531600 226998841 430672571 315527585 126530101 345494500 255368318 40799634 15388451 605891696 597545566 820638185 805094786 701987235 444530359 349084354 200631828 620037686 868445008 287534646 625803664 129483936 228228076 250581808 975978578 559191718 69639873 726271431 737892062 970541458 260695771 752410703 93868263 599769690 534864621 495057526 99875284 141053542 119485134 481858707 506786035 727307746 793101729 298947188 368624089 428516972 993200967 728161777 198847831 456799485 181028897 957271554 85095053 539696573 212548855 103200783 492911490 300549257 164531889 124458706 51293588 426703373 357404258 935906858 580232079 898499786 741071406 488500335 470116569 187157948 632761113 385407425 350973049 576438911 902609142 821317746 472266070 492326245 776449688 812734780 444583300 443530162 128670263 36709076 451683564 743700014 418503934 143970039 319617706 197752401 872255394 926469862 311355075 868849014 617054933 525407499 358930397 469588925 678892113 475364755 487293469 183971408 515389799 389165012 295359269 570598445 547798899 924319140 436490279 547925776 464145544 910893067 932067752 478758649 724996458 439588414 174917572 508621181 772665207 209523450 627921102 65010983 625696745 877881933 403131699 681490915 164206576 507457843 232889065 780676973 234470104 319682543 951723325 862990975 800279838 760852680 119305131 653804112 316196626 850640875 67924302 594188483 475997379 187952622 906078957 613628436 176450645 956543642 246138488 922763313 658235224 354489041 578049169 22822279 72415320 113078939 928080245 420847191 623392731 540878933 121108881 326389326 633551686 98500551 992462225 83176148 772785720 838180104 137169336 887369498 486299951 864761120 77852443 288925263 18525570 667727546 438522998 745723981 535955248 608840797 470777855 625011376 311833863 270744320 380225999 475335404 453726140 871071529 612197118 527207834 71729085 719918373 783175423 866730642 361594423 778671425 101360613 15559585 297615838 653233055 321249823 547382894 166973865 509433063 564687886 423093863 782859179 194081204 5797690 183893837 932140060 471693912 858953803 265600850 922161499 86917563 335096647 710624120 950817450 305011497 895507860 452351802 498356607 608751638 744649963 134381594 846913979 710279694 319726174 831075932 274986112 151338024 363351709 196885992 507597781 166258320 237259713 195657274 488221551 716976335 629970118 418385794 513143947 431824207 418847294 117372442 332002673 664579292 669194714 351821530 286697593 235409481 16863304 268245663 546469165 145553892 824659653 445593213 521966970 635908563 13706186 89583726 215585497 955033191 868246868 624948460 42084078 185255126 145902215 298509891 714433089 862611081 945238733 886900445 465737140 895812664 156452484 439468941 841733550 279620244 674852323 624712100 123357167 116472385 757056671 454015356 569633156 831791934 839194693 234673294 154136691 461843872 482274879 849171307 6138110 753391743 990372426 971886832 749796055 590252482 208587599 561851854 924571682 491883414 974571421 507485966 846070969 773354621 327492936 819281975 997859612 454817308 49710586 487244228 72956748 317020536 624417678 200426685 52188332 346509136 484478293 332752800 150409867 335517240 515916100 479893670 929046266 743520537 898390117 376147930 286574899 620856498 948832489 762986755 716944697 50274331 978324753 158701253 23937995 138624603 633853425 579781257 923866979 735561991 633862673 810968022 553575875 36550309 575521216 542082459 571266901 138282218 301056399 60043581 562839121 409112337 225729517 216473238 574937047 414077149 430979920 453726935 763160832 522770982 196794866 915452471 950393507 502195026 667661223 684402312 588839231 331055096 991466295 325725761 254318377 970420369 347766929 375327504 57459481 564781771 782011695 981782884 67915205 107149410 731909882 274685548 843173452 784913109 158206098 390639860 628220655 519877032 82929522 418281282 960346664 374312376 298654710 354893599 868425589 173581359 379006297 849207469 791037509 42246483 569726539 294295194 339591642 766404466 735346687 200094233 452283653 849210886 684316799 227588590 524251540 50878359 854987350 733517824 921573215 342110724 253067731 641824518 316166183 516949502 666789683 418843067 854158920 343080273 574965999 93679444 799544942 188165710 909427360 147717017 134072735 913865379 505392698 538884498 395273914 204507390 514022363 380938130 103531 441754376 416002429 76135894 623069186 457244119 936313496 737602219 507816040 494286214 328769946 329715782 70937447 746806056 309575628 895894306 320813269 429055085 537688954 718329641 744041717 36176786 12145974 369848736 619353741 149874181 544149445 942576638 659697558 92143015 55857400 909962474 336151158 229255252 309809562 933841641 149906320 32954608 546378155 493766812 663116645 865279977 916020604 956826055 870667936 859716980 868174021 728672664 573894457 608766488 509615338 656441570 541928220 494993898 162581378 192282408 691518271 819016650 110630886 665960056 869621906 274929151 235545047 865842399 720758446 885507330 152499682 106006398 581236426 920058624 547534492 55085810 810326469 71366983 42820600 548645911 601078220 853724633 796341445 992785799 245928887 725261132 608170982 712799664 671379206 753781551 780061783 312904394 262287485 503316519 750720442 827202165 884558179 572596031 385234709 633886641 378777038 901906286 224470245 688402835 993209250 907280831 985399406 76952609 863218240 943342578 940215986 649650106 770808703 414664365 60244901 64117416 71994405 161785039 376372899 891474104 212584078 558955914 203755342 563170050 107565457 580087220 282763764 860589328 974136941 671443457 835697100 234475191 151276618 155336247 528755100 348414401 525013911 987029731 310596523 535606043 820526896 493200795 861000674 860358672 816237413 172118734 131568627 770932461 465942840 464875954 993428393 213353638 847329275 813763461 54657939 670845401 914765871 298257168 29376423 124961686 910411907 358704211 607238014 80040360 935835490 52498723 687484001 495194747 60741646 90726551 519889208 503895620 613982968 472704648 393334798 765805020 927435231 26403464 873227388 538892760 433572478 311547618 496095748 597502103 669959303 689223750 498031436 817460930 485719464 823370089 216601688 796018968 672615914 911437036 145499801 421836199 888176819 942199729 699605055 850360618 641017278 788044246 903792377 460667734 819493612 859811300 448344240 807036200 871214103 201511676 568318865 976116671 235950922 759352050 396449034 873718485 262195438 798996223 912954179 349536340 130988922 909424670 832553779 389417432 667309793 676329626 277840036 995080864 577430225 242812581 843332634 336001287 353269052 898626749 10972615 573242929 585969130 532792717 105239670 506567019 131356534 919819472 314525716 602083634 211887403 584437501 306425584 581229904 612905467 695461122 872054565 692671172 18358946 963876221 793236485 168897383 948293306 520891661 928840294 374708555 545761799 219179084 900055777 754193147 146686321 155788326 218916919 226749052 732356859 18256704 793059632 394629111 481433680 936097062 780543824 30180732 904706656 539065842 918378865 280994088 775996796 831904332 572325142 541412364 676107407 599156717 212776794 453135098 724895242 388902957 607962586 499016353 415479449 73081312 915777179 161559850 223050455 540303099 757776869 644008499 994579983 712652310 653490464 386081079 687788677 304128207 910403154 364701969 909283651 529236210 982247931 260116417 249412233 891367241 84846848 824073177 646165309 119071105 138996327 894451408 598472846 661509362 705186112 328201107 630750185 266035404 507277768 993257946 743746347 531465788 67950564 757862514 517314168 937392651 422669119 671221179 248647647 510133707 101803401 376358043 598128848 248608599 452660369 715319520 285488966 452127775 991385029 548303040 719196885 672190319 599773482 277611005 195026580 560001585 480018277 839188526 173349539 48790212 37332408 283386026 846961211 215367130 544307920 550085022 132676000 160364638 516848071 61985387 1461554 628527377 968758475 14399485 188313823 808666607 600364273 649023655 792062623 396990740 308293055 778592477 258423428 925866689 16414531 40043076 752870972 431000571 989809144 671794867 449140250 665201698 683171858 998217158 751817031 312168147 442907955 324514452 461389448 394591376 817819139 14279161 539554693 937936937 724322793 968433746 631148199 19603471 436581594 188505203 995899772 168863979 473891688 82320685 741357462 167531246 86562315 710257592 365354405 963107369 447929657 926236452 696069547 450774736 931549684 373657512 62860694 635493815 9711920 360244577 303026472 28176754 415799621 820329871 801154944 980629895 80915021 562089404 518315701 250149483 381942321 2771035 213878356 863849951 382515017 980904563 605283445 954769187 124518621 801090406 417905475 320134055 120230088 599284778 888833260 884966787 526284421 583027008 880304343 475648911 854768074 810057630 89527027 109560257 230499547 505890154 474664856 320332813 381943109 280172222 103661499 822977972 905442642 646130938 556838486 972075749 507034922 284073491 829842899 736379321 817280497 569872517 119043184 914424101 350581912 811482753 28661323 946574976 274201833 478101631 941107183 897271500 883435052 833459064 468981797 576646684 115875340 349866376 317192024 357013691 707010428 936709115 853168087 542828217 860547546 285164327 898609195 751221551 348027459 674445817 746302854 499521520 148262620 447088695 89879416 534924932 246037219 501568788 575087494 821843154 62906406 794971702 599533882 305882118 90648760 984070682 935056418 828537250 512848519 643835101 691362118 287560262 280789912 904538208 288711223 50505468 359511552 726802607 436888405 538635367 932695939 498763128 819691156 832887768 258936068 136017365 392938403 392379464 752044562 222897070 471123720 892490311 827684118 905698077 668730219 93811429 321466089 153831959 459253269 827945085 644495544 652926910 183666055 504128590 81933628 257430381 509022036 806586854 180396542 329338748 333145817 440395097 489282943 414260097 323158317 870987738 89571060 247501622 316086159 755283302 383362240 20873527 869167795 197392466 970247274 591204595 502202301 634962856 606923779 379751593 796062932 798197352 488022394 506778612 687804774 277914968 163668977 963373727 967560386 845173023 705350395 945341904 335951948 53223577 557501538 934199366 733470426 776057576 758424354 649675480 325610004 433655765 147597764 669770617 157972791 636085061 870765538 379926599 352699756 845196487 797106287 808897345 309496358 300998503 864440523 845717064 619932767 654650304 856997203 724164993 472139792 831431424 310599145 31831971 860880505 130327376 555827138 219970334 292308903 90246771 736396758 404995704 379190756 163936965 334706251 731936662 756795540 368150223 271396468 424465837 702364491 94203036 848960559 214458454 675898128 488541953 724032834 93167252 674319609 712672653 705332827 253220614 707194787 663866045 382485585 309890605 462536378 551005823 574282235 176453364 315502833 667586297 434069774 865838129 731936713 798200333 711099598 706162083 523840896 540594116 758026091 216635277 729999538 601286336 64017588 482737062 221953143 269099694 957652098 332452617 50156222 144024556 3276286 370097685 980339247 506583406 136963947 566761146 596283401 201387803 276344530 218531307 649838259 864321346 174321943 520678682 322886400 9690684 148982242 338496062 933865431 239905879 770774616 327593629 647158489 739291700 273035031 384516320 668512240 618070854 186277730 82759690 367603519 539141078 264866016 305593557 25632335 407536686 337230906 414333836 585599659 489269482 762863778 274143024 950507568 96104755 193915229 874172996 307549320 795370542 31720171 357191466 369515259 163036480 361036756 674383820 423733022 413466553 402739234 204990683 268914203 279107696 467669292 472092255 806815970 465264074 245246944 984201016 282770784 335316787 227604085 797080538 94924426 444639206 312576270 28424351 486931315 287384020 369185244 415354092 104673647 676863225 171319255 278267185 314777507 685332293 223439891 491516787 829695408 571404167 350897561 92466144 588624939 50960443 527892663 37864070 562481179 640683623 658729419 554112914 32688976 961839898 504405267 366165606 58612817 134243875 321419526 758214883 301125903 802822737 940159221 419429311 446556036 287530864 448334137 637838178 265702732 895293993 33868381 995338857 646204347 415834203 479867008 772158909 893198906 535290197 844125159 975582384 214865094 590857257 259733440 297550024 797417635 427949349 677556050 812729781 234311653 477788186 874670838 163608566 531762312 510052633 509884873 874425527 454794430 969777832 651590232 361748406 807462448 528537055 807130646 584531469 68733106 69041780 31348051 39506460 791702506 904901882 505331092 833731698 854484376 283490543 211742066 994424853 782448985 110054654 918266314 130519505 621923305 550437302 1665409 979170893 422876940 467011960 176907844 806069042 537698740 754176091 845057161 549008639 31682204 691577413 135539949 693711990 481423089 252436448 746340004 356520517 506183347 815105527 82177534 480015506 470836332 929480445 975113892 288770978 438882568 589267729 100404553 973870698 679098741 587983633 60918245 520572931 654096716 98405695 590135497 368555640 477441551 564383810 161501619 957413808 860015376 654895216 869021316 824973487 253324263 612243730 824702605 433199530 864124773 169057008 19500470 929451892 238267329 495066855 696357701 868996804 740604484 630451043 846166085 213849075 131175851 128940139 509409768 71101086 94465874 170353059 279709900 792586825 262023198 404963798 884990036 685331617 117974213 674327556 678290196 123904074 969305740 903377544 127571405 887651441 994914929 795098178 959497633 135077481 21165710 422154343 98261998 791110031 525310039 627667720 297799680 138901004 371486512 639450308 901917723 416206233 590960159 42278349 60771492 92530901 570860563 801908366 487035775 752928298 752129482 363614363 234667455 108394112 659985763 820861990 226928971 774093738 621090053 178378502 414389606 461890797 723073090 905990053 891987032 959799503 740055117 937780948 813465632 476746608 259106117 97836395 753879869 433762342 108211942 686799985 2051793 134085045 497361819 821921241 658689394 631806129 360826449 848716494 447569626 34504155 326679935 699060775 435432439 686086696 91529994 201168138 66962731 817533498 170800543 479305825 594521979 483535909 889017533 20975337 73725986 638990351 104028990 450509929 914278996 309611544 280543735 132046175 853126748 966289629 886057579 310358804 361612825 210184626 852704966 296124638 876811930 202111668 543594102 424794707 511964613 514589042 89172080 707937572 835380729 54341910 38827808 602502016 136196215 591215020 855422393 658131088 232415453 355649028 804943046 180058799 649372329 817654707 450836893 749446264 750997102 392818414 138612653 376342769 566787247 971432743 461012589 304412605 584874009 69343707 110936 771424021 714082916 109195659 121202098 803517084 510349497 390899284 978659194 789372620 994916710 199273760 782708884 122788257 576042031 604716191 135399322 402914977 508735635 441111022 314161427 682583073 297427877 209239594 973030030 222209438 20687787 17378831 645849937 68210829 534212088 643217775 916918333 481845405 351021797 151734865 769250299 174054160 998912729 466510265 883104412 811258634 833035868 344107792 531784513 269899636 929178027 229251874 232802151 459418413 979433158 516186702 790298677 145137284 458307601 777020297 199435627 340421242 654352877 228078795 742567224 91978441 82516010 565097590 373247123 827168149 667781120 365457104 452283090 725976142 28468667 696384263 773734355 873089198 109689320 401045113 542718724 229127353 741905450 54438613 484275241 771365569 229417495 827610309 836077805 548396538 705763813 915529558 589852501 527270138 219797463 941295030 662650416 932122722 163865631 220036219 763409922 612301447 65432332 129632769 367450790 243463416 900577445 597103450 699703666 218989117 909830096 285553798 495470135 83823647 514595430 310118823 495268283 377293627 148136426 844705589 38507556 630069849 257914156 85178660 223424997 443743346 180388150 887933579 646011347 244056654 284025227 6405206 618216986 747837006 219670670 947363497 978508044 249301570 401173608 872911743 551921650 919679998 861791696 749515646 970839939 703806670 201107478 323831665 750187847 891292222 701940109 710374413 356589940 576523238 408297281 489294333 976080741 750318606 554085297 23666605 255939020 218020530 556355070 185575277 136803814 393690621 160919828 30802450 325383385 691693297 126981220 321797354 39128504 581455139 193820159 515129423 46725832 544423007 327702944 795126547 134991807 355581214 989484430 867599246 573824693 241609294 951209724 322012027 774560178 854352339 545766429 685500693 745259196 969050295 274306359 753324469 117283334 266467842 598132332 940140787 213826028 749158618 187460846 478183185 925050999 110547386 46843224 703692295 763197215 676286524 950029794 85203846 753699977 288669098 665153071 683871241 780819174 468029718 489959660 437578283 856972750 106430295 698498643 391334489 576762087 413287861 128791111 584337529 326762029 600719983 593079115 790395267 705720475 275270148 224791090 727963034 914782250 666105554 728750341 395665924 419992205 459890646 743997514 815316666 783583253 304364101 44718865 533342798 211952003 68823435 123326354 107916410 781088210 204494166 489021403 610016911 514181418 979820512 617805260 446348788 193933160 153143659 8307481 121926751 89220108 394499177 191438263 178768262 269113333 993947209 341931289 298039779 666868439 351486871 176214141 57940247 549966599 471322658 65690445 309796884 112637027 240323275 794132108 201364485 481463827 759117634 319406548 213208761 749488325 981614552 770440653 428560844 265417853 264079353 614780693 396243195 214228180 182037630 375816287 282442277 973379623 335812345 227489470 437517647 429646487 931395540 849351311 88517032 753387280 286946533 565156878 109812058 210150376 601151143 190496587 928949440 692618993 819013689 214099673 5639778 511184418 839711255 818338128 100650814 334004714 667940680 669894140 405808266 821110089 270128785 284324506 514552282 571115501 740950715 166535271 943581442 566844622 256567318 897155772 428111919 456328720 80192557 867182469 193524442 716524486 663981834 28633855 741890904 27347723 498776784 951982313 777413009 794351852 363682807 42421973 329917964 449534869 25212913 703749389 356159313 142936812 84539283 23387619 496939704 28006001 306004729 526727963 467248637 456004869 530245777 781265975 838741526 694037351 519847639 774731337 197549347 603860262 342273283 815183514 651115678 153853912 157136074 169947847 789726700 536766405 269396441 17944078 602514370 916677586 568551060 4410488 459898117 439575867 198394075 99036126 51628333 744028379 594586022 9159175 764439692 47905360 49561391 70554677 663084603 380156649 918520891 184434027 855756102 355651649 829142098 519671200 97540539 35880593 97065204 200617508 450019264 639524467 352102600 580448604 128195610 68571548 998848265 794614309 74041189 591679746 223862700 454150503 712702185 689322169 529686900 407126759 115409680 757658241 866733103 71531219 771346494 904145836 262769035 99102781 601203456 956617328 699724186 749549404 570990425 79826186 53441373 797332352 17983038 196760623 160915620 66102227 902442891 936317490 650937223 376241678 743744597 156968891 999205801 25852298 874996337 578293943 32524150 816449257 25009028 914122974 512066256 812177602 282971779 267129359 557005333 456851666 90722947 471971905 178111712 929875440 585808292 648303978 882692709 222809971 475550263 658165158 571979217 885711766 869758653 244884122 168935691 328231003 173108279 986759323 798983949 382140749 954732726 507724422 716640408 424065752 604567464 918198722 404495579 899120215 490565103 644766162 115043488 562604286 840752248 689927534 153120830 578659043 331211301 66257646 113629578 261139438 885809165 922092047 359408742 971334225 944510002 265713230 662676827 567985549 577139778 35055121 392368462 788871097 649053078 336638245 318096682 436018206 442250775 413811382 626445435 527641824 720011922 9594505 613651008 38916711 948452431 565887389 835768486 17035315 910346935 296509802 204897539 609986016 365404273 559991607 817315242 704597765 624922022 192785066 175935712 259896070 559801467 567519668 133462089 421189806 916111025 977075706 721638362 428815413 122374049 851470008 586711921 738505290 208093965 583803467 731735925 252187970 121090284 495784895 236898734 685681862 207202940 768324809 535206545 990858191 217140488 455530366 681258194 58981288 241708786 648132496 343442947 410781587 166200320 774141862 628583782 339840486 971214990 776244081 43145386 801779242 347051232 671669211 523689969 175091352 55842875 575634380 256257606 807439192 343097694 178252363 745843624 623472921 682361406 192551838 490528738 614626331 167470144 107818099 195075798 757286500 791764497 366534674 525502817 485658784 617216715 398506316 765449196 995543889 869353448 445898712 807495201 956657390 678897803 633569393 190135043 386305262 278603479 958208367 22640514 1518920 910285943 536540901 649348257 103545041 454518815 140941186 768188626 17954780 809103962 153353521 433421404 769942188 334357971 8348957 635804018 120623309 44193494 948262394 810563683 659101341 918621649 764407091 33618133 422369026 215702468 249082795 743986343 207174932 772988040 174671171 44835210 380046838 291906441 921416015 461444774 66195673 230867209 517506843 652388992 483748698 670403109 471220712 994326766 126624534 407840010 624419916 711664208 880237111 544152540 107084509 385702549 708047311 212863118 923697324 141500744 199817235 984878702 850675877 230793214 261304691 203453893 162799962 132199706 586621280 231845977 86746355 802528496 316957184 558167795 867345301 826963189 651602257 483528098 53016542 574952781 523287512 716748078 85655022 961465783 741386674 596512519 254704850 720753309 730708407 382683696 802135297 843731218 148267141 917510980 794751932 269155998 595296238 473575129 884184987 775395305 523462370 998798172 821365554 94446752 98035142 604409704 7590944 293815468 756653342 423688135 857993245 241922657 234326135 215219711 829618470 131529824 648235932 129783241 733394404 626224802 187439766 659899565 650675550 337387774 3314038 423314139 934509454 768939818 632585719 77224019 444215492 741354853 753548575 416627736 411215800 667151668 171433797 237117996 421042531 960181230 508371495 216016910 98299090 180276098 28519818 20323156 25606998 211632872 659775987 231599102 826389572 560178963 270819727 287925892 756277263 459898853 649562961 866043755 306953462 967930034 305384887 292718231 878177271 957803844 989132606 46802610 212904564 432266114 589187756 342112851 289110464 635588891 1432827 174507931 320599022 931453579 846932106 196120931 686120708 432930932 452333240 788390238 623412238 753408352 199506233 611589902 962127522 19546293 60929483 301054245 282741198 640686771 649417751 246651884 133646099 219115630 614431940 755728212 662377177 447830513 545495433 904412972 726162859 913405613 594044507 634042526 335086475 153229074 674858919 687443921 770459070 916762841 430524643 194411615 937547208 530393233 987775915 432648563 418154960 587345129 993207514 612805417 114987640 146689045 180376972 469627467 375485782 259288608 729706391 379817154 593714583 622059744 188158893 488932055 843102989 472856702 280715838 533147998 96984710 581365484 667962026 891801459 321066685 480229881 232692677 555811054 197000152 655035884 129099492 639422252 213646628 964649973 622881378 386646602 194197912 205350794 826623946 726822948 746481287 688009970 346510506 169456560 818671858 169937578 803797344 909620305 656865069 715580675 501222861 677837766 203857953 254601354 756275674 198913967 720697184 117068871 121479966 497878444 868661481 36998553 393671176 951283540 875845572 638596103 104106162 256004558 700066851 106472444 921171625 726132829 248472760 595020668 263726723 590191836 583139263 628566999 640336804 784934482 767427605 93047837 1683952 769884734 87330187 69045473 313983224 950379656 522992544 154105563 744936122 625107671 742111377 348410264 475539843 144000584 240285845 272848285 766604359 533803998 152914196 75243939 349687843 516213365 796628462 169993852 739591829 168940361 642247404 877269678 259813694 968043575 780570121 357982866 574044443 570879573 75990503 813421524 8258785 471109588 42188499 394652942 148396610 142418437 17064518 490555723 43242886 262328849 785668835 371818558 495569010 625002118 399569792 346622189 430631826 59676144 361259863 259697716 474745612 220351474 57536544 582776273 159925183 634923550 658441531 340724058 813357733 991001214 286157072 661973384 696805277 211958404 977789188 770828609 439228756 677774517 41863803 653130669 129032214 254769159 127146833 740951299 893293326 319290927 124172226 185672590 850487751 221705968 13111958 785226404 227950951 697715753 239264717 263766100 568919876 843120853 30629007 916385897 438952704 336860027 772438682 675067974 176403347 606566302 185559186 752215450 470937759 580113470 54098936 388529840 374357362 759879518 540289843 524098257 831647702 164506865 949933369 689070997 281231956 901217533 553732294 577611644 980075244 756100611 375341615 499523508 174344780 656342738 795230027 342154649 221803754 919423269 548482488 588968941 981011465 513256243 761497494 790847804 600975526 862371508 367737330 221259773 941688167 297431175 172899825 693249212 387580179 764407310 400029625 702809099 587280300 24610988 182984528 865832833 309957462 340495641 308360361 818661421 668579493 977301930 349831957 989185245 12331844 558436986 268824741 940364698 968768172 683549762 410764431 795237376 391623282 152281106 889457914 731437339 780683424 354245865 956078555 167436752 791082229 392211620 885801004 219658580 582039763 662164025 517039787 798378483 160253306 941653561 755536619 172219631 106705726 728158262 224736401 440838972 667015164 773771338 704803773 778475909 899541483 273246668 224637262 603631676 583640134 719445033 15385462 130095056 493942596 966758546 248552536 95408307 143540009 851401839 345467955 509305816 521053652 935045224 60690362 726044034 587840636 185469548 219710315 451631302 860424929 775223995 922887162 268698262 459289283 791476980 851726361 826510291 491959529 404090681 758224270 812775863 746912444 184844308 929663537 952225386 86298783 450001511 46278751 266437445 349091144 626557336 871694959 243028241 494032329 374749737 999113552 983313271 157186201 706028205 350786383 543034024 489018957 713474572 955918097 488889085 58955182 607425747 933682701 229426952 435153672 278145811 509863601 971858191 993352566 701686233 607736754 995174293 214610253 246781331 838668187 210063386 10989871 445699390 227526810 630067689 375746529 115516412 322948374 95080535 878145747 670343095 372138114 309083207 242941756 118198272 870112485 179621785 393373438 838753717 384768494 204096468 927469651 609008009 391179429 440920265 118206475 826705146 997391658 76498751 859748069 789971870 462147813 526810755 153439555 617923646 220700017 312357553 172456896 934422088 532727249 934908279 684645105 412667086 372656922 71406393 563982831 564176029 790847033 277191116 617704726 108071738 590207368 251455300 1867945 405054069 117094169 827994080 207845235 385490649 140352396 193025240 766351116 356713816 226607726 668477545 803085521 110555921 463632559 2089405 704068865 94890499 975501566 41691551 401279 950461798 278999451 29025997 708619801 530600840 857658674 78939666 29670109 391739851 445578164 512465040 582109050 958377704 799188694 608829627 526392613 401904493 882479074 327136782 8407266 56140112 632431191 341402074 187682451 753011499 362907159 620395243 593359689 682487624 139285228 481071937 814868011 40229858 745966658 537973151 301087433 838514846 821943806 731362433 231914018 150089321 608275758 408308440 938255964 43048222 438016636 116023120 920520602 848024441 848604785 597898022 509186203 209189367 833689561 901986873 127630752 266133430 833838672 779545700 371556283 931730107 866941842 38234738 727607964 694817979 548241341 208796891 492654833 774039651 426843251 866108338 373837405 67385588 537933129 383249224 224850668 250928504 98653058 530386242 424504316 467089398 833020132 116153369 909727500 627825374 700440389 803192624 38882699 885808705 611747344 626060361 761827335 881512794 532578164 744138193 265117706 969076760 515867072 781166967 150268062 334822609 698201219 555549266 534873448 798062836 766314436 817079228 567282636 722917318 716291932 147186747 212496038 475332423 611078004 896629563 23449942 900048917 125133950 801967752 161157191 593848842 7633395 676795360 430217969 109692880 882757948 761760618 704639888 604473747 579334975 191675721 759347320 30544599 201891184 313597200 631486604 301083985 371916760 74298339 635438257 303199144 660935057 717926628 661200954 299731728 380432487 666325827 59324202 291381216 663565220 892917986 629203054 400940291 131053517 187370036 229881991 35860009 718087847 879518045 373457140 966087386 105597823 418989836 725510525 223384735 789135942 102020676 715580733 639304533 866055205 324444814 205371832 974651997 250267917 625322247 623477019 421409619 40149293 380659280 182740545 481512020 237544735 428032558 150393541 820858899 265533855 949082317 859146484 932861181 263507455 138673770 469935494 279030140 107423427 561364517 196180661 1231253 615329072 460148090 564851870 350305686 843908404 901634523 794922895 536024349 49010659 613461164 603856892 263247973 817998400 820894039 86476039 942131120 924663734 636982018 738814144 669304562 5250334 549672381 846131830 201223076 351900049 177606444 760633264 373471184 597227455 335817131 611903887 864584328 124510833 275092834 828911275 612240121 673536614 359257039 567853424 749509791 438845590 662459387 743856400 843693372 764347251 677451719 633675071 303443375 621859161 563826846 974045065 22940697 506388886 281272579 950052765 828745847 935605972 733139590 861698596 192634657 774766636 340127256 613913898 824967152 481794758 916552489 248712952 255038336 946623721 499694863 425416188 765304683 387365423 39661740 881403425 405938077 789023150 640709988 341443557 874821193 322631839 478346341 305044473 231124862 112871321 846770721 893698378 64646257 329549873 800626947 468985725 916751253 521813012 756042371 257023228 355957895 867930927 195707392 699450226 546224902 913492126 756630055 847173850 265355110 819848060 553556628 881864208 703684644 328185518 859404749 383617400 757379735 259247263 400116157 264418533 831074472 885684007 770738043 998039181 999256496 78593748 747274092 873113745 705062548 490212821 873256037 855011213 903574144 634321755 953269649 460029744 260082616 500748809 194237583 531519542 272654697 856203980 962580392 615563391 681804484 714940093 805649523 590624335 230120732 617574397 653654105 528115991 995548640 517521287 997304713 518021604 361046817 488047271 150193425 797538810 712566300 573423818 85451973 412386929 188877605 89297952 921018836 272453401 554786991 339537499 360258333 79684205 744760067 661053250 580194774 341056799 428360288 149687329 357489849 30214866 465647016 588657654 896642713 615159559 519801544 230068591 817974654 45802533 202918234 421808632 698178027 109703081 636950844 946733283 51641815 958035168 361586223 694660307 151133390 904338467 392976659 374975331 261874935 257895462 514936625 142009495 289217748 635365160 480884361 611731637 742150942 960421994 712030850 629961370 2553500 491136198 301450892 605224634 904353583 375843450 454437739 426566900 979251644 732087982 198115986 514805156 123813554 480968442 221044456 581441289 560788478 333118974 543136496 224881681 732517357 116821096 195984318 682074843 484796521 809918076 195818580 785709633 209283896 797765405 988374104 325499349 505924746 577891459 578193927 840014034 601949438 328556251 378300651 183299196 700060927 268299660 955969151 722962264 350765810 593969894 326802400 607676925 129976401 348760742 931076153 960278077 871631652 843386251 635468894 302342056 916245633 331152475 442658344 374211034 874904158 962126829 97364353 6335310 428173380 93228378 141813945 658285595 440396721 216651597 272017773 490505271 507376648 429652630 927846779 458143903 443098820 564095843 383276780 497598604 104901544 644297590 417914544 239843009 591090627 851368492 999592978 261234513 182927958 783050115 188517123 670514761 475076679 132529357 25597492 300182244 570174652 612404947 440457449 981090447 635543582 910515177 707738523 509872931 676766725 572598349 302804491 569484456 606771463 954032558 515684511 611909607 973675175 325708386 451974302 48545838 832646313 151069963 924827721 919311819 264709073 666268116 39030835 83989773 443016397 852834613 195676087 597165280 669090236 925558785 604913933 684895897 559448512 250357317 906059700 218474489 934954174 178820539 879687941 402309768 523690498 881430768 124938159 79687253 971210949 978621382 329185658 26842359 688693110 978394231 846962244 215427048 202189963 899150323 452499624 887577521 648321437 292578979 310999028 5506679 873638906 122860335 696935969 985543336 889730632 198421202 243354708 197731732 210381135 640636530 444974928 317755919 946085477 136941384 578029398 247336470 915227489 244931141 207697009 928511307 592105021 256445343 367061280 755807312 599515910 890521869 512768583 140420805 556982800 447043397 130110540 127511807 144824858 242339989 417126812 496501707 558367969 730184915 564413710 409391413 896292606 918319334 539695677 551086846 831652427 565519728 221670364 346097036 867238116 428073386 438229286 305923811 929342145 514031632 452015770 250827510 891748522 231024065 159935249 998503137 652503591 399215803 509633509 459397263 64480603 712423552 312348713 851885943 719415021 285968063 783450411 976588660 917772168 254488696 500020321 792259218 621425563 474650418 588299050 623922615 608628932 775617569 581451933 761867810 314140028 181678429 192183165 654845128 849818875 321643556 411555972 984657207 125904873 184008099 818005415 462698680 880849716 778006012 70170005 215029418 990805445 925327620 694342331 410247387 111513350 629152808 467922909 601014141 159447235 522188728 577641020 322508917 744668965 246816448 421121475 55887139 156142907 642807733 360984959 148930195 779035079 228230551 598353702 669792099 758597516 779284274 972954642 420204683 918800009 333721669 186035735 583451118 431562493 883130311 605480000 373459002 887924668 770167316 862979442 918672259 986657475 280191807 391593165 303535178 312685670 466753537 586528980 40465605 91423151 400036649 509354236 661906761 253196366 157122626 832102403 193516056 342592748 205811850 829905466 895236966 192754678 142452663 918923899 315797355 620401819 824786135 431784029 360780365 131450226 294295245 229263383 14088534 437222082 690923139 999614167 641069669 612912956 676819253 462302563 742583333 5190078 571307814 925777375 379868109 623686440 728359228 803359762 986480476 746948850 613586585 100310648 408371195 328250987 190136995 566116194 361993526 742146553 508338613 980618404 942938918 777859314 829254928 892931628 720538977 629646046 237498432 347154025 717553500 879903446 111224438 392707279 566835966 108816978 497085500 873151332 760225362 683327543 892866467 77503635 796063893 612621580 911167427 947964650 370006062 874523480 635328787 447649563 408533056 874487151 510158286 479869110 50921383 579174570 747931920 166285772 900363695 145140151 558249908 382956094 27130006 86394731 66940360 699013102 220742772 425544939 492790788 271621014 100031153 961429397 958774719 81170324 172070781 641309339 757294963 862699565 849634617 757097032 947126792 914501250 371917363 813041502 511268594 445951521 265951746 443907977 44612665 493556278 27334633 393086516 893588007 401998861 398001221 251679128 545133988 9292180 909313154 727673842 754243141 834614661 801945849 986905495 400830454 303389901 897887813 625620404 418324033 599392237 25062103 176471652 591629864 78560909 260652856 543203646 823074335 916681748 208113611 384892482 431596903 997261028 907922031 521604073 787118444 565425651 193302010 142132250 581791034 155950054 487802724 575660310 625701342 6148752 546301062 910607457 369963769 790564107 259911630 889143598 584795751 979582764 150505777 856287951 286401706 448033948 368177181 931052479 283619391 157035463 539605592 151867493 460052076 244156419 624296823 25174281 676827860 655031061 297153752 577428936 515863292 544186437 480179606 236016618 683576491 108946354 26035032 845315091 759443005 691307714 239383675 423044809 767096277 383245629 557602857 708891077 469155077 653933341 704810405 593689139 65232906 570771683 39535290 384214383 36923022 152953646 877869876 832392028 211538073 614113427 213002625 989347136 140170618 65951805 935914878 69336509 398268589 372684215 877081351 142517226 340115368 876627172 61894256 690680798 653341143 666818124 497240100 503704506 192931685 800236001 354564905 399615989 900461611 271414335 858347229 27113622 422014464 70231120 723867751 280196112 791609009 530165918 266975046 18239360 666440374 999641940 771484981 44066097 120363303 195708847 238972756 222936954 21295804 572626695 394814531 867369739 355480585 479626627 423348628 652448271 527993072 720873737 763831281 350923998 852997310 721779569 941887566 568621605 742379753 209688696 901656256 554247065 477465006 208977953 373870394 141076998 826557862 286615938 603737286 79639454 56733035 60687565 473446596 654978738 87249319 437083165 144692696 347483505 239176231 424570146 257410543 904998504 593482574 15303558 650801227 301328738 796830879 724255255 60784585 532623314 50250959 443221278 912711638 412593828 277199679 835815386 901708309 146476185 604706234 451098649 295073671 312812553 253023538 108569285 199394021 380412020 682401963 847965133 844350770 444923350 810432815 35767357 685457319 876114835 370400085 197625814 882099282 241662039 504725639 450159639 805379052 22315464 854349447 536583484 667253835 474044864 367882526 128549490 652532600 610383238 687693430 591587426 985014641 456420831 290553841 823206672 925519185 732644753 519821357 73415783 396840273 890049702 878959197 817793241 608434372 961693145 939793282 41037591 312060927 1660845 506250134 789884000 509097506 734060712 867059624 37517912 597610502 929353568 70003608 311719025 369710751 592970213 457987394 232834630 659084567 177965698 929265395 608961173 926049552 220966740 17268931 212250648 766293536 786591202 898788032 744839416 494524423 554020928 26030342 841236196 126214073 255653051 321211629 913060433 557396402 789923389 478730857 773635392 141103651 91019249 369960290 950440091 343402291 104836076 134865220 646640471 256601228 460356465 903514492 322545921 312655476 183565838 360836995 382900018 482700885 777086844 190610909 840435889 750974986 874937154 787355996 487130632 703752221 560931331 111900072 604498435 56802581 612280313 449953081 171656048 513284354 583185883 496300258 6226964 43222459 563400252 654817848 647895144 112680455 229679518 675137230 457364504 40435525 363023414 46177780 362452712 956418865 32343602 662488868 903903100 329673092 584322331 921069238 684968638 922356751 156976028 816143267 205849749 926093306 721835118 690741452 575850109 904094302 268481924 726933794 893541757 873211197 539391259 867025766 176043207 445072909 167490123 707110597 453784073 841784634 404182627 279756277 622799300 633024546 89437863 566901958 356488744 867320392 40764227 956208193 22069725 417143701 589100279 574588927 112042832 823169734 650269344 509685016 422772617 923117577 588862628 197348072 815093508 509806867 221258910 770107767 133637108 770755874 383166982 317779635 622444789 905172278 696150887 173177146 271456922 442646194 952956260 344199749 782505570 247070916 368219014 665376812 240677636 35970153 464001490 35333901 895974657 2010954 505432432 219637723 267181827 27497651 60920181 731017518 642105760 408138717 68789279 851976566 177597213 318814992 13580138 452588910 763516932 661000664 888267740 867060061 349587578 958448138 511329966 749222936 217033483 887228797 805941400 437061760 330137310 863769741 411680691 47792331 120495727 991268094 804464943 232071088 176192642 681559475 196041429 88844766 110849097 442456827 559087473 327905431 906384957 473315397 530022107 66785589 736745529 372835135 263819593 642355620 216198344 332911737 464186889 547064121 530001895 547187638 35303996 912265606 92918599 12925724 210362923 23083928 486363726 181618068 363626620 352547311 128440380 567548081 485421917 203095257 101921610 69520934 996295284 341091387 797987225 264287282 942787234 220405393 47223991 901043750 298013298 589808016 409383638 103602878 349421848 846918349 226363304 217845851 852462123 965571619 374802207 580547171 666268873 151505960 724224565 314609232 309331594 687162295 123332229 757569273 771239372 45278986 517173346 144591620 698175355 948756208 851592495 371702226 447012342 984410722 596022542 499263571 31523735 718591525 321849267 444565335 909639932 565848915 218770626 982927715 35381143 73709946 350992531 179820865 824014709 380296841 634701943 930782112 387869343 48801550 981353542 56670675 207360162 642834293 946754890 769476708 860316873 270490290 968177133 453560889 61324724 999625163 166308573 690251382 594602559 5644720 751867310 346887261 127308602 880832003 613653625 767103488 828005148 537164018 230408000 285859275 525586100 550734064 975415409 836459207 108005903 273336172 875433413 538699785 387887264 813495959 225710527 196448733 354932859 821732761 985041083 97478467 701336502 835219819 811038087 668309431 265653338 35083363 493996037 537819054 883931248 233671653 611479790 672748651 955552811 939834590 131477385 395474055 52520395 650706428 666687306 941663879 646939547 350381065 115135244 633215007 175019224 17847524 986602454 334287748 24415232 554397392 304529843 103011712 617389712 200814289 888439905 281829610 901047223 501877652 523150210 111042931 461526135 257178831 157860627 387719670 529949055 305115331 738709000 239207579 697751407 577149145 379729387 603021104 280457221 467105560 857128417 234246649 920629341 314398994 940617016 151382622 327988495 626012157 250144648 492376886 459562801 729805792 534464375 972959162 860577029 443663371 255489316 185772681 723844119 358801307 787395247 857146031 364682515 873663737 181914374 287194911 275336484 884052709 598771501 857882424 809502697 211791829 12359487 35855474 784191804 60966962 47159564 249242979 730451270 923913494 81925400 594157996 635797929 115738207 319818949 566265342 659579769 696555790 523502 751951446 901248812 110507854 585050703 139052904 884268611 8077305 588702646 149254391 441343639 119253815 168499396 490072600 821514443 868658218 190164975 408362383 652458521 803242834 903511459 358080600 785636794 754640935 350258385 216316575 705042477 343940331 951901887 601820327 487490261 33685131 792235965 586992469 826096483 455203608 229046715 911620091 156819908 393499944 696011552 725367724 119010100 649478010 892074793 3568796 258954791 940380436 255128167 798511925 108132633 389504801 708254387 107257633 530815817 39108316 606164844 564456126 840139942 270540294 718225459 314619422 155261806 819942445 137110218 154861751 486138992 275123447 767496186 927605048 702504541 516826140 757655255 659066940 342933728 520230873 758589619 52539523 888935189 506033216 95982150 223960605 262784527 634657850 378413856 288757898 170709151 606887377 155402465 424439089 372012526 990840000 584913243 129456564 956743878 497598237 790576340 50674336 435439883 343341418 122330679 749782060 198026116 122830322 295937224 438611876 461713630 995303901 578652031 68292640 925296948 772278212 23235753 88352209 65906288 398342510 303637425 88919255 50847302 803332861 654184259 873043607 804272350 995589522 865006154 895308503 457805000 672423748 782545293 546988634 425320509 421701419 623587260 16685864 852777897 533678714 111473675 525157286 405458234 98553271 564997547 518971092 309718755 706891035 571514842 501547640 913535929 529718256 160771494 774843817 551552513 92543308 149922377 381066617 380300241 166104139 114091706 762853673 921854650 592534075 327297759 364303780 217124786 672099126 935565923 424312082 520442061 818328348 225258449 189634408 802750303 244601271 788053549 431000217 168020033 750834427 59485659 621334741 923023736 7842690 482448440 399452147 170154930 570726063 177558518 395348119 883148218 391717754 605249328 66009616 31919087 657854483 400228422 822282699 746669588 697475837 756812225 151057632 912599327 172133553 66696749 39060621 266665539 599224795 296701269 109785406 803326770 222584145 248983095 427531340 487317309 716809233 933950088 203363457 35703897 2209327 380473005 330533790 913027373 214478692 143213842 840669105 833106771 906516889 496765984 970683711 324944892 428016123 224515727 148375674 728478685 948818195 798808100 990055834 105664117 185349544 799648088 529588521 82166803 968441148 672060135 578944497 14445711 556586101 175992252 24818340 590319952 19558370 696189820 786016408 721852586 879263639 144515024 924676111 281748256 795713613 825708527 230101334 901348801 632854072 823798327 266340234 665673747 98444330 586957603 780695357 513510771 157452721 422573752 218937471 77054477 135942745 77176530 920583845 926356631 322936310 386692133 759790796 421162224 848164530 544993413 990913562 915889878 185137562 445511080 178927853 716978315 919208956 844243853 448172412 321398169 580339967 44354417 174999658 580895946 840157124 430791100 826237371 685027806 744049098 476003127 685499795 700637186 553948777 683938335 644598747 501914741 777403926 586747475 557222206 61674674 439088662 350227733 717279375 997287186 970848550 23570973 802691816 281779651 379450242 314989767 738708190 301014261 714559560 129240548 234662126 786385015 962125204 517420126 997424694 882499610 549915598 758056176 835142839 986316418 410179618 751706074 88069194 10999738 207533821 873138050 370529513 361606389 65904160 425789616 402847729 130450574 319967733 446759679 510884214 135336305 829419973 397849990 443581996 134049900 751836072 84196545 716198988 32105717 568136013 553911653 339057372 833438496 100196941 393782544 148888119 283489535 433318240 37411128 567021793 316307135 13597091 99803467 537991031 733232567 905224716 732990190 475997062 524326659 244882558 221453187 579931690 653174245 502407176 877110444 372712748 159253583 231818926 656796227 247656021 497905313 981440762 272217947 885308238 49233305 777807065 486298738 462262367 657367322 145690835 648128324 345019800 664090120 21648790 294128292 286550735 650565478 795875756 128620857 903897931 258023024 965723413 871796921 625870610 758436635 521683526 708093437 556530512 106132026 622107239 465033244 892012050 372073855 268529691 79644450 368664433 875057620 527334686 637980480 995166945 970127447 38990947 300652320 299061011 277919407 618009865 188162696 442473959 502566395 110060760 694136931 598686288 963075614 512934317 79264829 22044099 651845216 35690871 691584391 415977948 979148035 266188878 524311039 727806387 840150664 546442563 778664930 438780001 106972089 705872199 779801126 66714655 52215828 259599138 456079407 985675909 913372990 887170481 611281603 393730424 486974792 624788836 114229437 881154955 180226668 558453369 462419725 844715296 243818495 155059790 997970514 228609461 891318585 802866743 606037680 316844265 3684083 800156950 234674865 305598067 207705144 257267868 411704052 94333391 494829736 780593696 674473912 933747862 838334698 448533238 218250476 674451607 703703583 372095267 199136666 543866871 53385890 479407670 252854052 365649857 597672458 756889829 398746363 482977393 604422283 619406881 929891962 556336876 455133718 460880118 454823913 939540311 482878356 684547789 36297624 75165306 6987963 347361542 849736607 196445083 484757581 778368810 883223584 158627754 562863675 30613902 50525217 76197766 393552339 304208765 906161416 296060434 997348559 328674140 530246716 764964079 296456469 419317604 646682404 860157273 750066710 571818219 92940445 7045262 210246186 628020190 956665577 587612960 160609160 226365595 646021835 746485804 828439702 752144425 17955666 30128892 902314593 580204128 479455551 702577770 846657562 539487380 546258285 19229210 490933139 620127075 469045475 990328712 193425183 291096798 395198105 478039398 750027784 801462286 543685775 34480046 65455292 667076231 984325329 518344671 309883900 499503589 71466904 796243104 713585039 377451611 877040346 25323914 848873270 499620749 520591525 77378685 614819470 23290432 123105078 374210552 866161017 250238842 912364983 373649982 23195440 56250318 357332278 442726514 315370289 669995754 176250360 207440908 506949221 707053787 602791924 250651008 409073871 217851602 170415671 824481095 157826916 509463041 612844595 737839078 826239744 611287445 718008050 105012538 206326900 605847826 736076891 346294777 469921758 835670444 959052152 182003855 483920042 20665531 491178667 895199959 789050680 490263842 431710062 717408160 592623933 618457724 119553262 282985911 932407849 670089948 229748351 208140747 802635197 587827669 577299569 406910394 853900269 138667833 721727466 689436649 437587233 203090201 622425156 694160785 813959441 394523641 93196927 853255187 865855914 46201723 317915512 83762989 235040147 311979355 530676435 268329832 232360845 806724289 510355916 879782547 710091754 763935638 150305841 620889615 659608749 48004028 965955371 678945987 332660504 892040122 941404986 354829054 405962121 767776692 457128210 564014833 242197737 731166494 325489431 887584707 652865964 305413925 795192133 358206692 698581017 836391475 285291826 467420121 699650640 733441785 715153444 168514718 464785647 941987694 247758021 358395561 568582459 956974263 158584402 316160599 94980964 211348249 180347484 780952890 571227798 575508384 636686048 553313471 446917458 780874522 438985720 211643259 182676374 208919993 510209609 876587373 446263874 711115101 442471206 176323823 61643774 966233129 12579132 707768532 526506313 741256818 670560005 919246576 635456732 520330599 781626964 561765650 647886057 696366469 82966635 525599872 622292808 261404667 723608365 830560449 468078761 555389737 332726086 217236872 913555384 301347045 230806865 876604117 118175787 497082998 274131065 333583780 605452594 87009486 382456282 858718619 535729332 126335324 125325440 499542601 309740366 369690785 215568809 645507966 781646881 844763727 676150038 751475787 518414706 571202985 317216704 303818345 527326591 818767259 808132672 300413805 243723184 98513910 656958647 821029783 71287485 356373609 505699720 893325775 360299039 635679146 137097303 820205457 464220475 829231895 266637435 286712422 797689564 660228267 804547629 729286187 790607058 153222408 967448828 684539753 306734049 268436825 705942542 860885286 674121556 951700500 90651380 229537582 823669355 941149842 264477471 80349270 86917174 487608192 462312454 24021378 998334241 353645991 451770095 716643615 633553819 111982812 132473260 537230539 432286975 902796263 188333781 461281267 748556670 709712517 57473506 369670633 32836707 651531585 195652205 948840902 393458078 968704888 667807334 799671468 220300612 118787094 254480805 885872144 379841427 25188257 213708940 994680424 423166556 335712035 796543913 342804761 332331994 189268743 205678167 972103559 483548576 42035481 406541514 821723434 613002414 208480223 942182464 124162934 732954421 904040243 394199677 496627118 693787785 595584204 954192425 902317923 771352630 372416435 612805875 519554015 233151688 783883237 158000575 625086394 108306131 846902443 223917415 43816863 943624905 123806047 24769171 248916201 535650074 547384336 945817888 827478871 377708921 132082724 855520818 314681834 873214545 329145429 466385193 44251949 494500797 304088977 691286385 279905956 722026491 266125810 201505157 725917994 217849817 149059824 926688556 956900925 372165910 377326224 63223594 649168647 866412027 524861361 659145158 2617307 107113719 326127706 424170812 202583099 527389712 763013417 559060258 44979550 268878486 215522447 251292475 682438928 837810045 581948356 27467410 711446750 166639050 484611404 449661979 772435425 849023784 567139785 223837115 629887560 359691228 828418628 426104628 620090534 211151940 297287460 636333479 69665892 677565499 362075530 644252995 198629692 620953115 152844991 514229791 1280727 19823660 593252863 127000304 196172776 229225190 312077722 831436469 175258395 431410819 169220962 163383588 698987105 560760671 94899501 668367014 756985030 616979413 407403911 596168848 692659676 771899552 396450857 69573151 351066363 935969413 63267763 9986538 443601898 311656296 342767107 525366559 822349301 522102535 482608864 1817023 306243745 192733370 876306457 209367352 445060158 639335672 743982008 612946968 754606786 527985551 754833105 451100296 716583437 570157228 187556604 955771523 329967015 875525301 153817559 512590920 480897919 182517200 516597477 276653316 171665217 160047529 291956237 21478368 810121504 812512357 646513073 297070604 214332665 504706907 752133646 841653891 771283946 257022231 915826502 895633967 800352429 642705305 94790501 340859328 153368289 192634586 371178770 60082637 562534200 751002358 55313240 22991160 905349398 692475945 352257115 234434400 337211146 60755330 232944078 634317920 234979441 689300772 109372882 832727121 962184547 646217443 826800311 422689251 432872024 281554540 713106346 521313438 935506450 420657626 832513653 893942767 924544672 898310601 407377072 162216584 751236541 431932731 677576793 865142989 594777855 872604491 352959385 244419770 389118952 839335901 976782245 180497407 847413676 57797308 520140436 839532017 69721818 387153646 651791928 532879652 836457555 231218553 271767562 526664051 209403397 29451292 607142007 281214237 287960857 760093224 82804098 781198643 564588324 90936093 202489510 952583846 360024451 418205945 122064206 166486731 938233374 840908032 945545854 43008420 679392843 988582680 541301629 815550797 535753865 174562532 96026592 687031472 44656549 40782013 890099863 761795600 262346308 269248425 4411161 930985249 649513783 805224105 289143699 622063989 955335934 912802790 345325684 500625617 545421439 878164523 793145021 603123469 12429373 857023081 408541416 886352741 894266244 651701177 410989635 561631334 504269580 473720698 411981835 17722465 931378809 91851739 161058633 412484833 657557745 201145814 296042065 785049385 405591322 430543250 853377344 797106216 949195196 254019672 840974502 112567715 540111830 66481383 958539577 259448829 89923423 923455700 884204205 209289914 240562306 517621819 387311730 214729604 336694370 678387270 83475332 762438994 92378660 910637997 799388518 146772967 771455359 924871081 790700895 840905252 261769347 382968741 754984728 730649811 663414398 151978688 38010183 830250081 927235274 606920659 621649248 31643914 182921571 460240328 245810226 300091363 585208667 453771800 701187123 473360568 880893454 874453633 550751030 314654400 162725668 785290292 385288165 859286632 821192707 181368027 496030630 311321747 850926501 717004667 445201453 530525119 794256880 1152128 71859276 867886299 219394349 697297900 601206650 363997080 382411357 268771337 100414753 49465033 932372169 767970024 128439260 175282387 194762781 347032784 704314076 575648338 422838173 467039423 797695818 910398961 664766444 738608188 379095018 884108423 631239010 261333999 986385801 93309194 106457202 327530200 653995224 507837370 197448615 659347758 34814497 295984054 606965864 839990081 137952054 453915697 904639326 711615247 347284616 316537623 807877688 132185910 954167968 941022923 853870464 275877777 650310853 254576356 901801292 299628009 351575465 50796009 739819514 38434415 214464475 232289883 15993167 340300576 335183645 207270 820830499 910991062 122880339 433461210 906386602 167232829 348789099 272760373 965847389 594502337 575698503 19674029 728866099 640538389 154675910 443025734 509935727 291317331 118996336 121445572 669774953 817441326 402366915 594546301 218065410 884158822 131014909 999922588 381620506 634943595 939456601 747506670 117596000 495859923 448303716 274381633 770235914 271505441 730840941 683279651 253020945 183368556 577187192 306891578 685912759 137984886 222044295 984677806 814274270 239065051 776550953 55518562 800703425 631730476 668449112 603704739 787072737 416118174 571004139 871900470 906945716 996347192 451588187 989161428 153256684 379859439 643279494 271453584 787328831 330468131 167043868 238072634 121013156 548664621 208408214 593694874 211321690 795825290 290588835 586922813 389093290 42238570 427746249 100306430 664652769 806190887 203499822 324148011 991165660 691804673 790893750 271468677 112533655 360365383 644140344 821084849 644947432 762095149 996158674 270471127 639197447 441835699 976357370 746725384 488869368 35585228 797074248 863742130 283210907 873261938 798516181 555537645 17150563 969530373 680487819 192128254 629064133 59195184 646201848 412096811 413997310 714062839 738336938 231605575 195800804 231093532 336872500 905692306 782208263 361456859 559361367 537800509 719945793 202493884 571872570 962248843 53177840 655065705 436514925 648704883 325687658 2064444 286303241 372421348 560972528 510926593 567572854 282181422 646670636 588266187 991921566 247823292 50859795 666110015 997492994 236096687 803609438 552538468 236915868 966758672 579594969 773309627 81473248 690485678 343309469 662028212 398146257 203543808 895034413 76196735 415605704 145738991 237554094 129161268 134014727 680793198 123201797 674525748 500790711 108683757 286876965 982655992 186588288 53573523 485092671 307682196 908099290 713134594 160579025 508805632 503761349 243902235 900780084 457704223 465449278 542719055 520815210 916486971 482082167 846716236 463989786 539460879 870458334 381371971 211994109 144639126 815112480 574154524 565035111 148464327 789333963 765760588 941132161 158307094 832703854 192220580 317226724 187297360 263115032 351655704 83867452 938158014 816469821 186269004 426825804 470280324 117842829 660506238 964816340 808042598 393135108 14852597 723298995 508320812 656973524 430202246 483351373 126618510 777765540 599174292 714258644 617881258 838470577 233518827 108190101 32913426 780209124 908203618 726287823 806744363 108955717 118848378 63140220 996252131 571983496 571159385 894721569 707318703 597457899 545885170 89795805 427506065 320843062 394199923 170838387 470758517 336836377 988506070 35107400 576750313 991071644 698144252 454818727 11423852 35108653 18195082 605442786 419963173 910689097 383369440 486428361 810565264 252811432 772662681 800369902 94506119 322382936 272776493 649898190 491155274 197523119 660068091 48602821 498090757 469614817 523496706 593997067 374331750 798667026 475051830 50278144 854016342 487622496 386282485 357102901 937666806 843284801 410548524 434087014 974378533 388271524 769235331 288573261 127880704 63246206 549163526 986632212 56705335 400230883 925392922 456573314 550487597 824014702 226180806 244526799 919674318 250614174 742072140 609988238 654889625 656158945 667131897 212395237 738083954 419225527 426585479 281709525 14683537 911502965 498751955 182647655 940434912 177543796 716136445 674907624 396645219 213556490 997479276 938427924 172142357 643236504 889354172 606817055 53968668 865461514 754912971 519077515 790549157 388208018 912695256 461271610 208548306 783064748 257469798 799904638 111490513 629498455 906381319 615497741 250864807 78605173 878051132 844024609 728274857 219582962 9208689 426771887 143711601 332794201 592194322 234241692 906194271 142016029 754225470 129048348 449687335 834722316 329407017 614043373 798466696 773629915 654287098 270330622 201743247 265200488 176439179 448512525 264382521 898489780 572284596 664390245 451297841 17571612 546253746 433549698 412901567 485747235 791139252 291419758 346463651 454010193 770804041 422319640 750505495 147508617 153813833 274539179 174939694 869470513 311865428 848499942 394462362 782565311 47066801 787893943 886085467 849262779 90341620 109106754 180169396 748782142 22571765 104529263 910174499 757066577 370412094 925901050 374604467 585895529 174648646 527042224 307422664 606662334 659037556 28235378 886716335 426108818 301332409 84619974 418143461 287418789 704562591 412041467 293911542 642152297 669087828 56109475 965101264 765556403 884806476 637198755 701975262 362179794 559447353 79041700 110476128 141809215 93890231 544994756 888773777 409618327 103652080 766018009 481065316 300213378 104085510 699694872 754798982 183099466 547886415 729891748 842431935 195744351 934778525 839450632 606459199 454952478 259800713 309862276 836232607 1553681 647933610 84627944 740653145 675027015 196051905 143225920 419132787 727100685 637636344 554179704 870571064 715778010 467944367 284837385 499134578 475427158 868345455 179725734 49976163 792463707 352487426 870158489 174985334 850676637 568050066 351354024 994005986 982578206 496712226 779807603 21961739 570262288 192171928 230618097 380655707 708696408 430530230 767423119 331498190 671732116 94699910 955567799 642423946 641236992 890714196 691423821 961413857 460794511 812477553 968462566 800215609 52637179 197851846 890737489 664585819 135419824 109995330 603994652 252025391 948987399 863735222 477289158 217852510 582245413 744136443 724862037 425210450 177523934 163246934 329580721 473306669 767224795 435080990 476055745 479007344 861055307 416302159 924132008 181984063 562308050 649442556 834453217 613992738 663210303 704676647 385051190 634110256 204430541 883661167 448436199 409641786 610534447 572488957 853254397 906930167 596094670 447053504 458315027 843595382 759396442 639916819 85183832 268430191 189141940 982514057 274224802 218389457 851809615 70178747 663889400 671768658 98251466 668216546 489984603 261983363 966604357 6947038 548653617 13056712 357512737 721980059 86466558 288383349 326315576 882832393 555344277 813409894 89975867 949661917 215755562 346270187 741384282 462702135 727119090 774996868 880953531 304087056 365004561 271842206 603308608 572348530 20135503 318136345 598671865 166007812 220153971 317178830 365900831 761182240 649894709 73206526 476368227 623500527 947775297 980130552 701953882 165842151 377107206 687626872 570283588 117810392 136476901 843301774 710750463 509188531 647296419 461454282 516544931 612520293 842125000 654952099 52924133 366588429 616387036 351048197 673912892 590232729 954435002 675148545 384006497 801896450 764635445 266852017 233129560 402257784 416700221 536688930 845884669 781872088 87836207 611006881 956913294 791506374 225842652 885425466 160569792 782744441 685759684 637906790 906235858 832081489 58535607 953516385 852181743 174903517 835056607 213082151 286421942 324668663 853435277 105296842 865153702 655595249 996138887 246066131 925907166 864443894 955739355 1700558 455129999 751737785 209215394 554464489 676478144 641164715 665879067 514233976 684476431 16281304 599122534 390278551 186352174 45671676 62444695 359894037 805684869 1962473 306687697 365281939 770548496 750496474 889557382 343458267 950619877 915648549 5912497 634415491 502602397 982367789 502855332 95127196 71494613 52555720 552353083 23340528 449871615 267736859 872256607 792957769 936192206 358773375 467198536 371494322 335692197 569760998 770855158 419985285 249634934 867840349 777873298 336191648 34133681 7218960 657120717 87380434 901858057 60516839 1637128 268855534 727616833 994030362 978935633 894515134 106728905 250942314 707211439 45335908 269813923 542726940 828865041 737337331 624513735 614356232 163681385 980699378 293443816 772706295 3435642 62947054 227239005 755243122 779016101 950615180 902783543 874919204 160368825 789432475 928548035 700154596 179947138 805856397 142408759 317931221 641919456 107558971 12262671 514598170 671633973 265931511 198586939 159955719 95173610 849545959 618061785 275458163 316462008 177508938 267847187 245105896 802061607 395089540 795421291 990421127 881789199 991882506 428565372 985376741 590932463 717691910 43838915 805640533 450544068 160024972 308035706 116070006 803631635 150715333 743608234 552873807 706046477 38525345 686969156 352791055 569571132 618015389 873694711 802450419 782988743 713464134 5563669 894366097 308779704 117214984 768931393 326878724 787901664 304107139 399691929 205718001 581273935 209073428 228298232 60931405 328386178 788855698 32465602 214969684 294702982 399085234 435860139 837279750 238844864 249875128 718555467 156925423 524937626 14614148 256745261 955594438 591404011 879182366 542527846 675557291 188102887 507590576 616100336 968113506 969196575 640467068 952557670 572372406 31776753 730973629 43818836 736877561 682293788 770890613 910924320 627821648 489961467 353099449 868040902 520454437 3502504 817401149 243833114 118845999 883366387 20319670 344299729 778905256 634466043 267939307 85647468 565340466 510820985 285291258 648808838 640385882 924419648 18888372 613151741 786956594 469392385 185235790 429396373 819562864 653961033 13084640 511419093 77466880 399019656 853134953 681036032 158689354 16801246 53273775 686947586 975831386 757466212 524375321 290157055 397157566 773232363 93575987 106221069 473462140 169605884 96449582 320079309 908753324 6039339 958193511 828758885 322743495 483862681 459063164 260322700 450352560 434878834 235080087 201249084 942999616 105356669 483782173 713823998 218768462 171274742 891729049 326598454 828814600 719445804 486533425 452158035 634550500 657139870 860161788 552414555 69529000 663078273 821829418 584206671 720018251 671212024 317100181 178607736 747212760 499827218 495052697 400206534 272487758 635657493 73688941 692451031 405322033 938297544 737509014 721698516 930153208 472494779 601667555 719842346 843798835 680801830 612411546 972638749 101559715 397250449 682870024 321733542 420048379 812343428 86045255 638327157 208602957 287809239 610715149 21508158 277879770 655917447 585577113 938598599 156590415 927558907 947586172 20104726 903179418 946356075 514582995 814805801 450088976 930780230 983058039 197925147 311548492 269202887 150622944 279695028 453253263 806451324 93839036 119013191 216585167 8026653 107173952 114134746 685081339 821854633 490242776 405089624 537362746 750377297 27062304 765164932 30658969 786621776 967758589 351946265 309633982 178651638 758892663 229541873 688112759 574087264 359687345 307463924 805780058 555439610 155142367 939425702 697530271 209324999 20327835 722368347 216144500 697083744 914037459 275008096 728500365 517622735 719726073 610954026 302016209 594569871 408593528 770047847 288824677 987547872 629976178 608299331 223168623 410640053 482825597 618428005 133319932 586880687 511312805 511319473 735724589 587524637 72500728 582017040 913379208 285560511 201254105 213054953 941801181 182758634 171393281 857349439 10505835 120164122 668531937 557072390 746389887 269987925 595014225 902186859 103381105 755381859 531427753 859006117 223648668 832283733 780343452 803199202 271859074 213081859 328306710 940860871 44722665 304766346 660741774 163198720 294717910 167115343 449240345 471105394 697672172 723895075 912609581 106064764 400836938 173340415 22450424 218808810 286550004 992387703 164603275 684094029 344510741 415778330 68165543 682296949 848324266 636225319 195794831 668665505 328529072 921733407 508013349 18519003 894265288 547627615 212251316 717720084 847597073 619001400 829654879 170292256 937069497 531405276 908127551 658238851 90608696 810619579 630468188 66120100 220846506 470286568 610817631 251046781 361668650 945947543 442936827 938036528 845005398 77035518 268977149 913612212 320373542 609003001 264136 820992560 577222861 638942486 31631084 45828632 311809970 801637138 709280042 29938466 508653620 988122006 826039400 75850785 260965995 240303469 279281550 136021721 379836594 202828856 340298661 241374724 736767758 976072901 716576450 254046678 626432176 413310852 787151904 508672834 764668220 82864640 978984702 545697430 772667861 375942623 260782450 826385914 816454520 947929940 640194426 768259464 329849525 785179585 389948995 424203932 342613354 458319250 42333904 500031926 458465161 463835150 245686127 349518055 27584254 433752949 238900280 754954069 420481849 961933426 480473217 951161703 169092324 664096715 920366263 654338220 199274375 898386999 339078291 812625755 605497060 735845137 99034100 132271106 577742071 471872172 630481824 102100339 429697689 213899888 860897129 310126672 512558208 763357265 473414656 954084052 228314625 109071847 517910268 820851276 302446234 433774328 880858788 978749833 399252759 56558023 502471777 420572212 490161311 417577092 205283454 628207914 291017339 580755289 693087660 27900198 448003796 688628482 6687768 186869554 142517090 960597877 296053514 374302862 294810388 584158306 475100188 235964902 829877729 931556444 495540933 308040386 510322852 443322333 558297875 718811996 722449593 986756096 874816720 243196940 25923402 229373982 242221480 917371766 343452687 800551442 278692815 249143039 236831357 919292476 760006458 307841923 670682793 579919607 380467842 291496700 599252338 729592321 641570442 469428070 855160353 507492550 202184791 250671388 533036619 21893312 856377635 862696979 959411938 984749891 2767111 764519579 396415505 495508453 471431919 492517810 38102864 765788967 775570422 509160126 503711949 691648962 240950806 213150504 432068445 478210841 28978551 93873724 103808447 245169800 964898851 107022351 57687354 354827797 187642022 18197009 364718644 296618042 515440118 238617511 217812200 651139034 799165412 284926247 952942797 606230499 972498843 800717250 519041791 775432612 213110 391921553 432680950 951235527 680705360 54850823 987123493 465144564 179419525 189243475 182554955 513300119 716961426 4464006 537052696 122932142 265227731 771026708 752715972 857956023 71155786 706316684 230610531 767513195 422093954 105975334 325581959 568084981 545171239 921258912 981166480 135055691 109751683 971286604 154948948 280638312 750874961 56646773 633538767 606263717 294632564 654108046 290020214 926516701 246817765 452485709 305891541 950541612 790556318 813661528 424383265 480431402 878653756 427002434 735423031 367128054 973837347 768735801 650419905 95818726 452721962 88447387 120562754 419057070 522435303 590885547 660921827 650990141 445768128 77112040 70717824 157392195 573240282 693030158 46960225 617637377 360446942 13195896 226095272 384837345 111500742 850153588 481821132 541512085 413564502 426275368 270319357 96825921 934991924 346308214 240013743 459813856 805826693 840423383 684767154 552522158 530408954 460123181 78722815 363948149 368665809 179870615 157332504 629084819 234951848 94619729 715349878 768679773 796029680 40110433 608883879 521309881 377143539 832902761 617751502 642618394 151477908 831616485 24524818 463960488 178166778 108710728 904521133 8047906 896400 32140059 151071175 923731902 484542560 628617703 508922434 112090114 233668880 774159250 338178711 233967706 864426233 380225064 392095171 752532170 78837974 683647304 897296010 249850489 184126334 767278789 585832223 154079602 539949859 552287419 28418082 615110329 78250702 44292153 588008467 528285589 400307505 962662165 862050188 554179648 648266141 586864868 136525872 200244970 808373413 802648557 594440159 291816200 182345186 242960897 524793541 971793162 674222890 545773971 377207033 819854388 265560067 907205084 379292842 697062962 534379176 77175547 543755897 314078905 476894573 711653382 20365180 375287523 710645409 248970733 73366622 876506858 76941655 732363113 708245958 518656559 737796390 67603627 451005297 491923261 756374856 931157773 848430473 440994499 280854136 3383992 762513192 463671121 366544796 703485220 520841029 17110151 865951230 158307931 219194411 724157745 369748553 895386663 896797186 62510060 584227418 971102815 578191433 458765339 964632727 8004107 285904815 223588003 832155836 714225809 383063399 287095732 608021347 978301497 398761074 726414639 50308906 764302667 728610184 459055996 771351565 737448571 964074364 222636064 891012911 501691596 881720861 549280218 973186886 41357176 419018463 241628551 942876871 717025813 415860057 580211520 326897345 173775336 235363517 979731868 983771121 273066951 237360574 514587221 312759350 336195204 205042075 181221002 762565905 446667204 897699469 136523762 321192163 61985471 501058893 941250493 471604693 295319025 803071700 816124370 477699917 154784484 250069387 871916627 877664451 109498199 751906413 382330889 701672415 864567104 794427236 17653804 341696582 260268723 993924280 160469772 304187373 138519072 285965200 530705295 906053704 401180856 592755719 44433020 796857085 368446826 906136189 331315506 236393970 52973565 203288194 655456993 195035240 356967352 190921347 119199687 572610933 379170016 412574201 1780371 594596891 740876388 858902537 681232848 18940140 573534755 720217877 379855681 349404992 602304686 7511688 966926210 138575980 324535353 241425725 902410099 590338696 482842804 262375831 866511019 503105047 632252548 144946640 818969129 772062078 3743232 832259616 337917944 206186718 762014617 686206366 234825730 674973452 126360888 384293881 412549568 921180606 242924290 524294943 3247813 687902922 736492338 24267007 199421237 795533571 254962698 334531486 94985316 108316121 10888837 496364189 695454639 14866695 371831736 307480661 774470272 315343958 521034902 221493216 124384866 830550995 38957388 537359949 374431979 555912131 537352736 822509566 81006816 931751976 325078704 512223093 575905198 964301237 317790779 416451917 575948997 453498821 820932092 520347289 538738999 566336086 811040460 457820016 180147059 707935008 656256527 37245336 981703303 901186409 747394974 655055433 136117209 24162442 266226581 690442458 897219796 839577833 57232707 763748104 222986692 577386813 297495527 64854694 492800156 159157803 56543644 553309557 840471518 203917910 123369341 377913025 333606504 509649940 932448222 998589277 292102763 306391272 551245055 831482973 334593015 340724084 283682343 650352782 94627160 61626347 487423625 127653100 663160998 616149987 450742913 978266996 52610649 230214362 980486830 395285032 989956475 996830850 531197497 728148256 479456986 848554750 242718246 41642260 208285684 876780786 939556129 886903680 109363602 23410284 161470781 471058288 620531586 7817911 372842551 799318583 53704109 470000068 600051125 808729457 705612863 996750560 422336745 554494230 735146977 85808080 852185820 775898316 323570127 384082151 419233363 605589805 265042219 513361433 390066421 778138091 693470022 365103983 3319076 902041545 723456144 541846486 583502156 432087466 651077986 364445499 102570212 858647638 244218878 384717634 804769589 908623887 419295208 596479836 109904335 556694498 700924049 511333278 569639078 366732640 34729592 59910831 291027507 670253976 782107222 373559934 116727687 132661031 541053531 312485935 916027254 286821291 338621214 798880485 17607883 825508967 877536275 353429854 385978945 593093375 983261871 514017480 210092830 339602478 689168503 433591137 599363907 689641131 450418962 412995422 132461205 720262177 559530740 170896749 272858730 350263179 19777719 949398585 974351514 225850736 730488396 626040867 993361554 940244547 820363895 477517262 319090717 500516054 648940594 557971314 978148093 985303817 900374846 131473989 902444954 10549484 765623621 402530898 639351137 640034802 243104484 205615493 665876545 792153253 710006081 535973039 479221180 100393037 240948424 554676028 143502739 679128463 428838659 294960947 372410772 393095776 738953395 416645820 52103855 394342274 556744712 679903027 29168916 282081967 160905317 301145042 528767673 512718230 942881441 303076497 733999116 655004749 586572084 296597529 937497684 975604059 216705955 639597686 120838635 411904932 1420423 92057198 757996014 430351393 487810831 143696305 145667345 408802647 974386341 38688803 823136323 227076226 979945529 121103186 297563122 660569496 465878595 996560192 750332486 26615201 420857080 374721279 954008167 90442287 105651875 423729632 745402040 774931320 252233634 55946350 268328696 664171930 356062300 775118391 163343607 482381312 895030723 758885674 225702472 37967408 837853704 605502537 931095549 752511260 115003196 720953845 536914750 436759566 562234993 443440165 800999580 162956935 275155226 824772392 623304882 983997565 921723620 19858587 799669847 957664284 10640509 127802351 442085737 599766614 34372488 995694878 699971003 196334588 659457394 307152540 609271520 550734493 364905593 801993282 733586262 87327646 802641859 68370932 598988859 22744055 215421697 453400211 441572952 689109562 21668451 787017654 568953802 954755758 405812921 330571993 253112595 444060124 893943602 62369371 656813732 384062096 83782750 733067093 524249266 513943993 53464673 409551941 827586546 179060606 438037442 886441321 936506731 128495882 145314474 201161975 115893070 106304122 256948230 243744382 284052098 754977135 97701371 552446427 207510048 574330153 286292933 46799082 239462343 30240440 243206352 123464021 850558603 330110650 369072645 59111665 748757077 25468972 246474832 966607849 430526448 471236493 219783708 25753910 114068800 794209145 363391646 544451377 338612008 57219777 196136340 553116241 75946319 944504111 349697503 50151525 667669874 732117567 90874788 298579617 810992806 529039960 183754933 742219961 621963777 616158360 908513374 794164386 955794410 717475913 650553938 443602975 727615157 646869751 471575966 50772192 122400332 570940758 724289477 897422422 935546227 377672037 478043257 273627541 507447743 982421318 835933067 931695775 833398899 876601310 894832768 338417335 966820031 670666131 864935313 224106902 716783909 169017801 276610609 353981723 841032613 882071043 350558850 945994729 583104229 513836995 804299441 737436303 256756810 175828509 935917403 883034151 828527747 899809052 697178503 514157946 424523241 754717654 605893910 858314633 908356241 758688098 767673656 191666139 238455009 632465776 576750752 183243422 922684999 318962142 115046458 163495863 209367959 917097646 474445013 762457475 644591257 588490892 137118606 756956080 266768936 865284564 683021124 197042693 629828928 783933675 241957830 790565211 175507439 346171459 986585226 232766165 321570300 242149548 379679646 964607894 80878404 137795685 436053664 530021275 234392225 722466527 95204747 201688703 43713387 461193562 381368073 742447041 333440672 728594370 940113554 703301801 348844058 254127204 535769433 98160054 18378848 462893572 581584388 608849063 630500241 970916060 800196499 262290691 239603871 168019027 907292289 777231769 84812903 768936067 931643216 87286090 182919783 307776084 617398655 240405526 202472059 16021688 413256521 137948053 261514732 404365478 765349106 388905622 276725450 996200368 957763227 796820726 14310815 323745472 899365673 709818267 763525271 568373419 919498403 520190136 55229281 896935507 304006771 937490018 483163808 391713399 691092831 378033216 886321199 917787017 522441404 683412099 160065446 13811342 49230517 618989903 24630463 286220747 838219762 658596560 754977666 360735317 210753912 53890707 940653685 712534400 779493744 82367048 298823883 41909490 849468509 662741116 505079069 890177490 700446670 436955015 523678147 487459302 174993798 107233682 27363196 521538585 600893678 549496510 967754452 865537497 695671887 461801687 616681789 286806448 394292040 513931660 730450420 674077881 800755800 394808306 194521794 591387197 76034063 672911345 515899465 82914463 764457637 98937030 851802838 136867433 67018632 486765498 493399633 441120271 942521271 899559237 25305848 235585033 283741822 677435756 518863644 249885150 467476709 941285689 963983553 502237918 158158900 920207480 865229005 57404667 739880706 288833640 543290395 517035198 919001817 989040789 490618454 341989439 672228045 156136788 960433201 958282357 462670643 858004863 664186172 953879698 444498669 999916764 451929974 466466495 383399141 558778168 438762148 182730951 797326639 603907155 437148639 18194560 836016534 205135151 775716364 850126338 954113184 52621615 732741462 988793932 112566972 79886395 252726034 144649003 956370301 391190990 33419962 934965585 971281333 994402547 981663652 701868808 648957900 1807617 258092732 188304871 104202558 866192045 148074586 416896486 656325227 262655998 971158286 844354171 304640673 909762423 151174130 283903417 79767128 781182904 16994280 647809821 967159817 342551583 265899342 412948028 757229248 705208027 910485928 786814590 849523708 91788594 273881015 757649480 590781904 684764425 558350535 423840850 377969050 727505886 580219562 735367368 335225161 164465745 3657994 601271167 886677784 494639607 984549883 516971630 332252794 326420490 904974937 406126143 402857128 452190578 469914051 585558680 351232830 588309540 911103822 947714312 35659611 428934201 600881727 241048117 640169713 697686650 601364728 664461443 407458215 312079006 72155936 287663054 762361573 540116412 470517842 386410064 765854576 48079705 575238534 825977704 731137473 34353203 887413899 822486611 665338094 921034431 482330637 891562985 741155273 611105142 453373956 969424053 354213881 650829255 250761083 532153426 14172127 798240208 888689566 503798016 786306206 586181137 682501842 787736902 326468509 148823027 501969869 302289517 47628285 374487706 938105509 510294193 208551307 862624040 797593873 708859496 823583453 635883885 798582014 826643961 306015592 656417335 587877220 443792965 210613438 266013217 727186816 164039802 349670844 169227681 630877996 975156201 138869907 446109493 404584580 459455 343338412 312461615 396723637 670458338 193634484 967244957 851649011 234103020 568976007 965966590 707724705 157210537 668983969 787949419 727126262 820107287 105316470 919445249 309391518 415162603 58008530 594400139 65130012 797679925 581441955 458978997 832323366 30330751 424770265 124845898 448099528 127160741 766729687 266238430 776566567 843081991 687152046 331990013 376770559 552127875 788727823 641767218 107186680 946220357 717368524 656724198 204529694 102588026 41530175 612357658 30346606 629675582 305551503 509276794 585568906 788998814 624999566 787750476 740851648 441753003 21542964 554020020 863313874 379138905 8165290 113790974 317522051 930563134 840754027 957362281 180086102 575499572 420661609 775415251 124541853 93972460 140855936 449946783 305231882 503030979 40337780 167835204 799941071 632248618 672503035 848904018 763688863 699929254 266826736 962369581 731641044 437992786 466422143 36058280 618820206 288699887 380552757 678801965 939826176 63749019 942383557 726494102 961022821 538474436 266337230 839610413 165726019 635226406 521546725 195601023 140091368 86680965 80379633 745867298 278707678 198331905 325541836 723086982 720800879 171336199 620323 613037292 757233766 94333624 120186800 732978543 791323659 16674838 209950163 603746589 96503364 495312201 476113195 757317137 880403445 326101225 752780930 994531350 807621728 635836517 838277688 210431751 782935314 63785021 602392605 873932902 564144633 811831933 196732616 500218869 93546996 320096340 934382636 685031048 510640766 702923389 697556342 852684987 631802848 925671754 578367886 142045789 397545235 906510360 789210020 681737144 767277165 361592146 760082576 136158723 372460294 124453357 293009719 412092808 110938642 605972952 117226457 247979900 802966491 323293991 150769928 309005430 219548741 908126295 134004277 181533751 60826719 586009092 279227048 909822602 502292021 591297993 452861922 152479646 8044400 946354753 428572425 534153827 927987636 649952227 898454671 626900130 908694781 735960441 247167386 171317709 315411704 941098693 323251992 662818390 21381885 21315574 753571856 377633149 872864317 899488757 956954006 337053949 195882528 237986378 88594199 482331744 292648513 7416224 328078811 344837119 500932568 478172134 979731101 982256734 76640943 637900963 207448699 145894567 304164724 958735537 213631906 620019367 893001126 53226221 883129986 597183466 870849567 868952856 480042512 246523966 197848949 75818940 871521717 662413757 659875003 628106720 577601708 759409346 794052621 227368520 398484372 325663257 224285469 14453283 319910610 295161820 890098042 333458761 325047027 290492401 441570080 612256396 927813706 200895001 729865825 936648336 769572330 736365966 138746184 988712489 443253874 190857401 747828134 464260832 747880824 373433933 157105379 252426740 166728648 905425337 5788691 412943563 716045487 139957209 590106741 628445654 910219912 335094155 539924510 277106072 533795739 980014154 533816902 715816845 956703764 806129910 249271614 124827561 382135906 534650844 674383878 682968201 860545339 335370380 218237624 338003217 415200398 15382794 871470074 886288943 544859561 54752182 417089957 432651636 604125536 214151575 353503946 281753439 969486682 941631550 593991199 648131426 527731719 260224659 73875643 311827107 974196636 97363747 218580011 369459068 406092906 331036698 123760946 267493657 709793028 308297248 471661725 987653373 163305014 20413936 186989213 856285950 849102151 547042062 975159681 308822266 645102454 941025789 738704140 387165026 57461471 448356800 619918643 936091479 912015852 504942076 789766519 893957886 800155353 882012854 967973700 527684176 972883485 790234619 814873362 40006208 61276294 5211042 330718520 458800843 173184077 230970218 629598424 774588019 292770370 740282359 538153980 554401774 715773833 958078524 76623639 50909242 726431303 866649058 937290400 831393479 786475484 98074430 700278104 37938680 315467061 314684056 285522524 521102535 279634651 1389990 361928525 905382358 646944816 512579204 226043751 559248868 853021366 805812199 934996012 515993564 280647123 610688782 64642352 215362002 111658533 625195235 124492292 978376807 967901999 768966437 285778512 885599431 845512302 633325499 502648661 663068804 125122342 690569913 39919896 62332937 636584402 250278792 962184274 419631162 705387560 565742297 655953984 966448527 681701166 738593706 355332500 801628499 275875002 76183349 21780393 721457472 823748026 532069084 158697643 393785595 58027205 325945467 254394243 839275876 579060662 883397121 225016952 788688436 827975191 495380469 454416185 644771343 378916012 28011668 190083178 507956024 732140656 50928350 207302137 790419548 763825969 602769278 110717002 642120132 350564932 843055339 136097955 470747127 890823714 722234463 252474921 351926127 336829971 208641185 583035251 346528179 867455641 803006171 164727645 682161264 287904919 12500923 20245022 920689848 633279640 685520411 501554008 783257087 52174780 703801799 855829487 760477314 755559186 412505954 562764563 471194386 92133181 116949960 186131292 639658195 744972484 906648001 405961230 31599154 508001912 896912177 406074788 9086139 492607445 62732888 952057744 884302075 228415905 396940413 787118204 931202669 755372452 492868416 564407023 874987820 274220963 876506658 414499126 498251907 429481280 824546634 922441147 437722131 231459164 421207419 388134324 745137430 151334468 829955718 617252350 173307077 6818935 560479562 381778086 66833513 23197297 261167205 751427131 621707765 48637293 480204883 158345373 401217049 632172287 358088105 652186518 356583540 455420938 618226835 53299509 260488151 339195584 805682996 125299518 668375002 129794387 43139598 972007903 781545033 969165097 671132290 650356715 927940109 440924792 613759206 20054219 852595739 521403535 315379851 568103507 665255164 387691637 380681534 464006700 286217269 927363262 132790071 872931085 36561381 803025019 196417539 154369503 845346755 461516030 951291982 578604914 554862235 140379102 448269309 569762049 14001637 75883492 555082911 330836951 623801808 451595931 243516355 148872181 943194676 336675912 11551242 505463806 830094003 675460379 58526419 241784483 4419302 495257750 897221808 728844590 611077903 570547374 462784872 628540243 647577238 858825328 881959028 602905933 397600187 111044146 477761753 597811046 927218645 783586831 822145418 921250834 264729010 929886984 699301740 427213817 48434791 460617558 825334629 333872108 837599163 807526403 946303891 145930957 408262846 296815291 903850060 882302375 814040167 533136296 965818016 859093811 361143392 250442825 378979738 404327131 32700055 316126885 167625426 898169352 189433066 81510237 713955145 153303010 209144385 514639942 993683495 798590876 825586479 304892978 389674095 603787994 38805737 40764939 657599089 830637699 607094223 780245480 957563684 134237144 448174610 425571023 734565470 998220198 615856018 946692197 266934384 207786384 534486287 726728657 877201078 145387507 319058255 124379511 102808933 211256145 233307516 586495923 174166871 871376733 682023969 239486922 105745598 746409442 287519539 218552294 19096051 841264638 731755596 145206487 41247251 2574991 15373526 839576418 184464804 522531556 166964802 158431354 331127032 324991974 377597593 669627886 174082498 102244568 633339943 483711731 374045410 515504701 893275871 556030235 926744215 407002768 626730170 956012176 649649728 32134531 315676395 167620365 17238406 343615634 764603297 645847620 128460752 386564955 889690764 566160022 584826960 479761531 282219792 940071554 799945733 530159843 915987082 761543709 657011155 279128678 590820447 827714825 336270961 501883436 806887544 783994715 942023613 881048736 353391704 802223869 356525643 588987070 64750189 844374835 633952624 367296699 71229368 257771265 92806565 347176984 533782044 456059863 20221573 942911224 683249857 679847378 663655786 292067735 311580185 267832037 559894577 668739863 821450971 57257590 519846163 633246126 232046958 540691362 22845799 513804830 283472641 92842522 440866454 748093907 228996419 502036055 897589229 658587700 305170745 912462276 9893188 565449944 822425697 753606572 83372558 749814101 703766798 125749907 720627870 961466501 970785705 550975582 857405631 269797238 180608787 343147997 835326753 107626117 434243925 876304988 993661344 255048370 327424582 858186352 167793077 444713867 683048214 461985116 442080175 4115193 56778644 863110708 557760044 274174840 309506193 519307855 907932487 104083390 737246043 851332655 614774141 761022137 902234555 791894810 434011160 529920456 37504751 585539527 174361340 903628552 437196638 780885780 981522472 547105652 948188606 80146154 797001275 777343248 153089618 903462113 757795890 936802033 274426619 240285914 552500766 223905450 872690763 626449770 173085259 50842126 331181501 902915631 535754887 822153303 753429685 274733004 475173770 4117726 765720159 877437757 411395116 370052049 952344566 988517343 684047000 297439790 768530922 269236197 519736902 787618511 81820604 101469218 323049167 157589271 902102415 689489219 422339377 963478427 252790455 287727377 373621951 377898966 996344991 404572336 180891242 129374927 246839011 994241220 360559790 279692410 41002501 788948172 10998980 559103159 880936426 949475862 649411807 126539453 495833594 858654655 979079585 134621073 207228745 971219687 633259223 708631661 823242519 824342275 193507417 52402157 316359138 403516180 16298130 881958988 881928760 709387618 220720607 166851038 795960654 457946830 455226188 494372528 197647945 962810253 494045244 963863838 270792639 686571209 985920227 540266209 616628337 717801196 867561034 835762461 859169001 691676922 643035362 329949347 375587886 267499617 749644244 551083238 208720077 20234975 829282642 781793183 488574821 907060093 361878363 958878692 821180977 75532517 369155266 346098319 820773343 440268353 66497136 940234381 941760344 414760878 162157920 946888441 313762650 957636366 724178629 395779966 730748487 693728473 168177115 242746774 433361959 186562834 94016001 554275809 557386393 956478492 441095456 430541747 476242452 391996204 426309956 884763545 416596725 17150505 751061287 903931512 807966107 645404773 327670649 645615110 431750593 688452244 18901385 41805647 896130535 837555553 954054171 746452297 88260731 560825996 516477255 348144666 811213501 604954131 997983119 261512797 562263542 27640779 75338226 330594239 502503970 959670888 407402680 408193945 373122092 597571062 997859828 687773283 379378545 776055702 446269660 138488665 375403673 42097277 593798315 561631615 598474921 384707852 67605153 891148932 416038444 779476691 292071656 355377159 206602834 781749674 845408864 529454319 716353836 163944890 90283049 939181153 46384214 626428907 747383862 387180410 163281170 201146579 468989971 853809904 750543662 752813763 128947006 781476230 792901712 287731438 184027612 205356514 879297259 718120207 38298072 735948438 530478087 430653853 134972315 514138429 12540156 602223901 535313820 28165781 402200384 564115362 895700966 713741123 355229506 735585808 122126738 120466365 889636726 83673526 952471302 499389206 617571518 608118522 61411778 736182595 744435081 337743152 567255792 27644021 932086102 732423506 464161439 795182283 524704107 217928850 583707592 527327796 688383370 221295641 846915303 983047032 453137181 677181226 399897458 602179029 949680489 625845033 255995592 389027504 992012936 550400444 497941414 749530567 313515409 334778472 350471882 234704561 766835356 932407147 29027601 976017455 875635029 104301293 204928305 659720883 894446266 207515540 650627432 883780669 68083828 643019722 574502523 669960479 605567156 234617422 910774322 644350206 807581225 872866841 968074507 496766279 920828606 918839080 221927592 138583920 813648477 151536601 701071758 446636398 104362592 3696706 295665279 862340783 580334603 460145525 306634375 898305848 181820165 750761112 95070996 154423882 714994726 311724928 848058380 388042683 514010909 149788293 460711430 252735875 716884091 943481778 54040336 892144158 867749442 589138517 545229007 531597923 109237682 382658830 845948952 554337956 717341835 779396030 98069446 593230262 473380300 444650044 1268469 521517231 851085553 799233235 771986830 316428212 210680867 957691979 893563923 29918314 433908390 51549376 95590713 537821659 877238889 772589671 659459055 456923207 224170207 746305038 160225538 412831968 610001985 984805915 528862430 274081789 744851688 555166817 267523783 82309125 777535345 749803738 675609168 654389593 8676627 42109760 610765910 425175571 351421172 286829471 838813144 213054431 437567530 99007879 632476443 338486165 448188329 374353667 517285799 379346611 800482361 101802869 423515590 206522912 496970914 320812761 653105021 489239771 482780831 721611188 976971586 536699981 271623849 186558410 407101523 197989587 45675700 626883830 631159400 262929728 532113611 886995149 569743851 49186933 580286982 399522453 439931981 728285980 541195251 591490054 240470453 615775482 656040468 591199842 584803199 516638356 466784466 375453103 167919064 820918285 71063212 277334792 411549200 759062807 560144798 428397508 510090720 745119815 872812997 735952931 456530686 95593202 608872503 161207457 304625219 682282760 52805333 172145252 172968999 139984450 782780485 854541927 882530183 764851413 183757880 621316142 230253193 852757560 685956896 318943620 42965044 282577341 651537785 897305156 640726603 380345138 495594777 257265448 827987754 848758589 667142536 474900927 494173658 909426050 4644019 345705616 712047000 387852916 119397545 949125491 40785040 190991660 419776099 777920722 742703024 384585469 611123534 690892650 366178635 111085582 887035755 660213993 336692316 292756306 468110743 498984668 182017101 564029997 160113892 114403003 456446799 205961924 111654022 961942654 993260075 5601977 156324315 483065691 472440906 683415035 23882979 529857707 111229382 197595353 289180730 173879807 276596884 123085844 990070593 616824976 86273648 345393958 470144707 582793908 800686773 909413810 640018893 877331217 231473660 194236108 727753846 682707627 288703484 830983386 780417966 699119433 264396600 267220865 33880478 388583270 930556607 495086329 941864127 794287843 829914125 879004354 381590548 817517417 196319911 557124789 552944235 406176845 57493366 694598492 500541803 188445445 560821215 234172128 941757913 875247611 760985301 811848189 540153242 702849909 9802017 724391711 63196653 121917883 21008037 287020911 783044347 336896103 557905715 5825874 631537563 69320150 152594776 678487593 794816570 12737214 69687427 741341794 85744858 277839382 385201384 765614839 642499085 775319050 5505867 398198256 822261906 315534019 137602818 739183626 78070369 528369749 459671344 310374300 454010651 909748400 494102403 263013612 290258057 199260308 396784820 949081504 321814954 756060236 324064431 323943725 749167235 681953501 203885433 783277662 227847180 263210434 349628572 307133001 866939999 739447846 153784931 834138204 278364916 207623310 648807396 509897030 957830728 359726312 425457486 472419736 825432025 623909434 429215464 98633163 827998010 90210440 201198081 963665566 507554922 553846799 748659255 834067222 778113787 278619846 948291264 724671812 747448544 623449471 153196947 919746419 606115221 487442073 948838006 802985517 978060201 449862461 572794486 900681705 377371739 167575183 795626503 418841334 348969039 501058308 490908713 175269194 532374203 421682409 5185370 743051042 360262345 61443243 802828571 902983808 243181981 900322050 334117554 715941539 955790448 886382588 239431222 18391497 932505672 314124068 391374726 263430037 95190242 497987262 905056233 437244861 564072252 117636341 77703179 375674415 448115973 259836010 542371369 832682233 313956491 580245306 248689703 4185979 442464035 445335106 591045400 571364568 684251439 364176082 762445030 108886384 801935754 14829465 914721657 549190102 843605897 236731266 22284375 451104322 417685887 669617529 270944650 739582578 623036139 300118253 273295157 576329309 53943412 738876699 703168758 817781671 493318350 254385740 184297915 953119562 680987055 651325448 942775724 38867128 929958217 668794364 424325435 45625331 53080831 260701118 128921936 847855055 758374251 382727306 717307401 406756234 454659860 829258614 468436068 189103803 832941398 564958934 6853010 991857579 207614853 616711321 770495672 349895982 892286443 27117977 96078423 364022437 928652837 503249587 785077211 923427125 506899038 250617081 268464184 396848007 434732947 260720838 107442954 684061849 966568307 41280040 725931771 263205582 22700432 77787252 254789855 195078976 876230609 11609474 201528867 476121827 370621454 908427495 911687316 210682799 973348386 583821734 255110714 701455119 663527762 167642055 243213501 485171 736507563 775586225 376575340 319982788 905866829 168077245 148164351 338394236 270558631 486673685 457057070 883144006 238899985 107028742 343151296 303689577 550973123 295514045 815804033 609340442 961644893 762756068 707361335 543048953 509442201 336752217 284224467 799636012 398455306 61088324 179147227 579518310 942652853 561427076 810218558 931104503 69512468 765921411 951293068 79836654 191736706 504866397 467750171 357143774 571515520 722189726 368545008 985714277 993329330 601754496 811102425 89545327 974420313 24848242 893490975 287455006 556731820 967787113 590509551 607433016 941072469 62677509 206254198 275351442 835606782 652358019 489468977 337407771 166206084 931785123 499843652 735993450 944532013 685419929 335720866 885994651 618091564 335242160 440859926 74876720 624935203 304818013 843470683 487791799 716240103 210239296 854278238 650251007 73868079 824544407 551672860 33847825 73269158 445658073 560272642 899518619 140830338 629461259 716321989 322182231 735799680 847531310 606213068 349488249 141268278 970582622 943578076 310078380 592018214 871960906 196784493 127534089 811936176 326295202 462975255 96808651 294994088 552245492 470276058 845186004 25810990 741463561 339167978 802280168 890458071 1485065 539180653 348683945 928149873 285704437 839806091 637320485 233657201 462267307 489694810 617900896 544373349 261918539 619180552 458136025 374274270 183849962 284851952 645471631 655615731 697299231 870494790 648821061 990769569 520394730 568874241 696446673 790443419 377307175 930137124 758310280 473014619 861898667 717220727 438138609 780573098 507405172 752793686 615477661 789669546 694276028 268512895 578912003 429533038 950074420 320403386 68480003 976478073 889161553 365396661 799833610 344097071 794053877 713677261 641134981 437784237 828833017 282947869 558494109 213926660 745379706 665845480 463312021 79844580 108075878 297310010 299375524 603675516 790376436 228479931 413940441 108254481 968283267 29180997 287093253 193089279 991933825 191656347 452163062 55376792 132476176 425582563 4629439 436958722 378056453 105709733 190236696 864304444 846239154 173118056 714038589 889110107 588727867 353852675 670812150 634586359 370601943 634776171 314290433 430742486 383456764 65175839 349213881 22962945 301447583 952635456 957125577 584663948 514834102 205645802 826828463 895698281 662800400 459843617 10073738 134273455 686188927 463843730 510437478 105860637 471964630 927938699 67395987 751333203 387557717 611692355 559421607 277803923 696440465 571164901 489768884 28595283 361189607 822460325 543461331 377959633 289736611 648209104 929447755 596833065 839006254 899869890 600396396 753169276 833921026 593419044 321938333 222384684 915114478 905505758 295567586 737368294 51546834 380994733 672606138 302910199 952678396 270623359 484682196 253502171 797596518 209023357 589096120 612640138 309647000 467216392 65531422 2059074 751683445 139799135 483227483 33047796 716264452 340592470 183992536 157534946 614486913 297349999 311428952 673454408 602890644 751760843 389899711 748989868 801972404 96750900 304060821 590043255 340752659 4340750 107205161 998242644 137623984 824704372 309109092 479115050 880911948 310683449 338410519 79783143 566472422 189276784 346708843 600916734 294895710 20737416 625679574 725455228 896524449 526429637 860261936 830906823 984485293 412436332 666946707 618517067 993280499 552059606 187389356 816103742 81257046 115338262 358566785 222452902 125292881 357225851 655268506 212973685 740380647 214460939 823824443 488681160 408816389 808298728 602845588 585078660 297956735 266256176 947991453 427459985 37542756 880769824 112163553 292259527 391712252 458127799 554700213 540009192 380769836 744501931 198003314 469378021 588940992 387515549 455909154 419399773 763878742 874777117 146125041 483283880 591858064 544660581 728717155 648301875 346541277 172063410 534148528 823498736 111824383 382309010 880444723 693616823 407348792 592434484 46606933 988417534 590343426 532389615 53429722 901123454 791408844 633112125 790819083 563021749 881705851 662383330 711248382 864615938 771148191 840208230 152172707 641167024 32696432 113783076 139541293 894363983 657399503 82098346 92487564 138224486 516294707 819993823 405197886 176189061 643638191 765678589 755053895 424752619 525083855 891422139 335278033 332848515 428991409 886688245 874011487 592066967 842034659 95408922 4536298 656652215 722927393 610577818 515324856 425109256 700572508 904950046 830937284 536936416 964756729 695118085 437980875 759064408 714395757 533238788 422710747 748101629 86963789 780418330 702738524 227834719 883708380 435124323 751224291 767981416 461718789 972980810 318544011 436850990 347838694 372361901 569459183 482051410 365121171 51302521 954163205 787439364 135505656 87697636 434983749 530422821 723174487 843023721 835011997 534185235 921642410 190705710 997345073 60134721 637705660 206722620 406179886 758528732 909478364 941249750 473391719 441328476 975276406 28220909 596790968 242473126 717880431 641803479 641143342 643819807 90739151 106698467 590105280 600607517 527585065 441072297 33278336 399253526 133951887 859529379 101580906 864999173 422995680 974218385 78775385 180250112 649875607 414374152 289763059 944670915 404278944 382931366 377663176 876551580 726452351 359569591 986401144 634670323 916785957 329265967 49048333 725964850 46483000 710924653 270076082 434056430 511313145 664436896 731466196 849139266 176648819 847448333 145923050 692898797 907188195 440675958 31822312 245745699 399250603 215042378 18899618 838285696 21067721 512069905 397222830 527828172 913105369 74158666 380819658 605891245 358114872 305351605 687969798 543320106 456349661 520159764 988916492 826178896 784447442 917737574 170340715 783204374 539962153 563713538 96022230 223177835 212159847 749653392 149577571 85189861 843085794 991899717 848631497 413945572 683788961 982370271 454198089 433204398 196561567 536233785 778067863 99676191 491240145 352628678 691227656 212132343 394655096 264339991 806024956 253248227 832310365 318006486 281941110 662070650 350749387 179995381 535915262 901423367 220603182 761284162 848352723 579101164 993401006 466485213 857227746 433372887 975170381 90279397 136447997 685620251 532784360 217179416 12544174 660303656 903849381 408558964 452012170 863779047 568263367 544313700 154220578 438912407 418358050 137834053 466945934 94442964 81803255 687145731 987149984 476586458 661569420 752111139 946934935 599973127 804783187 243678255 123861757 296026043 365836171 873772264 783203369 811708797 493127174 507893036 58079852 371182195 189329277 391690593 819219531 333809685 934583516 525244835 19573201 790508852 730918814 366079599 730908740 20872006 309833349 393404840 180603459 627193487 211427016 498747741 408876784 802820127 780026143 387118923 895269857 779695310 537014827 446949864 205612083 723866942 790637583 530993631 532065765 209341811 564936867 148922686 641111627 159964812 740100087 395515367 599580253 280273509 48373666 340841030 158661101 716061542 88003178 801874018 648965325 348477552 217378156 213023025 21556026 307711686 459230916 556578882 754399323 835508023 52458458 158932913 953188491 204010095 955542467 39681877 274027089 319392806 293841250 478116409 822740652 283233034 889293334 927823237 794700037 268858378 81920111 391864888 606327490 671431091 12111592 772021503 25509465 235784553 831050474 546279671 996957222 234303350 599372096 533086701 834226009 284888872 672512181 997225475 921511804 237167413 615779635 381871868 966477242 26151287 931403414 980347940 44712128 765797022 57024716 423078422 720648951 281232484 129329282 511980295 317779038 761697148 333827433 209279313 80421308 917069164 105789226 699648943 433359995 458782167 832400482 873102620 391086302 868517914 431036777 526493123 343382634 17601938 282055235 941964508 993926086 477631815 586978851 991822218 131257463 328294409 571834411 566757883 209202117 986796250 911407690 594304998 291272453 1752110 14234159 434912173 178957974 485231220 546668401 89656955 34328065 743201809 689564890 784490071 205199940 10065477 45999556 794052377 150604457 645487509 36305003 623834187 420844046 355450091 754442589 753239211 936061114 720910420 577956540 981220924 198399130 51774122 143299521 496365820 181409005 104717235 710215131 22796143 811372933 657083190 33557680 682959971 864265284 226423392 104824675 18936119 992530274 803200188 204860367 510736322 517175880 120225728 827599203 843808299 918665288 357433302 521862517 781965656 472724763 188104219 655161466 734795929 145473170 960760634 435282342 479222487 948765079 847364127 921111285 325560917 376379915 181104057 748638016 278704569 399244437 399358873 599419207 601874211 845884430 458032757 302121989 884912566 278584085 168608310 756067152 623335841 558235745 156141663 9891825 474250520 625742275 617937450 291200580 861846714 79759795 104402891 815538602 798507281 778960065 929090513 77650373 827124735 462250081 353409420 424813959 748091708 276932910 46760738 942415272 912431244 104390251 393965521 212582649 435791722 167985413 680258055 27807124 767624929 264013260 851524962 489662373 969391740 989530910 632978739 438960856 785698494 475296105 320685049 23405649 541144384 357929868 574606292 131515092 681732484 832635881 880617601 75807565 296915100 795744345 988618026 547268655 717831708 653467446 857721223 595283044 92181618 777260563 89779451 287760741 941826967 379217931 186983144 53889556 966271094 793008095 101670932 99868891 74452364 466094869 199864732 849988092 352431302 853741583 612666507 573659851 601382110 291927403 289827488 824856006 90876796 218017961 18776482 560989459 486076141 988081692 105484143 630386302 842608152 483280785 439577453 697130994 512968654 821017905 970738021 130174728 491798978 646108574 867214162 136344882 555034091 491031059 992809046 109498495 260312260 737185542 727673027 642335704 492053156 983018725 853904292 836508304 642668537 177812057 521213368 56369292 791340094 211325788 754280835 223437482 48580265 827547415 627035100 522802895 117349883 464443526 622706201 991804371 867969376 641508528 399521106 497069384 857329507 896315067 478134517 282101552 119544407 571626758 619267570 261086767 554405662 770574408 652374060 902109084 659273430 214994924 719783752 61605619 132669895 36230076 662559797 122986826 426797258 732668947 720587424 478499486 767751788 545169273 469807894 684321044 685753850 81886373 172497058 915902992 354876999 639352824 451353982 181848057 556292473 643140495 977518384 759977725 551489111 28540808 267857187 668082709 905797316 631525277 130824293 288070251 263965942 385924301 480030565 370434992 869183278 427872072 286835056 407713485 539001691 240947298 328231590 954468442 392505460 156174438 42416132 938766428 657870550 983276893 190323341 317902929 174076303 153169564 427352846 943049534 134063893 939214845 954467357 908691346 200346323 491651264 791022373 447539293 129142832 261210098 799638002 896951009 37585573 201003975 403442085 170035779 118388953 972127760 621135373 55142269 372151313 45265126 914448532 742753455 162503992 36034519 753556117 254468434 704705337 537005939 269746210 595135145 625955983 797133582 38641521 522961499 652305184 898427613 125080942 382751691 467337166 943373898 500878387 113139243 749961100 927981849 376831610 672901831 624134484 704283659 111481067 259428887 868425242 807554328 901513274 920758089 763894919 339220107 655166883 517494893 345630651 908631513 117868494 497506997 979966517 989117379 824278720 415270417 609985600 358019693 858027892 620643838 65143795 927724743 497331452 338072589 121214292 800060345 616212444 222011370 198005401 591141900 900942384 137115119 646686353 193024170 317428266 625526566 94318985 590203551 622959239 922571671 665057653 619894379 331552786 73413999 352631389 726890649 314637712 45946253 946865326 278086787 323152493 575144978 409624088 393936872 535464193 625783361 201908193 323896533 568494143 271490072 617132215 694229464 747177437 794675387 45064673 903614544 253992740 767366484 838626190 587470195 62300081 698147803 535220456 38552005 933803428 426275656 111161888 8547457 738244862 48408266 880779088 445604218 301997711 428028344 550238935 316095705 943521647 143321789 863965861 415817072 525123438 962921238 627734572 354830865 783073063 666067812 198087801 954568436 478530426 80171594 768291707 111685500 330317942 298081117 839317533 332940339 894124223 277355846 488232103 113022891 684409388 918656553 139762564 375188126 114151791 791885359 168422526 385821341 448488252 198524713 253567274 750106691 747618236 986089519 582343551 422972032 108913643 635922482 659067440 529547656 195775364 787584270 583375306 33614087 256602653 969150683 784693523 528151555 246132374 623369551 75847578 992501875 685592066 426127786 645017811 714891446 120271471 818192800 500887206 652064927 513372833 715674263 472290104 161012395 476842491 740079717 836654158 89459153 828516393 221076913 769206570 14149593 590970159 768336406 427961593 687537476 535054415 451116734 75639208 932918467 29659430 363277343 740059072 97963066 997784676 414158105 899826360 313409451 83704939 732506809 300760441 886982127 879789887 240169854 375591954 522808840 209590609 666990020 297675504 455753611 247982284 916202307 885584490 516043511 366524375 678664511 307871043 961714070 513757757 181880483 204079073 667554455 260661073 43864088 113490649 747267176 170857305 486642223 477933962 307461875 97630552 490003064 401063026 546107610 487127896 374906430 75877850 1006170 921013236 526457166 697112585 343893853 716495714 24354177 329636567 147396977 605888027 505344215 663712366 444068144 497306896 948648554 481082398 498400700 618978966 18397059 634144143 501317188 695615716 313653608 971274103 945570582 77551065 304293817 888724159 981452633 613417523 550979125 217207473 109646453 87421757 792036292 802503382 810850395 220140676 871233214 806598623 358541625 552726348 341825338 780779882 457930197 539773201 993304763 389128952 59090314 93342648 927485901 757688115 160853524 643237720 97729224 482049191 613750540 926598235 437437632 988150633 791986020 508772997 833991644 347373765 29052059 370231263 652948757 625634795 587312785 103500287 120166773 724509604 474642461 425340837 711452889 308645752 307273772 813068937 479242380 257574761 349803500 147008679 76680709 413972457 295224015 959934170 430254680 269854708 65125847 828867021 943760583 380152058 757113428 331057962 297772655 208993059 991413946 935581934 775498026 72927140 45791783 711421627 655360992 42525712 321216364 286075646 467507971 47119596 625617579 647136434 661352830 242483980 904387424 48052367 396138693 503204635 680944501 536636860 639532280 598515278 88925679 183492785 183581365 708451114 638268246 372869140 967480211 424512886 34017202 265739243 977134888 400031459 142497798 434786125 554545089 303955887 280648021 784977554 343640703 744310741 341662580 482968924 605707399 760780858 660073808 97781678 580070355 389166599 169529593 451666215 247392649 495918036 677639459 488813382 438114523 79610706 45373950 239458809 369133881 340063919 116020082 464975462 673064209 626813431 674058663 305672428 637404720 741826814 995858265 458458362 812053902 789497052 120757051 48132503 848797631 533638003 540213870 368411980 951609094 822159277 246246526 47761727 640722344 941037026 962495835 821764567 584767672 285010509 772466991 322917884 791239646 72492910 846375408 114683669 832292906 769123447 838792894 574288686 387489398 998190976 400066191 874629684 775111932 917265232 593943518 628262569 923161664 698317661 122594946 947024713 758976098 168924036 352799454 573254934 625440161 35179907 666114535 758674446 674620431 456523691 540631156 21225174 10444583 454677781 709489810 816069953 691250787 731560613 617959488 129117 320050476 647690983 143084271 391866908 466175070 270668785 777281740 233429212 649137825 232493343 947155897 729914863 875737018 312851997 410762825 797800896 572207609 83572264 274491480 330012860 590018222 159572286 131381559 899627494 858463211 107491832 419294825 489450558 245775481 617786331 899153222 423186398 287730639 650584080 343456642 796433032 587445518 613775344 722169597 823902786 570677102 624151142 177495835 803588707 905687647 588969035 11050229 6412616 66279485 85396271 50895719 702568870 730904861 582295505 676313561 710661678 659194328 965056668 352110313 587680987 97755652 681944630 287860041 126688325 972360078 634988681 520166224 957730876 583502420 46315762 650206230 485542189 507506208 315825822 675639268 746134641 153333149 658255280 192261486 14931757 249713933 856897251 641719872 901468180 895790382 166558097 490887608 911547753 621799803 458855047 367204489 597410872 959526875 128164702 737895102 93750750 939945474 813299239 870226949 695603717 919765554 80439539 814133276 327648475 779076764 778159135 671475133 798066546 319717956 727906930 576843941 434154 435976295 147908705 800643233 496907818 834217075 399717266 534465070 641858576 374828461 920732738 184127861 150671215 628948878 994497023 224619245 498337353 108334090 850414360 676550965 657745358 717430797 834747369 679242377 145248664 315518324 724807752 108581783 162183852 258345633 189719805 152803188 785457438 660411485 304209762 895432355 276157395 361869253 258573926 455032490 214530804 518885207 777557583 526515505 19040409 68467568 219813386 319897284 942568231 118166907 885099 800547018 286918321 455772897 816245605 398456728 808680824 25724544 276674918 499770726 296499603 926115131 572505129 34915826 247032538 160457414 84227572 213796755 993167944 990010314 923681606 249952886 384808139 640789218 641891343 242951103 679678135 389370460 817894690 514037132 260862372 385501366 129776005 785507902 441207343 827858928 7317533 80837491 402372478 942514571 192472258 439391575 7467568 446950687 892563904 88388903 182568479 252340005 856400194 80023190 547672733 842583936 879013599 466975154 765861931 880855457 651878490 748182305 702318669 752166440 624782215 349107353 705756110 595435836 811150021 850130086 708403614 482877425 845077892 618217651 921471514 722564013 958247279 767564447 787275586 674625250 616549528 171371884 472510791 901763493 142120818 534303047 912354573 136707367 283473849 114868016 666797792 724872460 85544127 830676553 740990425 3678850 388028241 834496249 413743357 429225991 307773676 854350875 3919182 87469991 638727411 194600895 494124905 770489859 948100994 717431662 363373761 621764774 942957171 920867465 983585257 1922033 143156999 988053363 784959804 445723913 246718766 99371118 10576426 96869489 583788110 208168796 469463394 750999799 445352744 408259098 81596231 529153542 814329784 820919585 159662266 269732059 259189971 956744167 302827181 55653860 817262278 290297346 562434147 328793440 421577818 619540455 456407967 884887901 31691669 657637743 441294020 827357293 368397091 13654986 207371669 303960498 248094456 290314373 97304899 852686480 824313753 357089143 149371332 683145053 390984165 994238442 876017584 961113611 436121995 39653870 324175240 129487096 720997322 475864736 915675233 255216297 104102617 210468771 294121002 551345564 239980431 726407287 818387405 402165173 897859056 486991493 357920023 541092669 51013250 397043416 487895721 139892102 633143023 538988826 832053350 24794816 420496364 772949665 554780470 888917358 939377906 634520374 443394412 360673888 65716045 750940766 489784030 885901092 707878964 757362343 846849969 152410235 766880704 546733263 640288049 377407961 835982685 725010340 300447418 582856091 571460639 168537382 994560354 561339844 256154626 862654985 27672247 58561722 638194638 109695195 635976886 133165649 919159709 537407977 149630384 775627517 6462048 720236434 974012527 992876480 635544674 555212144 449766112 299177201 5728675 192734604 321212340 350783695 259289534 56238777 459937829 79572383 463868719 881599061 623548035 973647913 420838485 636232657 166579797 424524917 264265791 228227181 77545320 259812585 555571332 32667877 817168898 579719102 313852929 434454598 479501310 98144803 2466317 215373198 108944435 198917859 400027145 928120798 62322638 17910748 624798759 154395141 853629363 866452483 186071685 203825448 278065940 644121383 354245434 748429752 367822539 735531646 456765953 708906827 338629750 475245506 311524263 777655442 659013325 918270081 25861223 8058069 904231408 935415867 30915267 710105604 466102740 968542940 189732041 89919653 299367373 322437242 561322603 991359947 610695201 505721386 936335947 41977733 149514761 684654935 876699222 789202066 475320050 195236714 414799250 506155323 353307002 293117951 916001716 809838030 493281089 375334364 66708101 425942551 617822461 788312649 764570314 225655975 749898619 37544775 837254998 360034419 758526883 940518404 185465454 503470337 9531927 707440674 618733279 103380081 448155557 838533027 35064578 1810756 225523607 670312233 273140204 767261601 471229090 918024822 976743535 230954320 934704309 233896322 116589407 726135689 805585807 103505433 908522522 441652516 2399120 479146974 115068163 95117868 260541328 868787389 744080136 19819908 233062746 589962181 584283851 547037977 821683708 281969374 924541869 75984407 412015311 932001044 873244653 670876997 219532334 707010385 735926961 34078984 632171839 855064656 51030667 640783575 119188562 165041655 739104536 652522880 439078614 458895328 764925182 823946082 323035339 698876151 416367956 576048747 824916345 340631005 299028340 956581769 12040117 70905652 901668370 229540201 111344220 23574601 527456478 284799077 548606024 364069826 523070366 398603534 150629587 80705566 870688563 954867396 865086015 112809957 683185329 716349033 347818034 316347911 16286884 472516208 435316043 264700202 819927741 364605244 431666730 885564846 999729653 456010443 679194795 976993359 321685169 338312838 184117968 825219325 354223086 525129577 522332607 190912601 963348316 298554386 301443592 631852414 709563918 803489108 314313601 430151736 464188858 369354781 880159568 209879530 508162770 932413366 670599520 193641972 934969310 964815734 366946376 75762151 789451734 512113081 859780731 66119593 846201170 617788197 380431953 272928068 991634581 405056743 583221239 853930699 196732232 946645326 550502801 562744373 587127032 71586148 683467570 476032307 14651028 918819307 892070858 565533096 175196680 97595790 693765301 102660473 977398010 619014210 587917181 45143012 395010133 575994078 312660283 686229099 719725863 885865253 841408086 872444462 904075246 692215237 118979493 130786863 560256809 169661507 884174941 363488441 274327290 27533584 618602568 984425949 388740729 231162876 680349756 270206607 439142234 220147524 583451044 654028310 12566897 108476317 793201816 908967170 876733314 742669938 252039554 298377398 182281290 528176366 612815403 752052638 841728203 660423304 404664703 295543848 174593148 983327552 185730886 407938218 808179598 564502198 951216815 418037480 40912447 478766532 355759520 903190135 118502381 991704432 222592151 488303452 414825443 649737929 841311812 116853835 430935703 780013866 128848007 704546555 591258821 84170037 102955835 768996975 42567891 90595419 305873865 382551655 824608659 517072006 733363086 677330726 456464300 348694638 624475812 112801929 171722396 648838971 563120891 6593456 81739078 913781328 220484253 966973202 81366843 20474028 910011592 359899930 760877991 552415925 532293174 822418876 108995531 136255727 430687440 128963560 4493319 359838261 842675540 344480381 909413972 659362559 360254931 621745403 621355274 365509940 259407966 393362341 725269558 133043670 996612685 557765576 252949138 5397899 648445631 440714922 935288593 575649728 124863769 529137728 281318357 601981860 87793962 824325054 396738563 67845969 682201527 884443402 721530610 758193953 743177244 563486887 840697893 180291946 76445458 971685025 313294592 521703835 395063834 151812285 722051024 587331817 238915604 550315334 343102849 718349508 28757532 854632240 992457292 734753565 796629508 70452560 723077823 537006556 560088340 121459532 194463544 994070713 826090546 562441654 5539597 160178676 397274909 950855933 168488455 819803979 584433222 446803956 24154546 394487933 311538162 840140917 665440840 664390637 593234179 719910959 221969983 95775326 396524950 762248617 592967861 555214795 226446521 632707094 985091881 810281070 432019031 87969965 497500802 390948359 688163661 59427033 454942426 390100288 112573114 823733779 759078541 99903513 796768546 221293392 279920654 17982899 651495127 306968158 95130685 468465768 236654083 234454983 949075597 360829960 508443500 577746341 111789249 478053078 574232555 547533573 208018679 343015429 842553037 776406950 877741211 674142295 937368585 331845781 940731180 643649166 139144358 903938315 417560134 594418769 684038138 122259377 425234548 676802713 853471733 724360271 115736206 949598707 553602673 127616940 779268548 578633362 386610481 746770865 491574652 235828207 369837248 169404795 558381407 20334665 626473007 141815578 219559218 895020663 940899155 308529003 866835831 646264439 612222221 777740847 669125498 841032184 861137542 260192478 28708470 497280701 80121250 756663748 946803187 501672849 815134026 594668672 490732360 762063044 468059588 232199016 967857388 884761567 772011638 661545528 719472083 519831268 434979658 340380038 191804823 524021744 983481298 325410045 33743303 321858397 722411852 147501881 975492470 264598617 412877948 18029390 706889477 27647386 592906340 612555654 747496649 816960583 846266191 504763026 854422240 919499496 199862990 295313503 722075283 883025643 603684966 186017199 952294810 507815593 517670247 560494515 321920915 167036266 988095293 207353515 674910706 494389072 901794395 799719723 53023647 362446085 134027912 557346029 284067328 93774865 309683257 814390987 50089074 835623300 57280076 213039339 933644732 42340435 636167879 921850192 62190665 460382131 383243523 365111360 468437235 517818338 315795200 204011644 766372485 508746350 403612134 765387489 417633116 412372933 467985106 351339889 92508933 743326199 642017079 759783357 5020363 517703908 874246931 982666791 773383614 890168158 21015848 564575716 594570192 842077725 250573676 728671770 267387106 669569471 871226775 475055251 221016813 911456744 982345054 189589713 54148684 667081886 819111726 927302637 605254816 313143408 317297009 960566016 296877705 40106775 200880655 734184555 485376554 157109708 654053191 571881238 6475770 322438777 958393446 473144066 513159 146325019 815488904 444334452 496592101 636490897 601596615 363769078 358903515 566094773 409850848 936240903 140820096 802690471 565693760 111610320 646733412 724123366 410272410 265917836 504567769 750103335 985680252 513004998 763922395 816443461 240070792 752329817 992577005 956623111 596160732 279689036 804466653 985964948 194786587 404324859 316747954 244607164 696157889 696262165 351034811 492774552 363619893 958017546 41216377 394208305 575544576 213370089 962935059 418783612 567047061 269796586 802786846 299513976 338883660 146676057 925203091 267794527 740348398 851928727 890931798 102933181 653197333 263424814 34321578 418776067 120229355 884482871 936697362 640943486 768958884 584631449 597325142 188475580 565627988 259440708 949341379 235612817 894520062 404367004 170888995 312859500 428553996 288633861 797783857 611765297 796544022 999583013 771425544 286271530 36258016 846761261 76337769 574895258 678052369 718606104 705994243 550546692 199443676 855952469 340180629 392523062 181953197 106184431 943268887 526453220 972177122 183899139 729821982 476814465 871145817 243277123 507510430 164125971 741701718 51200896 714101967 257258194 457908825 350240543 897740087 721395505 596791363 762852147 611143850 749425168 558968790 780864470 812705229 781135352 56147449 93906083 509995646 249724134 286952438 352614104 486810197 799093083 51371545 490768689 742968645 667745875 909213801 527440898 368340016 888693165 793285130 153935656 871911402 910826431 174413576 696464361 33022101 296517059 698871446 208921005 229421339 89002851 882554932 998598763 426213549 43831012 714400273 923659276 787780866 221864621 141066682 542989739 846949287 431901446 819895538 725760885 733661602 654089456 205168270 179708254 788011306 142494381 789072551 55339032 44912699 747276747 84296671 885412170 735121705 757804116 219732016 409469300 142468165 949552344 757222278 836996176 439201627 189787992 931674481 633409608 925267129 403306252 232126528 155736599 551646326 457649980 337045039 78488466 529988944 439106334 915641800 802519087 526804561 746566200 898078439 847808149 95852908 628147860 189553539 515652100 289230001 987378493 326601539 13482387 8167776 31651348 248451567 779758011 404922494 67972781 675625507 34818230 135275648 511447191 466269704 232571915 144068977 322340713 280231186 333864572 239827427 226559614 148654288 521762746 814755771 680504675 35536866 708560540 162133525 287066667 333984255 581624260 358950132 171428638 461468799 591770032 739097585 122477839 344155962 663037191 314703065 192165771 954863761 843034096 670508636 772221957 247892305 484788779 844169595 765129861 480014317 441971978 280927460 630503157 908490831 581171722 325209410 374559004 688851712 341383563 69338102 659192600 264632717 602192329 643457311 29513031 983674208 316745250 45741983 85086402 686704072 992275251 904541096 336884005 705218579 28120404 342101422 746082625 773521058 541085149 722420774 86009057 860912238 331893957 255389295 223915022 943572576 381941933 308193634 353590422 635867674 340142871 200832083 153819550 11834574 961361019 204038494 460725730 418273381 518923455 656717637 622813272 856586075 432900741 689130867 248577783 938020007 635626653 877739698 323486253 799503505 826532956 722375867 894216103 715316015 236048663 529068796 8990165 510011517 823182426 252564733 980627609 285194851 192661149 303888405 77879680 92048135 435129283 264154168 351608940 181405655 629247595 451560314 167350380 368880989 126086041 336785778 944140187 990916811 328442445 29375772 475343813 868321471 546208577 754333499 603533340 658945027 81083321 835807351 670596411 762166333 832739341 898303810 119926870 147068754 593859060 82928520 365115817 794838439 175441728 944327693 688821887 484010736 260562663 896319099 877734394 500490172 984593351 900750431 551336172 521394238 494735455 704984993 560289835 178142708 149309509 641134791 657095598 230511804 722312045 260935102 792396635 461988468 473550059 466805150 467925376 100229094 828893009 291270254 66158011 972599559 670184942 576314819 926324561 467863827 425544949 512285660 482619954 577574959 488732964 580309626 434791085 543458589 931629062 987799473 290217775 918271930 5157802 899320035 571212476 196015713 549904670 871004293 81857252 622992730 21696297 491587407 673219069 180252815 822374766 804042082 71662167 865468089 488461737 200523092 633972513 840522527 18697224 387118062 728953328 470684056 794119883 443308041 691222968 613787872 212102416 735374943 239233064 944458599 160975858 326987137 873587944 813978329 216015765 541694445 305546455 149234755 822402309 161390067 243225132 462575010 477672310 660790728 196521184 687897839 656381527 37268037 523904849 358029485 534157309 353670971 788934378 39736195 246214486 245257611 691170349 729805755 59418043 963843207 947575353 329463043 103189004 203975231 709680444 810300195 83019968 937335197 590481540 394944158 762402496 845396633 281480839 767679912 264289272 671500005 799764230 821661171 771431816 79863300 726085387 842257603 175181973 426626508 852989622 611934870 762042911 907929313 513616079 991058562 188804934 897389217 954817439 256814874 424885901 642228916 815796208 967801504 227263381 163308607 953778775 67964074 638955327 910127841 336276002 632122908 56208513 584553708 674625164 481361928 971298938 544445835 617104101 401634732 409599796 802429685 245427140 376827686 534767157 713962411 210523232 84521846 895929307 261794414 783302603 529190782 165527529 309091082 6037150 202923650 654265036 694041928 347722620 29884666 478006392 526416844 496148119 34416028 594976100 38452343 802336486 521521268 53118397 541406434 506247164 271473661 992420806 855393298 794083341 254210292 382455429 752738012 270627866 832687985 101338081 444747022 222918099 431668408 430080904 570044291 419251282 775344852 944382577 997310549 434921649 978471580 81020096 323061115 961329469 341521847 282541955 895271442 717847605 806248552 829919866 605976257 52131659 903891233 770223020 934620318 949118031 595742234 866045184 412473651 296492508 533119347 747105598 313147783 291037247 508589514 378813655 231708786 184155055 338135498 146054162 878322072 99920687 592080433 648270900 164429837 944524455 191436877 653284573 253390901 782570942 991595516 158821606 197778931 28818474 794228115 934354605 184048048 775338452 575072560 599267501 522417635 43394531 329096406 784510387 904730250 984334077 791173876 61720883 54144957 832299538 848632869 743200841 937468049 773494038 45967646 925070581 772078908 561637899 177356195 653828772 892706678 145785323 455383271 243182763 861229129 748174104 926808329 906951233 549430629 212575723 438395903 668969357 164753714 700311314 675655607 888327321 491165152 614147829 714023331 301685021 613475950 713190736 682104647 913976660 771708695 558098622 343301394 347639274 424120569 127144375 305002824 617788247 515452673 120490092 709291905 535664343 21507959 626684879 402454319 55270587 305224866 35372053 821556303 262040455 213880794 735936040 44571677 807593283 689216017 659590690 383298305 216678593 366858838 929889789 172777876 877921938 240802318 560707458 178076198 151413202 514694247 397262327 364004508 439098893 437082897 490996593 64113555 971438316 242269780 770406603 97176147 136937311 748939787 360770740 840748090 797234276 535561999 28072735 6323546 365536982 506735876 11975496 371242230 869435468 989126828 192219847 966982548 235969004 22141122 470733823 790917563 809916611 487449708 978165746 189155617 66845508 792141643 800224674 633588969 811330117 866084018 88821412 603256251 292225745 730755707 797387624 952556181 771583562 384683453 352601298 905323495 187472507 128424944 497563437 704417407 258832564 514085988 228359882 270836954 16701143 713494482 753850209 969742816 379040285 211241917 364133053 947421347 595536687 629158638 402091470 427340207 81414166 447059195 365996914 17290415 518716261 562725694 815479219 960775126 742478778 200630233 646143925 249320651 411654272 434096881 974545010 750366871 837238558 219358504 359017136 54528573 969555593 954592620 919910385 903007094 735192764 677610947 999333706 181522694 994578747 780269362 430577938 954022676 524142488 211271349 930164098 684276385 894808643 717066258 842051499 550733441 310635261 812445501 985560361 137892724 921127331 142685621 223224068 658525223 745728874 331379288 582706395 302672785 185802797 446371866 974314436 589804629 566171780 973738216 941507349 736754391 72605280 541146715 312419758 117111386 388881118 813332577 301723329 541125777 166559725 888046547 529825230 301324120 816508429 570408470 39734269 391683660 746194439 323196997 648718470 660289895 804533335 503196298 855390834 351409264 587829248 148181553 825462821 225161244 959480693 335209643 621715519 483445752 346005083 532759639 129796109 12303090 92428734 860714859 982141364 878142217 937275703 17370419 596972660 594953042 395403747 398303190 190831587 445345563 24834390 257508179 493733967 761264209 553714778 387825346 601260412 201958533 832192116 185839131 153489932 29068152 338841640 375086907 897297431 762528829 965958453 335202026 966249042 955960666 670588754 483313743 230056843 776042808 849125733 906959085 652818293 703970283 985791463 804604143 661329998 617409572 250492497 544844337 795537928 443321464 648384233 785077066 536868952 140451403 240100982 569357954 732862051 393904914 690091397 95883445 936821379 247094367 565736936 476226686 379537213 530573565 175978088 439043124 539624671 294755665 713361339 807913138 329406764 776349997 225264253 198942287 194299357 557633305 454152420 343905758 737007934 783406299 53801456 895110616 424899757 30843403 354398210 156988786 392276757 833864201 898710409 713851369 546878180 339191135 753295891 524544438 777389887 181939317 679807358 717368789 139772419 655254947 926035913 279254387 383211455 872783069 90703883 331931548 427093531 765239334 96285709 648750375 781006746 508057344 543327040 526495497 355217100 228256050 419871176 273709108 19470493 824515090 830349020 704666199 707156906 224248273 260741854 744486593 553714434 559383183 595588448 231534078 458624344 822260240 697934143 767119162 468198973 727589822 303405521 481292355 812796549 50079995 300357895 934490750 433694137 69013662 642734654 971770122 481388662 152988038 525696999 971518963 848493055 278145013 885156169 166210523 712894918 833887027 837096823 382375754 443455048 169036890 926449713 728142812 232244618 660851469 394945981 706616099 178154436 4624629 521598004 45388218 378040094 186109779 390864742 345410393 367664361 409739557 786208299 404473745 919982224 532462187 869952887 692980030 440286055 697183019 481365318 989240349 971894686 475400409 186837085 248965341 934608737 888922957 901667212 725497272 258434181 97290078 225117978 314131696 156600160 114081657 232718312 159237715 99814493 78608797 895620168 173453708 598596388 57679393 11819524 34917322 555697489 686515168 492788445 636263806 911624077 131023651 835975300 91213870 690222110 881325117 496573337 644952341 236155920 821848819 909933875 370129293 476998063 456495915 352684386 888564949 657265460 869746206 818739177 669703693 666423039 247557382 979499967 56805140 582748472 337991351 875979727 410866229 397965043 125854222 745404040 653709274 930135559 777783218 770464822 705056896 81463855 754837696 939048393 784799631 974432172 437816967 581654721 402973486 854989618 901371155 291435079 164676154 916638732 407627459 654635591 680310879 962375545 375633323 706069594 151679802 871498533 213726968 948559691 840235925 946793524 536811682 356501330 634344081 248003905 95638727 852451550 804282559 901678353 260147964 62956688 396898154 603980885 627188435 886145127 37696376 23460083 24869530 33664342 938528738 221704968 47785809 70736607 582146603 156343355 663894031 250329128 669205179 333626613 716772607 409152440 124600284 38658849 627819530 10610118 711499553 324896429 644320791 605436473 569187918 381777082 972141628 323374783 800828440 242436471 656260833 484061516 184061214 621516441 468515504 944196598 554797738 535946050 996418641 811721299 926844231 20225705 495890669 59072075 957927863 617901916 386772105 987551760 742738839 247254476 844637201 612100191 532957981 736427707 61144798 901453695 575006679 510117937 750997292 989865676 505061405 251784364 316541452 537169556 167062659 150620851 855209548 752954057 531518574 992005279 213771870 628787262 159577985 317215564 80849655 754797185 855000831 805449184 592180710 913491688 301820661 140345336 339898876 2607680 626758817 48999529 86958865 851062259 795602589 428183206 418327431 842945835 288321575 850093971 712965188 189109389 98367167 310900422 882565202 784719669 266938114 776497157 92103766 979246781 252565707 987569371 803321647 92468011 19788916 356262582 168747577 818892501 786496476 188230380 996539426 122533480 598483097 134891418 873357691 295627803 336952747 46783830 1493659 211721440 389142246 691448851 302560285 840487111 347741493 796411719 563478136 107808915 38093501 414036706 30162169 996673116 84324438 197931681 766839741 718758280 614423906 831767591 732739710 297781895 751544890 179421978 409437137 384290625 632442957 983945793 71522423 287418197 401231533 772454448 56931881 460831605 210703123 892954523 698111543 921042398 401304048 370560653 707314311 954988628 959463015 208852093 169509636 292091936 428790596 462624178 52283632 500433247 900505274 557235206 796212337 310209517 509070101 182090873 95931526 79188457 292786428 103896935 15672146 297627949 48320928 116199664 556360061 974557669 695417171 745726946 140575370 769275988 497107527 423708081 774045371 763283367 774352573 661365514 228090 480058032 109305968 788769935 269929705 726920291 908378786 174175929 344968204 463208510 119682808 273293355 543097466 19621972 715876806 876831776 628576579 220783675 679288084 596781023 453158935 301968576 558996051 696709462 349835110 796385118 468349806 997525053 513204308 705586722 670363065 546166480 295054019 173958989 289137514 713405111 791305344 957538262 711142186 199213237 607672609 154034288 143971412 588304721 939464725 635486631 78174830 517262727 761344266 520056691 749935602 236102669 162870902 646349497 861889700 467851466 760837572 322102675 625561904 640247900 917563338 962402155 991632721 465330201 500806707 575529506 829774258 704519729 554166226 21139573 217966749 815971116 802817122 638458369 654865485 904155495 875850711 932003567 161888868 547292434 52157497 147567684 177120151 48313508 410277397 561480568 175178325 862997103 999914870 787289507 272411834 259724794 275033246 166127149 720415079 568461507 819410465 37491551 196452992 830793428 350735563 138136536 72901992 981885950 555792557 937837225 863752390 976294365 415259550 342322075 584862471 350977828 423854682 635243796 914961649 597436498 898858436 458674682 853691747 72069348 580970702 77481953 526374133 985755302 481645910 251529462 133697199 358872358 785725760 926935499 27874714 862881052 491271511 949312809 107454849 949144509 363155830 143678135 612221146 93116666 439726974 804379463 985686134 446120419 954107033 802412363 600919101 176047630 71007541 353415999 412788450 636365891 648878102 830552452 846705859 949222404 722594343 332995115 57010465 817062512 519298405 305640151 545401948 656906412 183953302 292587224 783662067 416303431 763680383 774303418 890478759 424704512 376952003 437227733 770124365 803459576 977506451 764977464 866736941 629729695 832989280 865677559 824734741 683247416 628461017 411552840 946039936 360237002 130422251 805163909 386254583 934143232 253039496 975282338 53575828 83631422 57032043 584936298 613306170 785286472 329936739 325097337 782381104 966974521 827127520 531678665 762347965 624778353 234994020 762564469 999648276 623199893 741315167 557002962 485594248 850979358 48828323 983100340 671374951 575141842 760482386 414586402 651196046 402113606 515825056 74420541 96886117 882354284 641869591 869583913 402401387 468918769 597364079 474244908 510102751 836571492 969967062 493793464 470735405 290625497 306095166 372955633 873332497 5808133 529337429 856357963 726532185 832282362 130372278 323959262 873801290 256639775 412873263 162159453 95208331 639242764 241177596 582634053 253204731 925902609 460261624 409301018 345319135 114128271 976731330 657153017 877781371 725055154 195458792 613106803 444960215 528230713 289011651 64971367 407810594 185182481 922185943 308587783 961489712 338208540 962762693 192956338 791026618 188424672 584423081 633545152 800958150 168264103 413420174 592706991 991703774 525608922 695887839 692972721 212312418 402695677 378513143 560440941 345313233 854736957 704098645 950571084 703205741 903812636 145674128 963965247 171414965 753514423 265406173 99195742 303232453 399779246 911001279 710957133 66961585 877416389 736929043 209488841 210284465 573592967 353387919 166224267 187213331 649360794 545423996 535664724 334499549 584473254 253129165 800348856 24897434 23444090 924325425 419297505 649935471 756366133 594182763 453570974 672048820 178860718 662081151 374300921 445230673 42533240 252200884 543765178 833215601 18674715 476194746 272519065 816046396 62020697 438546119 37648417 743353014 750921418 45830343 354197191 897732450 949094418 138470760 393437410 583431546 115612344 788830282 961041428 289781262 663876136 227884074 318532851 403033710 576240170 680247263 469114616 129988949 705395912 602951891 725777999 8932228 482262044 604872445 21180334 44734826 603511312 545287052 583960592 421007587 779056820 20106778 885545127 720924096 481744599 811506548 712594899 483593185 851379204 720102001 521729801 320056816 175484517 820228563 160382827 886627465 853966964 486659775 86974709 385733769 383216396 382314981 793090211 281972986 894245958 522931534 281628849 744019598 391864704 161447475 77464086 753274896 851963202 907873299 835812424 595250924 188161222 939383719 995473545 5928701 213098701 371201227 123578032 58862302 887300587 91084921 27786029 717659109 84986551 614043235 336960732 303582113 731420652 923683986 455108979 742879030 766002780 537399929 436086375 304397714 255323331 525684916 832186086 491565460 548704111 362787533 818112256 971739852 693548192 861272135 603390521 973311490 756720452 642664381 102089783 828756640 528622844 665659272 532131789 263927303 13829313 76982699 525598899 616636293 566318961 703389871 67228774 634744085 831500510 424857780 240019003 623547982 555930157 338633006 891817942 646056084 187060660 500659320 341978871 813257636 283111308 738655761 251291350 63134655 558641120 939804119 181200289 414527133 571199720 840396536 730803216 632745242 119190318 527049193 665323477 212273228 67783278 531093279 896507255 995023982 253111473 145055394 70834711 579314722 673908417 268694325 205243784 423914130 810234955 235894102 209223248 16577805 424902306 244577688 412825435 5106791 960901080 468782157 756866835 476804819 645024899 164818764 688720712 900109639 629677391 885631464 258697184 518855942 851152127 141808131 734878227 172358600 34421963 432479500 662912900 389517913 653047695 579736844 121878792 93261396 764297216 179650949 639664291 246716153 22954546 637320937 300016988 74226611 392287115 148458172 630116158 571076199 781221845 770789260 761257901 673891268 498804587 506160343 901009587 874009364 766381585 383998293 608917629 216429407 616517370 803261224 9130662 207773996 778169783 517022622 86297366 567650118 953728036 640668155 314223410 559454452 832186757 648127007 100565352 12313408 501951546 277067661 174971009 13103948 307129001 897518800 481736377 463721536 641764019 339606296 96021511 880873376 477967864 916538921 906590640 337629930 47042319 543846432 240658855 840815340 138489931 639420674 232814591 38506052 237400130 679017765 243412871 812791214 255086958 724708187 749329364 305871323 790837281 426646784 704382732 442512976 789123942 814664417 551972056 985652025 980589576 639701439 993296745 872618690 91238445 914177306 68265246 797577404 105730882 259621602 726171629 283223883 550709431 577633087 914463527 999244564 315819227 401745980 296717536 663633468 731497575 61834600 348213024 85090684 331507865 515282006 146479049 171859107 288332606 873864800 45748824 267609698 345549963 596742200 787147157 787581756 451007129 172119438 328523352 812929042 372024435 130669635 993947322 277569360 384979619 528131432 88546324 459892596 310402333 381519371 402489905 763343892 933983646 427496869 426516551 126225858 811038385 455071655 442952550 552647979 548737999 343282576 242896488 708244515 768297497 296103653 393190577 109462114 734302198 571045633 154445393 195734817 802820020 425384632 12035197 998371869 186023887 412477274 351410465 813428735 845576602 768827822 781961917 508655405 268874583 364972691 53719137 870265201 997874352 689994089 985508551 977540336 98899218 96950625 556164903 77945162 971600845 171257656 495779810 430102269 716209136 567184888 415538628 452798505 52457903 257603272 329443159 865889526 194968613 238285564 481476808 854839326 540507006 5289971 770483636 428441114 133287737 460844767 854827225 999322656 907596830 430130212 730050951 448141610 418676094 182691782 658541871 609841444 277265601 178555070 386171554 831604648 340076920 274886936 672602990 670661807 464365951 530129213 79368276 433588407 515423134 418978852 618603565 132454417 567387722 11157400 283017637 767754742 391517518 894064760 645405166 206236164 684116076 855182558 457381546 734233157 399262027 809843928 919956516 500268086 857500974 900620384 984901338 122281935 77852230 530439614 13242280 346555767 720994215 188212666 477339443 260844575 118327041 381372363 843506041 186683885 280839425 209139029 405155333 192294531 769626904 379321859 162637516 26244663 809841402 174464106 854308441 351557680 284633429 650728641 987343460 108104782 273168676 871906816 825482082 365690656 997193599 861554662 54960991 544990517 5852890 872879984 367350969 842001633 349056390 52846360 689724670 222977744 294922227 587990116 931248528 748938957 404559378 822455953 878454060 620381576 942801896 759775732 597372110 651056299 801459772 269098442 745513519 970959587 610072577 228433275 251346622 828151782 135851382 718273500 280698998 91566018 281117372 454414174 267752130 198136367 262112600 97327855 106124411 586856745 132046390 820670021 879667094 148117229 917011530 93539514 967006366 487079035 700728673 64405407 424645688 965263332 308530669 120339052 181659426 731238406 753404199 245246241 871845156 661854838 564885621 95196128 163580412 28373109 914165613 286460523 623733678 993661344 953308636 970515067 991864449 825367515 396912537 407031527 929668438 33432482 475254935 631293626 19381602 110101886 140650902 872901780 868479903 39459642 51831844 346473502 630019473 675145728 556724756 610968180 856709648 492631821 730642422 925067567 78374494 45288182 326534902 106017502 259342625 41647203 319110484 87238314 706148539 258503518 117245441 110843983 637743937 57496046 687681150 333361331 224103619 625044165 246547129 551653956 32304610 472690675 513903250 985482122 597546565 720054160 575434840 492426107 369494417 82771379 49944085 109706656 452574865 809924522 387166087 308718833 252950190 630370652 268895488 504219607 264388489 685852860 514566232 98832154 168121506 770516362 2493396 122663853 812027305 968383748 211729162 964080907 726903163 338338154 367790103 84065259 395080563 253973775 246607426 224449408 590098294 379031377 874997701 817591554 883395349 304491540 896876651 557080036 975451403 804460074 681809153 827457343 848604767 773382580 625386463 653177718 94040910 254092524 254222055 49615450 359948036 615272970 715785022 220983438 441766728 823753357 218782683 31397377 179677955 131993700 925854242 992319537 635847791 50623103 763424481 151954743 665010494 329194237 358379244 175905239 320519134 832986480 568893551 98768124 945580948 64568394 452316975 448321848 960339406 308086504 118122009 281312936 277682065 422134182 569818653 876346189 989290720 393737622 738178752 616029063 663413356 252067151 886580846 14210785 794943626 626915482 69146982 757692150 954604484 750865481 682593543 498173526 25369717 135560491 970556832 258854384 775071707 592654520 971166061 866164281 899804947 185347503 605211128 223932307 59283076 230119601 496902867 822387517 995869149 953811222 516284754 435734363 89679446 533714587 718182266 164409743 834129504 575579950 831772392 209868008 817181822 66835478 622556525 67818072 334756551 736164119 560170691 113632962 331753491 384470903 589164013 629475391 496895462 912510936 60301945 807426365 426563387 2362868 170776502 595245982 283975752 706632217 892222879 145614230 241412371 150142025 411000830 946428601 688644135 355232950 814985765 539780090 318220796 809652065 221366194 118997614 566026077 824211822 873781550 605245466 35494590 340323667 344996075 135286262 923145635 63795248 161625574 121313068 138159629 434889717 999943949 7242914 812466012 314632617 828789093 108901095 948263475 928184997 981382655 411455344 238668291 564915853 418340992 535620090 606218845 814014415 620949768 172567849 158668498 187923421 110963559 987495838 421718289 35825613 985476026 558379909 947874753 519457107 552178167 925002307 98646795 578795609 209843993 737392139 670861720 822234470 752904898 743176364 182983800 491636485 958692336 703265500 961237045 68980882 504734219 416561548 745508297 614099746 787223845 472067645 734786664 378808710 526427755 251546702 5982504 244326155 903903788 496630462 938667143 400549869 414578146 204760401 465198321 602789816 226862584 699864145 410439809 727075234 189564715 952110830 878515251 389764584 276866171 472417489 174670185 148573091 46966728 301999581 461753308 668155796 553062812 581986281 322233049 17784629 15403426 890410154 662211508 232016178 996133055 200181944 538740639 105687991 552203510 929659198 366883769 615737343 10466158 190074034 600147151 11318656 895765112 183445216 985987856 313384170 862712191 703885911 280952152 916595793 259565993 810510196 900610851 19571053 382266360 16936051 42664346 999780220 220750256 69018825 726866389 981435589 553937340 577964405 785068315 566425786 622390108 435076133 43376255 529008709 133224007 867952714 590123976 372805453 361322236 490062718 391327641 329806932 754968377 944875332 865366397 754173959 239762133 686824833 788158254 386420927 554662088 15995235 835365279 336201963 804309589 923412546 413558273 329735749 218012585 740474180 544967936 987505106 203614715 792034003 43561688 385647267 395162707 334149594 406839733 403501444 521561544 733484382 693434731 918050318 359173406 151022971 271569155 856842944 92404718 790221239 960646553 960352387 71842113 459889348 869181230 853804516 513503460 219418136 785009765 76096304 286964211 394224287 550441311 331038536 963589105 936956608 251388448 934349603 704642537 115836433 40179750 461900793 166658983 172989615 789842765 202746867 91821386 104871329 530799364 247502254 737041063 762303265 983419196 708963567 259080877 479307777 423977034 20259319 625335989 755628853 12047702 839937897 339532795 161820983 442830868 426145028 481264360 236119468 173592058 12091896 516678213 522222192 31473521 800537753 342973764 33142760 899974437 33750752 932293790 114546722 992422832 842026723 947273983 873918324 716446358 320912688 653074205 519932206 796470395 53113324 54671134 384840990 146803477 846437887 551914189 642850674 733173704 258218952 608024511 449755507 635100110 599854541 587903427 64787565 767874596 700250471 891118388 78784289 578086971 972008516 694709021 286483714 579926039 256055766 159536621 70983103 466218179 690577253 430980398 565215096 240344561 105275746 534181563 422813771 124955226 686416120 138205504 975641721 492056457 328465070 22102826 977775800 705234619 796372929 206654554 366994007 438622355 408116230 134708440 742575788 530764411 959505530 879091191 88729637 132472530 187944419 88345728 102242079 276755692 365761839 697196833 956999717 203581688 865154053 673361883 259779907 173029494 755441844 962604389 793739055 752361197 182754397 533047893 674322974 143769224 449504581 374986368 155393733 60602202 424441386 69814675 361287156 576598680 888925012 281066583 514095192 34672690 118735258 14011818 941390775 686623484 409284872 36308851 968108949 621260405 37095091 553656604 957139339 58301534 987258345 753943796 289533565 248130317 661836230 44849345 182476833 511789071 156124377 649022190 724765706 627522399 5715869 323671949 904341889 835366176 652811033 827521078 355040812 160903085 506680287 207060892 964367598 836234743 534267036 796324260 164775987 362577305 168786946 622917886 570127908 686531869 565999825 162090984 65733661 457724307 348637599 42147298 125081785 532826667 50840596 315273923 902239027 660176361 77282465 115856264 466317025 18003299 299892659 760325063 94833588 827858025 409591240 655333735 428242778 138337983 971440725 680341050 885663334 268041704 740984705 351582164 95595505 159534399 175612284 438613056 77411169 908677752 830863272 159530963 457174797 268453430 477764293 941246778 98826879 107711000 935677350 368764305 213035343 763811165 222341065 677615410 823382784 531780621 950074645 94599002 188520742 139084995 147229882 630252820 242725970 599899452 373230247 198972253 92467589 380964131 707168331 132525089 114421915 605277983 730321246 732824641 412740055 196796390 385222651 508556897 561501050 959738111 550795668 842995543 42574447 378690443 391260817 85077884 947137641 215465208 692326091 150501979 438051061 744945744 522410068 492434405 542012204 170383821 646942818 184036587 806250671 124865709 361824932 624449223 259395852 759496016 502505953 566849520 968544203 113775311 177150571 606964916 33787352 741885760 567036839 904263149 945754499 563876380 832131630 800941240 290362685 469053674 127715562 950130998 624939917 115425130 961572316 17880370 735681790 157753839 543050261 950896439 261998996 101264873 352890457 721330911 680652403 767858329 252169814 767945565 418796843 591858590 12376709 561980683 169821537 732190333 470159602 402097421 830962322 884356307 369237503 278365095 318475832 864951896 881394092 214988700 38887208 562131701 842393277 912524490 489974441 902990820 466880766 285378047 787615400 469692104 264773703 107176150 130002125 266165397 202825125 400944613 79881130 279824536 673007867 900163180 931156436 270795413 64029896 408716596 673172324 741130389 926550667 67760542 689561496 877576194 472750708 362080093 130504521 440951661 586220907 757713823 181320090 229641646 455572866 892764813 325490069 613891030 267899379 847382272 363973326 136394584 790910074 245413875 978538047 808125675 646562105 949853089 146673450 103975596 750117139 473466823 572276887 812828687 916983561 542659509 388722437 619418003 729674184 306415442 116711706 348002163 306155611 184066192 666186591 342274479 944896257 465339678 758079069 35395891 278690358 200133780 851585834 280250021 330102816 73787972 279887710 246001035 729850513 84219669 151986823 419396193 470348630 57982455 597146436 925283218 129053603 909023149 915059096 884479706 518891348 540210395 317612564 231825747 349165895 10000131 804473117 422070141 145291453 344908791 695529949 157509185 535053587 123355132 887919063 570840850 893121167 56345646 92199757 613978291 778077213 856486785 775542419 180796586 748574306 759423019 937747034 198217699 171155560 799361422 927877502 805779393 666951834 449103788 585352332 930531709 986950797 280760233 652168131 214100730 681105488 436533391 444219798 940289260 154140577 799566456 636535142 111923147 570044020 703424316 926564307 356475444 42259703 275968505 58473475 790809708 960197305 489512859 741512482 746134426 178917091 927492975 31576704 292932209 977749431 237701836 88524493 787256208 708660022 159828268 677793780 443048959 310048609 478760031 867970692 791212758 413491753 771813876 194065767 255088571 391548469 202111271 51676637 431685745 774299027 36831943 282436881 363297085 123055072 559919448 85894037 82401299 486944562 987454712 635051211 361003607 761074372 133364957 587547236 651825638 897104502 421295923 826402611 571274528 448977473 120497222 725503016 490466390 535570419 871454237 833133253 256278237 417687447 495842064 702312850 430093801 43830712 492349712 554567028 446980774 490914794 67408456 678225361 404741963 307324384 958328279 478484645 2812108 112880107 56051980 820512866 185465528 910716989 173999688 299041387 585250723 908341177 321917915 494996176 899246307 203687893 273403486 644478281 294716023 137843015 812824330 820057195 551708861 37012992 329332825 301549358 497542747 297495285 265763976 976661738 49200169 168226368 58322730 217575164 919306908 930735590 374128247 318678906 2904769 640323898 282192698 536231063 225063501 545082809 743799944 195809299 701539321 339992754 941087306 350088596 466197312 992357185 638759183 380322034 622821443 913808184 889306215 760586882 328848928 864703071 741730213 966308660 740522270 198041850 285205545 981064888 610718303 545382455 740565974 17801107 639050699 794189682 524444011 843994502 359411340 607583244 454057225 534195814 672295000 878896703 757919783 238058061 471481974 659326035 592276481 862247002 825061871 710186877 292552520 548105319 496141959 416819225 774305411 679265227 844632349 399110974 358881647 523245741 964473137 494434910 251673801 180651588 456694078 440786042 787026936 532049296 381810258 163015295 725671937 702338150 215813849 303952640 525678410 552348880 156682908 520854771 321389962 503802538 619178802 389231609 487900170 125176979 807150702 924945451 462915082 777664191 1908935 967291582 50853362 367701915 437955748 100499388 579076032 160905048 274310050 461176082 141902745 230942358 807090216 991849170 869721293 251005280 413723524 575118758 690131692 540216002 519312791 121108620 514982580 412612301 389997742 285794893 43593672 783903351 577097287 39069606 632702268 201619976 10603143 33697658 368935104 444320145 877125866 737876600 11076014 359657353 56357669 738223314 377685839 640036115 493598929 483515779 402877209 991036894 672673573 683484490 44640982 762880173 761855607 510978626 489877167 598702687 959138371 491373277 190472397 785641064 107105747 778966595 841354192 426071760 993832655 574030370 57288194 516188314 76300355 526357635 530637355 161429000 29555048 544884978 308091694 338298036 355546465 835140838 557079702 528653743 548087919 164331871 147968574 903007519 882148691 747587769 122523004 155475927 245514753 207640381 426886649 939733971 642960307 438693728 483972492 907242666 844593506 336682674 92345788 851004393 844748227 329207089 864019314 429831278 24534485 374701990 849260469 2380070 247890871 965833821 289251191 176623724 229042028 149745250 494188318 370761391 809493057 524706839 431260535 376932284 650495995 581548527 702041194 993197402 878632261 762006326 165692782 878534499 358622785 308012265 507769688 703901344 269378612 205807425 32933825 878481579 168295497 535596169 904516027 172798336 150315913 216710222 285657206 593533882 943913363 437708806 105398571 981881010 741770273 682448848 100205777 72546634 971556639 772461 751114783 955247284 933554026 547571802 465443220 528614194 273549773 59982184 238681451 631754677 264051182 594378077 504638942 64519738 219840592 45690721 123937314 732982292 182944776 831394084 431876246 721905739 980254908 874197839 726512561 729353304 19530728 273732740 441002196 322341267 196422657 411180657 402678749 967227619 89513743 189888545 62360323 625261553 700759162 271902870 332744820 580029061 715431420 844714331 797433991 577183942 459821687 70662070 413894567 233788492 48855791 797234304 580283362 251651330 876103402 776492485 654502580 906742980 301771889 711490100 365079513 435243166 19978875 98263694 859454722 269159345 498698789 387690697 735279464 994317708 264197776 35380200 52246352 575268748 824320499 400312888 915386703 172703007 841348147 934708378 954262742 908047557 375560395 606138684 41945782 914184816 210066162 515339026 603487108 328843022 161686355 669105354 395282945 588322694 825580855 907507204 207618906 123312328 230395107 717486694 399909623 714758913 187827900 341211552 618814807 243987224 468456720 273800993 571371112 962820106 206770563 822175459 942044986 928871138 563716751 698304654 785983569 674636872 154865847 372444474 830046708 47659476 513350351 62441486 470810560 165183888 651746944 953077460 616241473 78622960 797671969 495100699 935421089 576124368 910534841 130132455 730170978 679520438 444494278 660397987 651917583 395425141 826244615 96176986 708804884 587055424 430846351 622545857 577912201 239564535 811077091 345977887 683849279 809515374 955678145 997287735 294024514 661653769 411226471 900547601 483393506 980915348 469353728 473804211 349081268 858210901 290031582 394971019 604866140 210408055 614030474 728860016 360841715 883254569 101666052 245904714 561600841 967308086 186816147 57537946 752650385 79226375 679413273 297259807 852867539 808449911 970640392 308945582 810032152 202271911 917810573 421600193 340986811 987414456 403474530 772403689 913807622 294527051 819817859 750311461 494674720 995631754 692940941 233142278 299194557 190132074 455137544 478534351 328773944 227682491 630656421 844387911 605609788 790391200 95098841 289906645 979163763 725244575 784164032 187409156 101946368 347200940 690716809 67619665 545920703 977285981 83175182 538217273 366772804 122365206 689216594 513405755 720926114 374436514 470026288 442985347 384867008 826959991 905703247 648130296 781201229 576916221 245427883 809803047 911399680 155011809 879260273 575778387 150627570 330972787 99761024 282106156 127098743 552820716 590123183 476649395 252791601 103745143 795023020 327937803 343454439 552978376 353996671 750750921 934896791 120877790 304806692 69000691 595714273 721559714 356839364 677497464 197527911 704509963 41359128 973019100 904346952 378078470 691208346 862468219 506395374 377232558 458700670 906912166 8054379 268361902 398130099 709700718 920415595 656640399 709930211 974518341 772961978 52326204 994812026 495282365 842849446 107684258 212583391 989855266 189191530 186611857 887201582 788089828 110513818 871579615 329905058 489454629 291902446 141467540 861231248 498749831 497465521 90663869 623105762 1879947 537158770 131339642 968465644 464043247 50485524 26333629 135799009 272967244 608813693 281450999 416100749 495535871 439210154 584142517 57716912 83460375 267584435 331436313 178429799 777738761 641171749 258451629 305568285 67945276 227940193 733949885 18515990 323041226 6941628 649303782 663049977 677476239 726417489 79202712 270250547 209109009 448354603 517097382 208965079 967830103 600239514 958824723 643167168 792603201 171607459 559535168 59299717 386637009 668662187 686976131 381732677 793863869 919415093 891404464 227735622 720892310 429506197 681501560 946632650 635328744 592185571 360057494 196074481 303258104 920579013 631239504 47939830 500118029 565595272 190551219 282531340 708341334 407794579 140452353 269528859 369943439 382676917 306064022 520795534 945277137 833956722 253031494 852318217 809146821 774766058 517313556 931129283 643195600 294717797 224151269 714300909 994044113 952377559 18255611 515175887 19400824 54851868 350857411 69921507 943341739 826251153 206288792 642123010 552186336 451256535 70154667 232974913 173411907 971515794 949921120 354739751 334149070 209501749 980627445 679731508 250117786 416932644 639862908 164375514 438109362 154805967 984848941 200283615 660185409 726881049 22062493 258805649 967846094 16392774 245013735 980259680 443045286 309732761 500007437 730132863 932225691 847879295 982998110 364387610 696959682 176793600 436047930 363935677 550899767 703941040 116022555 700606035 267892388 149690571 414145838 577079125 252829710 995390559 766709935 904349180 216982971 779245055 39625484 969837343 153819359 647885820 369308620 592003101 664510189 793968863 209159824 105199037 674198693 695928420 930456182 143763565 415670726 70388929 532956464 273289072 187868444 281964277 346577257 526291563 916109360 710732749 444989483 725753722 966666115 95886253 353993775 223220067 671094881 909987409 618066092 223617120 554335758 694227118 420308404 11995285 410720774 283001647 845916096 357956554 730848326 309285355 134915478 786868012 391652682 753542719 586659160 34004722 437858783 444482885 382127313 253926258 475624358 394018545 3338568 992825370 93309699 757654209 710440343 996194738 427116289 947828663 121828824 184364525 502987672 894840846 917089873 870925052 409868258 324694849 510321682 773864706 948541287 41238029 593594679 852483447 307113714 194342029 693053556 965493736 243018039 110836529 533572278 443613431 637137423 975472224 419998610 965400027 706122230 411443699 283558671 136744362 791187974 688238443 493170456 150956799 699149609 529522787 392835681 955740266 766903582 660212708 195045696 895861450 881930358 497569526 411944110 988796368 860651270 199576231 184921899 427937118 610165597 332614767 242384348 813772052 605589591 131885772 406604870 493603540 645843605 109868893 433941073 313036821 994952620 125521304 618582605 727096689 64924078 106548443 652920199 809449982 631797395 706856257 929399268 354706390 255926243 441354668 431912058 354255704 679101078 620731947 123810756 100719893 846816899 153789916 869574086 694220887 553578651 662591906 93244775 124256356 756824727 644705084 630143613 407495413 224607834 689354876 668937396 143334448 904144407 917131190 811640613 631274652 297619272 388693698 221218031 162409763 914743760 57508359 736648928 362006724 306641160 187571860 808413351 477749399 441114772 538937625 12343235 893575892 842448672 590925144 745145756 981103235 732344496 190864841 430943108 498574400 977263001 500766263 703255858 855322326 42558996 912118396 977574459 173365979 105528660 335403781 441485528 748351072 150878740 423299447 279708032 591687828 720577859 807752688 351068627 514650525 676459072 403558971 350910295 240027427 440598968 199217870 431662716 206869455 783415365 39720363 672209554 667198089 714697758 652949813 198705893 527579618 404769082 891039283 240385473 991050262 376250423 610764983 168339818 144519357 89056396 646401968 453930634 484420348 38315821 416865619 891749046 490780713 944743303 287940643 42804436 707531096 602577326 528897481 115105490 133464001 520159764 451390010 672346571 7425651 504093786 802492669 699803379 862694724 628272956 699670354 239792484 250498166 855837390 26800025 164040574 6777275 404098298 59246578 627554427 665763180 117658171 711402321 629852994 216260936 546529090 873068033 243179864 629641155 511564481 549486642 905013076 8009988 584392240 967945604 828950197 982633660 783854142 204863345 659475179 128358818 965626196 365505115 216415905 706506491 185027707 666609355 348853229 756481892 375555245 640406583 593557617 133727824 770568790 832331214 533288545 74933659 306637619 246365077 759952310 415553756 105474004 611744173 909645732 735452033 78012044 564382388 323647749 507484764 578205491 340664756 455719831 204015449 777563151 652294485 505373018 644289782 546872426 497044418 633262519 310151551 310306948 26563616 857983624 158599259 750953450 5812235 51965780 347815234 592085329 292789694 126867475 207618725 652671060 238336432 625097293 882366875 431969053 228135717 72275153 256189222 496648588 333772831 636155002 483728827 566452729 221475149 848257280 955924497 225564853 158130661 652925467 624201895 624172666 989669118 848779304 918685106 188308239 141086429 978626550 332877994 200640484 955239951 661420604 25169691 788866725 617128793 117614477 203863620 992684666 215219278 460374646 413184821 431194015 92988994 880685199 650919264 484468868 683109718 894247078 327331595 250004155 8069390 354267637 206389045 291661659 406317452 897986043 126689908 495769993 254111705 456534685 410774823 987975967 703621514 166859148 932882350 642990534 715630704 478179747 69718917 714365271 694397176 660167509 564140155 167218520 290358760 956200026 943836608 407229128 197450911 963196403 359760108 607312530 37033034 857963687 277519215 747728478 512068219 789202149 218343985 693007570 903775362 938628452 963440105 55848907 728165687 466667131 228862540 13186461 278505122 450960620 708160343 700925488 262568243 59019369 146403653 471122151 690390197 935436214 220354385 354332071 689277879 486186090 76969984 656264981 149733148 148091106 474637804 389466379 248504111 828496281 655296192 726214884 385638334 334638445 872673634 951311599 86768535 364995681 428796263 170034525 809729414 477884541 273260895 890115662 208712931 529228059 454835374 435806642 192837272 754010791 640347594 338225799 494056759 448161452 794060812 3161619 809751267 757454661 946146646 204956270 269573303 897872775 260551758 935346070 405702233 890359177 121633527 775027728 805291308 282873614 686197501 199338258 83655678 733351158 227442582 676161956 980040515 409652437 624113906 649502938 356174699 668540699 150356763 914671799 531325608 387279682 738531836 788507412 33702689 767604768 402739021 394724408 638709453 760978489 372895 898729592 366507782 801199845 286722670 839339086 807972204 342232148 196361828 269719186 463669341 186325934 657902424 437903398 666784145 527302554 839181469 583323608 109481622 23403508 103216743 777764907 693978838 384788024 252977988 101598712 620002154 771335061 607434666 113696122 801976085 942451258 207016987 245320391 937251281 535002945 588575904 88875226 238134085 433465050 923915616 992491778 658873092 632937073 744663679 656425958 740534576 853930261 871523036 583918753 992403521 804061433 281418714 482902937 859254119 527641854 234174586 262744548 55426940 772558143 703447140 690839635 880470019 703631559 450016059 815739901 211436406