4360 188
995367721 683210211 441517949 262554474 213641383 33838390 26224757 870862572 844365233 786574274 121535011 420516286 305010492 502675626 784003573 515669618 306250005 496709907 896515184 761021222 715731733 906442485 920034326 614684885 223604732 725092960 149584835 759069441 921562598 312732811 110019729 54360441 88240933 117102172 195936958 325769862 776524633 121637453 991041443 299607554 968064233 637954524 777055885 869972681 865629914 563628274 852360842 655495349 44315677 794135648 453459432 703779946 409152015 976330829 737401903 414884459 205106195 256410685 721759444 713883413 835857061 586728971 586394868 540578328 924261335 44254974 482279712 77027934 377203133 466101258 403512919 453499969 910211213 441568954 154116157 809836617 45373729 11797114 62390307 197727179 748559186 276952389 855215189 484834930 938350531 192431188 950133876 188332408 249100145 872598887 588874049 911892110 154030149 655784829 62585459 543129896 160445024 505944625 481063383 840672088 907906396 419110669 582716218 37185724 499280923 644198873 617792487 44868282 778771515 189545321 402020400 363034042 418174688 252987155 576785132 661507944 694742688 624503146 689960890 302838439 436059520 142862085 126506731 592894247 320819621 41607300 777736304 733706516 650174437 806197332 414983623 264746078 159623316 400643116 198336496 780893070 736805010 647748353 44500139 942565219 412724137 225928270 861418659 109843529 159643365 379011730 29911248 9201215 786851602 406731911 575444442 562946725 192333951 692758801 624882628 606013539 526041184 112980467 205880714 375042172 430488561 782864420 659748793 401191369 416984034 675752220 326415841 284108585 974971976 413379602 5201507 789351920 394644812 291070058 98179153 411780050 606023245 637142182 478841653 368507695 562475622 492938656 762060416 907083106 200772308 228547547 640161646 432971214 486733194 606183760 136545486 188027089 361641330 704498013 872926639 430615550 451766742 392834268 662492408 446629249 732831599 716118851 394824637 404131827 956076815 994522568 56978745 441918914 954614960 148325064 50161055 570827280 743406086 240823668 330441212 836839043 195637382 567653858 480483361 167421298 470218754 169886722 893922987 887401750 91708089 114670119 433345203 173234860 907045464 32744770 979678943 85532981 306466180 912357559 411061639 316726840 711369114 498721976 607555467 806028942 698655845 917647948 55257921 968291179 912578034 147496964 343888222 641810982 423065270 260579128 628866529 767343706 478410671 11482112 19471270 137522394 883503318 835653524 98586666 137910859 416254723 408167693 726113084 194989184 606163672 326688725 335891349 62620963 165115184 188756852 22203287 510768078 451097601 712122939 131471388 997920815 264171240 731119827 712481368 975167620 668076609 741944263 810016367 284781349 540028318 827569033 613804999 970317575 290745292 556783079 198595372 798525702 65024601 525855092 172088730 966317698 291475053 24056730 395542994 996179708 371336970 997603841 739136402 71039387 971685311 315654473 98610067 595956039 727515869 747236328 133011656 763632344 488983173 124859906 786623571 389773568 638116528 552285664 248920817 184322448 412146063 9287658 94460552 18749938 2636746 351310019 239696152 562461200 68693411 534562703 715933878 798607004 294817708 815221197 517181911 338251541 91043075 734633540 786845167 760132667 75175578 23270774 741749276 738997087 84083579 535075209 420400366 456522164 835359614 413132149 83962705 523847170 436417828 889523239 326544444 814356513 315096960 734679465 57878549 425915316 118508087 838591382 168819096 419220947 540278038 54204321 797659169 96572204 672256053 852361271 788316468 719874310 572230779 258912437 546667462 462865665 928978490 196971210 407649847 727126123 77361236 571749485 20116320 490936370 352784187 223548736 230536919 344158816 287588208 342272523 797847565 961611768 829596750 223593582 988594549 401484727 411719688 480209524 688042377 413086187 886712170 343137060 188804830 25877575 263227240 513543923 359586466 513266625 328026520 57292710 664452077 655180675 149557618 559719382 413322281 817420530 639997867 453394460 256862144 138397894 268558098 912622912 966644666 358445693 969009709 635967032 720006139 454324460 670222221 306163362 911127307 466790491 563389179 62405456 802753452 264389938 549492515 904999882 875671529 509861268 436087469 856102203 623075000 764650139 185851094 133629433 771567076 427655786 359411032 546634563 336902614 180769174 929266609 64613123 624369712 145663942 48450179 227371702 102405788 499770171 132450540 856070033 472130108 837780497 615833404 62103020 75965588 754278549 299634129 158533267 807797631 917595071 53709812 852586808 780394818 606526418 513091136 424846100 416558404 399108003 913869492 454079336 356088119 544198575 16028368 787363599 468585317 915293319 327566965 859834723 617741254 976766102 599479120 84782746 773564312 924596735 77923743 690881457 529877587 38963571 829047495 194941277 654440656 550948152 470059242 954396966 243242599 322502877 146603505 729298927 911041334 98240084 879989961 385523838 629506556 303497047 280754264 744676821 709766607 986212919 97304971 372698533 984001620 451109372 477021875 479610216 243247920 441961859 381829765 388187781 332675214 219379074 821685948 741767450 892344309 254429615 299576727 522085722 7006252 423712045 209688340 491827430 953727680 481574458 639339308 746109719 232250907 818996257 390128969 583504940 920210448 254723673 436397211 758930191 923990451 839259470 761845826 555568764 66570018 663443695 960422268 339785646 800976352 751002472 334344905 4050876 779136815 506871352 257351210 393251449 660193609 219401809 178308039 111805981 817262787 930367348 867475841 481680632 50520068 859392613 998215560 398791942 523409825 975871097 26857409 820167797 167529086 484301330 405936133 65020620 752568728 143420424 598838414 575424256 284589999 401875309 602107874 809950660 150682055 761389247 623067998 567051111 367342903 380910929 818418891 139242705 511777779 695118792 810585923 297612091 2329489 601792101 388434762 799878347 570562047 923063827 596453105 868425957 323436804 334899371 282172261 232488522 385566254 50967561 758237159 295205420 594115795 935106681 861704870 135465606 256913142 366124387 887442777 16061154 509525424 510681201 902924428 744205663 362949641 365231734 265236552 822782513 809933957 86709969 766462744 667981791 536940089 265443346 262846569 475872695 570629907 580977415 533797951 39375879 652938556 138334784 261587754 489323059 244491362 459660669 168361824 500101670 767999107 535411195 416807699 894871681 512811119 614613741 960649264 142138208 44393200 276760458 15058714 811261816 259642198 246513445 372298633 562351223 373837326 702505310 870819901 737236149 427432101 828152987 980956838 536440639 331885100 341391470 560257097 317717762 932732210 558049534 823513984 872013045 448569986 213124045 68205777 839509214 571098767 809966332 133086296 448137964 491094168 21902666 69100412 284346083 764190615 457520842 470713358 804762295 188778357 444378822 834909482 788960084 162724203 613960564 88623475 814443509 186716566 167957689 859917463 78328501 730109912 655344084 810064771 720329154 438829097 987681419 867071442 839300703 155914661 863801136 650433134 40455902 475043358 883440386 794686733 176039497 225344121 31316695 907578415 484720372 547244104 788720473 633585738 489407440 653019122 803182288 205985891 820714670 470873006 939684580 749424470 147751196 856925201 231874579 317479408 966365026 642033236 92683315 19931289 386446182 129351114 611569422 975075438 394269940 843640216 91801775 717359093 587954994 340502953 546435528 362961851 440996784 846506157 527709578 56444908 179497012 114775864 667181181 483883392 564306241 533126655 622069511 304266162 766563013 313024222 333880170 973566524 786382475 917765761 436523985 693004276 5921834 397554999 678990521 441946403 489992241 959520422 64508223 176925961 789850924 116882813 774254437 574064883 158184973 148774843 978742801 902989689 781498484 437346595 608444781 825862467 32472137 159192188 316449795 431801898 332453829 808048356 2932110 15709671 997086248 360175589 824082537 920780545 791285226 805516526 935118578 643805341 799566073 682016888 740781051 985468291 634878506 879479512 292505038 678706399 721714306 130112247 309795891 315554715 923620591 670418219 765973715 652157277 667546897 656596488 192148611 519501177 720546632 984800360 677284264 570558574 851094202 496869130 29097269 286291780 84349406 666923579 668499684 668567719 490736228 412511355 621844662 762496704 534295033 306447537 717677221 15003198 918635810 338294069 365831312 478112310 29244458 329033950 523399482 384624927 139106917 286407590 161284617 709057348 630239063 130179172 984386931 229748885 627100274 438202051 61349601 765674334 305469984 474175917 788293649 653255502 112074489 729513254 839643864 977651395 176204459 659607418 996668903 256566416 319218082 655897676 907878115 639465406 259432334 494997480 441543292 34767247 480952067 816782288 991310968 724455955 482299260 502727266 632738067 991022110 848296538 767548563 374244862 875542731 652890903 593019115 221388351 215376886 698646280 629867031 585868101 503069599 807092285 160809142 579487668 950396993 647232115 589857421 665595520 15857496 584841107 326330936 927725203 955053709 298369935 12121860 427933624 332615216 335628568 469295508 799854819 829448016 807004446 209107807 509490909 244537947 670985877 952047441 813361515 169273997 676643610 169730316 932355437 710991520 224382370 199239752 785351083 38739861 629662547 106438607 786263118 892074421 591624375 61832418 624489691 873299702 579228220 705700758 105099102 275011192 726656078 48552243 178714742 281257693 190973047 431186162 600275672 495852991 228665238 503865415 232737963 692593002 926153782 500483600 931248662 558130807 876003525 283618759 350283833 393623892 828472102 670790370 868939001 442770222 923247100 433696449 644158653 314334941 205503710 888988106 524668696 579812972 765761832 993397736 579430000 404029299 854386073 409354646 468157772 989704348 459085972 137097327 727539317 661851707 375167059 205713163 522698337 982315977 501160179 793060675 873470495 284189807 377309856 708742623 845530006 315407119 439660256 670879546 847971282 726682916 20188688 721774492 565128301 654643057 210346459 308732466 446155999 314649851 75226409 652830197 694417000 620732160 37616875 557151229 281967457 424311045 491555602 665719659 743731733 872464331 989761864 787858318 404121111 284872395 792646771 507878050 472414586 539072137 899310418 824102167 80641878 471727027 207377813 19939819 682112872 986060010 772090332 139470319 480221575 371215685 525280049 324209857 430865506 765988081 522273300 574005454 111038037 60634200 797878567 357615001 694383317 297734766 413357214 123874846 142891761 171511778 914055413 89195839 399721968 179929859 963048139 659118733 837524663 270478582 694217376 753124282 812914945 506525394 762003096 894294085 131104126 199402951 773345597 961288602 723216579 34308848 808475507 894040456 963161634 367365918 956090141 145202798 321405792 625845473 942739855 859576167 366998546 113351339 764926923 904721271 265792473 275442332 569852798 149478825 230605385 761625625 639611773 779231610 443291408 272616093 262025511 72166231 570755633 562437325 959297357 52844869 746413971 105209879 993249303 633048491 100189317 998679352 818267968 621936674 152251771 240164874 549195645 50099213 592613084 107658167 317377101 988128126 581472417 806050924 915356711 893996187 902749737 221476619 51466014 960034663 43614805 780485645 110220715 998958948 619918711 641350239 26934394 682750952 360130233 913877647 490911779 900181215 784900802 999999147 65206282 349134064 988315044 298342540 120113276 883671049 891921220 935593190 820421992 638205222 264755004 759039174 815097244 79839747 632299785 351639979 814381796 698364040 330807328 303738905 620289822 771419772 135252714 198096511 886560350 70899511 696383309 853110490 592789408 635818237 320538451 674648356 704972144 801356074 106779965 627367696 204492177 817039469 947509614 357517526 686311879 247974727 276365560 122809062 470921260 287861294 842437943 586345472 120785337 360248357 426047592 209957117 703679069 752419740 945121071 487478375 129470977 268223150 328078877 641005827 231069759 997537043 649388162 569982357 52187207 737997617 425240797 884696818 180639974 124131655 426907573 456233944 788157402 575445296 862558770 546237221 241081566 921806584 519365219 309140674 210250729 67241927 419766977 315229263 450838605 511220955 789152910 22554291 821339836 5860391 98894583 940835278 748281790 272887834 300869977 17907472 463540093 315805505 356589924 706999745 731371104 674221822 23891919 639111517 516832752 287068674 278633209 714297811 640592698 351017815 442832417 951182558 948111448 435715409 797764316 192664648 321470827 356480074 125607694 904784612 852379445 347065858 553128909 562086007 627244144 233760930 256346768 74555815 144692928 748992637 667070286 140200953 280206872 256923682 229532176 784512307 636379148 582189019 553300350 688922531 285387812 444162180 271418304 29059327 500512739 101961934 837865098 531711289 701654110 835598373 910355270 57846701 461186599 753441166 169593614 102305898 113419590 615893664 122955902 383836142 906573137 531902890 654154518 434825324 925700282 922175479 381965903 822691386 681110341 149143055 874383199 68059623 916576162 57599947 387210005 351776648 298179164 41599554 908216912 685222179 438930497 110406744 728731844 362301823 603133822 21219672 306720781 128854630 622382512 287297244 986396395 599598601 636047229 248290854 183397054 827818083 415696640 402050328 757786254 384383138 981547608 92578515 231905647 42717015 724314600 36320869 988081618 245718028 74745628 413999579 602811427 667005726 577768994 951897658 615136607 236710267 891800835 659814672 977104452 106355180 284103310 268199744 53986640 592622421 964669827 937733662 967326507 142956609 522069143 709082609 719551685 466239645 531117637 70397548 629493218 649700447 432012165 974827596 494251458 301251525 607823106 302386232 615725444 63879306 979403608 172295154 246833242 290175130 170432793 648888854 696677837 631491935 626683803 922494038 688103209 731423851 611173074 93909155 584121687 839058270 640577241 53626463 594011908 991728142 345543000 73334534 148488385 605882903 671768451 544661064 345566145 173960591 706310599 365294225 143237509 791763586 161275264 557800109 107264947 7091918 791261836 942815182 893604710 64452636 564912698 550309645 153336398 685533829 188459898 573529670 503111057 538277503 405875618 905999292 772833409 400936238 962938799 537984714 566880456 917418139 70927848 516791338 668546993 692921596 540117798 122059097 30105263 642198206 43063208 215107305 961407785 7773063 189920109 696230464 900047571 190165357 848930350 442828903 910052130 377503907 961652489 401773370 137608169 734970499 212171912 43630358 955952606 735675908 491398601 346433677 733521714 688898923 629770217 72063869 261903549 815170008 257032758 664562479 898966812 870080150 561941780 337442703 695568734 642492388 67304154 695372418 549939262 121574858 713989960 526398622 943605944 460132154 873203172 850764956 489548972 272360973 669510422 454673956 700261526 919884213 822190474 881238243 586787869 395333148 930587129 783282948 281762976 386987507 963689999 375203325 408650084 958828754 600908702 27882494 842832132 729593843 153496381 500200014 212615035 351139467 721862647 972288752 998702593 484993316 612841512 986565377 373596170 532972697 140830676 590201169 264067615 475037165 895597452 573760827 797702289 690298753 418186166 597447417 406936541 265534351 824733784 41265624 253365895 761473976 268240840 316816926 535744753 371043545 306093514 198170460 827274257 962595340 975040026 380774490 205815635 549315568 985681802 96799831 75223277 509874212 280626032 793911549 23275126 51708959 646738533 660282257 51735980 541114227 678087793 416509405 52005403 413817713 682426237 464483650 903993815 125449727 184692456 341492593 142620845 519647964 586351124 313821366 310268742 51121188 986098187 687577417 344660227 178762044 968093143 279228881 145291956 718654619 984750535 412329495 286337787 755540518 615913559 534385201 532509170 845354701 310639630 606645104 521336960 219207832 816820425 397761136 440471395 769093324 369681992 964055929 533925521 331020006 22984329 654135375 361799066 762760679 82224755 304462236 151713734 803413629 874716187 269364226 714424613 220502421 282586105 102184496 607205326 752706121 169816194 550525818 866239002 963456114 392018301 298758673 496153028 675969674 718497232 760006202 755246376 393972210 733302667 335148717 118392998 691127994 403395723 545963853 392121298 379876927 665089580 585014386 226420460 307903434 763588861 641127187 97865178 969128513 993807765 698142942 357799472 841326830 915709960 798250331 566764760 857033049 521722438 948974061 966248024 797170582 793189747 880155230 600718399 538103477 532222953 128249426 501764547 203367089 34954563 525945532 564546584 17018410 845134142 668074650 830349303 888625912 890127178 727606315 872777926 290492448 326833831 376572520 113617183 119850356 599573868 580564030 263194871 586524323 40300467 375637497 950334361 862555682 151779591 796396006 856996581 568840819 722853426 846202424 611653739 190090619 410529757 909810071 393320700 198386506 603698381 893011572 447954272 468741217 308095475 339533911 197734609 533078665 914475337 847472407 114377451 615400330 215275104 458739561 716982247 984068973 178663583 642041261 501350028 519659377 549370353 388966679 957374019 4952936 988590875 769641740 189217996 90545344 961139415 94976835 120442166 186126390 411445521 715904181 280056128 371449697 59959634 787221032 484338083 469365763 651998836 406760219 581015836 327622042 133030157 225356761 835239884 672493022 25502885 400713661 393505163 841975195 176673009 57496731 120438989 959928281 784270086 94096740 217757464 666379385 985460387 438457265 285755239 139647328 663665664 449795874 519077957 283751654 295148553 182936117 958585678 462024670 281327833 296620708 48487659 392820973 137297689 330892999 198970030 216331177 587638699 816058707 919539321 264911069 949487348 748081135 575525481 569727663 629564376 849793997 759707523 570594318 956228258 749324844 852422369 607282703 251453903 795627395 89821357 876093438 66283698 419956008 959768799 492564417 177258893 682148044 115812098 162374925 5958686 985433164 363802285 972242648 174855209 962374052 904156315 821734455 491843925 300407665 58425222 205572529 557953538 970846913 164417824 493329439 599579635 652219281 486428426 420105411 249584042 277840101 366830727 741906105 243026538 793184313 38144280 447555838 474988139 124522846 714792009 379538982 544092047 529763888 751604181 16428772 754794560 735439896 37515421 831352013 864444474 177239487 448492088 381169995 53424334 782971335 1079910 988101364 329609176 494024941 721739815 391021737 236293336 886487218 396619043 793247355 820261442 477679665 45887911 599100158 604697775 577797228 179685144 210931378 537186192 973550745 862959378 56432117 666259756 590011024 54671298 11120254 116720371 603740611 833841966 451050562 243990442 299244013 705699510 943520654 160425258 588809159 809650480 927037840 86264606 510202451 904593655 956725563 185630719 441325649 466874129 16617499 352088487 284629865 463053180 173144795 201293531 458169182 849025049 776202916 770277996 601117824 493416137 99801315 409954122 809904679 259958828 318097087 988219419 557843202 68243608 918700488 92765596 800266723 535069495 417026592 336680691 562692612 807333272 758592833 886335663 759042422 722154566 833765823 820131534 832441823 778761767 196675920 512459915 50981568 245085785 523668348 76921670 946624840 59114802 762500098 624275271 796224173 740746822 886865618 785294033 396752706 255742071 435105556 771405694 846827181 299082951 218189444 269898438 717340703 980874596 235395308 790136718 396551191 19700054 805895694 664726809 245556748 612420571 181731322 379487666 685437755 998166476 536721521 525572286 13893149 886560440 526879634 996522336 375330475 60826711 906474936 895993039 222837045 635719691 337322604 885337381 790022830 374595143 936015261 580188944 788134440 996516797 371622529 321549228 431210357 714267467 522479731 419454909 542426470 287951880 136968394 685151495 268328003 560687113 975002434 415246180 259597243 600194309 546447248 369114214 382496965 375431636 743441767 172227360 110149323 820266496 342266196 115748418 227294086 563965841 954359480 275011343 236830281 423557710 573384106 734434906 268576856 50200008 531328880 194149625 838132315 724701438 114107063 363563099 796288364 154664120 864771078 638509158 334809873 457352610 192339442 27158417 104162836 870832693 941119728 189259715 627375163 923838202 958112748 816108866 583837829 665860939 108513917 228484235 908253732 311010245 983460634 301716683 482978651 60961338 984810478 212306063 549606702 756686171 377260812 679512726 132596566 439857804 644251647 186013639 337340376 939568131 969257271 702752656 350290154 690170523 361017298 907519422 95600978 544065414 886371675 660771266 455488741 145435841 435565262 95150007 582450541 97378009 583711555 884483609 23513723 46525143 894391985 625859512 873192794 542734267 806140870 775428547 453472869 349243994 236395722 339886039 394457102 943962219 271283333 306594258 533926910 515507643 843305896 852724034 728335641 93200145 193372811 934698222 62903937 678013395 300367737 722718777 566187275 476373307 129796406 671110354 175353989 925696301 617460147 704852576 197033114 991016065 979717962 629339781 970701905 434610470 239367029 613425269 843764259 693110077 978143449 132655622 627684394 959713947 246942601 570900264 275269093 112681811 800187626 304514701 592033965 546216116 990731030 467344098 45139282 233936079 856763401 252703805 18143777 655915570 762024656 724354763 584909808 418635692 529924437 66068650 468148647 625310422 723388709 223772357 344087978 698185491 315659864 410494299 251375507 117569644 798647795 547159681 899055859 716963270 723301448 78393045 462672461 352815648 852910023 580873695 766953143 698527219 247973853 762666901 206975445 552172181 597580814 26633634 555712413 966756656 656168362 749981147 322147636 284558637 584542266 821647187 152142801 794921823 546650367 503849026 798969521 608445415 402484149 147760025 85442469 560299028 48485521 713063956 844704069 765343838 808359391 833754025 493077444 766697444 126136982 263048399 335799998 329562547 47867292 615307938 941124357 782998089 612244222 600002797 577000649 381333347 657536494 250725728 318664668 379301876 349503179 211463483 435599586 184624416 560386396 57517561 195731568 400855068 552660277 983825385 563724680 988258632 888889668 967467099 694425596 162989881 836315668 994140405 85253823 689828921 535234633 770147148 412009467 634911782 88499040 991928152 634253582 392101439 111993366 714219681 601948207 241886598 979248279 688746806 651259922 225921940 723065382 633271540 322083129 157950303 121631209 692708162 822743544 616481507 653509198 896197729 984366222 119969416 719196780 545032672 894107412 529785524 654801675 758050381 128902860 86758822 340856776 745065410 146419750 180761854 265065940 347693783 205761143 222372371 376054733 579832329 212636004 831682999 634805170 793656063 452383493 909535198 101652337 750572531 497593646 941167317 189629426 312870747 480795714 66827503 71168264 886752013 825593020 513043507 987995161 838289338 900833385 154856421 239237599 525473655 597079456 489317798 740755242 71608839 142871494 697428543 387753720 753181745 102954920 851475075 32664725 408724801 890967215 694717503 900636187 641531102 87087782 243336905 34654635 117677192 949247575 860343451 286224567 679656172 814769773 829849942 718785621 287874653 93276467 941294600 321716000 406716694 542206901 963499285 925334729 1129330 266412610 157960770 40435446 315458619 352184347 990069656 167249311 140897362 770409616 682513075 86084390 614712223 690017874 362971182 374593046 870936831 893305460 789853174 274195687 798637003 836072439 558271543 431037892 401913512 509973021 941882574 431028095 272813802 196815010 462270179 31362288 789488054 740164185 591354629 921205251 436854488 302966738 466300827 975311163 330893495 995249753 790792614 321271189 628560401 832951254 525603333 155948270 359283227 962583955 721700192 62454831 490995698 17043747 88377751 758647896 911647265 105864282 245129927 315415946 261079629 267989724 722154096 626922267 804192803 143081858 465612393 354587652 123539651 11778821 546512805 54702133 861190822 777519738 365986330 499877459 353928949 440515397 45035416 601987171 482392945 214837700 80954038 214789930 822334634 889132025 476025050 609804068 652184581 518652616 973457728 431554006 422619751 167624527 132046267 576688147 102352598 140292490 936855366 403552409 769429571 586069078 858594601 512660308 162598247 895477447 369333402 449546066 66320568 747558652 714516072 330239384 300401021 654703275 703617757 912569810 305363217 81143071 30427593 777639432 716662632 198107638 868608457 81551268 566511891 980739049 74620003 423268838 96350504 592320422 16398630 609584278 877845586 492149098 349746712 160466771 215243218 399102420 26851780 922224407 311942972 124246080 736365385 317903155 991246143 876897460 56967560 721659019 206095214 912785924 447849002 733387580 61438773 563289663 381326152 605236302 914565396 171505490 86552975 463319598 644194615 327880246 522788521 79099630 6489826 868650840 108614666 908988397 970933707 525794310 949043276 133888498 18964934 131964439 592557258 506657824 689301027 698360066 598652144 811428311 355627616 362958314 281370960 944220186 894752651 316273081 152261959 745496866 832712955 257845597 82866495 988234174 795946223 506416694 117363969 120154588 257115227 357489252 146180842 563886101 131810036 341344864 344189195 566575037 135217678 683321763 802445648 270235343 959269013 675765947 214789651 430709867 621529608 72263513 196270119 540873063 22543508 938203079 349521907 72293352 540676305 683835626 320850578 382776334 250340334 823945032 782710842 262098844 32827070 906394822 316559143 932080150 998911994 84415010 399559985 264156479 723681604 237475531 513064600 677669765 697611493 873022336 162651476 725009821 836537973 369607825 573064334 10139774 251443841 951221005 522147902 615151051 555406210 74194434 754238030 651913323 224350175 835347383 465088463 444783635 93184688 921694060 109127283 652368052 503299030 176608330 768166578 328322374 643265973 775799072 602364022 885783580 728969237 131902786 442569550 964156437 23770620 659533268 779806959 25608825 539539083 919944502 35489131 637946667 336555461 172315835 325840685 875619350 283216261 595719263 355458720 726086496 39278493 816710177 308218183 659290088 843107940 689285682 19834570 927225468 289145330 22645045 630052668 212912362 926773727 930335356 425165358 959073087 130285131 103786948 482201540 972525874 218421996 168416187 2085822 167060614 117109952 453604550 750497630 464248132 236073070 977660580 157581189 685963854 573092884 473588334 254348925 65682919 495167949 836749466 660535032 714077423 479655386 290009097 922434716 4577893 785414665 302997325 587157400 990351732 974853100 204952278 9093292 16643673 169185431 952566269 166658519 651771869 622495717 756857170 535816691 826212157 226292423 753912478 267741501 38855466 969716189 202620768 318601778 88099939 740381130 267523073 473804630 605139383 124602874 670807998 532735725 690136098 23609134 283355046 549260503 155649577 367294498 665007812 830072503 39961099 608271815 709196145 705387998 436373500 325726873 837879108 491160111 847425831 231147008 682256840 549184920 246626021 523472266 699173024 238509902 594351921 363233852 303980730 128717849 24979031 295629022 382290095 552760332 367464423 68652736 972141329 973281430 6253823 157802274 346974131 138239598 265523021 929229411 239222293 508769018 363095237 747957420 261824203 278691549 116967667 949870493 578890257 757011005 768580866 98090581 528081642 179164130 222948230 195274778 820367495 106718777 573078001 707630011 847949216 229521215 866538731 797809511 851795500 856330354 728757281 204863357 402205966 506109053 970489159 391523759 675043814 401348481 235116492 619542242 754141808 868902443 641314809 754531955 541013612 808279198 931260939 520479182 147773776 988453304 495399735 137431574 925695566 580997054 925030397 921713896 805332890 279235907 960543590 127724904 215892188 332131673 174122537 225332549 196514072 631004790 462882052 515956662 981146551 716553477 833826213 827134717 675337281 380419303 843363122 674676221 121665919 955601407 957895953 702711678 573029326 253692299 106648641 490058188 977884029 46704726 149229866 358762471 328424485 548081758 491654504 769826218 58836666 16972512 84628493 731838985 35402203 5921946 898535394 36291285 74437137 498292328 623442720 350110027 796609826 835543120 832300899 511749526 91936222 491691709 417974744 554985019 56646780 780972749 542519889 422469950 408901379 931947097 265141727 849263015 302635642 241897472 567942830 439894967 49597514 13489494 422344445 904342590 637871639 9004224 561881882 546695833 631869864 186358963 827212500 811466712 139509678 367875785 420290496 685334718 383771402 966741682 116705596 631451393 44796883 421527421 73372294 676489917 296400558 448068209 431136532 311454524 609156083 510567150 27200688 389444023 782290976 192620764 259703004 173819377 540525668 633039428 598483978 11522540 758536393 461302297 66617716 296714768 863021168 133248877 567851786 64685469 108989199 717033687 901118448 872680155 796533922 577403605 162087920 960199582 668180501 461321048 102095458 57035528 257614854 926179089 579202805 660316281 755344467 819729093 341366078 922614546 311147191 310978436 771688421 301135823 676012883 931900284 357940966 521420779 930357412 180960713 934486146 14792083 239800115 554160550 186400179 928345646 59069920 796291802 525835571 670527736 382867458 307694173 639391472 679274908 79203761 883280435 914520308 276115092 547813644 689488749 194076608 941776809 272679921 489098701 242878885 827201734 594393736 639073594 158342683 122904327 920414211 325283880 14334931 62979463 426062287 96730788 618161440 750425807 716255312 404538966 923141640 918743227 258611330 230491941 853670920 29515498 25803292 757476830 736905053 274903537 339611203 802939833 314447831 447464112 714931416 378988611 254961829 40951489 786584505 9590330 497498587 843415381 285732416 764651960 869742534 740255714 699077461 613872393 969593 474523852 41086322 2824197 811725782 797462408 367330556 467311970 413781678 297830428 639275988 214081165 869624472 229465764 897884358 92104870 328556407 487069046 288053180 621658736 719634112 499254963 15268439 312497543 843317229 374080921 308293215 646899279 891767800 601256482 988409032 181164547 343815354 765713205 7894962 64218446 988241660 5432351 589469765 410811013 699420131 105660442 226143648 224589391 742658050 927058163 51832443 904917155 487544466 942685486 452310022 22658160 827733313 37752009 812431842 558513867 236724685 839863015 804514822 360485811 277506846 572840996 368548104 708406639 916392419 694196977 131814983 953776952 673319867 756777677 377638549 66694456 636362074 298187025 471837480 132288575 581064894 135334358 204348276 492242119 477097246 943357481 212992260 146446037 97706267 919626826 506735537 987114194 697667013 338675322 763637470 645827374 259601722 673372407 611070269 562891149 902780524 406974589 601728025 538326198 926138716 34491099 109113830 311590089 405709802 556954738 181050061 224774193 365222850 14276718 77084690 46309957 974758526 545293551 289834364 367256337 479578703 416164991 207302068 598742054 539172817 548332431 129688672 998429101 319764558 588933232 565986692 367441086 488743903 615177245 196958019 711204909 164757300 980201658 154677936 495050772 362650150 598204888 725246776 764445539 998379821 740242848 911446200 845025742 537252870 688982031 41477402 173301110 665513182 886657673 225126850 431821627 440925018 529757266 434149285 355715704 112958274 997064580 96543131 490169380 974874626 245183966 586982881 235084400 86674711 297671255 129428874 624465886 847361934 273374501 641247854 483342590 219494693 52802845 471767348 404553447 475979387 167672174 664180978 399468900 403165183 21084417 957799333 518148345 165211166 568280585 242531718 433529642 965749549 237250478 581029434 474192008 884116093 715561610 456186182 721874482 463500415 524851413 176965658 993376974 980902866 568262213 704727215 613055309 374454906 286776422 782593512 469709292 129121650 59953576 923847928 616607326 771952783 43140887 262430931 784839402 127063673 374634671 170507466 430689451 486028937 116479024 663070610 734858618 318297316 637517100 57865976 663160527 732200374 413701476 506907352 698573698 213130443 388191865 457650449 98657380 223116103 306157021 963871787 853092903 362135759 249669251 996412489 240402565 126700685 499377026 920815049 17118367 860380527 327114543 866805943 447252204 477629816 68098636 18848236 834709795 572991817 820964341 515442079 928279055 489055514 720147321 216174703 739950654 148723320 780846262 404558684 700444854 320927965 623633973 468369924 734940820 282981317 452197772 93895974 982809380 394573926 617160815 88964817 737901759 731405531 430197907 531940932 368178108 115332957 97256621 430674196 220304266 972771759 267353555 559742420 421659866 381621776 918057688 252546296 33061426 622971186 722135003 763465836 810876284 672389286 880108620 584140484 585161820 906395396 140739315 656886297 253472425 31949642 544859151 548039483 85675105 863930371 517324830 10668513 387553427 100193837 691032199 915611697 327321419 994853910 960831549 126500054 141667356 673332227 482650113 96495289 110838217 141241114 909096849 149218967 952092544 101903081 494689772 447818834 234434504 19583431 661377578 252717851 139615621 581228953 386700028 643062007 372070761 713524158 987423212 344960291 316392432 89256851 67693426 127752670 680998633 290019198 680493685 62171289 937591234 871634397 75355487 773154900 361801476 85045927 423008599 893880706 86748590 818171154 865127951 185830280 987523438 980012775 693579315 894752972 462040876 594156936 771368598 962135964 734774356 465109839 372000948 364716477 18017922 548580887 272795802 167343593 515650518 557254940 899113022 601797033 298637017 834829106 616919408 111503563 402274691 48508044 327337687 74317300 712519327 295932917 152893595 798399332 404748949 268522294 437737204 198462457 980174902 481583320 220808315 720319261 946292475 555379125 309700635 884990833 641866779 467037370 795959287 661782304 663170412 686716956 908538892 527363469 259876588 266717254 222484506 157438945 910346626 539189282 652456072 894606254 620704766 864172749 75485138 435907546 467520186 260192021 91874200 817019029 543543754 632309495 850778374 623919269 586239562 752482962 226057087 255470926 268635748 212948270 562121425 48829570 672980940 384387479 257399029 202559378 926695520 492348974 494791945 652429816 990407024 564980302 951257504 311153352 708121514 834281003 18439402 562432066 976539860 357249697 923731472 433835045 986415288 145426797 782432080 561956337 296944287 988998021 201873731 340762962 981546763 745610937 840346650 844043819 472515417 890478098 932177247 473465140 843302489 169518302 98833512 316350550 801002961 721179661 262312739 385502210 706033501 878020625 315794401 482903504 52919575 684607562 938551265 296868359 946170743 38154785 343544774 949837729 334294818 538075592 142481085 516543328 849762031 439048388 417328765 331781016 851917458 276564049 518294586 801891352 755084897 762148172 431635450 125963311 138865412 618701894 702408448 886721498 843352597 725898689 521663107 271133511 749427713 266416000 345688286 46515861 783409172 460976110 787120361 665275588 528860999 137802503 458929040 90827669 628836401 695587262 877914812 533065914 877352351 109976852 770379737 986771846 218039266 858834892 829800574 371231339 217002395 547187814 280909919 714096000 734543167 514764970 308551840 856345445 976971088 564722638 145580890 497192778 908293607 790988291 244874358 507414844 5691745 937110926 390118212 109933319 707755269 658388258 120091419 824549859 813046366 221138791 805574122 939140204 801182640 139400153 401387738 96843127 879990169 439443026 770626062 487402471 443155168 362487152 164538160 933163260 992300453 676599733 259067585 313801047 165354878 375406999 550897080 602054365 819763270 986242585 30064189 886430283 109023305 564394307 808204134 512474962 617405494 473778808 731371404 714335631 979737784 562212437 554498658 338579906 685387327 227105210 744977347 701362700 684596562 60855668 897337621 190704995 570390839 536580062 911176649 264365238 52699420 13378168 730251946 379635616 99346252 444593970 267927579 994079324 523090821 792911096 107809155 423610148 523066348 984428538 917862411 97973803 798295953 576321103 965401742 43004366 764777189 196695537 704709519 785420965 912544330 431059534 431470896 876517803 795330908 870390497 319907646 579536719 341663405 652984605 132360930 72910565 332564564 943101468 119207930 544005227 350307652 804568361 953529610 881572472 59854913 698089047 487849000 390303925 850009106 491934312 413005185 152183602 540793353 918110952 944220566 594011492 649338367 346827682 412350143 917511562 70335108 790422251 731575595 240287945 616723022 681565967 133735625 377597823 660062284 261291833 106063811 974295722 883036278 144794572 492956030 387425598 493969643 761920714 820146098 893796811 222270110 931734478 673188690 789423733 656789350 557207434 197701074 380853545 301781241 194947886 611198020 693267650 761998460 658889456 130408992 143800525 564078614 206101239 115015175 118976427 429968627 534267765 191258385 614384083 214434409 645544732 175811433 422482483 606513912 151110854 140929456 20747747 218416057 849082410 612395505 474900201 215411766 429050269 428651154 287588900 711126778 638860608 393564556 106960320 598800649 277599736 932561514 574033969 784226321 237460114 72708520 35199117 960509073 294809730 459111566 170261662 319272214 726717989 786644756 633418206 191103856 711727944 600037412 328411319 972889440 294966886 755525069 150274682 642794044 935270498 110164423 885954590 712622733 394582974 607657686 682023960 311933130 256344024 315179078 929765225 140693516 73581092 60936181 246241218 129317991 331941763 107463547 508082529 294338530 20342188 875409621 964535889 586793451 799547371 471533637 640018380 117786090 814126433 279197168 690616525 478481609 889601142 564431319 233354989 495423588 792183600 942133650 822547842 949235995 370806667 194382001 168466914 911995594 550393805 511925137 95222129 429201133 899309391 430033755 23308651 535579116 278610303 380180849 824742300 613859914 399700834 107471582 615386379 722191403 150177502 383137075 146531352 60622307 954861830 59942268 896788389 115973829 48368480 332280724 417688865 631672993 549778510 604055944 262957840 485640458 817744652 463445584 371410025 31576461 461404526 635883429 511110839 876994863 828059581 395272292 694643266 729127740 265020390 160279607 58214789 526681077 592905679 254729974 893114119 282425885 223418018 343296295 93197477 455054765 913879098 289775668 570299228 730569789 910268115 902141912 89867763 676159603 473877517 455420841 38038704 388013019 837335004 418459705 812166587 28523059 290291957 996042338 19817826 897080612 420077211 259035563 227988482 806433352 942058795 309847714 708737736 37146791 778927133 114192453 100516933 577440090 667113637 576365971 760534307 618015365 719316732 576680062 562938899 464331943 287255719 513336255 760389048 146283142 906616979 613325030 580383699 531814531 518257124 784461238 639118948 625598060 402762464 486268941 425943837 736269736 163848792 63837662 39803130 153872588 101957377 893528215 517459858 881441404 358063577 387725539 901404889 94363370 961305800 822478345 743874166 29421304 566734523 870712761 712724490 935153134 664088835 344938591 961144431 555922628 736893035 774772115 498416375 403489294 913925571 175810110 343865481 259525628 845491265 202947647 648034263 63071002 757362976 774916130 982813456 125239124 204653560 277988020 640211703 327548164 947504418 758691239 764317763 927010790 652400300 560210910 542659870 709093878 684556841 684151566 788229304 760338458 241385889 765207439 800809084 136034833 911860305 338287285 533288486 358019723 264560866 888238659 145600762 313746659 160399419 259211449 186879744 532423741 283537851 292456676 136906589 822524032 2659464 666657626 657076450 589701333 629718171 274757928 309491139 128461825 555101313 457924642 698173982 957169934 523730829 287864361 8484927 236682196 828685941 874469976 198401473 546749864 277535346 11666132 265474141 486710914 86253841 247641678 830545448 231569164 212669573 831944789 647603466 985542639 758006185 349330261 983656619 709182365 992329477 38746890 195953737 672195591 467149682 226171205 834996241 140905642 614317941 416115202 292894666 796589807 856859344 281203472 33388112 381783319 247533850 465209714 699503334 845067786 728999099 27510627 738787012 872193455 142109997 89986817 68502071 385686289 798616060 929378567 103151698 830704762 339741335 57729563 256070984 841089987 558880325 138620465 645916609 327455964 492471124 854912660 308743240 601916398 499057842 167735333 842480136 33647096 339585781 363229330 688492541 388984977 298662836 674689221 278881859 859154594 111305196 347233853 852175405 286292420 862059432 896258485 502380701 118251549 152307821 664181224 543033733 48279812 308428034 436455010 643915822 393865415 839144564 387065656 253034244 28242324 312318983 736480582 118490847 463862944 279182522 71405161 581841757 917513671 785992405 489355857 579044969 967555577 968449995 604195980 395383024 364343940 3977668 399491830 389945356 557416481 732870044 8768875 37956105 541148670 395205706 385375832 699017398 227789647 67610964 448702760 893937773 296945979 504760683 690669931 161323745 192937820 219911620 732603725 770904016 478910309 561786992 288387254 945717581 384753381 505073892 112446790 515565441 296214470 233471120 386533266 143434957 361093600 463030229 689917956 18707344 986283678 111524500 789481604 155414935 85165543 738033266 98044183 861860937 441713502 980770582 133125826 196086004 329140693 903679948 347449025 292909981 789077497 40149288 306052303 906303749 56370500 772849206 263920013 637227027 955117959 166973512 122303070 188996926 615190833 258181830 648405052 120564346 125164025 640434494 734495691 833033170 302846697 864260253 755893063 26833416 781274388 288027900 10958259 661177991 282204142 410952620 202658408 892881881 856778641 648738697 596343516 680233608 80774130 273770156 173134812 888088761 789144489 921634698 30528451 281062048 247729229 714727627 691141612 522567531 866121703 135405600 637428765 598406920 362403715 663285288 807246705 121500714 678444030 725022775 789752338 548934328 997639377 31797109 344877663 315285362 91187939 899261980 726504316 390072522 432269059 231890137 860897097 717238525 822428542 424998071 354135280 476320958 544631406 397567539 122810429 829766601 275017197 458193161 380584159 451499386 353598373 
3186 723720022
1799 367172915
1280 133392554
3116 329639224
295 273403137
2090 667314746
2124 3235822
3014 933975464
2827 755775602
4321 994824373
1339 318882540
4249 68286465
2682 754318117
836 811372846
3389 832266636
3058 515656894
3042 300757606
2537 775455894
3075 913889594
2457 214422364
1543 858114265
848 90274484
2753 504900607
1707 785527743
4113 354971640
1854 944010994
1712 2000960
237 716015987
4025 430638890
284 520623866
3888 178652535
1074 438232917
554 802783147
3465 289888373
2989 150216967
4077 810130720
4283 697347984
1499 213682068
3080 164301057
3058 154296265
1121 663598933
2672 228120418
3689 493100302
718 772701447
3803 172218125
1162 742340809
4045 329893693
1682 513578092
4297 139259682
525 364596026
4324 806419327
698 75045707
1479 33090539
1675 613545491
3599 47841989
1334 879249324
4109 171766389
1478 526273032
311 691148441
1282 248340874
445 603257787
744 171764450
2346 990871715
2271 262986818
2348 131725613
4163 840587438
2613 358121301
2949 826242763
1658 547601879
222 320544165
1126 330381610
1919 332800296
1851 123250452
486 535109031
1062 328443933
1555 28771746
3876 868646131
898 410084735
3042 257322615
1587 420268434
2026 978437101
2840 795306425
1684 89383419
3877 329169307
4271 979228251
3538 596494212
648 699691044
2928 749611245
2572 57642019
2632 833748880
3545 898870756
1782 116697257
666 324173140
1341 162376112
362 558697124
3815 48834752
1104 222877866
2282 29788563
4277 323267966
4352 561654242
3884 626644060
1463 510181747
576 650236526
74 780810461
3902 582491909
959 539210498
2293 652210297
2633 98561000
511 94679698
153 824286993
2617 794661733
3237 221432609
2197 5774468
1861 685445461
3222 303251210
1395 731627266
823 466733262
3091 833677860
3055 593387459
2635 879091634
512 873373993
3620 395743266
672 923363838
2452 236899261
1797 347144754
1585 377787336
2188 647508445
2726 538778562
1430 744892703
2724 102304956
2502 776783072
186 252554469
2525 158063168
728 709460192
1944 899720778
2528 556490156
566 677861487
86 341389982
2916 897313447
1974 431829607
962 586858965
924 738335211
2257 496934351
1388 919818429
3768 654126256
3635 386387057
184 215172837
3995 257969325
2031 864580448
3742 467391756
2198 971307163
3794 41951436
1688 356445326
1387 659078990
390 252662923
2889 143662589
838 927907972
3910 971604460
2945 788257939
610 480517973
391 841124112
2892 724463639
1466 525583882
4325 41384940
167 506646057
1564 80608193
1880 238390027
3830 659789645
1295 855879643
1643 929234519
2678 389614650
2348 27760656
1346 705094597
1968 388086181
3825 561914979
1129 107703327
2688 62923948
3260 602563875
143 242881327
1833 933373901
2766 594507446
3220 129266070
2370 685091906
1471 636639249
3662 553271953
1053 660750579
217 796067000
1157 968026844