4182 2004
992859357 937782798 115035547 260321283 513376060 432730278 525751396 52056407 912660083 975114528 21189680 479094083 758146059 377900211 315820675 28360067 389286391 103942983 955548470 673234601 111923177 799047864 568014110 521333872 792523694 581689303 858897997 911059884 687654506 618384248 26131634 531727770 471032333 528622935 241073049 32294886 99574359 496777202 146412559 411030011 802665104 855956332 432798287 403134135 695364259 779833988 858335476 681737907 729682696 15302064 676515448 148811676 354573468 632136614 992756038 286113454 608418149 257853945 652165154 426980526 305270567 572167339 264859118 751139941 473817762 610164787 4905347 843787967 261714099 990358234 681210646 462194237 754593963 608293477 65443303 72985336 947395222 472057686 542542673 541170381 91325746 142699958 689536504 56851291 426174553 142272673 598471959 932795950 788646193 454181631 179352706 980886244 691254460 152046299 116872145 992686391 237965563 287597540 852859733 428116282 266538474 929860131 497059188 721437731 356930130 64482576 418331281 605392482 94441829 726167959 221558557 611418959 123149887 753012886 706140778 775116992 856002251 158400225 338157921 60408131 918452010 974556524 597560677 933032484 206012624 322711780 787804974 320635142 169790661 1553562 699660683 642936 958042577 551515147 621036124 248262245 517502332 744795442 530745120 28603123 843132481 762077633 943209596 470618191 985869560 977470339 544539158 793839341 862146462 336025961 727641301 571385816 940176334 491052521 650405041 306305545 9200684 989862215 78865952 118618377 190486802 62305685 826411430 719370726 298213534 715635589 686869580 693758304 429866500 22550995 127016897 843687442 653893195 834789721 677645035 361557842 699003296 129493002 356419685 662073757 180114341 676171052 610919378 217878928 620493234 642177701 296372619 520070716 966165094 697809205 12835690 365130241 697764668 539643762 391241347 79514359 248624870 122002138 761263869 849594425 643698635 501591032 125442212 407553494 346871848 715862852 306072248 953601812 478771392 735026686 789920633 945889111 907382059 867565458 730174758 451156525 873467354 416485046 141566149 352553361 421056260 409951954 388155570 419899160 153940565 418372538 209393901 451742580 878649272 746556010 86268692 567602148 972309747 684189161 881815809 834566268 217025810 256548873 155155152 789745354 868102455 653727463 309542913 523619823 70837038 449108148 480886005 937913529 342724889 567933464 368285505 909503267 376552439 170536611 41068432 88974226 607003292 358868769 782105587 774674794 462569982 452324781 345218206 464763996 525357157 274339565 254384984 30222564 624008519 200791039 254651979 61794364 744411512 130438731 980509957 667234075 564772992 948249464 494069904 377056341 467571507 63108899 651939021 701788229 719643799 614596356 760296045 594241368 321526837 568297662 278817871 732615397 517240699 894514824 984855287 190406778 926192217 56850568 438505056 717284322 693578251 228776131 587088962 738042114 216681420 674037289 866112200 250816574 574360838 771245545 751315234 47372509 34234338 223132657 140971074 25558506 778744253 916505656 22431877 873246197 444812799 762976739 24132015 978032134 131610815 149885144 216505494 886249854 109611641 831838568 344170591 556217031 43720364 570110128 736572430 753114013 669087191 134829676 248607172 907986036 866727879 646929498 972083815 502614688 573586878 833498153 363331330 897508684 753519217 294981170 95647465 92677605 276864211 837264026 741994979 531529852 425589992 327945579 452379073 707334373 980771639 253955881 164275002 546043905 379443600 830016085 16637888 202246329 251412638 719797382 745757492 222871844 564388302 717452152 988103326 844887832 145300874 448772089 957603393 718750624 896486921 270848874 27128474 420267844 878130365 285173686 855837412 347785871 241077093 934679231 275055441 610037372 912970880 915723190 708869278 7501870 975135569 503120076 692083435 415701546 913067827 580575550 931167786 32456312 208246710 189485748 403006186 541500910 590694424 541493078 495408218 184444599 768645204 618559916 995909713 34304196 147923971 539972344 568914237 3812968 313469900 804073938 447003069 528306516 23808470 831114112 623504954 290320835 745618110 210743500 453196703 112526706 419987979 185358165 778040298 165027231 225767978 286714143 796486704 393039045 445137017 257937977 538116583 664223054 165642980 402130211 651916015 988513628 28826112 818134030 292395922 207944812 583240294 134027136 959922656 746279567 661907982 503734473 888610531 22159087 417471496 814676985 468780783 985638776 358040251 745029625 516681131 492095731 43267191 534430612 355304667 236870089 219194420 798102879 564553298 568440839 390787313 54348998 702589380 719539446 6695692 419175537 943341671 994522440 489926524 920476675 841663669 673625808 832796571 7475093 528429186 802461852 802238165 442714594 884256500 110875390 759137998 539089469 657132935 887095691 109783546 853154556 577539140 893414796 260266966 230709885 25887093 35556126 194935925 833977176 418482529 437754869 51725028 32472671 788354522 879598982 970248513 164438015 310150934 893155121 598335387 600920518 968012745 997984663 307343705 744931309 848974159 872933505 23354549 975571575 763958580 541127824 515950360 830742972 430368711 38400955 375822852 418296620 542482308 450704680 343414775 913553653 643431887 629664240 442839487 137946243 337103673 564805961 553573133 621701058 159309278 134087840 586460083 547696960 845615303 388094507 282356715 716164416 579793765 269996178 189321080 433813160 38739582 332040354 449000727 246471233 663764517 140291200 266449181 169096117 113854412 93497620 815541969 606088561 668195634 419024722 357613632 346640160 6883504 955498328 568158013 433101810 561344518 220337327 515463919 262167106 316274563 328007659 670499119 388439064 461309999 533839575 409545396 613978268 872075879 887285989 182817317 535009646 531949095 419572210 214042275 827347685 486904765 886740619 530616153 252654313 699764932 134592635 380155520 74316013 901818198 105131036 572993943 506533090 848566247 292687612 287693864 948444267 384011613 31146191 763531670 874902908 236176300 579977426 532811292 629489603 513985773 566469557 879385755 146778188 512322566 148619376 164331525 831330505 530769686 197950546 763618330 595273973 735937390 275452435 358570766 49225612 919552656 317900162 541398650 323739594 753871548 548862086 847128938 667446391 714221502 325145713 333369433 958387556 216593197 738224601 123179618 13888824 880427976 339369780 729683064 587985702 422417110 206811713 230325634 62938693 796384116 609149411 918584716 655898996 511918415 435748307 425879810 42539693 562178137 140313352 887360055 855511606 212720009 923770263 944489841 480814745 339393442 748774685 383695064 341740342 946460882 504600905 132507550 147498821 913502819 394284173 331742871 633156645 116054312 545157472 11702656 144797119 467646213 918693193 349564966 939767648 903957170 494405130 798345368 899969353 754391948 129850465 690299608 849475728 318644915 454680969 464866602 852028947 208763375 29403082 829966411 695710118 87854625 639453401 914842438 213612866 178833532 769687002 231915081 493602333 771099048 212319313 479335550 896485987 828384839 316116682 847697501 595431457 619503979 895094507 956098573 190878507 12907610 480408050 720961961 271316413 847853692 781563082 170359592 645968785 767650096 386866297 386606964 462056397 633816602 508393180 373342572 842323047 507481721 969311501 98459261 206849854 902792065 145131084 247943745 665786391 515416588 128444789 133630395 899463923 847356138 524352297 717794153 693363379 901277560 813364128 941111659 957585036 843265352 862440926 722987224 496482554 571600508 341695047 724941104 600871171 275570577 745642393 241625271 16086010 42500530 766149099 431748188 116943705 223314625 747103217 939313676 579334588 886678660 981178832 402781848 846891988 822424665 129687838 774048775 648652458 175871977 284112275 420006064 204536369 961759939 276207990 595400857 761536243 51122643 685858309 587522468 951229257 699437469 575910347 648012871 975506242 808066313 290782763 786593617 751933073 359740858 135927677 731944248 857079089 809921502 141455244 394466169 23232099 445647939 588250887 121053458 653668498 897667983 361402274 783524347 886556504 631932593 389601826 111612184 21144484 948255636 838861345 326547910 288016070 423776072 495193600 242817981 838046593 653716163 420023397 646265270 808267372 15174945 780267151 551395627 54716794 892539433 133239220 717604446 725937307 502404337 995470766 437852213 154944663 672343146 593354787 442674035 874626528 584857065 498013632 17619167 811952617 981910332 704754496 163001046 480394939 384065766 832269107 772829779 553833402 272680969 778202531 162266279 73502032 375396318 219800712 2428785 119575046 400893489 250834869 935058103 644509528 655283927 871556022 970296240 918139922 18767318 933167271 341998643 206948138 946843764 935558231 605889683 706518043 26113741 749765639 90560601 372529922 528525169 381137129 402187729 31258321 547245831 983734970 106148098 281749412 430184222 573583918 651896271 725187337 464495456 747266939 414696237 640524377 631449511 219066844 605198418 543134959 43542611 410973027 605262628 477957853 721254480 908246788 406326301 779814064 429149548 115567801 498793233 775939782 553129043 529405619 260649287 865147252 14266342 17321482 44051950 710247146 350356123 123472488 99395126 757369420 62823626 648046429 682097808 530605046 229229240 958556801 292528768 592146844 55629110 5525353 502095127 652602928 532306732 174193742 657630425 448778067 429826912 615957960 708650234 94790125 118471907 585116320 19470796 885898530 469876298 834329559 48293104 753040163 672955603 479933906 184668702 154172279 476019412 757932423 156893148 785827785 715016021 835481219 315426238 645255465 228957045 166970995 319942891 989625424 293639408 384577052 182500319 264433804 387529826 156682550 17815445 765586843 507867243 700131861 592208366 787365638 588817323 209083292 661268520 124781383 667644198 234834702 827165365 463371996 543627079 975710078 29318965 21549165 228609994 70515880 910135703 429842618 136053176 556892311 507212459 759713920 606331832 898971687 302579997 204366098 497588158 594227012 592476380 522334713 772375245 979171790 179486114 544336239 75493450 241656922 881439848 792784155 406976745 63028411 587406793 843899950 407850023 399453059 301220273 332301548 492992558 854775085 895539076 176733035 996484492 194868657 760774502 825920787 911422047 425759465 271039952 171531886 396062520 779941241 690131401 636333558 152203263 27123446 747164807 610240986 488895243 396861506 588292860 387886120 638756040 226798041 27513705 8388128 880167689 122044775 457263765 630899953 663887516 252125430 971360231 488621948 503998196 196475778 836167755 209779537 924754908 763190099 559024414 28394089 795614636 722313965 778019649 723928340 433437669 133110108 678527766 99085640 210093954 912489583 214582032 983351110 373830818 568833767 148109669 734575063 112447647 401121246 471795878 966070350 254440686 925240203 468069033 105971512 512688100 313860136 375061913 538024553 851708672 338819151 938090495 273802921 684776137 800473669 187768054 632117082 591144303 453655865 360253946 462049162 386868890 679499446 166970520 360548864 63169294 387683933 112705476 341782416 577153866 716358870 34743180 159170115 832387409 804803460 277462800 475831902 973894363 107138509 984142661 405741205 513688144 224489292 653187561 816195020 629686083 354133151 768164074 136880459 485247737 365584798 529439198 390782294 146479338 17210077 775445026 94981722 146884710 962781878 294403246 637882163 52394628 609929519 945953903 809173388 85784091 378867247 902833035 47593645 940673995 128448201 875532913 662063079 272111197 680997635 726995658 584720368 777195249 797995295 570484976 562522417 154724788 128401751 391294868 898442190 469601368 555692298 353205943 424604222 917785336 732495389 594931771 529277467 185208635 685030499 122000834 522036642 516971606 413694604 25817448 263704026 383526411 312045716 555249932 650957119 357352408 29328160 336521194 842914446 972224244 565783218 928762159 997216427 627036625 433638139 346035076 885106130 506325823 988948712 251118934 234888849 949436179 180160004 356582907 571785636 288856471 508156976 570589999 419931567 398618849 401955842 962078111 124107700 68807955 26603053 441209474 261078111 681045807 150747202 323630106 528612522 108957826 255836417 716129171 129600977 624377048 966943086 339309680 866222857 466788065 782408273 607293689 237867030 13536753 822122662 962220971 429110835 858960247 476423341 840976668 419408680 977028398 427225310 89271106 628692682 708747595 532572615 642021974 334385214 664189801 495064982 979429326 142365281 505656455 515663269 898687353 754578425 605293229 600383249 683165386 438077179 114580582 340099378 555446742 732057392 547915678 102629749 909827269 439295560 124715729 729851166 783266649 192336239 586750506 717592732 520851192 318136158 618382438 479600413 333515706 742361457 473713355 219867850 27004769 10874162 169626169 146511971 564451016 214155000 675435039 673495253 829115823 23447737 280541882 25046568 452310763 884015966 771564001 68000046 963303455 582842857 359581475 930520145 642548797 797423558 472550215 442857539 506299595 447107511 967698091 530708003 794006659 705982644 501907586 179592337 789617919 279227547 377170549 945675526 556006173 258170345 549615091 613039071 878666360 716013135 674227930 421014783 964302028 150657024 200814524 876056185 613834364 744972339 811444412 850378973 735397939 458495360 900793876 47297820 776103444 147228404 443072425 860747853 540047654 121232998 756514996 398519932 526758600 390137417 258005308 615903698 928068850 436334636 205506554 591877981 866568833 264472216 120530699 554072670 439258223 107453791 675983356 39160032 842415160 776243922 693456926 848752475 169428363 182516278 866402311 864385339 209460621 947237945 313836141 727195548 848885819 571324208 750066043 341387326 891175396 356663843 543861309 189913401 490326762 91824922 621123377 422930207 201933041 891858487 164043436 708196559 763571120 914339328 78193642 470475227 1379424 142713093 264129497 309776109 569747451 131204263 971216316 516487764 28828592 518964349 927753099 39477805 69967935 778594353 836141009 440288097 577310159 521170861 841668383 2306105 218946578 514946826 453709882 275207597 42321538 297961751 868447074 54394034 97869773 115738519 599881682 981438250 842073913 956519924 426983321 140358960 252819531 669790602 457784463 644250119 980183042 355361173 767599957 555742217 795733717 310404213 559119868 330243565 470150699 226653733 74219066 877543270 377040979 320800395 441449753 195685169 223220967 875301369 606484830 158391956 417230995 894075004 19503999 124882432 181227665 190827490 901579532 325902911 902088032 809798854 467277273 873291098 151537828 799748851 596525063 284853622 135738606 867558722 552085618 927434626 672793202 302220492 163237953 699285216 125723737 582884845 941383091 409923097 484111047 837077658 390295196 524299190 63861654 740684913 219181056 222271394 538335714 663875623 101404549 761635994 810774629 361630915 730632774 863014881 988522562 789817685 168230222 40417283 33535592 125033835 490096033 431056119 309134102 442736455 517682885 463331569 773891368 521446632 3381355 504326300 325374801 803243532 727267433 803143805 391516692 222798933 454280448 534179691 780415466 71975239 354854505 593845820 41797176 947247010 790116508 339137967 966538403 277767227 336717040 144710631 135743924 822463952 711533614 335701499 978555508 770864837 939392747 190875218 310555925 508434673 2395420 673290855 253283105 862548587 158650333 374100278 845916133 244571067 406426444 402128249 143463296 477921857 76481329 732856537 387965447 571950283 351044076 831418689 541479922 473845322 660356503 874793700 913691904 595806552 93995257 139865764 290625964 284813953 410292126 293363707 415648570 234635495 613978987 13494214 768084488 125979853 206273198 952985582 308556058 288921564 149221542 739799779 573110382 929523716 200725592 35734155 636070601 531980042 889525111 72225074 222948399 477469141 803168116 929923672 46900837 25537876 609726461 521895577 269592853 38058681 48405537 414625277 695459044 438973151 491912959 176235447 241664975 166504716 718987866 360549904 317216545 337363862 919743355 999253008 27930288 747900254 3321610 388156605 584981535 973333153 32119698 265422541 733033933 554841340 940532608 761455832 164690129 161815706 857289871 773546701 667460735 248361187 332686520 565565330 979785811 288298958 737589775 20691581 461436851 915390037 383411493 785582198 266203053 222460388 625834925 879231038 312614650 784441370 930008586 552077580 276192326 717482268 907386746 564746337 927994893 359783048 563578608 231219427 305115528 981409809 629646342 418558946 742641671 137124540 677485992 596637937 248509049 998212039 19999717 527191272 793138414 884991010 331241901 740059426 436145879 382923055 995386425 957375571 15885301 805813262 349122819 379165058 457361498 495179403 941574860 736005744 301337799 359469850 607863982 98058450 202727259 989540548 943708661 659091945 580133306 70661717 473436255 491960017 595335038 972975714 451401192 626265272 340783251 548204040 47284344 800795281 45787359 675535147 648896681 679616534 823918913 590271346 593063875 287294928 647554182 866559852 9122263 533253184 410462668 274512180 453467235 718576275 734727291 342989911 112321008 738029630 841045463 916164750 995915663 752104397 620098604 320179731 317108526 873968196 579295563 872917659 934607705 830298174 830066986 563723985 245488616 539538058 481290923 982238617 445989926 85622546 300796196 707958185 379766596 441980774 839794037 889377615 689951600 731849245 396927591 508770300 88275917 684010798 221988391 714233789 573876888 610460473 413369170 425968738 376857083 193672679 420341022 302303683 470078069 266272132 375785050 212786326 131894642 675774227 307057590 451563677 938231066 150084532 34272238 561721490 485392092 110189918 33921302 413084231 338869107 469566724 550744385 587774183 42511285 962253838 202780375 139871362 5274343 977650669 741486810 711339493 677351274 974665883 192853298 774837392 591541747 477916593 42705635 45808022 322168765 893124099 665068426 636460640 190155872 394198723 773441739 12392978 959596737 918703835 6881674 33228065 369194629 772731288 674251155 413380823 427000056 393664232 978935446 433639408 307540015 271703905 978369711 525061864 894361862 314316702 681352087 210784193 582616445 21235531 948236609 633625683 11931243 91595330 54636576 135636765 525383863 115555942 526661312 155152468 398051323 324253223 839733838 548715062 656664293 455052198 327461631 715118460 390699521 469069651 903689156 730351430 228161050 614327990 425362384 557876350 601287484 438979490 377780544 965547268 580095773 156926376 939878729 581603197 269589594 324477555 7424400 240994265 26796820 146092317 620403279 126563290 344138889 247342889 23198781 8741637 406201063 568949368 150429263 690429637 784645216 170686678 734361874 242605770 720349294 479456123 859531683 964654084 719072352 134505407 566662459 91507502 354984764 812068958 323284680 507029628 293640709 686822433 72215044 20752381 642953927 419072296 801042127 853502953 176104026 829237755 502513897 249974377 396901497 630610738 559570155 507929389 913347542 175250380 439156893 339549427 129745643 840977763 772580561 87759502 20006504 573444150 828039930 522468060 434193746 811375102 366658162 609667919 484803238 763807984 832095031 715677569 315560664 552567970 689849108 114897610 368531452 751626530 374949012 296131913 740322746 851380675 723366745 568257953 919924735 785121834 356736623 801304293 140006273 662792619 665264734 529556216 669183130 186135250 405735501 969842638 961079707 942093669 41407300 546133649 124848544 252339866 521638900 77155954 594199665 508233238 971859641 624111239 258169100 407440524 690849657 907260707 394249005 362651872 321085664 113518141 382254806 688777194 764788929 996015883 658124356 618507256 918693418 431526808 410204789 178339193 502946217 715968032 797771207 725067750 129870269 894812680 154629535 790930347 451666581 498538452 415173657 344438111 118983001 219557127 439531307 33670815 187542809 509251065 246332753 198326160 384963992 345834695 309033245 761360839 167414532 376761106 815232379 967399114 392245171 955053714 620647711 581694429 108030096 840211166 790630566 830444511 954702827 391280105 352953930 697190371 344007098 785141730 15340862 946056728 26061768 353106095 134124081 411429184 968245962 834108971 584961062 456585022 250474464 820677591 363077049 99955287 715135147 931430227 81511580 653996840 904662359 540635678 850132563 928957132 64627762 495158327 70844804 303782060 420360387 389665844 643577899 311639988 4557511 825540199 38568559 219214646 692942267 452464798 714879026 6587568 950229210 207549637 209808474 564155950 258273605 564346386 602312635 363430568 102130417 449011240 172421740 411032190 700472159 638118548 927125280 870484954 953259529 329615363 210432900 973567841 843051330 519467199 634008611 836853509 645460076 628517018 529312029 476057791 474913353 560232539 444208956 801479456 162300391 97407640 614485885 90929208 956437389 650556043 844150337 251417281 215083593 211058876 228510953 811467727 799129019 971960756 814599963 856990193 772588057 826332495 603774261 687364925 661582297 497619509 961408319 824980393 67276904 487498328 698219506 461634408 927687882 742927168 418032233 184369721 508094829 580810095 7134708 475200536 911030358 932604538 837153465 162052851 257831453 661921917 999078334 900928188 184574106 704438076 748010491 228782040 21347774 819587441 433459758 64284795 663444217 589706667 775068609 139596853 154326830 595784163 954737986 723865422 844065753 458172549 645007506 299533644 299791586 949654834 319357406 536035667 886549254 361442146 38310020 888480768 102879250 623980472 378127961 585335718 338699248 931895654 217030949 660800217 446962099 726162177 619719985 551370611 409471973 161577294 100220363 906237204 165945775 91713388 811239192 479139233 158296986 516519701 797150762 752593906 982652294 738319555 469442915 207639078 514609063 115297447 901764930 158456214 714749290 703613253 894876466 635501766 616332276 459245363 958820941 644960550 149073128 652238495 71751573 246364590 251984344 47513073 569803720 896367259 32464111 232164618 41320954 719050032 794198151 890256663 89147710 86666519 638220178 311108566 591173434 543488185 189365733 743898692 788826144 704591096 481904186 87381977 508077361 428548549 826071806 253168388 389320095 740790802 783625314 811696491 744430910 536685757 133001559 556410708 632223439 312138702 536242734 693706530 714663433 250604523 532124700 502819856 465502614 989127963 827331701 759236114 607361581 271217458 574326353 63384662 468643967 668107626 118993258 967562644 362068219 942888166 352388291 827833989 972464795 829867347 391258067 534820540 924882983 168606581 298690976 742689707 782439621 49244579 678959201 990851100 731129632 697730952 860657897 716150797 990347133 59992948 277227195 966876114 444225369 805781579 84622348 90385545 305937122 947124413 374027552 807828168 309447804 523471501 443586940 859235718 646717911 41318238 636289942 861445307 224381584 970006265 387223649 417553543 964581168 368508336 188817946 495158113 496833298 981653265 514035048 693231562 431407189 758020044 535949761 236230069 302789933 570471787 486986427 571157229 998365019 259046944 498111576 965070930 797838292 514225950 844458147 9447971 253746583 107568625 598869193 997216282 417170931 517783875 959583503 17417252 508833666 387408589 775555880 272251083 856800553 878606852 670585960 365715106 55506108 250761685 741772808 933817258 686963023 168828634 39829639 22009531 729087242 489060075 685137260 762982748 824209000 240327755 313523501 118054341 650600130 598608062 367761768 413100973 537878101 23062362 777110059 895778396 396935073 739454597 674900952 166794615 182430533 249011793 97959555 93045676 455080354 197973448 800036055 922036967 749514063 350196508 577652758 41060342 360342613 912698627 778486028 587579440 468725278 557182113 899100232 971738133 173016032 34289442 125626642 659907715 205567903 82552815 653940621 872253524 543668861 684539998 172714034 109984712 256383464 499026305 318356259 898698144 404076118 534111274 959509709 232564226 277422533 459896190 719025892 538415895 19994579 555888092 426826306 773724505 413853858 432260470 83980661 261536179 7038440 522701028 972769775 683169404 759249261 570325809 621684029 27110303 37961800 292498928 711966246 728324090 829990019 771188476 459200218 831510477 677421355 718464377 354538908 677314201 827997542 219192699 379631474 20238753 548266663 301488214 510596884 617815984 181701521 626849076 126481760 874092702 992612407 610212364 803155141 744575505 152836956 73816400 936946880 485171582 708353267 455622587 532155589 96229200 6326343 600393294 870125910 856256643 998744299 878823846 698435837 350267378 151404250 766504028 980952222 834746704 220346024 993130806 169664773 247833388 410385029 640512465 369137736 578623130 895767338 823143730 396800077 438272660 591550854 494974508 810152725 206454240 617432615 975920935 498092247 503109271 46844220 760143918 785977220 985171874 231367043 407368850 766424062 246000127 760134150 264679065 435213443 548376217 531168993 583091857 143713486 57966378 353953822 456070447 468999603 947457495 130187978 395287065 425791333 58045932 948434249 369967654 753772788 792492725 595451860 96165225 129771540 989273502 702094670 249595019 418741836 792582728 278572800 693510735 569322503 298094013 542974535 76830865 767678706 40212896 74408883 429966010 221286761 89168062 710526252 725906835 477281543 197733452 578493020 996883846 278633476 401928883 569037588 865194715 281234018 414820081 243075445 309852270 82120838 490951668 535881311 887291612 943910030 891599633 153112776 60153623 577055588 67867172 498468046 434649108 217530658 137124684 309439702 766548349 487926236 722660106 72412711 501690679 283986030 365227536 97298868 119349647 847680806 379419140 682349716 168898832 209868262 134312375 990657399 5152482 783831787 401698995 624613065 555733366 851138578 368685987 605849095 411052816 65002962 512412450 938947992 705000951 240096491 145018165 519463225 77128922 360608110 908775369 864151908 493758256 701228714 963003188 895171666 468835222 654217683 578170424 607320856 416913374 256640257 541709326 976298211 699421465 529749825 472422407 256827822 703651399 304941895 905347969 226108045 733666001 403782528 303226381 160985539 915339465 367901971 942809817 271127491 949727060 935295680 848153656 941828768 67025668 959447287 440684461 873002248 383972357 435232531 843186582 83914493 815967582 776900924 999894135 34591286 971064160 9282938 920174856 48520277 747215763 42430976 762828122 198596107 465796268 213293880 795498907 657891361 568074014 345562176 652034287 182936864 89587412 325063062 397092213 517359218 542266138 983681969 794963652 295619175 880932270 975009254 408514619 137151197 611469884 306824417 271130601 405227518 162437914 190688853 339799350 217565219 566641471 836561547 121605533 292094895 830643426 60249253 277482192 981626314 714914974 131736604 109191071 88558381 78611622 827859343 64027973 364901369 667156775 936722603 282313832 932446150 51222964 872185850 216783784 71824387 503858123 647442674 727218009 568525634 240268826 77445094 881033272 876839515 215505533 965909668 610532352 590783887 255069145 901923339 424091997 559155123 136891986 271634325 545614857 952800789 812781367 82760583 187639722 256005435 841826901 359264232 8459855 223766804 968908079 402100372 850515005 194187638 319352485 897404667 400821393 276340296 361400139 890690593 718347883 347741468 676772260 323082501 355945854 571479601 86355271 625171541 359370987 486015470 582931328 138754993 697097779 50654875 164058427 889735659 440186808 957894161 784608261 610868067 36936622 499472134 293716814 107579612 632581578 985656236 406971497 578761953 147616045 863482986 65351373 823120064 334452755 140787974 842057057 818449813 705317164 947346322 651904320 257835085 571236322 646945012 650976622 531403173 921051624 258438071 89775024 729249642 642165099 939907713 698523045 93478760 205583018 511496975 959213052 489938529 233211165 50415555 797500124 739792865 290198165 97320863 428184541 965536216 560767806 9046866 426589784 745852338 95779178 782037624 663836713 571019445 941377505 975725072 952240662 723604634 669090943 520343853 248564265 602572079 450958970 712996890 594153168 643319673 613409913 306907266 626534498 403325843 882400260 267891383 737947212 721328070 589106569 48673671 126251401 232067016 558421666 330987074 717817689 385374386 559388087 631892056 796313787 698807557 200784476 670158191 35478946 364971647 642377488 789573596 336271657 936701670 499385427 232539173 447628123 789196249 976505833 320873925 894605962 745801156 766919464 422419950 677401678 679243261 879037154 625697822 64940606 330810013 800703043 89348525 681189086 413393319 612910640 493667400 822376987 503483769 365710400 833771545 110931917 301756119 606369476 34576753 428933015 252100719 189070195 169516062 198209801 746525074 146745424 635863057 437514750 57078689 958426265 235092828 547720937 705417083 824549125 73954242 155481666 340719817 637562592 198438645 136629517 96684023 899176096 476051750 710729491 475589853 953359868 62912443 774698193 588185588 455025424 395624584 485501613 30663690 119969088 814449588 544279141 93679350 333826749 760527047 640933799 411169534 967689377 406500653 664591839 67913289 729826334 609951628 600703659 400372867 471599366 467227401 238133915 415005356 594526680 438667208 730804023 891213079 850157886 776800351 490219263 621117798 449243191 711867555 217678157 491217582 852481598 495633834 414663185 759971164 83229398 150715432 693340657 285124710 84374506 621671503 17106235 97717669 766486858 424162011 323225534 915350285 135384200 537343613 103781449 689363005 81101900 907591103 707154382 182400636 789099809 548433850 134319817 165306664 843969881 693370559 68904100 493320136 914595146 38633285 145287634 59866820 43001776 402754428 93872661 241468708 193930031 121113403 119342399 990163067 54324260 471374790 647397449 63784547 836559252 785552826 872703616 776464737 645382774 732694869 810448584 215667219 472633242 740743251 728537636 833237481 575073502 860370588 270834962 620531961 319550969 466648187 221781577 73386629 289909200 763758565 143621601 922730655 786901906 263937640 867469639 639830369 762556194 529337883 498849164 131712915 339637551 45736421 787271742 589582574 410719184 193489497 383997913 919613248 977395326 690877269 614158965 97562140 269211805 229694907 902065420 889578552 282914006 786046783 860940673 638335532 107370811 491721704 524072812 795371819 33863924 109932212 796970439 561664217 328395711 536265544 332722662 290438673 485985645 467397206 227426338 753088455 546828297 606521544 823211425 566072867 177334505 25818834 528309886 626948372 358493383 902700556 112961694 700759180 503497117 162920779 807861042 793250390 29108030 537556533 270311581 783798683 538120775 949446497 227676167 707035182 663149510 133250079 181344724 782131812 27612527 296403004 54729368 41194731 505995924 536262796 158385930 564031505 790764098 617532269 495240408 531463123 781199933 124463189 917794090 578060214 283724937 671845104 715814765 644064979 621223770 672782957 19360319 509123192 784381731 736030544 89350848 616807463 504270743 665648179 330057900 501018377 359143424 415546155 951384168 341040235 307258046 607994693 771511486 474774283 969297789 698497957 167321676 828499947 80698576 405289246 391972112 301440456 628857300 580503049 69326519 498737516 777955935 484071945 648982857 202404023 666953541 862670866 643019937 629949128 715470056 147303000 520394916 570035129 440691201 236113828 780839068 899683544 507028682 722290801 141376032 547264234 929962824 382257828 153138925 1082913 204410693 259298207 544010384 970814162 115098089 948700555 133450858 309307545 546515559 279940164 646810896 989865189 481436586 228520482 571184594 310106611 338457814 460330012 791974070 86241620 978032504 473549248 266321766 516158652 243722842 905011923 9436779 397115308 172813455 143989368 540249834 39953181 135224390 252279772 175194213 333258331 822637219 35563955 609337060 140876636 940239638 16267163 572944613 3322646 862291083 181497033 260238869 769415690 26791891 271722800 299720613 138096282 509695979 462724936 276978077 353039224 398770814 112788528 772493628 667862951 321865975 650277466 118545454 160460202 615837403 177040200 772840692 689010394 37718883 827966183 488068952 516379269 995656998 698050673 344763273 973101251 639364410 20067571 318943974 642629968 213116658 875341264 987944250 750860748 95535033 822089363 436230867 750568952 862245235 510862161 95972192 827225123 471097208 166837720 642381941 774970939 206732891 992720795 971660285 360280345 435057662 825865057 932923636 380173317 659247974 595703332 90077738 284725495 260509158 414798945 252591506 806890840 827696806 667010835 365512630 961480008 166668574 848567318 806368475 768244947 762909219 808356805 671522469 708477841 405770498 825500228 81734047 15102248 655504929 581066054 263186945 697414443 533730906 239811507 128183131 213107606 213228965 409891277 995424314 54153443 190647823 614034624 786364105 408424970 356438464 607358660 792565405 183935509 930926514 12407611 553140135 560656350 492639617 644280813 818100015 465103229 483824018 914687926 280753255 130298233 836228363 739604239 411954232 874869600 307365882 819719730 451633700 232051042 560189941 507963060 22442224 853732273 55783965 726459922 8510364 226918500 464955887 396834095 309091668 937358851 192856120 779710899 738487422 824213042 601074409 923685730 483489651 960070278 819708869 470231002 595618684 353420351 923946062 728718254 104368262 584889317 717613233 662948403 867430246 399527566 637654534 875485382 793012202 420143518 147520526 170286591 114753994 568315277 347187711 292534973 986888425 748515960 143516277 423937318 676868576 406410589 88112304 520930108 691546571 861189301 738333024 235343637 609273192 990623004 168982529 282505763 712329390 583911140 506634773 120742026 608530542 344308101 241060100 237092105 496116198 963286298 855300387 324338239 426165775 146839425 534064173 752785111 229586384 174909326 319153585 754361011 793392115 480994766 361373615 209382429 223367877 269123503 129868788 402272433 368945229 316393318 366012387 655199489 972684549 93782643 352077889 271806217 764420852 875683048 651685463 847215574 374987220 299900422 117518404 707750160 320931176 429559121 690260130 950234750 629595805 666912723 41717560 385704094 224435114 625841213 49927979 917797732 557494510 101772851 327858879 687570713 586168756 111999079 916907318 56052075 466461083 561796906 256029653 832730360 303455144 26696813 904895544 18285569 141325866 925521280 797655738 639790129 489229924 156121669 420946642 319183811 486440708 661863188 150578125 953502071 176606622 415616264 510044076 676621049 980734993 649947672 585869860 88720694 52567701 175931384 957160058 431809264 718004501 398342632 486155907 344928201 626660923 636593098 298093618 190725125 929204246 737447580 342974216 136635213 666015973 340382013 600814667 52478076 472743268 953515335 967335270 155837984 668178796 768100158 7452560 427512295 673741790 395324699 293116454 351582086 333973466 658658059 150877297 45555988 795602287 634810231 226979275 685488044 333979575 834719277 725402111 551167016 188049148 546182858 687296428 458930734 941388133 976916879 591536332 292396268 909824462 663075787 40983690 418775271 757064521 592805019 952358070 642795325 868325345 767602731 65221781 541443588 170239242 892234038 986008530 806502338 868638665 138764640 36401240 104353 809065458 232607732 359824943 198103158 862031346 962748998 34289436 359805857 429152844 612534956 231136746 731784693 974034301 443729675 918190744 969333711 378995085 61601806 571167335 113536009 502200759 682394602 654627678 554451516 326871341 155435731 195711342 915389439 775598246 149439469 818150250 758187762 6155603 668258197 597572511 846379985 651434464 493539887 904127015 889348170 111388140 293924909 561629487 668220355 186052232 637428896 664818713 521780186 802204510 97777568 791780907 64337246 453127284 827656395 959321980 694868487 567309188 170718601 715057268 700407156 352185102 104990502 214603502 619311975 589251592 365171355 83286546 490428008 655349573 510945057 582705248 396883795 130236811 994123152 728957301 888886650 387386270 43235275 489351267 468342792 937079334 269648531 444027909 152954670 674669839 379536885 179861418 296073415 533079283 42286049 917943025 110485173 172554790 771385951 599241726 142466496 189319222 529319441 830324157 787825545 374363790 452975019 705494328 784434191 332998560 77334918 173978974 790398123 883992132 18784474 24172325 825389097 305822347 242601586 340782166 369680802 400249072 820549680 614219421 880599509 888532177 64454083 36214211 22897711 981131146 195575563 522391983 182291968 959802635 795864532 414254880 899707514 31284065 945757383 560010276 728830989 315002151 609926297 579727188 743531563 753714516 835837736 127446550 63165667 539956041 330831105 498480935 794142365 608272104 435519574 753081156 917437772 776197198 280478927 57953672 932013748 34640085 851814569 262394451 776559050 618678725 374257352 728036933 53453277 616066650 769676141 891737321 573840597 926265377 42255382 722371442 691295367 386668326 623708752 247788394 460358225 768916795 1226688 456649146 462588206 785556414 644546575 985407607 182410277 275029575 170227712 662966189 255345602 409316747 207828024 470757538 313855854 457225996 719565188 446254740 439152883 36809360 632901727 387078236 877952236 366468703 819441251 563827271 649785643 74470130 442412241 947351320 768955446 346695030 489022467 178004737 694696060 708485441 613226379 255871472 432843598 338511704 341021006 543506843 838963590 730212166 848566003 988073963 284787276 13521634 336805737 151037168 578163873 488398416 230816321 202343440 192830437 334008101 730379578 215200003 776677724 628728905 116624609 677026157 903588237 908619740 125768279 653164104 72005493 431425092 203865415 628843104 211132121 576943546 732319313 813183396 956508077 52255208 672186008 612856898 158863857 581313941 226594321 968861077 779361191 357512908 624731353 599088524 586553872 232084571 327951294 59750838 875709974 609933656 993069044 131698099 833121133 141796415 269392803 549811275 144505071 818950653 523449512 499168410 197473703 239509905 518387488 833008530 66783900 512413688 507887831 45206909 476530353 469477407 482309575 542650194 972109708 827450833 867773307 600003496 561959404 43935988 760945495 940201971 57540880 638774264 996172256 58954464 273543481 940625614 450050149 358936487 362568582 275023076 531728964 595584513 780118904 258735730 970298443 805754786 471814309 932652502 689471393 314275624 898591728 499355342 731167521 326693528 702843999 280733593 130883138 767008350 25407676 980255753 122525449 274259594 916266592 487555235 701807990 365447554 952093319 41858682 962753522 993404343 89541108 986793313 784586634 841300179 921374652 22702941 114667443 273934072 325423607 425691340 711219684 533861529 881592401 455667393 686868315 924718553 92910462 409056030 245127227 874750415 877933647 690682051 978078763 714936644 582044254 263509959 27969400 23594466 248086037 605911894 150506198 354417601 200228186 383979354 566961721 209727414 778463205 299508692 925667933 585347517 601473909 808556672 189365472 977873203 93378826 713129079 114030815 747151355 328795620 172576098 285735297 571516351 816254948 663144277 131416891 608361875 209069075 646465850 793198381 256903296 162633619 557835674 875092768 399488289 102884011 754940609 588030803 891137205 497875124 792517338 579894527 970957139 961077804 527731188 729759051 967490758 810094674 798359572 343229630 648693852 296768648 199796593 411620919 767096064 909600635 669520185 201485905 569959858 215582422 855255023 476094409 771740570 970850374 233854676 915752303 471347000 71098710 802660672 55731351 35626528 965568989 275421384 851762495 853433189 794891283 132149130 972311172 551520786 601031850 845964998 305473914 459089002 963747555 11025590 714691711 928278681 558485361 394350111 505417908 88562669 755054523 382243150 401513935 971107627 835917854 868686218 513126674 978010037 174944458 359807792 313073588 824448410 136117172 330049281 368672095 553266026 835968117 373807528 785993620 14651426 951356616 110059389 634633866 225896403 694479821 281393714 771090697 105416494 361278503 182033145 447567698 586598208 33152331 611735552 403754129 847209561 164426441 660226884 957195432 346188423 353404364 820467295 206630236 596301528 544811071 723026061 66020859 720747277 404615755 663413241 836297827 266818043 238658126 548927076 197076191 635384224 329614452 876708967 689168860 920977211 23341996 292035517 896394269 67028352 495188957 590421797 457787952 65816137 958688689 928920153 262848438 753037765 345094717 22221313 54458453 886064507 181675235 256885257 575331838 566635257 333474586 263817116 217876581 745786513 101071436 914569148 378778317 831686983 338634791 458561704 72111787 785040540 515241351 446612067 988840943 266178482