1000 2528 7 222 109 897897 949 686 267205 506 753 206888 683 710 993280 157 650 469936 913 689 591389 262 123 307216 299 905 698837 361 746 466209 554 417 459957 110 441 641459 581 42 842983 934 351 365870 1000 278 136866 475 695 980688 408 807 959847 237 728 225756 673 926 243405 373 779 170011 873 610 270034 778 296 621645 951 942 735153 797 459 283480 866 251 136612 298 251 50706 315 183 617 245 22 773651 482 866 386871 363 529 690760 591 450 535504 696 239 709938 955 966 538560 882 126 630910 721 858 974747 376 200 128170 707 419 15872 174 13 198748 541 317 415507 454 482 831624 480 419 987614 458 125 1764 748 509 769527 485 921 677164 400 727 133355 896 360 286209 362 125 534598 955 935 62138 883 867 735823 226 94 515122 75 568 312919 397 647 250501 853 171 560641 903 518 697044 31 892 67510 812 25 915282 240 345 578874 801 509 11646 42 690 643641 263 111 602224 832 14 480033 490 37 958899 300 866 510045 15 52 824091 40 561 204242 292 337 205821 981 269 107390 873 199 833171 837 732 805404 755 134 667006 503 305 233440 294 199 69796 589 78 350364 856 128 103020 403 54 875972 317 513 789062 685 700 336835 270 529 733520 462 709 638273 389 558 647023 221 937 280575 854 684 520503 102 544 455416 10 29 269749 798 209 230172 165 86 849846 65 590 273740 986 470 276235 368 957 773082 659 208 652748 397 620 666648 286 129 850293 726 438 990301 807 340 724548 38 729 113805 945 789 144360 99 256 297678 60 179 295936 830 325 842877 302 970 379283 250 961 693402 962 44 544378 565 583 992056 753 996 599510 370 241 400011 79 271 261882 48 19 534103 123 648 46997 274 366 120620 995 891 254796 169 891 872106 440 90 960488 574 5 828232 364 524 685039 814 744 691485 375 813 969598 764 489 715180 971 198 28804 286 139 642049 446 641 121826 697 110 785020 234 780 180407 409 327 213623 386 845 871667 516 910 70303 386 183 1818 950 453 49017 305 975 547335 917 997 749494 264 341 691443 845 130 92052 470 701 118102 385 2 614778 647 596 505096 866 761 946055 87 587 743637 519 279 953126 791 592 472458 929 200 128351 481 62 640139 194 472 319790 108 311 244854 326 616 944515 935 220 492222 296 126 368778 603 16 311805 78 319 32259 3 715 940957 890 249 555731 715 577 76269 152 47 863529 439 387 605156 707 682 187690 641 200 387129 674 654 250904 752 585 773179 541 38 209509 700 846 857237 479 521 986236 40 846 377950 272 935 804067 401 362 889948 267 943 495843 881 853 561705 960 479 507355 470 574 928690 295 416 844598 609 397 485204 409 142 166978 479 556 824486 852 371 914428 132 149 3501 369 795 713713 307 936 476917 995 928 621348 965 549 334638 296 655 266505 549 503 426260 204 510 873207 688 260 396921 424 798 283843 830 360 818755 882 450 792516 260 775 847480 612 38 950499 704 725 94782 794 833 887152 367 47 679413 350 60 436070 198 697 846377 81 675 121656 100 571 214898 250 739 366343 98 886 969124 125 577 127175 889 620 489643 380 739 443502 252 441 827952 455 163 428229 187 252 261260 776 580 824302 55 320 271519 951 433 42245 502 87 190348 659 949 765659 811 441 413805 604 329 472077 856 25 221444 805 646 960299 235 277 379076 578 842 15722 874 149 334561 684 677 471003 421 216 687440 694 664 617342 854 435 160177 947 627 341377 870 749 867635 32 609 723322 372 496 548603 219 406 369489 281 377 954566 889 267 149585 866 982 728052 220 290 177321 775 387 199948 491 198 180671 395 214 801483 88 860 112516 269 950 299654 602 232 444527 917 19 673107 872 145 475095 693 205 356313 238 168 739884 43 986 140785 9 485 712060 98 255 740667 170 171 147709 184 992 704286 475 679 978276 442 902 690484 301 675 62683 253 803 433317 799 8 404555 538 66 202083 192 407 139385 423 200 424022 453 80 851009 354 148 974858 506 430 290677 914 946 554708 489 263 150719 177 159 788151 145 717 337478 958 214 360342 324 203 895656 602 631 342448 458 492 817021 437 110 819538 738 775 583577 496 142 801087 60 278 601901 904 164 80244 749 248 738071 410 771 748807 130 792 599429 457 798 886350 710 689 73510 305 505 135666 31 281 442608 906 319 110372 749 911 351714 775 3 871016 786 632 65153 756 152 221832 675 694 598165 728 899 282754 785 393 119443 193 884 228768 842 814 97999 168 364 854603 951 991 184175 858 298 206538 718 473 685035 494 358 222173 77 449 146169 288 918 514314 400 965 837782 335 265 610510 148 794 392603 606 61 779357 268 34 23863 158 167 376790 192 997 618384 216 703 259324 578 591 345344 827 142 398388 34 778 939577 942 550 844514 214 34 426167 756 218 928186 429 113 342235 983 146 449226 689 458 245949 807 489 989297 10 313 668271 893 679 253891 813 644 186872 950 986 704028 821 746 234189 522 627 965245 950 260 716244 586 907 689299 705 92 851116 835 866 683693 437 594 272402 871 464 201969 540 8 22778 495 534 465527 269 891 608072 63 921 679489 59 99 99930 282 678 979365 260 169 563608 589 604 639110 638 916 911546 21 350 45161 545 931 315571 711 616 312814 277 810 991543 456 438 251657 622 689 568309 157 918 538159 553 102 980862 94 940 752346 866 147 910560 750 278 905799 22 286 327633 974 357 309456 543 727 582203 670 858 802324 98 539 766467 793 907 63826 996 147 329218 517 199 873535 111 429 68096 686 51 226567 51 364 230255 534 584 577363 282 16 839225 131 59 376767 741 71 697522 41 193 656561 337 489 954107 629 943 419155 176 738 959760 521 175 266321 377 699 564428 11 374 138560 801 594 48500 273 130 174437 535 856 161711 256 367 340058 687 137 607350 542 999 598765 936 634 365578 31 269 725526 892 366 919151 980 446 603017 910 834 308301 928 895 488364 691 604 483789 917 451 627433 133 241 386036 331 73 939709 44 150 946671 359 299 431777 106 309 671186 680 782 227411 573 622 900771 431 791 359564 853 433 637040 300 979 307537 646 995 673320 335 519 66228 495 210 494719 558 360 603712 823 389 276498 642 594 842356 724 123 124541 884 787 560045 991 5 233152 471 39 532826 289 593 753009 554 973 12663 603 958 889338 716 436 317187 76 108 665490 672 280 957369 197 928 299281 632 242 639946 328 445 472465 832 748 977578 176 784 721687 688 728 65323 146 764 969799 764 953 711639 618 91 465328 639 729 798302 436 965 870415 840 37 402008 13 693 528218 566 341 465239 817 983 124259 342 464 904752 339 550 997357 138 509 826881 577 728 930908 378 210 245956 41 988 936262 862 545 42932 606 187 371161 629 93 750603 512 727 421506 110 377 295985 43 592 707566 903 926 859588 726 612 647804 617 547 980494 335 881 858288 681 954 804862 94 650 276797 656 188 183080 22 492 962339 982 488 255575 311 507 431803 746 909 123020 345 281 935876 10 694 381060 922 784 922471 722 539 905375 59 591 535259 471 67 594907 400 820 426965 549 397 541095 19 98 613552 730 80 184324 74 893 337178 34 879 859661 555 154 384734 901 987 120063 836 644 119197 800 256 528060 180 32 512001 28 449 673440 750 896 988759 679 118 420615 742 504 359635 458 284 640458 310 125 705839 646 9 608750 433 13 807525 333 611 176440 796 825 746076 692 65 559474 681 16 654505 430 752 135519 308 414 641267 935 648 172429 810 150 786301 60 341 253812 711 985 905073 368 571 620491 120 816 361515 688 186 560485 870 842 977008 890 685 801639 51 871 623320 880 744 914760 235 623 362025 802 916 270935 414 280 434660 461 802 948709 815 31 465533 306 917 61585 788 427 74040 102 38 59428 168 209 907106 285 495 916839 811 940 530909 670 996 576253 288 353 278129 549 556 653899 869 333 425666 976 757 466691 709 232 128252 76 200 719862 203 370 519675 777 736 955530 820 886 360029 554 570 220411 46 229 391518 657 87 426184 994 887 953350 358 375 621890 747 304 575705 110 571 822002 812 292 939397 963 461 309043 868 879 317725 793 776 318649 304 425 299951 300 936 620422 513 880 509274 250 758 428004 885 123 112996 594 534 995074 925 237 501428 612 254 649892 109 85 183516 596 43 378563 597 885 515766 618 517 636234 667 715 17248 264 177 930970 302 816 619300 326 913 799080 948 714 167758 362 622 537738 707 91 333145 378 438 836015 83 912 945317 98 376 710406 431 173 974449 920 622 390547 542 377 892720 845 917 152688 299 160 348354 835 80 699990 634 643 63058 217 487 900915 70 130 398791 568 244 863950 250 854 504762 770 442 5352 750 639 247855 708 124 232238 461 362 966872 910 780 631073 412 331 672220 439 119 668229 855 613 153932 598 124 142103 263 920 567952 280 466 314621 354 126 405573 255 326 919617 92 767 565173 756 9 799766 983 158 415121 883 674 35734 260 190 220083 676 20 780706 463 659 405939 650 302 470558 328 789 680033 397 817 425146 500 853 239832 923 736 980250 266 522 623018 794 591 2363 564 560 873786 735 903 213824 516 506 754252 389 79 552251 700 602 732760 967 936 67643 870 146 693115 434 534 847248 270 44 305148 339 796 764692 194 472 399640 248 206 809241 143 832 93259 91 890 856294 157 126 654328 344 976 143652 952 40 926022 971 563 26713 672 662 743849 960 639 971093 536 7 267400 868 235 750826 861 746 529916 405 593 609708 422 434 167250 290 738 81795 144 497 906663 619 514 861849 135 794 981717 703 613 321179 813 478 511364 618 921 461479 160 833 155806 139 247 193412 141 947 623830 270 920 447432 762 275 877522 565 528 959326 72 866 228566 500 98 637136 19 242 211686 840 7 174147 83 364 49684 40 907 619891 723 778 857992 301 916 6446 850 319 351056 842 696 868043 741 758 444270 357 239 177103 323 58 216474 605 507 683028 284 937 190923 547 673 840771 97 897 919034 961 970 501148 262 545 793505 313 829 527567 491 509 737452 555 974 33932 858 615 80084 744 673 985766 290 357 158487 508 540 870902 30 670 314203 642 527 205894 596 520 262852 464 73 943173 973 656 680809 878 985 542742 752 993 729074 53 605 890542 360 537 147119 492 269 737405 215 800 115544 485 257 229028 69 292 896094 393 994 820884 57 252 74209 779 426 437344 362 494 684138 129 198 512088 389 810 467625 573 991 636215 681 831 482921 52 593 731474 432 141 809266 102 803 581989 773 98 58251 995 893 706540 903 87 202537 892 724 668263 176 313 350737 996 395 685665 427 140 389962 569 716 99504 196 304 620156 464 396 337413 880 238 599928 422 454 260416 49 663 751891 590 5 589905 209 701 760179 760 456 942566 779 728 173514 766 518 913253 498 909 852630 349 124 737661 283 299 23185 69 775 641052 895 894 396930 356 771 749078 828 29 975804 390 988 781958 706 914 568520 706 890 697667 112 600 921634 960 596 722533 650 214 520638 711 635 253817 489 790 475649 596 935 130789 160 981 674752 369 360 524265 957 547 274068 184 800 14898 490 820 469599 733 574 293469 258 583 6008 413 151 269881 898 350 191484 373 839 321166 529 294 902271 47 487 554713 267 580 862689 320 664 976827 453 516 763460 920 293 981642 656 553 994217 11 224 886570 295 27 920187 739 313 204500 606 918 12712 495 306 784885 4 800 235667 336 644 659271 926 376 641156 19 126 868719 123 581 698289 782 329 366490 61 872 263724 684 647 265475 683 45 953209 729 321 719709 292 136 241527 537 775 184613 906 678 86407 91 300 179671 977 169 918703 615 570 973844 986 158 18647 258 190 306802 957 35 274866 33 46 135000 399 339 660421 212 200 304168 52 163 168537 503 737 932463 342 427 33601 346 954 434042 396 665 544938 867 858 787724 369 823 100576 880 846 571946 734 924 864030 194 867 185904 73 355 888231 373 741 840257 569 708 380403 937 650 460006 66 639 788040 877 550 700994 952 40 591813 663 340 444749 501 853 99029 870 602 483890 190 633 293822 578 421 485206 453 448 217172 787 979 300291 229 71 724151 682 537 71425 48 7 984703 329 137 205368 483 609 139285 993 662 393296 36 354 215328 225 379 360489 963 111 444118 320 176 350642 122 482 597744 322 918 850105 672 183 716522 873 54 558406 643 354 151960 978 826 571300 629 918 724723 519 246 642954 137 786 428723 603 697 420260 479 499 623275 86 805 167714 44 530 561855 613 935 147286 496 301 845865 882 887 205806 181 586 267561 117 289 862115 81 99 942375 821 918 918231 11 169 474864 528 822 74982 285 793 401074 208 668 504640 120 658 335826 373 513 173242 582 347 241068 664 332 752730 997 870 312684 460 519 225574 214 287 402223 431 642 978198 336 531 197389 701 895 857834 432 411 995302 547 795 811617 368 761 867526 331 739 671289 324 96 287365 72 196 841539 356 33 918092 782 141 817368 517 456 677585 253 293 889465 437 65 356527 203 484 296261 428 226 174649 771 49 123196 966 183 25486 784 531 328139 503 36 953202 52 436 252378 741 889 802317 926 188 448822 869 180 857541 623 955 907417 235 453 878188 96 714 244600 192 404 395861 429 600 594030 107 745 70096 325 182 108244 903 472 833131 418 98 522774 50 259 228203 691 386 106693 553 962 984672 866 376 507359 857 877 115498 217 440 333656 664 76 378204 460 134 626255 961 854 677665 827 483 36566 324 883 527334 486 529 146535 210 366 318477 876 885 874484 565 412 28706 861 452 507003 917 856 583300 470 649 464472 236 509 790245 981 327 463231 646 733 521276 989 118 240023 826 729 258712 532 275 238853 36 481 473400 402 675 452136 339 344 821259 15 821 20186 385 662 934718 710 140 174940 179 907 859499 514 823 254895 751 490 26032 408 831 926321 305 443 237636 433 249 112843 158 928 722328 796 117 547902 609 23 998430 201 461 556420 508 929 451865 559 327 212140 428 262 614890 177 997 575804 998 60 509479 960 136 862132 847 74 258995 907 364 810806 349 756 145785 489 282 832728 335 205 342254 321 534 236143 776 142 329597 452 251 278034 92 207 301928 814 956 267733 652 575 12325 713 718 788700 768 277 283205 229 142 637865 881 461 768657 420 849 602213 452 318 339744 269 397 128269 889 930 774266 918 700 943361 350 25 620981 909 720 726058 239 597 229686 675 685 998415 969 763 395488 917 347 16842 302 368 834446 232 132 697885 497 723 679210 37 502 806104 794 275 209567 422 894 754264 127 881 739767 980 417 617129 930 952 150730 366 362 828918 144 281 928761 196 775 706655 889 91 736653 952 562 771811 888 286 148463 384 626 994766 689 898 295584 273 143 420650 985 544 542647 320 749 954682 25 4 758973 54 780 837838 493 175 403965 51 484 335666 49 42 229607 195 957 395251 789 29 110539 158 758 99150 593 443 173267 37 925 992125 30 993 182482 451 594 811066 312 165 400729 902 215 174837 14 690 543841 532 426 586710 417 326 252549 408 317 187175 568 311 59242 322 489 959769 550 149 600186 447 875 791529 844 375 319076 382 122 482990 342 476 29362 753 226 451351 148 159 230955 367 315 642487 668 603 528685 90 218 441327 240 732 970947 916 792 280315 975 56 288449 311 270 849064 180 763 185557 961 818 41248 496 639 288629 134 398 188420 312 434 521857 781 295 117670 326 362 828869 728 136 532423 162 83 750589 767 444 100686 666 283 337914 550 584 289511 710 87 54567 536 501 757578 196 144 951840 170 485 283624 688 811 301503 29 639 802527 41 331 612230 131 228 957799 812 582 95143 183 162 159524 340 520 296101 839 351 779774 537 200 31110 936 221 87020 62 607 650359 592 614 885957 757 750 904444 662 571 968242 43 739 376228 796 353 951062 611 435 878228 437 790 774610 451 995 85241 234 111 884808 229 420 211950 896 188 868705 701 617 877885 670 124 838753 160 297 359840 992 771 974007 499 489 20981 12 3 285503 765 226 665889 30 265 471774 717 669 723416 522 722 619650 637 717 167635 158 521 752849 482 799 948729 802 20 47722 612 3 86348 132 557 479645 872 161 908658 448 665 921557 405 668 529718 976 86 522270 69 224 699834 601 838 978144 981 191 686089 246 604 813426 530 536 309836 313 451 545437 680 74 604070 951 739 892853 318 621 316024 340 736 366536 498 321 233359 613 682 844536 707 381 556783 815 50 459372 824 32 291790 228 651 646636 69 656 153109 560 303 643271 267 232 938391 808 607 861275 393 666 5484 815 300 295193 140 97 761932 110 184 342270 584 97 91459 182 685 581245 168 318 207767 759 421 610979 103 483 622391 288 883 331078 855 568 900529 305 910 231506 375 794 437347 967 715 982067 371 481 580336 729 90 691189 389 551 548453 714 400 701365 298 926 785906 410 948 14348 869 117 472591 459 960 572505 434 257 627264 270 103 898052 655 249 943861 357 276 429223 100 66 388737 383 983 147816 221 194 814901 33 787 535910 18 809 25004 372 558 827475 65 839 959231 21 45 573744 541 854 65509 697 285 819427 289 376 277815 811 339 302539 959 348 857296 33 95 408297 823 782 453679 862 859 546476 572 318 99795 408 332 316966 801 254 189624 533 861 217401 742 129 234818 703 696 509065 12 519 896689 108 127 423972 132 220 525122 290 145 347074 674 680 474912 960 178 239538 43 768 676857 685 769 218845 192 491 244431 162 726 743904 264 625 252237 363 393 698314 539 506 208464 808 50 450561 887 612 802570 323 686 254930 780 946 142323 17 989 254035 126 139 230885 473 471 889080 209 613 724736 385 698 912442 282 272 683165 853 358 371354 93 346 301714 103 536 243766 137 222 490637 221 388 967719 803 59 234469 752 547 14480 633 593 445536 237 691 737776 102 177 483949 934 203 235410 546 454 350622 737 402 322152 27 108 218555 564 132 251271 211 949 617006 540 350 533957 619 887 630768 713 601 211355 785 259 732163 286 606 729842 206 834 11705 356 380 528545 323 64 85015 380 696 654754 92 167 376317 68 472 11395 801 654 37499 874 348 377895 304 26 214576 753 618 409442 812 561 365390 846 175 384709 633 87 228091 890 641 395432 566 324 172028 66 820 204092 282 630 603961 120 264 473484 939 578 866394 695 995 784163 518 639 442400 636 764 377016 412 601 764510 858 201 288151 488 536 33955 513 429 607858 716 368 557405 632 469 880574 891 19 92724 107 823 278982 213 490 95229 899 125 816700 352 183 553612 952 895 165283 501 563 615316 108 734 539511 682 803 523332 197 9 173752 361 23 792356 504 90 287895 849 374 387854 676 15 758066 932 67 430479 456 997 651536 56 369 691591 541 123 654766 100 676 937064 525 9 401550 545 493 310904 439 493 500438 813 203 143408 5 453 785540 990 350 148360 665 281 701703 808 53 472477 306 126 676325 199 594 442883 763 409 932594 259 160 795456 27 681 351334 878 268 615197 407 526 805219 445 988 940761 129 331 46430 703 644 884752 411 895 91441 136 138 549745 225 36 17753 666 917 731644 599 732 70730 972 306 482096 421 409 603316 135 552 67613 23 808 510243 943 245 232077 583 880 627011 755 859 216510 384 280 886412 344 801 554540 230 19 723380 505 477 699105 324 712 524372 159 28 556838 755 172 301055 982 453 723531 147 3 990789 690 755 803561 691 811 691125 192 702 945148 461 749 831015 979 669 767443 459 938 70372 188 845 413190 696 3 800833 726 196 487195 415 171 510165 848 164 910740 491 867 346992 555 414 245751 184 667 772578 996 20 891046 22 699 766051 808 982 429934 788 661 725474 81 163 337780 781 572 357037 793 314 38805 922 486 880097 295 709 688312 890 440 175080 596 964 202385 473 176 272647 697 198 577577 919 695 202313 385 718 712867 236 938 4061 430 459 90918 78 121 923130 37 212 138304 101 738 913748 177 344 483241 876 124 382292 878 716 528798 169 234 186123 522 19 749410 78 627 477299 254 195 476043 336 912 786893 864 237 7844 278 417 284668 788 533 978103 100 810 56694 698 126 276239 414 666 288618 453 125 603186 527 724 201537 494 449 234969 442 913 373075 211 137 29881 643 480 832727 828 976 255555 690 127 92252 952 762 225797 728 700 379799 999 847 455805 643 113 281564 510 26 383670 623 621 214668 646 454 618114 141 210 791430 992 562 420045 629 134 982055 872 957 187375 141 867 994580 178 607 219652 323 457 548208 960 330 437303 670 835 419422 116 742 835540 805 825 242612 777 758 932110 371 585 798206 233 879 665635 223 613 598144 754 497 591287 83 252 44036 953 102 62372 356 892 996120 4 834 417675 427 151 870157 197 363 613653 897 9 158533 684 220 157151 629 109 203698 70 182 181525 4 819 688889 252 424 607098 193 456 186638 896 311 6022 755 57 598377 314 15 355050 183 922 115961 410 142 112235 493 94 988063 174 68 325200 646 80 89850 162 295 992228 646 856 336272 441 901 545382 520 95 412565 33 344 197954 950 226 545685 246 78 158842 360 245 275584 184 400 444317 254 206 446771 28 319 640962 749 85 527845 187 99 356091 173 672 677556 482 401 461910 328 958 540379 596 246 816118 415 579 29656 786 447 181225 440 377 29399 860 643 207759 883 102 593847 278 916 677437 211 944 836904 933 262 406548 190 13 408145 40 943 776163 954 359 710356 469 835 855963 441 96 741897 998 166 424127 713 674 32962 93 412 499574 993 188 983915 470 783 993172 97 942 529166 272 899 411142 907 755 955770 802 272 872385 316 536 204536 859 870 934272 805 685 370805 515 322 37510 401 979 303246 146 691 224500 80 793 195478 220 543 427492 719 954 103857 110 559 58063 762 988 459012 527 926 368014 986 383 795311 225 748 234435 801 882 33373 5 491 499608 74 659 81641 969 660 704444 732 222 484266 859 622 438715 429 291 587179 264 190 391524 194 421 516972 504 588 290818 764 118 886613 615 703 27157 466 29 652943 475 956 401685 273 915 327431 903 814 757106 981 217 216103 795 179 917288 105 410 464028 90 525 62600 736 310 671752 107 71 661574 671 480 105742 449 624 598646 341 773 386659 470 127 646 780 742 305317 767 854 40232 869 868 40525 386 525 840192 842 754 204381 364 370 151466 105 539 316274 696 278 218214 666 118 97128 589 460 397963 778 911 11171 842 873 280758 115 675 656098 66 45 654689 909 50 790874 494 324 975218 967 284 423979 373 31 526813 364 62 33689 229 816 158061 57 738 820698 255 944 623418 381 858 524600 222 637 209808 434 130 937391 669 24 205967 697 212 408164 733 376 142761 878 626 434506 878 445 496007 219 151 569369 343 584 109686 46 930 324612 570 571 943343 64 842 199749 913 510 11902 55 902 905188 451 745 124531 207 754 254177 257 548 368941 125 401 858007 833 913 673850 978 225 892218 521 108 844616 481 51 974707 6 538 713966 170 134 376973 969 304 42041 567 117 295960 414 991 19393 146 525 426348 755 661 296555 857 12 971412 155 35 629867 372 26 85231 554 853 902272 676 448 786496 532 804 679120 84 995 491574 108 414 924276 547 998 494549 251 897 74426 169 287 471287 816 663 150431 83 828 612176 913 392 822860 533 924 434692 682 219 339869 344 335 115946 578 258 651356 263 862 179234 214 153 391269 739 263 723469 705 472 848835 812 806 371090 323 958 106236 677 561 457329 32 108 519768 50 223 422573 169 515 17295 658 729 743088 824 850 864354 165 500 761521 457 72 648566 777 3 840866 410 869 967570 920 550 476255 401 407 279637 505 768 356134 304 935 976476 925 998 9911 761 131 264184 449 221 374076 596 565 877010 664 227 239987 829 866 15711 751 725 840601 50 2 260277 742 169 917068 34 186 702326 676 822 760611 140 783 347800 401 736 711566 810 680 730126 111 313 77617 930 578 440189 813 876 442499 694 29 223952 719 279 729665 237 654 776041 756 797 579387 359 780 852685 798 363 745270 619 117 232188 79 244 709786 958 840 183087 49 263 530061 464 425 172682 723 123 324540 955 501 550143 655 134 101868 356 189 431051 86 88 657785 941 735 341955 29 848 986762 734 846 45014 264 463 917385 358 319 818552 550 758 268705 122 758 588306 667 815 185006 750 236 243695 367 212 371314 394 63 661599 836 72 338680 441 354 126310 104 149 795629 679 227 805623 821 634 864420 132 877 91497 117 641 265824 295 323 310900 813 916 935103 255 182 899587 247 932 557184 631 878 704823 783 82 889746 729 388 904724 658 696 935912 563 752 246743 604 478 247653 249 409 613428 66 875 563998 786 811 242320 319 837 696569 486 636 447387 961 13 985295 91 148 506913 520 852 800261 422 662 119381 188 25 368391 17 60 339338 876 822 697139 250 616 484689 873 361 533588 188 264 474193 624 554 282731 462 981 44521 956 174 440342 703 863 874849 172 92 99523 224 356 958699 909 647 609724 195 523 912316 960 781 972904 232 519 428777 849 846 591949 269 531 821571 511 598 565832 487 903 577760 530 905 64876 130 971 6228 61 409 462367 588 157 821135 965 863 76192 839 23 827242 96 277 562504 490 443 440799 946 202 568097 995 811 905143 741 670 636878 915 884 486637 996 901 308177 247 331 843915 591 352 539032 195 801 248358 785 940 754502 654 366 391543 227 364 999787 755 686 590685 502 285 27531 535 89 612223 933 447 482694 276 358 538382 313 550 117539 930 578 532323 809 751 266706 744 380 758685 233 677 710289 692 5 971637 371 252 829962 528 610 116557 539 899 201522 467 162 196898 873 138 486185 929 373 400925 709 665 425489 105 140 508513 484 590 720180 891 857 487993 725 470 512882 624 219 446097 504 844 458053 234 833 984171 952 458 322028 863 483 890250 18 516 482550 885 616 819611 244 268 555779 780 450 344956 719 253 520472 542 945 807216 421 692 615561 140 501 62958 51 996 548546 995 390 730745 521 825 821010 147 31 813541 390 793 316669 348 774 10522 611 692 140778 295 940 819515 82 359 469543 41 354 616629 724 589 235918 938 363 675433 557 390 611680 526 991 440456 213 401 822221 583 36 768611 117 145 128125 518 517 35558 553 154 573415 110 104 473433 625 959 80279 890 263 763607 435 377 871640 96 179 22956 207 704 165051 575 142 879283 64 397 952405 925 243 399533 238 733 650622 949 766 55788 11 723 902619 566 728 498553 973 481 467326 436 803 773802 682 220 371944 675 473 230315 481 11 672525 309 874 631141 428 923 562326 890 972 260066 281 76 149827 647 884 7645 893 360 852870 517 546 700774 603 775 175775 801 473 831399 480 48 373894 795 811 576439 565 40 677042 812 909 56354 388 306 19796 342 770 144248 330 484 324825 330 606 516818 60 453 510014 338 862 933077 456 774 718448 766 669 464109 785 67 809443 112 72 871403 287 488 954029 140 633 88679 171 757 414175 705 832 250345 219 865 102963 951 53 769806 217 908 268650 678 916 532383 489 267 873485 992 754 649272 337 83 132159 945 161 501818 642 661 536716 892 165 510828 925 918 76302 234 530 889469 352 187 343256 343 634 666213 581 442 966886 728 459 718024 900 671 120367 278 260 643322 121 584 48466 46 392 250924 236 558 529542 1 823 561132 933 183 291211 680 821 963021 401 262 254385 40 687 707886 637 845 155035 598 799 898957 826 130 370355 961 615 85615 461 688 98207 233 611 901938 905 83 980512 485 324 673289 772 244 58935 450 279 730633 76 624 673165 84 873 805369 151 981 786216 768 531 390412 92 854 203942 487 562 505643 790 392 864817 55 908 35562 645 388 738505 36 112 904194 762 170 162628 473 110 263952 733 24 452921 532 500 374768 869 93 985567 924 543 739237 266 883 233089 862 61 665295 934 664 843253 49 213 260411 719 306 525857 194 721 466463 802 24 914713 590 764 124320 257 564 302291 475 791 762728 695 421 75222 757 890 714471 532 170 190014 226 207 208730 905 738 931476 414 329 77006 182 97 146626 123 330 883342 460 651 703227 125 175 571408 301 424 702740 947 562 517768 578 708 223722 741 14 879972 440 428 891476 607 501 312025 489 926 148370 67 358 900234 959 176 913516 885 470 13375 546 44 938655 695 835 309842 48 87 365297 933 465 766644 192 909 939482 405 589 354336 48 985 304929 932 120 639555 757 798 656020 921 906 353556 19 213 718690 630 215 427333 638 64 581534 185 841 653806 638 542 617931 833 230 422477 680 574 817058 471 248 403821 869 649 607230 725 936 232456 618 191 367275 192 370 224062 764 786 36090 446 716 716667 726 529 639930 85 233 625466 660 245 455546 963 450 666180 953 472 120219 915 774 69506 991 57 677907 788 55 346651 73 490 817441 854 535 923848 92 566 561933 755 692 137259 389 83 18130 407 849 940345 510 249 640175 622 389 129422 168 913 199329 977 446 344666 778 559 11663 77 704 709689 792 729 417412 2 157 985576 280 24 192103 959 561 582538 140 653 143064 399 587 434213 202 361 467294 601 962 712609 848 930 52572 321 625 899121 465 695 343731 585 114 562457 952 623 944369 917 225 929835 226 715 393412 122 571 518068 103 820 947725 93 488 219751 759 467 611962 773 231 415751 925 820 446761 726 263 410710 62 922 680557 925 244 940355 866 149 354338 701 54 903649 489 949 647213 41 324 117394 462 874 396581 873 461 486938 548 993 663465 568 469 310711 59 274 138939 443 948 882520 521 352 730438 477 327 695071 553 220 330244 853 40 320947 236 742 553268 501 576 308367 36 699 423970 853 980 208820 688 111 490880 277 138 167709 42 845 819450 891 58 330777 68 478 479440 657 149 236167 88 1 155650 458 799 175487 665 252 492266 331 556 357504 99 320 100056 141 20 22770 802 240 343999 512 704 806091 48 950 446325 648 428 882051 707 188 111469 45 443 646791 552 59 278502 763 11 965036 583 646 839460 936 891 864338 992 724 971320 56 469 647707 779 432 152793 76 993 740177 851 943 364522 631 533 398849 481 234 132382 6 919 597279 60 739 290607 466 158 557730 286 572 732553 306 362 883395 419 593 469959 904 903 994597 300 545 748601 19 479 766626 966 265 50225 499 332 640269 708 324 944834 795 503 800930 296 907 818658 969 991 11062 280 605 201479 617 415 835752 583 346 430723 46 659 391705 263 466 392465 282 175 201548 297 12 764593 513 528 117097 279 593 696487 206 233 453654 971 752 307764 3 114 72435 985 234 285332 817 674 91207 345 22 150525 211 748 290264 646 171 335307 148 120 843890 176 787 844400 656 125 193499 632 475 863692 239 903 507091 125 890 73816 370 863 907750 988 743 971978 769 962 899766 838 135 57923 582 129 974242 86 835 200110 304 872 420061 121 833 844281 188 297 245388 664 356 164961 844 324 946760 478 822 317873 406 515 734855 469 841 720826 168 759 579579 736 904 795966 426 661 248886 862 192 984501 977 189 106607 19 832 962160 679 898 638571 961 532 515022 167 269 449189 274 316 532855 933 269 509128 436 477 913532 325 255 612693 6 908 987000 219 989 3329 249 96 775472 423 779 818979 494 751 417508 190 814 740505 409 137 7966 874 344 842246 775 37 811724 870 677 581377 111 271 677470 922 760 785453 899 715 949065 239 64 231656 264 663 959467 450 94 225246 748 381 890692 881 522 779417 233 451 72681 300 582 777989 216 64 999750 482 520 325406 265 567 207606 992 507 117264 86 675 253413 109 601 634886 479 368 784694 993 932 754729 881 421 563488 70 2 230185 805 897 717806 812 186 36055 207 601 508753 798 674 944950 659 635 503457 837 911 877159 406 710 484365 410 986 489845 533 849 403212 991 838 570232 756 8 63953 625 211 528184 703 660 654627 947 80 415629 598 637 998850 701 977 492226 355 664 411232 621 970 825015 209 953 258526 858 111 132323 212 385 330784 695 800 709820 294 927 238065 287 464 2551 199 777 506865 999 165 449308 472 681 144757 297 453 895971 944 714 48817 39 296 642785 770 713 514936 916 555 665599 338 726 860482 933 7 845810 482 385 848432 242 191 418539 447 370 107869 939 359 623470 152 69 743692 212 32 214412 33 406 184702 39 639 269808 63 446 176121 208 636 558410 407 75 832670 138 554 516989 532 339 363196 530 846 528246 500 820 296763 464 967 559590 751 386 999599 426 634 664032 885 580 543244 499 114 124894 549 789 349016 843 762 205191 769 988 983280 57 836 39990 175 903 653441 323 151 493138 693 739 931798 624 896 647616 611 150 486344 142 207 567122 459 24 316469 954 85 868303 638 323 140230 832 767 771600 322 991 626426 512 984 393903 33 700 635398 202 652 230421 391 464 699050 52 881 294656 372 911 933918 223 855 998502 723 861 500775 31 910 866413 986 392 850858 375 611 146534 947 325 158832 78 600 737958 814 424 826300 615 360 472851 686 90 883646 73 101 901192 189 203 889119 303 749 338220 978 217 964357 904 656 481484 763 370 756622 626 51 176863 489 741 884759 847 711 603077 755 264 672884 969 644 821532 437 705 803509 314 51 103409 539 579 451933 761 663 725389 294 865 498526 834 668 586683 994 79 202190 329 913 644728 506 921 717867 504 191 569420 209 434 811150 302 368 778892 31 209 500293 42 48 216139 108 358 305633 971 312 671144 701 916 729365 773 653 987734 698 193 776357 35 416 996852 117 649 290161 69 714 950293 92 623 539716 538 777 685987 751 169 468344 241 62 663418 414 476 199027 356 118 341907 310 729 347498 46 182 176102 918 327 501098 863 693 277244 622 73 457046 587 943 855391 458 260 215079 829 698 84557 483 212 148976 757 837 712314 472 784 859523 409 915 138887 601 796 321714 372 752 244231 939 560 289711 672 114 636046 926 142 655802 444 516 807457 832 564 119484 863 548 211166 732 271 242109 141 220 841639 305 34 678306 186 731 170075 785 854 934767 865 91 508814 314 352 296334 2 709 43422 687 634 857979 601 106 353997 482 939 502304 389 721 841000 677 520 810527 270 350 710643 498 53 812605 143 582 753866 694 806 299168 636 849 748735 819 371 756229 46 497 729423 11 10 992898 686 263 123817 187 467 530996 200 815 63780 718 632 571839 161 963 70989 567 875 675402 667 423 702112 54 1000 473536 579 899 303038 890 837 936154 581 64 977012 214 174 317025 478 746 820861 740 2 524878 922 908 884831 175 736 958760 873 159 643788 215 42 113142 670 216 290740 68 286 837083 681 945 423265 154 79 884309 365 761 493831 414 578 578004 714 436 852739 79 166 541744 818 959 730518 87 332 197896 640 744 825830 803 57 489469 500 8 189392 235 74 130215 642 612 771533 350 80 770539 186 529 308041 937 63 495110 966 874 991352 706 105 348361 831 517 946708 737 354 184402 727 46 2485 73 942 516175 813 564 566866 890 124 276736 756 459 921998 192 601 80640 22 136 829619 989 654 662921 757 116 207765 658 492 366554 145 963 189140 736 862 393665 807 213 820142 296 397 176421 415 914 369590 686 881 305889 979 548 734486 555 702 743401 772 708 951278 572 864 131659 640 781 707624 608 426 820910 842 247 559457 269 502 358886 938 538 972811 363 464 174779 895 400 907200 972 475 408674 926 969 153374 732 521 372817 816 650 463783 292 33 912679 178 240 928498 189 982 199165 607 520 982532 389 170 609774 267 918 679691 149 234 304920 421 580 893778 229 514 631908 483 218 241626 278 350 828421 146 712 42525 747 336 498707 566 712 325105 351 595 545698 292 23 884909 155 164 952235 180 284 415029 23 47 493273 962 293 248290 757 170 88580 973 908 73405 22 997 177541 432 517 381449 314 986 733395 21 990 951403 872 644 883244 73 849 35317 936 509 957306 110 366 451601 566 446 747643 319 22 859326 378 886 684212 985 660 183047 924 670 498062 302 165 532190 116 403 727674 827 240 434867 94 158 538990 777 827 156349 736 251 252205 824 897 579877 986 721 754526 187 472 71689 877 117 525869 22 696 815037 727 435 966893 201 705 883514 904 168 107236 335 295 425603 819 550 877133 336 41 759774 239 919 732678 236 248 944984 463 130 449756 287 449 158624 271 672 369538 231 427 813360 353 887 315273 667 434 508195 922 637 530589 578 262 60242 984 194 859007 277 317 934532 22 13 46772 31 385 431329 994 267 623631 760 603 486117 175 816 14469 970 665 106439 716 104 706026 513 714 402734 836 708 792643 877 668 825309 476 507 844842 204 909 916770 29 11 872652 359 241 588317 333 428 405242 819 896 820133 495 992 650190 680 126 197582 268 739 127533 28 432 922335 147 6 608005 814 872 814940 190 859 967679 576 284 836666 834 89 395943 360 368 203961 397 168 236693 349 468 232265 968 785 598202 36 498 620692 263 239 462866 939 807 137893 484 47 265727 11 818 581687 326 201 19622 162 699 253976 235 243 684770 127 779 431688 837 890 977474 787 164 948772 131 978 941038 248 741 287690 401 794 255009 448 971 236841 344 542 836812 180 877 984386 622 331 112491 245 662 410073 75 949 363330 952 812 137375 308 129 859722 50 928 46848 466 798 883502 692 259 997873 775 651 104881 37 128 823682 495 883 23195 445 422 675515 91 84 344908 458 620 209697 548 561 992127 29 888 157460 352 624 688757 167 504 759062 786 766 576596 153 889 1425 705 323 600524 320 341 936060 853 18 692745 279 919 287601 932 951 422192 47 16 892344 5 83 594984 183 814 317004 163 617 704822 314 846 628496 302 855 690828 31 113 565218 828 47 146702 660 478 517211 527 362 279311 152 162 206716 84 66 677564 683 663 715288 64 78 428891 10 930 200750 110 968 882809 865 880 775417 318 958 55843 748 283 296715 387 798 375174 529 993 295447 984 830 483922 514 662 942106 444 514 993787 535 852 29969 326 148 192042 548 105 488334 513 24 511485 327 941 615561 699 914 918072 723 208 45948 347 446 482380 10 609 885792 642 863 873879 388 406 368670 364 184 393892 500 930 870264 903 161 769360 945 970 758524 610 808 372304 108 608 177546 635 557 548110 267 693 545822 695 295 164682 638 152 606101 256 122 656371 933 840 453041 25 411 531692 43 878 383225 273 368 749103 129 832 271354 122 574 152052 610 856 744625 914 912 674687 371 908 796594 860 897 500074 286 788 909025 234 609 483207 696 440 564982 324 466 845089 690 817 294405 25 507 938937 978 728 442888 823 107 871018 513 297 860041 440 810 348511 662 362 726948 599 35 851917 322 568 210842 6 574 185348 329 123 287838 731 315 761476 673 78 407747 620 281 323380 794 863 392850 885 462 149267 667 340 206133 880 458 866140 707 259 383401 681 432 906962 472 781 751367 999 276 728822 420 782 301676 615 522 77825 395 939 578557 535 316 679905 436 913 109705 793 954 30891 765 673 341729 765 884 255945 103 678 38880 310 376 701011 213 191 199156 946 156 295651 464 280 703168 868 32 209674 388 37 600888 466 872 547509 262 423 596237 82 242 378162 430 53 409121 657 507 848494 26 200 952107 708 629 541840 315 665 94561 550 432 240758 486 978 285614 177 534 588317 267 377 547534 253 887 368445 124 320 78010 798 45 271692 599 742 14037 394 623 428775 310 945 774052 180 641 586904 203 780 275423 818 544 774991 16 214 791380 682 876 712996 12 658 428234 982 524 326642 589 724 563878 889 188 131535 230 337 574500 92 337 222500 167 607 774444 498 451 21266 691 232 976845 287 935 547103 353 520 367155 517 32 430098 856 297 333297 716 293 603894 614 96 371648 359 504 964503 898 718 186477 760 84 384611 976 503 523362 708 347 829913 952 907 893835 434 238 119753 266 192 181055 23 521 340428 925 939 558684 999 389 239663 860 157 611334 388 155 509031 305 487 13539 352 778 373852 205 893 40670 119 583 8065 740 702 580361 346 417 271231 466 243 356751 580 442 32009 824 506 981874 973 58 253501 136 284 792352 446 539 519872 531 46 797400 714 515 989200 838 324 202962 187 886 284485 818 50 883499 178 505 813018 511 590 371455 1 261 10833 261 334 113491 334 474 631799 474 628 489621