4998 4998
215383577 758167311 821075592 957863828 661084561 972132688 799375423 567472608 1043161632 160514892 894732465 1066943269 984598294 408440784 453702158 39616545 252761127 1073338668 311276078 144709207 541946858 869349300 77579530 799853198 410698331 623222850 389744446 198502224 554250074 258497202 467017870 146209645 84062505 745703525 631176798 830089333 994772722 281705151 129916472 554697025 417401663 802986410 999811146 443873387 723293824 138631696 789076453 149741265 971993481 939541604 984006656 675869206 841340945 952109850 344498 354548513 933563189 68792619 804092604 85687452 531526642 533577874 950363645 656601462 320558510 302387409 472602619 732961633 413110448 1033346413 779651425 889512277 118125731 641854573 1002484092 795655691 528622359 485197023 380645564 293387907 264897024 334034259 246336313 72650879 478035509 456485471 236778284 870195462 861167090 79156505 546677617 118311650 626811735 813736352 556714508 1971489 155254503 17530259 280380065 81396120 92623370 930852504 334881018 248605531 46645643 937457879 435194757 60847430 100718618 896636284 706962900 892078200 851589323 114473273 449121051 165962451 897032597 575613633 789043381 218281341 363363796 35580238 492128415 650826593 808650952 815915804 1033034748 1019867055 429031444 1017265132 526390671 974613592 672851520 362062722 139822148 1066776723 641324343 265829415 440884647 1009762139 750248137 284496167 562079851 756770287 620103978 601759060 185267941 102210128 858897778 892297602 48542095 28242374 146861595 930056969 977990022 427022172 508702598 793782854 368175883 642009695 372337782 669677850 71886853 680045795 109127826 251900266 1001935486 946938430 729862888 961180573 551833378 507182475 29829221 244727073 350840771 308920360 143074910 506162918 731792856 638462008 734825738 452289505 164953337 318918434 381547013 1070241675 731342180 875059216 769286863 464280671 309003899 632204913 826021707 100934239 462393668 223171704 114832449 988302736 1044245224 176472474 750493148 525671546 837273396 249647380 323967533 762650281 1014747931 507002979 529826726 148519726 681635634 921222602 359156639 985679646 603421235 572327632 700386516 374254610 89795451 738760383 1022029285 81108646 991919500 69821734 1020531669 974152955 559229067 92615767 792716428 274869556 339138 653258729 604756309 219870204 829582623 323164984 259023201 212990719 811162036 698732513 205444162 386584429 238135861 633785414 103052400 464609402 292300925 807408144 199590343 370976224 1001622282 372544680 161733639 434984539 942563196 718469052 723039571 120401452 834241818 240213440 634934451 647087511 288339789 517097067 730917011 767129445 597895202 276921654 71952705 728487779 681650892 768808928 279284594 467450081 141651489 1070105837 874562237 619169076 844351256 506112546 659608607 978592308 583273297 667685643 841349238 705833151 297237389 583806837 237604614 276572980 148684337 80781812 817979383 882330616 568125896 592223838 1030352596 206660597 748330878 196794446 536599821 683931926 1031026085 65044898 250174583 175129804 595587636 839801086 897429959 495176332 114185539 761055303 102778650 504725071 782988177 904893224 881872496 610597648 802906366 355800464 405271596 421316946 48114449 639898162 907714966 294794647 36463475 92147972 867684186 335754986 276380273 705678785 816244742 64578902 653339007 619525735 153696911 904233069 192687536 163019193 6028493 749045186 788206142 1054221758 309616122 1015011183 864602888 901699136 788736311 402977424 448421647 187560782 456259591 70170054 467559161 258670522 1006957778 883079093 574522254 914880412 144321892 267300230 861773885 815808205 610923883 466379110 1027175832 706322285 562419964 291289348 210229204 870570078 718937871 426593303 721091914 330808263 376265726 817105622 628939000 1012489618 530486282 873657470 980616449 768987629 157871574 349363664 805125417 1036352461 681571562 887670673 305391962 126446438 372337714 724845832 426326049 76336308 157659260 800912003 946587954 210101750 438250238 804617170 314730464 1035183662 723080141 184169162 451761574 220251042 1009435751 902968771 413639841 1054829150 612588074 128853531 388440594 105773743 887941338 774401713 995807457 240342953 34307359 159685227 36402197 698467747 379399940 821213872 649832798 720689334 230294650 516611566 816386955 626127681 353723347 80680470 709530900 340251752 389617224 141332251 1056021137 741422736 231529075 653899127 19494209 309427684 1003456213 32992421 418760068 1035302612 266124370 323966376 437712225 1043670160 778512560 160834947 38093570 770842513 603838747 206244799 527719218 150471697 1065852068 672573672 504398822 765259918 344454845 587928848 1061312177 79631436 626598335 954562122 925436750 302599632 896737636 1061889840 857821722 741235045 61171021 839773534 134135447 489426842 744094589 661110773 139543018 713700290 869520093 742202905 44184926 93999730 947031478 140342643 666105055 599240711 216884282 717232304 415435136 1049085726 982947579 1036568064 499672054 1010456346 731541874 595770776 62072602 1070138018 1027529849 434497584 581927531 557284896 975405265 118623622 207789193 231951939 1015249310 764517081 573214139 275977853 946935526 144341358 325151338 28964742 773599253 273249550 60415396 542277079 67864188 635908742 417354651 288497712 157464525 673691175 838644771 131681811 538722465 795277892 78654775 378572358 256806643 837424566 603262324 648818005 1030366370 270824027 775990940 415857678 309938674 149787538 599978005 219127299 39800843 365718721 614678887 326199307 1058694009 791562192 390479042 65588929 318959274 950811563 914903414 1052534020 587893876 357053124 134250104 347826806 419302028 598704526 977214692 394258941 902003728 578325763 722549365 296511556 194632702 1013154079 364479503 657400379 542883771 1016797026 691617846 494951315 935172493 720661842 109599124 199245123 93129504 271411959 651786615 865780742 133351429 573454686 702165585 4603610 162498607 407554327 200423990 805395843 207686260 662595766 75576673 599150342 448538386 649096021 203657391 391671854 47313447 451993361 183364642 35949066 944467512 733631368 783160672 518234221 514641579 1060221026 690950706 472305773 999606860 1046846405 376650501 881376997 284917196 26112223 183985516 787453683 527556158 609142368 166895260 113973370 275037080 32670973 597063150 1012184737 140137272 431066606 994891617 214943314 556954204 451670385 905704982 315243708 208087209 426456389 272778962 240877009 491555493 698690351 481888895 358922953 995132477 620222329 708044971 735174814 1010547519 367814510 301898248 64525966 644841953 208943072 773956330 641223836 455661881 439151522 933043660 41605646 683443138 916230669 212637131 657632240 81504222 192175487 520417578 574522256 785351246 684583384 169143244 151405824 968698043 560829179 289776061 683300248 1054989361 251910995 104507818 513182321 936766367 1046962764 387006308 404825835 13280856 64711381 77561441 996764455 47046293 927789541 12004410 927478414 100924401 412177651 878875438 1000448584 736992747 464128124 774401182 430139334 296046184 486661761 944102287 201623353 438191150 1034706182 385152811 659012120 543634794 665396372 782820672 838294943 300399147 975201975 307070144 619311434 815939300 497314945 965453887 327001437 1030915822 7449862 520347768 1004370272 172965636 984576990 110089929 1060924059 881336261 447584167 730216370 35107486 117874742 422002816 385199450 880219580 76527677 897629838 501672458 36487563 436286247 973631611 127746735 722713446 949129763 674675186 466966876 55664364 404160196 216959524 419878854 462810238 557370755 1019015750 312654279 291121092 1069518907 941050896 928229340 119670312 483080363 933195840 1061118374 79392089 18172664 543096085 37992557 1065157066 523378728 537537749 909842840 176751921 97499304 826326088 355969334 789267720 972431047 130736442 734489721 746101007 960977209 618320124 254837813 550597064 608169364 323835620 1001682789 417265402 276099798 199817928 449678759 141801007 47657950 27113351 829569467 716103990 300966382 365379969 911250440 171351202 807753520 879353114 269640983 830332488 502458670 410207547 999931926 50256837 70404951 939303376 440675670 964692213 911507841 411569739 673768653 273720957 480698978 188952608 442013844 327868483 109980182 289660231 622776170 407993329 617290908 667603645 708857648 487692149 733493337 1015151363 255596396 298055556 495515795 163497117 999025606 136963602 1015719927 448727188 1054994061 202219739 627491604 938180853 527125299 596039646 291433182 991416144 269480140 926137308 9365292 197071674 246406292 578690270 204224826 55087307 711357542 735680684 549994023 960816929 835285318 621042007 546103672 934172379 153541079 860152752 763158419 388569247 684199141 1068332494 464984133 54838164 53533661 257488268 196374845 649642984 324875600 61697800 746932367 1068032332 319119220 43655974 639072050 467719539 416891555 114927115 728720258 1024914070 516211674 405671330 888021950 623696371 808202043 732311578 579678347 174834250 3093131 735670886 102868848 868830814 669476789 690497212 362290519 1025766266 212234053 838826775 87687442 58978282 775527150 320042933 166235604 962285949 489236485 1067748761 56642996 583502858 418712067 566015242 242658350 969842663 374949126 309238802 1063000226 983683187 764041297 974677248 64698578 400255630 813086920 413234407 764881768 381623068 688446325 901435933 609114734 326948230 1063407622 958436028 1629652 762038841 136407884 718887716 195620334 458190117 983302589 460516471 780789235 664013887 254030323 877085468 1063442047 345044479 88391467 800736573 1043539985 683978722 302185415 964264265 915754382 589053161 907854796 918355058 167577277 388690969 1011648357 914690351 569946825 829351673 528803166 165600700 175092418 596760599 422761898 69091989 870669340 950354307 394093534 589590783 498367278 291924818 461765043 530123136 676554164 142316061 1067891080 624020065 261266765 1052089727 632678621 854249011 215745022 256829082 222423769 592206407 561222830 741052051 299059909 480722228 146262440 572187922 288249487 693615958 308275996 85286595 965691720 939726665 616434590 75275223 1072498087 64556146 654248101 660504196 1043980419 617808246 325623053 816894336 966785885 133475520 832209813 731119242 281259732 260822272 953133410 529749218 302286126 460267431 438005883 753033164 968672470 960556908 850068043 278973713 410913496 1017959114 638071330 286679933 559314279 1067942527 542404532 301304162 537681496 179433486 9095576 278649619 392209828 622126142 717422538 139415915 122588138 220409241 40609322 1048574020 457940202 410771183 210753275 923317504 8825355 1011195344 974320996 275684611 606655703 1030881557 435388402 136305718 429173114 150830936 864645909 649374598 682117446 875294071 147209118 338745187 66659633 617483541 7813448 339695170 656001109 561883929 947999020 712470299 483701359 165531181 2429002 647589867 762233441 920384832 977034759 416314419 887566513 49276420 662421162 770751352 557292040 979045233 414197214 867733441 412228019 862544960 151181619 85015581 128218149 246382961 540402333 508334874 399855987 525210822 484709107 426214734 226854870 992874310 650417266 306759634 240219693 860082106 149359927 855673537 256700025 868966707 334877128 671727550 726052959 210618754 678733708 1015574635 554234793 555476927 687970126 512435443 966132421 17883843 345329598 189487746 376137028 676538286 146872304 594184647 666868317 659683425 737268187 657866105 180642664 860260869 1068240092 451164366 266608227 510997378 449947696 315960837 688173168 946514953 198935933 668206302 1069842517 373217675 589187914 324383005 867991803 47427391 621262722 867670283 12635119 387193888 610271734 948079605 219991012 976619885 76107479 917129387 534312751 167340327 599765312 617223169 1056283209 719770774 760790442 1063870290 900608593 9583301 335850614 355991288 45602696 232333057 873335911 995160277 780187603 1025795934 496534821 695743181 158540092 279132978 115517883 1046292809 305241202 982741399 646175513 735581622 64558916 494440430 900610707 187407621 205561641 878958679 443427936 423878185 708422587 590243898 971631133 452434075 869202232 784000705 849388871 692576985 75854592 490193755 1051572676 631173346 329002522 1046250555 1040445531 370207419 843871151 464168150 682774839 698143470 839474060 279807081 689964649 611024134 851441316 188441713 508546659 873337877 420940172 867333937 102628989 734212398 749721342 1027440176 260019571 682623467 509999703 504330424 348478949 505806567 915231256 799433303 1037639894 165556805 724957800 923337058 176154670 272535080 510154641 352961901 76960056 9818937 73904255 511948245 441773861 22775588 837900612 480047158 546192775 611515163 310144407 889501429 1022206678 594043473 108600144 976490424 943293167 61995136 697531630 598700520 949150095 586201189 15729681 776176950 598840540 724542014 292451328 608759827 690718685 790794835 501672995 232797751 883854590 778577770 225215114 154511131 138559629 29997393 965570149 180247678 1049164607 796450648 613401226 91900132 889083052 659719891 397719539 993187346 507033038 656218525 695699517 884642708 1009286022 113882256 734877738 573666615 39233815 749923854 40186399 591143311 539536041 702262396 552046758 927912050 857450439 1043631297 825784557 367212923 554198498 81090763 565454150 784306824 442514124 138448394 460439462 305372733 74420029 1050866675 545467430 22596223 194802001 772981375 305324932 642932473 497465096 953178282 524639651 881736602 199798982 294060788 440044550 822322965 362179536 394973667 931882073 578071904 436045013 454721663 871037673 699141686 851905122 161409748 579153191 29375381 909406060 32085107 591584297 676390976 560008651 276348658 17053481 767960638 713341113 330371176 937694724 764745049 992862039 136628722 595059644 779788704 310853416 1020071472 353278198 717115877 261400212 793753544 301057661 7480896 594823015 272252898 966995901 162563722 731781455 793097387 337737033 484491491 874826849 261406675 136466261 888215597 569625493 603176206 962058300 26993295 85020485 857333911 246179580 530823155 316506034 602303912 545618357 957788295 139601792 832896259 251768878 227324736 876836405 139055980 3823184 577197138 698340029 145967148 109248169 454116281 430849513 887765904 782740714 960547764 374490347 73473384 909152361 87383877 1011287003 540312457 698207904 502839474 90355766 124506188 715873708 832407559 47571802 456517900 512585423 495104401 1063910667 321813675 70478063 915315812 163755505 429513230 847639316 963875031 647973400 262559389 1051234029 585967363 722953070 967623876 171524940 805356871 1054608456 326105716 965564070 104672967 108704222 207349666 301373844 66920936 899200714 734477511 16725 950240981 154572173 489857375 95408713 81669629 703435531 612989546 281221751 585408147 909279498 979321070 955530248 381187341 882086070 271771763 641058762 107270566 771241248 1017959814 519366574 977262300 803378618 266298422 1045993802 86554611 917442781 260570778 310540376 348739440 1070845507 457982793 583833909 701822366 69230989 956152800 504165219 944336652 436141247 148218752 819059720 799902477 1068741311 565853517 61116525 726948406 228379097 360233712 558452863 177743076 275914302 487207702 83560785 824109492 193303680 751871983 280137623 790096905 587471896 819568047 727738925 293425802 775078368 823869713 120532110 441570721 833770137 498441679 264528222 551845373 29101415 53765419 8324321 436925200 207939152 650822761 582487937 141023634 198858944 177752915 872616012 346472956 547670536 434463412 879515507 230500110 333839322 1029952221 482029773 288029770 26840783 393304611 1018244689 456707190 718705890 676582239 21529248 1060825118 806138866 444329068 586607481 130950160 860248131 918842541 1005268034 1058744286 577173245 11602820 105781382 521358431 695001260 984733404 42184305 699468334 212837311 308128160 90718550 691763242 723681033 884519490 781366314 411097588 680518723 174983477 110380038 857456245 1071581831 471193459 87581353 766422613 1028657366 510594296 1069785332 371747461 549269652 648390469 1060481388 469744310 668532743 109905886 1049053883 7752671 7554268 283400908 283808303 785850043 582178465 93588763 806254137 1018758728 324735308 636408669 844632304 305837642 235329458 821116966 690645644 977691078 392996369 125954702 656331755 449767815 932983943 951100594 776687887 353475228 473967001 905495091 108958622 232226008 584899757 796847797 998376800 498118993 185510032 407966817 56156869 691626210 282054128 313021028 209675613 559332009 783345123 69632878 875363934 729318025 136209503 303682612 613589281 836284329 1000221375 95873519 454827429 465181427 487664196 408885466 380472075 766197142 401610386 668805815 770097688 297992068 965748783 312849739 224421814 132290037 593456904 1008140509 502073203 1039561187 623162604 951713468 316325376 271826572 1061384206 578834358 540046260 827977714 217466247 352836257 418260743 988995934 378837970 299234006 894420759 630260697 198065486 211521201 17473062 689151154 636259007 527666706 831343642 81892347 840220110 656576735 608227580 808211212 58964868 123133312 80226169 841954046 231896787 384391009 457273188 577796913 657580814 874218868 42051634 285142982 850359915 14362796 106691453 380923942 846183560 117334659 702158722 225715577 32798947 75885429 360847778 812400944 945183073 534501763 764545253 609504124 847886536 68515505 272883826 665682388 94204229 623912840 1007299096 721667443 418922215 743825813 500279496 288135640 681390625 202912232 121770777 394736452 795390540 1018483606 217865667 641537344 961515555 542168631 215684644 142786836 497199173 255710312 473189567 215282768 558601655 204847690 504729527 221968199 17790047 547167234 25818456 528939919 600519562 549657655 668087951 764676739 884439143 404775575 850221421 898106305 631607433 496411218 982608808 840117165 423818345 263401629 753913113 716065260 894687714 955034417 309529151 735893481 486135475 467840713 1027655355 661405523 317592321 664837544 523778002 1018472605 63278034 333149712 137506543 685201789 942531987 623917260 205599774 520069997 791596691 426303399 301150353 144957997 543846790 1001874419 143567135 767756863 643659779 553112835 106236096 86427498 278699269 200441521 247560979 748825400 505007982 966107097 13129432 156494712 526247039 356364507 756619382 266481852 13425250 351156765 341666934 884995292 1021651617 1033255559 225888773 73888113 914271404 256777734 331586934 597630555 990611542 429442058 1029374654 934690876 752367704 933369351 424513527 918980347 357178573 880881143 904277982 536067137 522329524 393612502 250219605 464159231 951672178 405561637 601393377 65216742 507804494 989289833 908774701 341829358 202434034 353771177 798187397 48928208 415710704 955359987 809455451 1067049356 933873723 173821911 85356486 487423715 584347818 986810601 100180478 548291038 763157625 767153732 469872610 988826693 1043532999 77863682 801551986 663833641 824283417 327965637 1066836053 903367259 575424981 1024824626 498806868 953616626 533805768 919577201 381033437 531198409 69791137 896709550 1065694593 900994302 946136180 18928794 736077686 182957941 510696504 833028842 209075734 66974035 592650057 314332375 892584542 314104963 963422182 809512860 192832624 371675956 985060020 176033276 477345297 585154137 855990586 845829818 455980332 860255272 306613347 232964895 117433933 1069786780 113436415 66147703 968228647 1057907187 1062981697 285728660 500670734 241572656 365819458 54663497 216408957 30723738 552527997 514344688 362606226 476917307 787397202 694808549 707814797 814571618 664286596 539043081 915366229 672976418 378444986 303290176 514013939 885817809 496008705 628080115 613410325 676926857 246748488 59624846 921738124 885535146 783269603 758103555 656282575 346561366 520878601 918724934 124342645 458445556 812579670 748521935 828144575 757908142 484036426 524337436 872204555 534969586 702942407 395709996 705263970 44829429 856201111 858983428 943448300 244009771 466547428 680923181 864420470 1049321425 706782142 862396724 794212851 268512611 142615449 683277609 869529335 718137638 810148556 860434465 471762750 832124832 1005837075 935148213 479359267 974674714 558707213 551897216 822337066 759689765 331443135 335378085 855774583 263177746 244526352 216541766 404096596 832645496 119639627 578189070 402907823 125331122 119831968 849253800 990333337 702168671 787296675 918907462 269976008 1039594976 531147723 1073027867 187089942 96957918 228379380 455456481 190748160 407861441 980020702 494398292 157627432 31246650 390636971 410340276 765005012 205951161 256833637 911419207 240372332 791590392 967390070 1043328981 371715584 675367790 870370862 5517355 304249280 997363165 605510721 712118936 671787905 457405125 591958086 65468275 882984767 956090094 260755001 301472659 300052885 1022483682 105795066 605540053 88185415 650169200 110939596 136264346 368015033 361839659 995808470 647215174 185830517 945048041 763725222 115554242 303188905 637923141 511017129 1000781307 214415783 501908765 169727668 920699745 130788195 802410772 289966974 104700521 414093304 207201297 199043107 928269835 607931171 1025509566 52157859 602232901 213426118 85230090 333297504 639283350 136555111 682580391 953638308 885641859 511077294 506560141 1020684313 665865238 266593003 635827061 352567375 599207002 588789902 174247263 589337658 791742944 461109421 147309069 533321906 773495101 393141633 553535110 750050289 106582922 378317289 234503571 250734615 738208995 669651941 637023813 288028073 361224936 5717788 583088749 233074190 404040511 949733208 300264739 565968401 733407760 867916549 755054912 95025250 396712071 758343093 435834852 289425429 109261654 792349342 322909936 619410210 43829552 822161178 940222349 1009790179 438935887 485741863 77593763 670070937 730411503 1056343525 848032099 816110566 428254929 447253530 15134654 547496276 664156089 698597041 613543659 911616717 1041665776 28941111 544793061 1049154594 378585026 590934109 97596906 379381125 267832577 791091321 475717886 382539278 719667073 92718084 849248358 611360313 769838234 194106397 372279085 741857894 832539817 436061445 871300259 74153304 355942799 322513057 541051609 925946551 443362609 565063931 123018534 885297550 703657974 503270081 90951332 767606477 1067034444 491308997 654829748 357933000 1051436067 660806011 288960886 194002102 772985200 354294654 299518546 798356276 480588459 377908747 399335026 434608320 761504338 555704453 323019077 1050586430 196679780 103312367 1038900478 934255989 129597671 819674485 189845778 925373843 442770018 212521188 16392382 561046437 299930724 327392045 918425983 260794912 633521659 67978470 1056692632 961749595 860197949 1072231624 920469136 130002707 563179715 301017650 1050002352 253787877 771037225 477833125 430139529 828309207 539809935 798387526 923596653 675241168 647751707 122372960 564388849 933255708 445729653 836588767 407124338 129609193 746933322 503929301 236165516 660436940 945520585 289821177 314722980 909591100 27188521 101044003 583554656 923637014 398943265 837996497 531216425 167843864 578081646 875669925 808754096 248202598 363982673 732038117 146811750 788507656 238245902 891118074 460222211 273465961 362279022 297156082 812268032 784025817 245847102 888746750 640264732 518798348 160784078 992884724 430683611 945543066 4014451 127265229 918211330 664840317 979806725 179004968 808058141 682274710 436336993 811808198 538330105 688133160 258509289 913131277 271043114 303097435 899712511 712177797 701549446 994996666 379080333 274051933 244024232 76881846 392655232 812881383 404663406 408381985 210808905 233057815 14224508 367091123 910267995 79184904 869569975 597175433 613392303 272217208 87331786 691884193 62680899 959404871 308767396 841596511 275846550 739675644 174286072 932325131 872671022 929703488 501912252 314854224 145875731 836476001 399030186 392682942 98871633 144257488 487803331 364868938 342753658 898182051 359301063 82251721 181104929 495754516 993423294 353674360 291660384 381665792 334216562 702039671 784620115 381020520 273144050 1012684618 1005272987 146763764 345099536 631523671 8138972 203704939 685514212 281997930 923102015 443064381 289486663 357789235 960479472 361330169 237497177 960762055 340598689 1044178903 75399420 462285083 83535622 305460271 234869335 104190861 469684055 308008448 829324115 681319515 171581393 823619434 47683617 968569385 351761717 679887924 735318963 40331391 841635911 952173639 465897022 260950600 213050449 236725809 538289086 209157205 815283614 258183587 612088434 84226008 525178879 337566195 456573276 267691241 200265033 47089819 223409858 555400453 1065649108 388921272 316411568 61349258 624813310 275987596 859304307 1013375548 1052042150 126558716 759826975 335175619 3019441 761312019 667264267 153187883 349768585 823547261 157670992 720630626 185492633 239662093 959422541 455280061 680507347 55556407 112374309 943472244 650787114 796645783 977884736 803546146 387210519 425193064 223770822 958223686 787386136 485089294 176647719 914307780 1011087405 32497805 370426262 8309348 27776346 975402511 503190409 397007185 983162408 125244770 844171323 1055456924 130169635 173591671 90359338 1035830711 53709917 938441956 336725146 176484603 1017839593 945497699 906570255 481528866 500037729 754434385 368802519 656051917 913130337 513452336 300308350 975425280 818176010 332535590 55642967 236127137 766956928 254258299 797846266 893818620 152279404 895356191 536380097 913738050 97748603 464718369 573936970 250962693 576283357 1042111545 812984824 485341118 347141831 495808063 28404594 833042503 785429233 103724978 32249378 197186914 718923544 1034299187 846542518 963998256 525731965 424910087 841119907 584591034 461080677 1016034712 764773534 1008210540 728218263 1055663092 930836257 532496020 73583585 980966476 147338988 283676904 421546132 33148534 687625089 630672893 368849667 1060237420 1046533030 417246161 87861767 958126283 105450471 87028802 458465150 36481365 894653713 110311316 723132103 244550000 1067899577 82710255 34972488 846803109 154499507 641658591 750059241 138477857 1039773339 685509075 579850390 1053274679 305796176 632898206 447253184 262441692 717648499 983674617 128780765 493431849 758635501 477866494 1009990372 970976221 942759270 294090415 922440145 340639448 60898255 329151085 388993063 263336865 687817433 443864961 950377321 17169634 327951227 232361879 941351840 360451047 412344944 536057406 528095705 549600034 934041270 260467561 974337699 322865321 49559568 304879089 283349141 408117430 794180997 647804432 248677062 479885351 214256608 250030055 217064275 1009334012 645837870 850736634 112626141 416232155 189432387 697064367 910894601 408238479 1035655989 755570643 414983678 180251525 208268254 858017557 440528106 948397645 306046815 812629640 712972669 417824543 514200984 39321125 952114284 806325588 98365873 23237446 406609647 359384297 421845140 997167917 206797124 568303871 118245232 368661883 1020262698 101408349 598354487 408139449 304527462 143066605 417380897 502098643 968246082 740722491 1050340392 814571416 302501641 1043784441 453963657 177614651 1057800332 213804413 184237129 21242581 643973793 79655233 300593582 384615649 328166558 947083619 309314754 893420478 71563490 227560483 778649300 260727856 479857484 327535976 255658998 753681376 56068034 29081914 371071360 447065047 640317612 500532809 877118603 105820935 636126583 166764645 725571702 1667267 719059218 988050180 890510693 621870914 552228980 377523135 346060478 828116511 468420884 970063061 231117226 981107932 601982831 660326311 95757210 294073690 691416453 492754746 186890431 225779298 553486685 336759481 110334608 1028865568 154649469 602623984 311432776 42562723 353080690 332778961 1005570918 320403039 17616974 259563251 705751595 601771690 259486501 91560974 790460959 986706498 745656719 765900416 4784269 691888582 978143786 929194699 370261762 772889656 96701717 532026133 880673234 991617 574255733 799850919 459341459 1393901 771678451 579308398 513065632 324767659 1049248828 872766077 641675671 632615759 884937601 379297929 386962396 332139599 959080437 297541996 578958612 1030239369 541172561 135417251 1058476714 1068017084 916891219 633515216 144513613 390573066 895686458 917297208 141326448 718891133 506181708 615023941 631600840 1024172926 1067404880 499818502 1031039698 115814239 562435861 580875690 592393291 973986515 420696041 1013804809 154454966 721089393 86166562 460741403 267313370 591747125 846928793 489998718 1062242625 467409918 671990058 983463157 645463738 524990481 456390966 509722083 604892631 334778004 200478753 589804756 377607280 777485588 154781908 970208501 877654046 189480704 488657723 935562903 205405377 843243563 556323528 219005360 765166331 1066041166 981529839 583157850 948106931 914792580 1044256680 556659026 370566546 1006161869 1034059760 504646266 415495561 943346571 978722888 854924119 75690825 562032392 45117236 994701203 1058386122 773272814 904777149 985969021 675771333 782789069 813137392 731075716 439153722 276133528 538978653 882642880 291957482 127527720 6616985 130099305 1029582813 558665912 1051407548 673008733 948365534 1042123880 109316068 407174303 681461755 875991482 904575408 814155731 116120070 429663512 964856517 489526467 276915478 913043020 282794573 79379676 511301382 522001158 984374387 372061874 641418228 918802777 152641768 1060737144 565540036 424292926 502147426 177437320 530679195 767028240 249647127 639836641 1002640484 543907087 835993158 290462372 1059618638 90162653 286274222 859331223 677917516 577276932 126539797 418694050 467929748 561286254 86125507 467189333 1007172385 717979115 987722756 800187487 696866097 659481519 791922346 419838744 732418503 716902353 977084296 190283256 7123242 99038669 704710392 794851614 350988644 16878850 246499414 290845642 629302468 1037370165 786937987 925346531 102256733 33980172 602442851 515791730 308214404 693252756 501432159 608001317 101843286 1070726588 271518180 272682189 1027019056 70705368 93349858 237029088 475919157 302874399 477212493 170799608 551496652 872100141 724252320 938711378 421472542 503359362 205294421 7739216 80445852 263691520 311474286 410374136 488358520 513022321 633085167 1051360114 85020199 673498111 104682082 570917006 565693158 743523770 968696658 804953915 442769713 261831702 525177296 178924305 16190029 90159978 732720625 657970632 572075711 571728242 226393165 335382975 1031722195 361265102 966077570 651285622 639934231 220604032 522936239 323117332 177429213 1043543666 69549818 685310691 622550716 403432430 156344842 962154446 337180943 510214436 380142990 654265066 439447157 731687080 797774260 448929514 110364751 450019313 789295282 580118697 87765830 441518555 739980609 933106084 388607426 632817958 98275613 747059837 850249331 675410676 400006023 61715833 194915020 117600591 373548995 761958659 60605827 321353121 306129817 777073191 39169299 607722298 638694872 762216216 901620283 442112462 158233807 713595307 978624124 143017972 229706962 476195289 728035998 114503080 35782331 922073153 457209131 749774538 3104358 431462564 864403698 858363293 531962164 634905703 1029473158 1059202377 322456714 1014924564 297163709 328703065 740699215 621792985 831408178 736280381 119077233 459778823 103392707 1039450825 537987168 102650516 156843539 614092468 247256976 348362906 364242441 834244634 716289532 103007447 518171727 680680443 397474206 377683499 298686420 536797626 971294200 367019292 485422666 213052830 304243343 641039957 545733289 863812436 36118890 565480738 115501994 59005036 953996695 688684534 76915277 411801303 110451111 430063846 12654676 623841136 424486445 735573036 625886917 86291568 552302658 961035940 389059692 930903032 461375492 721959506 379917399 14707338 159797011 266825434 125097048 903062928 169991954 447667206 556776327 754349524 526501932 140547140 124909757 423547399 444501900 779839270 169935130 205474107 807089636 825531360 229416575 543458664 881053159 566115277 458133013 188014058 1072603855 75721962 424292036 395278849 985460440 1063836762 724352957 133038928 297312707 806172896 974008049 547743838 307705684 705346920 617609111 438578969 787881428 489900926 408752298 993122126 723397776 601134549 267152232 456117554 801286744 955636418 1027342805 207285212 125821952 379006655 416740662 772345800 47960802 1005934313 441400470 652884310 75977563 465777537 411296581 122208073 899509066 846314094 299587411 323490121 568434836 73990586 478627865 891751009 1006886818 72112657 1053037745 394089345 165409249 557381957 790022777 662492669 950797377 1023751373 1015985045 1060224525 425803191 176376897 520516970 935464267 80897468 331170783 794804003 598621496 671029963 674811657 130648111 823128503 944969959 859097797 201055936 870005648 266473490 971655228 427214414 404646638 833293015 30156603 533112339 1010921953 903275713 516407477 549537677 860247773 502714593 696492351 415589631 789133113 289992781 497144723 251480047 310368690 15923355 536623886 228358057 737857766 876964458 753499698 35682235 392408537 1023072218 779518244 93329016 142525042 326646543 984477742 213764981 1026192383 453794994 970086974 8693263 396238253 237980271 882989926 1040894946 548143889 314793336 177264474 1056933715 838914723 911593728 269665269 702309896 140654653 308046017 349307829 170157930 1039138720 410527607 301191226 816167722 744769263 112465251 5682379 1001885625 928203058 63182537 382998737 125595854 1047202004 591843955 813652569 102675941 934511141 302327851 451246230 1343674 835669465 707868484 206327389 1012747218 1043975048 799569170 32955560 281184498 59321388 875549549 106833172 437800869 934122662 599357235 528028771 477830075 36786233 949976771 620100858 194223045 108532493 400906370 1048387940 986877850 369118381 360393050 166940365 901002965 178358922 544785206 699631495 1073598292 147778166 392244103 987151753 1040098235 701668649 73413058 862756075 80783855 236255424 26023392 683763308 311898523 391387961 86490845 1033460204 784343726 183180536 366707001 947073266 843238363 470668101 654079354 29960487 937476376 503980747 482959015 172826328 879053343 512254491 950673615 422393720 921067760 667601959 762464128 38771741 285458510 720143047 463346769 76923902 656802365 304390456 898878808 270192379 683822730 990076568 199500724 880013333 815044931 414269547 25807365 921692146 216363323 1043586329 673784559 282529626 801529480 279490157 72396699 363753916 122802436 562557976 968427062 24213418 1039048399 820192812 528832624 785850713 579605195 396851105 1015089661 898715938 954436383 433711316 727996183 814425603 834185140 551217667 655198971 740910623 186157243 497290706 1053378152 1015707962 412851493 319474633 847992355 1002992446 866320682 133944019 925997429 808824504 328887491 566225857 583399595 446691164 238465584 641264581 12184469 747455613 1069042803 639776504 237637640 645890965 455671250 257118932 505303132 506589892 580583001 653953210 633674223 752388936 124566101 736335981 817537952 90438666 847618266 548567701 1027818581 851162129 882344510 1042527038 9230709 1040448781 509509276 223360086 317734255 1020831181 14582867 703221811 70274609 127024329 363355780 746470410 398001073 394320537 253055896 1018241657 685872744 221215868 277402551 193185278 925513170 514027218 246429521 898642813 444452591 765183906 398691737 222954686 527491781 97644822 63208197 222278381 193031388 54019065 213755856 844757272 156785088 540848704 252034680 1041811124 1023905155 738525566 830208576 551174681 5077561 682857838 902383023 202627842 114214522 295914093 815917328 747990286 710738915 162062333 704858352 214495809 523400596 827519811 628405410 519226755 271836852 623544714 306726078 795931936 590287081 603171518 601442718 1056646470 622695136 485166066 298633696 82051722 509703883 638011867 5411047 425149540 252135646 440021842 275074394 127614895 319143377 531473366 403128227 139397418 779970914 369651207 42367088 598616057 33064144 749196844 414820150 1003247652 648824160 551951534 826538153 1054268695 850838236 609589403 147817798 22406176 627109391 721707557 39014346 7075573 995891018 565710112 256758711 202735147 721847522 204665735 566230 426202048 145103280 191827959 1003985072 1020421522 313199503 199419954 559419155 207677413 636529122 465274782 246560404 703993826 435860491 690227651 299331591 898666002 87572469 679359697 12729352 663265511 692138123 581411863 968440182 315643699 119094335 725025421 193737714 255027887 460030852 1052661068 97763941 194501238 47200084 151475728 825488759 138251655 101109675 324525501 798627353 956237126 238703114 447635159 75428860 261136379 20883444 235204616 86131735 767552338 97715572 881714846 818941733 1068795610 803200918 1005977867 824127524 1043404422 347566826 782573923 36561623 416433455 123132420 301733857 48652869 139253519 1017394175 748027234 758880057 145869896 397433589 881270248 913036992 1001034587 502606472 631239449 389951662 851168177 328750684 1067986622 1011142169 562239510 1067962522 748934468 505044955 939032889 408666223 252667966 27565333 615475245 391579787 941727969 542364071 1058113771 904355235 101497478 945880249 430345422 289500399 708496684 84901685 1011756309 918983341 395393012 518871626 109241700 406986908 414129059 68287978 966243907 673657986 237888803 140420941 721123230 500539046 350218242 767512428 511032132 567629910 336759026 610904455 141115240 572066403 869070919 857518496 940699939 238887840 990903420 123915006 700808944 1002995559 370592942 768503467 20183854 845880339 76970784 842951158 732368546 541090183 805171125 672705777 709114610 906786726 699822713 445655283 71839019 729656537 291718681 618675992 558571579 728558732 589353574 848182972 192958328 672941489 768007894 665449476 435321112 393773371 824564994 822888022 46690486 391727268 608781097 1016686299 360792532 968711272 599127724 427691780 490234451 957373064 128665232 7556866 719418621 342267144 576845311 66710604 126426107 331282545 642569927 681365533 244964191 876675664 878310362 624068084 806587292 1015105461 305089484 186272274 450092041 951716788 141433688 377300991 248505697 521364968 686962652 646949126 391662662 467499243 1024457176 500077236 760640441 97663199 467056499 708949341 26132388 978764264 676286198 901434007 786392912 565821104 935149902 1041589181 343988207 460578530 534600846 360081517 407086868 308764079 757495403 177087755 282432822 958437452 17381055 953575739 402399280 773272690 405926407 13743723 81208772 132798172 952407012 676232775 237016595 161835468 144775582 581169475 342701607 1056764807 195009692 15949076 342520426 9370837 164916461 174660407 18858283 539232130 499858371 1014632297 103847200 1022334176 718001650 858142253 840458207 1070447682 991391349 959890250 141370468 1065668994 103315690 8343626 1008638350 218438524 519312401 35494652 297262242 665459344 170493009 112808946 698069958 427286308 1014152755 381943044 843669639 995946528 11632869 314070987 43516500 561103217 105087160 861758503 469371137 792279686 390046114 838954682 347846468 333434070 917979580 415149930 709014843 779852376 653595589 985200611 995046117 441297929 398330270 341635603 708549284 587249770 1016188621 329412268 658232258 552139263 183030522 139183014 580719849 1027904978 544597108 1008974522 654886569 511513069 291986093 859803623 465597941 1013242851 513986745 339771377 786421414 477585224 336228308 948856541 664589815 907815989 246991321 614297207 545799432 1055141317 725795787 673926348 701227867 516485274 469209168 645862064 325841242 208632153 656456241 111872570 528855759 291908393 222346972 197797187 479361386 912670264 391461090 356678634 664964926 395429431 219421305 117627666 379861316 548718809 321910779 432399074 177981911 830923864 831709797 323859781 703185719 703038959 27382233 648623208 42502662 505589857 75276316 1013961023 340535246 858509937 557552409 587360768 52600185 585215335 187856732 650950822 827606487 676121490 271436440 310661487 29509660 333448896 246707746 392769886 36248159 129474248 340269427 495246522 1029641244 467329025 597943465 1005194637 898896050 712595912 586908423 418869798 110240230 70100221 843060593 848559000 805163614 205339271 693714161 242269240 127203367 1020680652 1047147829 306894371 326014768 324108089 336658190 69630390 205411277 611347136 799218418 848524308 126809397 413185621 393401211 82529699 168261636 272137328 420124646 865204367 27734202 800591502 930113173 674533190 671678010 336247728 23218061 101393147 211782731 784639707 261707513 437721635 117089818 174370198 722034597 862199546 285317302 915594863 454985092 591863295 154576275 476217206 469794859 631297140 485819656 982426816 1020290387 823750367 448002257 163567334 636027739 795162508 742583950 147114371 119491523 495047945 957067841 819569082 771935666 334928040 810725588 300043437 68960369 924146944 997575313 380429831 892247534 255423596 405648808 825372275 1031228730 151529355 449573037 785748515 535616780 498189246 410797335 883081034 75550267 590297517 965040578 596659362 1046343240 75779011 864474478 616525798 975782354 570346669 733679934 498713689 339902239 427159007 20306745 213164350 385980570 915054095 1059440844 214827102 553310031 183138232 923932998 38794373 859440497 780713881 52275291 787132421 663169237 669414195 809758882 771496754 245583220 1011672910 278601240 415955684 914939885 672069236 898871450 315041528 414029824 1053474676 305606254 1036767439 809530132 866677729 90826427 375216589 946454195 160970385 204063756 938064347 311243529 731286047 466562769 151680486 344431976 753454953 608960478 264316510 1055955654 828298258 980157162 767233464 458809917 1032974592 706054417 76463852 42639242 790968544 814254931 33346552 181198223 486979229 513793299 338637915 505184466 531512301 588148376 100363162 947147260 22888389 1017290640 52334527 235280474 375311583 344236424 75675605 427836511 1028161595 7793269 611943021 306719264 121280411 756332334 452996124 180407254 136187909 806657519 570209787 914568288 250041413 42414296 25140261 413557183 97680233 588591212 67378237 435666840 984094531 541314578 313428966 121745845 251237099 179338904 965558088 931540612 274866490 257121451 332988306 440592790 952646479 968792928 540250482 766414370 379203342 509479086 1022020511 486214016 487767452 750297073 204750160 110290350 477415909 699247721 7398594 710554574 575510295 297237433 275477941 1072793254 28677924 589897833 328708079 888241439 59623747 275924068 106251704 321707206 1052878959 442108794 908874333 250657870 411511270 306349535 370106542 1027882508 748538796 73970346 983204224 841505401 495891206 169939543 1045787179 114834100 216914687 68995398 233788172 134816510 999871207 1017500218 478408196 204107068 301370574 836747483 1071025399 832803704 272186381 134812724 882335823 85576288 647807934 599365942 178124151 262712262 900052287 740547890 959200608 220721438 912547508 894644323 456139519 174603779 179464577 309213282 327135692 729086643 896665812 267686576 421219397 433241742 986920985 369166128 728625769 448875163 680200579 847694506 780867646 226038786 102532234 194302281 796036171 292413075 756225128 965849373 273444382 344713022 155453083 159454362 480982216 158998169 17733990 658423064 97207644 98235230 94181967 801084753 114530676 143109353 186815650 727012326 823457196 668390846 689770477 803778010 541667364 668382721 580116099 725522709 383059714 949018109 374864889 355770082 34047726 474464414 390429611 167951985 643334548 901307894 746719032 209444694 866882598 1046183356 968715522 810210313 25968088 614463944 259014319 741764196 863077986 305240216 589234091 341710888 83637377 439744463 798417828 1014831480 1043731574 260769457 1026497804 36095836 265604741 51056807 302660506 1057579071 393629047 701028289 173218505 590113906 199406873 726744879 411033688 926036135 290318523 401245639 764316361 110571638 898802098 114757763 155881442 837894363 343479766 479315200 847678254 691022518 603008516 957314048 392199293 232676682 676678813 234771432 360650336 1029681343 279585798 487066434 710188206 53622945 987667750 504384316 190632706 858662494 537578987 225704488 643627834 734378955 682721222 575237627 161768441 4476320 687818282 748795598 877430566 185652727 84550928 466155871 242858092 669685457 1024706422 746805649 161047480 372001937 566609371 1062204647 681728958 50950271 813006021 380103949 810989684 1003490118 392196924 1027506768 1065469332 136910711 569397580 339820065 255394078 743830532 217507463 160837014 454896085 326264517 49332352 907979753 831937981 565489399 4542801 603340023 739821731 783132600 528721430 1018296258 258073237 663124620 229092720 530546927 330874470 423879131 643141123 537531721 355493932 587398000 941329656 728998972 736285633 272378620 817038459 400095835 741727045 453119121 826141246 435289050 253349274 373356327 176711157 594439956 38243558 1073581851 558462936 691689223 545471765 999909547 979480356 297459155 299467349 873282171 790360218 185519935 333664152 640557075 158092542 156181300 704726294 317320287 137455514 751769664 899587784 428346413 192146616 274456084 913421038 971765938 681973804 1065078790 851017865 1053800966 652561351 347127696 125881826 269187491 590820837 1068846799 551114497 751674602 483198944 868145925 438406199 232857502 692141211 1035761432 104947861 803833448 282586872 43447824 535406706 94732625 314556514 628163996 567707625 304916043 290574148 367581326 118354265 724691880 642792847 106193243 857584611 591375008 522700601 168107164 39918063 469578192 556722360 461826960 37427112 6973366 904271243 182288023 291047803 656506166 1060667058 331894712 670237340 479571992 330918192 469806364 134884225 357965192 48764048 427414417 363475045 139076756 23966046 547395848 388546502 821319858 1029466025 446408471 493164775 967836727 443575688 596428152 336144975 234076897 374353298 281982088 969457737 344980558 348978532 523638729 10503010 300836482 337699871 156463201 370673389 844265573 154169575 95266712 327296898 1008428099 600449381 755575134 372898171 704639562 988239942 144871107 1071875958 760443664 552199098 141678716 514859222 406929930 534647798 560380261 1033467969 806311958 498819506 330133753 480367139 660499954 681649323 418002396 286737194 6794946 723212834 981217362 231833289 390068878 140344156 264012997 326219189 336902338 545678368 608136771 144966763 91110061 1021200700 101738749 979268007 577711618 605601536 1006005450 69172462 890412890 378654657 598980513 540065030 745475247 848274008 943892515 535170681 385124322 8597665 1615887 199053845 78506295 658935292 593766091 742243182 293442004 140459471 709829602 955854683 392347205 70982145 591120768 839561845 146139387 645089665 822580984 532178844 845626568 973686461 21601087 986816113 642029413 95090220 714293102 1022357980 221486061 804113604 850305348 414611080 561272159 194152068 1021443490 437483874 283142431 197422316 539667213 780029470 120346997 542584192 629384239 356003251 539351053 973750345 773792342 931964122 32843894 918937171 27936755 689050258 526160547 903579696 76274461 266843806 569894253 340368500 371494924 888557573 1014827279 284524087 387015582 1009929106 620503464 418368406 392496597 81298002 924828092 1001628722 753947735 833718297 1047211187 124092335 830137580 424577533 679291225 219321399 688431108 508214488 525198429 217435380 269937455 797694922 191783634 179294362 299656099 813774518 1045103793 160274394 646555833 157601984 74094421 818320368 428488304 528060118 531429373 398124310 935546856 894334500 697026125 976494863 634649065 855210653 492512974 346565021 508855642 375184761 176756073 678728459 404302282 191077297 786352112 673389220 342765546 742714501 951853206 195374393 358296593 700338167 828321905 211287455 1004587191 458927438 253577727 176270127 238690554 934052244 799417246 387151941 639380252 882056727 977537555 711364801 116798211 259290860 706454276 1061249161 472999096 1031930215 6963070 391182853 527460072 66626213 516439664 661523617 651199846 945630722 157777709 735865679 455699367 683635619 290743278 612868866 374009669 737697517 649356366 960897332 692120189 434873612 319303628 102328929 177186480 734495598 459923532 258662538 746018533 71503429 181189783 508533171 993043014 534744840 608144087 80103013 53362335 757691122 1026192155 167192621 1063066338 217434498 1066332633 1047861275 258283942 983814905 340351591 947690820 367483811 475864799 894462336 942969664 1052613175 995506815 670230470 871162028 759009765 604761958 521886778 207633833 309820624 780472808 93212358 687049308 728898884 781508507 808032947 1005925740 661837870 202763738 941969715 786281095 909434783 53323843 1028860889 915374301 1043361101 210493241 274665244 261603747 987106577 766142051 84942040 577527442 47282026 822887212 746968780 263077990 910621689 109013825 930730269 610768223 353729539 190518037 8451281 911026115 1024914675 985730144 1044927061 670942297 274569941 98415772 500728824 356626671 58098395 337998727 80978029 659272406 329932252 731367844 1001798989 284697953 624411344 16707258 1376659 856531050 161188182 808288339 1054984222 679292621 768193582 474136638 916771379 983569643 812805055 937747213 29592056 1031579432 540903570 897969816 146494714 335556716 571420116 530622584 476378792 474212518 1061417944 419173517 942736086 63568709 468853395 82215801 745365563 62791101 355236895 393916706 813619955 87602696 121378617 232485684 489015037 762941731 1005046211 242612125 247247550 304785805 11379522 826381071 796338556 362937803 621246305 805412738 698549732 723285734 547846252 1048603311 32068741 50519787 565895637 181580949 428557907 522774378 53031603 630832632 413479716 252329976 718501950 306079453 7154742 336444589 265529429 1060363536 628268712 767790247 683707384 641227422 299959804 237437061 31996366 345175131 263925404 903635180 999530656 458586206 455051346 946984198 809902556 664460416 1015449806 681564414 50117651 46742752 184655396 747226245 359581051 986770017 377336139 972808528 642561646 845777194 973060254 984355224 394396649 425213734 367581791 410748569 477334030 212497026 842145584 833914643 272664226 519510066 145765528 894191052
872588176 144708204 928071556 656459788 353079652 1122091 442285763 205184031 455684561 973035181 246775177 1057759191 1055052331 296401397 471242221 733124359 666465773 421318986 123143019 875811337 845590837 292084406 212256098 1019290681 522294083 183240840 30380439 536111736 668475646 764366803 544577201 185754026 1047813999 688047852 945213115 38374712 857206340 218305520 160129445 217230735 39891534 160787260 113579970 164677279 195399684 390634995 1066458187 726611548 792180221 125253755 848515035 465951552 346191737 1015296256 130935538 162810568 418002649 169715184 853127283 470095859 617537571 1031449726 1026289701 239970758 721974143 228405023 944838965 889954763 243965885 865131535 405937330 703124108 818048205 715793357 894558224 536233501 668431940 415909787 923451302 535942288 485045726 513374207 634659120 746637950 307518966 264995653 628954702 242524037 300762128 324965371 393252611 151502020 54745936 735739763 619846710 907989857 702496512 663692356 828391988 176702211 193187086 953800905 879909676 37490777 1047449739 912222625 1014663602 882764689 530005037 55519277 413514557 280577761 820868302 530778389 725170857 25558274 530394091 543085252 601182902 975374256 843794982 265280487 565444743 706496043 525789637 902650354 1038726691 430298041 186147120 133742491 1034136824 769519138 774102391 33467229 745195603 353201203 595954890 634643958 509642728 451331132 520476926 603451626 444664401 616997521 191115791 733259006 753082247 368316428 278685848 593322173 553020266 467576969 35854429 143640310 600053823 576872809 891822786 947096892 238131501 805429264 1054095697 536500837 389840063 707584104 445315128 337589515 775671653 24914779 942117064 304579087 1025707507 99720540 843219960 669258513 314419232 591019231 745368800 65914104 888247048 82600157 426924862 770158192 452979627 583591761 697712116 650108519 264284524 888798141 551116168 820882064 1005215891 273935782 355690146 11734497 407409867 714446611 349668498 341514004 134585252 111694610 879987656 880535337 451022610 148735027 91141209 473186274 930795500 858958604 875127937 158212677 763697262 160271539 238979868 891157790 806461112 503310663 818154027 863988603 936003405 84066919 512242005 1012630318 221472661 834351545 1045710948 457421647 988420187 976768869 19638724 131248823 669489231 62007447 814411015 636452485 431865477 382453249 615063907 772270237 517504244 466698838 582490162 1029092900 549253880 1056534736 589447026 236932614 508301265 1017418667 1070337091 401536880 234898722 362619560 173438315 400369751 674056563 727228811 173571541 13362159 423684783 70551197 598101774 329656628 469954726 934949162 613180359 530739556 1003884428 47935492 1007829590 712982147 1056336504 70588415 406406964 13023702 951657959 541993587 742129536 772563560 63932982 232164285 516887419 489540488 612546091 166316478 543342858 546466633 318202221 877359707 694085175 577468673 761999111 329939451 543628208 1022712779 309727210 31404556 681107271 984918277 592098664 2936702 399134320 1052357330 771003321 863928646 349008070 350103193 1067086969 145528541 497816198 704985989 515578152 12007102 904703763 744255747 762473897 621257963 1020128112 328916294 867355332 598972777 730308809 289573830 294308004 330933952 999225067 685763517 425894233 557985916 885984967 809979561 305931095 568291758 602979571 936933069 569652214 281940843 949212200 448607663 528507376 859132748 194215877 925440667 221218790 610580973 222604875 244986143 988675803 169304431 464980959 236408717 276717751 816958454 15961291 1047655805 1069472453 260229674 423430142 478526024 518459445 889385402 558948743 427379598 717917339 454271957 749061406 50002865 823412335 591602607 61665435 327442519 579481995 990297346 705728124 714670316 223175088 671087242 217555043 755471646 1058422017 1010363528 423623062 220648287 259702406 845545280 969034110 991448934 304564394 841343355 1032992297 1023928494 824477630 1010891526 641500872 795527414 789931124 1055519537 503930417 759198399 292849252 301844305 372770141 542302162 853108362 457339198 222643691 963981239 1026748870 447258070 1025823900 281372223 202095451 512488312 830917589 770357755 919027569 535783561 101922337 945222338 48543124 113355251 212707500 260397103 1044083506 370938273 464776649 188461088 20766240 8498436 71024492 600427832 422997782 605934481 810979760 38317406 445432878 789040449 693136723 953952317 453067625 729745679 99408437 586296770 334318890 875586430 11295197 763466913 746913465 275643664 906424820 122484944 739640513 947364048 179324616 958278153 340393427 28687049 970245578 638331468 593554657 855301773 190603280 867613787 1048034244 12836271 841471188 444990013 63262134 829845065 307334131 502213564 81273304 698605943 795836526 749647079 685475245 541485530 47201005 688698513 919820189 990048790 968711223 421149392 131914099 308740948 465090492 1056128894 561058528 506248129 415301131 419209403 933348342 158717196 1066137436 170340713 391800750 789494508 466308615 707516334 950126178 1034858904 1013573899 1036893046 953653331 70585421 567072392 387613935 1022801956 636351436 336807493 497724171 1003611485 919387354 559289387 1054822914 811079402 1068519102 65561288 102971853 869359001 715200966 815220173 489471148 2021023 387063234 216693904 876305824 436055572 371196039 224476299 307816178 591606130 248558701 1001950171 228038826 354447898 173321938 623160258 727115545 576616400 675753621 815043365 679266640 27329338 988582556 485619983 700159910 531095652 192102478 660533036 332364342 965331263 104045081 427330639 196929375 519624733 250643950 1066837740 521351746 478218806 1024885696 118103967 338504007 231297575 1073501193 73284515 577619097 399587950 723627588 563547996 310535333 187832303 712116084 880081102 111321247 778128498 511862940 1018145315 718284029 804002083 550491461 171656233 219587066 12222736 805552635 193200337 499894804 374291375 70261456 62025137 399433870 352696149 185784791 686143107 281630703 575941568 206646698 712671140 829358209 520797326 901558245 524570774 364725972 160639939 261041065 466816639 356221496 137501767 414020634 816842407 859591494 457532518 182831841 278825214 924455512 931459150 120673963 517640851 746245644 138556565 703703464 626788382 193845701 430616752 120903693 856916087 156068905 721617277 250617490 573349661 263998884 686588858 423926005 105676465 505943780 262178443 448596085 47229816 292093788 892538361 9284183 152284636 337624001 1003660653 886382181 1051239659 922283152 738673209 182213994 194769110 820583557 921843215 324353975 280292723 124833573 546320776 412881825 95730876 517513014 301422238 49857536 1066803534 846523713 328719154 618303154 516843755 887234071 796572552 790448918 629991161 407464265 998603974 222576786 905576193 1050359727 196444025 700353806 947470128 299045346 207774223 438606710 703040217 70721217 75428702 863611452 299652337 949432816 1071035675 107569619 552069777 311159380 558886500 59439925 919981432 783868057 489344567 127825502 283844230 51144108 457285112 265216206 539433026 654168385 21464048 368061451 125999446 63856718 621532616 348230685 36716302 751379342 649460498 875238929 836603868 528842240 856154048 494958199 351417814 740373349 765294251 935090147 617466166 92669637 53300238 197583215 470592218 967370987 600221704 279967032 616787650 298170084 622117149 535951069 784357012 447023236 211517110 296854019 768465947 349736672 32983964 16675027 1072581571 217776853 690124929 940511866 1000271647 468886400 615329399 76018088 639027044 254723268 323959 867486482 294017004 954789320 28226268 919327728 593068212 677644150 629928933 791572608 41248989 170859261 1058338871 581368449 762870062 811638864 60721240 396924857 956032657 47897765 1016579124 429138031 903007378 394809590 566691228 619746801 1061836771 849328259 462410435 1001498896 828997850 786405198 757948607 561172639 120706545 231921822 116729358 1069215735 551376454 806092157 10026254 842698102 841112601 896031545 996234884 990681340 409900881 89123303 745765910 519422573 422320118 1056187099 252469969 698638385 134080696 294743858 1053068708 435185079 352368999 1017914952 969867234 907864557 51059065 945069122 188071876 135675338 99598983 90456197 488663269 28545733 146272976 633228349 856608452 150253915 468309941 1016103128 203075398 742702989 197363771 378730120 758674737 1052251999 511643532 440793796 326470322 474819930 982484855 540442311 238730199 372049675 887177963 859346448 25831702 115982721 119244928 950863072 272583109 247441363 769645806 12410559 777027232 936761752 789110163 1050457336 453850182 41714030 132885233 684250392 56661436 426679156 60252974 21534579 202264296 772819919 957688979 99532191 66314007 1018185001 833081357 144072951 1045035896 952614701 923591599 795144473 350355870 557350156 163218734 487146088 308902402 1015997435 1059267684 16657547 77867647 1027711410 133225934 264681709 917780692 233956079 508093710 590373179 324230438 95001073 470417257 43179496 789849211 69096702 957189705 319751340 983974720 904733918 828811709 802305793 487684036 14652253 329435892 709910693 905411770 405285324 923272902 847840795 131304379 950208385 433641515 658957098 171798466 219613266 663681729 240916828 606349230 980744990 656397642 887615104 236067012 337045573 289076268 932191016 476795178 939616299 243831792 851945772 833477229 321063353 502053828 453599781 414260220 227887323 583264249 1025199603 115887531 517575939 455394437 642531640 111082033 169699237 1042380674 884407258 154833322 41315001 33815469 259905413 561810453 925183804 177310440 118392359 633183191 131429295 1061820600 492920946 976416822 551189142 161897671 909624413 53053407 1064530170 995683684 794592164 1061819233 503899368 479128062 551936579 165046192 141380592 573552045 91432191 82477219 404527527 203178409 174993373 733811574 410969637 728721360 139080873 215855432 321102984 280941861 583364976 745961886 67463535 576226380 287735558 243981534 902349184 445040655 243216257 691695317 100440034 768337371 837516476 1056655666 291089603 421838916 785385174 551648777 134355924 407441789 1025385136 416750161 700609224 65648096 697170034 1004779622 709973976 401704556 232960519 610738823 1032798274 566608706 824916380 341509465 197605062 377818664 268339237 1066644066 233648679 290026758 213779416 1040151183 299924400 962923628 131460783 635791535 648553901 279255561 536503531 237503478 817402349 697388853 443313036 948175483 640485447 94999400 859082458 600769466 856513810 464150209 359076063 104442643 92841899 96969856 996222954 797758024 37390578 401657228 923454733 325929987 543621581 504283886 571775648 999863886 775739812 38078548 909884093 573037849 1024759012 456189583 226780610 869018808 900791165 573056533 176058578 974271586 343813988 293394816 679701587 765442227 231920401 716814349 871813745 812930602 439336961 618924062 713475482 808104876 713018677 45783481 57302784 808928511 72754610 284643590 530779419 1009196368 104017663 210485460 574423588 31674799 331251626 820401429 814559899 334293901 705357251 774704478 443802562 329313092 466910559 125978472 714689055 57957007 901928727 423598482 514996222 20442894 178564742 121322844 129752044 676707524 666251470 318999021 306024254 470939800 819712788 438435470 914961544 969558743 618871040 1012489517 284829222 859222449 163949374 702993628 573977783 279606199 15080959 432094287 929871260 458203747 55592825 668621921 982983037 795716753 100320866 459033231 716784325 916717822 101111929 351064955 1008792609 170737872 1023287550 619378026 547680005 1025311246 1024884533 162491079 937863719 245473827 896333031 365773982 663963650 71510111 508239072 1045533986 463377748 740538486 224604530 285485608 780736417 121574655 840016625 312825769 966568878 464204278 966606389 87020100 220967942 785962811 460776219 370743738 282384248 668029712 225987332 881914736 197087127 427375775 539418452 264205552 349980473 885933682 49291252 1023909480 724027640 589832441 812489169 105350441 904314292 142241032 44166491 538250793 753531664 764362326 792257799 134363266 684319216 307113471 734632909 182056946 455740673 670465283 974402474 853548889 788041521 862078661 474192928 504716093 279790131 390448013 825026737 1014119497 512304380 107944710 948778855 908677577 14142025 503727808 1062086480 971494448 707712791 667747503 868376314 857038739 1068339497 73423274 568697595 672284204 691961221 1031087085 396328044 8012503 164892407 1850776 822046568 862040984 531391629 1056911150 209764754 496550931 210704409 1017311767 659050636 1072111634 101555378 1034208030 560199809 626034179 767765812 586974451 705432221 827519352 295062203 742175402 333730703 371447205 334842668 567403066 288895502 854910949 1008400300 658593535 406764880 439450165 776583975 896181305 794327956 1069442487 202367178 1019830155 558868634 255460657 1015341705 800121725 429460518 708788108 478791579 881762810 680779905 245310037 386568953 2819794 801622264 614992959 624771554 401173049 908580955 895543199 920705626 1006867271 609232766 147485935 41847206 970017398 684194748 740238668 1034605265 637697063 71236975 538248439 1027788074 1054894877 1037074041 790279639 1034810052 915370751 1061179582 731511286 320700149 625826523 423472296 372559360 30268632 598947742 799090593 738759623 1044620747 217210525 229423773 485280962 361705457 689367055 575527054 699524233 1032465585 1061601680 609883373 711166810 219666229 268587168 517134904 1015455895 476394221 929244450 622997614 425307462 220879369 928922590 794596244 337047184 988339202 704696575 511793716 3174466 321661969 464732822 683125721 1066612559 365567926 225936149 764643221 954694732 1025637683 522820564 844192379 902591987 240982543 566247311 102114853 689877921 296716692 294317286 238303022 489850840 848780113 947069148 979758009 169312957 135981464 943561049 554600937 332856474 84654081 1019783080 58599015 817016925 273048037 374084346 975968991 929621528 82843876 999918305 150736003 359673215 448279392 878553557 460948103 758753389 907561727 727615410 689704099 477128032 546564909 683400248 25426324 708397560 687394712 875540874 12230042 494144892 731820722 525215408 729164028 989414229 44444722 935674389 861179520 735835536 507256723 563991562 589232628 195612512 81115796 427354433 856053416 514316186 997295030 517131602 82339312 806959928 366672066 104930618 143386023 410560471 786677056 867559895 132171431 733656633 145381633 1018751597 457306962 261022915 349570710 850345764 95659533 966664704 618172886 353813383 958746559 365651740 36554332 734523654 44961366 343138921 781905414 154390901 517059394 548254174 208625527 883392908 901569016 1049341331 784637078 1015628645 1065651825 290964039 297697550 815243521 275448745 165075930 986382540 70131395 219830816 1015603155 14775940 411106803 115799644 535148507 1019380267 786206525 976741 849439807 557512574 48895279 402382151 166252146 996138106 216807102 528428947 128103306 449869794 738034114 353792991 951107262 569798589 945126773 153592898 455949294 1044772821 1031982328 709055961 212666907 142315577 481354190 962887492 545297898 216028092 383958623 640634665 502293542 998528627 1060587639 322081456 645803067 8623163 354790340 36088838 69763772 71561009 113298523 674109659 530977757 330612280 452217140 706054371 514354682 814738294 63311529 9667673 706305038 160965335 412547323 76096119 475975741 450597001 945784525 591417343 395828811 905064318 334863271 984458677 64800290 842868718 541479541 498061026 897683023 86490578 815390725 5210067 995307141 40357738 953255309 201260120 349719066 71132087 933958434 467316294 278035077 1001441538 150731330 552193014 305932774 685130579 536014923 777817795 17497470 990628603 693838081 768473487 502091827 423123723 366571788 998321983 30162189 302895066 204066935 715544891 63683004 877122947 57023795 831856111 126370063 250340965 88053138 1041278796 861474174 428399009 407034573 830814535 244278177 75039135 303399806 88692825 129330359 824203914 297254438 383647742 584130848 304826575 566461352 472705334 262226659 869427106 44915149 1070260487 668919849 739665785 486679998 624340729 360486336 855866511 464195213 353962905 552102298 586079586 774533036 293906166 659084619 548950325 853236595 305512231 952035470 738807439 154414495 684902083 514141120 395684282 201665998 220994407 164760163 693785413 867713540 293424180 684969372 585049731 546418985 1051324494 640886454 829835274 217019785 411077982 246696349 108696628 663297875 167415313 529700708 395419041 363972378 964315287 1019664576 116079540 496242775 84645156 255887498 864102673 947370980 648410227 187444801 827765285 217795202 6866494 506316933 700019614 291090261 283086791 94717853 595601647 363270755 255775315 216700914 860719821 907059992 799338921 865189010 332217781 891288261 257534615 1000864175 636768355 1039470364 152115565 536022813 423774812 244167862 824660096 842334935 1006684774 167752077 971144873 560561018 864236810 851074947 1068672451 671361736 476541721 214425305 1030971697 573917223 315932708 671930552 682146901 203725599 582813955 310858156 901880090 674665952 538696271 848202787 72787563 222789561 657874663 152435443 862578362 485404578 81587823 468206545 497567354 566023860 111651788 132927963 1034437285 360536747 859517866 996276239 975839031 259342443 713382646 404923346 442019249 446932600 771587428 1038327658 570991511 872501116 283401194 1014129795 368607474 818003141 277187395 771161774 672204494 210884805 343437934 959643102 195313085 534262160 383441196 1002666217 833555539 1039582049 882247301 475865101 756538792 998757141 631205699 85057384 1055872985 480303278 489911414 92934527 179315335 722532818 303608302 491438520 847166806 882938954 786619588 770834143 459892335 827578499 707506642 360103333 430510335 296154128 114947126 812403485 81816502 886098982 1012693971 71225149 878409545 117655582 116184016 292773731 592522481 128527351 533653783 233447629 1025651945 933692114 495995095 119438112 295218419 798792052 1011379971 744676066 824835796 505579719 232301777 19235840 825476819 772558937 304934715 925889608 406768191 346423516 930778497 820172272 842923494 133723812 42010533 729448974 214768798 486712364 516607214 290296605 460606912 234941585 384459365 873170815 65199016 682102294 884810075 788460533 305363510 610737310 162203106 826983976 355114320 547818549 518393167 808359716 578248542 185289608 229221566 21040600 49412044 766537320 1065035662 481677719 115163532 627959882 376073697 127339674 36000145 1332938 1028680477 638385788 815832405 45046820 537975918 898965180 38842708 398690746 198805313 793497407 262109071 630217361 929171403 304324299 899747338 206454227 858500992 355179405 441757006 208712014 29553564 30127508 417505000 350579700 402385821 906309971 366855144 961681497 87482311 246721059 998386531 274243384 60647327 969942207 502741233 970195439 811800689 816296390 126638895 219792638 738575306 438673469 754766398 792193676 579618302 353222666 162334275 288914657 1003021475 708686970 602664421 375204077 865516820 653153980 959513810 577038528 438026991 519120995 308302394 264584720 1007079063 385013224 360274 233831607 852638643 381208870 1050082771 663758130 486610861 593710044 45465208 818564898 1046569013 564935215 762083204 494805967 139088315 539477285 678361913 1065674912 165496312 159696171 710680162 753932708 138846822 1053400208 587017930 240030733 1056659139 429533703 260340163 350671023 133884818 376523561 919462560 419016325 739156122 652603121 228591931 537021741 453679973 736540735 49053808 183891815 202155458 402600021 873239711 746790298 96205891 965904733 151396910 122937423 243903680 757068001 952564741 877243060 82969810 931000912 895967761 818109722 532287577 136309120 6948802 349636471 372353015 592479527 654027404 831927268 812814226 880236897 640890985 390807840 1067459798 139657773 928056917 62639372 1042783665 792647152 67049169 946253614 402708181 124659696 43216994 952435502 451785273 791648986 977961999 814367579 247006617 522879805 797877222 31650599 897128689 748804621 942737783 1001806246 869053702 867188513 934276183 937741332 555631069 697109429 57682078 562726988 1071707458 382235880 788755817 591142737 500306242 965426751 6531930 1028190153 473543345 266009632 204839699 66662525 539570085 164914776 973632447 97585883 716932601 602946198 814987657 432850292 425155020 692072174 704269346 363069054 233538559 498136151 805928255 738653779 1060221114 273172781 7780121 853600752 820874728 358980527 421737196 295173495 338430390 688143490 744046456 390706861 260448536 955719980 1024300931 957351805 794574404 388839066 589252693 943646835 1041901364 334349211 932587578 815858498 74808361 1825635 686087428 247459134 833472035 393371657 925397638 773517795 734827882 315069705 409370906 527297868 132493320 575422915 80798748 384677565 710299724 264889337 721453165 42539802 252080968 149221973 205232881 136963949 967227220 291188449 11550481 737313636 234113674 491030925 599143737 511712208 267610440 324211373 672205147 858414375 204729521 924056952 338469227 1044495875 672098603 992719498 643851233 458316193 434724066 1000043106 556527163 459168355 158330436 536610789 1064950648 455570510 400145027 633506522 283056797 23490445 271135767 310194796 1037751603 621626092 1063883065 236173227 873752007 462044766 888162921 621266954 983490153 788776312 714942697 850790371 775364398 1016797683 353985855 865346799 629374127 984299054 471389623 1064499406 1028945544 654915497 983084254 733657989 216301017 490985867 119621641 363972091 35146695 350551837 604179916 347366523 633260028 128896589 396024963 343652661 131071779 1071569452 210569420 391720636 330180974 241950065 973761547 544832138 208060688 692520179 873136869 102870904 821045443 832293427 596876230 737337414 141222467 571399632 653366619 623268377 375444688 620700176 435957016 1053867768 923214768 314979678 106225075 840968270 595334315 402033862 1000852903 1050425707 503875214 60661371 266980786 744929795 106919848 1031937106 127592280 914133165 366746704 610647620 637860702 485741925 63341917 339942640 628781135 524022795 294573740 344923158 395964666 509533922 1057918366 779707677 764066546 658559249 650860439 724201871 675183885 618668325 36960384 973415831 816858597 982852493 366985542 1055357578 405111386 105979165 97654361 141015387 7277582 182502796 297240110 773276965 740673512 36329975 958853053 381777317 921490578 393002843 132135172 648675773 900843771 159593758 168695170 366082547 1055687382 891361159 679828668 774951664 450823448 118829633 755265724 838500353 466904702 377922268 779334797 702258585 509726725 658000716 623252160 456895437 833031024 331732072 655889386 645617878 663626181 535117932 204506404 221633427 218794448 849775992 981413514 545250821 173663903 951379983 444537276 388593617 725800452 781381017 861202528 200947905 257412886 316604129 789494430 603341635 36933809 9511575 115713442 479917800 1002250225 826046415 394017310 35531495 140695227 659241088 488544965 229767320 425624116 4541447 402891473 734041593 1022628168 789178785 411835518 707805228 1051775780 504548084 864126861 245282295 799819196 968126087 509243330 346440259 382202951 576514629 863196006 337172125 149906878 114576894 508926405 256128440 693640032 645666278 804493745 690957801 297934640 999370005 451588094 64709545 582394486 225017861 398517764 109227031 1003039802 716480279 824584224 198899572 467130316 196964622 943066163 944982949 692659007 480703889 548710434 945082036 575622633 800036782 89192532 646046031 891700965 393187410 333633079 435702088 5417873 689526994 565018299 479161363 988108304 649604453 664545493 152475979 79068105 292724648 646392829 295363886 514481126 600357144 862893745 765465372 183401942 869543323 733746416 811995164 356122572 1032429048 293930688 119930198 51311934 351726170 264775336 525453978 737727846 8623314 648929335 886530264 969767364 993178578 1070069371 140336294 283847834 517993650 710122122 1032149182 545081199 914370094 1064800765 556419196 448160141 946143974 780430704 396419684 353635971 678958045 825478915 855120538 278801571 578634491 669761756 825863529 707117957 206734731 502864803 581450173 847704706 808502974 903249157 939584424 786919226 1055447590 1029983793 951727841 16094223 975699515 707844702 558244160 925662887 112389849 1035072835 693083459 84819566 648677312 294105501 838562957 594121490 466155283 196945837 472400481 412498693 832700378 990333879 112197163 682906110 803458177 453268612 883234296 770752376 882266454 8139233 462723321 415282482 911982350 765596446 432435716 404962733 783287616 240352656 343552531 702732978 740943081 475329295 1043065539 315765705 213390055 731392120 80779477 1057969346 535161470 511200301 672603825 172096560 823570390 33086608 933809886 802879978 969466490 302517899 963151499 592846216 1003757530 633357324 934500362 276411628 61543883 60953217 933250384 60070582 312018178 500914528 390072950 968938702 822432668 914516129 333379642 421610206 682536857 735524674 943775359 287595734 653246812 746891715 853837512 583041382 117206573 333441191 340049601 280548487 69380792 774260473 890434231 936848883 336256395 616642756 75290651 254973864 687296923 310598042 1047078915 275373161 469973184 1072235278 163146153 132523581 1063599668 123269946 1049119978 219950318 414034200 560137018 342561992 583595147 50695919 419622319 951128552 1060346855 963778081 668738877 211987733 1013857047 152127610 981318413 197362107 815026680 727348648 480269643 437291117 772458151 140486080 224802217 977326431 734163975 554539962 1000132571 738545388 359909438 560621552 704213017 843624466 65205048 450169507 995946912 24169201 488416547 642295415 655525169 362518352 481942769 781796082 353240976 820230424 68896474 582229760 573499399 26942167 850143959 266474354 209526497 814684222 639822631 604308858 124466159 390510755 582914766 400091440 940954886 507738496 59307026 20173841 428047486 54470898 848615164 222666619 149170101 124801083 155236317 584588082 970169738 96808512 410260934 747687902 311837922 824656396 417321230 187453834 811174695 985228619 54532560 801284647 326589124 538474192 278589035 503784455 867246507 563844368 578693632 377789539 1014261711 546597028 323298039 685884885 823588266 629997259 777181563 773747422 957942455 243971045 273954297 718585954 342270969 625815033 797038501 427350055 932434547 495806256 198996725 479740761 270410158 993937496 124764196 421285129 816778806 550261602 647100848 948303017 626592797 90136036 941746908 321974418 802692470 320330648 633933359 43270270 735312091 760264923 742145011 461361166 454836200 518014255 997681335 274573638 434881982 810823098 1057158094 997275404 992404865 641075140 238028238 286857132 211577050 659123005 73105169 973995863 54853238 181050677 19461687 362850975 260194437 246499937 281593506 603840765 425872188 904778141 1010118393 409700171 618324819 246128228 24215462 327828042 504114311 546280282 868899160 93530398 226619417 49906883 68680577 949651405 879719246 457294601 821797593 47133123 284417517 50017594 522319833 548955217 173519044 372474759 427756865 930658601 88984612 699519431 965996179 1057728740 540116576 691407345 933805718 344431997 390812241 498906790 588375507 878482643 285898197 465202597 40653083 479548202 306827339 425544276 467681279 387229098 445493529 751827006 626991959 735655135 675626535 846450063 484707260 993748792 621308513 455570842 146089997 2937736 970619960 578857812 530732014 981058440 191308834 756122582 423867972 17319506 507847446 245680351 641593275 1008227047 590709008 947872592 276715840 126089899 727929747 262165934 58512007 1023355876 77698082 721438371 1014636678 643302463 1034946246 970136445 583162872 397882186 309768332 298164909 132870108 836627707 4775427 624873034 269756403 208202791 35764674 564133516 36065093 135070988 887714528 897801297 1433244 148654024 598700922 1056883611 656423688 410989280 1005463345 568409616 403440729 813331898 701190570 99847544 661451688 745259811 475329804 1027163715 903629263 608908233 834848901 305068545 809553388 783005890 196656837 1040937448 940170210 184032771 193076353 117471569 863011544 867638506 911613681 108542011 96023480 415825589 26587731 391716294 795967409 27741961 118175846 742480570 380626614 396762732 556457711 231336958 928429565 406049995 793937464 12956961 995227264 790107125 34355084 344074964 987097983 951429661 793390012 419827054 614637820 742921308 245916062 1028862823 239241790 774213932 497894536 363095005 742961230 167658223 202007257 162382098 848457853 354148966 802763888 719307500 478595805 950174011 568291635 849494388 492323011 600890487 30078858 681086807 943866699 641613580 578011874 819995752 13251028 840758349 505246250 38819868 50325632 108612208 313777753 79244301 331112117 24683795 101597414 388408952 149116319 446439348 841771598 1042103486 430085803 83673144 964233361 970771942 649183758 965720421 50986422 77409562 714190140 694304104 1054590531 953302054 298799473 400318544 303624133 526980604 993970731 486541968 726802254 638110003 541090734 262830977 1053108210 1028760195 620575103 399530974 714617161 522159946 279569641 683860038 52194801 1019731979 767736700 594213822 118186505 358093545 307207561 546120236 1003076022 869961264 270718119 587733725 833040289 361947853 219611697 840131328 807076727 943517393 55745989 461414440 168329321 273651698 696517574 503063246 435950506 658281993 52827099 994900173 644641523 565136789 414965614 848400356 771314434 768358967 403859503 579168312 464399894 426961204 478277262 331077327 591370869 276497399 522932292 719509526 88846566 49932940 255555275 50524764 1000014648 863690277 304502241 800925781 224436921 759511961 736918025 663681944 192460479 580568544 257337097 370016032 883532579 854950041 372835950 371816911 31735489 424385156 565306883 342628582 444799482 38529032 577177182 423277199 814404914 178154926 147585364 991008852 82413394 623344291 492474495 952826277 330871878 692278074 14244799 1003935317 679105408 151645032 345454518 42074397 442164852 797618503 179235914 842215960 812687130 118679444 507697959 296331589 771528303 660967473 868269627 725639433 111776500 738420387 555775544 388649130 986439469 845441685 505669909 766885589 463581219 3930707 479588493 562766873 932453347 297205071 143415455 32284010 779460605 263986848 816213517 620129951 767703046 774739838 374217949 970790132 350290966 841353672 636985051 53668232 23297867 540699262 392116756 958419936 54642244 314145863 902631260 329911394 958557606 938236396 273905865 1022258907 345204891 945164507 302807094 728030458 105742158 83151781 39728578 606023891 309515632 226331776 758713934 621461341 214925495 514029510 861254146 925657844 1025224537 676343412 41439944 686081495 725016213 736737452 900555472 808273067 325820714 311296051 495837963 886767863 45020638 727145204 813318576 47909798 450801145 295150971 585025721 611766152 1057219527 991784314 661658726 613319632 663814426 778972232 393169338 954183319 513988037 554406237 48555257 339720024 608157218 1035033816 686045233 551455091 983062925 311642617 399180206 579290795 440881383 664897959 897696387 14420391 244362516 1019530475 800627976 966604916 966999421 807427955 338477911 987850497 14159503 206590480 283276749 626706850 552693818 1051505977 476647823 915748750 710642803 898032517 102444803 456637793 627903922 644406324 777769043 692174746 514282868 1012379047 651730926 38612254 452215482 773058532 986267398 500089268 870811784 1012190995 523183123 995350663 469865576 403613188 185993550 1019498151 183076069 816720039 936602423 681801096 296955920 710549137 155621136 340497793 387561982 1010019710 504973663 909377614 1002748743 915846089 134175856 539833230 646215561 827798262 737511120 564136774 949134307 570706473 176466387 298910813 701840763 438812844 805122064 35557150 219803641 763633773 213613536 406876601 1012468745 5693565 895772130 277363394 754355676 1033248658 187157370 673366960 738046887 892628614 201272653 794149727 40182819 576400086 183393735 63008910 21898508 431024420 272809877 849327202 910352803 529788854 567514155 50654434 125288748 643645684 860019263 673070969 940297584 882914798 1044134988 460651383 340175163 862562516 45387536 522849424 98277087 612413307 791437326 674921819 270995119 10937823 820810765 817596884 879748485 1037486235 742954392 840843739 1042678590 1032134515 484348796 124500915 925149496 585234379 500584269 931681923 66078939 286601005 438336480 661785816 670493197 293768647 616082386 880924450 835789244 570913002 954519552 916987442 260184152 725222797 578078221 716357059 179707989 514593480 235009760 75896558 755260590 1026053209 19858723 694399667 204207965 83125538 988449733 304378999 1045981156 135149993 1001155705 360504449 912148936 711961238 901066292 440097404 133939984 139169593 626060211 830943224 337246922 72345602 286577139 421782249 487235463 1038194950 841002678 632012838 46890458 795096193 73273093 349531628 658613980 879842639 1052863913 129076824 981411499 941459825 864481713 619311600 788351719 188304526 410402031 587356699 367130931 579670640 924961402 983092132 591009210 1025237379 86269229 10875195 440400295 845348185 610565671 683347444 563411372 681091368 189795146 793051079 1065745532 854510154 354604476 734614030 1044980049 399512253 975097961 187195401 943715943 1059199905 802279038 836470621 204750719 142804924 827576815 104327825 966446173 160204281 797305330 581616528 617766730 873622501 693346690 805094955 56828819 610295857 737377758 663687828 809513992 394106163 992185607 1033844707 671461757 158045028 560890949 864142996 758802764 996512739 677899939 300380935 344853458 572582641 955050862 186271743 958198510 1007387251 593820858 87976228 413792389 261088371 268527069 210888065 400841984 290411935 385784306 766253574 782548428 845709257 14793303 935339015 1009589209 380709989 783983919 651813819 57373212 855346958 711070689 907972287 255122446 324149249 515688855 437211792 1049250858 154797729 938955200 583370516 953602675 32674801 734613135 104165650 170816235 78957853 699717498 309138614 663718941 418579954 860186555 131373070 455298452 345705313 475028690 460174735 410795617 307486208 859112705 555040400 953602970 264141960 287129039 499166670 525899477 867515992 305963654 29346278 89382065 1015954929 907102901 184375262 780274510 374887288 664901806 255679901 88633552 421273399 767531017 777876591 519350752 790438941 55045151 747973506 671062058 588837433 392056464 884505195 944564448 377807171 900931006 40977313 258419509 533945107 381713231 881256193 952563427 279918119 403241647 119104584 403382950 607985697 475717515 903974301 490670783 358389831 336456792 108349956 555214706 484899330 759316682 981592044 691221385 401479520 740640861 705626018 341451470 369157010 724285648 96396763 784246932 258223470 55877796 17673775 775786031 56322541 476743073 613531032 379459959 1046417070 624989010 138079479 97534794 140967026 871651716 898808719 674135559 991951262 237837003 838734216 347933715 3390653 425503485 821727853 292283992 931530491 855563701 778108847 1062318785 91442859 819496146 815934240 787630783 152238529 154828533 856390008 477778375 980756568 591189510 939619540 335502290 820383534 251915695 54882098 1036166108 288023075 637354464 1009825014 309252709 599871166 320877897 938987368 928535539 321095336 53407715 736679731 45989773 302275119 1022610792 128702183 671567170 697361092 562420694 931282297 201841824 800046461 344156656 243851454 20679486 625104276 206972349 418746355 738876210 1013169894 175295239 374879800 251849115 111747188 999678429 467340561 1059140889 190951142 462098 511860452 586832 97892099 467167419 627792253 139033705 193542203 254081205 604958860 765081489 444108573 374449949 1014943782 958311288 257634273 307221205 698834752 597888978 65138911 416804358 294539832 970880217 351823126 749546649 1066650956 682686922 285361830 501105341 112334624 828674916 237007190 302068580 196926268 99574380 678096143 880357061 933395595 221125163 674531423 246448348 296417246 254473966 273351415 140349413 28857959 156714117 339036205 264268517 981905470 718304453 913586555 702605345 199999200 949765639 247630078 718492581 488144811 434928038 945169400 368422335 248899171 207231620 673033550 640678273 97001392 2806662 721553419 1043471170 481190814 479024659 203878875 12109597 1050662939 735662234 589835665 281673584 692978556 802256137 173948321 972268383 390483705 501387094 1025027751 9506127 304978220 56896506 501510622 436552043 755325079 299191921 616875946 217918499 644206107 320944059 897169935 967930024 851724161 98319582 498870071 170018673 783217140 562376034 998202352 173829305 957136005 46451155 187711019 682925822 895535782 1068321347 502597502 504049027 906426032 603681990 938479523 1040783055 242541661 357909492 377235191 794998572 226141006 529243498 510492924 202639145 528671111 685348936 844410583 698771993 416361966 237196213 817441235 157944978 667142863 657939799 442428892 817615598 789745755 856565723 545432581 692049869 135257892 738890099 454778115 690387601 753377955 70875731 656071599 594116065 182444978 160459571 749399944 767527 1016654611 842025937 225566511 1012615186 743207911 279193964 986571497 858748692 504262199 807406921 874032928 220857317 571298159 415458098 753176290 418781950 785481437 1003843570 457150048 193614623 595309623 134862810 770717040 677723082 839454226 633124159 716657164 298908613 831494764 456441594 881873617 18907036 411007779 417496806 972042625 653342749 518133883 765433958 184937858 862709978 144466844 586325724 402298461 109119146 397125906 21527603 389113407 137143849 644379468 1010460502 327642235 682949171 700742941 113928887 580077574 149414509 462107710 262535881 48689657 174033340 212093897 627219590 575412243 130028748 525262528 46242794 201918260 888627338 694461060 49107574 1058809315 662458538 1050323294 1035632046 746553034 110112290 582890746 199697818 493148981 595498413 603429094 861705033 24767894 970880585 487140632 996988746 623184899 399351738 529420390 689233969 264829622 775315717 104725259 591012121 167691916 151795445 791077160 1055836188 199012232 797772441 502539585 866944220 322020173 746586052 103389884 932732669 566675367 1047974796 1030068326 62889128 597562626 806144716 362830573 6076682 1026949361 405254306 527103847 420539091 29735081 37184753 338812362 958970552 293432196 1047853792 679177073 802925041 533177726 438560601 103255454 1015670972 562739643 1070743435 783315954 50142424 593837311 1066862441 90821366 665532427 133173301 1062506536 29505174 334651036 771685097 318138053 159474849 576347609 1054758349 1018221181 856248138 852898451 613729591 356803411 798332842 654483357 673448865 473600141 494772284 107402321 935836713 807888695 40939359 179446538 355726607 786909343 767074775 335529899 735545914 1038235863 41561421 85212695 253540274 977976631 703771338 127772855 547763239 291162840 767205696 947209975 512777065 10044698 973334530 1004403657 431155438 1041566751 131791175 969073696 333333071 145234765 795139242 33258870 102650315 540391376 572707245 411589703 251097283 636202773 221119025 701756052 145285692 612443472 595281151 653452897 124542304 7861240 270037059 165902391 1068738558 274438214 275561484 30308771 342704389 486650297 914044109 122049461 222206732 164204693 320880095 411540865 885712590 618484831 139502589 498713250 518745510 527440482 56442822 892058034 385186839 771734574 523216959 664357587 905501767 278076948 780989774 73852457 553508991 50105771 777130560 635570782 793279916 353873998 532127812 495237917 949253601 722043291 177203438 137398167 190452435 629268981 663118004 175284481 185200732 838481155 845199732 885063956 911136505 49680431 608175341 264052875 357443148 809728296 366896961 275824040 266784666 1060713569 164583802 881865392 737304653 318350224 515963905 112909419 864230516 78623792 700152104 179867813 52865342 600923647 945846178 297575600 2344835 509456768 992779526 916653023 918232635 287241849 397779024 36886028 543757572 1072159350 585919583 928790035 304201376 903262021 56218232 125433940 311677813 227719545 996297921 781156661 409549836 562925287 461656263 931998622 814001043 608372012 479670777 680181628 205736539 544747557 571315242 386594878 935063642 561836149 607383059 607722331 939519914 57315842 40836047 556637898 291139336 728070776 1031831902 455663496 898618453 668592069 432094498 265578518 438288153 952123035 694544997 159696632 914526971 1071245553 1052505041 595162424 711758410 418530434 107738613 907693280 202016888 438247757 163033543 725192579 507675802 1006620692 414945053 978681013 787915753 704528605 481144627 215152783 490859587 982397299 303927080 172147244 129513131 258763750 724941441 211827246 581544389 501257479 435785125 1016019258 912213083 519899885 42469471 362739319 89913306 668783475 358166622 310869523 446452437 702880440 293503928 23771071 1071135618 453427613 786725731 1506606 465582648 100269130 814751163 541147290 943707127 42107049 518201600 868926270 817591520 363775210 701930964 16636893 139651769 974474749 859754945 516902202 673083242 270011931 17428913 958246045 91308930 908284734 394202228 1022482517 806967475 149636516 998374717 750616112 144444498 196146769 483225125 480096773 511504856 947715465 674753191 379130923 913616228 945989978 32571939 652216319 951672374 62929936 667187804 269318753 121215285 712850110 995365369 660944952 1004532586 72043452 878662407 420926698 248323203 149234979 989721973 343515364 614467921 273746771 702665111 542224408 78589514 991879022 949445284 386560122 927681032 44514779 230938936 184209538 201310152 827206852 963132883 312702381 131170796 46258840 387851095 1022231292 998247546 741928073 408578446 762376052 29618074 213212431 917082018 547974300 630221339 88271459 234165923 406838530 810685423 959845637 515798021 793205430 540055723 913321526 945886239 377277901 105677320 93943423 190114989 948277984 218206821 577096745 593993550 104051082 639938370 466807234 168111111 717267694 558160838 476591262 275821503 672245806 703251258 444013396 34130625 452276469 769217420 811303997 1048894269 660820462 726558670 482036728 1010243527 213830475 658539188 717575145 843873750 571776831 195074329 41099445 722069574 979024004 765127802 550013127 1041248727 816980182 1003681145 940831439 848881579 480593781 346578523 942351422 163056588 778622887 74714507 1051795403 815556516 857382708 734609429 793809905 449670787 17040616 230011948 872405358 74264605 198676245 100623269 624787909 477649673 552761871 661114489 441775549 386125635 194600622 32101703 563553249 662749355 557738191 284894160 547602174 586738052 901455315 298462073 480349352 173034741 932492062 25177548 713180084 1015318924 876246169 58742519 121731775 284048310 71514929 799500363 405022374 427814984 531821398 143454910 318384396 218375929 439694205 432087402 241037016 425878757 123822750 1041208333 972136116 500848396 116911799 230574471 1050924943 222659792 958567239 885693022 116129563 945328763 448180179 825148221 789258320 1071715255 158510693 958234480 491608552 789081621 809466376 155431786 38264032 1032768390 460227917 453519168 18512637 974200037 889053385 46977324 1068385605 474328171 684941717 908865546 519551618 1060913208 822007757 976991710 456361410 60738769 167499025 969523788 338283738 435271581 250479367 60796190 1030459102 886221159 1038453206 817979586 915706538 591032544 605619885 850003146 193684829 314209561 841781818 160610410 482207961 968800269 946624308 581688573 795275844 701327637 185481426 509603968 633960586 164005746 242452817 1049884693 527618776 941921479 728125553 1021835906 24839970 356243355 727425528 150178480 650356894 897134044 1018266670 780919340 943212103 1000697687 519136864 603720617 755919196 455270465 923543390 4988284 855974878 36484017 195046397 427590687 1051111189 739876387 691209621 180968623 59120140 463108087 779495555 585555821 344033296 1022849008 8565416 977558080 738230069 810962358 656294376 826948402 473155281 1005831252 284646061 379366127 660035071 644404410 1072062050 894973769 1072747037 954712124 489525752 190025143 823139662 695929618 901395556 660653521 781087993 759860950 509715742 797555669 223289416 852892937 2497188 257194789 595603114 70693262 208726261 234830023 282642002 291583276 425121815 214162916 786072246 576933905 634817169 756294217 689038096 832916554 102331377 517912297 1028868320 774441036 934305608 382337113 603883112 634059118 500762025 746021203 540900655 394313325 632960174 549492020 943934591 765116903 312706291 201071230 361631719 537062624 844144792 876129622 220540345 1048373567 958732739 192893446 265926029 585593938 107991324 370339708 42487484 192561478 279571535 951089610 1045772006 487025584 968154254 785329316 955306093 221968903 186545421 685790693 349454583 886763560 442241412 311308299 428023792 168292817 353324208 16731318 332117253 41645350 893503186 152112941 503662251 499713327 497613870 1033746137 273741974 396334167 501394317 364378567 416922178 34037486 515361980 988557098 1008125294 128048552 911939339 1065519575 1023814811 367740957 615028687 1018946248 762509713 796501831 929552608 420647834 640637915 641562631 377984795 914153743 660170566 1036017056 946112737 145257868 546890342 895870010 1040331927 322890652 559850769 984437600 927913764 270755947 824641250 57512067 258202230 1035159115 263708088 270078325 549641214 352669491 492801076 368893678 832095023 673843003 725131326 293414667 402450434 678266657 862323072 6021066 103729525 345269960 961949673 66189711 1054430215 253605812 301961772 728998306 827406398 478285711 337957951 640619694 1037357346 158704294 814765533 499908932 567057087 958688876 844671236 948795990 202127527 460714999 656187511 59701692 420383853 189465214 793144893 84275891 926637099 348066273 910774816 914551897 857901309 593964321 316856367 657480754 733959556 412216547 257599292 101816486 783662180 159941106 432168799 340130688 1016354502 634277818 473237618 1061395569 890491606 90183374 1025020050 589187979 727120454 519384930 123558564 885068742 573196490 641651666 985390286 338840959 809734810 304577305 66572026 114475252 210025203 185877339 488597847 429611209 37190294 19197020 365474519 727770246 223327815 712106502 56057777 521202454 514680144 692967142 422920161 905153866 140019707 445050543 689487267 300644436 298036764 195295415 188869628 531916877 873139589 421870197 783852849 690207407 1043703951 885410313 294762830 258642139 561218711 331118772 556444833 760382100 627077247 83250524 40568380 562028674 71293737 794627849 33828470 11536049 792738304 940859243 749821290 805060367 985333615 280520017 259561846 655700978 846307687 765462323 535381438 445117071 366063582 605926825 207437991 234519940 1009875786 817612274 876057180 241954639 554781482 629070958 136719181 343321812 408626302 2516772 308327083 244295643 715464778 678111293 652764397 323269008 426562070 373346439 1002996301 998071553 190496369 538159604 693620044 616296867 545382761 822858264 309631274 459042254 782091541 659096750 885614703 752130364 626436108 438826515 554244965 569714575 444314603 142327241 456208027 556264136 1044923347 785699061 583666020 951096784 933247720 96210146 589585494 284004082 676522707 670323068 194777035 110580319 425200193 549071830 265732707 754902185 252885858 570790053 268720000 944854345 93299307 583476930 689771977 265572634 348458004 623518124 757487016 136791259 1020503066 617851907 57425868 92606384 440810430 757228046 818322343 100779425 38838341 393174070 131608049 332071450 118620534 827214217 21669667 527026793 601057311 181082681 1008017917 33456196 289815696 749615642 632730113 663151680 29842718 918051623 175669749 555198555 94225570 635686909 229540453 522326643 389660920 44430942 167127071 330247884 259406208 925774256 427244213 1017352847 30868896 228947323 102970110 368946757 13357887 376365039 569715094 873771104 166436172 912745563 120837465 98269106 440054325 488998327 11344364 1058870772 711248497 591077660 435922484 717283905 318746358 276023366 398664412 621124504 416116675 168995865 401633492 1036393309 553101912 689477401 435943373 45488088 223567929 947812336 791020734 832894645 10411375 460717036 314292322 314060675 180498182 464337279 709952951 984890933 1024534928 529263293 772227201 892577188 646414241 141637601 952515525 384664074 940304465 955912648 8583246 938584969 279893437 54172788 913990443 367618210 837467014 1057106315 259204143 509194430 467985744 135873238 872479856 551583401 296443205 612615362 415053001 695513874 91644560 314444002 1049533528 44664588 753496034 8299 451188480 535498384 1028641264 645537462 670612456 801098488 266423794 328692674 487457786 369511814 771577893 373085872 246614117 238643675 91216459 352960581 922669340 900561024 78383654 211252587 634565460 1037052257 521228289 901259696 421183498 107603533 958905639 330924486 1024180859 534529399 1021481577 715333121 342216362 895716344 366859932 494212316 145940445 525713483 362806553 879457652 579176224 493046991 1071225916 188328460 700197313 953561673 1051046885 659583623 767414226 248629855 1053328378 907538161 901546667 43293214 871461603 858995191 418593637 397882484 83297292 918557546 1055416672 879439031 538828391 731159231 128637118 196876573 928080615 763566482 471081189 802235713 610849542 261447199 638059265 204027045 895715136 173090248 817156223 132060458 548287894 301275026 818983315 266781082 559630348 347786919 886932404 156120094 996852523 555054293 1030244379 729663688 671366272 871427342 1027908167 41332747 700113179 787811814 30631548 420868413 147491857 918809624 54343743 189857052 928705786 959886594 481736923 7852103 498843251 463673636 750568928 225781184 245861533 286869157 492226463 1057798512 595790749 413201357 341217199 203168419 10354202 595458444 194529130 802950792 24030146 594312690 289468017 740197043 215574469 14954165 805267748 865046427 292136792 961973167 1062084395 1005914907 697739316 627982685 464562672 946809589 671131413 659559264 116658978 1001895754 196257339 14374656 812688180 40029476 476136428 300514724 625459164 622768364 782901487 1049407323 681859732