950000000 950 856379212 174179766 804572093 804572093 562087752 331435362 893644049 439099699 1690052 119003957 620626189 404459870 45356491 904643510 685048553 685048553 654383643 295616358 272771072 272771072 586479407 435457872 74204804 167397234 327120199 327120199 198304854 24825170 329058541 329058541 119311321 119311321 244778792 244778792 134276602 880019654 495544060 901478366 126213148 126213148 715718389 234281612 38294248 864167634 444341036 12768109 278564404 309701895 232781919 717218082 90092791 118127530 371650539 578349462 202228768 202228768 226570561 723429440 193472427 718186549 231106475 718893526 713428084 236571917 469649165 206306433 124135654 825864347 91229896 858770105 328403337 558554856 611536591 121232530 777330810 777330810 33322328 641599900 67200218 44934193 514912264 635510696 104350352 353787777 523651115 523651115 45705125 66877302 575934769 374065232 666961478 666961478 511585956 438414045 420321970 353897290 689308049 86565594 89286917 89286917 187697112 69608691 192651072 757348929 31951313 918048688 944184219 189428892 456196816 715594522 114475573 403946071 109058597 109058597 73139560 893378192 103722046 65034897 227722906 348015824 32950088 917049913 184540002 655124161 936630496 887980555 936802562 936802562 224408824 725591177 376658832 376658832 137517880 838397067 769712169 764147113 589431972 360568029 917787434 917787434 142287003 772813798 674419882 674419882 91868021 91868021 556411149 84681190 825533756 124466245 85501677 80052352 532614946 562922670 14217674 7773082 751879329 210474792 484231897 484231897 135145591 8823859 420889116 846818896 146685240 146685240 908286333 591747085 553942328 615755947 189178466 581883263 147729157 47863659 475734897 474265104 167950062 167950062 861241703 88758298 177555567 772444434 256181534 204981071 945831985 61275677 461393901 702103348 438911356 572634373 566708627 172536135 114673671 835326330 238149867 97969551 872019549 676345499 343669390 606330611 701822025 355065028 556484199 711266576 637513332 150613291 36698064 913301937 909743979 926161268 466611907 466611907 32240088 917759913 639351327 385352348 288094181 159763022 191759816 19002666 897945393 945006118 181531570 94322015 867967063 867967063 226823766 723176235 3672219 550695663 510330435 510330435 1675305 75424315 509526925 440473076 389682234 63234245 113871066 836128935 18417002 308913887 264678973 136128818 48246233 445153488 512000966 437999035 333197555 616802446 57432513 236564685 826419403 368208324 345552020 48949865 515648270 551559092 785729560 785729560 340463727 340463727 331977919 887094999 146023004 763871121 141136231 209460508 58076084 58076084 43694051 36927174 258985827 258985827 664872286 181817813 127954500 227324630 106901227 843098774 430976161 817565765 18350263 18350263 13677194 785697574 517429460 432570541 51437802 13435778 243335305 243335305 307073382 163415482 153489025 796510976 650671501 102699556 461259803 461259803 857704342 200000877 260153201 442718943 32985479 138367745 906380068 906380068 800629636 814568369 217791693 732208308 85141083 155999632 540661112 65505240 539520490 141664142 914515438 889239674 76669589 42577798 442828082 442828082 653279735 548645768 671839345 278160656 868263822 81736179 105497366 844502635 322729317 166858598 349460867 807348363 624781516 412573534 617197862 285950930 597689464 597689464 924759786 350975065 625274854 787246930 135769496 69881123 230284489 150493122 96774333 853225668 595214258 186921037 556604538 556604538 414676050 790327286 688307465 806881700 190740817 759259184 212714071 737285930 440418523 594447717 418043262 272948888 904505114 61311179 706966391 706966391 120584636 120584636 174381355 63283449 342045258 606726058 576596684 535822766 597723343 427215115 826837393 339392003 157859695 755554274 780340511 169659490 466464777 466464777 92833795 731718912 654861746 654861746 195380296 248426960 54184223 895815778 651258419 104729691 190871730 687619862 659790396 659790396 933882320 699268550 145990888 750239695 96071036 31505862 106432645 106432645 672276885 672276885 30833404 577814829 101839878 186012243 133633835 179386842 753060873 196939128 882976961 882976961 574584240 656158400 152453477 580185841 141513457 141513457 311347908 385402514 543084374 420378566 513691223 504373433 926358935 196091686 635283427 394379547 334357510 81023661 112005244 853842318 146527115 803472886 199755603 225526888 63722107 874647332 692383994 469829731 804604310 145395691 130486201 692556146 456399588 207221903 354739316 595260685 350471469 669052730 892912423 732521880 727243613 624755936 730429193 340877805 878707764 447841616 150103786 948904955 890179118 476982462 372433262 341256023 802404261 88736221 693941459 693941459 12820734 12820734 543115578 417833359 616987368 616987368 266946435 726431339 570221982 556019999 241120747 708879254 205972869 121268326 751628751 671320968 760798363 821999878 264813859 850559331 296289622 296289622 187483974 69863365 554435899 193743396 84036005 865963996 744858421 56729156 415555093 910803451 57600063 227426922 217201408 732798593 554530824 660675413 193019181 456969348 378607277 186650689 854281293 95718708 668440836 818709967 878987592 878987592 14280436 935719565 290632082 90380400 112660090 837339911 897245529 52754472 703784835 355071349 544365242 305267090 160470412 160470412 715337437 234662564 880698115 393399699 349102399 86768413 535241908 818490702 776522157 929649049 660948604 50980797 198628604 198628604 917755879 199226386 177735764 177735764 305081394 305081394 634845441 23227827 16084740 483531632 196010659 173293461 703732281 58820123 651822214 109194899 451437708 451437708 851663653 98336348 595504930 253410464 796965735 31858678 745519431 745519431 310137527 639862474 140423244 103016378 281636782 574005561 511061520 311343211 96627278 108309432 678398771 18325227 360191761 510117894 345473532 463259329 771297605 163963632 442680707 507319294 750798751 468008604 910715385 193483787 487126101 487126101 682649260 11769741 235534854 167179466 71480508 71480508 842057264 368576505 520167021 429832980 109815323 662094033 292910287 374561732 437950446 523406911 660983412 865323794 676847732 584600637 853114025 394252731 410145353 410145353 282181822 667818179 177991153 594475095 13242631 450198356 80507897 866086297 131292081 625802925 224534567 725465434 443008195 506991806 189525792 760474209 852431301 852431301 440214659 907083251 784154096 165845905 823003487 100857993 285996769 419908106 648131460 934454272 845171609 104828392 231447336 303580467 414439723 271198484 304734051 645265950 769860876 608831775 472678687 418016104 589151477 122237106 845954147 699671002 947265959 247437799 14859045 935140956 717989409 104518156 934084715 934084715 940339501 186827813 138763097 203409626 302482653 865339324 500231575 19904640 449132640 353511478 374419593 287148898 308917866 861110347 597481243 132026835 736949582 184650993 931626603 43168559 340264869 110738205 807868552 807868552 559373383 390626618 791761215 744847626 65593453 65593453 99005666 458113318 176539953 773460048 3197281 922584816 309631060 91276675 791946127 791946127 212081226 212081226 482839345 467160656 710336280 710336280 655055638 842189077 73046860 829440424 134183047 815816954 791041071 741240540 137743980 795276097 317108170 632891831 693878133 549043232 381410267 129268252 1099963 948900038 586742545 128220209 546461015 403538986 14875532 14875532 7362363 507853737 867623904 333476630 796745869 262160328 781370752 318999266 338426161 141143693 165134906 209792278 333207562 616792439 277381979 672618022 683013394 266986607 28984885 28984885 621956383 621956383 169668563 799118849 563172891 563172891 63194402 838241580 454771389 269835477 663534014 663534014 104341245 104341245 33142678 33142678 196878009 21835488 411443563 538556438 12783513 825328811 476870695 473129306 218354266 661653004 463873516 693200893 307386246 307386246 455489006 541208316 930101569 19898432 403297960 45119479 25105025 924894976 822984334 630332686 681244756 885306226 607871512 151048534 873461387 503104416 85293649 6922069 640257094 495065772 203064655 203064655 211918150 180335915 626921707 251348385 588810937 20104123 420637411 816691434 84410444 930533244 924956514 142417156 903567123 599052739 838783206 492380557 650290619 292997114 315955378 161255678 14633137 935366864 874371940 75628061 217481055 217481055 9093836 9093836 560795042 190226685 307057574 307057574 797475116 797475116 834792987 862611756 215215047 371922581 611453621 880016660 731139961 839467835 208382546 572549324 655386546 294613455 495279317 207747329 319286528 839404701 32082625 510874443 171351224 778648777 758835930 758835930 210243012 210243012 687146601 653315429 621618700 384200972 133218313 816781688 291764102 921401037 938864133 844663253 271979628 271979628 112799797 57149183 85823081 867960411 487520697 137070695 893809177 56190824 601098960 601098960 135067658 78543229 239002229 239002229 795837593 183215502 939672129 939672129 88126395 88126395 445866317 562709781 115892800 834107201 460473326 421139112 431153479 540387976 895849194 278559238 144075679 199466308 371718806 123631835 242326005 858222335 44248406 632940045 480275293 230717301 879013562 70986439 83605770 853150361 555731085 895016745 292849307 292849307 844424467 915298651 201351986 758216732 943431007 309063187 366117076 562097291 907882193 907882193 132872550 873857317 455825057 455825057 166263503 11738329 534741905 534741905 264707312 576968614 386663602 386663602 863269576 86730425 210949291 105972539 490597326 459402675 451607852 451607852 493330936 493330936 284174093 608834825 495582349 243921470 100467273 487867270 582493587 83583594 323870531 662680994 248521082 248521082 399252163 399252163 881873273 881873273 806694561 64808113 495309549 454690452 3850619 854207918 926219325 492776978 783398502 166601499 26006303 25175574 46578732 903421269 453975663 496024338 784842809 165157192 239859541 239859541 317822166 161388710 460189591 489810410 542206737 295748562 534030538 628004487 420116173 310743201 186654082 61512541 271890117 823504050 150615829 489906494 404980549 545019452 292679131 447861603 946047350 946047350 213823046 799305844 81939301 453632530 761681158 761681158 684512971 939379094 393407469 393407469 56182074 111208554 388858337 388858337 614979865 335020136 675866911 274133090 550040756 399959245 426786581 862494714 376845262 81466387 881635188 68364813 561955311 213150114 13778700 662618870 107963748 842036253 632000581 806982169 322111235 322111235 49730499 28555483 777980706 172019295 99083653 656031397 154376449 909198991 14944247 935055754 124257803 164360270 48198842 168921316 655372011 207845455 638473645 433821793 318771647 811603816 602648274 602648274 690170141 690170141 408067999 185065502 322677538 627322463 167075532 782924469 775804359 775804359 793165951 156834050 866070917 622835176 877274156 22749468 628602942 321397059 750731823 237088627 70388521 879611480 726741295 603458293 418740061 243059512 764632523 764632523 421846688 421846688 306477185 539360425 36737445 699464816 443813956 443813956 708170175 241829826 789956528 67788124 743073973 743073973 7706361 395188462 167551523 782448478 514344442 627285894 817794098 635314090 709299657 191514892 912893169 912893169 18122080 455410210 834749155 440550322 453221902 453221902 214855643 275444858 221329559 191670733 325185825 325185825 556754640 556754640 578006699 578006699 931989279 685042423 282496796 282496796 644485989 938650282 489998117 16545389 183641652 578750979 17316786 794901767 217786438 382831994 186169545 763830456 373788390 103197845 133851921 904390724 223480445 787325496 888494599 888494599 733080091 916678077 480012618 553054314 484273309 944825365 437719422 554997154 180922770 769077231 666492981 34184741 471564417 478435584 731143632 731143632 122783771 560848576 857937480 857937480 323044301 626955700 498662913 451337088 441966329 636081840 110806564 839193437 854650458 910276368 738875991 738875991 457797475 457797475 203901658 724678902 146488079 75054632 156344781 156344781 235443337 714556664 42537169 652483234 68280238 910522284 194159375 448349350 640671065 300571037 404782103 404782103 179134987 20525143 487552665 616570322 349544209 349544209 488919465 719249304 222570065 154857120 93793228 856206773 802200822 42640958 642943181 188640556 49176478 900823523 277544278 277544278 919884295 30115706 43856927 927804438 383380542 383380542 842564414 107435587 577334980 745179148 682971351 836308554 723376445 70080880 206368941 206368941 841795955 108204046 270613055 270613055 525508297 525508297 179387400 213739832 669788216 669788216 331635290 894153109 202017486 728808823 229894391 229894391 1380941 663186432 240909708 240909708 87302151 862697850 922073753 27926248 413871325 191715587 779926896 507229181 395326409 221443354 634495372 209399414 522377204 121926678 202475217 103049343 463733484 210478831 302889130 628599573 132244804 132244804 400034944 553679218 718799927 231200074 821329686 237399887 384864387 167561751 5923209 246192375 601859418 348140583 244935420 705064581 39493368 189020517 483850858 466149143 652340002 896711179 87551688 460483794 902989834 607083482 669281744 876375993 13204071 936795930 315942088 634057913 296792352 289083170 170733449 821569529 181163823 47014736 942343752 7656249 232357203 717642798 888296283 795102622 834162739 834162739 624735110 325264891 443005532 506994469 896246616 345354788 678707761 97423383 533904502 917706585 13753107 49258892 101853699 101853699 918853332 898194087 357469104 81461678 192183848 84558827 351454146 194585430 579862958 247642513 137466715 22902770 681990669 681990669 856357642 477273922 396504994 396504994 665475186 284524815 89377942 582661560 277811953 277811953 232518146 717481855 242731229 487502821 927456926 927456926 677379716 272620285 912780176 555835045 410362796 539637205 36720271 36720271 775838281 269559705 267632391 267632391 161624604 440945009 442915228 676789157 118067915 101860523 478813237 478813237 157819516 792180485 838146691 565538921 59004544 890995457 18567624 162942981 429859724 429859724 887077303 887077303 290141487 199383429 112420554 873240637 934903839 15096162 173582107 514407907 15315627 934684374 268137245 343893996 931572463 89754159 167131281 909690459 767185592 767185592 460900046 460900046 463980338 683858063 903472237 46527764 887675834 554872678 835224869 300768845 145050142 145050142 611211008 338788993 577764154 827873202 132297602 817702399 549691770 900334508 216601327 733398674 144531068 805468933 52727254 8118602 436854580 436854580 790232174 719090007 784232665 165767336 761343437 283892372 213528847 82171706 568374994 568374994 99836527 178863300 908153264 511104361 22270313 927729688 760191275 760191275 425975434 418086764 28226805 15739710 737755737 430218871 724328677 68476829 197504732 2004605 626838355 323161646 589147938 589147938 841341524 50761951 141100444 111849599 620097020 97614917 108499086 460587328 89956929 860043072 54384373 948540165 11611195 207121281 759886882 617087637 188623611 327450928 898912447 898912447 333741718 101901873 697114937 697114937 304774565 407947138 211171260 334843362 659730982 556090048 427697169 548708957 310746049 385470703 143133772 566377912 158799882 835070249 392061777 428694426 682326731 267673270 407120214 288676422 188284341 188284341 423983186 183708353 249006449 249006449 4165514 4165514 391716536 635305854 43586746 514113987 804972553 804972553 177341259 622844820 550383089 851656960 80922943 545076837 134162398 134162398 205171222 744828779 367231202 947259080 565798697 384201304 807328306 389314714 26123447 26123447 776846040 686171653 184285101 587194729 301917614 315917588 287325525 287325525 11911723 938088278 505184853 505184853 577604656 372395345 693779267 20371782 523849060 443333953 842090911 18857423 140393548 140393548 229910248 458942591 762338136 164482128 512566200 869867675 426563441 815634013 91530240 95369661 353610169 596389832 65044345 562801702 207778712 643501577 407185915 407185915 238272221 129523183 394467710 758755070 511929693 165707028 870756007 79243994 459138002 490861999 463423938 463423938 469586984 480413017 939338819 939338819 496805375 181216950 214056258 214056258 923773962 259228804 27916996 79390451 627571407 627571407 938054882 930975827 216737445 216737445 379624409 379624409 837906272 122086408 824300550 125699451 165556335 78432238 705153395 705153395 38379028 453679177 854666092 95333909 318793431 424953178 663535330 901623855 741516247 208483754 97132842 57628530 758888512 688967138 369930626 834873534 445900506 213287846 182408465 87549574 626008095 323991906 245562005 439120930 100355286 849644715 214955319 596045274 768676447 857693386 492085645 644619991 149765504 800234497 324549040 311169810 832444898 832444898 184015460 661606680 9898638 313769295 34443426 858752266 329610058 125653663 871679771 871679771 485448715 485448715 194415568 92836227 762434161 477354586 92036519 840808628 297582044 540237702 784840869 165159132 91119747 464812953 778629938 171370063 375074609 375074609 432716036 517283965 538329 89308595 230698477 461235718 238234480 238234480 675651919 13264393 497235359 539601101 90876025 859123976 138656315 133322844 324186743 242534099 78582614 568989797 381859933 857748845 150137679 799862322 263859603 81530218 694931744 512077747 125025418 45601176 24596321 639073745 473768003 690706267 803678419 234837292 330581361 330581361 32800152 320143901 241922001 708078000 490946142 459053859 19476449 352477124 321586170 544701899 28001032 242801033 53036269 707034942 893703321 131036328 44780239 44780239 153558187 796441814 356507266 18201853 563308748 166043050 426781582 949932708 609414625 340585376 420130364 420130364 440155322 509844679 907525696 739177336 225758531 225758531 725991065 614481837 706664691 243335310 678761795 545171033 32076001 917924000 830905530 575458486 863946372 448750987 239147164 10215856 155149829 155149829 848456545 299189665 168227719 944085303 705575493 244424508 575548508 575548508 267876441 267876441 879525249 70474752 305941871 175246396 103087468 126107356 13580609 444036986 462715192 462715192 452758592 334314307 176634085 446455678 308337659 641662342 752314547 14186336 40792085 40792085 176208087 773791914 859031673 90968328 212545880 595774959 399522438 23070668 796812891 796812891 610803059 83013820 935845217 14154784 813865857 184266768 765423871 499560226 115468169 29172771 4082856 945917145 797783449 211007434 76723773 873276228 5357169 944642832 757810591 757810591 932151598 17848403 119290529 585323924 43986884 241809149 765041587 445584289 368704945 718613172 203318294 575572699 208771559 741228442