2998 103
719789 385667 503327 690848 5817 824736 566534 909189 239674 187750 997354 12429 364402 505868 789253 575925 867456 934529 519623 156755 114907 979576 236865 748683 811123 182307 938264 955050 218006 209544 798583 186972 201735 662350 583505 474369 594274 254919 616181 705488 737382 927712 914904 492953 944775 642040 131865 679010 758936 51109 291836 331981 710387 930869 504971 860530 232332 780723 467901 578032 480599 983116 453596 505779 670914 345037 927860 434557 135065 212214 674112 131177 214244 914840 552521 611224 708564 180102 511069 676159 197789 7275 514886 947928 646796 381353 960209 561069 61043 234779 992424 217563 657159 738647 489646 142021 194430 65226 604840 606369 491163 264401 554637 671055 35827 274291 748782 404718 170155 359107 50988 872975 906133 12299 227611 998114 855792 823985 459831 550943 784232 920187 821014 741077 707588 946879 960624 417311 259571 710267 19974 442842 863169 3349 164110 448300 230931 183516 445726 716604 450839 212838 599725 987326 346812 306438 803110 536904 633796 829960 841739 30541 535128 729528 567021 352258 583021 182455 369774 429901 296479 929727 849563 139193 256107 967807 629790 613644 254787 715645 646063 670269 736857 528318 972059 774043 298766 505521 685984 477833 476707 394729 571158 301784 11777 221047 222396 666014 105843 887923 381551 382643 627449 111713 60187 90217 79104 527377 523204 164662 255032 526119 496225 906893 503063 525738 827039 555332 202717 901223 809376 898894 251541 15695 866246 143071 744032 618274 878734 100703 184787 696406 168832 293079 467118 613808 823397 10996 524949 148820 767453 183037 274933 476015 651979 894031 117451 58860 691378 445474 844668 133134 501676 404249 864122 885645 988765 448840 760330 775669 73749 848923 928519 447907 255575 959134 459459 181633 679527 797009 80334 996336 299388 579570 10048 836153 111152 917168 229922 455305 660403 252031 881158 511644 643572 884269 134168 765403 523314 161750 491385 664085 107495 437504 702679 657696 462687 803119 530747 5414 204739 125411 768436 341937 625899 252398 471070 150823 240245 971393 392559 565260 34786 244304 3542 723865 309696 763981 420122 587306 588255 106045 759304 284723 997609 931787 524181 352084 887894 211548 359610 438857 655985 694223 116488 15267 364777 697386 270012 224084 651514 972693 745109 90729 665492 737033 680054 398630 343020 856322 180899 108646 256767 197835 778005 817579 682756 647534 309091 216139 584166 360461 490783 107158 58142 736836 21035 295084 752296 239654 942084 919868 348208 173288 266803 957872 696644 738631 817943 717896 603954 734672 435346 919519 152663 624947 400575 345801 786156 375040 866786 260410 148153 800520 720990 321255 16032 822584 754029 157069 159287 212930 532366 293307 257205 563350 633392 895297 364209 265573 244012 658431 516960 628823 371965 502509 327498 998628 216011 452325 349962 366840 757979 875021 108811 320674 54185 875594 783703 749349 42762 937624 547971 134911 122350 319307 596355 956640 354608 600001 134117 75093 829608 505189 657565 160767 185298 831623 789749 702680 4726 932534 381675 482045 227852 902070 943969 269429 193959 280903 587528 403516 725116 868715 683583 185737 55689 94552 183862 598168 36068 896779 849903 611004 117102 780813 326251 23595 874357 2905 661377 541569 533796 976745 354049 743538 990341 948761 200786 13429 963064 75891 688618 461854 569224 905775 888129 323452 359582 870846 643512 596949 101111 337848 869702 896122 156230 602042 285358 336184 245642 17771 120104 619146 136511 345416 802791 454680 330843 864391 603681 29489 815568 26466 818663 938377 442127 474532 209919 909093 714697 178594 627830 278780 408655 771634 876381 222338 912274 117775 404398 388387 390768 449512 50677 296658 212434 362149 810338 326933 33696 156210 982549 813245 689119 978246 157418 655759 473468 872137 396174 897139 812865 337056 499615 406027 528416 215236 271431 925735 446339 756030 371943 39213 134857 143931 502770 133981 916914 186454 211072 321508 599315 110278 276639 15463 608603 943660 280114 205492 809715 370127 396790 526043 264502 372411 773393 13514 170387 411470 89515 546069 329670 282555 578167 246285 648794 752680 323477 49213 530722 767347 804837 166728 463201 94960 669024 339247 691511 539623 728250 366570 816389 456904 473312 873077 293436 748394 956878 477047 878884 702900 406342 141828 583686 526326 175179 783825 993094 589743 940631 581258 792021 39660 178454 598645 123465 884382 622540 766624 286851 300694 705804 809921 310001 446264 479343 608110 180463 615410 751336 631750 208990 16248 680118 40981 459436 700245 165899 514963 855767 863244 126196 213197 952459 289953 743798 601285 487924 110122 868533 683129 574623 349968 659429 772447 688633 131806 680231 419090 467091 909870 199801 181420 46565 440663 487060 989365 50367 688906 175648 674759 142313 192337 5577 721593 210810 418800 402660 184585 968348 608794 975329 146653 248206 16455 967359 730062 743174 215323 208295 767579 201742 519774 930642 571987 660545 196581 580667 74540 129284 766236 866113 405294 930179 441445 649127 652473 636251 341121 141014 804810 845364 956450 512715 206210 594482 938473 568454 111301 605705 924311 366354 600859 971140 576719 455716 584567 620094 792579 748903 776076 715240 870337 115430 73225 274398 993497 103874 781146 932370 707564 681224 650109 745988 459946 55532 318179 713466 199113 120733 644420 306646 826905 641180 794212 517360 713532 822449 377673 365445 528349 855590 575812 540134 67473 691184 106197 780800 829781 704520 9183 776488 473454 891659 449230 44051 619459 864018 235198 886689 101862 928824 785009 558539 964778 114200 697868 231110 674575 469432 762809 641595 301794 625280 22025 91845 759576 770922 467397 216670 920944 868185 705502 243246 530546 126442 830507 371138 376625 741712 753592 498590 616613 203486 239257 758517 30129 92337 146203 21936 586985 248147 725221 400539 957402 418145 404161 506318 172332 142996 945642 834545 56742 381670 894446 496136 302716 210026 325313 695899 261261 224880 411626 454557 521576 619550 339554 248373 920467 142579 651502 2249 755470 99782 747658 436011 177380 946032 422011 245930 8516 371230 518852 119499 358125 273954 738188 790010 236526 461314 777766 898299 665749 136121 319317 215089 759461 314828 14934 375560 972459 177551 551592 150421 461880 836782 74481 132373 87191 361978 692800 965345 874684 282922 777377 194133 526744 229141 735432 816923 837411 740701 897739 705425 268200 631939 666308 967895 343571 473264 98823 7946 814863 510911 299980 98375 61493 986559 921133 715937 751973 236706 915243 443883 971403 666001 648093 476453 143138 18135 497784 441281 665477 462862 120784 235954 315779 106085 715904 804356 716015 820758 648275 747258 229810 232949 773440 398154 241223 851741 982178 494202 440011 129869 950380 317430 262685 811962 541450 584527 515277 967796 977555 513662 582203 188956 80243 906976 14110 355114 416799 101547 334382 194348 642626 429695 19764 422231 527150 295835 527488 592838 300272 805177 490352 95650 611126 778378 392586 612360 376859 318700 38585 11282 222702 961505 198457 408378 527484 818488 874074 409123 987757 395177 794269 315952 307180 341925 905467 593538 647635 64556 954991 27712 545146 345439 408109 656657 125840 944644 523355 669112 499565 859268 126490 873110 201239 845697 924554 807055 652670 299221 100450 695147 281476 617858 296368 303561 217950 322352 804246 693370 566832 785299 564498 491176 921795 414630 663591 87178 199219 165370 577563 28910 627054 427906 208631 63828 1469 45119 940911 786177 298258 154433 597164 190201 816676 601805 917451 813056 924257 479867 425268 312296 939415 118349 957598 897372 378510 1000000 130079 923339 907012 563149 912645 868047 562657 469848 412627 674989 739263 600749 1892 479310 554838 265828 190992 264707 501736 678091 783519 695447 995729 520250 539749 349415 467525 864332 280322 566087 636241 892419 733963 750407 271795 196510 558926 469535 515870 80807 794915 632270 986152 769096 758124 466985 367675 788349 769752 751659 383747 829175 676223 223600 754864 29807 801864 251350 660138 111850 94199 113983 963378 953518 158854 414351 334820 423519 340299 959109 645957 972410 434519 348067 562201 843207 565497 735606 909821 526631 758035 845583 401880 299505 286442 168614 898184 598683 501323 133354 935030 350925 142122 648506 770828 78439 622925 363728 444767 812949 544504 671727 491137 548355 377891 90438 906218 928886 512262 201176 204252 284867 357824 202202 664293 123935 295544 42905 880757 202393 520322 789776 799073 707791 285511 259960 125769 28993 560112 925494 168948 595863 4648 53352 509367 713211 649365 457186 286899 17400 879297 152070 3191 19942 560559 496144 548406 896648 995034 495670 789869 334702 652757 400139 834459 403303 358758 639428 432428 603123 593504 373961 557743 350841 909471 109066 488116 218541 519010 979196 880363 368838 963940 61678 673322 691381 363922 233254 636138 955465 696710 169184 776742 741410 799714 101813 75037 25187 613998 749877 706890 301763 729052 110596 191051 306159 730065 783165 521276 881132 941182 522482 751628 756321 287271 90716 101639 178709 80888 713658 527783 248560 263533 769096 653867 625885 419588 451205 504109 282579 802204 572042 961498 629445 138722 852326 308705 230817 679955 432417 396459 524417 237239 253874 286903 321469 551514 175216 713980 602312 630231 51370 528015 429475 688865 142058 944000 428997 828265 275564 316405 378282 149429 165573 79205 757691 941121 479712 2498 603525 54490 726561 214130 522942 125971 840124 544553 531991 734678 676909 533981 527270 180513 414098 92107 284459 895986 493758 936706 519667 173806 632835 447106 957141 244805 59792 235485 518451 690665 824337 400956 458773 87129 175302 486841 908686 249167 98675 265775 465785 930831 830946 770585 363133 69104 244448 574673 618656 406926 683751 415793 551363 749852 863466 609064 83491 235273 913804 30159 342170 76271 195431 855845 100431 149041 848115 466681 363026 311398 5434 157571 542697 882800 87247 397233 270566 417877 813662 695986 744712 166000 314789 634953 886099 184465 564992 62194 452806 588086 260139 231994 567176 407856 972486 402670 297586 581794 504981 227350 149662 856330 973894 598285 713700 445018 243397 509853 816661 141824 327677 674015 515856 735278 867949 393266 654358 79697 337861 92310 108637 732795 970180 324952 731320 417401 837919 773194 803211 392709 827911 714555 702649 499969 657991 91542 81620 682106 145672 579600 894747 988771 585309 568036 503429 796838 296156 820742 855106 84982 33811 770761 441783 691758 765709 448383 694180 346889 595109 496164 990621 3645 931772 529547 767482 547544 683040 274107 467081 703653 304977 954478 820228 405383 241903 789544 768660 316088 902108 535508 495450 435733 14554 947195 643279 716669 862214 971173 826106 537817 654055 212742 202659 140074 365835 396857 90602 871023 474384 322590 500181 307768 863544 241670 288345 125750 186868 488860 631504 1 168946 246764 621945 183276 939871 749422 21266 134532 691836 408310 337502 296355 443936 915425 940156 231025 664181 998434 209696 733418 738141 935442 172185 241445 168715 894650 853359 530042 139746 731507 288773 921767 352929 755520 722057 699499 318309 391560 299293 709009 32048 448258 230162 493302 62319 615053 719931 828460 297988 401238 358915 489231 55534 677677 853064 888604 982550 737431 909665 103443 703870 573333 552121 890970 26108 741580 643421 492091 260909 40440 839834 612188 871698 177874 483987 438889 550642 117160 419918 850548 736385 61899 549961 956007 955681 702886 384300 962361 245210 202830 84844 387477 809145 782086 69789 164406 234699 71459 745535 925076 23399 495113 761925 265384 187161 266279 457924 968201 152692 352472 794261 643212 147034 271542 462057 109740 118901 685830 699800 430819 684170 670097 849494 701854 317926 560038 274079 459459 601771 751515 457730 933684 936465 118654 682044 520535 138521 253415 384458 347997 266368 852857 263697 966517 496098 724884 913785 362329 594048 105567 414573 931621 812208 560229 734737 363181 5187 408193 630621 293855 259913 811065 608034 371134 337135 969972 57582 713532 747778 911869 724334 649057 725397 582305 738393 891542 225227 803025 500365 355215 229670 568735 862136 391017 759765 269267 102330 780586 26627 613690 427509 87512 873486 984025 62126 95809 613594 403172 95133 255064 111790 300898 956057 167569 105955 825059 637577 909401 233772 507729 43974 947210 562178 543706 68749 368140 988677 667830 358428 95167 657873 89751 791300 514876 327593 973008 54194 35209 412020 618753 2126 337148 898023 7400 298066 276163 375393 616169 77540 969786 341286 794521 606436 958400 462889 197318 195884 144918 993470 692881 41418 792729 517039 883061 682545 665706 436633 979847 84839 792131 381018 353099 466212 633799 911990 166159 709144 755481 293109 508200 497511 490391 35022 304091 191450 668802 738789 990375 981590 182421 141423 993716 88990 214980 895213 818508 192526 656558 412909 388828 229170 681808 547659 220607 167957 75222 868268 502839 257853 671468 347468 56727 777001 265283 939916 964373 735772 801331 451738 78384 251852 447151 320470 319859 11106 725237 19680 602244 408956 815040 169917 562898 752612 812428 247993 780789 917747 299396 623299 103411 748391 253205 644712 471957 419519 384301 444834 943361 854781 441364 723220 614881 536080 960605 394005 879611 230678 116294 355776 233346 985060 428751 30000 606204 812797 103626 513707 140909 543608 337197 254053 617157 810247 962497 876241 645986 353548 766914 602438 673776 669174 859249 54984 286769 293056 705346 962444 918480 489972 47191 402720 477385 403095 344743 457098 773073 781024 560156 942990 309644 773057 707259 531769 713224 738846 254839 793136 397450 533214 332044 375891 831791 652001 4615 596043 223470 3558 510243 929184 357212 563984 488950 500491 995129 125239 895409 824498 884177 676280 547473 751219 668544 262876 389418 182797 743504 954533 43134 439985 475945 391613 853137 506505 837645 694873 638621 574276 166808 628465 855267 287364 917543 498719 427292 307831 496588 42120 442329 552796 300560 380736 124138 228207 225036 59024 257626 388693 25974 814840 358783 395561 126076 741879 611710 648059 720228 714479 107359 418663 210809 962042 567027 152523 730798 483067 43776 682878 549531 443140 882256 951316 676 352209 110233 271716 371832 78051 56163 215530 828544 910729 597068 80554 805023 99058 321209 95941 924471 842566 623722 253620 280584 540444 77794 892782 703829 786646 125304 121791 67298 846812 778835 820524 787741 864867 51926 117099 130921 175750 792388 654607 915890 114746 969378 935297 166801 710859 257597 348644 404381 997289 108976 535488 417138 804774 318686 818569 156592 74913 987585 526451 966848 62060 500669 122261 366568 101379 874400 759304 934769 44237 579653 652253 319398 392677 543122 924168 252385 280344 101956 158757 501375 189526 384314 204881 34654 615807 316240 833351 310412 638000 376009 486024 777329 555179 715320 282465 337403 683382 716191 147957 965418 341541 687721 402671 819261 48441 765810 874776 11363 776657 806566 801621 164290 44999 341966 384887 782376 598226 356559 190627 326548 84609 373927 843295 437699 536054 133078 957872 987218 152985 139333 346020 530399 742518 93055 739002 150783 649893 921253 664264 628789 504758 999026 17737 903456 210055 431533 83813 565052 199525 692011 382996 315727 542544 904388 706573 652711 404604 133340 491698 485831 502084 518734 823419 192802 84947 29920 424698 210438 373849 488878 834346 287500 172439 277390 924304 811653 439420 260647 201593 11572 565957 221165 892692 399518 1762 592976 339411 688610 932564 909433 122447 533938 106422 894305 975923 693163 133967 455887 853745 795612 864287 69123 227333 991807 724906 5558 9390 21980 824191 864516 523832 79791 462551 81608 968806 35130 616327 773647 217668 389056 778866 571759 87328 450662 98566 125156 41869 866026 47888 973394 353079 926431 334950 463619 605105 418364 882885 395172 28302 343507 394177 541143 20519 526431 555218 664312 718199 232371 451305 365010 702251 451433 338830 828382 64098 541959 858834 192507 706899 749243 283640 684684 602143 185206 984861 437473 675868 187497 376430 115705 273113 628574 855724 862057 485829 904442 746507 208110 475538 164757 496490 707023 835361 560727 663448 436376 797121 439129 301095 976686 767364 920413 465807 794307 261122 218769 234518 163902 140515 283229 918306 137087 339362 399424 509450 782264 604639 431362 570983 789166 989793 286191 704307 25055 566759 242885 49275 794282 594869 923026 670537 229387 344166 782951 899862 430884 385322 674286 103200 245948 432470 964786 691331 694051 615300 407707 883623 474808 450418 527066 38099 265904 701109 708895 957825 187493 720966 888746 608834 250656 454008 667538 554499 786314 512439 806647 727035 831948 909171 918860 7157 631207 384888 857016 28605 289623 664741 815263 521977 587935 887053 301284 94652 974883 466686 18249 799491 152549 654915 37441 451227 992435 206220 760757 745648 815955 975789 239891 348035 385299 827416 484351 477933 309630 210939 492519 531012 978335 849845 983442 261538 406017 386414 934765 358373 217623 626382 241523 905533 235060 385953 853504 621924 685919 986140 883747 812234 523681 455666 98808 250686 142309 635148 248973 102296 575010 254129 619871 396893 140296 962071 458569 601906 309840 814492 94742 619133 559877 425209 425996 494750 8316 797049 137285 919838 204551 80141 943762 418128 801397 226612 331414 110464 417646 615394 609683 216886 533595 636533 953324 611396 739830 843817 67178 44895 458064 860022 466991 949879 626926 132707 761782 279774 390875 220974 106651 511140 556636 721049 779578 553527 999982 17489 226609 56373 490335 487205 883838 624338 139447 198773 209048 939476 948210 815065 986506 256968 138346 170305 678522 652029 780627 296929 854877 40731 348918 447712 720539 116679 588313 951608 272947 728604 720157 216054 869570 574568 883039 811818 846223 443336 161631 151395 244920 160239 84040 6000 468523 673659 60635 125840 537269 452377 719937 517313 684303 976806 922046 543859 366902 131919 634004 417429 148537 886123 792576 553186 431129 235200 41987 760464 630304 735770 258469 1693 276529 197612 994900 393231 854665 579768 207293 209946 796013 971997 444253 806775 480235 802970 75836 623841 320470 484637 625522 578248 273354 328553 31868 531262 552904 566105 704980 651903 244206 64648 650649 736001 359609 625683 285210 171507 413262 854202 862075 56056 890993 433527 1641 598780 498442 972865 631067 571901 71638 567966 296642 836903 357207 781262 576022 174102 685510 73960 661160 498968 862662 592527 273529 144049 535784 727930 327895 945000 579698 471609 969034 494331 368374 760496 20513 90654 646803 276146 31517 52924 156360 469072 922899 53352 858595 824192 746584 411251 296121 701021 928317 951348 245697 106898 959383 273892 938508 392887 789013 553606 242478 688601 878355 780951 58932 736697 80596 297560 485751 384166 377133 29215 365905 336452 564907 377123 3263 693787 16915 75422 72242 440971 38915 184631 67549 448773 884834 368214 808413 321974 872620 530484 324414 64070 887867 110889 510442 185168 17306 205742 939271 697110 664979 601209 908095 606885 726835 231034 371368 700797 886825 982780 200898 218091 965710 140563 761807 387358 536910 160468 999937 827768 292679 289829 301332 129509 299584 257771 558539 861067 985413 987414 34756 372700 682506 160249 334764 14030 917329 187471 424140 320084 292559 152514 253948 351051 61141 875695 455592 534118 920229 930134 525659 998532 78494 759207 538410 201903 781973 492773 778792 816131 698826 16607 296940 27198 532345 7823 760604 294609 475548 676775 624317 258793 844268 741945 693594 999719 845094 502909 763925 45301 13036 638389 504569 784004 374625 715923 56190 512507 146075 522725 342067 202027 683954 982030 702457 570042 574784 249758 345151 209303 969086 953309 580642 134839 643101 177618 726209 812735 997691 457336 490383 161849 604930 473010 225029 434811 577471 251577 326802 657506 424960 679556 907292 697082 476963 702420 525773 403094 668668 564603 748301 874944 628010 776303 815179 698981 884917 294590 173392 911746 173218 176757 39719 39273 753710 820508 782547 679759 708277 529586 216557 765935 816394 197640 284782 790980 273173 706515 839460 394314 695462 951922 382301 223677 914546 270164 795406 368246 399656 859282 415020 332365 544359 674277 187226 679863 870833 372403 61272 783980 964166 364975 450946 370162 36900 845638 329930 556635 864336 543581 497878 393128 158591 101255 127724 21706 113721 441429 518422 647924 548295 734624 947778 115074 160350 810667 251179 115195 206015 543331 917844 749048 857822 590104 391336 501732 186247 113931 87702 151434 146154 192875 472883 615699 828181 342289 720514 114677 230048 157985 704771 310776 731578 470600 187172 133620 282087 151883 740001 274109 343268 117552 508618 74153 400890 439528 402805 921293 733189