4000
307036266 882715779 508316354 383709544 785521339 175839348 519203593 196102721 604281310 952759676 268075381 661753432 985932081 732609282 506344176 799772804 897417771 480996212 934159401 400234817 996249457 989335214 653350266 840758551 321779967 7401938 838373566 310231988 92772448 457404743 814566190 723414154 634616886 523008280 40700959 930041824 535483046 672039666 660748874 369021979 853718466 704548827 259781121 747831434 972659815 844613535 809952118 192088715 952518680 576489216 324642884 901016277 1024162 471328519 868513481 828695592 21020968 570045184 650399478 659624081 652050948 194371153 313839264 124540945 482957744 324813678 290693998 771927988 876331075 350566883 442267024 630525511 384418389 35265669 809806904 890169589 783993618 380523711 651413533 111908865 354596330 42574132 114411015 394720682 670789918 239444089 488898494 332267445 43766989 159652662 948183038 362609830 108027828 516082256 137306326 589036594 379141823 390063740 571970355 501188867 201542310 376549932 467016195 995874701 572728918 99524973 264282884 117995569 596529624 935328643 888682673 363671526 789921014 852375735 543711349 186425403 960289853 196194586 549307419 927003264 529812985 703743156 912616873 72631860 931049979 425819987 967108150 799740505 67845793 804469822 341691922 47462692 462239639 810997095 810017250 626434724 342329223 611922450 630223015 361216269 493858677 513155103 198016947 870708537 434639188 799352343 809946081 551690453 261366253 439089222 285124102 165550393 946148848 500046685 532395142 974794080 958704277 936845055 229206467 61175636 972912561 388309742 373767088 762915084 475757253 40820797 742947790 365656054 553206298 692446695 910741850 767611736 851970656 820342897 771930209 995154636 281398189 321470121 632331583 670679662 552138811 927633229 215189668 894522214 534437303 542951887 447579100 926768770 540238967 194876456 695830259 88681147 613235135 941723491 454488172 279350129 517978369 332046512 588122774 467333822 111888562 856909587 448916048 197609456 48485717 550786852 956898141 649281512 339793354 457374674 242880247 812766609 928494396 883493950 80461118 685328329 187127173 754573997 5913776 578774085 590633353 122150351 244355028 5417981 263081745 155161070 813223532 962051866 539335931 400403898 845698575 749377993 249024997 172640405 984835897 214249978 211521907 671284350 139393508 460469999 955654430 291490246 729071884 453975483 658808872 14528547 31254738 748765173 671138306 264814988 775951284 479156505 979058806 846782031 28571804 172696485 257347261 645742592 661325820 874083949 772121569 39812009 810220249 788064743 155970545 937902148 628866689 719250783 836660344 377265325 671837509 612889037 857164901 434038493 248139793 172912428 98338905 462953512 571994181 203368417 919838941 350792558 157965983 647842153 483455813 744894531 109018902 432687801 30120420 971254905 432303069 874979360 580341241 733223170 467506100 104370420 226072271 381908252 590285162 453576211 402940904 72979804 19229193 305482190 73289314 319007534 761480894 200947466 760289333 486159552 309026324 700608235 711830950 810988179 948889165 414240141 713846289 63247437 565239049 243754 861080898 346606378 852679610 721202821 143975940 313397969 556878706 404194151 760406225 927074629 939167991 216097802 993447971 641830610 297951407 232910492 988475518 441635193 840001146 316009185 936841485 538039431 432578547 156539600 746560632 27414588 411997690 571265562 758530448 164948319 557943038 584776756 481816176 815450847 518963619 437035783 119460499 96873391 91948209 915882668 116043552 969756735 216521817 386120139 977887999 907300779 131496972 415447369 832596249 875701442 389056228 735874314 857667381 425558400 678667333 105634880 397221257 162063079 723116835 209595583 85008387 517914756 65679811 778516939 143144456 732832509 276858556 27583572 835507348 640230454 546471995 387546234 913368345 740976320 580290161 89227182 121439654 812350949 707907938 343207536 141792073 247136899 351122388 684312329 564956758 663262594 611239196 147891887 107502029 730250307 904980580 25762951 298193783 160698924 88510321 261977645 261178876 635930476 243222709 688836163 851589177 747850125 663568017 881906615 119468729 626460593 269317233 268505790 936010526 335035965 131108547 639574983 472049755 952435626 528674710 940750228 934218943 539575989 70528526 916699793 841019723 945808097 271109426 304552543 337234468 268065089 756433889 969679349 681307022 831243800 299742728 340654185 345652063 584065276 620235411 620560710 62202335 554777124 735966872 861275833 969145191 391161155 387460972 463626904 186075450 759232081 903850810 787319593 205789794 195900302 995001041 817530242 618487756 6260128 147445452 707747960 803275174 139447994 749566796 979403129 429478187 767096380 946928151 649667501 663226022 704775596 874496832 831646025 362151629 637733976 908977907 7575733 809494943 138204082 951904184 800861701 362669915 885857252 349238018 366198365 225091617 355787614 714809793 474474380 742801396 216615918 465861820 346504447 748287739 705042533 953913096 296417469 320510534 241021279 577877042 276638975 209919983 136432206 328458128 480120294 59302284 584324323 784824038 937903092 286759295 451475180 708015488 219376868 555845291 770884680 73744454 941071600 306311249 795936685 808367801 418385018 470980475 456477303 927825969 607559893 173480646 554537207 325295062 175525847 245710954 274422796 522712512 195437413 524768823 659188920 351006968 208177809 974011284 76110163 309150235 255937207 233581942 171844892 672339026 341197558 796010952 92474700 359031191 883479719 226956310 827696173 733033391 655876484 588523784 807457981 882469247 241311702 178741757 892238582 329419954 510526056 832319977 707645959 175886208 782020648 170464359 820053805 898608579 422835200 499104996 761436685 125768415 941602354 993768318 83880720 653704311 444689783 464260787 351431727 729240435 708461338 728755463 961051036 926973787 810842108 95422786 755052463 858634122 464200241 820442330 387482601 924991326 154778201 554229400 659495081 963519909 678806691 417857497 606947037 6091 114362534 619811594 6803669 145630633 712378038 570626335 885375632 391656428 551102417 325420273 710171116 865027336 953539752 980814845 717035590 873221200 464257706 406971721 520750616 563535032 260330226 395793037 754761722 879548115 505450915 615370249 453456915 818704091 514860384 684136324 263131645 4351111 438517703 129536885 412066622 567813782 822467304 312285776 960012189 700636503 739142188 808635409 921037026 713118248 780317901 71298406 515580304 223039160 621399459 749018468 292615888 755368716 325673568 953272026 838718874 366750650 827741819 652199289 263415991 94228994 89358771 967741647 220191459 910763863 974310590 704961820 21979220 7842479 734249273 370572347 369450925 604087635 831072355 65936301 506680004 320280536 843004566 960559385 632967825 161203672 561530623 487006209 412945800 666170980 87415822 106529176 99879289 324612162 443286765 974323116 760444481 963757048 636726082 842352846 853187929 170939789 922374671 197782308 579350830 392224169 352538764 5521184 898438364 407425030 129279017 474054644 858837723 776184043 430476942 498496056 588666045 819251084 445557291 145785889 34385236 635358471 74343182 29916872 693664018 405828474 160291876 181880360 9618259 800974148 629974331 934291780 315369811 313491442 937893488 325763639 161738518 743603928 27099015 538010949 419065913 516495718 440947022 917351278 500322560 629879555 406246033 401167858 365493443 477445710 637465862 846019163 894626967 169716358 891700367 53831481 592516170 619520320 759882072 600665241 423025709 680228177 289473591 810832945 446799560 772742623 79650830 238364247 620035716 552494949 111645668 224599550 612452287 219964620 312660967 871165207 760633231 563760695 525978030 447965392 54583457 472766919 836913850 174547848 856985825 962081027 263274997 282584416 171604183 184822290 459332825 127885827 279582785 295903578 52541082 308536974 56493003 643036945 854979600 958125482 396922835 801029519 558933762 324175766 81218967 158647972 747379299 820355356 532837866 252880045 709565478 771827829 996797249 738723660 721387637 435094999 898491278 947029079 337949591 788285447 910389729 125866549 247828633 713308272 488823857 186808335 807174403 306835159 892378754 90538433 613041631 783825291 453909775 951168766 910925330 602993017 993636906 416754727 377167673 849052386 559230142 390461095 780377529 644540737 879480887 479121013 949026425 309811918 943249349 355117523 560531756 301336098 594314154 611931296 252227041 277827296 767152433 745949826 568556282 173119854 773592068 911829621 628681194 925618908 25552217 402765342 797210288 436969335 537506578 51589449 864051773 219817616 129524588 449422587 350635560 372931931 400490557 462515151 180589640 886362216 516526962 775496935 27924327 588192952 905219011 896210968 395726807 247425680 299826036 139624163 866657161 68155025 995272660 654813179 679934014 210466719 35650986 208567965 947472203 291831010 601112301 791097739 399960713 682840767 346824320 961156540 462445002 141434883 270066449 897148832 884160035 591478430 529937392 827957117 513653240 926210894 498399765 372172369 381259662 432287148 667112963 445250208 937776422 880393304 606486614 192873736 789239002 94181861 393828495 940944024 261102730 969658017 802804832 932110277 216431537 85454698 115531380 149831118 626241655 656710779 949403349 370563851 358715120 740730669 924710875 672264503 496768467 739973708 356373315 482263828 677082123 830877585 522454010 76031029 515554111 949701496 402337897 887298097 650719523 48911629 79917591 249043652 652167153 899944384 882008199 295524388 607651534 98361533 787180671 919809767 653207634 660321316 213830582 654918865 721164325 275217331 650694197 584318150 424737873 829739745 527506287 102565377 403551529 479260479 152869364 46855571 957898841 877772763 764013419 392064727 124896326 464708427 449601935 391917396 369021980 738038697 339258925 95110874 818596481 296673736 382234183 732031266 596453277 951860248 893585253 460512398 7966449 771606608 49428256 830949571 866358377 592710645 565857795 727719413 979563547 138132855 199664118 592930810 329879236 899659283 705141300 825262352 985349029 141669146 489468914 203174361 392239983 756218488 10809324 557744985 315819152 370340307 934360401 956513983 586376467 278483244 590822943 615065243 648590618 933369397 25871732 705936263 968008071 851908686 588642913 536997361 319919481 518942285 558910865 677368663 800614670 120928013 462064847 372696641 591672155 962030380 680723511 420023141 466396225 660239407 546576739 855054490 952156749 46577376 258324404 718237895 795509308 64841564 281829492 559705462 752518453 52835775 722199013 526123644 236769343 528167933 957981322 410535558 329339377 284693048 180561820 909284934 127469675 290559517 91206400 388483325 124882752 782928194 567673833 42492541 7983460 919271096 477335665 826710025 778243393 683311977 978900424 231959542 585981606 760526583 403747719 198176104 151785518 285990311 16710753 568319597 523740934 635072085 244421262 161342801 495825140 769497134 602879863 699039532 463958905 161149708 879905179 561637604 263744810 692067609 372316550 565600448 324026550 112541592 7910993 855858462 900850397 53622614 670302738 767858317 297149228 172881457 296640195 30144718 498572331 892067302 681655241 382780813 569181692 522124808 173754368 259708758 206066948 454444969 800225887 961904921 764823075 236651583 395342370 644223133 877743401 966097928 668889007 457203036 359787161 193844765 220440295 811766938 458243298 989874007 15286404 491209615 519887514 830003431 691951120 245156346 170572368 625137805 727240119 424756427 795385634 343016517 765983347 682394872 743197741 172981127 528358593 273356670 135924176 657957345 781918468 428068450 646415431 676343038 907074895 245532497 657505565 241275346 933991761 892183223 299472669 963239189 424856344 694644221 204559322 821561606 661671815 868125856 371917571 408329485 678647902 381900042 161401014 485714449 494551464 929334208 826536958 91157383 954992987 81730773 904943829 163888816 397109900 444690822 217603677 860225160 338334646 534167076 136050371 624104321 809893244 277793108 847711551 902476140 409683508 2136392 982794892 209498884 186062770 766608318 318744841 445185996 386384332 144267138 22864970 288221417 158977135 773965740 785807648 166011527 302435875 337000049 780919863 691358442 591898721 857091493 709394034 767643296 746856725 890296372 613695871 770845131 596910608 441690440 548242986 140562846 846829056 288962416 834051924 373501222 414990549 500062487 567613608 478540918 6259248 189516322 63103388 270242093 98770697 384383204 309661531 37932793 809716276 321073535 429568747 587347819 574488473 717886664 677334710 53740104 385065394 578535851 103751563 931381902 136983727 534353772 712540357 603331652 326331061 905191225 239990182 993372455 489013114 860049641 558649374 278711664 110702979 360955438 625176603 592597201 63062885 780656564 352088514 319733476 44029239 796246329 6755761 113457596 938458036 631546355 661928688 513935284 364426915 521703955 796253536 50522113 392827587 166094057 588301511 495106903 722901281 210735069 797785101 118366284 215559246 645286411 625074256 461253914 269929259 254478356 295968026 780841940 459181634 41309396 555488350 625720600 560449411 837413871 475772394 237578678 841683433 32068811 629562228 940995771 353022809 6312271 131999779 714701020 870812848 356654724 104516269 906533430 454226490 987968165 420171197 201679342 294066544 9547406 228169030 98541249 13746797 755729387 437793780 150775789 606118894 314680313 112918464 548118662 244031519 838485551 231739828 191470358 465346970 289270185 947276853 499381076 854890285 623148442 191685507 367190370 310491443 759348293 6460715 66478643 423096341 200095984 5107850 927895008 785381410 830390519 861211425 348852186 902305117 628954075 168946350 196386669 277641595 480448035 413588983 265752637 192499427 441800446 832775688 30839780 724996253 917074501 770168958 540481529 32516489 462782731 301612883 862581530 239917443 328737793 439484411 793374188 375076503 599349394 508392103 493081213 128144575 714006134 983190714 753300547 520040852 548324882 733446251 929236932 444266740 682769219 704981620 784521087 472017308 209331459 440316340 192922752 787195948 151490336 244883988 68300179 804247354 140937394 960874759 508524959 685901019 679792669 827295905 692721966 403367552 15016673 866466614 32685852 528325587 579798988 326761215 359923657 919775086 847032131 861430169 506544190 761847217 100952979 624876419 180585722 411145233 442455478 433671496 670360083 643224096 759273939 78403074 665922293 853535107 793067066 383488224 219108635 24527861 600798231 430987003 467397610 267133704 611201526 782318114 972054966 84002837 769439616 755403121 487658509 951723383 535023047 687139289 64071272 834410919 837113897 723971388 321236306 7805789 713998325 493234340 672973327 600193519 93747251 608061391 281967540 383332374 329106525 665082471 459108158 904141036 528858586 447783200 953288082 29887386 142290566 671054932 523158571 837797475 604856507 591933035 250620055 816490096 280289256 806741535 768674263 85970278 661038427 316841602 486155807 884201757 233209695 889889320 933700351 31122766 894941146 966469342 990514168 493601796 432075322 591557907 875490891 457524977 58830611 334298661 425689426 395208330 255833440 980658882 579314594 679135352 531459337 235401218 720539647 184924404 16471883 29200039 524391231 975881161 436703644 756908047 334143000 133607168 895190563 178911582 626576231 952503322 847645913 103362822 264412999 139177991 126494928 9293438 464592210 446293833 189284956 471808077 82852760 815831785 172378553 652329600 541791837 643812744 466960031 788831460 90205786 746810850 16285138 612432531 335102042 837835047 434094579 433803124 349910980 790840608 397396060 374327003 228620102 774290462 70125129 225895534 719983720 252652212 942552602 685735880 603340297 309655920 37904640 78025808 268566749 442248892 132683805 485957724 701928972 979303317 764606827 291270094 582682953 897535629 939804348 139361111 914724915 769697353 978928822 192674599 582617266 185010852 496877736 994575212 307427275 278489910 400841779 23151217 535387071 711040807 928582589 580482674 154213356 306321712 163958064 504535323 664206444 475605367 694714314 109184959 729017665 921574801 992784344 258668976 617201186 204104669 326087978 234274272 14324187 222854257 759296303 547025908 269061605 65639873 712734324 495818764 796804510 712709737 820838969 190980865 785336301 46779907 233615305 29105148 925439635 349778209 795104533 68198488 537811773 239610716 821244047 131033468 306464041 897859019 297697833 143380019 864032387 505409938 929289669 853087240 282463257 520308337 202853158 266629087 952573213 217653447 211062521 175213657 771104581 553546821 481631791 165079045 942925071 248325297 425031142 878325296 882521803 207737957 682611801 10143772 233850624 905414187 613486995 693375310 727941141 502150820 421070732 568887463 37093683 276204409 594153481 775945713 185979152 388342359 455718161 435615987 426738607 915794609 250848534 84637123 794824667 18086678 806105384 864124877 944224755 652378671 252762991 190948096 103335941 668679717 174292562 32074642 357224115 272216615 301781807 791722510 111786362 193898492 943066222 70675639 378373854 895950176 471420798 987624274 289361999 781279349 352160167 32460659 419034131 221935136 983734532 443509724 48188964 107660335 272381564 848513875 247014947 179188312 87453827 603832617 46875991 683143307 476525498 167177659 572339824 98342402 645856323 314575907 605850426 665693581 277504995 146019790 430259225 771804037 311309296 422850824 439033676 712226039 954531718 828060130 866072037 274282648 497228658 151283627 595497985 708019735 195522153 382913268 45992499 766256234 389673310 680989445 775827708 14986729 491964552 661649325 42796688 702372114 950789284 688391667 240524940 695329086 26632755 364498750 940693517 512068940 428470059 975932928 581651920 310040200 297381600 731705442 455477264 910781944 327590268 942815325 138644759 60217877 924770949 987966871 640802297 995489429 64910833 946295163 487836073 380462915 790087454 960194098 382477434 92482405 664613677 680166906 516517995 704310341 214398601 604581455 256796147 497494701 216951424 734070137 761637603 846805828 769201316 181452588 287487981 753999904 413365062 421770594 130364020 187331388 68834352 506551983 589501393 369674080 906344554 460508377 49144945 21561728 2752007 421369574 308622650 529046625 7128058 96632439 37394924 62600566 545406342 766066539 648121912 845873882 352342429 509233886 306633582 375696725 249808571 360140677 129924983 531750059 434750689 115928898 901368711 881027572 866801511 845741879 121258600 259939253 253505874 18694418 248282878 272450600 683595254 290772427 288090445 804699053 733817258 383816960 544614199 154296443 140852874 217044979 754407609 198960039 137288554 246069859 75173626 190448741 451966792 468967388 767828848 672155524 261353699 479837671 846978179 687472510 333529541 870607365 718071677 185372802 943655275 529323847 239878033 205862123 57022668 955513739 77527013 3752567 358305284 601713871 855165307 414541946 394505686 986847603 333798430 97957824 317231444 23104993 134813547 777754755 399049928 389873027 340513528 355335804 279153889 615361335 640654109 969619075 798815171 729086845 800909359 749861217 801639258 608809725 357673818 260685842 322695543 319079833 952003477 622132379 662248463 969205280 99249206 186607159 852567742 497545299 61245188 74005543 36622379 182977583 834041101 37674632 951888870 254451663 157231518 30840148 68366791 648426635 867362558 309733284 685581443 218047602 933828741 222118702 96073955 277323900 819103316 848896466 30256424 253190357 926077151 906792348 181156114 829542170 589124445 781782430 248086335 182244733 705511553 463841369 489678032 608023058 63460033 944214316 196232037 419920339 128629534 771345507 856761301 678429647 589078868 133672340 567457862 503786300 861029302 572642219 779202361 317167150 88669071 310348864 882392669 781326259 922687442 364744301 332841178 646385034 118156345 105316282 486124583 27220065 533504629 996247580 954817688 349020218 46917658 683273436 227414659 69026870 275214379 191048161 128761700 693260749 554653202 385402649 693621012 729816116 735655725 191410493 420440284 182987997 829025166 9865651 964615973 34384835 8771391 398886910 581546910 372242437 11314498 877377605 918326232 240835765 563204133 963347833 995915322 98953220 354174556 125573236 613553994 126974678 349688157 112780137 115629077 955978726 617819406 698416041 950784723 26005382 720923097 291894212 903167283 171678922 64002111 686968960 643835316 663586144 696612664 857620091 328436456 909185856 67700658 508452541 902700911 388039206 666667252 268985357 319620435 925704824 581514460 866648446 457302750 28644675 991376533 654701025 636720899 969915312 964293985 113767731 619462191 697084033 873910894 490160886 199850725 679005852 638746933 455313872 564348416 166432157 602543860 575447904 90615878 200579759 93177557 367385331 402833822 626969708 116459005 720675822 603990566 229388249 723969199 873986299 730505900 708038689 315106218 870324398 516066641 295938603 811980011 430447333 501159756 911174659 937971966 562234187 172357760 519912806 707327798 663543157 406581235 550082327 686357557 64252829 485188275 346492267 487190104 237793787 751610682 358314310 23103110 849676639 6548788 616220162 859921124 963733687 739089401 485580763 90210701 775176907 973212477 951121883 457966316 436217664 437911551 514713760 737463143 190490603 672388446 205409332 810900618 219109548 886865470 84139116 502528642 123393284 280004072 221544688 433050358 699828603 716352236 693357119 982192332 753594019 722569796 433757998 398850842 653685210 625991664 792332632 570159065 516980474 386413243 162616508 445365535 474254608 561115948 148282914 354280508 222746775 59054830 962229386 612443225 720908786 109933143 944265202 854724328 943347059 487247796 994436489 327403196 954528709 62089044 651767221 257693632 168623803 913232637 673504414 809067393 957559288 240055011 557971453 234926477 106817890 639184318 151876803 811126694 536959061 93942735 928271243 995371678 374609710 401630255 789398675 234613959 637194837 384149861 567381505 321127591 526298036 487315808 640182877 952970329 417823858 891073570 86809345 813422911 776570917 944051654 613795272 284432038 845279268 977160114 595981660 559548351 629694690 283470034 754644409 961433913 111902137 823618968 423187118 300782282 232297422 962660801 613585506 50392931 178643503 798913563 327591229 390573353 767247404 64076271 364197894 740022800 151757321 804560799 683253008 353349860 757185169 621279575 109423236 713490629 929748761 508405230 869274331 47767624 256687633 871711943 109164699 558206463 992709508 152937868 102954026 516897515 708080078 491285676 887918178 911956524 485063322 700110854 289886129 491478467 620526643 643582667 438772718 606927399 852339973 730601110 641107749 951281054 762001722 346063727 530918379 520492808 383296293 883700251 889504993 994730314 965459908 321896897 789752913 506131261 450410996 750399301 210721772 845178241 765118863 691189573 905710712 688284001 187214725 452350537 164041160 236847264 88578824 801707284 830466241 651152830 450666009 784833056 311353984 557211201 702574491 663339662 671851408 371609066 212670172 4377167 558031124 520937113 606443259 882812603 863919507 644453200 628226663 121500808 411801358 410188752 972348513 101096589 210611545 921321861 308656212 843879087 348731450 541629154 184203177 76443532 281785312 533904350 882762104 661992811 805773482 486418165 990955582 890332094 689915799 978886554 562764655 484554580 972978949 62928818 798087678 533082741 10369711 995459524 921876419 761398610 21916707 831562256 283078405 430728632 798712055 494159046 822013660 280536888 111348584 170996598 983241157 334167088 330323323 253609662 224678170 221282571 580061141 315344372 209810558 269100091 533244349 87465404 429595394 386498483 31311506 427491848 728995959 118091448 278102698 421923413 2529825 899397641 780429322 205316526 125937212 85785627 509955589 387500402 701995157 794162370 341026605 997424024 879283423 377853610 406046955 942776904 921679959 272106299 406969499 471615365 14025347 246547179 695794767 500803790 148920361 159153433 89532863 648851219 174490100 784249571 963369236 77732971 771924767 716943104 770283930 335049749 525049761 173542496 973212998 975809135 841486731 576621997 813121998 720835629 179893680 761070407 280082814 428474420 611677202 301940658 337950317 815062625 952638818 997360565 838454076 717176157 569941376 655802248 476987536 510334039 29063855 599040984 965225881 709094145 129118022 604167796 298852076 486038261 633444351 418386636 366282222 340438539 942730362 512634622 364503271 1643515 294151293 402978248 405341559 787665321 606246972 204424756 201702740 831642235 384382321 190873 238172575 744622461 643590794 744861222 672423870 365774059 6004203 359032330 820522082 322993197 124824031 109185113 428952133 535214474 881677730 281578778 633855470 861685301 995978846 699732501 855979028 851521148 634619651 524189864 850897519 370470733 117783934 670686732 913432509 340692785 728477642 441658610 855395515 418455244 401544768 669649470 663509710 915041783 122765211 934346622 693355403 443048003 887571932 50678249 662382885 413282086 660546536 283520653 879830636 539091646 17364257 36336781 566014818 223488920 65223720 897745559 952180116 755157691 274614107 939758453 902714409 934597041 863659988 852003840 377953066 433633797 194976181 930865101 286993720 958113317 798103495 144726513 762377654 674695360 223131173 782762318 74910028 401944465 282967563 296689362 337770849 841245912 589637600 703901278 509643762 244053678 324889977 29688448 158555180 170695435 796122008 511101292 6021965 674261635 907557523 552903566 672857012 380236729 500123292 756494133 799577801 798336228 276195818 472224915 887664952 274475501 457148545 953013531 615207207 917106030 24058333 736429363 469982139 113272063 687244990 891323096 298106891 654302024 727923579 309533501 449113276 372421107 861301956 924285925 861686094 314442680 557718768 416859663 244714416 145999109 195481995 251242423 147937646 640444904 764318301 927730435 641283778 850939396 2074069 912474575 529889439 804811468 627765314 992080011 250482293 902148343 341618428 105582772 926605722 536003565 240541649 231205277 23920335 225294760 840483066 987133432 277946042 307833823 669796243 836608931 399730427 90598512 70237314 76127571 515571589 562827995 271054793 915160105 400115321 879620766 749697754 645225168 657005757 107070686 162128650 584971247 750580511 129299496 154947041 923469447 414187402 470722713 299283918 594342583 766802794 912996100 233131310 148096463 331773655 157784243 421905598 390706083 628257423 299542071 371376722 7445337 844914472 821270103 393600438 58145574 501232868 326540707 971510482 119051712 784946293 451599582 71933153 615547263 277131313 591488487 408512363 210906101 507546381 972955074 486418904 9450563 492809108 666554431 373333004 246264968 705336291 684158323 30625564 6250521 697946060 832201031 822351170 87609223 7625020 570568538 706805627 179008544 289502071 594923688 800298834 425351595 345875021 434105457 559680439 997277661 439332668 582836828 700259245 653425331 262690009 785517058 536386344 579404831 327021800 595060985 188913158 839508629 717721671 66402225 138931269 190287657 155566349 202281117 491327575 164477141 823205135 85723010 631433296 903811108 445694625 430749823 106505996 130022470 615092417 204485105 296909010 961214626 138618214 155808560 795860036 32642661 964240880 511187011 108820330 109281358 372041774 871181756 25581421 624734385 845305711 43384468 177432357 996825014 351698038 920810845 136998044 681357639 850285967 673640764 810513984 517015861 344645959 160887860 952701220 610416380 691874388 577621537 497567908 237680217 912898681 559428203 263299766 734171128 331979150 451792698 575264581 495865823 374766803 702623903 799364660 50561570 148157536 395297460 379792210 66565677 576998631 608241121 653782903 218014038 486484500 166699203 623394293 728250452 746739438 199758553 85812867 608258792 55778715 438803344 436943910 689716959 687590666 706689521 193174727 344116990 148841195 589709566 930646965 29791209 47914120 499903494 394755753 910148406 52678402 294641004 149686148 746861807 344958579 647403235 442415393 787407853 700421980 669641130 918107706 633093088 818707770 293384114 698187530 387411580 203266877 877644606 551585730 665394477 843770240 730236417 856396773 336884165 835225685 655158412 491099789 135527806 210784524 520738898 808893916 609589177 766397701 703733378 170826950 730641279 73745817 776827279 409549443 443793617 319430128 448556183 234837587 587438847 148496756 111978370 53423922 78491844 833474047 60455535 157497427 863321940 260465306 808570488 560647304 842307872 981400734 384790242 67069373 472352352 171155559 665610388 147728876 886767856 622205463 408312110 367795374 769391683 997173316 821333106 698900314 63310980 218347770 817272439 149634029 46956772 366444951 121200361 194544097 495771305 368526853 308218358 878442780 705338441 868847176 223654975 657225001 103825180 77822904 492498773 171591224 407621683 237375060 316058849 18177244 651644341 110348296 726397600 30134020 343496335 807080920 280634292 214523259 807490785 486776454 964789278 626318066 996400678 351359966 917054792 794830800 263283241 110380931 952292445 447244224 336065498 407576880 454940583 97281136 775748976 269925679 174274760 267734558 153415333 547714996 781264757 303442028 986753160 417534581 223584600 233433698 694000757 417822542 210025174 819869598 600308736 233497650 149214303 94231357 382347809 20650264 882656673 819014301 834343437 753718734 47859110 801365880 637159023 441655400 138601550 956581405 192217037 184807134 508695675 404589239 111690038 601647000 671330788 537826391 362432320 434935833 493856721 483544 312074396 473498819 191587478 837822964 387493028 832823882 823015315 29713536 127845143 600934347 185712219 499195749 126043305 713555869 579099514 903793716 732655888 460106570 820858292 457547946 78003847 178718651 355163363 138958890 846481973 267463218 430466226 405794908 535556935 434392374 522210131 474516176 351006421 932708049 43270586 957621458 857621483 876385594 141470286 567369836 804277183 785963132 858352158 715536622 556687096 93754957 50406557 489651256 33593996 626305737 978460743 128844562 622732754 286781801 634016959 120620994 646411538 191714288 80529246 244001216 406644496 811643070 683472584 902694771 527463795 291063091 948430277 22449422 294725933 275446423 894434155 909464143 59736130 348731378 762787114 454096972 636768370 226737960 565374672 105632785 179409953 726026354 177157200 729612546 430282708 459065500 541585652 307094213 281189907 842627533 834125745 171297201 906021347 473934278 866495006 603493705 784008869 936323089 242124676 628532284 397324615 689249499 43592859 234457100 799384758 331011946 69342008 361261256 834364380 303917972 85285478 912490228 883455381 617634102 116660975 40010342 841044592 967114944 563602119 196382492 839679713 545900724 251531190 940373398 562551597 576147275 163714004 891564574 607721582 137986730 935809913 510946740 340135516 188646013 236053205 300774366 822392863 398775420 233627745 704517508 42141905 841339554 297045687 136369478 280701875 189767146 205527888 25435349 262679406 290793406 246815031 271835376 486632404 439253966 46725969 469264156 401489039 971659299 502349064 109264926 222522574 863954411 261114460 782966267 815478784 875523352 735606131 78981747 327886648 415915728 834278945 626546754 524590780 251210417 636227573 214779840 922812290 249646015 786091016 763528054 812686013 990667364 112592645 558537581 350431330 920754613 134683471 121464657 359983332 283725743 587197452 389415509 476543909 182121813 77970783 921954491 604335727 921385117 152847275 456278794 812769991 543496280 241017797 478649607 554260049 244224609 594302287 941498572 796565622 733023966 227913479 920634754 801373069 940778224 64899268 836405462 162876449 499149571 96270026 733226019 559225278 891788996 217455538 473870801 807952916 754017483 501103706 491530361 506145955 407560914 32122837 86558667 347061910 988293091 363397887 110694446 579294964 973929873 897043580 47575606 687354864 246046024 667516746 25051110 650429062 205907136 340353519 16009746 660383818 835497438 971111243 276661968 961318457 934697445 778233560 869280717 25614451 657039398 213668230 159192378 394483487 794887161 853029081 974236393 520633884 925692756 304701968 208733734 237318798 950020939 411942067 415205121 77380987 429971517 860428308 14328910 124188969 711174923 555514840 428986797 508360638 77944301 392174251 81285933 62472027 989585129 900878924 850088535 785627846 579516959 617176829 726980070 972062770 698102690 908808918 967621144 563296880 665516593 397751284 798424316 65369181 282065443 985642929 349688466 604216181 452900270 992571234 260330654 500141244 970653860 750678973 600361563 188581421 814505915 228147306 836301444 975558355 720375022 609655226 626480409 624181257 847549669 15895297 580007798 103675455 110276873 232674096 985601633 290500165 856938007 399672773 513194223 975337013 329176018 721916376 469504214 81059546 275963530 837947075 955806027 173191740 968868147 609661943 832781721 524572123 97221950 220002103 773003471 176818823 665557931 312646282 43395688 194554584 482463180 834342706 397513755 301852000 135657944 596043178 761391130 265784475 618122596 766163937 203965761 447327449 236642742 328124075 141574927 82995438 969436384 407368682 259813646 918070550 567400395 335833656 152346101 425110776 809168253 283281539 463865580 533549134 954747543 387841543 650181571 83418332 374178725 111814219 984916546 117406480 839871610 400753450 627979699 97145919 348960886 878610727 719097987 539421693 857604450 323174805 771720776 461463671 446621258 378709706 969009603 689541887 726079944 339648732 724565492 418538403 803602997 902415004 426952393 695999969 764593341 634886713 663453053 299441748 628838770 187754634 106041835 54840188 104581960 150817187 542965804 68341821 830824561 957494583 289020200 141886842 680598611 705283864 979898675 879733413 719606992 220079727 882095290 336026158 266966216 943940267 768743228 438176644 959855825 152185563 13481187 410862364 292328037 582220394 377801499 566949282 353366511 486572450 319671568 431556521 146198992 24802126 157456824 267085643 861180541 845275899 111534153 113208213 900685854 282017593 144029703 943047898 162240834 781828153 176370406 351108273 262277189 229827344 952667884 837959525 561383238 886895002 527533447 463185250 771518626 185901846 590795484 100401743 755084180 466751325 19118918 117300392 162872833 723021503 214295315 878128924 175281176 847555852 491112621 670602362 967678985 779227911 413022320 89730626 896016734 622962837 719819106 252289300 183344706 694417660 562052590 261692210 342857888 524831939 687666719 860896746 815647778 439098023 534518104 974340926 335294990 141378035 715571421 86674954 55854153 989798820 614005775 894252461 310257246 711192170 458785533 152169254 225993404 835636674 38406320 670793602 166834533 101046084 766456373 344658394 24195507 214454094 137534447 900573026 197139509 723126349 819918057 258690361 431658193 62447061 993831533 410297349 442188820 114896238 219340691 313151270 228641778 443563825 504961506 794666846 55303315 654254923 928874539 317749641 512215923 64938526 408582572 949234088 866657522 886345082 462859312 880145540 230000598 685035617 907968834 20310596 149589283 250932513 530680890 773635492 348672992 193327657 568613022 419767920 849827659 339848530 898593675 562059076 793899639 739704553 447655972 609720529 387432781 955265576 428748726 974394707 752127346 336690268 967357063 731519524 509198860 923970539 470028951 784671597 316097994 445389757 487423037 203090997 413136746 521923596 550000745 410130550 843538303 101824123 664563086 253143714 839056652 603201196 59418751 383682638 568522170 460609927 714552834 453404701 528523161 736800176 326815334 882681711 692884569 159491538 202600930 831470551 646053089 611674474 231134097 572405945 980160847 335222892 129187261 289564686 208049208 614059270 922846418 624323903 154598227 771345980 570285723 176125007 849184683 32022803 642885505 545602206 412154246 374970750 430628177 165760702 222329740 619163438 939365462 241460296 790977405 372548011 724153468 74290179 631903686 899146489 295802486 772227677 600575268 715249011 2843406 693313064 386798515 976573713 809778005 989731479 821397949 541556906 499599990 529586396 392844998 977240667 608240598 472434207 4069635 291716785 254783704 802624460 957196310 92222261 335486702 266133595 461750647 789258934 457371522 243201276 141066172 942717167 369093946 182176883 843363918 604907067 886122423 675328401 292320899 876200237 269192275 385963786 435254068 780500799 195894565 182429566 384675549 142243141 932678786 584567778 371437291 887601783 257169694 439252514 420826010 249428445 431048704 557653121 888513462 88402208 989445420 980899961 369271998 283815342 411234260 333701779 157320643 740124473 239430407 425944397 26534526 869714927 260240465 707777903 516338400 243327317 19833890 892608351 497903920 597962131 909566196 538585131 832164727 659255158 931362434 135717778 486226980 169039707 821995220 516450132 846516843 240147875 223726101 229374953 158286005 951954338 960647741 340532917 144132840 345250134 761344852 219367669 681860652 750526558 293788180 121435113 982102257 385935857 876987136 596749801 780375501 716424911 312988478 823165608 685551590 858173361 670388341 992366404 462277543 146703052 6774217 704849978 126058051 303761217 179573745 649158064 104069809 202716079 41478389 281061096 263796153 287071648 808749889 880906664 638792034 235156148 416491764 46650552 766263693 335975375 6830561 431466078 40885627 111197610 175270793 234742585 528311071 834279228 524216583 549248582 226200957 481672560 362718893 900989316 61990070 241129619 105147518 471265004 954989893 592602102 901928942 650279330 841754351 924771752 494003408 391316265 486119224 797214215 31602695 710728705 615087576 167743863 711248810 457181684 104777559 169454114 821083268 333364002 306204045 638032619 979337397 806884199 884783358 207875757 368917165 850173172 568548012 802252753 852781062 200286396 414398771 134262621 372905119 242021605 510799224 731240162 436819948 960731514 466630062 317042945 172635296 238201801 509092608 245883410 783237741 166516257 968364152 741690992 36394120 809248872 519533260 544134573 179429418 569407183 898250796 294098697 16692122 392703987 534741836 641939728 994746239 110110902 97011600 431963927 585844048 479733146 386594479 939579429 141677938 807930645 741488739 65334215 125910398 563372562 858859713 933419769 634686385 300790563 831784830 194965897 631382177 767315187 799277069 403355914 6292796 822630840 457483394 127806508 184503058 771866199 280937863 155741877 70519742 619881237 486823699 320124495 580791768 131224046 764704869 230282283 5745316 136750943 705039638 632407201 32050423 293090910 722284845 289834814 843201274 425096230 70786694 899313262 687475255 704585367 466543590 456819677 493199760 357299112 849428374 680245866 287883311 462915232 218285248 540838385 978598260 163439536 899865674 730783420 836110424 895163740 791292372 93394282 831520159 429907695 871006123 831076000 672854368 941768265 545839728 856903169 807921867 936437346 555448356 43032208 571582054 232190634 397862954 87636955