1621 997
962 385 287 163 748 167 318 619 534 450 707 981 21 810 232 383 380 747 81 186 947 754 971 162 142 351 945 432 742 889 841 872 980 105 491 319 474 450 629 396 852 615 440 796 386 774 246 133 120 328 552 246 733 29 712 890 993 201 453 144 308 299 137 570 766 409 568 410 777 297 803 406 687 51 815 47 675 547 977 497 528 249 321 824 106 780 700 163 41 363 837 296 716 392 181 185 856 289 126 291 665 768 538 296 340 217 607 571 531 636 880 313 73 48 133 61 807 985 80 950 519 642 202 863 824 712 461 443 244 163 649 631 905 30 326 500 265 890 750 621 812 819 466 775 361 881 128 753 992 4 311 263 329 265 353 602 220 483 911 703 522 491 612 454 356 786 950 253 478 971 199 185 891 328 976 384 386 916 275 676 610 26 56 410 168 441 686 644 686 549 372 234 150 338 696 11 29 51 672 641 239 803 589 27 329 692 228 284 20 699 364 961 817 327 309 146 437 317 46 331 160 354 530 486 102 197 89 79 420 728 508 880 654 883 26 323 224 12 836 650 886 244 191 39 844 764 800 701 961 577 589 593 391 101 970 53 464 41 142 133 237 65 332 357 797 281 479 9 83 885 340 921 875 944 981 337 537 778 668 126 419 429 948 898 860 802 859 715 957 6 681 892 603 219 688 278 210 130 867 400 413 846 946 590 444 465 31 545 807 291 469 683 389 372 325 633 638 739 787 463 843 736 337 8 935 952 724 566 18 158 181 993 274 653 148 850 420 823 483 87 623 901 157 980 584 878 919 522 367 984 560 496 905 156 583 314 122 784 899 968 469 486 271 987 581 22 393 432 408 155 159 111 882 366 254 101 555 397 273 415 830 815 923 67 565 84 617 684 477 824 679 93 985 378 174 231 454 125 455 884 729 129 93 490 143 709 912 380 245 221 650 780 134 693 170 135 154 296 121 368 175 385 426 532 56 267 49 492 459 542 306 91 397 292 335 652 214 647 482 215 229 546 513 272 22 166 737 98 619 233 458 706 10 900 229 908 726 114 808 50 671 270 626 418 428 966 591 614 653 702 543 514 301 112 184 779 619 564 864 503 480 319 220 268 110 611 733 963 909 177 930 751 811 741 576 791 395 107 212 390 608 863 122 798 685 748 716 398 794 172 721 574 82 524 138 952 894 131 917 507 200 580 788 913 582 476 591 799 219 851 951 485 541 843 572 797 586 620 948 866 678 991 9 434 223 349 495 652 822 490 76 278 447 825 809 124 747 320 61 586 724 63 195 288 832 833 59 348 749 336 592 54 388 674 451 850 270 906 694 58 279 36 803 213 596 842 2 855 448 279 57 616 701 659 792 852 445 34 608 801 927 32 897 922 648 679 332 960 896 456 283 398 228 334 112 42 338 803 203 204 862 970 235 33 240 409 289 690 941 552 35 58 75 660 873 586 298 25 711 987 123 662 364 99 909 804 986 478 841 727 756 402 556 925 111 711 8 947 195 1 221 127 648 832 986 197 207 69 141 505 54 422 417 118 834 77 770 446 983 277 763 565 216 559 957 266 278 914 658 131 891 371 370 315 994 484 663 355 731 888 81 14 839 495 109 435 693 968 95 508 743 346 373 268 233 294 402 665 392 603 776 588 932 981 47 226 172 454 900 147 180 516 446 526 439 794 17 385 781 235 520 686 535 97 569 177 82 286 818 972 544 308 624 732 90 723 213 602 358 536 819 942 680 688 841 247 866 324 345 881 363 610 862 831 197 828 341 170 426 47 108 769 902 978 275 853 92 737 955 881 269 674 946 392 525 957 297 717 415 166 707 291 377 432 23 520 303 964 407 951 291 260 452 280 738 782 643 623 773 637 711 671 28 604 382 294 570 788 1 695 860 383 282 365 656 858 555 647 662 808 677 332 573 828 251 858 435 94 893 408 350 849 979 949 684 698 29 255 544 825 40 826 360 936 42 318 990 689 578 188 634 154 842 615 509 722 401 718 236 218 141 632 920 78 645 424 488 465 595 171 219 128 660 378 816 310 849 317 551 760 856 379 407 591 856 453 527 539 448 227 803 205 550 752 225 965 23 783 740 33 571 770 272 221 887 982 288 240 901 294 361 748 112 297 518 293 183 600 973 411 652 848 315 939 910 155 411 752 867 628 155 93 786 113 468 19 292 578 776 869 802 523 563 457 441 455 889 714 711 994 462 898 200 645 5 871 421 587 45 868 319 594 699 542 820 958 302 276 869 123 391 847 227 357 413 794 196 835 39 920 71 656 401 589 161 379 479 895 641 996 510 136 932 822 835 156 767 477 560 890 765 252 498 45 585 96 805 304 149 369 510 842 126 393 756 80 661 178 657 487 784 963 266 447 423 865 209 561 376 584 948 44 965 832 11 599 62 38 271 609 757 833 465 627 904 935 961 611 562 15 249 646 795 666 434 501 447 93 262 160 962 793 256 569 690 758 270 553 100 655 801 60 423 608 673 460 506 27 473 669 113 521 512 330 258 381 334 675 330 771 950 719 516 993 473 193 744 73 286 80 932 399 352 97 422 697 514 929 130 556 74 39 71 651 72 91 20 157 232 537 173 300 840 553 671 234 433 605 826 163 772 13 830 187 729 131 927 348 989 665 250 705 451 707 285 105 8 139 613 408 995 34 386 640 486 814 640 169 138 900 990 307 144 937 562 621 425 835 713 534 668 245 918 450 310 152 238 682 582 189 762 682 294 533 567 630 670 642 606 382 783 856 94 438 940 639 822 973 520 117 806 768 55 784 484 894 420 598 182 339 194 475 347 598 761 765 164 449 431 422 378 56 96 955 882 92 280 344 70 751 145 879 933 622 926 205 346 92 969 153 88 359 108 954 979 862 12 708 259 940 353 516 85 508 229 449 156 865 9 362 37 239 295 436 548 342 544 366 341 906 535 230 243 308 406 838 956 511 403 304 864 719 915 363 163 187 326 622 603 811 646 988 197 787 137 198 517 685 146 490 811 414 242 66 885 66 889 376 536 323 813 883 569 77 816 745 870 529 374 891 523 554 418 697 975 305 6 667 100 467 564 929 635 191 222 821 515 805 211 698 412 233 648 770 382 43 680 611 752 45 427 369 360 967 3 499 168 857 519 416 343 16 826 261 967 710 904 691 116 192 854 575 24 632 703 492 257 785 470 189 258 945 744 725 884 316 53 7 768 720 135 463 557 492 747 716 229 206 68 907 974 115 582 244 501 472 259 179 789 601 458 597 394 759 419 184 59 868 953 436 391 660 515 924 868 542 741 725 845 993 618 704 197 653 493 923 213 829 726 659 348 425 39 76 956 934 478 779 502 465 334 471 836 790 270 481 353 368 510 911 241 625 52 29 305 766 208 804 877 730 31 983 182 384 290 266 697 504 991 333 382 959 274 264 814 430 631 958 474 36 724 857 190 88 73 13 46 79 47 322 978 29 842 846 875 635 532 404 109 489 668 684 974 861 527 664 176 99 68 57 149 892 943 827 248 902 453 475 88 590 755 860 12 734 442 417 85 482 151 870 165 405 720 931 494 272 377 47 943 375 530 103 86 846 505 558 132 697 785 837 521 312 746 273 997 156 154 413 938 169 387 928 732 876 333 502 62 98 855 856 485 850 140 735 579 970 540 119 406 903 104 150 64 243 489 548 770 874 610 642 675
331309 823134 290448 998938 227201 189150 457428 297030 370287 68875 422190 863107 807750 665579 524776 430757 612456 464829 722526 36848 171788 351727 168322 801248 990207 93670 48473 6306 275167 434938 753212 149081 848030 975158 593432 867162 543685 659228 588207 222447 418543 633056 519445 538968 349193 416232 139635 344006 512537 603922 302343 626526 183284 631662 180002 985148 962310 741695 429481 85101 264398 561343 420181 136372 450591 13912 155251 172166 522721 456300 502117 783374 847821 43278 17758 54826 10869 6086 106730 695212 590073 797585 684900 950618 306707 963102 790590 417006 122508 516946 979516 865686 309381 881157 323257 418485 458351 829379 388577 448736 584531 100109 770294 791714 15307 997973 171083 721273 185287 279685 485964 686743 305609 265848 350708 291938 357737 744896 163412 337012 59730 95262 28179 185180 230851 380173 917865 593179 596303 291320 234979 793319 292829 704639 500706 170155 36392 470326 376924 221702 924864 388965 324761 115272 132232 273929 349815 339000 811958 134034 605222 965008 899479 230628 753773 638783 829320 892822 515876 303526 282109 191477 943351 839004 2302 371586 461098 115946 751909 60528 889167 514063 974689 244071 781393 281469 268406 558148 777389 923803 903163 881878 279284 442881 714267 566114 256586 998143 859988 790176 670954 696470 593339 14204 69855 747773 440438 247767 661132 551774 310081 225283 138086 314582 969065 611530 190261 465592 416468 449255 68759 636555 139639 79883 590716 605192 596894 372058 977003 342044 770728 619692 309627 964204 45960 100428 928987 538060 445574 852860 672011 289607 551675 179503 926816 999322 300505 303182 357060 320889 742177 585332 351923 440328 369898 225138 120896 528291 718113 775179 884238 376599 833155 686904 887320 704487 266661 869030 462249 404552 712493 366515 183524 219301 624854 830773 103677 702556 406767 438195 132670 840574 398749 813482 29380 245075 3925 761673 692991 497556 621602 947509 451509 762543 364133 990086 683135 44039 255056 78984 49547 882097 46699 210108 865177 505400 272207 459540 471742 964122 196717 57722 740771 964937 551880 739017 745543 144939 824694 571922 921145 622106 928932 564953 131615 755109 635215 769302 283506 646156 55883 698292 116096 165384 626560 276245 726632 168833 158248 940556 977634 787286 173650 215394 548660 236377 838434 790994 353789 664592 373263 747340 759535 220085 732964 930550 299405 851191 610752 604710 65841 703031 119637 617001 525448 854796 355948 338880 953748 406911 156576 423262 260649 744719 730079 755755 361968 373614 973292 123844 113191 86851 916191 686712 306015 917030 171683 40012 604349 502631 398456 801848 969146 296071 138479 221224 186339 464829 831344 741436 621658 175026 800695 880712 365715 970630 434770 92885 547927 558665 44133 551903 393476 616642 863527 866836 900043 31084 337890 843803 806641 42548 60919 908171 370831 35580 464599 302704 577042 210523 440139 938121 949052 637723 578861 593356 481248 423033 98349 874721 231978 608553 896909 746019 289877 85967 194789 301218 254131 671367 369568 821284 39336 406302 222333 549023 890095 650391 888527 796672 508052 188263 844349 592104 461880 848697 442627 403242 586641 719850 805999 867918 396071 319950 4581 102480 270488 84970 672539 15778 543957 57719 712094 242726 193635 189158 396107 468405 707738 267158 245974 76827 392041 482080 882311 223128 280528 357772 331192 492512 321189 269848 819161 15324 296656 862456 663980 677415 397775 60369 727176 278226 580275 848445 216474 234913 271584 613578 722784 840843 959377 123 196461 78398 137810 704710 248808 76313 545668 218708 425420 383408 762524 305604 255785 886923 751908 680232 897250 899879 172537 987654 219565 794740 153484 878040 229718 650005 131617 758412 617468 730083 924115 8645 223186 527595 158029 456537 847584 573099 926802 177873 369600 127001 66359 170476 475617 974748 501860 295325 550343 858768 206423 346312 645641 349447 361312 706504 86481 483715 841317 846060 900960 925372 737568 890549 370887 941600 943452 965018 209647 474958 982716 641604 442898 311067 728437 678866 465536 881550 979343 217495 645403 950371 869159 242903 767963 550155 125295 717517 650123 555497 324653 537320 373706 908567 31352 387146 671947 661280 161023 183111 337110 170563 350081 774380 453444 568630 420822 141366 167238 33889 793380 99862 479199 812767 387051 927475 500518 795712 993978 438312 837253 442953 34487 571010 856444 50739 39388 579908 753055 589160 497972 305507 728147 519753 620514 113545 967445 872747 540954 725014 567540 583573 991462 739162 557522 842180 97122 670493 704231 112039 438016 670616 962110 449123 443973 476857 764277 768272 975242 595427 581057 570 104957 899755 901288 427489 463453 274460 407686 340089 23041 904116 477129 506347 731794 821348 726324 127570 643724 205652 874976 865151 555137 556317 326518 733557 620630 124685 205046 981422 876228 580711 749875 896276 120089 644257 485717 73417 503220 860004 824022 460064 584332 878542 497477 404897 865194 274163 974982 614345 494954 672280 291728 662920 619390 348087 408621 984641 324651 560639 241278 139277 701642 244305 193524 68089 693896 622915 254232 428099 311014 452769 573637 382113 609850 24295 988392 640250 648173 685256 116679 875050 164091 517034 319351 289474 859574 769703 862820 394630 205506 974350 529933 31022 841370 634848 538757 967590 931850 932179 967155 834958 27508 524563 739219 79290 947915 24828 420339 946163 997147 466017 173559 756788 733887 264648 498901 483694 582505 41004 232730 102789 88861 510266 68003 687696 156406 526484 268772 870173 566368 139665 429989 133482 805852 756282 227072 799277 885248 838159 218661 683662 70324 786048 540694 413991 234038 296180 515051 480587 435031 336646 303823 334140 42235 972675 930560 996787 200413 418669 559379 743836 735625 989179 271982 85208 237536 619735 185421 867769 335704 49311 468478 70153 267705 540260 43684 726596 165409 201902 974392 371609 305920 810997 455939 809837 473309 924073 663781 825496 318095 536364 795537 962214 41029 499219 978895 660695 410175 443241 873145 532383 69651 681900 398462 950247 394921 800013 208610 849034 74047 362932 12412 588312 743717 704186 925366 656663 416834 70509 473745 61310 481165 961040 636639 878712 620757 282520 532487 137831 464442 18416 405636 733470 550065 452022 159398 508581 302852 591292 24975 661177 911632 435016 268535 189385 669957 268884 739369 694010 698473 7246 742788 186085 99798 466713 16827 317780 723639 423115 451286 421640 102607 124461 205678 202358 416243 604734 12661 720836 182474 469040 141995 735569 806164 733737 394602 959019 797024 130563 167003 434007 418581 87757 226175 570957 276842 552968 562727 247481 422317 664810 880892 724474 334272 167647 355896 813799 163927 438147 592619 607813 499324 328233 262135 534034 127436 365719 997268 570494 267895 640135 71757 212461 952003 743464 371776 665014 611145 928347 241186 8679 383735 993335 561338 631614 312588 476294 631585 266353 563487 361029 709896 661607 829657 756519 583858 629053 167222 744850 244725 357187 926089 324833 239037 90556 784309 975329 287369 741089 336692 674260 744429 536606 746067 603377 252942 158803 629044 874786 180905 49493 528779 24068 416845 34091 704609 747179 227612 900561 680660 977691 194509 312184 12821 19216 663341 920580 355945 116407 551898 895693 699754 597554 940998 557535 725379 447832 826682 956858 502326 625907 459345 763410 797337 352513 7736 700879 315093 437043 359093 921102 377638 347121 113117 448991 658654 832340 613788 181766 316322 36650 789553 434426 803179 681398 523119 588585 361542 885293 329982 656177 491156 685114 385751 963176 250315 578875 84108 264789 61171 688321 164349 152437 693418 508884 58084 309943 334177 16877 470154 341057 327325 364027 997392 257257 827767 634334 842919 970684 968924 803055 797656 358394 199565 766070 932029 248983 756320 595634 38470 570364 617405 605077 325429 232645 657762 811333 132066 162753 489696 780252 17912 779445 103964 353704 832310 800792 491022 505004 625391 606296 5509 977822 211530 46548 219042 791399 762690 626720 163672 20646 275815 802309 867378 696941 446428 492478 804237 459330 523672 680827 661402 924192 702437 898274 439134 568243 160291 546953 973809 133088 771845 254398 818434 813306 57363 920511 284625 474766 38375 762114 693556 910232 868848 419886 165971 969675 340530 537248 809964 186637 368324 681063 914255 492345 341905 340681 433187 680860 834903 219388 928031 985272 974507 432173 316498 766404 513523 578044 889564 353513 587435 497213 907314 234823 673376 574969 232926 900206 997112 861484 364541 263590 305448 771269 555008 253671 316156 311464 944555 450657 238419 947375 632857 319286 618272 447717 461557 560571 803627 604298 219714 493882 86926 727186 829524 632563 16440 177701 423061 174487 163821 455840 341698 809291 437763 833875 263403 415595 377895 486529 40759 485380 60630 421860 125533 118297 395365 269094 613228 136351 687994 564265 899395 949569 717712 712063 87002 205020 630582 830835 554488 523652 993873 265726 45626 159614 888278 411219 411730 714372 37969 488660 31174 962180 782112 804890 717997 771041 239864 106097 602293 348336 4896 10393 532576 401468 353457 732358 835394 811843 228188 59169 850885 764727 202148 896454 87973 597438 374367 836548 64949 775474 532730 92127 532440 652641 510706 721873 931080 678734 680155 475909 468626 5871 416349 253338 259928 805037 560370 212007 119694 685607 927145 367153 712318 210799 876326 711478 936836 196555 953504 717734 693714 949877 307490 468900 919469 86492 792587 334857 658670 648225 330509 203042 526594 512795 760625 583469 136299 324755 212050 783968 964413 235144 956190 279586 395298 482284 764056 414480 269270 403685 277592 420793 297451 281166 82185 262114 161414 551668 801067 367491 421600 695449 752079 706376 201414 260340 281693 376977 851481 14318 874769 937779 512847 143847 531513 981172 299761 23343 920249 819731 422363 194317 502408 586366 346815 120188 916848 291226 764258 610665 467666 399998 531741 143606 911711 294008 356573 103162 235936 956935 591395 554687 389359 921055 920581 787842 365436 734568 583979 905207 707209 48959 556819 597058 247022 514932 455950 994239 851222 68298 246337 616955 482048 90490 960933 943096 436095 417585 482823 817902 318074 216013 750920 770180 518637 92260 167070 948763 575910 822717 713489 121220 81609 531221 624383 685700 699980 330715 898841 319703 109116 412788 884259 518378 874038 633784 119288 868000 710126 901619 378180 841038 948332 477221 163464 538303 423242 182658 407962 486385 522680 122995 297314 840918 340216 355411 720222 710356 898466 268723 904286 74693 246624 935063 360201 184759 718643 688055 44118 450605 942445 648638 533332 47517 239605 600462 256675 232560 800518 132602 622585 51269 709040 754506 382942 279086 505174 401403 763248 875889 514670 100605 746399 192008 356612 938163 918002 662241 45687 382583 47296 981343 34298 515859 713528 808344 546517 908808 445786 50197 40418 25931 130491 150613 978320 143811 546629 219978 4323 307277 397877 47066 265970 28600 621147 748000 60647 417801 723422 238761 995715 990200 198901 894263 227095 922161 474991 383744 981964 712916 27500 463088 160028 450421 714465 303971 382935 541085 352216 525804 663263 920135 993902 748562 209836