1000 1000 1000 926087615 42570981 544093875 301592954 145684452 177926321 786417972 694242403 402442852 856403542 13397204 793624386 161704280 664078636 110678288 375072207 964703506 379092354 423639851 212655187 213217924 44996998 770238082 861568098 478291339 294497236 522614804 456652703 693170488 143829280 224065141 646569071 621072889 896605811 9573405 807822610 378394148 760296666 401984663 246409186 889090490 280262019 537339881 135395328 801168891 985089553 672749587 352444338 428902575 797675144 249033060 703847101 995034855 113260798 84789308 737926707 157084233 326994300 39403718 212272606 434093925 246088116 945440911 733413392 179330560 132530585 496500516 573748088 910419100 28200928 940402507 331113700 551536856 253243114 357621455 255416560 307128548 670687017 719559470 159882591 753953726 391731466 71088730 442679933 539588936 935020297 300750387 83457927 165932709 856674463 347361540 457732953 773277304 683904004 281518836 421897412 405911160 756526448 244860542 296593641 989625978 550780327 266739851 605650614 6285495 630246290 752048373 211802764 981157322 526295612 476499705 286216511 566925419 682065965 902417092 827076336 898024120 829268690 671719555 212791868 429282594 144591449 32872489 225613357 981353035 746007775 793258828 835156652 27271114 475756097 605760092 348874631 68117188 484661507 659722512 83377871 510255231 425991227 264756786 996427406 940521997 851758594 218478719 410950811 220939794 71070702 597874844 995044333 986719691 667094885 674960007 702835580 20702497 100205048 539425744 198589948 898206935 187674528 341348819 917266175 162741666 697021169 808041728 190851624 398290619 841104248 827259 702214365 873333908 41525396 314408228 781168278 518199558 688724356 440237596 424044262 194345126 408421295 14452396 388418351 569861642 172010838 423672795 855531581 801797131 676655602 669208266 689276902 639246283 755011519 171689991 782211205 463129440 274751015 467749994 394641689 896985656 996324010 947577556 619430726 883744166 658134463 182745201 544036022 46808732 601954599 571182179 512918009 879943300 158197044 660755052 613398069 685647801 290102529 49394648 29867015 559912974 785525439 554073642 731586308 174561387 455491986 28946944 83393920 171189675 344867878 43150210 583402678 155656329 373294540 446159153 982350800 305166412 880145057 993886181 812464429 799182883 592977222 936086750 172497984 750263426 227017285 326833773 720780538 278433268 368633958 997542129 167698487 981446446 82731514 257911590 117901959 809121896 688048191 52239622 896963259 853596254 283681580 878835284 341482219 827991304 914612993 858538093 495328786 416278679 738823365 886763494 631786013 218649188 555837973 936817664 924369735 94170595 687453221 294863835 933022727 821900884 198716652 612102158 495319543 76137543 683599349 60547949 425243365 504867766 2728407 748220130 480014995 688182946 107035766 71919564 121080412 50370190 801187864 64727532 150638021 715626826 44662596 590327366 807456172 74255474 760601555 138740957 649096028 453120751 802287209 576006669 513286634 382973776 227194618 909643253 306593481 722990026 646125599 969244688 42315651 33850860 582302071 293342067 903452099 957757440 244708169 308004553 908178229 134685847 591259756 975706627 100324592 103652748 814082223 620287875 302155987 687415820 653848796 600060271 115618752 57436791 620647819 307166177 710223438 390851053 780998671 5964783 594269438 833090846 955780723 119005574 709795741 113728564 480327920 476926574 587276696 101134956 818097235 1141838 404502850 862721390 879988130 138812277 745660776 558328218 423081964 959097354 458878641 459456517 393232332 802032443 946405109 627397327 916642835 15939944 154446851 878997033 237203512 337582976 175421721 326684857 434403011 960895686 702522296 305062461 179907781 427649481 747517493 322802201 820887070 978583694 193039115 341615584 64610930 351750738 637099063 827793335 167026134 145615954 530183562 235819402 375224600 340297876 307342468 189896458 773374854 879787536 740318310 376040685 440680980 377390066 318181725 206858924 161906338 309577071 144280987 766041997 736037272 109658892 453278503 577352972 2444210 258340785 298612697 34782829 627719357 384006966 299549888 835701283 508386133 773825495 854598532 917850317 995425355 685558187 216597617 146513957 213085710 17934475 994377987 54187154 907586094 78231991 392224412 307008229 154754687 477422289 251174689 754278573 211612951 600341203 608352997 625835680 435214263 810522272 497995229 585756994 932868494 945015013 167913346 618185021 402761566 342586092 706740059 700231139 159566882 250083784 90377040 250858434 714700148 87279893 783428229 554029564 261393952 185167112 546635415 507331181 810392352 732514657 372972359 66870773 303923147 478031389 641286281 867498512 929793048 193735671 168442329 177737650 440069394 20634488 886786991 53587 946543664 3148103 649261832 588337203 246206374 696373954 1847714 58056426 281500364 11247429 568990383 506104695 154200874 831071031 268880866 808893698 680245843 228401704 251337945 726939813 530474157 174041331 140899940 539710922 616684216 846747914 740310143 795635851 738225606 317951379 753063875 346115 182628069 519399183 72679786 362378528 465836013 739298928 723918301 417487123 282320817 390314241 165234446 95467551 42186836 588416810 237977975 354871169 361430904 362275335 389860998 984245538 671718686 445302478 711113217 393699773 927233468 910323230 246668304 489199355 993260854 327712410 742249816 170468378 148948129 786732944 978331365 584545505 638363470 159959689 336093860 155751562 862882606 492117013 277828749 366765652 628027671 204923128 592919915 217010978 814383231 474170518 363570161 645313401 867286977 430110295 371794270 213984422 379557754 169100885 805211033 829867168 115388213 879294831 155071250 459876972 937794289 593760135 993368615 541570278 299970133 330220859 468499115 446040724 932539990 565445671 415412155 434345775 611106686 180190454 513144325 575733335 620477474 554117009 484484408 590945718 712824485 764943293 592003427 871349213 980978397 225840414 973979886 181706631 665954021 67935979 115283580 20360533 13734461 61462810 377422270 683485506 495317626 88223162 858699469 194462361 420460035 673295903 345958245 327184657 915636748 885677378 369409784 314714188 183134907 796951945 354117495 461076586 109923733 476096457 743457300 190247012 601632055 187945066 286129280 472676027 634513595 46276462 621529691 746198456 922284667 369664902 734640513 88953425 52483021 204495644 425371891 373413975 905693483 749658403 500151675 525674225 12730976 137368970 596295238 1342797 843706669 884913577 72525688 90968966 274742438 976390523 655192724 264038488 665507178 373809351 560486178 574794170 730264687 916327649 601249089 979367399 531193586 327549019 165896118 845005147 605498215 515128828 929422550 552014012 825522387 946157768 262091576 617644379 886417243 828493959 483750480 683411101 873839115 848530597 43159603 817938335 76050729 635138600 318530886 157396491 245946420 966127693 613975117 643381155 795307891 854105804 887820318 714645285 522357621 192911868 151530272 415474693 85760448 575710594 839745869 509077480 95550984 853966173 752327104 237787802 27887307 723331930 575234265 224251590 121652600 235535491 402703619 273763604 686121109 616867199 446243968 461698962 655943568 559727006 592435418 1860146 928027064 94217703 621465194 297875720 297441127 962562321 894524480 389129697 764397397 702069213 212821593 962772861 198084777 784610447 75256790 834276835 237659486 211145979 524232250 562701454 620701570 415416466 613394608 906346677 919876794 226097394 322530672 755297873 280858258 778809474 145788774 37996403 516339519 827452046 104401409 989697991 19654781 752020683 940792079 997813436 948593706 910027246 329357186 173154859 944148277 771340413 987452916 11474515 121949605 851504485 266040217 390487001 513877874 171108450 134682705 966691032 61815948 63388936 366088138 211580508 622932594 314238449 949055539 831055412 904099345 364566314 101624212 856961437 419321458 193002605 891786135 892247566 58118441 840248176 363178330 391210516 505740689 773100544 156837880 24723316 523446979 9437405 731220695 786908042 439509395 18028709 210810232 392885035 816820840 364871173 258829467 262478782 634272850 946465110 328128356 288854163 224095080 310622933 717996930 446961082 947440610 290482452 542011237 463382007 474331253 693696367 810731009 12895131 455317614 575680088 237237074 904709997 700132907 803234159 674958356 847042127 487050564 754629823 468213309 909325116 953187911 635066477 727449331 518293668 511549937 366635877 660638467 143715339 767739822 729536255 54066643 686557646 459740121 442155658 819705558 81833235 250266317 6725025 222554593 104198993 438306349 626945844 696104193 49060743 438355025 814552520 850936675 552150676 714115466 832700260 723520520 359683491 583720703 346578845 606367581 655400372 765284005 521799328 107152593 211480325 623822916 793257374 780782019 773168500 345889692 618345693 517684911 738427320 325411154 739540044 980015715 582181112 427677273 984922287 329093446 393322874 781139638 917802581 944578412 90606334 405378070 954166884 607840178 945736650 923026610 922931104 166368759 303754589 205520058 168195807 613351406 338515958 765383912 196192491 728085682 708162981 528009699 240492683 845198648 146572596 633185353 39256629 176847063 846412066 660104957 237766724 334049610 2332372 379471994 456662032 693268450 289203338 444299654 541222105 412477338 74215540 247646071 193036561 63478626 905184381 788410441 749897737 373809585 76311596 980367796 872607928 487502265 182811764 855423012 997140858 770278661 820536105 221857708 928295905 295442017 771140496 653082975 327876729 226017538 526038102 902189867 593344061 977868441 613116517 230152228 55579613 961095249 208004051 23487128 668848385 899462983 234336363 608897791 253451309 413813338 768146237 378312113 920796985 19176855 322592281 481839939 402851503 647855346 887703009 275569030 806459553 626610147 529515889 696773959 969437452 361828004 280643276 769520808 288828707 58965101 875626538 607339010 70088547 230138705 133483130 549282066 796242324 442428427 810810769 955067929 983905214 229141166 934264511 649596749 705150592 440369560 627083056 158954336 369600919 203931768 616935351 417451858 854347637 978496434 538464127 104536204 816658862 51405358 39902767 204046993 846251889 96812115 975378728 392900448 206814494 897910033 557366413 700976938 114190746 135648553 697214642 808066118 787098493 131537388 76967112 953157933 219797226 583936440 922372832 485100959 746146760 465217516 37592140 390531788 664535244 216644039 843008771 166187647 804410942 329329326 622511552 442481835 302090771 366014843 8239456 686293651 759639829 939973595 609991292 7978617 880396299 629005330 823330019 902833835 750862808 112303837 825292732 826180021 785322118 540077839 164293525 323582440 285219758 534799276 968360538 648130864 919839452 723184080 855982505 237976608 977953886 247848547 901824661 60673457 62843879 664073532 629677409 374708261 742755176 929653521 64850361 97199688 74721899 283482022 471391397 108076322 268694371 447817182 126142874 643780307 307065955 958170229 876076177 249469191 712793401 10366811 325146543 155470169 475094668 543621199 168725336 706865561 222238980 451132584 752340958 545757603 404116838 883894064 891942568 218425429 197711769 713986256 766949479 313394520 607984072 335774165 741356682 433491195 761491936 755919796 87699226 680495206 607510904 709011799 201981369 289005795 914108321 373639822 552349579 484671641 192826909 893349178 310921575 920032127 326750694 737860658 761574257 114562259 360449233 332551336 281461853 952107769 638624542 460648031 277180397 620645483 234899511 370901842 99710677 807731373 988424849 149392640 485662778 864887549 230208721 70032506 935622514 885238678 791684913 646042160 41897883 332620151 45423559 130242243 665002031 722482320 620371670 100393084 634089429 896702876 846429376 651051023 459954038 901833562 801308572 87146530 587098398 896527208 389029320 23402115 370580990 361942305 681386857 729811085 810193837 449214452 6667473 774026768 354030268 443885018 271942551 48687393 768248472 969088367 876860767 663302795 504601376 92254495 148245749 588343487 493561388 34553917 843096133 787118168 753283651 507483591 513411032 602414339 109082293 159437485 575560879 137664639 435938912 682755325 884424962 400898476 613007285 632722567 729344296 265836082 670102811 650655914 956579188 247027012 645724249 50231140 875520756 577329743 804863776 616861945 72634921 705888927 379496932 627125919 186844222 850233714 143911654 603523953 757248195 123929242 318840865 103728230 216310713 424592362 608827947 635013723 855563874 884838425 38652620 15565361 693645921 471787089 858077342 451363195 319029984 94707177 866206580 513388853 665560855 55015792 215511157 246125931 574475901 830953444 464752427 292772243 331567456 629134954 877104881 765119278 167347673 138354372 614511104 342628967 965758215 653392938 964285451 141252139 108189234 868780977 684551860 456714424 580450671 119400437 466253946 623819157 265466087 734101930 300877671 986182169 351590632 443070115 976455438 170323533 410266932 991730224 308643299 310187344 167705669 556616034 377356603 659648518 392126145 276536547 739445668 26785764 801277679 16663077 774643278 717793868 430263075 213582372 951658888 622501584 113686903 644280294 397065076 379429169 162417605 44227434 278444321 632294694 57061549 445868151 192669754 638060433 157408315 386017731 370712421 281438113 896437092 629033417 753191764 576901445 930941149 437016399 452198960 139235748 484393061 80512149 315897488 579656242 863165969 890384018 491295856 314560837 324099657 821829958 703205621 842710734 636213774 458705740 389781140 150980451 793457150 395832876 472126725 28159256 892496095 345645453 105415264 1248218 971758219 822290138 729928248 433684592 295931975 355671852 285447623 118238147 450312711 563852187 647945179 188114961 356026970 174524710 783874389 70206821 289231093 967263659 716530341 79228924 896564564 161572678 445722026 756280979 997248279 424935507 482681934 428573108 836631244 809622202 932798942 961233311 70637125 867059439 157233692 91280422 718446444 676243902 49722691 514386147 137077577 261623463 526350925 722820405 862488974 487868802 397279023 418685162 64256492 582864985 539543202 512792018 923567916 251269678 537213613 833265556 929737729 830105612 815309987 935662752 265730431 168515993 500623767 390925739 823521168 63478983 793582572 373473540 194687450 441084505 264173447 656508102 64624163 677719858 151222221 668936635 655584102 777188786 485593643 926933933 478484323 858413530 92546366 705395526 364144302 513582646 839584211 369613324 553851188 552685918 39492686 820468948 448492828 500205176 809957347 449844353 744871366 144139955 598712498 263910948 821492954 318860542 764005566 447992557 929580132 47487404 362810753 110404775 29297881 300832872 604383262 850973255 351955499 435816710 833787055 88577791 313451418 437114470 700542857 658401988 991111576 691510267 706583024 759737071 194767288 889111364 37865734 299928760 51829081 639393914 249105404 558585369 70471417 584390076 685155694 242115466 926988966 323006470 127493268 67579481 598877890 449615604 106796222 146471288 927016988 997386717 541897833 369419151 48460481 573715061 665392836 181624622 328959894 549687649 391953470 566825188 756641986 513374528 269949373 312540826 853285314 794348968 739949205 612038943 781518633 506550299 940301011 996917566 422756515 524909253 121084157 308511608 374097890 828262836 39745787 324658353 683734482 408224645 713992514 513517906 702113344 705548476 485512727 678906170 663110738 825277633 496328845 236992997 517285470 651509913 596324900 319640427 397753132 201487612 404522855 852864369 794446938 41172849 32662563 769245575 754795527 673848479 124548323 289911415 564642497 428467876 419382890 503359365 883566165 186250418 591341091 309829537 395012615 796389349 243400322 815151663 125873502 197485008 433099882 502051070 747811344 84821725 214545047 460513926 762997310 469035825 95428645 362723707 584669836 565601442 966343812 561443824 50755043 418093934 507231454 609994403 33659741 3004479 470159792 680238902 303891747 624777239 153178539 203459404 503954021 582505508 545124220 480428457 306669214 966711413 306285933 682189533 109078114 526328818 176249623 432320438 378143615 805665228 378767443 369305262 595449613 934224463 935684084 858861748 315954867 689032131 860224948 825564512 734997047 298737487 816776762 892955046 658676626 45645860 356917767 818236149 302086531 556223778 921636195 308737980 150250562 817270004 840585700 780679903 477950210 318876174 379158134 627447113 522370079 565416758 548040127 977862157 365760870 678790442 728043210 225277749 532510565 19114458 392174032 241030017 534410137 655660801 660215915 137247334 668238982 662793813 858119058 348507791 7083482 535824165 875873694 404121552 839115723 43230555 814213189 567682085 312556116 868959366 643651807 939316551 155735044 154575902 877021824 207721831 677191069 335275693 882405411 805873267 425027416 836999554 234963707 12935496 285453353 675811312 362674031 102893083 320340646 899804722 978368240 76822685 281323683 7542390 20643037 837113202 37319424 421993757 352141035 294202491 511587100 414819995 894636547 685741756 122225297 242040182 347188992 199401073 298220241 719836869 484804088 714655914 605405224 283778598 810393460 112104554 723376116 130816045 991553558 593834268 367120376 914304955 364155575 23379391 917265989 573230389 74322937 438290929 103857156 801462991 551833305 142604984 821001992 363107315 179739745 226812794 737284165 512898159 880500056 587422896 982098593 51755655 907597038 238975650 177055793 226458121 435084503 133772435 597166738 316143665 486740766 301531356 631018541 90689614 266767891 628515224 384676008 252284314 616058551 839550791 541040932 736479451 811618707 862025309 219595963 278899952 887087836 707401733 490022516 623651173 67957607 420121687 356801272 85527261 307167269 779897038 346973218 907463442 546085278 788354215 886870672 597296439 854763237 848587259 317922804 408141489 246247053 584944088 171415209 950605128 658337712 806454264 577107336 533027691 799438731 99644745 670989221 649730314 799173950 234187767 496550447 975803825 504114627 424506252 144563474 263745577 42007890 881720660 753162100 220091415 866649241 516641567 747715067 450091737 940145532 80663543 414822161 687283831 967517942 27364214 810060026 608228884 904471192 34747804 831137162 245541104 523577675 745899054 57449553 858946274 218409464 158199519 415539931 830912627 912926465 837137111 353320598 586668711 223693429 581845253 135584251 11783029 800284390 819851180 810750233 932233264 385125575 504150152 867303073 996311466 915119804 616040067 197776092 805674481 911514456 572966063 986578170 65478634 424370788 409309110 122370573 296160212 116432401 155981305 681333717 410984530 817262902 809807611 341523834 776300935 682522706 575329507 887180595 463258924 626730191 739967437 393074233 332895316 266225889 871854004 763190024 823775549 263632889 761614377 217022710 180721316 326948748 127887976 831592510 40748858 260750671 282666602 202263581 479470972 936972195 551515885 623804529 23283891 276254789 309169530 769189418 224257334 948846850 244199170 334112237 369750675 697480378 100929034 618923073 880555931 677601326 114043874 286837393 288168757 532744834 164689260 903550211 997547551 782358972 580181265 16487337 926951097 652098292 182773575 12305399 763393917 874266936 519243458 407749735 476984632 797555946 361305667 953141920 253991879 539855913 172709042 48469470 14600106 405869300 82327565 190550886 753584826 583208250 728229930 927052216 710974649 767553079 582971901 449933964 760588327 907330993 983973747 551033235 46553279 250 680 10 436 304 919 2 990 176 838 381 883 463 988 218 823 15 754 28 917 224 797 329 836 33 484 99 282 43 768 4 510 848 975 599 800 253 846 716 727 126 960 72 899 21 618 628 757 106 762 777 783 566 816 346 829 10 611 142 693 129 907 23 839 256 973 915 933 794 892 87 326 15 666 177 980 401 973 425 960 168 841 83 705 687 971 367 716 396 775 675 675 121 699 117 671 630 932 373 463 186 873 74 956 388 880 445 755 76 717 346 905 536 732 77 581 595 612 1 68 321 826 168 783 26 671 58 695 535 909 609 806 632 788 89 316 47 848 204 819 167 736 404 939 130 221 238 382 233 493 52 374 329 972 330 982 103 786 177 997 779 782 435 519 172 609 408 536 122 974 29 932 271 920 140 676 180 941 144 784 141 490 51 928 525 886 93 782 442 949 311 838 369 774 321 778 123 289 14 774 252 432 492 562 314 910 33 988 85 267 485 840 13 359 72 350 357 925 398 405 495 703 73 259 143 755 409 858 414 853 443 971 188 801 256 943 331 781 372 941 114 510 571 945 247 890 719 902 192 207 37 212 10 826 200 551 796 891 679 928 92 522 337 464 146 815 98 556 450 908 346 546 83 616 398 928 425 935 54 720 131 850 475 489 158 786 50 621 776 1000 303 383 118 992 112 779 193 515 222 400 190 288 106 809 52 851 145 686 731 800 176 994 709 879 560 808 43 527 254 428 57 144 277 924 797 923 178 511 417 795 487 756 48 365 388 681 36 341 426 772 327 653 336 576 115 376 171 270 142 712 215 883 17 608 330 915 254 540 650 986 138 504 198 755 353 923 455 966 323 922 263 845 431 655 527 564 325 805 319 431 83 859 63 762 15 635 75 448 152 568 418 480 739 757 397 589 861 919 355 524 11 889 15 707 427 878 379 511 81 985 128 750 219 948 149 265 433 972 248 851 71 890 12 720 15 715 370 996 16 627 54 842 53 1000 26 575 947 997 429 626 551 573 993 994 229 855 347 922 38 559 87 647 31 889 62 700 154 715 232 977 233 627 505 768 304 910 199 709 548 652 900 996 99 918 432 951 174 779 98 757 231 865 132 855 187 728 207 903 154 762 545 699 732 992 382 592 253 514 323 520 687 696 28 804 170 855 544 651 115 218 298 642 155 431 384 734 391 490 475 707 183 848 266 838 76 642 15 872 26 651 270 918 470 748 558 956 395 647 217 385 299 856 22 980 448 526 780 807 409 738 578 586 374 925 176 700 113 742 408 936 36 599 261 530 69 626 498 699 634 738 99 162 742 844 15 225 213 803 13 922 825 939 167 823 193 950 95 401 149 741 280 797 95 779 201 768 466 728 340 786 357 871 284 826 251 782 111 968 50 533 278 911 46 681 330 855 354 882 206 796 237 772 16 959 232 968 221 743 300 480 650 814 114 942 442 981 311 816 83 655 70 940 59 671 160 870 89 828 19 802 141 946 107 836 221 801 467 985 400 919 599 847 120 426 407 562 801 840 199 838 8 628 344 996 110 1000 51 671 25 762 316 988 216 928 4 637 28 929 473 982 192 842 493 538 201 543 396 897 269 948 235 598 116 436 270 989 231 846 479 711 404 675 112 658 28 703 65 595 632 638 285 964 457 964 317 679 867 973 185 577 238 457 628 792 111 249 504 901 48 779 60 957 51 654 188 224 808 850 449 951 181 946 497 719 350 759 210 718 168 525 111 655 303 872 284 842 86 938 179 434 113 165 545 874 108 158 201 971 190 966 770 942 595 942 324 575 104 699 18 857 90 760 321 841 100 823 672 834 551 713 275 357 397 682 141 902 59 864 479 560 140 795 255 612 655 688 355 892 148 640 521 861 424 680 76 727 66 814 590 819 601 669 43 857 19 901 385 967 461 970 673 797 59 840 64 852 257 757 12 975 267 751 253 998 100 620 197 859 175 771 36 898 38 764 318 632 613 617 45 830 168 929 128 789 209 757 159 179 340 711 207 861 186 792 36 780 550 744 149 354 224 978 7 924 49 737 64 837 24 987 5 69 359 599 222 931 303 944 669 674 361 548 470 856 572 772 84 278 581 984 200 757 32 618 149 367 399 970 375 832 140 443 66 277 48 342 130 925 184 760 361 720 151 689 228 844 338 912 59 820 188 923 293 892 664 806 386 740 637 956 87 750 61 813 850 889 437 561 40 942 218 819 160 168 574 680 246 729 9 573 449 982 14 546 177 572 77 630 86 729 3 732 60 779 189 794 439 906 247 319 389 953 71 983 197 816 361 944 361 938 46 640 7 790 486 987 315 860 57 894 81 586 127 517 425 541 317 666 424 818 433 676 83 755 305 967 175 726 304 772 314 908 46 662 71 865 175 993 248 347 206 681 312 611 39 289 1 715 2 950 93 420 703 737 128 926 71 472 248 980 129 794 266 997 20 595 77 860 18 990 694 745 271 671 234 789 208 714 395 802 586 630 60 792 61 811 782 987 542 762 491 805 31 49 214 615 130 618 224 607 321 618 135 196 53 489 170 920 401 748 108 608 293 860 304 924 144 968 343 967 479 995 241 965 156 679 258 445 807 998 141 468 163 300 77 960 91 711 53 581 423 979 2 975 69 843 129 845 160 858 8 915 101 906 26 998 272 959 4 145 726 788 195 775 74 576 48 716 156 719 762 861 417 631 569 605 98 642 94 793 71 305 266 585 241 844 386 622 203 758 285 970 289 308 54 821 466 937 146 894 435 792 640 699 173 576 469 605 191 597 3 952 82 99 49 649 49 556 506 836 367 662 872 965 210 922 93 234 154 336 368 679 30 149 179 811 393 927 241 320 49 680 169 446 504 813 480 653 17 832 25 30 245 328 234 338 14 886 360 888 68 762 122 761 73 912 121 630 31 912 153 388 397 918 270 964 225 935 388 751 527 673 115 923 122 762 53 722 115 819 166 843 364 860 27 77 744 857 77 875 163 742 129 862 305 555 267 618 498 536 122 853 272 871 50 513 669 906 78 901 856 912 11 870 194 628 75 934 480 984 154 809 511 790 185 685 128 862 17 470 518 818 312 483 207 614 722 793 143 780 187 671 334 379 574 688 313 968 213 959 229 805 5 450 460 878 738 860 826 869 121 810 301 323 425 954 247 942 32 910 364 864 371 481 171 665 540 977 691 930 327 888 64 884 93 829 363 970 147 250 40 270 157 891 138 958 27 560 251 752 93 824 130 995 167 910 109 658 180 874 394 577 220 809 175 616 142 937 114 314 165 943 245 751 269 869 352 399 456 867 392 731 45 801 280 862 188 794 229 843 493 956 173 827 631 703 338 420 32 926 26 756 126 945 660 830 183 288 27 28 55 983 29 500 191 926 309 956 758 847 375 999 623 783 62 290 69 914 89 942 233 808 633 676 76 983 127 506 121 753 146 259 828 839 554 754 232 920 98 783 148 425 13 716 368 969 182 811 563 732 109 842 59 573 141 903 405 552 291 491 177 863 259 838 199 489 369 466 202 290 598 956 330 402 7 540 896 942 260 435 485 911 407 629 535 678 83 766 142 753 210 965 181 735 142 690 769 900 954 969 111 320 219 496 44 471 46 281 417 938 25 781 268 873 19 250 455 723 504 542 584 980 543 629 341 908 135 950 127 813 119 749 246 896 191 947 219 929 49 630 307 904 132 780 84 870 803 910 349 866 310 849 185 849 59 959 173 641 395 439 529 918 369 807 213 932 90 809 55 411 429 434 731 973 368 619 345 944 284 839 47 886 799 883 234 665 337 459 354 719 96 557 151 875 738 997 503 635 297 679 212 951 825 1000 89 332 725 974 292 856 19 922 60 706 237 812 138 510 105 470 429 431 651 880 11 661 154 779 864 917 382 891 130 937 281 881 419 674 576 895 78 254 190 472 252 413 175 888 40 785 44 916 738 969 269 656 305 957 202 748 542 870 542 965 271 749 768 848 55 701 199 272 405 696 541 572 654 716 155 428 385 919 236 825 61 742 67 754 8 516 272 778 90 605 452 972 125 952 355 853 470 513 50 804 308 659 231 252 273 766 91 972 55 726 132 992 79 659 502 749 456 991 128 936 648 893 64 724 111 996 166 850 225 858 35 779 112 869 50 747 43 790 133 756 38 945 15 861 204 975 21 542 736 965 958 983 230 794 118 893 23 915 88 926 417 964 73 694 251 792 132 638 120 998 328 989 113 737 264 893 418 577 5 495 116 749 11 552 54 725 363 690 44 930 232 924 136 866 3 647 357 638 223 620 436 965 10 706 478 998 48 733 430 956 85 894 43 198 578 727 305 878 94 618 237 425 782 892 130 683 117 695 81 238 401 826 294 889 319 935 119 628 210 788 501 979 461 561 124 557 59 157 289 701 57 762 873 893 585 973 94 744 122 684 367 869 175 799 220 984 14 992 114 870 215 953 230 741 49 725 366 407 513 957 294 870 275 980 410 984 280 924 75 809 55 562 172 931 136 971 376 481 210 600 343 775 358 838 218 728 81 931 379 891 75 623 410 602 114 294 276 901 413 975 60 65 334 965 600 962 632 714 211 753 190 821 34 645 370 913 382 995 199 818 194 897 19 815 268 905 174 900 481 550 628 709 338 767 571 670 41 924 14 545 184 835 882 966 121 144 7 794 249 846 174 721 146 857 28 837 149 192 554 845 103 182 912 968 238 385 797 885 305 825 220 797 88 648 155 764 260 653 276 912 104 585 238 918 65 923 42 918 175 820 210 540 6 624 394 932 171 923 61 887 41 813 133 788 176 961 157 928 86 833 129 766 345 987 298 959 81 429 717 770 228 937 283 979 411 965 291 798 267 909 371 956 231 666 5 385 12 930 19 926 245 338 907 1000 289 791 174 806 485 996 246 968 142 975 618 710 215 968 273 493 231 949 263 763 307 920 32 877 56 886 6 515 820 909 65 647 116 843 64 865 223 969 71 865 106 970 285 945 85 820 21 630 433 979 7 956 595 796 409 817 463 887 160 751 135 719 82 689 296 814 106 849 69 124 565 741 287 993 14 784 117 579 480 998 196 954 42 881 147 979 210 983 179 321 630 762 99 855 12 676 331 985 322 925 703 902 156 274 296 829 22 996 386 783 486 870 75 758 205 815 51 620 17 661 185 476 301 554 225 861 179 724 390 756 77 110 152 803 297 848 24 927 62 806 819 992 594 930 699 936 379 647 102 254 19 462 275 287 962 996 44 678 244 962 401 892 564 999 195 498 340 856 385 799 463 984 153 844 332 996 426 946 74 926 234 556 239 682 226 907 240 811 55 710 16 684 77 200 73 101 239 840 6 881 74 344 32 492 222 373 47 787 162 881 245 942 183 866 192 991 184 886 395 581 92 838 486 993 37 96 462 611 36 600 98 734 85 624 27 889 677 788 183 513 215 938 204 995 269 775 472 984 245 835 25 951 33 481 469 693 197 973 487 1000 537 635 77 516 336 825 909 963 117 553 157 674 251 341 12 401 438 471 456 865 103 835 85 625 418 512 652 808 7 82 210 220 714 779 37 329 173 469 736 998 264 846 4 628 191 741 306 951 125 710 109 820 415 447 353 710 84 945 321 854 71 850 22 929 439 948 885 976 160 973 33 629 419 595 174 596 227 876 307 973 56 195 167 549 89 665 438 485 477 743 366 527 274 826 198 982 24 625 165 833 19 803 26 846 348 881 333 913 526 568 62 650 272 934 51 604 170 899 272 935 161 751 130 988 289 929 162 696 62 922 131 672 589 908 500 542 17 906 86 598 382 884 136 805 235 496 46 982 5 959 36 974 230 947 189 712 346 614 720 721 828 889 199 689 591 982 82 283 231 940 203 942 95 299 78 517 365 887 14 952 351 923 378 968 292 851 218 441 311 883 428 462 120 120 232 611 104 115 378 853 144 799 442 602 354 403 610 998 258 863 142 901 246 776 233 923 6 913 563 911 479 701 278 699 188 895 120 406 14 798 195 880 50 808 200 844 70 526 168 800 292 931 395 932 431 769 320 532 101 913 192 808 475 480 536 783 39 861 5 699 244 605 107 276 52 845 335 923 243 940 60 722 202 871 35 814 625 750 376 710 45 682 65 921 763 829 47 313 143 529 743 843 407 909 94 922 39 465 513 561 115 762 686 720 11 645 216 802 220 820 37 594 850 871 670 672 4 480 563 777 379 912 48 829 128 782 598 615 354 415 869 899 424 520 38 595 97 123 886 974 97 660 793 795 410 990 86 712 106 683 81 963 105 481 632 895 294 813 131 715 29 623 335 873 323 861 407 927 544 973 279 814 490 855 38 509 608 803 132 274 369 807 230 492 950 998 361 620 62 615 361 914 265 902 232 911 36 576 296 456 215 839 160 980 117 720 17 610 236 960 191 970 139 819 54 866 804 946 461 998 28 817 15 968 51 668 138 700 178 778 249 307 93 848 56 608 38 986 667 838 370 960 19 650 128 704 305 958 232 958 386 934 154 733 169 815 7 235 101 153 16 842 75 784 53 924 300 489 590 697 533 711 141 940 17 859 68 693 393 941 270 888 107 695 506 981 614 865 696 736 84 207 102 834 93 596 391 575 715 999 311 816 54 976 559 905 455 500 319 955 304 555 815 927 277 376 74 269 485 673 8 679 218 908 348 909 443 616 94 205 533 901 203 928 111 835 227 809 53 939 200 969 312 871 100 375 123 428 865 908 393 908 242 933 264 789 55 963 183 762 340 968 17 751 803 844 176 548 80 847 391 925 44 738 92 792 44 931 114 989 95 803 144 966 563 568 387 818 277 588 732 996 66 772 151 887 237 915 566 656 71 686 397 986 466 974 133 939 447 957 112 944 143 794 666 914 142 956 137 977 334 672 593 807 589 964 910 937 337 867 312 844 189 949 172 705 15 675 315 914 299 624 27 479 7 858 146 753 120 939 126 721 150 728 337 947 16 754 21 533 23 659 24 725 20 766 278 782 356 704 16 576 509 918 77 841 138 916 251 870 234 913 432 938 72 659 245 814 533 913 226 356 716 891 289 459 386 926 418 982 61 847 389 981 82 835 194 733 102 667 49 659 172 895 72 574 330 839 304 356 153 330 63 757 412 947 86 612 327 928 3 692 186 708 543 801 272 716 127 820 222 239 317 668 190 286 351 888 305 939 237 986 8 758 10 519 34 64 492 665 475 850 393 941 143 619 348 853 337 364 317 812 91 701 116 885 49 705 37 546 199 777 136 904 475 980 163 909 207 918 116 806 70 667 73 962 351 908 130 939 790 828 244 668 73 207 134 836 932 964 895 994 142 740 141 885 11 486 306 535 302 894 812 955 11 589 283 418 265 356 542 867 8 531 65 877 206 902 315 861 3 998 141 709 345 876 239 802 208 556 775 962 549 860 638 809 358 463 120 976 613 660 669 887 204 838 234 933 226 781 27 993 92 763 279 883 126 777 85 702 5 930 708 906 249 831 32 742 149 669 134 755 728 729 841 956 119 824 608 612 394 486 127 455 14 157 292 457 515 665 126 652 241 803 329 954 90 725 208 886 71 902 9 717 265 328 355 673 83 878 31 504 17 644 135 888 147 774 23 903 186 776 316 981 10 698 373 877 124 967 7 716 536 858 283 748 344 563 581 782 436 945 40 968 281 941 137 871 116 940 117 799 330 864 218 390 318 846 241 834 392 462 649 807 180 839 317 411 218 752 120 866 649 934 131 884 518 713 653 962 25 542 325 928 19 734 387 989 36 797 14 588 142 897 54 777 237 970 124 957 222 728 308 703 52 781 163 969 264 853 389 583 182 873 13 998 259 875 70 114 518 871 41 576 314 416 21 753 966 993 200 663 34 844 217 850 192 824 34 251 94 862 162 700 374 687 549 742 12 946 62 981 6 667 29 567 408 826 32 466 20 794 71 891 2 991 226 831 661 859 168 557 490 944 284 331 148 923 45 799 61 854 286 913 70 888 312 851 161 914 392 984 326 997 144 900 396 946 224 931 196 696 647 824 795 904 349 972 319 609 197 884 61 954 88 612 33 553 326 603 245 879 2 811 742 913 90 866 7 597 539 721 41 95 414 969 362 998 177 844 124 601 162 926 716 789 656 918 470 542 169 256 56 253 275 585 200 860 215 776 396 929 278 911 247 977 229 932 511 860 766 951 39 811 161 823 279 842 278 925 306 995 162 688 108 293 437 646 497 542 6 717 169 847 153 672 224 840 324 964 366 920 173 577 103 907 138 825 107 758 130 730 815 817 7 243 36 956 457 491 144 647 134 1000 865 927 247 371 262 901 72 578 224 666 512 582 476 986 79 741 135 334 188 568 82 732 396 904 22 196 247 661 116 934 119 890 126 790 650 752 101 320 75 113 282 989 41 753 152 719 56 715 276 935 283 841 316 690 540 643 164 811 33 686 258 301 273 784 16 559 5 663 55 587 166 959 138 145 518 708 117 826 114 730 88 680 125 865 173 759 61 633 109 516 416 764 72 735 42 665 191 859 198 628 660 896 186 863 101 621 293 872 509 812 284 684 494 847 294 961 226 952 214 865 628 698 412 452 266 924 50 569 561 824 745 807 518 742 192 535 38 982 115 962 39 197 343 625 79 853 15 389 161 996 436 970 94 731 380 975 378 911 50 948 325 475 175 789 299 837 56 614 2 513 522 922 374 968 477 991 41 904 4 535 301 853 26 786 365 877 7 921 426 721 214 899 478 552 105 769 102 905 102 667 120 276 406 619 307 966 205 729 383 940 42 885 803 827 38 740 177 822 99 843 74 693 219 885 681 735 213 903 123 782 119 777 236 898 25 621 229 752 130 587 165 708 419 996 738 859 9 888 261 797 266 856 352 547 471 621 29 834 167 736 352 646 609 883 395 970 393 918 309 454 459 801 428 515 121 881 1 160 86 399 472 591 325 764 9 593 199 941 82 985 60 894 347 604 915 995 279 989 165 875 73 754 329 555 381 945 30 680 78 379 130 755 13 636 8 203 442 696 233 352 1 576 207 921 181 363 373 774 278 881 381 938 92 603 151 586 784 794 511 593 216 288 403 862 115 565 133 489