1000 1000 1000 98185333 780343777 34465630 374317015 775562728 214050313 724864125 790118092 333646553 145442434 517003734 644979520 739798810 788032959 355439374 695634443 371632177 680293816 851102314 504051930 705326125 294016320 401562723 48649909 526807438 995507482 300591303 607353974 794438121 918415567 315639622 137954774 498387064 916905024 867814220 416142224 882733553 202468253 560510486 589903538 182065924 111101900 833082952 644105261 191350098 295788460 279531258 735876245 144860689 931485582 99221277 990023484 303067843 659029727 17220348 142476522 188685379 389884529 9126319 426319339 81795946 769982216 9941534 739935180 5204927 414671463 18474147 794351658 642810142 281949822 160177727 310024885 572247745 270476719 285966478 260238243 147617570 75206285 357194251 489652826 572756836 19862300 765109282 297481428 558246412 3080908 143984170 776375548 317283023 37836583 839697261 632963364 830728196 376381366 771661140 314111038 594960734 170721549 3155383 115474608 843427020 147663682 790315713 367949173 289971100 168441308 477317636 5241062 627630541 706963696 704994237 620029933 393138298 446507695 989393911 891213010 628092683 590086252 589867909 730880918 897559670 414930558 173811044 825283637 341883477 973272949 57308633 852378094 273879093 10856833 144153930 242531014 793746294 337464254 471649111 616880022 861224533 500845928 915856239 894700906 472536049 803203094 286324223 835222247 660814622 996928787 927488730 110825396 776427320 241688372 285212432 182571044 240666931 904843625 11102662 336177503 21094160 113237491 383110390 151008839 531348275 3172187 342909993 274291084 245753545 505154579 966679954 314875191 683945180 758511917 237844434 723103450 127060708 958379129 535746384 117547688 263815646 1133574 952275009 481516044 950857796 806807388 991665801 287366448 236242535 591524682 639230844 864210961 679089930 254586648 418780537 294153271 826793257 978598614 69902282 306032709 805407282 392678510 982338743 668562853 650774061 566051297 775878983 253641694 831113109 150702987 214813805 61367371 911300473 838555865 759884835 254053205 805043408 559262738 688865864 791460225 363044015 825236962 761860567 374520750 777593934 687071103 449309906 759918431 477790599 674743635 873589611 748359179 386406748 330077368 854602356 701085068 447580635 27173020 782699952 680687427 450862014 191234975 34562570 800064914 101485111 947251969 521970868 915501446 277666460 52664199 975048766 880161267 761095726 11279714 497937162 202128802 960703515 823973283 477913243 52806544 477418469 544962067 789296861 941574671 861812396 131120989 789404496 725071560 183546129 195715562 535044067 134329286 859691427 707707566 440566745 249648136 400222689 517930630 808264051 841296207 787310043 920122610 167737112 239865859 476095223 933486332 932776441 811881429 973550 341158256 66287974 382392031 641685651 585162146 530570096 286340074 675515755 683801187 459888523 810905694 503548263 610876454 925672201 760295453 996499051 309131407 199037008 778967297 290129172 117485756 305480505 205898048 364711829 766111204 64271955 935906893 887604139 609786229 381915728 526955478 381290827 261349002 887974452 681227150 234887932 956742666 502605269 841126578 849590788 91258294 765625941 68993047 904806473 174796701 763746570 202938530 405928703 244033741 433994870 11768707 462448275 412450275 900781559 738091601 733362303 432888401 44200930 891116644 277367225 407870482 252351459 158280885 346746456 607301646 143453658 716142821 4170475 991287106 487414112 298507952 13352559 383243831 851443672 897409018 632120148 247170498 163309538 606844331 395523313 552313243 393251547 549767003 501956342 2473951 101738047 268126696 339384797 737643198 939704453 600710850 829281280 591877478 725699877 359957150 746837718 280445876 649082 833424946 310189411 50031138 900488062 806690080 571865792 608201060 50727882 355371282 881818435 291497399 621469086 392625230 961711627 25817514 725572528 201781405 47645200 985337390 608976452 991152787 844398251 739938477 618679603 205502076 211163109 42993900 631567993 591427748 329070570 8859966 230235277 458944468 570286627 122534370 706470476 182879965 772184350 484371757 26711836 384748587 640318922 983016658 822629612 772730401 364967491 683261733 865791268 200980846 515501642 258164688 562537792 814101988 979023857 996747992 546133360 515741576 707613563 682150438 782304961 455337361 587765214 899214384 595079227 454978614 678309046 345977254 100194606 65204824 347641257 508220302 118567267 715579171 555699973 271873491 557059636 536600613 194340961 46710939 716928417 827725722 594942293 357179961 768164727 137432290 336016481 152580376 837483528 359179271 818748214 433192361 854325398 884239461 218420990 548008316 196114185 838535208 190634687 667371351 997941094 70648426 916177213 985816474 382786320 323103784 769050543 674502518 598241193 583228792 80713128 142097184 981200265 98598480 321146936 10495592 113978112 429704314 97971707 934333678 205645292 517793643 687877744 331095880 720003822 789312010 237947527 869502270 803409789 400422563 24066768 638393536 273663475 728825605 287876755 447144593 734212298 815422800 627173268 769716376 710462311 369464940 531794610 893523143 909212797 794086925 703646296 527239177 263490277 109572514 816595492 346892462 746402315 317934419 515675449 808013175 269656218 978888212 769984370 569713974 963539850 7284700 972361779 321439158 340510156 182654704 433398093 388663439 465076225 871211394 807484941 162819589 197411039 225144466 878795882 92860302 1910216 14336082 147201017 816240568 201454927 757227698 639914664 953500015 582587988 969742563 381504695 775500281 318846197 981424601 589502565 534906538 555290229 391469145 669773370 192141497 88169574 895205610 575557535 615419815 631905742 351401941 709765566 895327399 455768491 104834572 732480984 662632877 649572689 475509198 767757138 836035601 68659294 247971048 520341677 194513894 732764310 348255299 253812301 639270565 269323605 317975188 141231733 380438219 460755856 725452510 492138892 425920287 499607752 704036821 582846811 877413757 429906420 667986523 546878712 844984180 54856085 718846378 276296174 818689998 174421083 334659799 404348856 597923677 213648587 549746830 270742559 583710926 701860225 854682768 225909230 757220813 795748980 526659854 410178978 947337685 385160967 381742435 893007538 475455322 248409116 902449665 313647796 488085992 9939087 526222391 700186992 356907043 901917511 570980087 212564507 570826413 121763773 283145918 451638072 982160009 53934080 925200003 849868333 233537034 809695022 971476570 494954993 199584257 774386461 515777849 583823906 615176578 451642676 815158320 569795178 769222205 837918926 225369969 887466749 713245728 515128208 966651772 551742908 959816806 57125420 815872623 818580529 5170276 833928759 221964255 719138457 846729647 285158049 878669692 296578904 644502379 456420461 657709446 614106297 719617574 257920788 589543967 373642788 779985796 903367902 404416853 578462762 47504392 141234811 768762953 716847819 715144491 543334292 389020656 852793128 222996679 13154134 835183231 859162339 124022551 685671979 796038538 456335157 744003883 335163592 929162691 655043386 833825327 533875474 503360475 301683237 127494724 160486591 741912424 298911767 494504762 135747591 604089382 530393803 768100718 104190235 455453145 603174802 1039554 866421978 549246471 3446074 904507413 905898838 10387582 95390508 521153395 35480108 404669011 886355061 47965397 86215438 463267130 958319142 106403805 584474460 847323534 146218381 168234597 55055147 557119038 679073400 313393194 24245818 351690658 412972539 818719047 664780504 429954692 61916813 221199368 468163462 128685350 909232963 890471383 171754773 730368886 403826123 630867491 628021200 348767106 406829020 573678018 932023217 594694732 745726606 726952730 759488037 162975522 873875802 712766003 374031407 61279602 437215526 544184025 716448648 837416341 8004354 468341663 459748266 597042944 749527209 154263142 273316952 677853452 803800991 518426642 203148245 789499554 838733004 600850952 54170991 49170565 418960568 933901630 975533142 761267699 175317981 695703989 239799075 899312573 121435532 976223317 468930956 680390181 184299948 892383529 420323199 466551295 877758744 843666402 945840540 448383029 962592427 780411168 321877044 211849852 529921359 112529869 42226956 690861200 166165089 555415509 628796453 608416622 250624807 955603793 310555186 561444321 639180279 229729317 122221287 869261681 715329874 449542293 593501443 614175144 101690621 198647535 22604045 862825852 441812817 811634171 236082388 606062383 956510473 412653712 154334510 296155503 257521727 834020053 709799095 826846231 96646663 632228847 559242769 393878464 713627452 757885111 215458982 545556894 787104691 718944448 505373241 980399692 296787486 168703819 543462608 205752174 771535587 808023050 803725480 557607626 828883893 136900909 508307778 938730728 885951142 558414613 387212386 858170827 215143382 144642432 732423753 409115884 886802990 694430133 592736740 912419599 20287975 30148746 470150099 656938573 864280026 267034053 140517296 545407811 278918023 561861127 778167605 486932931 64541586 381265505 680664440 923194179 114923514 660255307 193270673 179871185 319661340 906542504 340586759 213150887 586431110 786952158 643345389 701879361 79092422 135209498 271352656 211977679 910567614 557689445 501043034 15039065 979182921 87631593 723206083 397688074 926771435 131864358 857756596 758744374 421425445 951774028 212919580 591417840 157663684 649180844 950003384 200025273 39175446 775640226 512795796 819075329 13820303 355041523 287817815 219007671 371658242 596310583 78093849 985228026 465617556 681057326 534301565 793202960 879778840 953396454 406336574 983965375 16882691 158016614 321896467 971109656 6860569 500428416 155919688 800685084 84444258 109004457 338248967 259813354 49632226 21854367 65630214 112839613 453502275 187624191 105362001 308085088 805562693 997436732 565378696 154544620 301777210 306332334 974213460 916463131 683224588 166062968 163867330 27117360 840596835 627229490 555724057 963759627 533693871 531168500 301195710 448497123 371101171 89404886 847497489 551909348 367711106 861919762 722920209 549491729 178235924 478382374 785011820 439009114 254809610 399713049 176781836 313114790 307123968 301699126 699692709 323653240 348605335 87409388 349047925 719597075 735390013 452494114 41975466 272025728 920926876 224354716 903648603 440876035 900695934 631117998 81890004 589490037 810658450 10054466 727002118 685388512 391132365 606863952 975460427 748499198 9167385 781098549 120021271 261201627 335212166 150425210 595273776 216511787 84059396 318744752 633030529 758146880 963742965 46541879 757889076 717972804 942575611 681144980 789912866 562824769 943819910 35817056 708663872 61397624 633803191 27040340 764311289 276348060 942349996 511753524 512808280 694094645 458727952 962227462 896594823 997873537 578929739 219921976 595481894 786129837 221864462 245786794 34846238 85161324 668469095 620018235 683416696 827650676 606219368 932212235 636836908 630771883 901572823 925019898 781280068 470799124 388379620 268058086 530930441 28965857 3849794 554131235 969780457 533934104 750149726 421340404 114197779 833920624 259672155 658762335 772282728 656301243 784715631 566206204 657368851 941311908 933188585 727998 493149718 991132372 943285945 350380912 280649685 429707587 249201391 597141544 206138895 430846260 582043597 120015973 38365414 466327746 571440451 788548305 791859486 975990339 232932321 65955953 143213838 465937680 372354672 991024281 362820302 354882220 586550790 974172526 109366608 925598366 138539115 172720396 120168439 819986472 227887482 500936957 292550634 456166347 608975308 918169270 93731727 868653482 709034836 692711410 379388171 119116781 414026829 10447594 8021648 151129743 335934351 479754317 988566522 683930417 910863680 57882617 691419939 856299894 157962882 579577604 568470116 120433991 561847418 268288292 282923104 326556332 585137844 631019403 721585923 924780864 696434207 563346697 379612870 614008199 949509507 718879 544826014 690086388 414577455 163749735 68923069 701891102 617009575 545703895 125836042 418296179 759743718 446081630 202064142 367604903 709066319 148157052 208610325 885993436 607589379 858928433 980654837 238527195 380086940 643834559 82557945 299201418 218943624 604737600 690277850 612657235 529476313 91530008 401500670 754507544 134383139 936047812 874912920 574997017 598860473 394231903 207654766 679317466 488958474 272223339 762630276 664391619 18271764 878555896 638369834 949906793 506839285 833446024 4026597 911168419 898523953 947850801 794508261 248610782 983630531 307869240 88312907 460635713 604713043 870473986 754717550 133371093 830482348 816631967 120814175 92033544 967504449 683064436 84283646 151464907 218922303 223500958 914511235 470967163 647014401 122676144 191627789 255386664 472998316 99196154 251023587 290063652 928509356 763791233 959992467 379693042 507429984 183961449 662245524 796355790 732280766 520219757 785824189 839817151 871967905 447317941 429271179 894472865 493911731 790030886 720934577 411720461 372668986 580408814 501233237 919852798 230873604 774841087 380125955 426232235 437195406 335555823 901636002 943685946 242673173 706601973 375317745 543084439 554522641 25734544 845586741 277359328 38420351 458274424 284905905 840444347 420142110 411999493 206647261 191609435 121019236 677801166 961792946 50033404 622719184 635569358 656557343 153894027 316707416 882345858 749773840 819783797 677409821 86019442 782202906 336774426 459786351 435315735 680716752 267746176 327023115 15711408 624191290 453024149 897248582 71501315 139590352 455858421 275297599 631942724 906349161 848011711 302338727 597786292 413393824 379615884 767908102 638766136 471819152 504094472 539971661 492985988 873065055 607374379 502923370 499357702 69914967 59509108 318700308 101105793 128481631 217114174 948138568 168362353 66425109 358643291 256074275 708168803 861088458 976130088 644718058 913340569 842122866 909605826 164778527 283010951 306546861 205803454 203820826 27353234 954219485 527528615 876584949 842401812 85424303 764488928 763497229 247550325 803346296 323318251 841505135 986272857 148080881 512861241 559983615 781163390 206355440 597497133 182862465 116392124 24324505 591905207 747903767 356765808 817630171 149520724 825118906 908613441 411321178 334227575 779075429 662012538 406238333 456040561 608083126 550823974 421452773 238094871 825195626 197869001 455871283 443214856 708485313 820955180 140851390 782484175 332690923 567747668 714991346 659068151 395391944 828745522 312151965 903859756 570645741 112983584 328369491 910914036 659845887 563899746 284368156 145716986 909846212 335902966 915414533 318916861 421814086 656801588 782401607 209618630 810462532 833114725 693963000 410381085 538373767 636127913 797421994 799316980 951306437 193316391 293933902 172857836 979757291 373632984 615211899 958236903 330668881 909758900 678029408 818867041 162840003 79262279 471413143 689213190 336977098 950708640 889070927 817445444 899491827 769213221 495094067 587506410 359283384 646291102 298180951 631943924 61437680 501828229 102716114 759004698 290467707 42800005 489458544 962647546 284873441 458538019 266626297 617335009 690988122 85936525 924818631 399218067 655654661 191688831 41730048 10221424 129576559 504180626 853462839 84031333 851132949 596490819 673373078 412911361 409409707 109509068 646490303 817229964 282481128 539824055 482174938 102565381 414290403 585932326 908098159 209338860 737403870 183370374 59127996 882855811 131804916 943132628 147978168 697848912 845948453 395153942 656161605 514389854 661565482 602534821 769797335 788466372 920456169 82722295 380028136 40419252 617143257 896774281 583658242 181727916 353815129 405359288 562112994 472377823 882702145 195099667 37716439 699659861 531599355 511041433 942634777 271019540 843560071 324105036 608290394 720681642 111859825 755096196 986045284 199313914 592502707 321139269 78054064 347418159 902559642 284938485 461854417 111712130 28297134 205874300 154975853 804499209 412867454 238082046 371705212 867058864 62935358 722208133 270003204 963422347 822812674 895579972 770947072 598597773 680783923 310747005 647884805 290795330 423717154 748517133 59198041 379742468 166997152 945732966 841552845 536338887 274254790 963331245 40093531 933484178 372995527 86023999 708197838 83522817 197790445 742351842 728712738 554544840 347818851 128633185 403011330 459338703 209904651 495275525 761627170 54169065 886126342 985954959 406810519 602711007 223621441 596247049 209547061 909192601 119857188 331762412 243819363 79258276 235235335 987123338 907187792 966240992 682026999 67308888 593019720 921537491 845521874 688499594 728412303 756390875 406650514 357546772 270650205 642553261 843757076 472647620 530636032 500107729 601453707 20292975 502724105 744128481 413801362 695152575 880917165 572955734 692334301 181506243 243949518 378092554 600274418 14051906 61799810 684714940 34187863 947375768 184890459 614837181 893690074 789992924 257027171 533783849 627923691 942574806 149877041 848296775 521158905 348607892 423293246 578767883 259797707 145562239 117086275 446394738 520792789 256962272 328590100 492146881 570886118 110774868 854605182 228696526 747201322 902879490 649740490 143031208 677818386 217532105 794163243 236033603 315500258 153882722 190533832 702143522 980006594 595360743 217094269 887619459 205016659 244439163 921690596 957619307 12793620 832215166 988607393 277594932 941098717 481426689 874669017 544230984 775313337 293870016 512211628 483864479 258605886 338046820 896637197 591436888 681832619 566130498 933693842 772502110 562395192 393184392 814941149 324840590 888328659 992105458 329290147 676081192 611013590 921174214 531857598 228105002 480202436 303356801 12884268 856502661 482170171 124761525 953531902 831670180 657609578 692661834 825442655 543266258 694086189 303149115 776219077 259210477 728449987 856999253 67613035 13672128 365533760 663583739 230205801 728418189 325657433 614733673 740001642 367726384 646447401 38130500 874694917 276980540 443705761 564606179 683771645 456405980 252112307 795367399 43451297 960665700 196678409 362018101 142056650 890735307 500834644 195922841 916758111 229307085 289738786 742650971 328355489 747061071 804622688 900066108 339239354 461683565 575887003 595725048 365985987 240472719 646504424 278378142 729346296 854153549 113779087 305829105 331809381 495295195 288844692 483705950 491558806 850259829 24745847 252417540 170128205 618264153 229839695 829390834 401814277 701939609 544282433 467942557 835719709 33044405 290054117 953657689 851800623 154759799 112490567 721471139 205252172 392627770 970183727 500390026 432584588 68950071 696900139 573106327 336994526 219709013 542225440 442188391 393286651 869737780 893809713 187499947 855591130 780861112 847344572 67882645 52820613 933508468 41413448 313349060 471972872 482628329 137659380 964279408 542763966 130635609 537107901 155028794 285168423 43179364 101383708 409544497 838424666 317675655 746174890 225043039 877087140 458718785 89430722 345781407 294266826 834401728 8792047 753809450 631762713 651795405 74609810 561386886 449468864 803903025 232489956 772701291 696192008 410927208 807521692 261499520 86355704 850430767 218748643 508513269 822436403 866347154 843462684 272983048 107356467 894293076 522298136 448324446 622852925 126539326 60062209 226780039 739964865 766494517 965123681 521860290 349153741 406228584 352366613 749171562 58645661 383279648 928920827 965528697 177394721 733545164 677303098 898241044 309783295 170724900 658468389 178732113 287675538 29852637 141735581 966348696 796245353 885211283 214882542 319470732 187060635 470921033 583435569 775950652 84504018 159108505 275 563 269 768 282 986 699 832 101 990 148 994 190 657 418 427 507 789 436 894 120 385 284 799 163 810 267 937 219 796 12 715 185 724 91 851 674 974 568 783 52 693 310 829 593 924 17 168 31 975 106 987 439 818 313 366 88 895 38 775 57 879 398 921 179 951 162 903 2 576 26 530 57 815 40 882 199 526 96 112 246 856 537 944 107 854 284 827 31 207 668 731 93 623 393 436 379 987 180 686 109 937 241 861 384 892 160 695 319 863 216 928 287 792 118 985 117 678 15 666 232 581 123 351 1 649 39 966 35 536 311 988 43 549 213 959 304 765 59 158 157 183 168 824 252 943 56 603 58 819 314 965 227 989 287 853 877 985 12 767 23 738 299 890 404 844 242 427 679 903 564 901 224 732 23 955 235 659 356 638 427 940 146 806 949 991 272 821 67 760 291 974 30 642 95 862 334 972 276 596 307 979 269 800 229 948 1 931 20 661 85 957 470 919 15 496 35 704 219 892 107 799 116 691 623 647 258 823 83 353 409 899 202 944 294 910 312 964 2 628 622 702 181 445 390 967 326 856 43 833 113 657 32 487 553 843 80 843 70 583 373 910 345 938 252 863 326 882 59 682 31 660 310 830 18 573 201 512 253 780 179 690 457 978 40 62 13 774 277 977 575 708 229 733 47 913 45 723 175 886 86 360 741 873 241 812 325 884 56 732 272 887 124 895 202 893 317 880 423 925 319 860 197 792 24 821 192 977 31 840 37 811 153 368 42 903 914 980 117 913 111 537 84 484 14 41 676 677 180 822 445 657 439 545 875 934 271 933 142 887 522 996 708 789 324 721 504 974 431 514 843 847 257 733 216 790 272 884 232 970 35 848 120 484 56 433 873 943 433 964 177 780 146 994 153 914 189 786 163 789 77 946 88 825 336 840 22 882 70 667 140 703 313 971 302 893 386 971 26 686 535 845 528 754 267 489 949 992 205 917 294 839 140 986 67 575 640 982 103 821 6 944 296 989 183 622 385 538 305 959 61 882 44 668 10 707 186 236 621 781 37 765 55 787 124 954 117 630 112 943 501 582 193 783 82 620 275 797 154 974 217 518 8 52 135 719 79 976 166 951 406 950 69 669 274 900 33 630 46 999 557 935 363 375 336 660 739 871 143 438 343 895 638 980 199 271 47 568 6 533 19 841 176 950 283 498 254 413 851 964 471 515 236 355 14 983 36 755 181 985 457 906 187 709 252 783 461 991 152 762 375 927 105 832 43 957 105 794 198 927 42 674 254 862 238 860 140 983 281 977 368 721 608 802 60 872 266 863 213 986 388 942 153 661 291 535 101 306 49 665 137 741 57 651 104 875 662 768 215 729 457 709 96 901 355 984 165 855 174 826 103 974 223 832 174 752 69 650 37 817 274 342 432 503 442 977 127 944 66 717 172 725 390 495 91 998 823 897 500 580 152 558 32 205 87 605 398 945 23 717 73 977 35 698 121 962 654 701 701 969 79 655 64 834 39 853 4 933 56 894 263 278 253 952 184 800 689 794 186 408 47 887 61 923 328 378 132 357 97 260 205 324 177 828 439 944 100 890 62 600 122 978 93 834 276 893 84 957 784 806 304 438 61 950 41 911 21 36 179 585 329 979 16 746 239 478 37 638 438 910 658 788 289 876 332 774 129 733 2 599 87 326 229 353 697 928 227 244 562 717 314 383 317 708 336 757 124 995 39 622 248 843 368 997 18 557 26 546 801 839 576 579 242 778 162 702 51 98 270 671 204 912 295 912 221 826 26 935 51 833 77 663 682 754 257 388 232 879 102 601 206 819 245 955 429 501 76 235 545 960 370 535 665 833 113 290 276 802 66 588 716 912 89 953 667 885 127 302 33 638 495 688 20 545 213 682 301 969 67 663 23 608 156 708 184 780 436 999 554 577 239 661 120 995 45 653 630 720 90 489 668 981 514 891 104 968 334 904 14 708 118 216 228 767 428 935 330 972 246 455 92 902 93 260 485 656 115 832 598 712 601 872 113 875 76 918 127 919 120 819 120 434 396 518 40 676 132 870 175 692 17 919 168 685 271 775 25 500 694 891 389 903 121 956 361 862 10 832 634 892 144 286 573 614 153 898 875 962 116 817 162 896 188 743 208 850 96 609 636 755 290 864 349 999 115 684 47 614 264 770 136 364 253 263 20 614 276 907 277 800 162 961 549 895 459 587 404 518 680 799 92 816 302 514 274 792 266 880 61 829 414 928 54 806 34 594 60 719 228 990 141 663 179 704 48 927 170 679 48 791 45 708 177 600 450 503 42 710 388 890 23 898 135 692 180 824 6 173 434 473 131 351 338 951 378 989 170 687 623 906 121 946 4 970 728 971 286 622 218 879 27 589 72 827 127 848 22 858 8 831 302 967 188 781 232 925 499 853 234 760 344 674 332 942 125 129 214 858 258 995 45 840 89 869 249 771 78 621 642 890 58 552 10 792 3 253 338 341 107 373 23 67 151 152 375 896 146 677 374 925 20 294 110 114 687 791 28 768 338 709 695 818 524 570 245 750 276 947 265 884 19 736 428 953 101 388 236 816 309 822 292 797 14 597 451 538 149 854 694 874 309 370 578 786 594 634 680 733 200 953 127 796 35 921 346 769 72 220 330 778 91 697 474 637 682 867 283 564 39 894 557 928 13 733 748 959 646 673 84 629 62 857 150 990 82 666 391 563 132 679 114 638 124 986 352 462 236 519 328 861 408 464 114 924 143 643 252 954 231 892 819 903 180 505 66 705 9 618 112 142 61 115 118 824 193 791 153 913 211 814 613 655 443 553 320 877 100 869 170 861 215 739 336 713 533 851 79 963 291 846 172 306 377 485 361 972 36 584 463 631 234 751 347 545 113 655 173 980 381 737 66 823 215 770 107 776 784 901 280 512 74 247 77 762 442 959 21 790 82 925 38 839 716 975 468 979 140 757 717 782 548 691 167 884 386 952 386 967 9 702 33 828 16 590 317 740 367 545 62 741 62 744 372 589 560 731 349 926 576 995 211 243 46 778 113 935 127 678 110 707 36 983 61 589 338 860 143 816 240 761 759 995 392 492 45 575 16 559 101 953 222 777 516 884 737 839 197 898 65 798 628 899 515 781 622 698 655 886 321 678 635 680 333 514 362 614 11 763 164 878 302 802 103 762 241 767 2 802 68 638 126 980 159 946 32 863 349 915 239 756 125 888 82 703 20 798 208 763 59 724 374 925 33 847 322 962 18 992 388 910 6 752 22 803 120 817 622 999 271 801 51 872 217 417 152 873 294 939 270 834 137 313 2 507 229 735 116 647 283 884 247 982 105 523 517 691 445 992 70 743 146 669 36 965 7 823 68 909 839 978 9 826 405 969 43 772 15 613 177 896 110 672 147 648 578 858 691 831 30 881 171 258 67 114 247 540 205 872 269 976 680 707 222 410 230 741 87 993 252 980 283 793 156 875 8 738 146 959 250 764 189 863 387 992 9 781 363 956 102 569 891 912 87 749 449 855 4 213 41 611 16 602 183 788 286 787 35 911 271 983 26 698 117 893 51 550 194 877 201 992 33 859 394 895 221 395 579 606 572 659 792 863 57 663 280 865 139 792 204 873 578 717 204 840 192 427 301 353 537 802 436 925 445 945 388 393 811 880 296 848 636 873 454 569 20 530 10 765 15 586 148 659 150 529 140 542 620 869 20 648 294 921 81 879 284 789 26 947 97 496 206 492 99 521 635 854 510 896 653 721 8 813 300 451 382 773 202 643 833 867 525 731 435 765 252 854 327 981 326 926 103 609 397 988 211 974 80 755 132 817 172 718 798 846 230 982 636 813 463 609 62 827 236 739 184 189 548 648 48 976 122 655 51 966 193 976 419 941 10 748 327 933 226 992 144 651 49 726 46 577 120 938 126 856 261 509 161 796 432 690 472 474 470 762 70 565 221 952 151 447 71 667 429 709 550 842 23 229 56 548 21 569 222 852 192 458 363 501 235 926 206 853 217 875 418 798 681 829 745 809 277 791 25 913 296 700 634 713 212 339 129 891 23 901 194 896 505 831 495 913 7 91 185 315 602 638 230 251 205 809 162 847 307 803 225 892 30 947 14 880 97 910 164 915 46 578 48 633 123 821 381 948 18 656 267 423 143 273 201 677 25 578 666 793 475 704 54 563 420 941 248 778 354 912 49 837 350 877 34 859 22 598 99 778 63 449 13 746 121 789 175 943 1 432 489 747 229 435 681 931 705 789 723 823 184 743 60 656 161 684 347 861 22 726 81 619 19 834 214 703 781 928 61 127 306 499 325 886 800 923 654 718 205 957 249 948 127 711 228 526 458 964 247 935 308 353 654 918 20 539 148 707 229 361 479 827 551 637 276 431 220 396 257 576 179 720 144 906 53 844 123 635 189 800 73 681 867 978 38 42 873 904 173 272 201 706 179 918 51 771 51 700 732 901 467 586 171 807 226 759 456 857 82 862 173 799 380 716 280 783 219 935 164 725 156 952 715 814 161 900 358 806 376 927 10 945 159 827 163 722 346 986 621 875 557 902 199 329 519 582 527 992 196 440 23 876 90 725 277 685 267 982 219 746 192 971 56 742 153 732 118 655 261 941 635 768 347 445 123 418 451 904 286 792 18 914 14 991 218 993 506 567 473 748 367 974 207 953 225 934 194 944 154 981 305 828 412 535 776 969 313 878 298 905 119 670 626 703 577 843 260 328 257 490 30 370 114 625 176 874 37 446 56 414 219 739 120 786 114 957 25 829 51 318 155 173 79 166 118 367 15 977 58 854 249 820 4 565 485 991 235 895 695 977 80 667 535 732 94 935 47 248 102 170 39 806 17 643 34 162 317 984 279 645 32 667 165 189 58 742 196 908 318 979 184 918 27 600 75 473 84 114 1 824 522 942 162 887 24 555 64 565 76 869 468 849 353 687 257 900 304 969 229 297 60 185 303 968 371 935 43 744 376 939 86 823 56 570 63 690 354 941 494 999 200 855 342 955 29 865 362 967 10 979 15 627 80 978 444 757 321 332 343 993 170 793 302 942 111 845 186 978 320 478 176 747 13 806 479 541 138 794 828 936 421 995 17 808 80 669 135 155 499 972 114 438 341 994 94 897 51 612 374 513 704 950 71 991 111 189 115 797 17 582 395 898 758 774 56 826 234 794 226 980 45 876 311 888 133 640 64 834 112 686 255 811 188 799 178 496 466 534 14 707 146 855 696 748 353 843 476 995 82 610 394 644 36 853 52 582 330 839 167 862 170 559 166 807 43 837 93 670 172 872 102 763 432 464 797 975 223 880 200 955 138 638 209 961 124 395 14 523 264 890 110 983 257 931 59 608 252 978 97 978 18 844 137 940 58 912 320 610 267 694 110 778 291 795 259 822 160 942 296 943 676 886 307 929 22 744 26 972 281 854 455 563 601 622 205 751 4 611 206 891 413 971 91 124 173 806 772 964 582 595 180 916 80 759 2 707 93 870 15 559 153 1000 129 997 219 812 529 641 487 968 43 608 9 661 176 989 85 863 865 937 223 824 29 844 105 841 161 850 120 835 122 914 38 604 506 526 683 949 252 429 456 971 70 576 134 831 115 668 295 1000 436 797 387 909 36 884 31 880 45 364 936 977 55 888 48 813 120 750 172 863 369 997 90 952 301 816 292 903 159 555 805 948 22 305 163 545 145 749 57 820 5 684 150 763 330 883 189 911 28 651 193 895 271 812 73 1000 76 639 84 822 266 432 631 734 421 449 728 809 3 794 408 944 397 504 107 236 6 193 118 289 173 479 110 167 453 985 173 872 322 809 852 881 69 798 54 627 150 432 47 957 34 703 136 722 703 945 76 894 241 827 45 716 333 866 292 852 226 858 221 879 660 786 15 535 18 992 393 713 432 937 114 831 220 303 108 327 31 582 394 946 259 772 40 543 231 245 877 991 296 631 204 521 320 846 383 950 303 930 106 901 50 670 202 877 835 840 139 845 66 975 362 964 179 740 276 811 167 200 498 888 498 517 65 313 273 423 860 931 456 695 166 493 452 975 262 933 90 696 32 666 155 908 16 606 505 897 96 941 736 918 470 562 10 803 25 603 152 551 58 224 63 776 53 720 194 758 124 701 43 667 173 727 286 981 195 830 103 932 239 837 485 991 256 518 124 711 28 822 506 730 25 643 86 413 256 735 111 889 38 870 415 537 417 433 609 711 91 263 179 931 221 819 637 998 128 813 253 814 71 967 554 593 116 992 46 707 69 995 375 677 329 657 130 425 557 865 349 852 85 879 289 536 496 909 205 718 8 910 795 809 371 637 225 778 1 636 106 663 769 899 120 877 184 807 145 906 142 964 165 878 318 990 297 983 296 901 111 911 91 648 321 999 100 774 24 842 24 848 168 860 91 748 734 896 353 909 135 955 149 942 264 899 175 974 40 925 620 710 6 807 215 846 220 884 97 668 25 693 264 800 130 514 381 604 258 885 71 759 218 826 178 790 17 936 7 934 83 779 241 808 148 170 687 916 180 864 54 272 356 985 76 820 215 934 369 923 15 713 338 982 147 820 109 698 81 793 45 800 174 776 37 1000 33 783 121 713 57 155 454 585 320 976 51 176 302 567 307 584 240 986 206 966 853 943 205 683 737 992 388 964 415 590 444 877 492 650 583 836 535 700 734 927 132 594 137 214 108 697 72 996 673 903 37 934 119 692 442 982 407 954 371 890 314 536 240 283 45 721 132 811 152 238 160 847 135 663 404 911 688 774 259 519 10 735 355 908 133 979 656 789 265 691 84 349 5 569 30 657 616 961 170 541 381 883 20 661 777 998 717 868 46 191 234 777 127 899 139 656 11 547 88 753 192 714 65 855 608 943 64 302 110 439 594 883 112 819 72 618 545 603 18 548 270 322 105 505 423 585 397 761 98 776 90 284 124 735 87 668 222 745 199 801 182 870 338 587 38 224 273 533 237 649 98 644 62 808 122 721 363 881 378 993 233 753 121 814 120 865 342 352 284 890 183 952 183 929 100 656 76 716 205 508 486 909 738 977 175 957 234 982 290 908 174 726 201 933 209 912 212 891 10 798 121 145 160 432 617 893 465 752 701 819 350 417 231 736 751 937 185 820 79 909 376 897 52 649 243 759 68 907 119 805 196 785 299 807 102 792 46 198 316 606 109 723 533 946 144 784 241 513 711 898 300 687 52 614 117 698 246 807 1 874 253 826 304 894 288 491 118 357 351 885 70 823 198 707 244 938 518 781 508 745 75 702 92 600 65 640 179 778 259 847 169 712 777 911 43 542 115 649 174 882 438 958 158 947 46 998 153 739 524 766 419 460 24 664 121 787 403 702 746 936 73 632 100 748 277 993 445 959 160 403 338 530 517 860 4 963 201 280 19 866 210 877 71 745 154 767 165 956 29 899 218 900 686 960 244 608 344 885 367 670 92 606 1 937 175 905 163 843 201 765 62 980 102 680 174 933 832 847 643 795 199 201 81 601 332 942 192 964 125 991 130 777 291 868 81 792 20 106 814 844 151 818 120 868 261 682 39 413 161 994 7 910 202 872 191 897 4 355 726 871 337 402 644 918 250 791 266 804 432 759 103 415 55 791 45 863 198 788 64 783 426 795 410 980 13 520 181 810 37 778 209 843 61 311 591 933 96 868 1 711 640 789 137 391 121 652 163 855 132 702 184 868 406 531 131 964 290 652 295 845 700 885 233 464 219 892 109 666 186 995 32 582 404 520 517 805 646 705 117 336 24 870 27 837 7 857 71 225 332 432 521 562 446 730 386 912 406 943 78 717 249 914 106 609 434 939 220 255 67 698 219 763 754 851 86 289 184 270 680 940 12 535 176 710 386 729 233 365 15 839 205 916 15 829 51 695 70 594 225 875 340 998 160 735 345 879 67 940 330 971 250 792 970 984 78 150 242 834 100 783 69 984 222 819 639 891 100 633 530 558 204 491 104 605 452 994 230 834 187 690 92 630 823 926 415 686 439 618 50 735 199 720 158 743 404 471 139 942 74 595 148 168 272 561 296 349 435 483 3 807 63 808 1 730 158 725 154 878 202 813 151 696 123 737 68 217 22 63 1 632 114 834 30 699 32 553 165 905 38 951 372 710 207 353 137 766 208 835 309 520 46 59 266 375 79 559 292 797 167 891 133 806 257 761 85 978 86 847 310 883 149 944 181 703 364 996 162 719 159 794 147 962 178 738 62 943 53 718 22 877 186 701 49 362 44 594 729 895 623 897 185 805 226 963 90 909 232 932 898 985 213 721 244 912 275 971 75 860 472 995 286 324 8 396 158 904 309 988 604 996 691 740 86 848 176 970 89 872 160 705 170 758 290 910 369 887 211 914 250 779 47 990 116 849 290 997 340 916 72 796 29 447 400 866 167 806 386 912 54 678 171 807 48 916 66 928 213 984 225 892 43 970 451 984 202 908 80 811 65 851 1 750 226 972 4 833 277 752 142 893 338 782 238 419 271 831 40 920 262 947 180 977 190 966 116 998 151 987 145 806 171 992 74 771 410 959 42 936 82 961 401 981 18 790 182 852 48 466 705 962 749 826 678 821 481 553 360 638 157 687 146 957 22 980 225 885 103 708 223 832 159 884 201 950 9 272 241 543 294 526 395 628 355 546 63 808 286 915 21 651 361 996 412 574 536 823 304 460 96 950 123 816 13 797 349 815 391 906 147 924 269 834 117 794 91 916 78 617 299 552 258 941 378 933 295 801 228 917 480 976 15 697 401 844 164 788 345 967 341 417 178 395 36 672 36 770 401 651 853 870 17 764 212 768 172 960 189 821 232 740 193 872 149 946 164 874 111 622 246 858 128 974 52 734 546 901 388 864 54 499 936 979 585 647 159 911 433 957 17 890 325 836 134 877 281 794 273 829 147 800 326 665 367 871 131 863 335 881 223 880 179 181 355 931 556 665 506 645 22 616 198 800 138 689 118 798 11 731 381 924 124 783 161 843 435 524 472 512 200 763 164 748 295 479 554 822 114 517 37 241 18 879 142 781