1000 3000 5 658 703 893155846 732 333 914663795 936 344 906265514 773 18 493977048 323 827 355349306 857 748 716587337 465 710 936044407 369 324 807339024 785 28 654881761 382 913 208918701 291 541 280469268 505 747 861364369 466 751 357639816 853 315 860193291 884 228 287518754 656 124 132787862 825 173 298505447 781 718 997998274 91 791 741552902 363 850 701799595 363 823 824308955 633 374 91137850 335 954 426494123 246 743 717794318 743 560 22532560 855 970 435907041 34 140 951852471 821 27 987653398 672 792 703148558 535 212 910999693 263 135 642558189 738 408 149784400 382 413 249271227 509 404 156963087 296 267 783260298 67 628 253432274 48 180 703753176 454 150 144662805 622 224 596468637 645 307 944802649 369 214 494472658 134 273 431940233 680 221 883761046 751 736 837123427 581 432 591523614 185 13 369649024 295 232 792924517 624 769 695099437 449 847 880010841 338 43 677789799 11 395 125439403 445 504 760960981 716 19 175915120 747 762 696628376 117 819 704807029 86 21 428871968 783 522 9712394 178 912 294325793 873 252 300951654 835 228 185851598 691 264 377865648 793 25 982329126 762 674 495347058 202 73 680743972 395 2 992530745 158 152 350539373 838 941 760215977 440 810 267032767 527 77 341341637 962 994 66411340 105 535 25509745 565 685 175734807 676 50 120105905 816 699 478808876 633 678 899632475 761 859 444456471 853 145 422724876 765 650 346613986 182 112 88603408 180 140 228834828 337 800 132310424 86 462 444039278 863 357 566988886 582 289 251888017 677 536 676030757 318 276 915585369 257 929 256799187 150 704 992380321 370 671 492171999 828 550 131826499 824 249 943721894 309 456 714311539 423 672 543067410 53 342 490039617 138 982 883194015 785 626 52991954 832 531 560947197 848 472 154561022 748 978 469240101 731 935 271819384 123 916 63736656 858 227 894659754 4 154 635184767 62 542 36350064 309 629 605597937 380 818 388027623 298 543 815153701 250 996 452313807 499 249 448677609 539 672 547009527 483 353 736631671 109 463 171967090 479 611 413171295 143 439 27460675 126 37 262246428 76 496 715429408 616 570 520559106 382 55 134078198 621 602 85403220 77 213 57436198 474 436 486983235 939 297 909598562 873 692 382533576 949 779 303720817 851 429 425757957 968 433 791740350 127 597 475289713 851 775 442104015 12 312 761691142 593 895 545518240 689 605 917642549 561 806 561926633 957 750 762011577 787 673 867923693 358 919 425447219 846 909 829428575 810 241 2123339 957 85 610866063 884 91 425513845 656 980 302081392 354 151 852140426 104 958 570034457 568 772 897164056 228 119 633554177 950 235 83611584 735 857 560038979 139 858 611514651 811 675 667851179 172 18 919947858 208 603 940116132 147 896 761535632 288 53 613937752 558 40 811260997 543 983 960883509 819 239 674150707 802 688 942671832 716 315 994703906 67 739 712806085 157 135 77212509 969 303 739053852 46 229 496927422 83 12 449516820 42 664 461935170 409 992 322509198 154 634 225510576 811 822 504276103 786 47 721749206 348 745 410930764 144 601 734510408 204 999 884946166 890 174 405422016 499 661 101498981 706 791 672696260 130 382 260254193 580 220 984388054 655 15 459488949 513 732 688939303 959 559 945776621 93 889 276694646 754 290 28637985 707 474 226364963 572 342 133355945 80 978 633096692 986 63 131215382 719 497 504930528 94 239 181274548 94 719 856244777 577 685 631352196 1000 359 956604423 94 36 212753458 26 648 504675620 340 536 853577915 313 725 63534302 621 757 228558555 187 536 895272326 481 212 392681717 483 289 472910243 38 151 23019378 560 85 855076032 432 333 880116449 886 731 746879281 312 744 808135638 617 625 127574121 388 948 720174123 69 924 301281421 502 939 883700647 782 737 73340194 777 436 114316096 108 198 78955155 285 782 632202136 554 793 882411647 542 926 776051179 974 187 545243965 203 837 196570538 300 444 206011887 377 800 981903408 860 142 368121940 80 935 415930850 567 282 564019900 400 833 462624477 950 213 740001165 434 244 131769373 755 38 495177363 811 36 293714468 837 229 689809195 372 598 17951266 675 23 999231240 579 12 571797764 997 136 944199063 909 191 894739649 710 798 465066624 936 872 859105221 433 958 231840193 575 883 42131033 560 893 873878942 877 618 26964396 303 73 503251453 297 500 122862059 99 549 341470103 532 593 258488726 420 877 521140916 872 865 40959912 325 587 673588021 391 825 938818709 608 675 525793745 426 885 949145623 1000 930 627274885 837 660 943977488 821 955 853830269 949 341 980732101 855 846 723658406 901 530 198675610 452 426 325843072 245 38 935537537 910 213 12443421 711 859 518556422 683 324 586804134 493 773 976773610 827 440 997056756 393 310 697040771 508 802 158242510 81 806 47432725 395 594 443545594 801 784 3948616 424 455 902093472 880 314 213941342 271 382 251701000 601 936 768974813 604 73 302099512 578 618 526376163 951 858 378817092 646 805 333174236 518 428 886205498 361 722 445097737 631 112 82828182 802 232 460093407 284 108 332308803 226 730 35446555 808 256 776191006 287 803 782038066 772 521 826932072 375 607 408465199 103 813 910818087 602 174 858288068 780 506 160908492 781 328 392502034 409 164 608653018 824 910 240988392 375 908 182894009 664 739 733673488 596 582 506400470 50 578 446515537 33 448 488847753 107 178 841665191 639 622 778428827 368 194 347335214 608 412 116853909 476 284 331351801 174 898 79611097 10 422 167993310 278 357 860666298 730 247 153743706 557 772 671675423 25 500 687062599 998 85 597615526 367 441 257094032 936 222 797702662 414 250 31281087 875 223 789802023 949 843 157631363 985 992 351189298 491 523 507557189 352 934 203136030 52 613 922574231 367 973 869608158 262 81 755149182 563 222 779111423 556 561 243495571 914 773 126017599 641 138 431726601 169 567 171548193 873 517 625447358 823 331 902545870 702 990 131512258 906 292 319066479 221 582 544845281 460 314 18882532 599 132 913005501 904 859 234408893 943 338 349723399 705 497 846326985 427 590 312078470 629 111 686772104 901 211 702011107 131 602 509600342 803 448 907367116 211 741 639940879 974 55 385332949 977 749 792931768 280 25 282474598 395 955 632652263 804 650 943858265 193 983 166143505 851 508 59311919 145 33 299102616 875 740 510718665 570 423 966997328 317 179 898467672 793 930 241085791 731 381 259356592 226 1000 400212771 617 276 523484410 597 138 783827217 459 391 144875924 163 1000 708343918 981 781 440171950 104 511 414013223 455 548 624497856 325 774 883894436 201 163 474359836 411 227 786865750 726 856 331467950 329 54 191649981 113 984 735344999 513 836 338641866 87 832 648625770 297 738 366054379 565 461 256709881 928 346 694285297 544 649 31597568 997 675 226255751 569 29 170227239 690 109 806218664 269 485 522811274 360 135 493624302 173 2 47127778 894 545 755927694 981 851 98708783 14 716 554991958 370 367 429397446 221 926 640681555 948 134 986316916 867 966 695992529 436 976 476460434 353 538 142312187 54 811 397144568 608 335 675193027 707 856 964166495 358 53 682220961 303 516 188813854 36 942 238856626 269 739 686824191 210 533 191400995 695 59 399520528 595 212 297777620 439 389 217761536 333 793 26481274 292 601 451112905 605 24 291764895 219 40 641591759 833 52 367875297 753 86 23938904 235 914 810549361 926 570 716119570 379 451 311727110 521 846 569497041 340 139 412113096 729 418 491568430 548 477 339137021 841 607 59234886 610 346 990323944 662 827 482683471 327 530 144920682 795 548 95996581 573 974 515564472 786 197 761686953 820 821 715677682 55 316 230299355 743 1 316655589 680 817 28486822 430 710 278224700 161 53 44189357 972 929 486795113 736 481 950489034 789 57 551680823 952 133 911100325 504 763 966084763 450 453 466249683 792 96 626739217 711 947 61055396 80 416 744164277 687 17 73880592 946 145 815993288 532 484 790088174 382 628 660016482 713 540 730994402 257 770 915708375 706 698 55583028 751 641 82907374 787 984 955111059 338 471 940440306 888 111 115724837 372 968 511653914 311 200 123468589 253 749 101212872 304 521 836852703 633 495 546220121 541 151 646218396 488 7 960605316 772 764 724166105 239 306 549173303 457 973 962669309 734 336 545556684 434 59 950264939 840 395 12629323 193 572 539306368 103 389 911273470 178 691 866993716 255 58 427382085 616 395 761497939 455 538 277430831 236 485 139715504 353 147 903338484 800 230 436859079 111 780 35906466 288 385 603105942 327 566 939163550 639 656 154113879 683 267 484300659 599 543 599462946 589 609 772958173 799 610 890158794 226 988 218276634 285 381 262960668 365 188 93396423 232 840 660165571 823 126 185968457 732 4 61210603 378 24 692565889 305 19 600836956 921 165 857085001 223 218 77961461 995 31 350249947 952 372 676974863 14 317 158841768 273 150 53724406 259 511 657694002 516 772 94536190 416 467 810278574 457 71 985902448 933 375 754457244 690 708 130292400 855 345 729222861 187 661 230475624 116 476 497347188 93 568 476137589 976 82 87682315 97 755 160110375 552 914 177441601 504 276 207300923 141 531 728654671 995 680 77974008 247 852 108163820 827 169 690702037 879 887 538927725 840 516 460987650 281 300 510059443 293 77 809944120 995 370 77124584 364 699 972964748 471 278 306161051 877 667 420199424 194 546 442876954 766 580 572887723 859 315 158354172 472 258 104992429 310 333 675529869 727 580 484082290 621 820 515904942 129 99 107917670 366 514 320535520 618 72 278499235 401 650 150577228 818 713 137768954 292 505 587671744 24 344 986986841 706 894 306711638 457 15 15942708 963 671 4556904 539 911 813620337 299 527 139615405 409 88 484556361 425 8 266159240 213 305 172306959 316 942 5621077 930 223 20124988 322 999 624097747 877 924 622052076 725 396 503206892 688 285 294759497 367 546 909945615 228 875 518447692 948 589 157260103 512 22 895779720 289 475 527092234 515 883 323316841 388 734 142749134 349 426 276969277 83 903 495996279 297 995 592178491 668 290 31141173 295 391 723507467 540 847 944257483 554 125 991544233 53 356 60857638 318 327 336223469 772 362 824984971 794 974 421070043 862 431 120212517 79 420 107605378 78 844 842028341 353 430 531557314 153 876 13480451 197 345 782577809 318 911 191936550 186 975 395523490 514 468 825471989 290 13 873311414 240 731 331258813 459 355 176992221 319 342 17561675 100 848 925492172 12 402 679864432 334 813 571898272 643 990 49262507 911 561 990585553 124 462 482078945 631 767 453739262 181 925 829605115 157 305 140834958 830 142 251184388 353 790 603354495 147 956 705298894 184 497 730468861 107 940 779660849 40 146 501371407 55 205 677068003 109 306 202887834 715 469 695048664 990 933 719334436 577 96 263841100 348 750 67701792 98 465 95058613 806 512 946031413 364 47 363003016 387 804 658808809 637 370 598496677 524 749 790469583 246 355 840945168 239 90 534664765 382 528 438987092 951 938 783478677 918 648 843830878 546 220 22867885 829 183 188673405 191 12 446452865 216 945 695712797 226 836 748580667 149 242 798655166 993 841 23650807 913 581 98863528 118 578 29701096 383 197 930113810 229 591 675186330 678 359 720935935 193 539 63860590 420 867 281557617 432 186 807236209 923 220 174618043 972 112 925001354 505 890 4739306 553 910 939332314 232 814 404957222 436 783 822318563 627 823 831615290 142 520 581615785 415 466 70357527 143 468 858720030 401 981 461848290 547 291 661256558 560 996 996195238 899 924 431176344 453 756 903644583 988 765 888298175 256 182 666818231 645 929 224052111 591 159 415976578 224 404 751245690 860 489 26601410 322 860 309822552 677 217 677018622 704 519 790771354 732 606 450596065 182 654 55396936 134 479 986524996 554 711 865636479 692 709 982843629 390 59 706753182 494 625 265695795 665 121 110565321 782 110 104964744 386 933 64464706 920 356 392227598 174 251 196308040 243 993 967110793 195 901 336544340 755 894 151939160 327 397 387219488 595 799 162411387 200 512 694634175 204 889 181878040 625 454 981042525 750 68 727505293 463 915 927583878 582 28 223167969 50 585 453624364 102 400 603004272 996 771 361882657 535 61 359462303 407 321 367209103 624 917 638157799 324 661 802419201 257 259 822352718 760 378 655277132 524 138 878255822 487 351 575786240 479 992 826141216 454 962 579582225 751 732 733945556 940 48 830794295 895 769 232872599 235 590 741487924 197 626 149852405 138 397 193475136 201 506 2665494 408 511 384878191 784 353 404752207 580 331 888722909 207 846 599327175 862 535 934923264 921 875 703238910 308 447 353774809 388 799 967095887 329 802 300029127 432 847 666530143 153 216 136074734 302 175 538439155 276 955 251933527 158 503 849465249 578 755 612090127 976 35 135333605 830 305 218022810 58 542 516485861 987 10 488812159 42 115 766288961 4 89 103218616 242 647 424448623 353 440 873062039 482 487 319179364 448 177 967993276 864 882 201586465 190 234 759003828 529 392 557575366 372 718 104295517 5 799 124169187 72 355 901144976 585 376 4953671 195 501 658501613 907 819 84958093 237 718 111824535 844 845 205558523 128 660 925138525 921 481 212867865 667 704 906351233 274 130 39525975 300 633 789470280 201 408 371812548 898 275 667260006 136 84 560291068 541 527 335224806 760 798 662507093 355 115 935562145 867 338 998348885 827 248 473288585 255 799 158092196 444 670 61000371 385 197 748092836 775 147 579627924 958 219 827334944 577 337 298525027 460 150 604376409 457 192 193384132 583 776 726083844 615 138 619983508 512 29 149914759 345 490 969766167 301 604 970227368 388 150 41851578 733 626 656644869 813 912 12672801 405 831 964463970 450 71 222050851 404 626 482798429 720 468 48586139 679 332 813765867 521 484 261425097 138 303 122968048 546 522 306796909 209 624 518054216 332 846 39040226 214 583 242487208 693 206 517650279 706 833 371607888 872 681 788074621 206 243 271508307 812 407 109496131 167 410 212354193 394 933 842327260 833 143 210806618 765 311 554771132 612 773 856798809 889 335 845956429 808 661 293017362 349 677 272610383 430 784 306246680 38 234 738548747 30 680 844869561 573 743 139964051 791 582 372856184 359 551 504855989 322 800 998966468 78 991 483252875 977 994 333605105 377 221 138669388 479 506 15836140 902 592 429029568 872 796 489770539 413 42 656503743 862 908 327610073 133 714 730630093 729 444 600354605 453 378 167018242 918 545 158168891 164 522 361843255 649 300 116231541 761 77 152080250 230 842 391832516 363 738 407784736 446 649 280620116 198 997 722727359 510 898 166503247 882 621 111508150 331 235 859133181 885 269 802137713 386 852 502197700 986 278 556090925 609 575 204569605 769 418 369003865 704 967 254794372 303 758 768125106 116 866 722907285 79 951 904262671 249 160 798287284 969 637 744962405 77 557 246798126 735 524 647191744 795 490 532373413 244 226 923325301 144 537 866823532 400 146 669438638 235 999 705560580 375 421 296699989 521 920 685551650 161 36 654428033 366 506 36362304 319 869 233465626 929 412 82712512 229 948 297678431 464 641 199200822 293 319 690215045 169 125 222734777 703 841 883497374 524 360 740857090 506 707 713383434 819 457 924881096 110 10 368416047 155 324 40319974 992 256 40404139 635 979 400830281 53 371 548909171 704 701 171472821 312 940 124695468 26 964 917318108 539 222 191297555 872 92 776478659 633 651 55642895 37 605 55020801 19 497 430812314 410 200 463666023 353 394 502542032 825 677 685518034 509 35 650801533 220 466 234332099 540 320 958455258 994 198 152394685 983 261 192534438 468 374 227875475 216 667 564138539 182 394 180792565 268 57 63634555 204 128 169885743 521 734 713910445 985 881 299808043 391 698 292026710 931 86 874460368 699 680 989254318 515 982 617259324 592 983 846351448 582 698 659660579 917 419 886715816 244 183 793805910 240 417 650751395 388 207 861783649 263 510 893621326 839 159 911926167 810 432 809959950 280 278 899246579 745 544 207005566 224 531 823391517 99 270 114198315 123 186 164461527 442 654 802193406 444 191 857506611 323 596 640901229 939 972 482065535 106 892 514293629 678 41 250519411 23 529 295178168 393 425 118396359 434 295 736345242 203 818 832826780 218 329 239110504 662 59 591605594 995 73 552289131 626 617 421408767 584 25 74058246 105 541 785094485 701 737 715681198 28 315 71370838 717 663 862541688 334 828 552045014 803 961 724137465 897 154 784343838 768 926 29051080 813 151 710731033 429 676 481399128 408 623 760281777 570 89 306078279 500 598 287707485 356 865 605098902 19 249 84326305 174 320 139842612 453 942 92627764 912 884 282728335 671 509 949095699 821 74 519012939 427 648 932625091 449 777 651343905 838 967 788043024 112 179 959351951 42 780 561144564 86 43 108366980 590 226 920598714 345 26 621947759 397 2 747026871 234 341 938721639 412 131 508327728 415 977 704216057 275 457 696709413 559 544 785777453 298 608 216283615 343 810 142142576 226 894 231232422 44 766 583613695 206 458 995533052 166 949 796536945 64 115 156885512 6 811 731231689 250 846 685641138 930 602 343910858 917 170 497225609 431 687 463374985 482 563 971190337 4 592 676517752 333 552 651505768 49 301 763827991 206 602 652229976 681 757 839638134 846 965 569106727 238 731 706081183 150 376 675503942 285 558 601572401 42 847 248533119 737 650 970738573 102 645 344116163 813 959 638146399 769 288 204536384 396 809 144235388 169 611 707229576 900 16 740122817 389 181 213861147 715 205 561012890 974 74 437766679 785 632 636615346 813 773 334144918 446 224 271312090 87 208 549947989 786 400 166002078 432 830 908894470 756 848 761813766 889 15 658675874 152 371 292588517 642 60 124620818 503 541 967080073 284 14 382346111 847 685 762088176 868 14 182717183 872 784 585418383 55 842 591434680 572 172 288577576 999 770 786359464 925 932 430214046 512 120 935293549 987 225 744156778 694 123 944902708 470 328 372902059 532 771 794365119 570 766 36339602 515 198 326938053 311 741 54566770 461 178 692713800 882 978 423873483 83 703 991668650 502 341 782239584 586 641 411645400 992 742 600274954 116 810 303037907 611 666 844908184 801 36 130071817 215 167 424135637 315 631 534196363 789 752 281154498 537 702 99705245 576 166 573820440 280 819 202604881 978 570 179522404 746 377 455677295 422 314 562829944 30 321 830744598 931 95 458556401 846 980 656838392 314 61 189293722 253 633 246207543 293 608 403714253 899 484 506469940 314 532 459066249 750 784 355558032 47 163 366553981 13 24 549534116 931 896 771876750 169 295 38615855 702 478 107930243 717 810 654275721 868 723 506734032 690 665 4186781 628 681 661972381 599 841 550788334 838 281 811540333 252 446 972921723 339 402 691755111 613 223 256735020 115 763 789399080 646 346 464881496 825 72 177059219 906 223 562752647 748 820 727159426 314 680 934459229 214 66 283594859 482 718 315055421 372 607 948993874 919 802 29465442 916 73 258657578 275 216 177603594 571 658 60505025 990 444 288043562 641 153 60297244 730 441 71665511 550 689 496791559 820 618 101801916 398 310 346642045 752 713 856368568 571 824 525808780 866 474 966212548 280 28 713868898 709 635 935290333 522 448 158967868 440 167 998368177 425 460 946915173 775 194 70153157 478 932 153841743 85 282 581959771 156 652 557885602 364 124 122617664 281 163 77879092 122 461 802363612 91 88 757521138 941 233 578822800 429 467 164643512 528 937 987479334 479 85 284623314 390 407 161939371 260 558 593764518 506 804 151823135 766 128 230621563 973 716 459360056 99 819 352742866 383 583 51630159 474 414 554489705 50 748 267068798 3 240 91799187 70 11 891078887 788 987 471115626 832 666 852305844 43 593 684254314 790 309 122799783 203 690 856631813 770 323 584235548 544 981 866563695 50 191 913346425 391 343 158572986 296 215 1966044 537 949 397363827 450 795 234478513 940 295 679552307 50 943 172826296 362 189 342809073 725 913 814885644 76 782 927366565 404 780 375986903 399 379 795070489 124 368 274104152 893 466 155515906 836 352 412689789 640 439 459140510 702 510 575505162 608 2 345393464 308 386 461050733 311 51 54499417 742 510 397909924 521 547 330481048 684 86 497681956 392 149 153210068 426 652 690663567 160 737 32789048 229 584 63770331 108 285 500862717 807 187 617598903 846 823 313078643 176 523 864875715 980 180 181747449 718 708 127478903 50 715 940659954 995 255 977287992 999 420 873221849 144 931 634669210 755 312 216348846 583 788 579811562 764 295 81209147 356 755 291897825 150 257 865262321 24 742 912744391 115 97 950456382 518 436 296733249 388 653 609812420 308 343 681820117 290 253 708277257 561 590 543330031 486 355 557057785 519 374 524409255 841 1 310314447 348 486 571508107 293 111 852967783 427 566 512788687 819 520 32056141 269 80 507471163 500 456 566324171 991 734 802524775 649 946 593874723 123 85 891550867 564 298 986176675 172 136 953790834 873 453 948173443 86 690 526162799 835 764 644328466 590 614 727773311 807 37 990795413 816 449 594067624 871 582 986895886 303 338 231077387 114 375 89619235 270 200 986045419 466 779 44292078 315 576 509307759 36 126 414921002 217 688 306269425 712 739 967573495 500 877 149126447 257 879 98554430 398 101 72324162 337 703 851209689 959 467 839807075 841 190 581137144 876 257 559669795 453 254 32966771 628 435 260890355 196 981 482465428 58 587 886545623 473 334 213587064 377 419 449579379 371 709 717674471 729 581 701945216 71 263 853125677 338 461 501312037 719 953 268551116 353 404 392713913 419 791 105968601 659 896 322432051 387 378 931634622 613 290 245325636 894 966 928416136 539 528 542402622 293 981 234564161 110 460 100513906 449 307 102937265 87 534 792397817 585 31 510648554 219 553 289958152 781 868 795661881 97 753 233128659 805 478 804908474 718 576 206079111 269 430 917025323 155 716 849352105 520 593 114302344 832 488 817469218 120 937 830473727 787 402 196246928 740 837 159577979 112 596 937587427 585 1000 584084648 458 794 477506283 752 134 710380557 931 663 936543833 756 43 799730321 870 801 678091831 986 201 83799749 280 832 34840149 9 751 350274036 110 72 233923015 492 229 175540460 907 311 539128963 341 239 476418492 220 695 375830350 281 760 546116709 602 326 695295807 562 278 446062366 789 6 292997047 255 962 885948927 559 443 928777725 609 664 536694546 686 227 832959093 775 953 930898862 725 310 669313650 276 597 634658252 953 926 149814512 2 362 311548766 464 757 781933379 719 309 777266461 188 800 447113334 185 375 202962426 385 44 933916633 486 720 39515365 625 414 22746926 94 937 65634304 337 517 443141333 883 396 508293432 266 387 488401809 522 455 996955302 971 469 837066015 544 131 826941745 336 697 684615340 942 109 493983980 329 171 395045542 966 884 752525981 389 730 494619814 665 672 875873480 879 370 877723716 16 415 280108776 976 926 499417469 538 294 46900138 928 304 992034832 718 310 874613773 917 979 799543290 564 708 204832414 190 594 326815648 161 458 683684807 530 322 110358679 415 22 750837877 526 368 506328489 716 323 69492492 623 942 691179908 662 999 48372997 221 343 830515717 858 868 471224 393 383 562839720 569 577 645511604 94 26 698345706 429 387 671374830 300 338 509495892 688 950 184140312 947 133 194039711 613 632 893052943 84 212 234233253 633 371 70511294 696 373 470463609 722 696 927245581 710 99 150821324 696 47 765272162 710 403 809124063 222 174 98173867 653 578 857289649 968 661 295651716 801 355 118564111 133 358 461709564 947 985 244735839 641 488 900020604 444 96 869876218 630 223 425593054 976 437 992696298 386 296 56978194 192 453 636977838 321 133 193226521 386 857 54836108 322 317 961832963 901 323 212517227 528 531 233713919 436 720 90872892 121 678 480008256 528 989 755226546 203 804 187165643 892 905 297906742 252 789 409616409 742 21 639976450 82 609 926425337 968 706 602312111 324 945 884257814 441 437 476328784 438 156 358539720 822 711 992633992 258 640 976027896 151 223 488348275 618 949 555657585 396 828 636385599 452 395 772961181 481 465 809798220 681 924 890654582 519 288 962457519 149 696 178461304 989 404 279114366 852 93 137812726 663 493 751077768 537 891 357754096 280 569 445416245 999 967 625712176 760 499 99822022 279 541 245685276 409 2 710060339 479 973 666588620 904 756 122476800 243 973 594120578 505 264 731999806 813 121 44522787 26 238 686853577 828 801 424322871 387 410 858451139 520 651 562539433 750 20 453014055 479 59 431509501 381 292 246879143 56 17 957687563 820 74 388803315 543 92 249688797 84 794 998628611 608 20 4355644 148 25 28054979 965 288 918902540 224 785 885353932 778 586 202375514 275 6 514270775 223 823 524835773 428 385 343603475 275 368 868661097 822 922 137935924 390 341 693325363 731 880 316434617 841 612 748755587 641 489 865473553 304 400 674538340 436 298 564524992 164 430 789575051 189 497 884918221 590 207 309335537 547 8 101853147 300 790 236082766 592 330 297606 896 395 862520343 434 966 343892471 237 623 473998387 286 654 453954639 326 857 277756181 11 195 719330059 426 419 941509419 283 970 462802104 494 201 694639253 348 775 518674054 571 746 106811858 880 791 918079186 772 836 789018602 573 900 477730496 113 308 189767704 496 935 222755785 165 417 467245934 469 834 171982581 616 641 487247550 431 280 696473471 622 65 468168979 381 634 122360587 950 741 708614646 604 930 753463264 248 533 414499625 654 432 715741291 583 252 887235968 508 517 579129535 215 198 709514001 489 451 684986126 523 901 653126407 211 349 30592501 98 449 291405018 882 194 567684950 503 149 851764128 893 847 853903384 875 236 25256030 694 728 285239969 221 614 196142633 610 774 888325062 135 393 471448050 915 515 906979981 681 550 884601290 946 607 876255334 341 337 672168969 463 183 984575695 375 905 36297797 647 78 459685701 312 470 943758042 101 559 820606759 210 375 735825317 824 529 50050178 799 787 447605853 204 173 694100464 639 104 93217144 298 202 125840745 571 64 337705267 261 747 892453786 538 527 981945554 618 901 424044680 729 688 662715564 387 763 185941277 733 608 971950720 133 141 287876890 343 261 854414078 766 917 172614257 90 805 601705624 948 544 745875195 259 99 87856228 610 960 296329605 657 208 53936933 59 522 227158267 804 738 826346630 89 582 170642721 159 616 214649150 456 150 997778390 964 817 985771675 298 168 41137765 536 323 358330871 393 170 568535589 384 833 334843164 769 926 34724102 174 423 893284070 11 452 802516143 379 811 855938143 536 44 952460575 187 462 543592540 122 189 302546226 891 935 196197948 68 805 219547237 635 842 688685670 184 492 760986289 352 995 46448858 775 20 362923309 27 524 411479664 593 214 861964829 430 713 879952906 528 971 542493178 790 502 510965285 241 62 343292830 249 495 509034786 811 836 345424551 809 877 968538671 691 520 123223498 356 831 78456155 674 523 288899012 122 118 594719858 136 39 172075166 730 209 850775337 655 100 284495424 95 531 867063034 237 609 629230974 105 313 836373491 397 830 330342309 226 59 265560286 937 485 562690847 615 731 355797840 400 50 995473152 702 156 516724502 314 365 404190401 495 517 405399214 578 949 814291501 402 391 573929393 49 726 670235677 430 576 390163837 476 921 989018306 641 851 743262468 520 150 28715576 984 300 551034412 456 838 37954780 678 165 386951346 897 80 706414911 11 703 246778907 622 625 732919954 55 412 494483038 700 810 134853523 2 549 223503714 265 578 40429137 114 985 874079859 347 820 892678236 54 435 184736908 457 887 289442735 250 11 345224249 180 312 444791095 46 218 576805852 261 767 588371290 479 426 936876224 706 261 644210316 18 692 861723731 714 357 481058721 228 304 412734979 331 605 864319763 182 54 733115612 102 246 299225308 402 3 192193897 487 627 371939305 324 716 79705016 245 809 209081447 477 283 123540044 286 138 954443584 842 460 407712551 636 160 160958120 330 941 869264488 982 362 484806947 321 462 723936859 659 910 38158913 528 68 809929420 219 580 605246535 829 29 957940434 140 736 104469100 502 473 417860591 765 820 454520539 376 453 75086315 271 781 404371132 281 852 401797066 862 750 886188706 199 814 153118267 202 954 616785526 185 958 793165480 557 841 27869531 700 413 951434343 908 836 574061122 697 27 782807045 600 243 471105536 235 959 108640964 178 811 489670207 380 199 58890661 978 297 649286368 240 378 911878763 100 771 979644451 428 68 273563772 504 787 950266375 309 51 500267897 106 589 823659410 312 909 534762842 34 416 688369434 456 890 614254078 298 590 313349233 77 997 591827475 67 548 352141834 220 980 389449991 719 806 948957036 890 490 213034825 10 877 83576406 488 149 469484531 668 931 631101420 783 956 613436757 840 136 319276469 298 100 900407184 398 407 843306996 416 975 246033962 797 53 88165528 503 623 325787751 911 37 38406843 590 272 398050559 670 370 797964020 167 72 106807780 715 1 683969849 135 120 570002576 444 220 541809002 367 127 20828186 360 32 835900493 463 635 974052859 278 613 300979769 539 47 475406587 705 550 245530077 622 857 255752652 527 316 180599809 373 905 887595199 12 756 141095125 87 878 203375415 878 279 276878904 437 928 304221514 872 861 983937701 432 710 162863716 584 809 63627733 175 88 994320683 860 451 429498589 113 797 725874890 837 784 571992913 958 567 202497560 130 808 356112883 845 530 309317434 218 86 690980779 938 798 185358298 513 735 131159425 410 860 684904537 144 640 338838791 637 524 47449030 431 382 837699833 545 427 22490922 710 636 428126241 965 677 809535571 528 278 348479409 32 835 41138039 863 784 240251757 628 294 296561948 565 66 956547043 513 885 717524131 978 489 716304027 711 378 820022124 789 427 987169675 392 442 783614363 675 256 506095593 139 294 425889044 196 238 17605431 947 540 524124893 129 416 345160262 300 394 550583776 316 24 441920822 843 70 378043677 301 98 361576874 352 108 386899846 893 390 841678480 1 209 352668158 434 681 788305621 985 518 854951326 801 220 174769599 577 7 752373361 481 725 933320379 2 305 5715753 259 120 375226193 39 121 91504988 358 18 865915081 75 304 127025702 203 836 135307436 989 304 127276506 92 651 923326733 452 91 609836473 819 685 304455709 192 267 705702918 377 287 818473388 565 777 919910983 225 200 998146615 579 269 166057322 546 260 770198419 310 577 744079875 861 771 817433767 246 329 536316221 119 172 51407111 969 200 950932973 403 369 300936752 941 727 55062549 860 167 258532061 981 302 938378159 870 847 782626397 912 556 950442244 165 532 64522564 171 267 580582256 744 351 239419666 908 969 538818744 20 996 123479004 779 319 657831860 973 334 413129168 813 867 455605574 421 356 544674271 455 886 595994625 938 772 593387218 29 616 12994904 929 675 633586219 658 285 434119570 148 453 58502748 204 833 104493812 187 979 567325958 335 992 614076265 372 556 50538873 841 182 573096562 960 464 57523868 949 607 191811096 627 406 630785416 835 312 992208517 556 221 50507617 299 168 888601331 328 154 176044009 504 464 277172469 633 659 183380082 148 523 260741094 242 836 214308450 482 781 175011599 997 235 815137378 304 884 300132472 230 68 100573828 16 451 706052319 318 71 277537579 428 529 909692685 674 546 255794723 488 490 114446554 375 915 651289865 801 247 411318241 361 928 489415330 746 730 827105737 156 389 827799313 808 477 356657743 874 570 88537785 751 251 393565015 74 24 143742650 661 133 965372345 961 875 722811309 94 711 489332025 895 46 628349184 251 185 563643936 826 741 649829689 955 409 276402183 412 531 488192802 388 107 958251803 762 506 370211941 39 630 62752274 390 351 962748498 217 915 456402987 227 99 476102708 753 21 766922372 577 938 203141290 245 844 929272302 977 49 283189799 120 562 948519169 977 855 978873618 131 469 33401585 564 862 649282970 4 438 291115200 568 436 602497591 990 161 45962624 368 146 857329774 55 508 136597814 187 783 417858913 722 828 75761556 119 282 866234983 909 824 765741371 523 599 985062554 755 261 624678508 444 685 162845224 202 952 547101458 136 152 250017582 796 399 738220069 122 546 856855115 9 894 262500511 124 215 23470129 17 218 764432806 758 64 662600644 954 584 165778545 466 47 180225700 421 964 31634256 964 182 234246370 223 726 757627402 893 783 898398176 66 608 457353419 842 911 127647148 456 960 603809364 746 507 752487620 106 104 266541043 666 308 883455719 520 589 70285903 513 264 876340791 408 122 931692001 663 712 356918925 534 653 867988129 302 587 831167766 74 782 400772213 451 27 359205703 84 345 49590258 900 936 749409308 775 701 273276545 230 236 436635003 418 133 47281752 560 706 791051358 934 786 16973690 571 524 623794160 170 352 301641091 914 647 912096391 475 398 339045858 187 965 964337492 499 900 491511930 810 739 239465241 373 501 864201986 406 546 300655834 642 758 508273103 921 343 282288432 531 621 687000391 10 25 502920304 546 808 705449748 699 4 37246787 601 875 744563312 125 7 7201907 552 998 490659344 191 861 504095037 798 67 193143061 853 277 477184983 743 55 836523395 266 446 912337802 242 512 807711101 576 190 94153112 326 556 86751228 866 163 465678663 723 79 647566819 671 244 428742572 840 657 543290813 214 326 889247877 401 764 963255819 330 732 763603773 49 119 297820462 834 467 927350906 827 78 674347540 153 921 319849258 294 383 595391444 512 415 118874108 645 67 190200835 984 90 680859495 179 600 650506851 231 672 130547236 272 336 68136736 688 739 552211045 392 688 746028859 265 180 183855877 710 637 603872105 159 724 129977122 349 44 123392323 271 169 215625567 172 929 196231832 652 127 188835451 492 899 645560632 899 266 750126610 752 397 779956719 715 799 859292921 238 216 207523468 621 176 553461252 850 145 300344001 174 263 502545985 720 961 953694880 622 617 608529898 13 336 762501349 29 655 918097546 930 440 823186805 501 569 219703965 755 270 809662292 333 532 612216284 468 582 217602397 464 583 218355162 695 550 589000565 837 434 529761157 183 586 79163038 82 509 193875360 277 260 469516840 448 755 654138403 624 516 218856911 736 314 851127134 431 456 569379645 758 741 86625183 602 978 55807300 876 534 282822181 324 55 613178929 565 544 333260076 296 546 843032898 116 732 745123515 464 689 549133975 125 320 253857298 873 145 192854511 550 235 9340628 59 991 688344815 63 290 550914716 495 580 864909189 775 735 858426357 249 305 783751193 671 270 160359193 435 588 728462089 221 518 255531061 162 492 12761854 286 651 297580036 203 325 363755778 987 128 750203292 841 823 741674904 499 279 484598719 258 920 722190989 594 759 769792646 435 854 890437739 998 376 171112210 710 335 353878727 219 916 391938028 456 898 16991100 789 823 331033751 103 229 36469000 732 537 46889199 42 868 132608492 187 318 387659785 786 757 664275106 551 244 486936023 25 936 266848599 26 918 718049517 262 117 62381967 850 910 53784220 114 109 354200684 923 97 445444094 671 890 715965149 236 214 363113936 1000 41 391236133 141 485 201824825 509 984 866918083 261 865 496236581 82 356 653856649 243 792 280140573 135 552 272446064 619 2 108525185 91 752 597230385 347 542 287819223 243 38 523662177 115 29 341045833 554 215 848000738 97 303 381889744 531 340 314699763 447 808 351793857 642 769 607261809 9 467 716779082 147 862 333673880 251 217 182332729 359 360 108496792 93 915 541065743 939 756 99070443 672 888 247859592 96 821 843091402 747 885 399508306 454 807 694458499 673 610 815344212 45 92 868467837 629 148 201002334 300 8 343245825 54 150 359547590 836 740 771933630 723 435 719035148 359 486 468921140 117 354 625925620 694 526 604651410 490 396 585015266 638 855 252372501 839 757 973527484 186 348 934207240 38 685 956691505 177 638 305207664 848 96 111610727 978 277 139058915 345 147 410697566 100 514 806786647 560 539 437683693 69 680 765630859 372 11 10086604 168 348 437162854 561 858 353624102 867 677 924436642 636 333 398924138 576 794 157902339 960 892 146496868 201 246 880121263 767 497 710969135 34 318 1361089 521 616 903360276 279 12 88218629 892 119 870940677 733 815 506246743 193 72 844075914 228 379 319469298 187 529 317018284 902 723 693623576 607 947 951247725 617 459 168171331 303 787 572924706 619 764 269764900 577 975 476729574 427 77 696252087 463 771 82156175 511 498 403467127 315 515 133554247 264 880 34650450 629 357 729183087 344 74 387241365 933 969 412751176 361 499 367111755 218 700 475937734 180 37 279415327 479 127 521375003 134 780 33221111 856 802 604754672 208 247 857088316 391 771 387426072 519 322 30078665 944 208 382379675 345 803 809385484 479 415 482637966 445 797 108911530 623 353 972667753 47 623 111970782 999 273 478879876 976 891 63292534 207 396 334228780 367 636 626617026 353 74 232940000 251 264 866445971 125 992 428514791 329 484 1159426 655 98 925061355 421 667 146484618 473 47 805983705 755 521 70478828 953 695 933908997 459 549 764107259 457 186 913938134 259 239 718571692 698 450 382410711 411 486 586211734 618 864 915867726 696 230 469219674 396 89 895524495 175 161 735970285 422 548 383618857 796 494 63220554 297 56 129905873 228 927 312441758 606 412 645361582 441 629 584905461 995 942 36571314 931 846 552650734 634 762 615160659 362 150 350172363 824 78 601275422 797 945 394899794 220 181 168492159 513 435 124312052 43 90 780693426 414 487 393243835 685 286 388951361 761 102 830803153 357 740 526427533 7 253 28290723 48 548 418913440 842 573 264087329 898 870 401891001 971 132 627992616 744 178 298306665 710 560 318151148 206 307 406407732 388 928 737463457 829 161 52885928 750 497 676363170 425 634 936189182 448 872 45743767 654 795 709803095 46 989 566716697 105 522 114117547 185 868 286529360 653 190 113320154 46 471 712084251 754 244 220483196 409 699 480049425 862 956 11884027 705 290 245586834 202 16 375725321 287 580 424684866 327 419 356397035 463 651 960334032 687 606 74735732 543 611 936251322 387 527 929105678 258 253 256883715 325 949 204288406 574 881 489005353 685 883 802583277 231 158 965032286 514 919 805353455 748 13 119222571 316 274 971451199 403 874 27632780 221 235 525468185 438 720 154264693 28 645 316606129 400 696 356857953 161 555 82559953 271 843 154106905 320 747 2000469 353 811 447582352 137 177 187952306 162 26 865520537 380 339 779631948 255 608 703170499 858 672 256973843 987 74 292183290 501 967 425607552 651 245 923464036 911 769 392646647 705 826 70663161 384 83 430630983 205 342 687953275 306 694 977582206 798 226 309006765 885 160 896094618 263 860 346455712 349 824 224456180 160 435 697442084 103 485 721634663 961 506 368391585 927 609 884889018 504 63 691298785 254 927 549854443 291 549 840079072 492 107 53074613 529 357 964729935 314 429 310371943 797 940 657065027 140 695 810829404 713 374 52324148 256 704 328064228 6 987 155669172 862 875 310921603 996 551 519328936 633 390 924468617 952 144 916605458 192 465 746646276 456 176 366310373 660 782 691937711 368 619 919373485 526 33 7448033 91 782 324075829 508 60 101791690 57 754 157713046 662 308 18053538 98 539 598685266 224 848 51689063 58 561 281297518 614 76 960074715 333 748 848493508 317 417 601881577 659 270 120445607 53 340 107635993 526 623 336058114 485 849 626878528 629 14 123957695 796 811 563714094 101 755 668438338 652 389 36962197 747 615 341388530 911 128 63054693 255 726 393652990 111 94 439454929 715 836 930919333 168 241 889622754 903 853 736736524 501 346 272274445 94 135 516493495 853 490 729933432 84 670 432776348 254 533 981048484 778 933 833716347 604 845 127598369 465 966 978081583 897 628 835523399 103 39 118063286 362 683 740176929 489 955 665362389 51 226 789390906 448 735 309832791 564 579 946640834 951 780 845259420 602 911 903306146 368 41 521310342 204 956 110934429 360 246 859088808 785 112 42010520 837 289 427111653 185 351 181592673 750 978 493182451 468 20 369777317 284 867 946099706 563 870 156989011 555 457 434854564 564 603 489670857 783 443 539354138 483 70 273503446 506 671 456451774 830 102 16853428 977 68 454351069 283 501 471279302 609 364 234073736 947 820 851957234 421 155 574362056 186 883 359026862 849 75 864324524 566 605 979028672 59 15 500883487 255 43 947505523 993 306 730412131 701 22 240369874 879 648 188143226 225 723 194448188 11 605 747907005 431 356 668091214 689 388 245330102 560 389 121224846 539 790 684114199 350 126 930335955 698 206 28310964 727 967 746924347 901 566 761341853 578 174 465900208 962 959 919037422 910 801 947799485 939 616 549158652 311 508 382001652 223 642 75431852 970 231 562959311 650 577 629424648 72 177 548911372 587 828 326622317 196 419 770930791 282 312 675667896 401 419 58063715 864 73 744161233 904 499 765957311 701 522 385869714 645 489 239824387 735 412 532073920 319 563 59842854 32 632 592760319 242 362 933170127 764 222 513149968 975 275 885839772 713 566 305216072 363 562 765464108 695 815 854462607 612 474 913281239 787 544 915112809 916 595 361336920 175 823 388765330 537 209 76033703 416 364 461171709 277 397 978075701 861 337 578846379 815 354 743883547 21 543 775401066 20 620 696350634 420 997 772101894 465 272 625817503 925 159 331885713 900 559 576360643 884 427 253905060 954 903 211798626 77 280 203498062 976 488 715548922 849 865 881801803 916 349 481883806 6 600 12394879 155 592 824647075 776 488 76765448 56 96 879567674 639 512 106066683 224 886 777040427 261 932 201821814 398 106 784719237 603 442 989756292 174 569 483384273 999 686 736498575 189 786 380635188 479 190 37555853 517 166 185744627 439 391 770210 863 488 37491247 322 379 408629503 790 175 817586623 265 409 38156138 207 996 518701107 327 508 704671069 15 242 704763212 983 980 555343245 140 859 41900119 590 109 731020728 584 775 197295533 170 728 260309847 193 299 683344509 894 583 50788952 289 715 198830840 500 276 897870902 96 298 893984017 474 949 781352300 901 962 490261365 163 355 458576376 946 188 555199364 258 957 286731209 557 421 164781698 993 929 661159269 89 528 914775023 398 961 743758578 902 248 917785374 426 726 728604583 107 696 875885310 175 177 624836189 232 150 499759508 329 935 177201024 940 734 645946537 904 261 56155047 686 485 313724323 235 844 494455462 626 588 194898870 273 916 207855377 446 204 963891404 404 126 953038835 872 112 858322079 919 206 190548085 265 108 426966246 278 530 297688092 763 577 447645503 52 87 943924367 680 557 937397051 379 863 179476108 511 524 763985252 555 93 693287675 280 412 786378105 902 289 693253072 410 216 136877707 280 260 726490683 53 456 695299075 171 417 407341488 607 59 397547541 299 854 910155564 403 328 280695926 2 77 891618955 70 193 564837266 606 580 835071554 620 562 420314225 739 883 803384702 372 364 53295469 879 461 232965997 501 206 151167659 621 75 763698426 674 292 969077927 854 726 545558278 715 414 907620190 911 86 926613255 269 629 812845452 912 143 147026145 431 302 297041030 935 801 572250287 175 887 943954684 717 982 454441219 643 819 412806445 554 283 653898908 88 445 21409139 504 100 571828363 556 558 512176526 394 78 698172293 44 160 875344706 264 295 116574491 395 980 732639056 753 99 629157225 817 356 827287644 858 891 111749272 22 236 42332462 570 292 928674778 513 694 787395160 813 24 351581743 682 901 587812288 528 866 782442101 963 513 72915168 903 355 434268849 13 487 629096460 499 901 595025311 694 721 927001336 423 846 925871000 122 480 333366962 170 275 297472516 418 67 412955604 344 174 958434037 703 193 664595967 176 368 373321588 873 582 824399863 249 958 711196130 706 180 22802067 150 950 166957386 771 128 197828363 175 838 980386699 429 847 689864565 94 725 965775573 998 90 846096538 596 456 951795599 871 388 834913332 291 687 183846520 518 414 995833506 676 215 522277656 709 760 62744814 362 767 855001115 205 749 786620943 403 812 601471203 748 106 449468124 370 933 473908097 695 572 247957122 645 750 831910937 894 55 180821743 674 853 45196203 266 723 351957733 492 339 415108393 749 104 218894367 289 713 168126093 804 459 405954712 773 115 620899987 419 60 127127900 572 582 929330225 933 751 772853138 833 465 595415385 595 953 320550230 453 296 221786993 260 567 419120316 349 831 374644236 958 660 180183380 669 53 920979407 578 887 933537757 169 95 645078259 785 740 18853107 188 229 270753213 236 739 12843255 885 45 23680814 867 465 927937367 924 352 753015031 659 886 642835822 530 164 932810204 506 187 265044634 333 475 280828830 617 309 686327928 353 429 280280810 939 764 51005586 987 572 693473144 105 299 644435725 925 292 910268103 745 279 541615025 908 489 660972269 937 56 303155522 79 424 16168793 993 981 627285816 972 950 746854232 513 479 827713422 494 35 758627907 498 241 669395103 454 428 522045388 998 269 443551982 670 842 507437936 715 627 278372601 770 709 540679056 607 371 652667868 417 295 821255909 434 157 570491748 863 547 847233542 804 889 939155717 337 1 67272393 305 117 912863215 186 335 158354888 63 89 383537632 527 86 651663745 541 642 262110133 153 502 116265560 234 369 806848634 749 210 995085463 295 616 652848254 252 649 765656821 506 29 275486001 601 833 568406259 540 628 515025607 216 802 753680995 10 135 319215627 531 300 622749973 454 523 192113783 682 907 499633365 895 519 359243868 644 797 903402090 364 226 653518075 666 598 266636800 485 646 972203584 759 267 472684202 144 305 24023044 481 396 236176674 620 971 374591631 837 291 476799556 141 995 308928541 526 557 149152141 140 531 58799453 19 583 479574954 433 744 474232687 73 78 840462969 794 17 598146430 484 341 284035376 352 306 796735960 610 474 521753820 340 93 41811042 368 150 252539005 655 421 43969924 214 435 105744940 506 860 680815510 238 826 825147601 701 324 205653160 152 266 271966149 976 444 960386730 861 43 373321940 248 380 517680537 479 298 535036591 724 596 370004321 988 155 268884142 657 958 779491923 145 223 832213107 62 194 330468942 751 878 287343737 154 805 468066887 365 876 66123298 72 503 899620838 579 991 643846772 915 754 260061663 319 262 180403033 442 741 78671967 405 26 582368926 637 738 828248509 114 259 550867039 887 458 886409165 654 32 568359833 531 449 287186094 262 665 898829416 894 230 347728026 759 294 963830168 8 411 499490385 248 461 22002799 590 523 928673984 718 851 749929320 334 343 440214795 655 105 337744754 884 708 697718127 605 896 9149241 943 196 687048948 864 261 600367176 544 39 149567109 293 556 492090570 296 574 720306614 840 705 845044253 802 101 539930680 419 431 665996431 988 492 664633420 443 206 582695629 435 378 120321869 763 730 983621580 424 555 181835009 922 403 735028988 626 229 766237462 665 286 824030645 249 26 601714274 756 872 583111225 876 995 136807907 638 932 250028328 404 922 831204973 671 650 702103436 881 991 961105478 925 648 876488385 578 109 522225538 344 579 805125738 771 43 432695146 834 241 877546489 808 338 461650591 24 116 138067057 209 50 564586171 939 342 304864419 903 720 592886594 670 736 567446513 543 968 338047912 722 807 527274939 521 795 181377484 313 61 995875606 961 18 415927427 599 348 720843304 17 676 37367445 554 660 487594388 932 949 145310316 952 350 786335515 287 364 836279153 588 737 904001770 689 119 413145289 928 725 892677680 298 410 649582609 430 870 243149995 179 709 588963227 873 309 437607711 944 93 872877152 357 809 323121564 910 431 668642973 576 52 744415876 970 948 768612484 683 719 455489383 964 577 145016792 930 538 250702071 708 575 634009279 563 795 257012393 742 50 595128912 664 498 483070076 944 955 139900794 80 287 371183940 779 453 619699628 896 911 787851798 195 762 370292632 383 580 677326376 529 588 330368672 459 757 363946552 249 974 376605863 44 578 238278125 579 103 160327901 368 147 578762372 731 660 784595270 290 272 97893319 474 598 883893145 462 127 578310855 720 192 563955644 360 433 193202667 165 142 697079439 354 69 645430151 732 255 644474378 946 1000 210144207 542 161 152684419 912 197 81568620 797 596 733874223 96 376 332447339 711 355 45438089 952 117 710261897 474 983 319636399 503 920 905615661 676 34 314958782 494 484 423229372 746 664 395723196 566 31 102928597 465 566 406019806 259 15 558245712 39 150 41437530 282 555 57770540 26 35 84506732 112 513 87657790 872 406 479654535 996 713 852589177 203 165 682632750 257 638 764853028 502 202 478633938 702 508 601920908 26 40 503305809 425 508 623421662 612 791 761732110 775 982 773155957 251 627 615223602 931 756 671421249 506 528 535240047 609 762 980015030 744 675 970517638 771 121 278973086 659 600 906576929 678 677 8322606 61 88 311521653 983 779 322808236 433 734 182128943 268 3 492623569 453 238 838911638 942 542 240563360 745 466 879111824 16 634 549106801 847 404 210902078 703 732 476384155 786 65 259097996 406 559 835428962 932 291 12281373 73 105 304021875 185 92 672289222 152 63 79689863 856 604 774026496 308 950 738862514 672 183 240483405 656 821 92204360 354 629 991735976 788 841 338331049 768 967 531341466 960 214 587396089 117 370 358067303 663 958 219344587 141 790 100367188 300 726 929895106 913 297 469455627 211 227 117326980 25 330 20215645 339 382 778661549 473 901 86347209 485 603 199522146 582 735 40781880 459 895 224063326 408 287 794244957 400 566 500671748 420 308 777080595 977 680 75116395 84 574 144377718 784 339 81179470 603 382 836934249 111 663 700271483 832 248 750598982 540 971 942645289 403 164 682449442 18 9 993502392 38 202 350063186 489 304 271490726 753 960 352940175 392 64 775349986 373 224 696348410 369 538 395023868 383 559 133494014 907 998 973598912 181 69 641746638 74 893 964732286 969 443 451663915 796 783 625428833 418 384 690852309 4 316 909593314 789 52 132244156 374 452 252688946 745 569 316257603 148 125 866221179 678 90 825547620 629 491 693499624 110 627 168627804 101 937 238604079 91 484 89069333 541 264 994401319 287 276 136469900 835 394 62238800 78 750 50999063 446 682 271286083 682 845 690732421 997 302 294737397 255 981 486170416 299 290 532076937 902 512 179175265 56 829 866975569 395 130 486668972 318 325 293435838 988 21 536458234 795 874 150378015 711 58 404002653 392 284 999783584 881 592 541889221 353 359 89114132 342 744 712016870 921 953 934266462 878 572 305814414 923 212 444625727 108 337 170718938 558 606 781363992 367 923 614975495 878 819 657383909 730 707 395796784 373 979 129650818 192 125 596047499 55 728 348233895 658 47 204796221 575 695 262481807 828 442 283578659 831 444 747138351 454 589 491834068 641 268 494108607 287 161 863744005 822 366 488100816 770 703 502410705 657 339 281258458 300 883 384126991 761 851 716935984 548 505 735185133 147 543 797923410 403 677 357638785 936 998 565857769 903 398 332546483 870 890 324019386 621 737 95357898 779 767 444748941 921 442 25215935 510 971 719178095 591 908 486456504 474 980 326597196 711 250 639461166 647 149 356158811 356 170 883651513 361 954 915356823 507 166 683417220 233 250 983454444 126 339 219599520 647 521 787671171 630 35 990990485 191 633 342063632 749 982 944474626 261 126 463985433 244 958 185235619 969 169 939525921 872 782 620981517 725 143 412284672 609 438 705449477 895 643 690160619 953 368 629535221 206 216 364577100 355 165 814334472 581 309 254953403 351 243 897501676 335 421 365339904 315 910 235528902 220 421 452790261 961 693 360113584 116 274 473837167 552 111 277847047 616 416 267749888 440 608 796287997 175 803 220222360 777 228 823716706 484 180 482096838 601 995 817630992 505 708 853123966 313 114 452056132 613 942 179088874 438 247 934596209 35 199 641896947 617 258 920592499 113 242 84530157 884 734 803962252 985 489 122913288 482 346 618907219 886 175 475377843 159 823 435535489 242 30 661299791 303 363 522662823 982 473 728711606 72 430 366679342 377 678 2037951 708 641 233871650 528 361 297600026 693 328 648552181 123 215 541756430 571 761 231945299 416 251 411361065 559 340 982427824 336 473 107385621 747 470 704032489 808 311 949986359 210 488 72332204 35 453 589247619 860 852 93416405 899 954 280122173 54 8 768327832 547 368 839627144 54 271 939313103 239 473 389402224 606 362 140103881 869 803 398414469 110 940 195121667 28 822 771673439 381 310 475900298 539 646 136687088 713 302 50447686 41 842 308000380 743 13 106039843 416 953 236771043 658 468 390537188 975 258 643023991 594 514 659318182 216 399 703024153 106 172 604786752 1000 610 543751347 532 980 967391995 775 813 213189686 206 956 511686931 592 957 237402951 571 76 526309699 710 787 77236240 997 321 284120157 679 401 211166356 152 727 381678477 364 398 241244904 200 801 593673564 990 70 827323236 955 402 245772656 62 388 802087485 282 184 967221842 410 155 635111606 467 8 117470161 508 356 455201985 39 686 94916935 124 803 414374189 182 605 514634224 147 6 645838237 552 958 67777352 858 860 43748066 223 183 832395882 677 132 198276928 314 746 497994620 972 56 731121016 403 644 397336085 418 673 807611304 740 745 442836186 590 325 482331750 678 884 510241725 390 47 706714679 271 694 288277202 962 48 13013539 340 437 490850403 185 484 300607391 114 965 233833206 264 975 151320088 620 35 819986322 336 951 434435239 848 719 219830417 225 513 365625247 459 602 291884024 787 779 783314592 188 668 607358465 468 719 205675509 480 177 384345985 546 175 738028038 423 755 365598393 681 435 78509963 343 491 291135138 935 525 774542934 495 267 814750642 212 672 310876342 173 140 948723280 62 800 919666561 636 467 850833065 770 892 231586786 904 149 932357267 920 438 332775929 381 206 76685318 709 887 74865267 656 867 231185743 473 660 152302637 790 409 576952252 864 441 76492401 734 862 969606045 526 61 505120863 533 112 377343441 895 54 327333567 670 833 483844667 497 363 18541275 187 120 304179310 514 653 866733489 758 858 192251796 531 523 414679877 431 436 174999682 911 304 781439594 697 630 434761818 525 54 657367770 324 493 686698336 487 620 888004809 523 104 683352678 153 333 694201088 353 183 567151010 638 496 435451372 896 312 783300304 810 88 137580303 91 311 731365174 733 234 745691839 885 63 127039263 87 701 773299280 185 380 687265757 400 459 885996706 18 713 633403588 151 343 756859790 669 549 164642575 356 256 550343592 558 768 989490126 182 285 737699887 184 431 828537359 540 420 830155760 751 23 98770629 173 454 813047164