3005 994
466609 497107 980267 181023 295275 129102 706586 149195 748088 202635 978263 807351 496045 381116 358402 273259 142035 171719 231426 117452 92942 563627 894038 141730 554655 400504 646882 528368 572609 247267 35858 456655 605254 480922 785493 479093 213056 733819 999061 523418 742235 806200 21572 304523 474804 388110 798322 723344 907785 485391 305853 347244 133474 827883 70722 844222 772111 703597 254609 573665 765107 645924 648093 979908 242423 719637 444127 568538 163483 713711 369148 941416 714811 4588 582599 603767 11230 234686 482622 747629 633266 731808 970814 826976 295920 314448 154831 992998 958124 283439 525943 61696 285923 578305 800867 999216 21251 833457 563343 689504 12092 87156 42116 213038 456350 801728 797904 139609 652205 755621 996338 403223 86702 42886 24089 480736 792181 141255 387741 882327 658507 284438 404344 136465 616214 629619 199041 188805 308097 961817 956884 733195 1967 821196 239066 955158 218550 763418 460042 243010 207850 356901 580920 748968 607514 130245 390995 876936 365670 159700 97974 131998 981544 721077 907506 595987 363760 640404 69622 931808 245236 870802 541106 837813 602359 741984 914632 387199 599155 224001 186592 76655 16960 69891 88142 537296 864836 547850 361578 404237 452959 660773 485184 780582 430833 877182 511200 514162 175089 730719 153421 853638 63068 20321 348649 153623 492429 889592 625512 228178 476949 153044 241591 257387 215196 23362 705306 93583 863144 333545 708118 182978 177235 877379 147331 235564 207988 869246 104354 605244 478733 740550 945167 290149 48559 411970 353552 147455 372253 186361 345358 347245 415918 197647 242864 339679 162892 869792 816112 44398 513072 18274 760238 900028 333652 559389 582276 448779 168019 397609 459117 711036 408068 704544 568900 735648 345303 806021 462805 286703 599868 571105 607973 564533 328704 815481 240862 115595 97572 353410 99894 193429 71402 840507 110495 596939 694979 754129 651628 998344 80124 110032 128432 247020 402713 167551 17876 908059 490128 424163 509220 839316 138966 178871 825260 591654 959496 550020 911133 474645 495733 413878 71241 853988 604078 155874 115953 5521 284232 574404 446201 744294 985082 570729 818440 118510 142615 2419 290016 144151 231685 778870 348199 692515 309531 805338 43636 611193 204364 746403 503273 231021 708007 798132 326468 121596 26348 121378 935895 381400 615752 120476 107927 957560 581284 85152 70248 99501 411409 141791 785048 879076 918905 27834 208315 745638 20332 519837 843709 796460 85858 975442 403538 243392 750414 560386 872003 102521 981734 873134 938915 635518 373526 214673 108951 318944 163319 507011 996999 936919 735752 927268 90299 403182 748062 457535 249844 277694 461900 139127 297964 100580 81140 822636 389275 829257 342792 477025 371649 678682 490603 921654 145974 456096 963108 613103 714405 393242 124333 889397 142967 241111 210623 349733 432975 403795 404223 636611 681886 641300 276020 315377 588629 964160 885328 902103 371565 734873 522167 255292 3365 477557 476275 843603 640720 288832 105261 167442 308019 451415 83840 307591 663215 880013 73463 527748 838054 157156 908696 117815 51296 515006 645931 308855 134253 496643 95181 770025 982265 747931 816682 999067 970295 909337 536131 667955 934454 634627 868538 997102 786060 608255 737030 585823 511333 434466 702245 239329 669588 14076 67079 605340 240113 283769 957352 886422 450529 58242 380398 494726 952882 837318 830235 565661 159941 471035 137656 753442 1598 304581 322688 14117 965737 399297 748870 903778 357133 159583 203855 956821 749736 601627 283480 25883 976857 348886 828681 922431 673963 153391 211301 89193 701968 943466 488728 792000 43259 727625 381637 875674 695138 915745 140868 954309 591619 288693 67972 321745 296916 260814 155147 183300 575674 460593 986530 541169 719992 607807 940781 606843 930466 290262 99187 841082 966160 985697 341507 747971 477707 317009 845605 452127 542097 825368 433533 872043 153026 302407 461330 102999 210887 52295 189868 452598 575776 421446 891999 949555 437118 282441 260066 421887 523690 532902 905441 944883 774212 845659 652523 933584 419694 338134 967292 404715 630617 570579 551256 870375 447351 323295 120024 704707 207200 781300 534018 252130 774123 21908 671249 819019 130448 608626 767164 275314 56 801841 940154 145267 97093 681641 953981 281159 19102 612879 436414 664974 790717 81837 592602 763198 848408 58343 726648 533896 262741 549619 480711 621955 175810 546047 638224 386642 450895 918498 138209 755519 85105 864120 846322 471949 190578 822091 890413 40231 12620 105738 295626 347631 468014 144233 912101 210657 238256 507397 777461 144828 446721 288908 94311 807172 614771 153287 80135 97112 208885 703551 85829 481749 1 824339 218935 25387 783089 152148 740263 581854 818449 801034 286681 944884 482622 202576 591050 703566 510405 755214 35641 916644 919156 508086 782781 821165 602189 942099 646712 737546 342516 236181 784963 962059 102928 667367 168863 924353 455005 583282 508563 457931 427094 592484 216023 122061 280168 408692 983590 839089 803896 467105 2867 828680 854425 183586 671553 428270 251890 887744 901810 75298 671569 824371 457117 268790 878055 362716 349508 735471 739214 717313 883911 790551 48600 606552 842884 533968 212271 538003 536711 411377 251506 964355 554833 361783 213818 320245 888006 757709 823573 93725 890474 863178 967106 354081 879428 338959 586756 821036 94478 273781 949189 318012 624053 944931 106895 468691 512673 614718 700189 107721 472024 946981 203608 465549 336408 933536 238302 418937 750050 412071 830394 896114 836139 411987 981652 836461 659659 465615 366637 168282 677015 129410 972764 852544 200742 746141 931748 510043 524493 474658 252767 85705 868444 745369 320411 716423 544467 909314 582987 779758 63676 46699 43750 468441 147357 56681 382404 15797 51719 885394 44664 712967 415580 752598 862790 790775 90325 718134 439755 384120 711932 60086 223783 962256 283046 425970 83898 435347 221659 81679 210868 61611 785140 66497 642198 500699 356125 372403 500361 238206 156365 111128 733496 906082 742143 337013 229584 63217 218892 496415 916176 150827 746231 975049 331509 532908 297203 124046 746800 43541 893877 391015 707121 236716 176899 394085 526182 858863 870876 267754 181644 60439 654576 391768 84244 252845 76787 326801 794170 435879 60943 999539 31275 157672 749791 506142 124766 287145 58559 71138 688896 716062 951029 122422 588200 307838 143508 100539 988912 509545 812307 375601 175207 28391 825386 835629 311033 217930 384835 950465 138228 723132 599303 841478 395026 603613 523758 986639 471037 344718 981462 156092 937012 759982 999287 314017 908156 334640 269968 435192 381898 309858 371694 817491 430246 415602 129624 615108 505454 976055 315017 74644 268853 658617 346152 508715 524200 242235 593405 46026 341881 382677 555070 344139 139158 759563 299143 713834 535768 644403 94109 727465 618636 475805 767717 901626 771946 759401 665544 934135 380628 820352 461495 36727 824402 196808 697765 75240 171600 186820 384491 960532 532924 903329 425908 677633 173903 816319 189930 559800 115366 594601 631335 825794 234117 723878 924515 772044 470321 126455 714703 639705 238655 125758 228087 214009 995186 9706 436134 514016 977338 627129 188746 892971 515825 37441 943749 956995 766170 363155 323088 803032 733734 170018 24820 593976 719951 332758 731280 815175 372848 293595 428650 270162 463061 408658 414995 160545 14143 663666 407605 728484 211136 852893 919095 539530 558816 29391 148879 86289 901340 107147 952073 164584 459547 67592 162691 510573 325427 719036 496421 109518 780207 395093 720434 94287 420426 76974 225867 64605 766442 446894 620692 870224 258926 233965 733935 415806 849198 682776 878811 875669 104290 637587 208539 995806 814922 929808 699186 705801 429431 179390 555150 660821 139765 274776 183703 826156 487614 748641 626706 78820 149608 757148 708743 48256 713294 510448 448918 298190 449375 867849 519428 619829 992137 859247 497461 279491 95909 872385 319970 958329 493988 770725 890436 408449 170805 18785 876962 454244 112227 265396 515764 448928 874333 931030 125140 96452 100860 948976 754007 673859 227211 582839 828025 572558 766228 89145 871517 439514 656654 308074 395929 126505 424320 789640 56073 836249 657299 195967 530940 935659 864043 210155 373099 937327 946657 768997 532558 138369 340903 323562 118212 36327 288590 571305 778476 615852 443089 721224 441432 387203 473784 127789 828039 281037 912796 641302 732685 405711 280948 517934 105391 663840 143531 478025 101920 263630 343795 166200 151099 993067 51629 207942 844333 628410 462646 223263 759698 715352 154977 640962 862002 949955 735966 297347 406387 115180 441544 547150 536726 419402 166405 962899 923429 782930 769007 60672 144754 667018 467444 433513 881646 547080 974623 596509 493866 340490 834790 811648 220659 74753 782540 143248 156303 516540 975656 747198 384941 807376 583092 70230 199940 696697 150066 188104 362502 160030 472318 301003 321417 828645 12581 364879 954457 564176 498461 676145 156427 19063 716098 719384 48661 635299 590766 280973 149184 820654 641382 484243 848869 819108 364941 316624 734216 942809 100394 156156 73323 369225 447004 18019 653444 569203 779388 28366 628757 759038 221191 798577 133391 847844 585574 422944 236298 430120 303777 214563 955502 83558 922980 743699 591412 658176 967931 855455 414745 455842 377263 57760 60994 393314 388446 132290 980002 511898 68311 140971 699526 600182 319919 30164 86204 247108 73547 225953 867421 561856 689243 828031 239818 540999 717739 779822 360808 736554 60299 775247 791601 284487 193399 660154 279130 23534 770230 25689 998219 980033 396575 739527 534912 903836 875856 96019 613986 565729 9632 24349 483494 803873 117988 765221 797624 818389 150491 805512 621638 684142 657229 777211 698933 697111 864154 848815 601081 544320 306961 82809 411265 112797 264199 570911 250974 976081 299941 84649 653945 107462 676099 339759 527582 973549 547135 409665 915601 894750 396309 236934 79687 924831 771042 711158 718586 55865 878711 863798 146099 150592 965201 156390 701798 576611 497695 90083 774678 66306 409753 712079 150099 254484 330455 426889 105901 897100 245041 415060 277793 191954 566027 174605 825036 911982 574096 595144 600997 444642 799399 581049 867792 672397 466009 204621 406580 844522 949480 668737 43854 131583 923070 96 24962 351894 453111 69492 105501 380833 390118 352416 381472 936104 728927 457037 983933 505690 23043 793454 435218 576660 65857 212308 264337 242064 577497 483794 96457 763149 242206 314421 800840 872443 345186 697904 859648 159957 251332 615336 533561 689803 699938 951525 345097 843660 996215 181596 609232 487965 939675 732363 986596 739385 165738 772391 7561 539819 278248 887940 475103 7439 86433 103227 352846 287020 421164 66351 665969 806011 666011 466340 142398 994997 308257 533111 413710 841407 50084 214596 709909 778373 402922 219360 443646 895329 235806 394097 915739 46599 491904 527662 987369 892080 384323 260211 875279 833934 788146 946167 850996 324705 718120 36606 525120 241961 671080 991134 232257 408067 794010 200545 459271 660263 492114 82009 931999 162052 4827 185817 918869 219526 320881 167416 861171 239527 789302 582463 332621 524912 770084 911642 4915 495131 455596 38987 778019 701050 987837 643946 138931 237714 373914 326310 797315 164441 754410 59124 132242 389671 290845 185405 935819 667050 427720 574683 134705 618475 369436 542035 901319 807549 930613 420557 554818 571056 787013 408594 925784 896282 53601 755365 287569 575498 233636 682227 854339 446896 491929 702143 995376 541624 863817 223477 460515 632301 732225 84905 290650 424354 425488 878403 520101 360413 606841 263538 721302 587168 485603 383308 490752 417239 950258 737816 10567 818719 908953 976476 159775 719278 596601 9089 835685 537653 142009 775409 438684 258837 602441 424936 676237 755349 242801 136653 656651 897038 26150 74581 343650 276613 962392 223713 913974 402894 921516 434674 290777 503276 207799 373485 840853 791076 950984 150523 17172 811185 463939 562457 656925 236899 20479 805013 483854 147359 927509 923048 376641 666070 537127 499479 813522 719630 918470 630313 623272 290746 781139 449533 429613 925848 775555 586785 499330 743605 202835 450417 799282 135301 502728 63736 953335 993363 694452 818018 46574 129169 167521 456101 495721 610338 39685 774308 254904 727878 227479 631474 456523 934332 704628 246884 114924 154920 398303 444626 60820 662328 313089 87182 88568 837726 245723 495321 235275 714091 204751 270090 833109 651116 228767 123648 148751 303257 777080 243678 441357 990618 456727 314974 536954 568675 593031 714860 121029 461826 21780 100796 221909 434965 660031 577412 655705 942468 375537 652159 582614 524368 944953 456710 83882 214454 655982 91935 725153 672176 646717 931681 767433 463228 787978 833098 511524 674782 936567 924086 701558 793711 659659 978996 93336 506212 172347 467031 992812 208490 418975 902096 816022 424069 702668 158413 673523 366383 683548 866064 165887 495060 666477 444912 132477 408914 52428 357160 714214 22374 31233 880327 896869 437965 607021 307682 343387 926944 378184 194883 923355 920534 833780 835397 785448 398920 431201 139137 471497 409651 525226 812140 486581 760749 192199 281599 327555 867099 479348 152030 233914 31684 419450 668459 729079 285931 35714 752714 358814 101291 584713 40237 254615 658343 589221 310112 493665 410919 923390 875780 595096 232263 308709 418994 762866 935348 650707 362317 648738 398831 758607 248599 605374 973035 68165 190699 525369 186870 208796 544800 3620 19325 444453 195033 762370 661240 394149 152626 654274 272201 786060 221228 519382 10361 710713 984024 133220 138159 710534 816766 414022 658545 327644 324447 531275 99084 935695 38046 57594 835939 352120 830458 16111 454106 415868 385641 115323 334828 175336 968168 778036 191830 35464 196729 942052 504231 943680 605370 879748 255334 578917 367032 517805 534349 143224 959933 877532 937697 776264 727853 209608 319780 338309 314352 76593 326575 73201 373340 850716 879284 622944 811113 647916 149936 352063 355069 995086 656612 84796 422527 351087 221848 102849 157015 640132 118981 752216 901225 546250 695021 181562 436139 557262 430690 797948 895387 927300 393027 291556 335278 789453 786400 141651 611935 75566 298783 14099 20462 194341 793742 591478 815719 255342 679485 4382 595250 520534 869427 607500 981481 615348 791620 332680 632435 501090 408551 325700 104305 762065 762810 288234 492145 147132 385021 382042 175689 271717 18840 654766 476572 161218 299558 757274 232634 932963 122621 887883 202216 585625 787308 844573 634576 838534 897591 2455 529722 298531 336851 462556 287510 345935 421314 775191 787287 342095 686703 828454 646661 653717 961444 636884 82021 805040 774537 402858 865134 983231 567849 939454 728103 561408 382598 669900 475167 955831 452737 806559 451923 364900 109164 970636 457107 106448 431997 995203 935507 928040 246265 696815 67383 782872 167346 563997 207222 190434 89639 111820 633612 944500 985970 437991 101505 9018 343246 678984 645392 531869 203051 941198 550301 145013 537695 354606 330093 773748 929671 807650 524277 225107 256449 627127 660686 188488 952937 567385 944379 698852 972407 145343 588218 999294 434797 603063 687125 778642 361122 425618 928991 889352 99793 191159 980563 779577 810809 370657 269081 973269 992367 544510 983028 770302 419778 459621 355203 362932 515306 874136 239005 814627 919071 37989 901153 223354 488394 188154 589314 836235 452395 521440 888019 130972 265401 310927 377839 692996 393477 649717 735202 727336 796340 315176 903544 988476 901352 365596 382710 895088 802952 996172 372427 412661 370235 460281 998719 695082 245328 147160 721399 225139 684981 992844 247076 368753 684532 611503 500760 718854 559163 249104 598579 357682 891407 696273 710643 581382 957971 118446 298176 592697 804579 235299 861206 309387 172646 443085 778048 789853 843072 302133 327681 585969 667730 972277 931918 365982 455171 665977 767709 66346 263944 574032 417437 715713 609020 932815 984861 638385 365661 501596 761257 673037 824623 159717 16324 668989 980722 170755 871020 58473 481019 927094 366460 504421 78246 492421 263093 119798 809667 74209 820673 241399 585790 736837 92692 858543 338329 266305 129147 735550 892169 576781 480785 874318 795731 267809 382458 8001 90110 378745 110722 194292 714116 446859 641795 32895 485410 451707 930674 816322 476302 135364 154068 247655 452393 858407 146047 352949 203018 399381 994008 213372 54464 434469 359873 29879 391311 725323 133221 630652 261616 577318 490869 191266 446028 846417 589972 736730 637951 589978 176731 531454 929881 620575 631120 383227 175870 699037 279163 994415 611630 240078 816008 917272 775225 810758 827800 415295 741071 819963 510033 380924 759252 971772 134231 499586 671683 729676 729343 583343 221598 329475 415993 423587 383883 369236 277011 320713 561155 53053 966886 751740 644384 219927 292195 274643 424502 991199 902661 794104 314732 885866 944852 826734 355028 983952 423818 750302 64536 691560 761335 221446 754991 988365 284381 757777 468432 91465 367072 106337 568332 380607 711185 357800 222976 215347 80381 225023 173625 97942 972404 677937 907460 438329 92501 660517 628369 563383 650503 947224 943715 276229 268133 434777 475353 731407 616090 652296 2392 291586 222351 713321 237448 696547 311427 758129 67359 484380 919966 740310 755243 174642 333035 442304 1000000 170146 260113 863663 968866 352820 711259 301515 131004 109296 63330 237058 344119 899513 11983 338862 858207 111070 182799 557436 158295 37904 945514 250945 393414 308839 376827 976107 189293 258049 133553 719576 188035 542360 305971 701064 238096 612440 484671 47510 53534 297635 407617 269922 662522 592806 57725 963883 353582 670042 972368 109421 245527 610455 251988 894019 43116 9544 74941 590723 515829 24667 985027 784256 850114 436654 141748 429607 795487 711214 969796 743109 652486 889430 115933 865105 17953 687584 670840 250520 352971 71543 567229 346628 994978 525961 994692 286127 383921 670048 34168 246756 353627 801914 889664 489408 479879 989455 908605 939698 546118 594445 238495 589341 54172 633348 848794 737944 410656 228783 886218 542222 409914 459854 368533 187445 757022 690367 513192 154961 651287 984446 466693 915474 123807 736413 113287 980411 688937 356260 769173 530888 947253 738975 487480 359491 150186 187045 400266 446862 560985 200104 858392 220281 585163 111293 910581 333840 549927 944485 821287 745552 165762 712555 197970 986930 732729 184665 667010 979627 463812 519247 933811 681554 144702 852111 969944 828272 257824 74363 331476 596172 800565 263371 432380 108657 737345 171055 745786 753244 215473 477034 359133 393495 146902 951555 216731 744045 961380 729244 540352 947336 266117 199999 733344 523194 794399 976361 438669 853206 590520 93374 258205 318192 965768 745015 633426 721556 704639 830582 879795 222027 596802 777376 99497 29254 668471 575755 452133 573708 179697 190351 447273 85069 533747 415357 432433 231289 165834 420608 355744 625812 217882 929958 24944 896822 307844 421848 304343 386764 289040 456901 320669 698167 261497 421826 332113 572297 370886 583975 823635 794444 36149 263398 147062 115106 786794 597768 510349 77116 141930 83548 443448 450342 473986 302741 997138 842020 591429 709394 410341 869559 699634 180479 498625 972544 997909 33121 243975 974759 721152 698372 326513 108937 827965 88793 433751 807838 633976 620424 816840 132184 439641 108054 774789 257402 466644 315490 813377 5769 127970 360299 953874 177018 545224 489265 271450 147633 551494 240892 386702 226588 340314 921082 221915 500165 281930 585926 858423 337922 277349 547763 884370 716385 855937 905399 784718 61727 692593 12364 721127 984890 150544 437969 720056 277667 657465 747645 656656 69973 978725 738849 845274 868840 140905 852088 677640 252881 813635 629520 978349 508382 620056 529011 542497 838926 833820 84020 887852 581538 713612 684654 997467 274328 84447 285586 582036 952819 68419 302821 941830 92289 892247 419006 764631 762127 354778 769561 645750 96710 249561 710260 209863 303593 783979 449956 710977 707601 509558 458639 710878 19824 529105 627597 688367 48379 880683 982354 416715 270037 87344 599135 781796 360196 812186 272625 112285 901648 969773 801889 206610 437275 560223 973945 76560 677839 272352 3800 392772 576121 228397 729602 549919 470198 334370 590603 489954 197054 742417 51042 192803 333194 700880 159033 518132 411902 907229 133589 575169 572736 65494 313772 893644 633587 280421 520045 655702 259981 151191 874448 327507 625607 320010 19118 86964 535377 895758 217752 648625 361371 342544 743822 769133 585109 442372 959156 269266 211710 643838 728584 622894 919789 954541 893979 466790 816497 752891 423819 201744 894758 918291 374888 944937 958338 999919 572695 939124 542821 327234 572766 818237 351826 46357 652805 357289 599137 867194 347281 855140 306172 569430 259813 854280 383723