4000
137842185 565428716 663409714 512529514 542066917 744269826 640991569 85006860 520643915 742170438 208778626 541065111 367808302 404090882 289234822 657410428 997484704 632849349 483453913 492583341 582536554 272766177 629622054 772696040 737931718 526311522 585732827 897509555 197606319 275244554 651389983 594686910 885697097 301518460 944516836 113230063 817860177 969575805 272385989 21004671 518785744 620793736 511087840 70685092 343072917 732899355 492621343 878111694 862722116 335864521 150404444 776682958 664012193 106329997 135924814 349441678 184274311 565395593 148118911 873128550 407056667 407219372 153458069 549452022 250171553 469012802 659022509 969878693 906046867 360500643 657694419 292083036 843258282 367594749 555196385 770838903 585288253 329383591 509971159 316339738 711326375 593275557 244709072 409215750 184567157 616735974 56523504 762125812 244298456 83051369 515908057 185845128 517663204 880762432 316220787 646540908 884780925 646222701 160762130 773152806 580063856 149720037 409624231 613640882 646380687 281954542 911055514 994531782 193412745 777537437 990386727 932920133 652059222 480399017 574195388 562065201 715417339 296139598 751483022 180716887 231383241 988688726 598117590 146350051 314413086 19390274 895806299 857801808 205157193 200673620 242581334 757246761 897230308 542436 885242183 565077307 451942054 602207700 117611988 955244715 851558379 626939977 342953564 916695281 780852694 222927751 552068768 965065410 377534061 275873224 125334328 512889337 826748066 530483455 52439154 789226688 351508099 812174001 419524871 327844848 405767140 426504601 974145932 456902300 907958435 384736025 630163817 23940440 886456207 801236881 112192172 314491163 584943763 497316085 541943596 525885024 101726524 72778495 708690177 841091523 669070265 77073643 84695104 698515928 678128806 333356053 319939508 645002014 988929800 493337570 81052118 684998250 852384016 442130389 765813807 638657055 298563100 334332744 820438201 896312659 912763684 66460279 535255623 885707414 864257272 671996318 48409631 50297005 970532559 594463622 918560043 709628999 857674887 908620923 986024108 918205238 339627392 938007923 401898107 89165564 579256234 454440934 19423048 107979817 768965900 562611874 137303800 568166721 363772915 579613183 638544929 361828981 646356228 397184919 224345327 96075154 465935263 96489115 340943407 877386787 197648770 988302992 745502691 867255569 8214981 669925704 252449689 3867152 948724474 748435351 276155954 828959423 877355259 344146110 493445037 715285623 598229880 218089633 125360378 472258095 531598074 850956312 581293757 651614796 570829402 752792458 392818185 862252428 259256624 48747273 200586161 413715098 635446208 355958104 110346411 606314057 89706575 919677671 846939120 127732767 289450868 20701671 729573522 375506329 873486321 838381960 660968372 584915787 4402897 572744274 846103925 24547934 269134456 112013763 451152872 992583413 648009397 940074595 706310917 257506328 23324874 298707556 281050332 488834279 662320992 133760028 711224118 343053346 782184549 501119316 183874912 231870968 367345193 5976581 296987417 152694698 620626639 553205408 409564035 740087181 271545150 454839580 186482320 808887815 844637804 528857925 887987021 991113124 90501985 541480360 488103668 336968571 911876484 909861589 29771743 936996819 358181534 291108099 431324888 767863723 692986374 982448876 161196241 497517669 63546089 884498923 550600545 273911844 168623107 92513775 78169607 320499088 38833495 667337763 860775731 928627051 504983337 481798658 146053337 657597712 155247003 646048642 720675868 976630325 934147285 629690557 374415551 823798644 912762848 788144682 264207475 880114449 196672222 152469607 772758264 499662023 38010307 191461138 797744644 206972614 748349483 428048428 493569847 344467016 981949986 28896881 937256258 492299537 4465022 245064717 550044056 640227001 507119854 101031942 925384519 76372545 675902628 780188658 140353953 465584559 222602613 126789163 98712757 654223783 247430135 209753914 411861871 804661819 343578543 111401678 710970750 86583704 259303097 973310034 31304624 91009398 491357647 447337881 507027871 450929497 461503571 666062186 606262846 589189159 176434581 766447511 925551217 143174359 821512044 203165139 824082250 467355779 454805995 463044426 410810378 508314789 51915741 2756332 527730346 822311124 772651045 405610079 709754327 530318523 502322174 601697195 446045768 378489022 704484354 38056971 253798183 769071704 588390546 815199127 291877580 700442586 229888986 605624657 748595727 477041171 104131840 646909937 826164190 864831376 581916084 501521427 114185740 894248921 205664373 919719533 965124426 382851907 831973559 540515632 667281771 883619308 229321744 218149566 73634794 162533020 823179230 65864821 409446176 735322264 846192615 757808219 223805713 636271798 888868722 978065980 528317497 187819196 935202701 688091136 325378746 112816703 257204893 846404728 853055120 984923610 418941807 371045102 754341014 495472272 677593272 186609400 901408150 294795417 351337450 506814808 107803780 365793320 27333191 589775922 805039916 697909046 4165701 344059555 464043396 86115919 741765006 663697295 552514954 778301249 137179527 337373981 111240897 7278672 67745306 197405451 728037484 354743313 163794656 220233741 157717595 155098137 705152404 563944735 274567413 828801079 84771551 896530581 216502788 527557590 282482252 345217270 729480260 340595514 211230016 904551978 519694432 352358888 884011991 637795324 94130837 407152687 634962969 638325917 314095410 139781585 440622295 897872092 881896510 669965033 457521196 785310544 448894033 224208977 419206440 161405353 455677316 748715744 870025454 124873412 898163653 786683371 272547848 438262146 200836341 181573117 579886031 11586668 432421636 269770843 939466761 415663355 67368021 922243744 968007861 129838422 777907564 603965219 886414896 242755972 846171414 658677920 358039768 662510754 895180855 889563788 916087685 649804344 665125087 630915323 688021996 851676497 105591627 86804953 891492128 51257254 582846518 102325627 662743388 463473517 508901017 599622194 387639469 480050924 382799458 653428041 375096085 896549195 699476606 594250087 653225473 172679953 228190571 110813375 281110227 800160719 17139784 192268064 513040708 197091965 847774983 526382122 17423791 460693726 322865925 911303566 267921498 449247318 837112988 295004555 664389871 449604505 695926887 348181109 369294550 678079276 58567952 799164168 844215301 737697598 194196960 419435526 576232003 824967740 99060362 356317662 421561620 479610799 315647406 172772475 583859827 26660686 236607876 828522863 952442696 234768974 263262356 524723076 530919208 978712586 213547298 750402940 779557819 206332407 201674641 621750967 59412682 718270989 193837825 13812991 641350858 55001093 836180395 541064911 811142963 550775062 225131061 865496693 532714682 379749055 597533587 152112927 301795903 345660644 600350618 795847133 100297213 146454470 786915390 429739544 678231648 477625539 138241384 580097496 510175015 883307214 721045674 4628850 637003192 840760576 211409750 746566609 277425610 332651661 340098119 196061622 520998833 147862104 89858575 852115374 806439768 484182669 867237024 137372884 12884399 500877114 136665075 696385033 579856926 68141270 605644042 678660865 556191351 145774681 239147498 887637548 457213830 949382919 842202224 301229571 381356732 288948867 481646178 593861164 442759767 803070831 760961128 854256535 32178218 56558232 323332486 28248004 952868702 529851256 731646811 781626695 34613708 403850458 863802840 786663921 967409431 445456743 218137225 953444628 339626562 359244275 780650262 6645105 490547957 891674553 270355693 724294393 4493453 220491815 385564615 593498009 935649485 944814836 99296072 352341074 185506205 651407820 34298868 438243015 66183068 390500168 860326476 837442397 453376882 592875422 545085634 993036858 423931667 256910739 330503317 688471512 368632063 800459829 793233565 974391961 354452975 196345641 103170432 953193808 412118459 84321635 699089040 106471625 741240779 972613339 432343277 92251038 360568402 807100651 771788320 958941965 973543235 98888880 760915642 593827906 317430444 509729772 354136261 193358695 851656344 241183987 587365062 94271563 853240528 177193516 859861044 589944274 538038117 852625937 597423911 590067267 186855846 218399056 977338108 651909695 506972097 312513460 237718823 906658387 465299970 253762245 841781530 444440269 118026861 326204093 25255101 63008561 68427232 374936145 172939194 701615575 172924862 955173950 860190379 811625964 336923284 993194315 113983086 877243404 744487467 719678001 830614817 651835371 596519718 575010812 7782135 739934876 497283582 581998883 956949726 769633882 818028610 426320162 753423351 452640617 472797315 602361719 441574904 355407725 836296387 353635681 43656687 258657733 9540142 844587077 165780939 539428512 387709913 289186425 328614592 216732654 69005027 465384003 883980838 284226393 381234547 469782481 397213397 278079968 468148913 395122181 284469916 320592716 557777541 486724315 325940728 228481279 143800737 809769051 422373839 248598683 511460730 793381449 697513936 75478625 588200113 342075946 850048430 98275182 565173691 396634479 499831134 428977574 389687844 478376143 761134286 481573055 111855935 115282532 975076508 625592142 719812728 926364622 355369768 429551941 89662728 573771558 379505199 451345616 271176891 780175680 605538092 640372777 520674077 151689859 47858199 768429641 950639962 618408260 255283194 953136160 5884328 860670297 800442900 354112036 385466534 430530681 52434246 525697001 982423976 954177484 235721505 798989052 292531788 932584227 445345685 749294771 202411013 515237740 571382613 147284803 381313122 740330563 47067934 206576491 362147869 398650924 253060722 496713026 452970040 142793371 840791055 805809791 59700640 171296745 403588229 766029706 971253900 812821893 482993293 120827745 481727300 541829956 800357866 337414138 668034493 977928680 976065587 506648296 721053873 539583496 506883828 187166611 913583765 997645768 877338293 244921858 212162662 421319438 496789856 406291896 293724462 469101666 25897612 859650425 650562994 529443438 46354575 755085404 501723647 754508870 261243987 36835828 625661264 708518492 536606297 761468714 619335312 187787321 175138136 41096343 626537932 758337643 493546647 379006813 300507956 825905805 442136285 22860849 878719662 356661070 198949618 526396617 464088823 50994224 662653404 418685600 157132013 907432750 57237701 457554350 300189737 129614005 201209542 557942429 276181131 24238080 525327878 864065161 469742035 477133716 948996246 491482315 232032847 621625202 656079031 753308729 194041925 734542621 111194386 181250005 709354801 287380382 493405755 761588365 109155878 281408989 82704337 523857790 79257414 232078488 456748037 911844697 629181598 307942738 664488723 70089769 505896696 375928837 986337971 530605340 453725550 498713367 586320751 901280284 257772327 281093632 455761850 6233225 363799240 479815193 223595521 654784574 178366036 50551831 592292022 584051350 299800195 110404956 139890397 830410449 823835647 283505743 54570472 698719677 445983677 652116874 325803773 116903374 682781826 253742660 156270768 452964899 222434192 989230194 900083385 418982348 315573807 512724157 583086810 356488568 375387121 139904407 902839929 142711136 341448327 231200351 518018389 708773801 570650767 507899318 10781706 625597802 125909100 990809222 162969263 917155571 647007000 302770488 283864642 306038872 485935289 673701488 150551328 786847993 970852299 662879899 930702736 463799412 284753739 238582449 563409032 414230644 137168835 56471235 312512195 712495109 119098456 724951663 326071095 13117140 729094714 533010684 788381931 321413872 736494309 530695122 329132219 628669490 63775116 113154772 548450335 631384975 226703497 486667077 302870822 659087015 106572307 199533854 646104633 543292160 570884277 1847364 197841089 5542344 39786856 454461576 820242426 562227262 929947174 322617218 383377543 77537826 882016780 717956717 969702106 783705497 669174926 159896187 700075911 571527780 161557545 422543742 573857749 621771039 950398662 554359027 949737372 837933806 848921303 313091061 955279798 942398006 486167275 946494787 977415876 871415825 721915721 5982359 183360661 223237843 694886000 254594009 583329451 3252134 735542139 694831964 202923196 397031405 907544745 818876399 831940709 61100630 191383181 981212731 279865665 418813319 330923753 393018811 364636986 156323390 319498947 801693826 313915462 953937587 869485418 344002392 300270673 876071662 471393433 60578981 31214738 730730135 758427440 246304490 945769185 905449062 230171093 579648257 964131401 764021922 527884340 917239744 403135815 149067129 154091741 579239464 10504380 865365798 317600193 206014152 305258653 703464153 475978864 321553937 161624316 384401348 213223522 4709734 49091507 868321148 572293489 844156477 140066427 898715513 885470442 121294361 902525845 185516110 522073657 69839058 791917064 324586299 458821079 823930703 22148047 325927697 126345714 41190261 69074673 413781025 704992225 199322575 639470142 709507613 310797622 176475171 620246759 822055254 78572806 325022034 686862364 856922049 459149736 99311155 558509977 675002827 571548601 772380648 418024822 710455809 696934451 264670470 108808020 681574902 562392809 667434253 60249916 947251902 519551596 397317371 871571676 54355270 902122844 436050804 368823982 438410241 39620838 969914516 722268456 257986650 172061911 357957241 622738290 94056480 136407081 393527426 110317347 851123278 50437701 832393671 593097576 84242440 758509867 552632090 10288886 101727902 54837754 815664763 905588768 445747766 659135348 169624238 891714705 653413281 264361016 171475013 196278162 505654408 747336321 395334590 707008255 244039829 149634575 43864277 990592810 379395014 969993738 175051813 291646075 777011184 176810233 402898903 710211637 821057677 991139809 435622317 614048848 261695565 590152405 271735923 104864688 102596933 507348720 886937900 94461015 986257795 473386826 753474061 646614901 962702305 817586827 280037385 616508051 30233030 484547755 753726898 272010689 978684857 968906490 64951502 814259015 19858168 624859495 868835442 124970392 35372685 376896838 885442819 975252116 274253403 481055298 465049308 845320372 440628726 768495451 979961280 446459660 802040646 291808711 169602102 300169827 568638395 740575288 650974540 365929095 151950772 568772005 992522087 353363026 930219602 662227089 32867911 204338924 420452714 237602077 698841592 815085637 61582242 986160431 690459454 225088374 129343713 99322568 953368754 511710291 411763658 286028229 285551792 922089470 901684307 474600599 892733850 745981926 880646997 868001596 521290904 356087518 812186709 347905866 315172145 870302394 81089588 822389224 232329101 393665399 950865489 845326748 557944877 219300369 475848288 2253463 351543936 181217940 328929065 287214132 330335162 520374309 101429738 161433692 809792319 605146072 274837674 543969984 518042746 422605971 436366973 139513123 400489273 979372096 870010851 868739685 561750282 705003290 296996097 683305714 957049401 870034946 738398727 809458147 306824889 698834563 515608182 879142135 809408885 957448359 750671539 377200402 641743420 513591104 550532358 912730823 390721804 167979299 913519918 603195459 260039901 424300778 819935367 630128146 594667067 638041396 402280653 827958547 169885561 155352407 533001532 695761731 807703868 671148660 631494217 520439015 680136229 629759226 625985885 62496272 922705378 468537249 360078188 808399002 72095287 427760933 534975094 488933246 218216379 100821617 877623313 826239337 634313508 306399715 384490892 580523048 431971601 638366557 642917374 172071178 457165168 637857891 374639297 206617025 259079446 706214537 374553317 626845189 983831075 783033206 511247432 386430286 760023665 349717422 884713055 281789617 718974907 257755412 433086313 293904600 423608342 701175296 705084343 692701291 813549625 693218012 567463521 384817603 521402455 439486102 15302387 359885575 20431048 169203973 394805135 601531573 344460100 813065103 261697958 660195570 482930120 866957644 81338683 907061378 83151426 948583125 817115706 653073387 646654153 980256471 915645430 647751156 683789071 472645654 478576315 321324985 931823196 951698380 894926578 256604936 823573114 328351177 965142013 218524724 668430029 434982840 526400668 339520540 988095767 53070813 822098591 355941673 353098614 242929709 654232878 151644796 370666441 354713517 652652869 311072231 426680849 948490162 785643911 607482936 635228641 132203695 499404628 607314330 970209924 56933569 140708296 327578091 15433879 156522496 21433710 413868727 205229614 736192699 996070618 987982502 283536962 93007325 81261014 846982358 790812696 625946294 128003543 231833179 965701088 120958636 347937506 897786646 585256512 925540508 776049045 972102139 466875128 13109035 328770715 553674297 139068463 785323351 485438691 434736379 111462318 837330670 242259856 229998718 169284844 776129595 411179142 320527316 528004120 802353397 653908769 481852425 969035899 686701927 338143714 309653839 61957600 894710057 748660727 930320719 23786953 660762455 894560127 983128378 176087204 911683362 222425171 814392567 308388177 591902730 954349738 41867577 851588002 356894803 577121701 653966811 255072118 545773070 881952685 869023964 562391677 382569893 444229304 734780722 793479569 720503382 454652415 297779209 373371075 323392994 473859749 866092668 585911650 431747445 722653748 425309781 281194577 824159417 977201130 425636238 297375300 152541889 797247824 411588666 185631082 67703644 811816502 294541515 312113973 827756294 261259339 751267778 183420854 778511441 381988993 380992189 286058447 736580461 149193036 472433247 448537627 244542641 978310227 749144092 73353324 378811556 408963799 454847224 876165198 442163591 245059733 744933051 550621335 650026444 194881999 763341780 766228900 603734112 376595797 656432702 802704319 87319911 570215398 757515834 173414551 672988211 299101548 828047135 886455325 498738392 435865189 133787731 145519484 174004897 626953123 261177474 193854522 786394977 969252251 807435115 43132380 489282764 183751179 934923907 513541428 402639359 4076146 592316333 270443644 993223806 797634818 79855327 470900301 422411642 877233105 571011171 875582585 491321004 240891298 389605147 683712046 710535202 192979808 636717632 173440597 801075681 70903430 693220211 429735953 481528102 431030407 952361678 578829590 554076673 626654402 403569335 947685296 68323601 216823569 268465146 471007973 828675059 852364025 301847055 568072802 883263210 813860126 286569096 58492427 596808273 712240529 604202769 743289620 191188470 675987608 749954461 729543766 53243321 268176578 966254487 800442626 21095866 941736950 714288547 562182559 541352376 307488730 962573 750838762 127664130 726461276 152790953 321927563 688312499 965397001 281999991 121329817 459242474 121173969 294672960 889023907 392176230 221133080 674446391 809550812 634147521 244323286 143173216 758321340 665258089 9763038 359847789 321444096 778319697 381112610 126064896 60396161 275755434 625363735 705045402 885498808 320887454 258392718 597766710 229104522 843869570 929833672 654886955 211298833 825234464 531680641 992725715 923162952 74792216 615714397 727203885 700473426 891737429 80882649 739371610 224220599 491637414 853487573 754493003 678105880 853404266 120251295 619539842 203502133 178487400 576898474 413192144 213692556 487749820 188675123 481103952 28973906 622857049 373503055 359831552 258284459 525859229 76111754 199984799 828806558 406748211 717748157 116594819 121812183 9433072 346268527 250812023 340855060 809854899 872132969 240147901 797016576 452972788 884597026 262067952 908805123 411468079 884688286 815077804 984253012 120803148 913172960 734776049 398306396 753979031 226260614 577871082 243799859 979008271 576509885 509338757 287347838 250655074 146923049 673833316 845190884 387315900 629654482 234443105 929439836 286369794 453722871 501974641 84988152 458858286 632807552 657868707 287575012 718268161 744536417 589003521 998060030 696798233 119666473 312491667 288055881 821065572 163105407 774124559 494446722 847911085 375818998 238882201 773316730 466522322 855897084 86931892 252143851 12810773 418295693 955215437 931322604 213775868 922201909 956738540 166429879 675215880 53630406 348548462 835326389 417589239 614920864 558364971 519585475 863937529 43883488 69808663 666766641 913184370 845570991 169679579 332221145 339055842 316593012 438046370 949816807 889445842 154654173 509984921 418183356 947233512 311523389 852646267 452404767 738295523 860455250 852626912 565727352 312342115 83884515 871477341 937177836 876738006 20636367 651768495 577269550 35977466 408296759 803837412 489440065 983131411 781819068 677816271 225277104 720796325 574739381 145343296 538477389 380080261 872678897 147485379 403086578 298590451 745637424 335743419 616690161 98171785 716732539 838709857 575705277 298504177 240529111 966683508 71416686 158349976 926190068 233773609 952058569 731883179 281700354 764637969 949680796 629910836 299946050 583500798 217505623 720597882 509021961 734423216 526589750 341951731 348792002 892132556 77800630 786288143 348948400 281599929 975295485 311551404 491791773 438240019 916248370 838487785 38169145 491134121 914420009 626207687 576118242 417920220 57268347 393913018 140900504 414006106 702177374 875659043 826457804 623153932 514873452 943182129 251906674 248287788 822996029 330639453 356131381 530762044 681083139 183575538 982491060 27525107 789741798 497124084 877178480 28941559 669352585 411884562 638278065 75460667 604529269 519050418 447533678 47927487 634497479 55561478 662314730 117562503 576397768 469007897 984857089 926875222 816826186 128104349 563991603 528955165 504816618 388285484 3464082 249583045 93253146 693452101 569072929 685323819 51629967 790408072 220804140 292368449 635011595 505759795 549574518 130739710 215174760 373820449 644315085 480299941 422630534 10178008 886669083 705833636 320886241 993661420 412657347 370269572 993592558 805114017 126106769 189813537 747854098 644137002 161845244 531343168 897531875 520612872 506462045 467169354 798800434 756649530 351873320 752683015 166715885 31627478 718781924 292031538 503354848 536031441 483337178 653719147 954656694 487150179 989654032 808880219 590870492 188568940 580435350 554614131 449824763 834562467 514304623 384641037 351341964 379581336 577228296 411015382 985065539 664462620 889551128 841276232 936066267 312508626 762079830 285862383 618249421 702346811 572811372 58727241 768806945 926256998 875540397 569411117 461156873 26343828 491323869 91580192 827460782 610883057 130479958 973222403 364070688 328867955 128039975 267487793 842626593 494307097 802238374 428437970 745057671 746431954 419810998 852118367 966661849 60469326 47564090 632633916 653889235 924306948 881097798 193469602 473602940 10607517 405615946 162317644 575981456 713708709 933041515 442218027 885366285 907960995 584858306 936754481 320064264 32966317 181929533 580268635 700144859 450621629 851704415 384659203 911890157 371921961 60440017 385786958 821748901 375535958 775839782 597402848 724710938 836577159 92608979 924691121 313512950 19661835 75683674 850022905 976783639 414082979 595345094 461931115 318896039 914663635 670206816 681312197 168745223 533995493 966943531 561930471 826471137 704504333 181339102 406994099 450258643 343717514 158261839 888591958 596295156 531410644 263029722 615144278 607059855 530319950 742405947 592599226 860581617 522559625 768694437 892793939 612440705 176759869 468348901 121107190 262779377 70114601 256649003 134890872 269557147 432769096 220092131 616455412 655232445 122615798 621957170 91831389 777645295 776587686 354918551 974342841 385600976 92046589 662465663 975718766 102913455 304996587 219624790 358426219 48129646 277392760 978829417 848427915 771861018 450836748 101828065 222226393 245864445 396762232 840519764 64281761 129012839 995031129 679027246 54870613 589188045 347696346 948432610 738411419 172966361 429819732 615976469 704393636 39173008 162271211 527930583 72186720 248674071 37116474 564432180 462910746 832716785 897152461 741054712 406496294 380922569 774171543 972417912 374972181 800579017 205254542 774273034 102119831 980202220 385939029 98306938 670708809 653790615 503896455 658058553 778846233 513168204 392788542 322536194 645802623 720694489 316227746 805468516 790113286 916773038 662627855 579264095 668155121 802231477 274642230 825013737 905886725 539421317 368736010 853074416 16228366 683483107 685014881 986559943 413519074 459693045 498470449 102440031 541542391 748623398 431612496 305358651 556200120 809389647 962273157 136515780 549002511 673217566 200209282 320569604 137681768 288630064 18775097 270944155 300022723 757834765 991632924 859944520 725549051 120752923 384782882 826915632 277392052 985461441 36362173 122463743 48112158 182774392 34924761 701025010 448911573 975128211 196813080 294629276 476642980 215224282 646186357 18697011 566312594 853417599 547727757 408436208 271198923 692154507 646531586 651310438 584239627 484161080 773763607 883251533 796034968 657268819 3391051 111717753 237225703 390657738 978636664 815257623 599981292 562395559 156841108 811981682 90674911 981658029 137649594 476025736 513555560 524834086 536338270 442451648 516028073 981463193 298524205 987617051 904953134 629861871 362969740 228427527 695303826 331061848 27456013 629466111 683518203 507464489 980661538 48774834 459168993 640332614 554162960 155730767 879905113 348636184 901318801 514008542 444643362 487838096 799593722 178192946 887307558 874511440 743961762 678342556 242838426 431751796 502109111 822103411 965927654 888723369 328565852 751963169 640976789 600887216 598739156 527097308 407912979 994413271 22268408 142776781 194747025 520668213 417860451 260232095 590598440 636996427 785196687 497887351 556947356 681333359 441532201 459073867 973115505 359287334 871579008 685136849 724969986 689070924 569372544 57334338 585032149 209358069 496235314 111109166 48060459 340201170 470071539 862696328 291785677 126596312 86520254 911425582 309906093 992283877 765403774 440175920 84910097 978093018 403205126 658970733 241497789 405076009 989306319 426811925 689476528 468428087 480692740 458019593 406408138 606478101 776009879 700612191 89587295 163461680 228404301 647692050 401227977 792755629 273815066 734682115 538669166 282422008 10479370 889683148 687714635 885569439 113943446 952976168 488304041 543335821 618940478 861402551 977519546 340858876 91738071 655476341 833104696 222959229 78748282 117148787 530180585 332858158 113081181 32411493 949348935 534795566 192615793 198269818 266374407 266382508 746619354 415500521 115932442 657498668 890319529 417003485 326265912 407129389 129313285 597454362 611751664 91511746 361822733 341209010 481742923 696307173 713611509 845091691 713095064 478505703 141195618 886763578 512252957 690655657 165004054 653979431 140142182 645050374 577259801 219378729 430173208 343647676 374699727 831944169 714596255 494842868 485005479 434565406 980255914 31779675 283866780 745667357 131904801 736011477 706913183 850668365 61070088 580433007 379642540 222497147 989435341 551764658 461769160 610061114 615254207 691356043 751280514 614126524 899687890 508403020 931307219 377013708 355888117 857123019 542679900 174652395 202161555 145569782 441484114 310119658 114944799 660321729 155608369 920012934 931251602 898841644 229902203 919191049 313908285 100783648 405401467 451515061 145070582 32171948 244522438 252453791 66679891 583034213 693222558 988949823 348264009 565300622 85608190 610267117 511443366 532935376 879180757 333337686 593641332 603367762 153686254 649353407 8603061 220362706 220273676 896375234 237702551 204294533 523453562 170283988 845480162 55030283 4965981 258791398 403002949 939475253 33299239 705028928 53011065 69941639 600906 549839447 963347208 769066550 982502250 63762254 566684413 459698674 684367069 449942420 532131467 428401269 35188047 765104297 671171692 788406545 12787545 20493874 904457097 356343165 506783039 247894630 839059532 679029555 472617916 800044441 200704553 207558215 648485655 275669420 309506676 261660377 195772539 238136553 31416796 625622098 738473478 796714231 420439954 982260144 417403092 962285489 230307601 401179856 683082872 381641170 434698706 762040964 377413034 16859429 778008466 571077829 847822315 508714716 626897310 344362941 362850711 820496809 580736242 197717553 24516366 422642405 868005403 281777000 992721182 843729940 507104192 9096312 643902937 783104475 418049694 233973240 432593210 843672353 713790929 169143962 720042966 921106439 423361078 148705482 219339776 503754089 792033005 490424011 585431167 21612357 895306179 890261868 17998195 781472881 253276171 508426169 363864770 574851593 962170874 519062140 367314083 754242057 431721193 61560705 454721093 769161263 150410633 632129325 549914996 742841226 793189150 973218146 163919393 724033503 667342608 387346868 195631219 460098401 756214811 640393400 374527621 558775894 69626639 357216197 884790942 844954500 5520674 106817155 446037406 760780142 382856820 582033622 928564457 175994671 357452122 117430799 194134439 884260872 186691984 655565959 628489119 137292346 559418812 280683714 452638510 248604187 900243406 796561091 494510237 162205568 21269472 659278341 311053232 7016198 276299988 844065352 74150546 274532712 121703898 16336486 156782599 158807799 86604028 117177503 522474133 809138697 885989020 763556223 694298256 901632579 518027862 891509573 612494358 310292535 607841718 590020767 78212624 69953545 503320822 274159146 299493794 17726480 736174422 112829855 706509292 634754942 382826455 201139191 161230836 80980572 987728795 303909241 500534626 624172118 333095525 738599144 345083459 21829436 124243246 446695265 524145842 131779024 744717447 167749799 576776871 798974753 802767831 842973911 568950755 910182277 224114165 242408012 25925929 298247889 463403261 551164948 687893606 111361069 578786637 615889297 960843437 442400355 857487758 872492258 378321742 467316673 872369955 685964101 59270088 123850697 715400716 952084342 173476594 318000870 163804267 212365336 173098764 185701149 284836610 71971502 547249963 273780801 11443097 74107504 807488220 251589513 302827036 863250602 658875272 242550115 490574116 680312746 861094041 532239441 865756315 360131533 915246073 412865333 60757567 817063968 100003311 796161899 574936662 443600836 741012922 804856385 937175622 569243038 569077088 554965549 691327293 726264100 755819082 566466524 656848899 178444320 451880851 23052869 918934770 24276965 324484286 238154582 476060512 943965084 948994232 10894030 41553584 729410823 64902213 485749063 923667255 422379101 575265592 701373039 970398535 780488899 932701508 112868811 504684484 372065694 8281945 3567515 253096110 240726331 232803755 132247113 12194585 845746050 529766103 264748707 394053131 507259685 534791434 687294767 262106929 900738165 186923961 595669088 765372512 188251193 109550232 210766916 289064775 16053923 841268429 613948105 433978235 35132892 408416421 992361785 713773079 479875641 25677451 818991227 653876076 221905214 322889869 447334221 765095948 789408994 491125105 207031413 626419457 208708560 312957848 236485310 157297787 855927353 212926517 349745402 354211148 89405464 695081074 528333177 87455096 894072335 207207285 159182632 891242611 831261661 221976180 887637873 682223787 375674872 707254744 819213101 740830808 568165505 939093338 844504471 109500312 134068908 234288726 242609988 849025714 392353677 591001143 548315873 676777113 880398669 105691432 704470114 971342339 575484792 255802718 477421215 526102356 163727145 143926645 332173410 645337311 995099207 769909397 510909457 91090472 478786572 158631465 560114972 550022683 674168569 457286900 402915308 68966893 827597462 877528523 54262031 586332267 93055190 28411046 559715951 464957961 897034772 294881811 947564599 640006478 238681839 394937780 901621959 960589182 568792859 218102618 263245286 386396783 810875651 734546365 378283033 437824933 200833748 477564766 99280006 119900741 7650939 695585850 385170671 309762126 674036390 395199709 677539192 730458456 418299066 149009487 783305746 659055385 738852417 40555162 353499156 451291261 65388173 388386738 410200887 569600719 761957934 958095195 624158568 280531167 381162496 747685824 892598313 519453532 269297193 858126688 42482724 610137501 915243650 324477597 41686979 261317818 480446229 476234179 907548851 139868580 360383017 411628319 251302190 126461016 877757048 851629271 188882469 103592127 906651871 946001935 991367582 665011865 113877598 61676378 199130876 145282460 234408720 566922884 571084239 910534663 701739886 315851564 930272317 817411567 663987250 813865098 427709071 221548738 30322371 982727998 78255864 142457274 173333499 607943658 450467029 363995456 871062661 245981331 225027375 96974031 323432943 28236653 970917929 41705526 636736949 27199980 686569463 784563246 329517930 751137265 602757728 464255425 232329646 144712074 980235465 213936362 577641489 595732438 289347990 597758111 246013064 684582239 66945452 929893842 328984126 548922642 694936277 112579751 719848685 489842254 954569416 543977664 327029267 539747964 837986043 612839949 57630452 92119808 174247622 825654358 50317076 879734004 109810041 716531349 121929033 292491522 84792901 550108200 66547461 408421088 96027046 455111797 194451779 526311938 769419062 300637837 885784501 327348765 158155007 68002670 198086921 380673797 680337738 509570828 373148388 823541245 652038275 69755808 859494286 10344421 619807715 42062962 316732890 253660810 285749405 85937262 1128134 743905493 661863106 204449210 872031069 712972126 762530179 391090429 582326452 942586583 280959846 919364129 864109584 568461708 77953208 11686791 350298113 853418415 78513296 834058332 921711077 401888493 763833746 362122203 60485051 77353916 367709134 689039318 535552612 929465123 360432195 732371403 571933074 13610476 754825629 69858230 63994402 685504830 411875185 767842033 504616353 517854370 284382720 702024758 848488364 376016209 36612997 249644671 182060360 2665236 132826239 272142464 785476079 667523369 140491901 243361630 340433480 392043178 701256981 255605067 860741728 576373986 21170559 734913915 240689081 895841567 98580634 266770665 29260504 564391622 794268932 475196620 169756374 830959154 553097595 243923513 608557389 816676898 139583701 133371311 346778652 144238670 49317915 791429265 305672092 786981533 363548884 112393373 363448680 593815780 11982841 602923320 75218463 616104408 344938057 747625788 69224527 692762464 958041701 220142084 200599810 37065194 888565553 706852957 592668596 578537003 841693219 344318763 411270513 249957205 62544687 510053621 631507709 548493546 142419409 594049962 620123022 776977102 246339474 814892603 39947129 270922882 943168515 833983998 350104263 43470041 498141921 21692085 847087373 694731153 529252721 446241114 689552199 615017716 814326712 785274774 542812512 74379204 763594641 132640612 5886773 569606824 735231771 129710385 186335699 916353159 640211852 378760863 481676243 504051026 883159548 562013184 114304180 679907170 910869915 184882784 364262443 989722534 912049858 136626488 144372591 582682869 613540938 399475742 956972800 65352744 9005164 477144139 324405503 266172462 219448276 190636980 512571084 845061152 637612584 614023585 203127461 544147714 948760104 980326649 957907057 195111857 842211355 613292592 270837107 916035340 308954481 308929371 413037958 420631584 528987904 735514286 969422215 836898322 479637909 570343109 965310716 615079929 920813793 872783842 290362821 303499914 598137194 244530601 455114768 258712276 606041328 716446656 613897429 248906239 617470028 22465195 105379511 23472017 194166435 616075837 819179873 881017529 1712388 546638086 318859248 857030013 453226222 228309554 801991424 214984654 189979208 356850250 86616363 497467974 236799435 831024942 402663235 12891575 248536045 620289305 154549083 247701428 483649674 287865540 272719188 354251583 616939130 83542382 692426937 405314195 157499346 701929409 570590354 291252624 635624942 942849735 838924786 86021110 36942061 210141830 273924861 844932212 751428427 209146 3387892 899334259 921647157 451886813 10564941 648075217 921504624 384429122 794449892 583443789 894081137 467612737 986672594 826442885 589304342 425481806 4582699 156360099 617365402 351816412 178765426 119587454 121949663 165112145 912842928 591332347 218035272 580178797 480929330 282675920 596162306 748853774 133592164 250668697 83215942 14705222 393595862 427544753 771124444 316809900 165843553 295293078 129036988 785630797 564321815 83678475 581499753 304654822 612612520 835461508 418562546 97277704 788047605 199512292 924174164 775979022 134769063 225439331 775030678 692703743 805435770 88384232 723843812 33443308 843037093 103748754 436662551 698286519 527958626 651934180 755914364 103618500 753665154 5828614 512404022 369954553 121266844 560994381 126120371 562406674 839985908 378553498 887777362 127527682 473276900 356150756 438631928 579274469 785221620 709715995 413879023 60230792 898070532 28239864 320437963 672094675 455863081 460324451 816820304 382884635 13062450 196259522 905256625 487388130 31857315 569591389 414807946 188400967 591779554 323491649 794153517 563316646 251960726 4214017 14693462 301915411 6011422 110717816 154907192 213732391 382171162 770088882 927466137 51558440 333994976 374317570 63937259 913449115 483814491 547321004 675334064 889202437 251268667 460265078 101668214 451593477 213871347 407539489 907862774 611076132 130666275 260217598 207892629 903667430 89332930 402153379 923951733 351888644 236376452 707093659 670151374 298105199 868920234 831353270 516115043 697700068 464459041 744840554 990377583 885865143 541165966 150641238 297796509 729064003 671825526 902461116 14516640 340263187 493032001 452888050 257374887 153894398 234145842 349533068 76348382 616912217 305840175 481635243 243826289 110110049 467728319 916971968 364130453 940515335 814899498 373050189 912324799 645149650 331923033 27006315 360350210 852961718 949122664 383043728 374667180 488888910 385058151 293705937 920561850 896752384 98375667 788774806 704116029 744023953 354178550 945071388 864989820 80124101 707676586 975146942 198813554 273170344 573457298 383788705 449716764 525259526 175556883 297704128 163029736 995577405 726372714 590847728 16534539 535385393 931662777 55146438 481348829 595617114 792666052 949663941 873790347 628459850 581270406 844415491 172440295 718137674 219928429 929114211 788907877 573068868 820470506 521954707 468255268 88894710 203278122 665982971 985930235 682156597 398153363 302092678 913107115 221416353 549572650 133806197 537927827 199824549 255866436 441791081 300087543 273752473 146921251 381054535 569096229 959668650 384851242 16795091 665566982 307829732 792879743 792160096 949814943 601770645 274289752 949732053 127475375 995642944 479532334 533278796 279187574 766845229 256617091 645261878 622768068 354771617 365766320 475876102 337589839 70598471 518035219 36358463 140916479 840867487 305715390 377190997 319672744 455650893 12286748 596687617 101177452 839271199 360014023 155633748 951301189 15780728 444831653 81044747 807001284 387500695 930963815 223609536 110354622 176744949 732953438 438062186 665464133 812793783 888999633 160744428 640272591 957563998 491917492 121881322 409988741 514539603 209121865 987209907 576655802 504412858 746546588 583254083 504208986 626238735 696553442 958925316 804277896 928397496 162375192 838139246 874786640 902564190 175895649 310451332 239740196 95007480