1947
740493331 948416682 434429002 348479254 92471859 605014686 371477453 667980039 721033305 172920088 574328128 345164714 818635772 972389781 244437981 325873741 27017039 238481956 888954302 522086358 507669997 894121441 657997304 528968170 623111561 858103088 915844113 931761461 482767673 764435589 124155514 215804444 206771236 500612988 359414446 176611448 767486921 264604304 458393707 450330997 564068514 586093659 406479836 305506745 929543133 545529158 948147551 329371570 91634098 409567435 382745126 380549215 586248495 851523687 895984243 153054523 592436399 912060198 578665262 851606391 407003614 383271472 652597065 415438047 615806322 526446531 589281386 423690984 730649102 526937729 928778287 387182605 630392144 241587324 96238982 718720421 336229609 636771036 258179930 300464525 499229355 582385220 296169409 34164722 251985242 959482528 248353138 83662892 709935820 834764880 592502709 279634650 587527942 68206611 862311817 689227733 315398157 824592984 376484495 102532850 677860933 311717632 491971974 892201985 266981837 517143980 35028313 229822097 278727840 663604901 864190835 586138054 232843758 158014700 648775753 27677240 803669854 790777547 262545033 677878200 923710232 56795977 771703471 828084251 99596600 536823342 566215637 975480026 423718931 350773944 894837258 404212855 139087267 754182399 277995540 379507560 429239242 464800658 413801493 155498030 380741989 223309632 788359473 598023603 632862650 537880126 991635799 585355354 20145344 306546827 539202457 451276582 649531332 756349679 836366992 649913512 102932690 876784911 623604825 641519030 46195971 629418129 486448151 11400022 950961884 146941739 149910655 579437612 672689754 696152953 512333504 228936030 685271439 354857057 571388780 554342958 541194990 99480389 292765048 704754460 366174497 875550833 8644892 848845543 79249055 7221137 611536771 972994834 954799351 796290662 101149291 394327855 710566534 451275860 269432884 247029869 346983779 140604288 799578930 242431932 922909725 55477131 89277229 106822529 933382490 235274942 62187774 38736470 320481334 70250319 854574477 787898916 911226618 768446819 337083688 660698348 659665784 45989867 405860056 232957535 888396859 803408371 89599663 547065243 282044404 984850552 339868862 116994698 877066281 133545732 214069661 750815824 176865555 575674258 872423387 657034402 585540955 356927632 894485215 181442356 338847460 47074586 150256653 564975566 852282755 337556657 707803767 75645430 451284680 818686873 498941881 561336439 802770579 108447978 509596481 363923835 841128734 67247292 579885403 510404647 236048989 125105128 385965989 625445655 475720497 309275379 778564218 664341844 934142840 320853160 727234688 118971866 610526600 703559380 245649945 248326234 176101852 689828131 337567321 736853030 925362649 638117143 152853583 287428511 575827094 788456978 91290089 241622275 896549474 423373846 376746764 452660982 183800050 689539182 766960202 286419189 377584066 619069858 595852259 807569499 144189379 714690283 787769523 666333468 70891840 304107263 503024583 329235905 716522248 65505312 589203934 107469162 758975871 205695710 612901949 978030268 726683232 916963880 736707508 473807622 280699558 150712999 976911904 487207059 231532780 960923800 211283889 256663942 968012166 562525870 795904983 408196841 359050190 216510481 60330338 80330578 293206735 795781604 695080522 934027906 856016850 469542042 294001714 149719107 866931185 362587179 518965276 65486245 413504033 915552142 4629968 606344849 105926677 57992186 475873429 123148601 938784680 807981553 463566754 123926223 417796032 588139587 904661601 932025340 490975379 473695455 872321882 738203114 768256523 931191689 516748475 911969806 593776541 700270321 727036093 375989803 440543412 761173837 584283078 970369424 294675526 152868147 884070359 700305965 447869008 958382490 895589615 547038666 7432410 986362645 60096895 865891652 543095028 94770987 306718485 665698699 652973658 439538254 896306620 248580956 227855203 287357672 461609847 287165321 486652065 899729840 189184222 196789488 61237839 501028885 968734828 918893285 178670742 851242539 213448838 695664211 107769628 431232721 645419599 800579307 819553176 629041600 358514524 207370279 698463018 861582828 714165081 593929371 398995932 213154303 192819474 163415135 336928099 661737851 165812733 957951753 920561845 333714722 312556217 624534872 316982964 47263727 297869200 532698964 722607073 112011464 389590617 791019885 434541382 563282917 749576275 896570117 403940179 261999825 253678153 162537412 50527414 240943218 962691140 429392163 620971458 899074929 349711136 871988224 398127077 55265581 769167397 716200179 6111827 586829963 346041605 645916459 213927826 423502788 467122874 834929408 177662448 253952105 24661855 13584758 403505625 203786015 610764371 887205213 525907082 830149197 79465555 792157919 978507336 354793729 603651269 494889790 729590164 364554460 599433078 998314950 405145203 105106688 184467735 229287026 572346460 415356553 454698409 350787157 728570292 762052465 464282811 896774778 19973039 713261619 69684055 654806381 827682064 502199895 301795309 96189068 413013641 4909152 297717342 279500474 207865664 499708770 197758943 471934808 526101447 795345202 876830544 91433349 549716142 351093055 825789107 330989873 93390631 592444307 153053474 814704834 715339262 691538940 443238239 631573699 430361734 443956316 835399162 293162182 518873822 598993366 614618244 124543497 980968419 801619841 944327338 977568107 597568230 962099184 577956906 709023228 565706696 318894098 387771931 95206289 877268724 85009851 145166658 504888708 94790407 725833804 699897517 854064081 871685670 212550752 159148833 529853346 126966683 699108239 376706109 748241234 497341680 18356892 815986417 700705123 171444965 265163344 321120430 327990279 795842254 264433378 162485169 250029531 546462564 341250662 971246225 836720694 146574154 168751477 869815094 335795266 662904754 311072754 349275427 567284329 350236915 753404062 279755174 879031312 345674818 323262368 263789557 123059218 172208190 168523565 77685548 502740587 352748076 493188254 478899242 456004207 263590011 109347682 846391237 249686525 655916533 851314860 32090553 771848538 240189953 230957160 58086700 332372525 82327225 733491612 424587893 103100862 787192771 54131442 65924169 640416951 787812107 846137318 643210656 686815108 639063959 185794519 880314577 272859435 596499859 796177793 747428531 629293674 509949240 380230275 291370555 178008910 706331158 773425384 463646165 782109995 401264416 848851377 855795233 372061071 362973862 906659004 568923133 926889494 996928488 709574696 157125253 774207585 334373716 955577170 536786637 831412281 228856802 307695244 615680137 437336107 628817624 64692978 106428125 172028286 499983811 696778276 693581454 324841643 344018451 62223195 557744985 436187241 756710155 510559107 818184556 114918226 722674968 434364098 429338250 521169366 954399716 910575973 957611261 319899639 219206689 579892255 525374685 761283034 762988678 814449852 304686211 996542464 144306946 82037394 954704861 71446267 611750577 544742840 729406855 962892573 881116322 145155835 979505262 982066401 56575934 63886787 307676684 840703619 736987159 647871393 835156361 896435735 940291444 803201601 912679608 995768327 869307569 664455452 17825668 152771513 467239989 494958467 225643470 222045709 221515403 633730101 41106550 934302660 650340070 156398521 966315907 232068635 711913134 172992849 750011305 385117793 796952923 384321971 788829683 5901691 137620526 573975179 299489228 944223287 589759337 56989906 66364515 703453575 528947223 477541023 276643250 889786834 821031970 543780891 317151080 760195709 418881375 358170397 357410043 585342281 711336081 309436010 445035123 11621042 107390245 708083671 571942679 573419390 38464909 704435029 85871256 947964373 173475118 444012350 880084960 492568566 347101690 841025966 411495997 281386857 996307887 223991389 820326369 560882344 5476344 685034705 787047468 671863342 660698811 489833377 954398093 119157332 91575290 990458100 132742823 86017229 156046706 953048484 932071456 87290226 85210710 869317223 507149295 691500212 665572457 889877533 610199612 985975356 27394122 28249369 694481595 70567486 371161135 276398914 877680561 849562680 845503005 572680423 534471254 250748307 638166199 699294470 955310763 298471334 561864828 583380801 337505727 33513691 970068663 345893818 518395392 962667760 72813281 546962512 405141516 341280017 376397027 678053577 641112832 533436789 625687851 998249366 420170906 891265702 947584590 602955074 742272379 10336911 223197109 181769091 720211687 99321179 130858390 482228281 534675399 429080929 333276505 222707543 321904753 3173837 375976023 915505763 87705286 400783924 225430845 332333261 898668151 366690936 97213321 339088060 633207842 361159281 852742100 5202514 159397799 740810849 279065242 817280958 432630044 4678488 835024606 915450779 508551875 848097237 48815563 871356857 515840354 477231464 257650079 820965231 515617502 83450787 906558667 155088940 763432044 302510068 214009528 776865447 466110255 459954821 509542590 188229392 630855044 252625236 536291192 825161548 188596345 639964239 169437358 34822283 161548835 902959791 689734721 148295848 73891761 849497956 587494567 711394673 739820470 355612248 269273052 978709449 839678318 636214337 612797 916185458 20150379 350803808 868699962 188997491 272111188 371566198 590320859 497597602 824941186 234807600 549178973 591321899 348350371 744531844 269513535 266725704 112425469 28921300 544478400 267727741 827378970 565068642 819757378 70060652 729852369 259013022 210708695 909090710 392436706 687663158 66416926 311120134 952286496 950735579 268110924 426078945 630357157 839630141 362735237 536831871 614379747 21570720 463005242 360051228 882099167 538745220 439939856 395626024 218409953 964138726 322013762 643405608 783761482 571186017 190669090 987932629 936400631 763892160 372943506 461101869 781365891 317221188 388583218 12300866 41615667 890635128 353054706 635316518 358585133 851560536 229956254 368484746 267917262 333140455 40991376 955567687 785211666 871327390 7593335 900877915 86102456 808862879 560217840 143446758 332665562 725275670 68257275 828051228 196966566 927445191 656566115 442328388 363792242 819816134 988291448 703123728 570401287 997498256 523943334 849017771 866601435 554140901 611076515 328751226 435411844 326114020 978917362 36851951 462260618 271414043 266465553 178456291 41372285 490203898 620438852 896062991 468645267 491442112 35997998 939702601 371113097 741480561 39760798 730754246 73995914 261163053 72367283 498843150 908540583 621836398 709544954 332445965 772648603 819777382 21833860 230390797 599203088 459421910 803565900 36956272 907400132 86055723 589619967 797944447 357359152 466195976 529087339 91934094 260830907 297217503 748605876 620825961 14900783 956009708 679724185 889107477 535879558 636336952 93849374 48730849 697064241 319468938 176568301 514026938 677677659 530643539 57047727 613090487 710957848 610147861 891548263 676809768 489445446 565611758 716133213 185630727 32333725 393445641 746153834 323488858 61724707 479453659 642166698 557824281 610160822 404850937 869007692 198754298 473545439 391384284 840162677 353504947 385277158 595725366 982872481 951373479 626085427 282028669 929362010 901620581 71923973 809654611 774034579 579061529 143615550 222407889 62175208 716740622 33830519 142180062 864620838 414395969 33700138 64179814 735420271 750691520 760968354 841860007 339440839 77239083 518271893 28721806 313897318 660775795 291413010 387573077 171824334 637196179 577643338 541952782 766118754 9208236 370883373 241058062 24617229 792400717 22846817 40664033 858228885 568551820 95729351 821705159 19647747 620225525 590223183 862848637 456669289 699372400 586042820 865166351 745670346 768731230 276845517 42596288 445779818 139553538 623507439 768119598 313154091 796367244 398044496 145478124 148421694 200716083 183936122 842063552 339238420 127403964 719764471 861897420 413079996 443020938 518210583 28458790 559311693 247643175 396921299 232018771 736901844 789928551 898551706 740499561 902312743 698977669 724761300 939287812 26403906 703688016 504836011 988738887 502785066 972906546 809465876 594629808 498266568 681335755 782781833 753839963 363532474 110741313 964312580 70768232 647041220 606227597 822393026 906495900 238366221 636036974 49814669 112834159 789041528 122196588 487835523 430418378 688154659 619843588 87002693 268869639 857742391 905548152 975718487 158895380 815856294 104647852 766419986 816069017 527650008 838462234 357078233 567928428 542489541 399108499 487281554 445907825 975576545 25918237 149921190 414961983 328095284 626524431 740680407 711336833 19584942 495022772 993935373 834890945 96477763 552099087 41824205 111950640 699965101 226396958 25569235 524053306 337990531 967850992 524036118 302350781 690923383 533382961 599185861 231566658 498997768 358025787 181721838 661451097 358261645 557572741 832927185 482640006 821971789 22184507 938325921 833358177 818001631 880314689 868732961 466712860 118624398 304557526 49865446 395830752 687969570 552970605 687621555 925297560 693624547 658956902 770021043 413845178 345821606 505831688 787640355 814521514 514077116 213499731 591457704 339303086 803487445 496124963 652612513 38691550 596526236 792693223 413274105 296686545 70167496 787120450 607553939 556218495 162006004 644753550 371528813 953329729 139557381 587934183 47330293 949403000 141907928 875415121 824953970 803859071 92452950 180010574 897885781 723096288 572179282 770469920 209734843 839424551 388992703 919745241 984606224 598631202 486086282 148959515 241350145 828346786 868245077 734476497 390867843 317917961 953160777 53964429 830235773 681049839 489818484 143279877 488203375 402678141 141040248 188022733 94178157 627713445 695543963 757850873 878558467 880412056 608261136 796167244 609505687 818122295 853020553 109090065 556995002 127418102 481176082 606623631 116279089 360744128 668585090 977081739 564308999 167702951 597284080 743763473 40762687 927084162 521343854 694205518 253343214 984730777 413900068 629283389 673895090 530632612 158977543 150772776 715563358 284712267 868463162 787325532 74766299 365475210 204316357 526821732 173264068 660403398 932327647 47254157 498027964 844816583 270104846 861547320 202840267 846601922 991801635 868380130 260067366 570622840 163776259 229096424 813781780 982392995 356178936 28354791 932509809 338248074 120466057 362662690 717830356 430435523 508547050 179550914 137936959 521547701 979139104 442242767 722718445 797096119 879288047 535610455 4478430 9110874 667744816 116797159 351204101 841699315 496758455 173793315 511406301 272926767 319181547 693767568 520411124 353173370 983172883 805360767 467636774 267798518 72231672 615406262 27040939 197149828 821326134 692698814 998772965 537773298 298242180 949001363 498621731 231007431 337358237 662678827 302477301 543303012 703545588 804770614 965416228 858062911 795806134 617469289 197689034 183236353 428109675 937237808 499037753 662552589 578318123 306538945 981613159 503591993 137220343 854257559 446529600 638730586 66957517 179866929 198399098 921953903 606676073 287015845 702965818 439036282 80386292 556428880 208726510 70186497 961357312 999963077 891922033 455081400 65601978 996751588 472965801 593827750 81804306 574324863 501515423 944036062 698040388 836119762 89885588 986111961 713527809 455450845 3093450 470104346 58359387 209797837 733375254 506238009 643535205 84994875 102782825 258774350 815111023 460313564 282735049 190898803 986542132 584790605 422151184 891861848 275439819 756646431 787232884 118126438 37276363 224889104 459087193 258969563 476236120 503411406 224292280 782407447 759961553 846993715 443847660 752054681 386837843 74352915 245008015 494352650 940127509 722468662 159603336 216571533 463667688 739128261 603281864 522635581 460568601 26103548 63759047 777459832 11807101 773147862 20912821 352530466 454650773 173260372 885366132 62416929 423679319 924722633 494869085 154772961 797825603 418147646 189977935 4677163 631823989 971999534 271999343 473346913 170690299 534271773 725211250 216364096 776256613 273549999 628919712 468318254 132315065 203376066 528885308 441931279 233086757 380116458 772835838 388654663 933665017 937690517 757551057 584213326 862355475 751642087 833667304 492604376 552063171 225695497 621500161 507657542 775243498 582548358 304914044 647838030 974397179 35242792 562617342 701013522 125435892 657787898 23041260 968748835 66470086 720235125 139078265 868405246 305689845 163475712 142042312 408521134 556571662 482146927 229114121 169537373 367379877 733810581 220946391 266531323 452021092 536506272 368910298 307963687 354027264 864636068 274532028 120609101 929342947 722983265 820973118 287900667 558101735 428000763 444535265 54640215 716140265 306730315 864804421 83921364 713704554 370973764 451426358 791253787 995339876 955262071 78258532 579565812 60174932 537390335 667863861 412172722 580984656 709816847 964871752 722925973 850756487 106741123 987191260 648952977 460728989 438478460 3006546 462089749 926783365 715867893 53570601 491791472 739758055 318420631 148762878 286050529 639488702 139547172 53228932 592380274 354035605 982931948 798220495 675936106 20630330 287185609 948655937 364874355 37158902 667418551 919835596 997329102 526680552 647221169 396100121 91911269 436228561 180987030 654963669 879490847 525240843 460935146 780855464 175910531 335301766 81294451 185835681 127606669 957430224 650200416 85857298 252885076 637925837 195810664 922315297 26673839 465606522 593139968 514620401 335440110 570198946 157299451 374416247 519991581 180360736 106371247 152159003 826618220 497058148 579277008 687595952 797170917 361316768 140280656 389844807 413814138 903783300 985236588 595635876 932199455 369402227 380466306 118217309 467034605 279913786 498551341 478853919 627797860 841542157 87235542 799263304 408930493 507904788 34615050 998402845 754222328 225979460 69416483 102201621 605908196 230939798 170242330 836842841 341077927 659361989 698758146 714611474 861797620 371965719 948686857 542719127 544261271 540960668 413676480 67736968 448487889 646484839 514333827 769448518 928967601 161307159 716209602 580031940 165018440 78246488 221387605 742025653 974062809 737823086 492890338 915116742 872780707 905694271 531305116 146151310 202707629 242182455 859775500 915557003 950485099 15387748 622598292 83869417 767371814 239809175 785624206 850583292 701297246 219817088 162250069 782856733 385325592 698930911 68838141 175807110 236055197 706336190 352380582 410235472 836582450 708902071 726181407 308100837 150975400 764053686 144280706 997318775 415834087 293058135 14446634 210401983 414624260 30057795 58940446 285223954 573213095 524536158 247263987 775706797 629356737 897641475 699951165 543742279 188792485 920261449 139418684 697557097 394802711 298823450 956243245 600288561 735906485 236336551 371665754 404498119 110386424 875216119 590258563 896672311 549870927 85270086 171566023 556389637 105315524 377463086 881704302 420154700 261934197 835224739 180455209 299360958 800481883 882578376 153547348 23060914 88774480 559853225 788021499 44124184 643459526 117191460 693735343 980615269 596713034 620417624 858052002 902362384