1000000000 1000 806379212 124179766 804572093 804572093 562087752 331435362 893644049 439099699 901690052 19003957 620626189 404459870 45356491 954643510 635048553 635048553 654383643 345616358 222771072 222771072 536479407 435457872 74204804 67397234 327120199 327120199 198304854 924825170 279058541 279058541 69311321 69311321 194778792 194778792 84276602 830019654 445544060 901478366 76213148 76213148 715718389 284281612 938294248 864167634 394341036 912768109 278564404 259701895 232781919 767218082 90092791 68127530 371650539 628349462 202228768 202228768 176570561 823429440 143472427 668186549 181106475 818893526 663428084 336571917 419649165 156306433 124135654 875864347 991229896 8770105 328403337 558554856 611536591 21232530 777330810 777330810 33322328 591599900 967200218 944934193 514912264 585510696 4350352 353787777 523651115 523651115 995705125 16877302 525934769 474065232 616961478 616961478 511585956 488414045 370321970 353897290 689308049 86565594 989286917 989286917 137697112 969608691 192651072 807348929 31951313 968048688 894184219 189428892 406196816 665594522 114475573 353946071 9058597 9058597 73139560 843378192 103722046 65034897 127722906 348015824 32950088 967049913 184540002 605124161 936630496 887980555 936802562 936802562 124408824 875591177 376658832 376658832 37517880 838397067 719712169 714147113 589431972 410568029 917787434 917787434 142287003 722813798 624419882 624419882 91868021 91868021 556411149 984681190 775533756 224466245 985501677 30052352 532614946 512922670 964217674 7773082 751879329 110474792 434231897 434231897 85145591 958823859 420889116 846818896 96685240 96685240 908286333 591747085 503942328 615755947 139178466 531883263 147729157 947863659 475734897 524265104 67950062 67950062 811241703 188758298 127555567 872444434 256181534 154981071 945831985 961275677 461393901 702103348 388911356 522634373 566708627 122536135 114673671 885326330 188149867 47969551 822019549 626345499 293669390 706330611 701822025 355065028 556484199 661266576 637513332 150613291 36698064 963301937 909743979 876161268 466611907 466611907 932240088 67759913 589351327 385352348 288094181 159763022 191759816 919002666 897945393 945006118 131531570 44322015 817967063 817967063 176823766 823176235 953672219 500695663 510330435 510330435 901675305 25424315 459526925 540473076 389682234 63234245 13871066 986128935 918417002 308913887 214678973 136128818 998246233 445153488 512000966 487999035 333197555 666802446 7432513 186564685 826419403 368208324 295552020 48949865 515648270 551559092 735729560 735729560 290463727 290463727 331977919 887094999 146023004 713871121 41136231 209460508 8076084 8076084 43694051 36927174 208985827 208985827 664872286 181817813 27954500 227324630 6901227 993098774 380976161 767565765 968350263 968350263 13677194 785697574 517429460 482570541 951437802 913435778 243335305 243335305 307073382 63415482 103489025 896510976 600671501 102699556 461259803 461259803 807704342 150000877 260153201 392718943 32985479 38367745 856380068 856380068 800629636 764568369 167791693 832208308 35141083 105999632 490661112 65505240 539520490 141664142 864515438 889239674 26669589 992577798 442828082 442828082 603279735 498645768 621839345 378160656 818263822 181736179 55497366 944502635 322729317 116858598 349460867 757348363 624781516 362573534 567197862 235950930 547689464 547689464 924759786 350975065 575274854 737246930 85769496 19881123 230284489 50493122 96774333 903225668 545214258 86921037 556604538 556604538 414676050 740327286 638307465 756881700 90740817 909259184 162714071 837285930 390418523 544447717 368043262 222948888 854505114 961311179 706966391 706966391 120584636 120584636 174381355 13283449 342045258 556726058 526596684 485822766 597723343 427215115 826837393 289392003 57859695 755554274 730340511 269659490 416464777 416464777 992833795 731718912 604861746 604861746 195380296 198426960 54184223 945815778 601258419 104729691 190871730 637619862 659790396 659790396 883882320 649268550 145990888 750239695 996071036 931505862 6432645 6432645 622276885 622276885 30833404 527814829 51839878 136012243 133633835 129386842 703060873 296939128 832976961 832976961 524584240 606158400 152453477 530185841 91513457 91513457 261347908 335402514 543084374 370378566 513691223 454373433 926358935 196091686 635283427 394379547 284357510 31023661 112005244 853842318 146527115 853472886 99755603 125526888 963722107 824647332 642383994 469829731 804604310 195395691 30486201 642556146 456399588 207221903 304739316 695260685 350471469 619052730 892912423 682521880 727243613 624755936 730429193 290877805 878707764 447841616 50103786 898904955 890179118 476982462 372433262 341256023 752404261 88736221 693941459 693941459 912820734 912820734 543115578 367833359 566987368 566987368 216946435 676431339 570221982 556019999 241120747 758879254 105972869 21268326 751628751 621320968 710798363 821999878 264813859 800559331 246289622 246289622 137483974 19863365 554435899 193743396 34036005 965963996 744858421 956729156 365555093 910803451 7600063 127426922 217201408 782798593 504530824 660675413 93019181 406969348 378607277 186650689 854281293 145718708 618440836 818709967 828987592 828987592 964280436 35719565 240632082 990380400 12660090 987339911 897245529 102754472 703784835 305071349 494365242 305267090 160470412 160470412 665337437 334662564 830698115 343399699 299102399 986768413 485241908 768490702 726522157 879649049 660948604 950980797 98628604 98628604 867755879 149226386 77735764 77735764 255081394 255081394 584845441 23227827 916084740 483531632 146010659 173293461 703732281 8820123 651822214 9194899 451437708 451437708 851663653 148336348 595504930 253410464 796965735 931858678 745519431 745519431 260137527 739862474 90423244 53016378 231636782 574005561 511061520 261343211 46627278 58309432 628398771 18325227 310191761 460117894 345473532 413259329 771297605 113963632 442680707 557319294 700798751 468008604 860715385 143483787 487126101 487126101 632649260 961769741 135534854 167179466 71480508 71480508 842057264 318576505 520167021 479832980 9815323 662094033 242910287 324561732 387950446 473406911 610983412 815323794 676847732 584600637 853114025 344252731 360145353 360145353 232181822 767818179 77991153 544475095 13242631 400198356 30507897 866086297 81292081 575802925 124534567 875465434 393008195 606991806 139525792 860474209 802431301 802431301 390214659 857083251 734154096 265845905 773003487 50857993 285996769 369908106 648131460 884454272 795171609 204828392 131447336 303580467 364439723 221198484 304734051 695265950 719860876 608831775 422678687 418016104 589151477 122237106 795954147 699671002 947265959 197437799 964859045 35140956 717989409 54518156 934084715 934084715 940339501 86827813 38763097 203409626 302482653 865339324 450231575 19904640 449132640 303511478 374419593 237148898 308917866 811110347 597481243 132026835 686949582 134650993 931626603 943168559 340264869 10738205 807868552 807868552 509373383 490626618 741761215 694847626 15593453 15593453 99005666 458113318 126539953 873460048 3197281 872584816 259631060 91276675 741946127 741946127 212081226 212081226 432839345 567160656 660336280 660336280 605055638 842189077 23046860 829440424 34183047 965816954 741041071 741240540 87743980 745276097 267108170 732891831 643878133 499043232 331410267 29268252 1099963 998900038 536742545 28220209 546461015 453538986 914875532 914875532 907362363 457853737 817623904 283476630 796745869 262160328 731370752 318999266 338426161 91143693 165134906 159792278 283207562 716792439 227381979 772618022 633013394 366986607 28984885 28984885 621956383 621956383 169668563 749118849 513172891 513172891 63194402 838241580 454771389 219835477 663534014 663534014 104341245 104341245 933142678 933142678 196878009 921835488 361443563 638556438 12783513 775328811 476870695 523129306 218354266 661653004 413873516 643200893 307386246 307386246 405489006 491208316 880101569 119898432 403297960 945119479 925105025 74894976 822984334 630332686 681244756 835306226 557871512 151048534 873461387 503104416 35293649 6922069 590257094 445065772 153064655 153064655 161918150 130335915 576921707 251348385 588810937 970104123 370637411 816691434 984410444 930533244 924956514 92417156 853567123 599052739 838783206 442380557 650290619 292997114 315955378 61255678 14633137 985366864 824371940 175628061 167481055 167481055 959093836 959093836 560795042 140226685 257057574 257057574 747475116 747475116 834792987 862611756 115215047 321922581 611453621 880016660 731139961 839467835 158382546 572549324 605386546 394613455 445279317 207747329 269286528 789404701 982082625 460874443 121351224 878648777 708835930 708835930 210243012 210243012 637146601 603315429 571618700 384200972 33218313 966781688 241764102 871401037 938864133 794663253 221979628 221979628 112799797 57149183 85823081 817960411 487520697 137070695 893809177 106190824 601098960 601098960 135067658 978543229 139002229 139002229 795837593 133215502 889672129 889672129 88126395 88126395 395866317 512709781 15892800 984107201 460473326 421139112 431153479 540387976 895849194 278559238 94075679 199466308 321718806 73631835 242326005 808222335 44248406 582940045 430275293 130717301 879013562 120986439 33605770 853150361 505731085 895016745 292849307 292849307 844424467 915298651 151351986 708216732 943431007 259063187 316117076 562097291 907882193 907882193 132872550 873857317 405825057 405825057 66263503 911738329 534741905 534741905 214707312 526968614 336663602 336663602 863269576 136730425 210949291 55972539 490597326 509402675 451607852 451607852 443330936 443330936 234174093 558834825 445582349 243921470 50467273 487867270 582493587 83583594 273870531 662680994 198521082 198521082 349252163 349252163 881873273 881873273 756694561 64808113 495309549 504690452 953850619 804207918 926219325 492776978 733398502 266601499 26006303 975175574 946578732 53421269 403975663 596024338 784842809 215157192 239859541 239859541 267822166 111388710 460189591 539810410 542206737 245748562 484030538 628004487 420116173 310743201 136654082 61512541 221890117 773504050 150615829 439906494 354980549 645019452 242679131 447861603 896047350 896047350 113823046 749305844 981939301 403632530 761681158 761681158 634512971 889379094 393407469 393407469 6182074 11208554 388858337 388858337 564979865 435020136 625866911 374133090 500040756 499959245 376786581 812494714 376845262 981466387 831635188 168364813 561955311 113150114 13778700 662618870 7963748 992036253 582000581 756982169 322111235 322111235 999730499 28555483 777980706 222019295 999083653 606031397 54376449 859198991 964944247 35055754 74257803 64360270 48198842 118921316 605372011 207845455 638473645 383821793 318771647 811603816 552648274 552648274 640170141 640170141 358067999 135065502 322677538 677322463 117075532 882924469 775804359 775804359 743165951 256834050 866070917 622835176 827274156 922749468 628602942 371397059 700731823 187088627 70388521 929611480 676741295 603458293 368740061 243059512 764632523 764632523 371846688 371846688 256477185 539360425 936737445 649464816 443813956 443813956 708170175 291829826 789956528 67788124 693073973 693073973 7706361 345188462 67551523 932448478 464344442 577285894 817794098 635314090 709299657 191514892 862893169 862893169 918122080 405410210 834749155 390550322 453221902 453221902 164855643 225444858 171329559 91670733 325185825 325185825 506754640 506754640 528006699 528006699 931989279 635042423 282496796 282496796 594485989 938650282 439998117 16545389 83641652 578750979 967316786 794901767 167786438 332831994 136169545 863830456 323788390 3197845 133851921 854390724 173480445 787325496 838494599 838494599 683080091 866678077 430012618 553054314 434273309 894825365 437719422 504997154 80922770 919077231 666492981 984184741 471564417 528435584 681143632 681143632 72783771 560848576 807937480 807937480 323044301 676955700 448662913 551337088 391966329 636081840 60806564 939193437 854650458 860276368 688875991 688875991 407797475 407797475 203901658 724678902 146488079 975054632 156344781 156344781 235443337 764556664 42537169 652483234 68280238 910522284 94159375 448349350 640671065 250571037 404782103 404782103 179134987 20525143 437552665 566570322 299544209 299544209 438919465 719249304 122570065 54857120 43793228 956206773 752200822 942640958 592943181 138640556 49176478 950823523 227544278 227544278 919884295 80115706 993856927 927804438 333380542 333380542 792564414 207435587 577334980 695179148 632971351 786308554 723376445 970080880 206368941 206368941 791795955 208204046 220613055 220613055 525508297 525508297 179387400 213739832 619788216 619788216 281635290 894153109 202017486 678808823 129894391 129894391 951380941 613186432 240909708 240909708 37302151 962697850 872073753 127926248 363871325 91715587 779926896 507229181 345326409 171443354 634495372 109399414 472377204 71926678 202475217 3049343 463733484 210478831 302889130 628599573 82244804 82244804 350034944 503679218 668799927 331200074 821329686 137399887 384864387 117561751 955923209 246192375 551859418 448140583 194935420 805064581 989493368 139020517 433850858 566149143 652340002 846711179 987551688 410483794 902989834 607083482 669281744 876375993 963204071 36795930 265942088 734057913 296792352 289083170 70733449 771569529 131163823 947014736 942343752 57656249 182357203 817642798 888296283 795102622 834162739 834162739 624735110 375264891 443005532 556994469 896246616 345354788 628707761 97423383 483904502 867706585 963753107 999258892 51853699 51853699 918853332 898194087 307469104 981461678 142183848 84558827 351454146 94585430 529862958 197642513 87466715 922902770 631990669 631990669 856357642 427273922 396504994 396504994 615475186 384524815 989377942 582661560 227811953 227811953 182518146 817481855 192731229 437502821 927456926 927456926 677379716 322620285 912780176 505835045 410362796 589637205 36720271 36720271 725838281 219559705 267632391 267632391 161624604 390945009 392915228 676789157 118067915 101860523 428813237 428813237 57819516 942180485 838146691 515538921 59004544 940995457 18567624 162942981 429859724 429859724 837077303 837077303 290141487 199383429 62420554 873240637 884903839 115096162 123582107 464407907 15315627 984684374 268137245 293893996 931572463 989754159 117131281 859690459 767185592 767185592 460900046 460900046 463980338 633858063 903472237 96527764 837675834 504872678 785224869 300768845 145050142 145050142 561211008 438788993 527764154 777873202 132297602 867702399 499691770 850334508 166601327 833398674 144531068 855468933 52727254 958118602 436854580 436854580 790232174 719090007 784232665 215767336 761343437 233892372 213528847 32171706 518374994 518374994 49836527 78863300 858153264 511104361 972270313 27729688 760191275 760191275 425975434 368086764 978226805 915739710 687755737 380218871 674328677 18476829 97504732 952004605 626838355 373161646 589147938 589147938 791341524 761951 41100444 11849599 570097020 997614917 58499086 460587328 39956929 960043072 954384373 948540165 911611195 207121281 759886882 567087637 188623611 327450928 848912447 848912447 283741718 51901873 647114937 647114937 254774565 407947138 211171260 334843362 609730982 506090048 427697169 498708957 310746049 335470703 143133772 566377912 158799882 785070249 392061777 378694426 632326731 367673270 357120214 288676422 188284341 188284341 373983186 83708353 249006449 249006449 954165514 954165514 391716536 585305854 943586746 514113987 804972553 804972553 77341259 622844820 550383089 801656960 30922943 495076837 34162398 34162398 205171222 794828779 367231202 947259080 565798697 434201304 757328306 339314714 26123447 26123447 776846040 686171653 84285101 537194729 251917614 315917588 237325525 237325525 11911723 988088278 455184853 455184853 527604656 472395345 693779267 920371782 523849060 393333953 842090911 918857423 140393548 140393548 229910248 408942591 712338136 164482128 462566200 819867675 376563441 815634013 41530240 995369661 303610169 696389832 15044345 512801702 107778712 593501577 407185915 407185915 188272221 79523183 394467710 708755070 511929693 165707028 820756007 179243994 409138002 590861999 413423938 413423938 469586984 530413017 889338819 889338819 446805375 81216950 114056258 114056258 873773962 259228804 27916996 29390451 627571407 627571407 888054882 930975827 216737445 216737445 329624409 329624409 837906272 122086408 774300550 225699451 165556335 28432238 705153395 705153395 38379028 403679177 854666092 145333909 268793431 424953178 613535330 901623855 741516247 258483754 997132842 7628530 708888512 638967138 369930626 784873534 395900506 163287846 132408465 987549574 576008095 423991906 245562005 439120930 355286 999644715 114955319 596045274 718676447 807693386 442085645 594619991 99765504 900234497 274549040 261169810 782444898 782444898 134015460 661606680 959898638 263769295 34443426 808752266 279610058 125653663 821679771 821679771 485448715 485448715 94415568 92836227 712434161 427354586 42036519 790808628 247582044 490237702 734840869 265159132 41119747 414812953 728629938 271370063 325074609 325074609 432716036 567283965 538329 89308595 130698477 461235718 138234480 138234480 675651919 913264393 447235359 539601101 90876025 909123976 38656315 83322844 274186743 192534099 978582614 518989797 381859933 857748845 50137679 949862322 213859603 981530218 644931744 512077747 25025418 945601176 924596321 589073745 473768003 690706267 753678419 134837292 330581361 330581361 32800152 320143901 241922001 758078000 440946142 559053859 19476449 352477124 271586170 544701899 28001032 242801033 953036269 707034942 843703321 81036328 994780239 994780239 53558187 946441814 356507266 918201853 513308748 166043050 426781582 899932708 609414625 390585376 370130364 370130364 440155322 559844679 857525696 689177336 175758531 175758531 725991065 564481837 706664691 293335310 678761795 495171033 32076001 967924000 780905530 575458486 863946372 448750987 139147164 10215856 55149829 55149829 798456545 299189665 118227719 944085303 655575493 344424508 525548508 525548508 267876441 267876441 829525249 170474752 305941871 75246396 103087468 76107356 963580609 394036986 462715192 462715192 402758592 284314307 176634085 446455678 258337659 741662342 702314547 964186336 40792085 40792085 126208087 873791914 859031673 140968328 162545880 545774959 399522438 923070668 746812891 746812891 560803059 33013820 885845217 114154784 813865857 84266768 715423871 499560226 15468169 29172771 954082856 45917145 797783449 211007434 976723773 23276228 905357169 94642832 757810591 757810591 882151598 117848403 119290529 535323924 43986884 241809149 715041587 445584289 368704945 718613172 203318294 575572699 108771559 891228442 204838504 759799895 233194075 674912676 761765951 761765951 226253603 773746398 694291229 717122648 946243688 53756313 733103926 777917982 495736311 117987340 670782393 670782393 579394725 356615906 639244748 360755253 624354278 355889689 997391552 810861412 775848321 775848321 60229706 956544023 219054847 482525390 40454939 959545062 59152908 940847093 659468115 435204048 774590102 188835976 141559319 858440682 943043655 726430474 349697544 148852897 803175566 196824435 487089383 824871510 945742672 33095347 829504879 170495122 220516473 623814783 924113104 415041942 675712740 80761468 837565054 259602778 358273095 2176022 771536990 228463011 801250983 801250983 144901209 75232378 881193904 62969341 300415043 300415043 116964005 116964005 11237035 988762966 41928230 793029032 757841439 990881266 210280878 210280878 592511549 641032777 997052269 27941631 48768874 229466397 86520957 112726528 378301776 378301776 554788220 939225109 702546951 297453050 681472508 681472508