2000 10000 454 705 992441150 969 555 970881009 753 873 105092348 661 64 504166301 969 782 586632227 855 940 545946884 449 401 510486182 189 828 545098859 232 294 405080980 131 966 953065420 370 496 543811301 728 302 617216812 250 944 903294472 301 224 781195688 819 724 786624757 97 931 217167874 575 383 798482026 410 263 738930761 282 946 701542004 917 841 267597254 560 1 524960231 702 910 467726591 310 706 691275770 866 436 487754331 583 159 505446837 259 971 261022761 956 694 443622982 660 889 144489882 526 323 90526647 600 109 438879808 915 738 881395894 668 838 810197486 867 654 58405742 912 867 501655926 689 707 619095742 121 856 743641747 176 779 15776509 574 289 726769320 529 721 89918513 2 746 464167705 408 894 131914587 505 937 801029324 654 949 841660246 505 132 6747055 172 968 988690228 453 764 577318937 637 150 4062825 618 297 60197854 184 340 302449415 1000 345 638143035 358 84 49848911 481 519 796109131 430 874 644290847 642 28 476051753 411 464 172941539 498 414 645962869 252 666 239424665 595 865 199536540 709 776 408863957 713 306 707934191 198 983 451009579 55 384 512857289 232 950 245906666 245 241 334049662 449 794 646647360 295 572 927926009 768 264 930052698 945 901 332044598 41 930 17526499 288 674 628762206 933 719 608592020 652 810 124852413 680 570 545705904 933 943 762731457 93 791 610647864 575 349 739789142 575 812 283400356 735 411 18870431 591 59 847776369 348 148 686634918 629 262 488313284 680 390 41770056 952 932 589469475 715 14 327816781 754 884 844065632 898 856 983207950 189 236 120075257 587 519 558690437 159 53 530255092 550 377 45479065 650 917 693176196 198 111 958749493 140 407 795039751 110 585 347735312 16 344 814819424 211 775 971258929 620 885 284487574 660 3 474711141 973 597 283386137 459 263 869502445 748 982 94078795 792 529 627338985 851 347 275864569 390 985 464586424 672 821 252245606 46 945 985986914 411 601 26722715 780 587 176227856 125 451 59226409 698 855 123193848 174 544 292343996 520 403 102843206 853 159 224770189 9 984 860535440 84 375 556269927 237 380 352610521 836 342 538535618 320 355 982714151 95 747 1715422 219 921 61710206 965 892 700938967 362 164 573495642 258 155 289920597 833 779 796758386 406 741 2067819 683 704 680814153 267 288 832782325 884 400 608998450 92 16 676707400 565 518 982079042 660 589 572751371 870 179 509749336 985 31 522341156 689 809 241156690 702 403 601492899 30 513 268026970 546 257 230816442 343 540 464387785 625 883 781875736 691 89 41455252 547 330 252307662 535 172 367785982 878 792 626200242 32 386 164564925 482 676 13241600 412 796 483460269 420 597 248406295 291 828 132771250 750 627 571069271 122 401 610411593 15 371 756574268 113 341 833961315 683 366 885547628 554 780 303316530 665 434 552891928 627 983 781131910 972 278 85665408 167 986 981430910 919 639 261386958 940 838 762090980 815 528 517405710 458 432 211451384 704 633 688555605 9 424 38019178 645 327 968203024 315 47 510629522 350 394 283698772 381 450 281927520 936 388 535729212 45 773 903754702 796 157 542800990 310 158 651002079 45 468 464168439 345 558 168798134 183 764 811597594 825 188 762325382 233 5 257925671 87 376 158934833 612 395 777370127 276 691 885408190 719 854 714891767 816 21 338934486 500 859 151101479 312 316 306861298 495 367 565425978 418 58 715254001 158 207 702702381 208 399 703374391 294 163 643058208 391 116 148753473 995 981 226937706 13 90 532274995 767 273 688366462 816 923 144429757 58 184 263820400 544 778 820077141 438 376 474149245 508 368 970276312 31 106 486960140 7 641 402114045 716 523 737720835 701 431 382682906 929 847 15023934 134 785 66238636 726 905 776345859 718 928 598543092 57 396 360479249 492 91 536423527 538 909 266933492 106 221 963855589 338 981 875773963 116 181 991707826 540 318 269538613 335 678 475653270 865 141 482119689 790 62 240718436 75 472 29531138 577 210 803374188 282 82 401395233 399 139 42361604 376 770 604031095 155 146 894456624 671 918 965345610 454 384 97240085 744 73 75285608 488 627 515287132 674 797 718578344 410 288 2397246 357 802 326314459 115 704 350158203 210 929 101723055 398 961 578945118 364 878 687425538 154 176 534994601 279 234 290786528 322 24 509161967 314 885 774040969 440 330 451415525 837 572 947432063 484 669 237966097 440 353 899033514 917 490 534490267 743 59 5041820 938 919 903129399 40 686 723161853 443 664 691034087 523 741 279539543 253 579 289827111 23 645 656130903 7 198 513952954 770 791 248481220 629 513 196292719 373 156 228507433 566 61 497880879 969 708 539045737 92 68 348595437 895 328 616726537 810 19 649516978 98 497 361424844 577 319 203233507 747 645 589174612 222 950 440145996 755 427 91917622 685 852 12693344 881 594 549672446 458 286 139596752 187 475 792818426 766 235 728704838 178 125 638588178 634 283 828014203 868 436 521680672 108 691 245877279 267 247 858053019 393 278 892470730 938 405 90940057 862 935 82287954 736 165 806003077 731 50 706340662 350 990 215044034 890 950 392741632 302 601 474918634 866 453 861973103 519 692 104929950 112 205 131256550 948 732 170775398 880 601 172684454 686 287 762257536 270 699 71408209 198 102 894561668 880 685 157423828 286 162 333672299 577 624 510522384 660 36 256483203 980 527 289212005 815 112 337138740 163 566 610868288 496 758 908800591 619 830 469435330 921 462 41581776 12 995 744943802 760 42 784125732 570 66 156649507 739 999 111730693 564 738 628260599 234 557 213685990 864 341 670010373 856 344 939667819 658 136 874339459 427 521 865518249 851 82 542600464 764 877 415556343 146 924 837394477 48 440 354795084 222 456 799055092 298 223 967934545 716 844 694288029 393 514 888423899 351 707 611644437 977 352 86218558 425 501 995833997 60 836 663764383 936 966 984610623 826 804 992987149 325 399 288773830 348 234 355155621 792 872 946513919 506 196 169427322 257 857 259164579 375 398 609995259 865 777 652453570 952 544 146108556 938 480 636822868 426 599 195896013 331 716 902668097 433 94 626649013 641 933 238537859 494 876 993392221 324 619 693835204 114 783 122483752 335 781 656995346 68 691 207494876 973 446 391949323 399 453 730744881 905 951 487234749 362 223 785591721 28 691 120842844 18 800 117958129 968 186 186146238 53 900 46981143 378 384 658285159 968 916 506831446 599 180 255484401 918 806 739315550 272 671 570204944 866 616 692822168 14 313 266515510 96 336 849926182 909 388 243584407 563 701 912292770 633 244 331348118 92 190 548334442 969 74 293534074 671 320 233971261 439 179 894889013 226 970 21680859 39 652 249702615 446 869 662759193 948 181 247224260 479 357 379797942 856 699 916950244 853 179 322152457 623 618 673146709 87 362 895523708 739 816 300456966 101 944 795452820 101 270 426996683 524 197 437617460 212 478 972261360 112 737 368814180 250 271 438483690 987 974 747373484 67 275 855566367 4 285 32484733 115 81 354379516 958 909 595506076 576 244 567753345 737 647 696279250 857 164 443036624 817 328 690664261 314 966 698438062 637 888 183000496 709 417 580001366 132 9 23586362 495 658 301129710 164 328 227418654 411 854 380398650 242 362 476845357 567 562 173381083 547 476 266146225 21 321 645672958 325 828 665874790 570 879 852932287 627 168 923029089 89 175 304307789 19 852 436417505 636 144 431391357 805 584 471948623 382 548 179965882 663 934 124559010 722 197 214156504 863 105 244315421 768 517 903181657 715 806 836243626 635 351 675033851 3 47 711112511 703 171 398987672 971 471 461122588 693 399 901010559 701 485 933039045 377 243 152417373 64 455 446595511 475 645 341012882 894 358 201416688 15 885 757387840 557 1 599251372 663 832 749434601 47 233 212683311 19 412 773076529 134 968 992811232 399 625 678659480 870 365 724074785 508 534 952577598 604 257 520586525 536 30 441579913 686 953 606847998 727 93 56829621 78 246 468154241 795 501 263450198 547 223 978393219 75 173 144484550 467 771 108065999 844 252 171382698 646 447 785902914 247 654 329114125 18 942 695507740 413 722 889454127 234 114 30287852 71 137 213932785 589 329 191041246 27 724 624188360 365 624 814013060 839 736 501414912 877 302 575028871 756 489 350071669 939 10 597769365 963 533 393995195 347 969 702190249 923 722 505629019 31 134 595365332 530 27 845587765 32 492 321994952 171 48 737093712 376 212 920517190 972 977 558699150 851 169 208897060 893 699 376608227 556 43 663366951 610 924 536778453 597 387 886545045 514 370 818149385 12 271 506603286 600 715 286100898 679 318 146802116 99 845 958148366 139 97 523127549 329 965 990091 39 782 914520787 880 780 149703455 136 321 914910113 727 329 2507829 69 173 514441519 713 638 210922292 825 956 726245093 473 979 514853244 230 473 538760231 190 473 529181324 472 182 991247527 634 359 752712485 942 949 135887857 395 325 127262151 175 89 890477976 938 174 365494019 326 922 196467516 133 379 495958560 947 114 85568573 369 7 177325023 703 955 49180124 378 274 152674829 156 436 376991955 462 818 965610864 639 37 117683842 9 688 915763661 500 414 38826623 465 751 606672447 755 451 444199601 541 620 306792939 249 738 952641424 552 840 331737729 348 157 952290101 443 86 274225261 154 904 4356617 720 461 128597288 471 661 706353834 952 427 101740397 299 456 852048472 59 726 576318011 568 548 198134100 685 902 983999637 532 436 487092384 495 663 271417427 248 506 78106038 525 851 150848582 612 26 718855765 437 345 124737590 771 20 396179102 668 150 431111740 784 756 353975774 909 960 250359182 832 142 565879250 369 600 326113985 46 269 256366177 567 723 653201546 488 970 828560513 538 571 303653041 295 549 885754424 424 148 420128202 804 81 664373420 778 424 100336164 72 73 111347321 952 87 998497003 10 413 41639118 6 125 344394355 127 422 771981919 415 706 573324424 725 871 31499674 670 353 878736988 872 458 606704914 930 774 105290292 916 353 240853251 428 12 445741398 487 175 718954738 304 815 222513689 246 591 260695922 65 459 894468280 458 831 275844012 555 745 822622301 391 591 922721483 257 810 316176608 747 339 901965180 867 662 496684073 322 25 891298285 28 406 360371154 865 24 476771321 913 651 763943560 327 722 222867680 139 469 167158417 712 126 774109782 933 797 837151197 780 332 376777619 961 925 810393577 985 370 86768383 24 781 483925829 767 362 148250116 13 60 950085363 935 694 27732835 213 517 212092002 812 480 275321725 711 442 366122355 663 978 625182059 714 75 15417660 412 885 589802151 187 959 148407045 640 86 62297755 761 608 120877105 564 578 360848212 399 302 690743512 338 886 499686666 427 50 167180202 120 845 822604023 487 470 1409060 385 841 838107234 855 299 285407361 285 730 175034610 160 945 944792618 858 705 13395062 600 62 824233088 946 212 17659252 221 919 31674205 416 722 755474463 280 47 219553832 201 972 12077389 226 767 964064716 268 138 619293148 703 752 187524358 278 32 486436659 359 87 374164970 894 213 440332743 454 191 514756931 805 989 972211653 115 778 357118625 671 64 255143718 832 213 61450993 341 946 748073984 981 755 4675842 17 437 700266606 359 683 718560084 343 613 780592461 930 132 431939141 794 689 120810323 677 152 573319863 990 132 8528692 394 680 909430000 296 57 502811623 968 378 9877216 519 786 503051112 345 382 728809799 943 964 234520898 397 554 330239306 739 962 304937425 623 902 567604931 149 379 170447640 152 569 370719031 785 681 401886649 140 923 108981048 436 272 756797960 243 252 534058437 65 909 121555980 835 176 660123271 976 273 17620958 264 414 732819323 753 784 875135453 394 705 835089047 659 874 228033119 596 563 432071675 248 149 17448982 481 934 856384463 810 123 62987919 603 552 4133909 921 967 946938375 851 840 787477104 659 957 528450377 288 140 118708870 597 313 318013387 899 608 541548828 715 55 544354287 376 351 432543376 697 470 298375261 36 749 629728266 773 480 864232991 868 147 184066100 159 195 847604476 520 344 119422088 675 494 86337813 833 679 316838120 783 957 189228203 203 671 349161573 481 270 784876617 430 889 419847374 492 417 354780894 726 653 158254110 155 653 976039982 642 765 211915525 159 848 336691864 958 996 179043302 902 280 979269035 622 953 921079273 234 254 522985132 844 110 559382885 360 670 265232204 815 261 845846721 53 186 281019125 418 641 11841035 263 44 893327962 281 962 483238657 731 624 107852578 903 882 842022546 123 715 999833019 507 108 907963078 307 999 462321382 511 586 527915336 285 909 106086791 806 365 686007984 404 291 443633116 692 593 264685140 928 941 770476928 616 262 188891352 720 785 192201822 33 103 757515905 224 20 801302386 845 340 383774452 422 504 44032795 118 256 805888139 934 382 153035096 638 151 365127737 123 800 310680761 930 747 361854636 260 475 437032605 46 274 501011025 688 29 673613927 402 716 730579233 98 734 125126641 881 925 206863516 353 488 303757131 463 429 7320808 642 518 503242587 548 438 364147021 876 126 381123522 741 956 531626014 270 422 650174838 837 691 391139080 57 744 332913067 995 343 458528344 39 215 783316764 39 830 924283817 463 973 188804575 402 261 211620931 427 633 925250884 968 550 304179726 427 84 175900323 399 263 194564858 551 311 999851626 943 802 989586398 606 890 653311650 280 731 48636202 958 817 383741599 204 969 11548149 583 98 421119936 463 244 339794136 998 380 573037254 871 962 758485085 377 461 348522271 256 756 190222674 997 22 63313452 885 480 204214096 386 125 115249242 467 110 466049158 940 871 718461329 379 503 64775389 746 650 212763243 833 480 880693326 274 541 776153574 12 597 865478990 377 339 4309606 215 739 653254888 253 450 205207717 322 209 915691244 684 201 111381639 200 714 466609983 648 30 201515321 619 380 233921421 737 866 794866621 986 218 933393221 308 638 991759151 670 476 205493047 955 512 787666910 562 783 413554741 66 544 462156948 195 983 805068166 704 377 164268025 677 757 438636194 513 92 655290837 375 196 121117438 412 381 598655175 967 735 517173052 620 419 61250344 118 407 585720034 192 824 561379516 233 734 226719949 476 231 675356290 40 406 663664729 171 638 495340887 518 193 764686242 557 577 512383753 345 139 155872019 903 570 416892041 417 718 995774120 32 489 841521433 985 71 65704555 843 682 404249919 177 468 51205606 887 596 567439302 563 475 156567348 897 898 554698422 909 879 458372415 491 36 392146587 325 978 406167153 512 442 522958624 290 124 812313019 674 935 387949470 502 709 245296648 209 867 822322053 319 976 532965806 540 252 4806650 516 664 22333032 808 777 568078594 258 340 899402347 312 697 67943009 713 247 666725128 974 181 344375377 1000 616 216435245 885 314 702274551 656 962 509816002 451 26 36717065 981 574 294885214 521 436 725965288 722 342 330825653 795 988 50415810 704 720 399738680 702 392 887507719 373 290 996745322 398 614 624841672 291 930 505149489 591 68 472142906 732 213 125558288 946 555 10855625 194 870 998042222 58 929 806035627 80 986 228229692 635 255 436714995 889 270 263762701 152 964 659194300 879 676 237286076 476 124 687689695 250 430 245304118 554 771 38786687 128 896 344758085 537 163 608077890 192 103 547064935 290 260 541287109 810 533 363903375 592 380 429424891 510 411 275109634 567 574 10521230 648 526 121670495 437 370 142902588 475 596 281875698 309 625 911325529 43 916 620991619 101 596 799360431 718 826 736223848 392 552 318521620 43 990 628489908 513 442 159224537 663 162 794996580 241 527 479065387 365 798 199160090 637 66 156083679 318 34 608283238 229 848 882429717 230 730 242401108 630 764 97109408 771 664 938910157 795 788 803245294 270 654 894473081 733 411 705465141 255 650 211713625 783 949 48231243 114 126 536049228 265 902 562992522 239 227 982106591 371 646 727683431 229 948 683000719 203 152 454796677 913 831 243548861 862 811 480582982 94 865 454998455 735 625 111483772 423 566 51116883 822 807 191952564 354 703 131979212 225 798 92463445 659 375 170650231 645 462 966873622 436 793 25829071 935 453 795323664 388 923 539875156 442 301 293333420 693 257 512119393 231 96 141331523 796 712 889424296 413 789 334096454 335 918 715587359 583 920 569180114 84 784 924754540 879 222 151013936 377 146 363861444 669 105 601587612 457 126 926156083 593 453 628687886 438 627 831000822 652 143 596984530 641 377 247925040 238 586 77248503 789 234 556086586 615 359 991568078 152 708 358586128 599 523 883296283 346 860 381971533 690 498 224668977 562 47 953838477 110 800 239388282 267 937 705856414 623 157 369772001 498 465 956342611 355 310 57298577 983 79 412584762 653 742 401803301 190 575 390187246 906 93 858656920 262 57 449177826 701 988 57635882 930 163 997307587 604 560 269165334 17 974 128022674 668 40 907547463 520 436 525183398 228 65 441221867 828 978 852090949 164 880 976828101 786 849 680190508 487 736 79692884 807 968 314195371 292 109 897919316 659 111 467125078 520 106 976763159 709 765 541155301 401 655 92823498 802 413 348476569 15 340 115186844 83 701 790436829 907 987 684680549 696 348 88842014 423 390 965072070 450 782 82871408 811 792 106114060 34 762 72185390 298 82 322385166 51 503 875542108 144 604 177355385 244 335 297534499 798 210 470116792 161 905 517345283 851 682 252478339 526 773 717202882 653 902 500114620 874 587 608144209 844 885 994943245 217 672 354437905 443 180 363737852 946 641 988532776 322 491 394757615 467 177 112004969 432 147 111463473 799 64 708856232 255 345 584850125 759 839 305925938 322 866 944486225 736 296 697831596 663 542 254297511 470 692 196183582 842 303 19425556 697 926 882594956 596 947 436845578 351 659 776243022 384 95 352370644 496 273 254228605 374 601 552833149 669 432 38212971 70 417 839968965 606 332 761922950 341 856 25780081 345 136 38870538 702 874 145355972 10 180 388239853 46 608 808824505 562 967 472801586 332 690 831247878 360 255 228937627 120 349 496771416 479 652 193541900 568 724 998091125 177 961 504652573 212 938 257716229 657 944 375591353 587 147 770122534 911 506 727530410 104 54 607571949 773 736 173876655 617 16 65849041 438 555 477197023 642 131 128780658 424 166 953701047 404 388 139649247 212 439 339393338 606 828 537842624 658 833 92214813 885 440 143114346 874 342 127058456 126 940 847718654 719 175 786391496 524 276 575055398 307 224 238218574 21 429 798901292 426 295 762977324 173 385 764056368 917 766 342574053 618 127 554270684 160 837 529165432 517 681 570127425 20 434 122699597 879 262 311305050 51 722 620570775 520 908 626352704 262 323 179604388 555 978 278035846 759 306 461501206 491 898 52842339 690 79 256694560 826 64 812842125 359 877 820105733 832 50 869332697 452 503 285544637 575 483 211871639 343 609 247710054 683 230 337572079 980 632 16680933 35 848 966377244 973 959 475556229 466 363 491926707 267 484 660513749 289 935 782192436 66 610 986984361 954 802 128242982 399 933 201436894 28 326 332408116 789 709 944251252 13 692 990552322 892 809 354005046 193 150 485440040 521 115 848075440 938 824 88775795 298 47 60097831 914 266 963317336 117 386 902648927 304 380 150513919 986 279 416611014 358 406 691468803 865 476 485725325 193 899 53876648 789 843 291494272 372 211 647716399 532 96 247413894 100 833 754440455 451 934 470230394 465 918 862550451 759 146 816927620 282 742 17435866 214 479 888725338 729 15 77745028 237 715 134930736 799 173 958542576 371 483 921802374 374 402 489778022 447 462 361529200 48 487 717821 27 271 324595323 623 680 165579354 254 432 684696549 470 254 751589971 380 44 735743157 804 672 381349300 101 484 925993598 663 107 400173170 643 205 117574005 424 714 189891415 385 318 989711908 135 586 972725554 500 46 786007544 535 747 301801855 616 82 396691454 243 895 947154244 230 110 892317787 983 563 856589975 630 382 821318597 478 610 589906578 681 411 572684513 605 420 463940783 411 946 186537572 166 930 758920030 634 576 438721311 509 101 469165973 361 779 849374026 371 849 201612302 827 949 383040927 434 381 939849771 899 420 162876099 277 201 730079926 176 29 268373701 979 765 288651529 467 891 723329047 821 412 465767614 595 301 143045347 20 399 412330356 690 994 736310568 264 803 741335378 246 805 499157811 883 947 951367248 882 238 980150533 656 312 430594539 760 592 960165388 439 452 737760874 369 841 876146085 504 134 686939449 961 956 536726644 27 237 315496139 293 33 88494560 611 163 962831278 957 80 283975480 118 567 192894907 339 738 470681571 710 372 823937006 877 782 674107915 667 568 603152268 757 637 814970074 674 490 867932939 709 676 565765959 432 542 85461280 657 369 239170757 839 754 465846536 985 175 755981254 807 947 729999535 850 684 517539497 183 15 905332596 570 890 473123562 781 661 957201244 800 743 842080531 489 751 995060551 976 696 309796546 738 322 2687705 471 535 835778315 238 158 643614622 229 488 936038783 107 23 434411471 132 361 404512758 982 480 845454547 63 542 616388018 186 199 837009623 289 825 352426976 177 275 840461690 310 353 438565925 576 873 33286546 664 991 647990146 981 216 908178478 505 737 833183862 841 651 854454526 209 425 51248314 320 393 829549379 566 508 392907812 747 213 396163200 106 450 145306053 7 310 465100124 770 181 375313229 61 492 166483578 415 671 684719361 920 82 901046974 857 813 879499416 599 657 378867361 785 703 257992002 552 214 247587874 727 567 120528036 460 217 233503508 642 566 438916495 934 108 731951639 794 425 327232017 594 932 471830675 695 3 696439548 222 449 386942778 144 288 8635761 933 629 398951211 60 230 441131481 248 399 805136769 721 463 229132010 732 424 333800060 628 230 749161113 958 629 634772114 348 333 884272679 800 668 448405804 941 576 900161161 919 606 63583194 527 233 431669322 256 567 591135766 752 550 843598353 450 741 428766320 378 999 612965859 108 891 218690204 845 164 977655605 714 297 810377543 437 466 168749427 623 562 256453188 161 286 417599267 70 646 736417250 751 680 642150072 406 652 256512941 992 444 322328713 676 874 518654121 295 719 819545864 266 503 221101003 436 459 757904445 29 688 806733590 647 535 608079358 367 313 125477915 89 666 452164080 839 473 554111269 875 657 372472933 161 78 990761886 658 695 783522168 383 406 250510014 126 245 476534941 788 261 385182477 786 313 424960039 195 851 593445737 111 579 516858120 422 817 287177287 297 20 281312628 1 358 190946182 569 726 456496158 721 14 763448120 936 522 149904297 51 865 463660062 61 1000 582187258 157 718 670544825 682 787 384090671 847 219 601715771 176 894 914613310 594 541 393332437 234 957 618475823 800 402 492258250 512 564 772836802 833 729 668854229 454 51 588020301 691 7 991271912 16 660 479649685 115 855 972273723 75 488 473700913 372 344 462916080 111 994 497748977 702 449 160244495 182 841 491204244 471 902 317696423 615 921 887435980 59 47 434776508 357 316 270947263 792 943 5208138 893 678 98388481 384 394 251721328 381 636 189015131 325 961 78494386 514 199 195473672 194 147 23205144 398 89 519549888 361 162 969922323 897 368 487741412 346 22 117715486 954 763 764593917 520 182 656538517 334 290 492855115 180 576 771899655 482 578 29801034 19 42 257420327 370 40 824429933 349 588 682288644 56 764 47480107 909 399 957870002 706 861 649605944 653 902 657905138 534 286 519105557 965 936 525638513 558 776 191252579 629 918 332938839 84 480 200462065 756 865 740644398 477 413 973897761 640 864 621387448 234 283 242620105 690 426 281400931 863 645 875577169 500 908 998812690 260 2 636160620 807 91 958523502 600 186 617408346 820 377 86704997 632 711 164308202 63 29 454588904 513 521 638665128 460 887 522821006 873 900 704775295 326 259 227587415 723 799 249532761 860 363 162574212 122 544 327117593 517 139 92647373 442 918 261398243 32 457 531376949 411 307 582885260 381 435 734242647 635 607 197768324 97 204 220143154 245 683 911201252 692 582 959682329 690 884 307592262 312 394 329933189 483 315 442438193 91 148 480971425 907 170 909984064 778 890 770618129 655 159 415187210 932 485 712583386 477 186 309843921 54 796 541611775 384 946 505228832 456 736 766733295 55 324 369642345 145 162 274108040 842 504 565338891 948 5 990094585 826 830 854385544 55 474 686642708 432 374 439316201 172 480 384296633 864 568 665825842 666 129 629676236 9 300 349905625 48 551 14814896 131 561 381127801 892 238 813747316 89 718 99525029 842 263 615658814 490 379 824242940 527 277 699242519 724 4 126772667 459 104 145835049 872 424 974664391 342 449 12069034 574 895 989004534 732 159 186195451 594 599 851003500 770 399 137062496 267 163 144722925 173 265 371911705 856 741 550392362 511 91 185152657 186 179 896157810 583 84 899240192 229 94 618023392 569 356 402316236 259 695 44682996 827 772 104784008 750 301 639748647 704 936 564997629 551 347 35199656 101 641 163121419 92 482 626277859 911 988 756953705 707 260 162306933 981 543 726232371 942 249 682547624 225 753 312473137 58 704 971169782 463 162 554501168 976 260 16035987 741 175 77390756 206 298 488188264 832 337 835662817 410 460 589934082 158 51 29545389 531 470 407016009 670 577 302631776 254 734 332019016 489 334 53061055 534 398 961597297 75 404 391309139 693 548 970269514 71 980 933671980 553 899 400362644 764 264 206580665 629 419 268391185 364 92 907267866 429 524 361991280 664 759 871686029 566 688 668382584 110 852 710693150 952 9 996855034 849 62 659779727 389 225 827787633 811 760 188680371 763 369 167242579 715 917 908320562 781 446 473286234 277 893 584345262 581 892 420483448 383 417 978663307 290 723 61957865 444 551 754444401 459 81 837953152 691 400 321552137 925 913 703964292 393 471 917983932 629 448 532755781 438 716 89930331 867 478 488008762 551 420 843707590 856 919 36300882 239 644 706440086 258 534 227731499 139 17 166588765 929 195 719663473 375 739 779023675 166 46 760890136 314 219 435779820 618 833 526964031 415 13 40570516 514 443 97221535 682 950 854271705 704 14 718452628 903 492 805524504 715 957 195097678 83 935 295772850 411 701 674375178 320 805 281891435 247 544 934653362 36 545 103668900 324 442 321238941 895 791 132481214 388 969 471562939 853 990 705546693 294 617 574580700 114 336 243512576 562 251 779276728 932 213 66678513 580 471 728483742 851 635 492946473 677 412 751030983 57 771 431078402 273 322 841462517 694 713 838171562 718 414 680262313 995 196 837446295 261 698 106178901 122 852 841371875 949 150 734094979 534 671 52496540 837 299 915004009 31 24 411473570 460 121 877066405 621 588 816058446 997 387 277280858 334 978 509586624 805 363 23162682 868 108 857899290 42 944 206813798 647 771 3880860 429 131 999900452 8 590 83826972 921 145 506618493 638 489 409277517 160 774 840313235 587 662 55347665 667 972 905519859 857 581 890081171 426 616 553911669 202 856 880146098 107 209 700134119 249 902 716381077 995 763 544853739 829 197 792658849 151 385 630144291 615 554 553757098 512 823 764482295 6 4 156433725 617 537 482849766 661 954 533104415 567 840 90499555 330 894 809527743 192 20 981079181 89 307 48900947 295 261 611423574 911 886 712542401 329 200 300065779 462 613 763345078 153 353 326647018 787 970 548522216 408 333 210705532 942 985 760965920 458 249 656791494 935 374 264075437 583 776 989995809 388 511 176913781 360 424 116785875 256 484 925443204 976 324 298836859 71 366 196469601 926 598 284376151 234 847 433260024 346 840 567166013 171 173 457714407 975 67 7182691 68 711 312048715 911 256 918723610 124 696 865773937 516 628 69080233 50 181 942387858 680 592 469276032 145 662 450389177 662 641 104494455 351 773 912068631 130 548 195857095 619 62 860608271 772 245 893207749 843 320 821541051 146 866 373083828 812 745 479678736 478 432 416548357 395 575 35911747 685 133 537164668 730 670 836152857 502 290 58272531 968 438 50782593 302 105 292633230 170 82 692630868 1000 642 714861176 434 959 302086982 768 361 904217081 583 227 259621752 981 602 216153830 597 186 793514467 433 191 303739890 642 627 32807122 287 357 977458440 536 20 21107379 447 109 928532637 151 619 687755851 357 402 478984991 175 383 534443209 142 391 759487226 774 732 529434849 534 489 200800081 897 655 969408726 493 457 802694468 45 894 171188396 133 625 906523950 634 860 532770846 971 906 412428996 676 185 296802323 281 828 763814074 196 832 860120704 328 189 376588807 360 30 716561150 447 685 332270019 505 315 687991134 553 859 462415099 978 51 236414547 95 72 643075150 588 658 574646066 937 951 335042460 734 560 483668060 295 941 410132442 319 238 723343815 598 776 127676813 177 396 572464984 834 453 503967198 51 655 134233905 671 827 443928608 109 666 163998283 457 320 221978828 149 164 789709368 146 7 34262037 811 341 342064468 647 983 623510822 568 270 185679807 106 37 559685297 294 126 301956983 781 455 857701856 686 209 660135509 163 115 637531427 509 135 792408526 252 361 77160260 125 384 787468789 156 104 905631101 362 213 497530157 877 303 327327730 218 60 179337018 23 935 327948221 232 406 98822553 981 978 70985044 72 656 619661922 905 669 685575799 123 467 827193113 632 596 641754420 672 470 5093145 740 278 940634095 635 551 154231761 963 364 179963485 491 477 871921634 556 270 174989856 699 70 286110056 32 363 453700721 865 299 487896287 620 202 254307730 354 838 3107413 824 328 495945002 341 93 22557168 901 269 707534245 943 907 394164833 802 450 814307177 990 934 458426256 165 21 898144548 680 205 857122966 181 79 18508751 682 17 986450367 607 670 358064269 889 99 311853292 935 244 285287185 811 739 721321073 846 179 59436753 764 190 124495516 803 721 613566823 395 123 659088100 496 345 703588646 291 221 59398625 488 103 606535360 571 300 620067258 339 330 755834893 220 781 65505166 621 560 56073989 221 233 449645511 881 678 291770282 889 251 305875909 283 246 830550609 689 933 219858994 696 672 158294561 879 660 96703588 996 555 5000420 880 87 380135728 259 462 228691805 882 438 405276752 711 814 775069846 774 591 493722223 242 9 746397272 839 718 111377830 928 620 495461055 662 49 669384211 25 548 420607167 238 528 244738896 331 521 779864182 4 61 722646918 456 84 747424453 877 811 234272227 981 543 843427203 408 783 73376461 405 269 619874221 201 342 788989694 411 788 920479207 792 949 357525816 175 289 395074575 630 192 931985684 327 271 553895137 230 653 65508038 581 724 3941668 33 470 629575859 333 679 881034376 436 394 510864317 144 333 494268344 820 977 655829804 370 426 56474881 477 345 645972649 566 310 62052498 503 213 18891369 677 242 50962902 82 387 433854134 128 182 329333523 931 379 228341344 415 843 335775457 795 367 924845186 329 69 315880202 69 921 177428533 948 738 527137411 552 84 376138017 423 971 125732002 897 620 377138152 306 441 575080114 576 147 819327211 104 117 981753706 895 335 475278850 166 87 102130272 521 12 676676810 316 907 624069146 507 749 976995944 794 359 91860356 499 333 332123615 10 488 427812662 340 680 94532454 260 131 124120255 742 542 785947262 690 953 537333816 402 431 263313155 511 98 396924308 802 809 682587273 338 211 514440448 249 626 116209084 319 816 535832216 875 373 997271007 72 683 82508388 801 31 639249015 397 611 917630807 921 223 372457261 709 845 109176200 344 433 958979420 828 787 300256802 834 970 987140732 588 335 940567242 658 260 470907901 333 555 709571729 483 313 665189120 331 15 185205627 27 73 198572085 242 94 677422509 326 792 661664100 391 427 386572527 356 93 544462511 887 407 483907804 632 650 214058140 205 860 696076558 854 735 350933175 321 285 977571800 204 962 197136652 534 942 550266617 473 218 16102101 871 141 520352331 799 167 802920895 855 570 319393128 725 77 110488685 886 324 735385624 557 739 158347631 696 161 823441999 830 184 434117131 984 443 769577675 370 193 136088299 523 546 111372080 274 238 674173053 794 589 949593657 834 35 778425853 724 629 144362706 860 125 830553261 436 946 10682401 340 198 291857592 43 97 982110307 773 681 775106041 509 402 302567759 692 917 461038071 251 180 172424566 898 244 774371908 720 447 733324812 908 778 501272593 993 551 233213647 729 733 217030128 335 232 998468232 952 5 61978274 896 774 691019678 543 608 357160090 888 796 261192382 4 90 479427200 424 396 418442461 942 730 438754126 686 758 322547848 850 70 327526180 171 767 931125579 143 963 333855649 161 641 726542624 878 962 743837060 37 1 997833620 914 55 819571838 834 283 834549011 329 765 574303566 525 247 930851386 313 764 579292527 282 885 996389497 904 697 822109444 924 141 259979260 23 442 484594673 552 784 702476057 95 257 159764563 609 988 128063203 782 155 529870625 985 658 915268330 939 582 401778515 728 405 764288777 135 612 85084138 146 730 563660168 813 171 746637872 759 327 70461391 785 304 108730767 597 180 740989057 999 756 16674034 324 1000 82673266 294 612 491332080 864 151 270672789 932 277 674963590 413 16 438424304 840 833 870945916 34 182 225988457 416 275 935991198 589 388 649924097 59 103 247433555 900 310 279708328 47 394 617856378 901 735 439837129 487 702 349912436 905 235 568365661 398 743 9307138 528 49 198073120 539 513 582869248 377 166 270579309 173 482 556431381 886 407 936012442 519 79 239199703 548 315 767587233 613 834 677093034 215 157 260322765 672 941 137820369 133 50 385811364 913 630 948206195 630 451 690505483 64 37 610262565 627 975 165956517 290 586 114237917 395 860 263160844 264 908 649832806 708 356 974647769 519 530 651863064 464 814 213663887 322 393 966542691 300 433 644092765 774 70 912483404 41 786 573888979 606 550 824192502 172 784 970132776 651 836 868299557 869 858 616859218 934 465 190187323 618 270 136716714 981 251 618849192 828 707 912973694 384 206 114418824 827 593 123188405 175 752 250386426 712 17 862209333 216 666 955097371 869 924 931286255 548 144 921028691 953 930 473995839 630 345 204368798 126 621 617072627 160 803 254357470 774 184 648112224 67 471 6664769 196 451 455556562 970 7 514001220 478 184 384561087 137 404 728624936 274 890 837764671 347 755 320645441 959 793 438396583 173 398 36569096 251 895 307242087 893 388 367628821 721 52 290449437 358 904 458997517 439 793 878581884 341 761 50861389 783 64 164185455 621 57 429392903 654 23 928073857 642 677 752519206 646 847 142136895 872 864 83778468 899 241 697238413 402 616 629372488 218 198 347062195 867 367 949953348 940 803 843635742 318 430 226405706 681 170 3507582 906 965 690698591 130 159 749784397 118 310 722222156 55 866 391140125 783 25 131975794 196 767 251791550 829 194 333563004 681 806 36631543 551 375 371933077 213 968 765053967 3 75 473001770 832 974 839619154 978 809 409735252 118 857 49446589 18 421 769384999 816 120 126668847 951 174 210322903 319 587 715951428 190 292 907920783 565 332 788182705 675 563 589315253 253 1 296786071 546 237 393862302 717 232 924195125 465 169 9207798 142 807 998622243 207 344 372538108 588 312 279815735 117 628 289804766 583 265 299237828 185 223 891483345 242 290 192602013 177 422 720728244 417 748 484579999 762 304 325011166 305 541 472519749 344 831 937955616 670 952 74858336 393 101 157696338 666 149 249361587 913 286 284382732 149 704 923803106 59 505 817137937 473 228 294800424 735 447 563600312 805 65 309094209 283 126 867522173 566 690 974978244 640 626 941392266 656 376 261330450 648 758 873611906 451 93 92807800 883 719 994999545 315 122 734882197 702 687 170622432 137 399 384404294 612 794 841156451 971 282 586397176 109 633 226796963 239 812 901055814 137 982 124529059 564 93 709514770 475 297 432444493 817 798 779508927 897 848 367380182 727 826 883357053 116 477 17845071 141 675 383044760 380 550 382331239 777 772 229254781 529 292 385408568 119 523 183419558 843 972 548701489 747 549 205906698 396 151 72991008 886 855 468086556 318 89 180425463 539 760 277476999 358 508 101108652 238 241 608607433 147 570 16090647 121 807 920890766 706 286 754203149 140 912 574334668 11 228 430661403 120 652 447636867 298 706 1231487 719 758 844430223 619 785 572779407 197 290 984887385 610 12 731066263 456 502 19648498 909 540 28929900 946 771 223400821 848 13 443748537 361 1000 384205794 881 636 119924960 621 955 553912521 723 193 388561148 176 564 749591433 579 413 911997906 331 990 661979366 393 229 711044157 457 320 416644393 170 708 697179632 739 250 223513490 465 754 958364370 299 438 978286246 76 781 337145881 205 102 582659449 937 920 166363779 186 910 652120065 945 83 490930482 998 383 609282608 684 139 576152906 558 251 946344462 499 960 329861195 958 938 845109389 300 270 300908407 56 67 177889919 494 215 273876006 346 689 974484439 334 646 268661074 936 473 353072636 345 112 43019588 627 778 37630340 1000 711 343744658 240 987 832289338 362 177 585627123 914 848 734314461 633 722 714511933 643 149 930052116 498 184 946237814 660 78 820094545 726 197 439366909 413 509 439591600 97 536 988860335 547 206 526573050 255 185 449367384 37 669 167146751 63 784 345519110 552 934 755884919 443 107 44972099 808 317 762009971 424 337 221088386 754 688 971748739 106 63 434759058 962 825 670847712 840 790 418674517 332 116 233912256 777 173 93882381 635 441 286565357 650 251 730952935 326 471 806251436 917 482 262663237 129 612 656925143 497 391 236540461 939 360 398078170 120 697 484479871 377 282 654658386 743 442 397757183 909 241 755439847 239 737 287798078 225 786 737915385 961 944 256361633 378 314 786481265 475 195 950505081 195 418 450740033 301 384 619730719 323 467 165452481 966 576 478918835 446 153 843303717 38 168 608759386 463 245 607441406 23 925 939313759 352 423 401232229 261 608 642182240 810 593 598325490 770 169 487989433 533 785 869173292 902 791 323262838 664 190 314072437 604 682 247565138 758 563 952251510 46 151 607400374 387 329 584567065 863 884 144367210 848 712 861559003 106 28 878232588 675 215 32026961 142 296 891201113 688 132 137465454 343 26 241047211 74 175 127660687 114 216 246836731 284 227 573232975 371 187 554323933 799 365 3297760 118 943 511407109 13 481 556814964 693 687 456582572 452 952 571131093 504 197 244763103 92 679 175353862 946 974 673122142 867 571 562361405 514 99 549927654 245 549 335610043 50 127 583669089 543 123 134879153 258 611 20534880 90 174 58204558 699 412 697288372 109 590 979577692 329 947 685570096 858 517 67038186 161 702 24497282 463 682 701194889 154 67 527407738 416 37 558152913 184 824 556797902 507 59 995594979 957 581 239580000 144 351 542284458 361 80 905893515 180 80 281703577 305 648 684209193 756 93 783401538 677 802 560242900 176 545 302414304 898 280 523510960 831 605 587731095 6 442 101510286 498 697 317239840 786 164 528501321 274 458 367095433 708 866 759044725 298 14 483209787 653 445 103703734 210 919 249531679 450 834 925900256 874 493 294945721 648 174 916062563 919 217 711060728 994 495 428080688 615 403 576151204 781 47 306685356 249 522 137909637 479 272 517682321 583 131 326104321 449 87 213774966 23 603 199240353 684 879 736860808 960 469 788783678 944 710 730833248 102 461 977614797 936 807 459106027 586 605 275149034 489 724 982330908 805 342 944221908 962 883 644015518 873 770 788870976 732 817 98602318 52 994 213285681 882 195 577351369 127 975 999207050 639 673 885264303 906 557 302978945 890 445 833928674 438 182 461224973 840 322 366912305 782 173 767826468 276 472 270682793 435 271 548302458 359 983 823485091 399 523 285805660 746 462 183384710 773 785 338539547 84 986 554179391 870 533 559907614 901 844 203404738 623 890 402126531 61 730 331968364 345 28 965794897 444 603 387879042 641 333 236291302 45 925 321704982 597 390 39945941 634 530 67459026 117 356 672921611 422 454 374412707 199 453 863806100 472 488 207865812 551 862 296313934 342 931 826167301 569 433 122250736 646 960 870311457 448 434 577094516 28 11 395633439 467 142 696304975 963 913 427299729 910 523 247029997 296 328 460574446 282 498 692219581 380 830 116291047 931 352 700552212 833 476 718484047 929 438 376777031 595 321 986608327 798 771 157731028 156 856 672886797 452 959 398681202 735 719 924523917 538 215 509287099 35 584 107542886 681 582 224440078 327 893 131785019 166 322 561159176 247 245 204409272 579 922 363984226 275 436 983947377 827 361 924552348 392 276 484701370 25 688 161403710 465 21 617596495 509 294 754386162 537 288 328034163 660 644 651378221 986 368 586278861 908 558 939835852 983 159 258280756 488 651 923392023 812 994 863346465 234 256 632762526 307 469 893340637 641 987 279733622 362 871 611300993 173 133 988761672 727 952 781950558 920 259 513590102 292 681 810465195 435 272 551178945 95 736 105331015 641 417 202284195 13 195 800314742 391 914 434685511 71 699 475703480 186 67 401943066 396 861 909997982 334 65 699930850 800 435 373365281 238 2 747136176 917 796 86684131 991 223 717130661 550 131 287848142 578 377 898838325 38 728 811874703 24 80 558789166 725 602 715820581 288 728 195269725 266 429 372118699 337 140 987559672 231 348 261058303 121 572 114816296 282 876 490314976 336 178 978594198 971 241 933665020 444 12 167947109 210 298 436430872 538 334 529906598 525 719 569416755 510 798 329823983 62 650 853893105 429 185 592535419 293 957 590818961 712 171 676813024 882 885 111057179 835 487 149653103 386 606 998506114 98 510 343777966 538 117 210968673 741 452 585892497 666 62 26085371 743 26 534463495 103 597 384550714 133 313 982716824 543 558 699354131 881 14 986533880 696 806 5206158 211 735 190034857 679 356 762681297 385 67 337896120 322 850 553143387 564 471 645505515 542 124 947243054 785 679 922556841 257 844 54134521 417 331 622248824 511 588 452090870 775 454 570227175 977 961 663600595 274 430 490486971 651 201 152149098 338 152 716830611 876 985 848753320 894 983 976456739 438 895 375191462 548 436 556030509 443 714 148988775 410 142 965233797 352 183 796441742 224 768 500516779 380 131 710607502 805 714 100365750 630 391 639310326 649 21 51969291 202 780 287508947 564 743 933602314 596 402 251938837 259 239 833567126 507 470 197934411 211 978 155542096 497 225 796700025 920 824 171414566 644 506 955898250 149 586 674558334 694 306 153518555 695 679 38067371 445 926 984910659 200 94 76148480 506 931 711450914 964 744 955480779 749 966 388769534 755 496 602016849 4 824 845306906 471 95 211921381 253 86 762532421 384 876 576629697 422 616 897328738 252 429 972805145 428 978 739504304 743 245 82953818 125 669 571517980 961 354 487113018 786 614 580557939 144 709 256403169 256 630 121804483 726 93 263490728 574 950 852488794 176 92 170578233 656 628 454473431 887 427 615291669 83 831 13570518 524 248 389791383 864 936 439583528 348 285 163015540 201 528 152170715 268 503 116279517 555 259 189530195 125 298 220457981 509 919 298914044 310 358 560825778 516 88 577121501 590 749 119696722 434 497 499459493 67 103 347056458 509 25 561135884 380 354 487002651 498 647 655805015 934 478 253742328 886 837 887793207 752 742 19900755 456 830 223419189 516 983 957908322 136 389 318102631 647 444 540827765 473 785 631935577 422 139 361037309 92 504 347290765 958 38 638375026 693 803 709239899 537 151 260190233 647 605 410172816 800 12 221960743 196 235 699272648 320 945 546135610 850 763 913152125 51 150 421701098 593 148 898915813 321 941 352044947 716 881 307942317 925 784 739472103 870 318 741730344 537 683 914842806 149 820 281950064 12 295 31265773 322 937 443957931 343 244 593996863 515 499 416702494 316 292 973583609 42 296 603088924 422 597 704292045 311 613 277987286 887 776 44048613 188 883 989759039 306 792 937209754 64 256 309334902 462 467 288746413 125 368 216093074 840 38 742577841 176 700 298517575 96 376 912747533 893 951 4008748 947 986 113767398 716 951 177179443 282 976 704443240 115 153 192904125 366 241 932220942 44 364 773371177 213 874 455580646 2 682 52991018 910 795 585854324 235 743 437541969 161 341 824521140 117 198 341153367 5 159 584567676 128 84 971200252 56 135 123534747 568 241 259713203 230 261 231468830 582 52 956396411 503 38 967136313 662 682 532810547 108 323 917255245 898 645 203186696 104 520 898705928 872 851 916622297 334 958 883266926 364 35 951393759 898 560 263406273 217 540 14911746 692 606 659486800 874 63 385586401 731 644 75830835 962 80 836085929 926 648 704682502 190 634 336204631 596 981 317108349 210 22 249184843 44 999 232898974 772 13 767884514 550 290 84162438 110 810 319999824 270 107 437326995 719 648 87228245 304 208 215350406 611 867 863266030 807 695 989289796 453 340 822060924 199 963 652082681 987 997 146027084 396 495 453025497 148 308 242336522 73 803 98165891 412 561 387432007 333 367 842642058 850 878 307922081 817 792 151191429 67 460 714627039 556 497 508115928 315 858 257765885 993 340 967597923 520 281 667727467 850 32 590008928 967 597 167238690 610 474 740165565 261 958 599342006 82 217 309940403 642 799 809472930 547 34 24071548 151 173 172498667 217 799 329525803 586 210 581607119 609 554 127726130 98 239 629667557 332 658 566169572 840 249 166228820 640 15 398456782 206 141 569624375 556 280 532597950 532 915 556335321 397 639 408300730 207 172 258311364 561 86 443674241 490 782 335586284 198 180 239046130 817 253 837750951 60 501 908557417 910 56 794965694 73 279 281623890 256 40 992449023 946 304 19292903 836 921 498291296 327 783 768985256 695 494 682501573 947 439 676447820 652 625 480056266 825 489 401019456 897 455 419841119 943 29 558165197 5 208 30105079 257 939 409986012 969 538 679448874 789 67 332014684 297 18 928626438 172 423 319126471 817 847 120237892 636 277 597496059 845 178 569914091 511 116 540893567 181 268 709947890 373 888 617438689 956 16 786840554 76 892 949472668 865 710 496107051 106 292 122301078 421 251 964389116 793 891 127886186 641 9 41555578 650 738 486435417 184 207 174243578 391 19 763576804 607 511 154008344 74 623 884403402 216 30 452764744 454 864 507441905 875 421 174500403 654 815 489476998 912 624 27778815 816 667 695847798 25 742 742192347 604 376 319979874 920 905 130640295 796 800 106274230 328 829 383209529 706 522 333859138 346 802 567544363 378 523 370251923 215 764 43609203 640 4 270813431 123 170 997378000 875 35 390334028 391 275 307371389 319 615 955796176 483 958 806006201 886 977 987483864 905 951 97382729 906 57 621839253 282 657 140168241 345 400 972467362 323 484 720085437 15 103 47377314 281 943 303170658 617 264 8025931 437 261 672426325 460 25 501924485 75 281 359986220 265 408 529713289 678 311 912489108 207 966 638230583 486 305 730830847 121 91 396582196 125 608 476522933 78 534 690075657 748 148 502812660 43 800 859732040 829 291 480522276 656 720 675166203 724 747 808764686 235 598 454684299 505 796 667975618 580 244 203042479 216 358 899188596 538 727 974018939 801 42 763365596 178 860 546744479 136 185 771084319 386 838 996010555 520 207 694249904 443 865 822507281 189 711 54929314 675 939 358701099 914 222 710315336 48 468 368529555 129 855 126839862 518 861 107475394 8 631 162348216 832 189 840803709 53 594 795992753 798 154 620317438 454 480 244527448 154 785 885881543 357 681 620405392 819 498 286707268 565 16 638119130 844 523 501311213 227 200 641182905 251 830 633191020 221 958 639939307 957 938 330824838 773 577 696206965 634 635 264225821 853 293 572916725 977 53 10272749 534 128 126609339 797 296 932720889 225 188 499819211 770 473 448588474 300 594 120458249 587 804 104157413 266 208 380185884 853 292 697248526 137 782 296775272 412 702 218485873 452 708 785157076 196 571 838132403 129 642 96832806 220 405 256046357 903 363 902929323 480 845 46378915 381 617 960695995 388 610 77406012 678 850 619495640 876 626 226244284 899 867 414994462 594 493 997893324 153 214 377113651 639 668 682235322 370 48 402678492 475 725 622100268 918 851 865040962 87 884 580111020 186 695 22519808 420 798 227214089 578 946 725249118 520 382 611401625 716 274 652362227 495 291 412367409 573 612 876363512 730 964 963075959 513 120 408477453 914 616 488456200 255 572 919100022 644 519 339252302 198 280 437476936 739 136 570893237 795 512 850028230 576 682 681696691 530 778 366482707 855 811 23081552 485 974 450050084 910 443 908164181 999 113 166671054 326 855 145888765 954 79 778271646 428 733 438425900 82 961 127791214 8 970 780829035 628 515 654092468 789 691 510304184 433 271 738379032 825 655 590949380 298 688 430244919 866 384 617761193 786 344 804677422 870 185 393900752 515 769 430072772 65 516 721581190 547 673 941049018 514 4 991470631 331 794 274206936 891 178 103717412 636 987 314032610 949 306 339164018 281 557 980573477 503 715 668673669 849 68 32549389 736 959 537181952 889 121 628642645 280 542 576280369 658 570 72308622 645 609 535708465 109 966 399756880 989 167 67739931 320 976 334180788 173 146 357169812 397 495 342245075 491 617 330227353 891 644 894296265 756 690 349208867 260 205 252304776 97 601 340648047 899 524 328565077 550 356 135416508 48 375 11694194 720 937 621293321 576 209 835422526 639 904 940644968 174 626 772289896 667 125 266473593 412 166 315543182 94 603 360638152 86 407 110807714 463 811 849249118 442 987 215260165 860 26 547983011 900 965 855670525 878 767 771462153 892 788 860092543 32 865 272561619 92 247 563474963 282 664 419499560 768 58 16735007 994 878 921771432 472 903 342541591 482 443 428235950 420 785 949270594 221 680 126768159 85 398 986424619 448 389 792564802 487 763 859091902 191 830 336904425 17 829 345410579 146 50 771569132 203 502 371397099 672 390 331840269 769 648 713046972 316 510 202196154 699 240 986778005 613 30 509406334 567 493 527114786 171 952 874330048 848 868 656319116 243 745 969889122 231 383 108947386 873 749 67720361 894 173 357988409 352 734 563301509 924 83 522507127 691 497 140890935 651 347 130957651 159 984 131137290 121 252 132842039 971 158 301445945 728 959 641122595 540 425 4132397 979 5 364809166 72 584 708483689 409 838 953967339 720 875 948010678 370 32 792874368 455 799 236992587 413 56 522425648 217 878 323189395 544 443 243980781 696 126 239702012 838 676 865586254 695 716 903426002 403 348 937890507 679 680 675856585 964 353 398504502 286 53 484574118 39 751 609469771 362 136 309922092 615 163 929716871 186 741 576993930 188 214 311874675 744 129 863149804 846 760 144080904 854 27 91841144 783 666 954018316 273 463 341769692 240 666 238184355 497 520 164076990 604 37 704233039 835 301 746382994 122 890 882742790 9 777 510928564 435 388 632082691 387 139 485457829 180 482 169339383 695 417 946265067 55 961 417762644 54 570 860718727 592 298 251552800 322 17 606565632 837 308 630718289 2 525 263376952 486 727 547537164 853 219 384827237 425 605 300804990 517 909 129256421 119 984 812674073 12 378 682359671 285 701 471291028 583 17 868935304 819 708 580993234 493 180 471649052 142 860 934468586 401 944 282556744 459 218 971467512 199 708 617853639 850 601 558697331 848 182 355214136 596 172 97944329 66 716 464221660 74 115 192323419 546 978 262966775 949 430 182641939 321 840 180604782 825 153 472038869 905 63 851956788 928 729 442213572 864 104 8540364 444 706 177499871 999 190 258580064 912 899 100630743 152 555 207749411 764 387 215581579 90 126 804379163 194 810 999846884 358 753 935996124 698 422 642001950 40 774 607564134 548 906 586501979 785 717 381132099 926 296 937778663 889 339 119441182 454 96 360422974 916 879 858852308 531 822 686650678 355 253 491877877 780 430 83272800 20 488 744255080 874 725 275823548 661 683 348759583 540 561 414322162 78 783 771276069 648 773 883309715 470 34 435382012 833 172 753777403 581 402 135651162 657 421 197209799 387 757 251317611 884 842 328788669 62 506 223110261 491 496 915199616 958 36 352590758 833 253 510785435 661 85 14590887 579 282 25446265 456 906 782180724 538 571 251703877 804 354 338216285 618 210 107852476 606 602 275601669 625 876 818060030 24 457 856289100 242 298 667586331 344 982 44639779 985 726 923837111 572 827 227726780 459 737 41603294 525 592 709514455 705 317 5706017 309 116 825375712 681 810 913819511 382 519 304794460 868 844 85274853 796 708 478399855 637 823 816266026 211 867 736381940 617 4 778555614 652 111 344314400 889 965 156883924 556 62 471265594 127 622 570386096 8 529 482901947 501 464 417501026 269 66 912086662 624 953 317266665 880 650 691906232 773 890 513429682 555 52 739571789 14 265 872489885 496 461 775752957 128 719 111106872 689 514 25849062 222 677 67840929 916 34 961022889 50 603 399786531 533 236 135946734 968 946 992596643 171 414 727201608 395 183 197967859 466 542 644678114 566 772 777810444 293 36 359681473 248 370 280691803 548 386 897696903 563 458 702658994 484 391 895111758 883 779 473086684 862 105 146599420 36 345 794158371 188 989 195781396 339 324 723227287 445 19 728008001 168 138 994186879 281 221 373440715 46 740 117033275 345 359 966671311 264 861 943565270 243 142 299310623 349 217 486254926 961 627 404835655 138 887 825470928 286 483 391431381 19 211 211061656 767 803 7172262 993 296 207861715 415 439 852344676 996 383 857878197 490 229 850387336 132 815 810172296 254 862 95495536 72 296 696287732 837 783 338281586 618 741 370023335 890 759 83327355 514 965 879869202 798 995 637067382 593 134 669344308 634 990 639771232 525 501 239770235 130 897 862193883 244 950 290175063 985 18 388920474 35 958 496564188 527 874 413997961 597 14 830325999 797 148 891054569 982 430 57570683 211 68 480735 801 533 899775647 980 156 938993850 529 540 383670817 78 984 379805164 969 574 278339363 802 195 400719503 351 245 769064274 549 73 234973057 431 603 425919111 308 671 999234147 621 245 523937631 340 487 959506357 147 995 355307890 899 730 501989130 697 5 878459052 488 644 482001379 234 454 286733640 141 367 37767663 556 71 160185742 855 201 430815828 268 738 670121036 875 498 413296443 58 559 91193034 176 185 132966617 847 129 2693450 792 602 114384860 947 265 783352000 652 527 181009112 886 762 214284705 498 436 396752688 592 102 250408024 335 194 703317354 534 88 726607295 96 47 827747306 784 429 437720599 737 644 428694025 672 750 661247655 703 832 120181408 678 757 276740977 309 218 315977236 967 404 216588560 243 776 14349273 563 575 522313069 600 821 274754989 855 385 547330189 593 330 411619225 635 305 731890477 92 961 398389760 373 389 527428591 682 248 990556416 933 87 612437576 64 772 951737692 785 325 191988464 671 10 408519402 507 538 341175057 803 579 163204147 896 604 8702368 626 977 765298956 983 530 880768536 951 928 969997493 451 507 912744682 246 285 559991671 274 543 314368741 605 947 598821742 240 781 68259919 319 209 678163307 34 86 610412203 82 127 209106467 739 85 501086919 712 74 747325307 322 532 847637581 316 796 534848828 802 5 706460386 230 122 749088229 221 734 471713343 600 972 705880004 959 379 775566739 924 807 150197020 306 21 366461102 512 139 624798602 442 440 552371310 616 929 208800290 535 996 477810627 670 873 631815849 322 833 504663651 648 482 980914087 707 273 945222586 936 724 937688138 543 216 664216805 652 610 113300247 476 582 31153295 838 68 950884424 529 801 115578156 222 941 10266652 597 546 21867727 679 475 496525627 643 163 586238627 371 126 966576359 14 236 254285083 351 416 68846743 935 44 81148452 264 976 527982106 487 86 209862080 161 651 59347212 195 578 914273405 439 497 804756781 273 854 866390555 713 216 531107523 555 34 608335170 953 860 442174945 815 762 974409507 700 540 954656129 925 458 240144099 940 756 590153385 206 669 54950069 960 25 148505513 791 852 934804278 342 620 179467718 220 860 513723238 561 365 611799412 886 52 615026970 734 45 875654015 319 681 381395100 520 32 842913981 579 109 960215547 710 102 959537273 623 528 177500497 409 896 334057177 154 270 90406900 561 982 13672625 184 402 213103866 179 637 488608384 803 305 992278151 587 275 927761997 129 437 704059515 596 293 907315704 234 295 974180033 172 346 400865452 131 369 417090807 159 80 357184968 704 629 706390482 638 843 653475584 935 628 287670149 519 137 142901843 337 348 60743046 311 610 312788228 974 72 991754055 243 40 277190083 848 855 539309086 183 971 417869396 47 485 28361427 681 332 722375059 33 46 809747773 69 522 713511461 279 628 802309521 971 755 492314638 578 722 188738322 537 116 392320544 345 162 823521508 183 182 127856321 230 526 205627027 590 738 783324672 683 94 99683891 859 826 601718336 951 460 497152418 728 124 905325414 466 571 893918737 495 318 810049117 513 577 473274646 829 391 642918930 223 47 774668306 341 576 165247201 384 496 367048296 761 259 342252223 699 311 537874142 145 605 605626305 39 636 548373629 207 695 848127491 550 717 61763014 884 920 392740298 511 364 79987849 4 226 163440293 407 127 598142831 473 41 61852655 302 701 207364613 430 627 107568406 981 399 77098661 761 248 437032842 157 600 15288382 39 945 766310502 694 733 597074550 393 990 344146163 954 92 329438402 325 550 65440279 267 518 194478563 181 502 451201478 13 445 174388204 406 367 968675976 867 409 709544958 854 605 901329772 986 816 953672978 890 120 617958493 658 943 984941075 131 47 59099680 728 158 681336828 813 377 326997932 256 717 670304482 118 131 478750541 324 381 988469669 921 979 385932860 957 740 386980599 633 449 792723902 198 979 79162091 459 226 581842566 841 764 244807065 391 531 971105059 775 588 246074257 771 16 859792991 498 678 825332824 873 801 923515481 316 479 924315055 566 897 679206184 841 112 249062181 806 287 122268286 569 84 308062310 585 762 602785721 64 570 851188658 122 350 24665908 363 548 555458993 341 140 993487483 512 935 359035336 71 601 668502677 338 729 975655033 683 649 442195616 501 139 298727932 129 632 700167985 628 663 220820551 985 883 424976779 360 114 444290475 800 765 118861544 305 958 750516077 103 339 375791024 333 76 92409729 589 116 792365288 857 470 61142209 81 704 551376408 251 605 789529090 211 173 399352537 927 913 888770796 986 28 98075894 769 609 793883477 90 252 367002430 406 484 168937185 361 545 584496681 215 960 389167073 323 548 599104239 548 785 364524102 81 226 372389105 331 338 457650921 978 149 127215891 401 119 753287742 464 28 317996293 669 450 579384247 76 758 36605522 870 562 853281353 133 158 784476557 329 946 231048934 105 446 221685768 823 8 900742707 347 353 956658136 705 318 551604018 65 980 331597728 723 426 9755703 408 896 620143580 191 829 775906639 161 418 477558566 20 92 197368460 922 51 745887082 473 198 891947327 716 398 323451495 941 988 101838361 8 661 568875077 697 733 235060401 837 65 768260403 749 156 168162771 958 979 654095321 11 943 326728767 862 433 754407570 617 27 346317326 55 195 774834744 17 38 10160548 968 130 341790580 993 610 996277810 577 297 652480225 542 643 925529763 65 455 573611442 545 888 707441106 938 677 488807102 189 66 400279697 431 92 685505889 764 724 550053679 662 547 772375566 651 10 698553652 995 245 606202225 400 999 304741634 745 519 929875167 446 633 525922674 674 609 115111567 319 359 335086856 487 393 247423518 141 602 227766789 619 404 846611280 915 502 814199577 780 802 44065213 857 707 857924022 782 957 752612497 445 233 687222022 837 300 941653930 398 643 619243292 453 956 604395699 915 319 214475437 609 604 450059305 734 850 342555979 345 616 936712307 543 777 616378895 740 620 382435719 99 434 198402393 939 126 411351920 39 163 973147687 874 795 596105832 114 962 144126915 720 961 726844900 333 488 2574797 780 407 719014097 806 671 509925919 586 821 648064381 987 203 969292031 924 498 163643381 57 763 547965178 720 121 997880183 927 773 156717668 432 408 402547733 951 675 897832303 917 527 847564194 368 699 881603937 427 112 116473784 562 960 838151945 670 310 129468429 934 14 801918990 520 93 859663183 657 832 134156757 865 871 223341137 10 655 717555963 702 519 437436948 188 768 730338666 525 289 905968728 230 10 163910027 571 537 289740117 549 772 657641512 446 737 600235242 79 411 114602267 525 59 768121169 737 367 907485318 469 676 920656119 535 614 993237146 160 561 859247498 89 148 100996549 232 476 431882318 698 161 82712033 576 6 43822823 877 944 403749187 872 486 539691871 793 431 744913450 625 122 922403834 201 739 656298899 349 21 657980982 509 935 370828359 732 952 717911294 766 934 485967674 150 884 217909358 413 696 500145160 673 584 946691001 204 876 488073477 912 155 38783017 406 514 798111315 359 752 137620569 432 986 674788029 462 400 460250428 731 505 425418448 461 312 590391862 376 646 725889878 834 258 104256514 822 914 753351349 35 876 601085158 878 240 321120333 90 24 150444169 336 322 688427171 446 686 674442300 437 407 39375110 214 653 552526172 216 98 823548559 379 182 318932158 665 204 900551755 76 434 42663797 849 59 71928846 286 152 269336447 325 453 52758633 771 141 346101544 141 394 822279022 702 732 668139557 441 402 979631116 309 126 832853163 891 577 952618007 963 318 164438458 136 837 151213225 217 429 300246167 113 48 736533898 704 900 198618361 884 512 253511324 708 69 469330214 35 12 311271128 767 889 287025812 454 435 354708447 333 385 230915838 408 404 477446563 880 61 789962447 39 740 321713630 44 972 821372912 306 85 459413866 355 368 200584769 896 253 972725228 832 458 443382604 745 494 221302478 758 182 710519349 974 735 677208910 105 209 784237575 897 147 668511869 773 175 382516052 110 585 812212911 991 746 769785192 588 846 482562272 203 983 729006929 377 494 549935852 772 806 496583135 974 354 4841199 2 219 739840558 300 975 208199392 877 458 983812592 281 372 526136352 231 676 778086463 708 598 322933838 154 330 472071900 396 311 9719655 499 684 121303122 511 791 358080666 50 220 762259987 253 345 562992335 324 262 593161301 674 846 201640650 899 313 125766164 360 547 103020812 224 884 849223678 349 202 483736583 394 863 259899298 736 400 987172472 797 511 811955593 979 20 728310100 837 875 827812285 566 230 325815493 844 883 459331187 138 696 856414565 527 78 525547266 284 838 964621876 584 840 995724192 563 181 678766472 592 758 745167096 276 452 940262245 747 558 357520762 435 869 10470938 945 206 30917886 337 909 568858680 875 105 780193649 954 430 164675409 138 843 593931986 358 135 555426735 311 792 672453944 141 395 599956086 347 985 606602344 103 873 778169574 89 955 31680041 45 10 116976558 617 376 500364097 439 124 868792220 390 275 750790719 679 154 422435771 151 43 252712954 437 980 704716211 892 735 745136656 836 548 979157676 437 77 267863080 640 115 570818251 709 287 355008137 701 259 247004137 133 434 677317994 750 880 639380787 164 152 700194082 842 42 243402078 58 844 923158691 789 506 296321614 819 378 396167126 946 112 631862294 739 140 545751590 595 418 558360427 244 921 920760160 462 925 103425714 786 330 125732985 871 545 909649350 589 893 725108367 165 748 487036414 949 709 7857169 145 976 173566568 355 282 170485743 502 975 405737504 305 229 959057810 995 653 438665183 420 923 927741239 994 463 145987124 898 245 600643711 146 929 273758637 819 799 537100929 614 966 301655210 252 64 497364270 724 225 272471605 104 624 166418461 119 840 346425877 986 574 618169738 417 950 114563497 63 178 309847034 547 433 345957162 680 564 720094390 706 380 876841990 582 317 919999323 664 260 928865142 670 136 769788971 845 499 813715372 959 323 609686891 711 755 941046270 253 997 684758991 720 833 698525828 593 126 178245137 852 604 152782449 38 243 936577142 682 587 209717520 919 80 831422025 441 110 247476241 616 514 548760124 51 84 540386127 462 395 637340616 60 462 541403534 782 516 916529048 633 788 971410724 17 270 804731443 948 616 746236053 290 28 542359910 37 185 755413722 396 730 115393070 654 21 124875870 684 950 772004589 360 398 529926472 262 202 816090682 630 850 458998237 456 673 737821615 110 558 748024250 7 515 479844971 545 356 270791292 705 190 424500027 670 165 814178009 707 693 570165253 871 5 285699524 493 287 448722817 768 931 196410244 781 951 717001021 776 936 844583649 380 135 859437386 923 887 697446471 193 381 734764798 108 836 612991352 703 965 315136458 317 921 485226435 290 22 314117866 365 547 282626337 242 383 273782932 870 758 288498812 539 978 888660831 846 787 306988315 121 575 304587315 904 193 137919558 665 752 800069156 740 286 558561484 652 366 746609176 700 46 275096778 514 879 586225105 400 254 517052290 392 430 797484066 95 462 883275706 356 764 7987998 746 177 799776693 414 440 433555929 375 902 111657793 860 595 723390599 594 804 55522855 740 811 655500878 499 558 562154728 23 783 697857947 581 242 454655368 64 990 300517115 581 557 917352276 803 956 482591801 784 670 282460229 576 726 477178334 794 557 145861897 603 460 79774430 647 421 754208207 351 439 756606919 600 975 729082886 167 908 65871160 417 457 41929337 197 946 623223797 677 900 135200814 731 260 213902648 141 636 191700578 763 484 261641222 357 579 993423799 830 775 773869051 859 906 273725771 260 785 717024873 346 18 95621691 16 161 789073984 466 603 888617181 731 555 90968355 69 961 12723104 826 606 300493903 302 768 360958062 962 932 256950615 208 190 786570767 143 753 309018108 187 930 718598911 229 320 522795834 792 822 620779632 836 608 557149214 895 200 983122322 626 15 628714276 571 807 698729721 806 461 357625056 824 321 505495718 309 246 888927647 590 11 770830371 666 856 57103773 19 283 876082724 94 964 103522338 766 161 160593112 827 756 662916068 806 120 108321476 405 338 624981042 52 268 924815688 189 115 534188405 921 765 985919420 459 587 923001131 478 9 165159447 132 991 560625047 754 54 313338873 209 361 753605559 280 599 163298933 369 151 453702497 847 335 311942229 714 482 312786663 963 60 872278081 624 306 520735565 62 468 705639342 722 516 612647688 33 750 659760736 754 307 779381865 132 635 683989201 861 707 319575261 989 267 391707112 570 387 946804007 131 743 219210361 804 651 385526814 669 774 986309933 876 591 819197822 772 978 782351693 69 580 180816248 691 908 271081298 314 871 52175052 833 643 71438813 573 797 108062049 123 756 125699394 47 227 505871049 601 146 622848999 365 381 765467659 439 693 896595098 89 202 342601112 256 954 773101264 520 933 323096412 911 674 484071890 320 546 830966304 126 665 888625474 845 328 5009490 447 614 947432732 51 687 765195456 152 131 391338529 271 833 791004431 120 814 429366401 966 52 530552352 737 900 609077376 856 999 674460072 872 672 505780811 567 96 302888910 513 239 852091504 842 100 407083773 572 555 901246964 999 500 748735685 136 336 542677931 992 246 31469931 133 699 882451393 319 492 991893309 337 191 869299172 270 92 84805491 302 73 88014742 644 760 567944079 65 531 480846613 100 954 943892442 230 990 373395429 962 478 871115108 974 903 19620204 369 6 252387902 698 126 943876067 106 7 275752493 461 72 417954869 70 331 527826272 824 93 542036940 497 475 206808886 60 134 390719401 885 183 541741833 275 745 460761558 672 969 155639026 957 878 658565713 614 165 572370701 714 982 485543760 123 638 564727811 105 342 453412928 890 256 422008942 693 372 480611779 275 904 666711178 622 724 208667726 734 451 485970332 675 41 952039335 239 531 758767877 48 161 613641566 833 540 253021388 395 836 825589500 675 626 816182215 797 542 278474980 693 3 566228374 17 774 396301882 246 191 342766416 353 84 810950187 686 602 269790301 688 673 81637020 56 29 281614057 393 954 279879074 519 120 880720856 861 385 156920096 510 365 626530372 659 258 574099372 479 819 192548615 516 3 663502765 630 400 828925292 30 505 400761585 175 289 204262543 718 159 911383373 933 944 481317410 81 618 851508536 309 173 702183065 983 625 909322290 401 998 761893256 873 686 55901722 364 472 244257520 434 369 750742996 653 84 963929534 471 870 388891464 387 116 859740124 997 608 628981407 373 241 363837103 555 457 758527099 194 97 205716551 897 342 817614379 785 178 170507193 748 31 703705095 140 651 681683118 731 243 594229623 456 681 850462259 601 719 183697634 326 512 966436662 926 816 64334454 827 473 41891820 17 365 889358878 263 615 983358270 284 195 24220065 548 484 710036301 203 337 508476675 28 214 667498499 795 923 490639016 716 748 786671104 835 604 700444694 359 644 785333974 676 536 888347975 435 362 100682114 293 249 448678141 500 316 264723120 43 221 459518211 489 854 80172771 373 529 955140059 479 944 649096605 114 931 811870630 860 21 405221208 345 192 979871014 177 30 582023713 629 879 916439321 55 373 840982027 730 80 172702832 305 698 329172256 84 441 341189609 992 506 425609328 455 337 620671688 685 517 704702584 614 501 829069532 265 71 278797339 200 915 105324219 103 675 523277904 404 166 532373775 281 974 141176477 939 79 224304661 205 877 489107154 5 669 523599615 331 335 299079521 919 114 771093901 842 613 829192280 2 404 760086651 88 209 646768454 506 401 681868371 542 291 980193756 721 888 34337316 157 556 229796323 119 739 756289398 394 30 658447422 620 679 368347614 124 615 318641696 930 464 999545081 661 41 257286547 820 321 367547875 621 502 477344114 593 680 366922336 184 492 215847983 978 550 803168657 265 609 977555494 569 87 63493919 482 586 16998526 124 673 926309125 845 954 778555189 583 390 214536423 637 654 135146176 805 254 394732857 892 481 359321557 729 262 701407420 670 591 560288493 654 481 378163205 446 560 972461269 656 668 995376789 574 333 815321284 895 775 819891083 263 771 656196375 295 928 751413577 540 91 965671093 783 573 911398107 798 89 414225995 240 850 448716591 254 565 457779791 986 65 915353300 296 738 675094328 637 996 3137099 194 645 109036608 527 131 686344655 413 482 822838923 560 276 68805371 116 150 446811514 470 425 411924499 798 168 247882114 220 3 251132319 152 111 114450307 734 277 830117590 857 228 833055545 528 696 880405012 105 878 572069007 303 814 413788532 932 815 478346638 49 740 114103329 577 600 188676278 322 664 444515810 136 810 454613774 321 774 175244967 376 395 609076953 960 426 688591074 724 879 640024193 601 663 185900454 717 367 759055683 146 734 481288292 59 394 571132191 519 56 867623554 144 908 510662398 580 198 453240809 989 19 571470463 139 755 889638045 719 478 690681944 753 147 745983151 425 743 878488809 569 460 403992514 44 52 248195194 80 216 262787049 328 224 931212806 929 309 560633045 636 592 269355831 324 402 815985213 102 697 472927101 781 223 735565115 80 532 283649610 330 340 374004407 937 346 637216377 410 677 90890380 418 898 395954133 811 275 595816734 451 165 492583324 791 565 786466192 714 905 667736082 838 389 146661985 489 899 701815337 29 931 587404197 111 721 611589631 140 64 325774911 553 952 468700545 414 986 950251249 204 528 867070640 336 89 426141118 782 125 161531627 124 387 211776963 463 815 624408062 610 172 133285647 278 667 314617428 144 52 936137759 542 402 918691489 709 719 884097509 738 138 577506718 424 344 429563649 186 48 484448788 467 899 907478800 440 919 97391517 806 691 58776804 406 537 838591753 198 973 197909683 321 305 318235651 394 987 345182525 37 458 383123761 406 705 786274398 467 940 642301035 444 655 2402476 85 64 845598620 719 392 955251249 98 679 169013907 341 978 550736091 944 320 186912759 326 428 355228522 121 57 755955403 880 733 714677141 671 223 374559267 245 191 614769293 677 647 496757526 543 139 53611173 566 953 222940038 527 845 757624346 266 141 417819115 817 543 802390586 327 539 254326936 382 136 453469780 372 662 286160956 112 283 254438788 668 749 563295863 877 638 895373072 341 342 86252434 506 904 858636432 782 724 108899838 111 941 815627312 924 376 884946206 611 138 212784094 40 812 206838120 71 194 803027401 989 156 436548646 602 173 422119168 741 499 844616558 133 261 876991287 633 347 249854290 341 950 572216178 839 672 594371368 587 623 966369635 655 251 501709481 791 688 322711039 862 879 763762405 693 92 281380240 851 70 699058601 120 515 310818057 278 186 220996757 391 620 385184424 343 367 529836643 919 122 177025035 174 985 841477480 518 157 708952376 923 312 836488346 556 576 461623650 49 748 553993795 455 979 135003634 106 545 3616884 881 251 358733431 21 54 466555754 613 694 414992783 766 211 265825006 790 562 591290464 60 39 702364885 810 661 277242333 604 324 304882031 122 239 932951257 122 370 296910407 450 827 311402081 590 644 75356343 11 396 486577413 981 300 532816436 519 164 825102776 38 886 209409683 788 283 756221623 958 641 157994819 65 44 58287464 228 726 252206522 61 381 340840067 237 792 670096814 567 232 770986495 480 989 351912987 487 428 268028651 215 170 784085249 31 342 153349122 449 892 19275580 430 676 521719081 30 254 129310340 601 434 507914349 739 609 575616559 451 650 414676925 67 49 913150971 488 929 280852543 556 791 344637948 857 208 392068369 458 366 25059702 853 300 718793222 359 947 262488017 823 875 674188680 119 740 594593254 688 434 81632305 7 419 156646750 427 526 239514301 738 95 772774610 523 556 186923433 590 194 681939394 1000 283 960820742 565 129 41957052 974 497 73085452 308 383 53488337 198 353 111229384 976 518 587131843 518 279 940944832 280 426 82373112 402 606 377426221 488 373 757648437 358 992 73720550 67 167 674097466 758 873 586343734 896 409 389969656 108 918 559068092 392 226 868186828 868 330 908637531 265 71 952875252 936 167 733910747 679 265 143086287 856 264 674827902 494 613 170363301 486 650 561330904 268 291 454323545 76 215 848756844 43 394 987872735 593 652 121689531 436 246 155991861 748 786 799552794 283 21 507735693 883 921 151172761 10 142 795055827 171 78 200866698 285 878 448424742 312 740 178759273 884 833 671694454 685 86 628178395 128 482 799625774 548 774 893321731 62 466 647173831 982 258 195449777 891 470 86197670 516 837 912166244 615 609 72954774 253 984 55657592 207 570 154716083 271 452 582949598 90 894 311281398 66 965 365758202 55 545 306679819 975 84 162726492 327 3 851232385 264 995 966631086 529 543 422368723 63 132 346795444 122 184 380354970 376 458 813934582 810 203 540804307 625 100 379572861 909 428 820238521 74 588 178752626 497 432 390800929 704 171 185047628 727 568 958980146 251 820 962414601 886 937 909272712 139 527 932108941 823 753 683010035 459 68 280424808 44 375 134823104 542 864 395194252 179 809 820834298 107 267 403343257 501 696 134875193 813 193 800659568 189 456 841661307 603 931 788180013 835 250 317251637 398 199 739372420 307 650 634661338 452 171 661258380 67 375 277811996 756 204 850869160 684 225 825612623 284 333 10336361 417 950 449431173 216 672 71330456 599 916 924960107 395 483 917411925 104 462 861235103 927 367 195857114 759 984 94456569 651 925 395072067 475 583 900579108 593 900 201862636 803 153 186950433 229 841 712538865 51 316 571635653 988 693 322783779 250 22 560814663 504 157 208426500 987 833 925422198 349 206 249766180 417 33 121729193 147 407 998169957 888 441 855253199 466 699 235770026 379 344 661851953 484 147 591713945 117 411 965355816 44 61 60081753 479 505 769852239 955 101 647693390 397 349 617160690 275 255 237043263 199 299 904162667 305 951 428491360 434 271 795107380 618 652 463999000 948 613 40582024 868 603 445719059 343 27 538310798 645 565 309440775 140 2 857853362 852 530 758684056 876 338 60401151 443 967 502343292 13 67 131579846 333 468 348262798 28 321 366316730 222 405 58813993 669 589 902234896 927 30 570979928 690 169 175063183 386 916 502482983 669 94 628974066 682 750 969637905 353 485 920151909 949 164 259948562 448 160 772407063 651 398 140407384 480 463 386002659 942 220 703537594 999 996 568188764 923 520 948717674 997 821 146105251 141 929 572203696 892 39 23836619 162 549 750670483 554 20 891063949 73 62 739930738 827 237 254037866 52 890 186931731 796 357 771863374 773 167 898748110 563 301 4065717 753 980 567593954 66 891 866636642 591 700 248220572 576 132 748019026 258 327 776314491 645 916 361463238 186 916 74180346 166 813 950456443 449 294 916752246 37 920 141574000 601 626 486445089 245 897 656317044 537 649 509584158 47 731 236772087 948 89 180464359 917 471 236819512 884 942 614400455 404 552 256115619 995 786 373815330 959 747 156388919 677 609 335740364 777 760 849922121 460 403 918662064 960 261 516095550 583 960 754929438 625 8 170608727 547 523 771652449 736 996 156499647 260 25 997291154 235 610 963169455 332 284 142564753 745 481 525035307 419 615 237963134 565 458 816895857 134 37 458884765 82 395 39221514 210 729 775994074 122 277 896273246 116 942 906178868 81 191 641192118 772 863 697073754 900 516 692641891 307 377 860836762 625 873 159551697 828 79 393562857 200 746 285080612 120 45 473121175 158 341 605794807 241 578 277230015 846 245 222107828 564 70 441002698 783 648 909313018 797 543 406571024 706 840 574726147 831 194 364284848 23 42 888008800 131 747 462358957 93 116 403041593 502 353 987468042 439 739 203823751 166 235 654968106 515 637 281831226 15 999 16233328 165 148 350653520 494 90 81514997 243 978 820497546 94 935 320014025 940 156 486595343 151 342 549861174 165 258 203783171 772 153 466050079 389 934 850775076 365 450 574374122 952 850 295005702 360 423 196703292 696 172 251822377 117 886 226691248 450 63 711624583 682 259 454584209 126 96 138508478 135 700 668675546 917 116 115645275 356 185 906105422 550 650 604102250 114 209 405477303 8 942 61822746 754 660 888309604 48 15 315821103 974 12 563187783 209 716 909659829 942 639 233983009 228 523 326610074 988 264 757182583 889 839 184066512 494 356 907239678 621 657 693188009 216 328 628949897 149 334 278178271 678 575 194389165 852 173 667788277 829 35 586360385 530 653 969074139 364 182 239770448 649 16 520366936 852 904 362661848 840 343 709915876 834 131 470866097 87 542 520587573 47 260 704120451 864 351 603909637 620 1000 178680440 400 713 861446157 849 894 67847470 788 373 663809188 765 985 1202141 344 516 489785146 831 950 794360257 408 22 531006482 789 575 43566301 761 237 696370374 603 153 890260792 809 464 626311565 316 523 184103730 774 972 430300498 487 159 931167117 318 299 609603111 104 622 146147933 724 413 413452424 259 861 37559687 793 455 426654599 919 800 880130026 303 35 432760357 724 488 756951982 785 868 377703670 756 136 392309344 894 158 17309592 303 580 172818848 184 209 322579289 934 67 73582840 785 758 921013487 913 821 191235356 937 733 213956358 542 540 841324049 722 22 220768307 839 960 237694125 296 354 897079615 508 467 910769671 131 15 212254165 595 255 945635482 894 182 285960395 699 755 695042639 992 582 356651687 920 926 836759687 408 745 290989584 791 742 893458628 628 357 544957283 914 83 279982273 729 812 622077311 474 235 928349679 67 908 529571339 515 914 133009737 321 957 780165189 40 78 541863829 711 260 936367834 816 946 736193795 373 768 225476674 827 396 382896543 284 116 805700818 704 930 287605066 319 773 538401092 549 293 404446968 280 572 811353855 471 805 246375844 465 854 38920043 662 520 700095146 804 53 452210490 815 827 808451585 666 14 233570276 967 28 67742844 745 467 246869684 315 498 336588941 845 576 788938459 235 838 800829355 932 212 308089392 364 710 784314615 859 969 556609717 200 939 742220349 417 321 831779001 781 355 822113721 143 878 861180806 822 284 738276502 262 188 932252529 652 707 528582243 195 920 736225635 441 422 776782820 36 42 53415384 323 525 475733013 783 23 360816221 23 808 279374521 792 583 183161937 583 847 107815611 972 513 837873475 349 941 95785657 777 427 346602492 374 172 262992911 71 616 834737054 107 288 446551884 80 2 598852323 285 101 238966473 194 175 423698899 598 513 303548466 360 329 88464304 346 7 196198489 345 742 332506376 124 635 308591034 149 257 88756701 104 297 508527529 253 81 31840539 39 775 220741645 788 648 945043279 589 681 906723027 924 162 71360776 359 818 339248263 347 864 536600813 45 366 98680821 760 186 573641015 145 273 243059306 748 351 378498379 942 19 291092309 26 893 462180285 115 317 41446354 669 6 871092641 862 853 180602165 132 651 706538468 946 503 459987490 967 692 35600193 833 474 742935477 237 587 580783665 669 756 261152578 712 864 230032365 50 202 495491191 611 87 629516540 671 426 446362202 205 113 554667475 904 731 858963457 927 719 773057094 966 437 803241317 939 370 142565185 290 345 535586961 995 424 662305662 336 920 18390860 810 698 653849442 648 622 844564365 512 105 687733829 671 912 146731975 471 947 290868244 680 176 37399195 270 944 119603988 279 356 668120468 62 820 483917951 616 923 286511636 984 915 749139848 138 141 447087445 777 832 705062828 669 278 861459737 420 183 188361937 866 533 674372201 696 963 665938020 422 472 557679361 918 479 64146557 653 725 502400228 204 648 30162680 581 879 761447635 362 49 635494263 124 541 594762255 683 946 601576426 201 226 698361593 732 583 775081620 927 99 280636147 525 992 403749848 188 366 215653708 322 7 689894344 623 123 157382457 549 361 649679477 807 8 447892499 341 33 742373789 473 546 694433758 62 440 358001848 530 667 153438630 644 867 805297984 320 257 730359666 773 586 875523562 262 643 300002536 251 369 319066782 103 860 330945568 513 348 517153797 345 637 804201150 885 655 620602614 577 102 37407104 540 297 322595197 784 983 115150140 228 43 893622593 188 780 645216443 646 876 321689155 576 87 805476945 974 769 897122672 841 660 976225834 761 616 554246735 243 409 429645954 659 87 771553615 670 399 534127180 258 194 262239081 924 655 164644179 141 238 164879594 362 348 815672073 191 97 621820438 974 151 249063785 146 427 240185341 246 871 502489100 688 290 375276055 698 679 861808495 677 410 626867798 948 399 952748487 119 387 369655670 514 273 186501247 268 957 837853928 218 882 787086938 789 432 577606026 247 798 135624178 477 115 113480296 659 179 545323010 381 911 936541003 735 320 390644154 28 696 728159332 421 880 53758714 995 467 761404911 106 644 280546440 568 427 905789969 190 637 756079441 455 950 333654624 233 428 332249474 979 505 40283715 707 883 71085287 294 497 986103450 464 304 189942863 647 705 929668925 239 524 687078389 56 738 804571619 718 700 12227452 135 604 340370088 398 910 110590869 638 740 314319047 311 18 100562900 113 996 143173212 518 841 665944694 110 391 420875270 785 963 500330816 125 397 807052850 83 491 734993472 81 104 88518105 78 566 593398116 459 873 636184771 705 494 303001154 560 875 292737780 854 503 699726532 728 410 66338178 665 444 576588270 440 555 989427385 332 466 189135541 448 473 582145867 444 516 487996091 863 442 124302968 239 846 832079683 963 258 342572260 278 217 701259198 294 492 662021780 896 148 728996639 639 27 842463909 563 734 925882962 362 91 645742460 244 93 124531719 305 207 330329378 624 171 847001553 100 42 568481105 506 2 808861890 597 785 137024673 982 92 526734291 48 901 189067867 405 140 271980141 337 356 924433070 894 516 732000287 580 18 564274294 930 867 941421277 850 447 122157196 364 473 177262650 705 744 652490426 893 248 144718246 988 286 643614269 780 151 503769291 820 907 671021865 876 154 446863800 573 417 888276799 325 192 753974509 252 708 973604282 661 87 105756276 545 804 471608272 942 853 41598264 845 729 973192638 440 705 68481504 538 422 598952855 9 554 696946084 413 734 556123594 823 410 731059208 901 465 301510122 684 193 392398437 264 964 505340107 71 770 577795393 911 975 247479307 484 726 129857556 555 160 17228802 692 179 509187643 620 520 810110151 299 586 332569597 576 663 679430715 684 19 920988874 592 279 331262500 870 199 640231745 197 871 519487891 956 854 695158084 685 106 130348089 336 641 933905341 968 209 360947035 44 749 193942564 410 450 738911999 265 54 894734173 389 276 89092430 187 431 886328051 305 963 28552004 349 47 80735331 513 247 883380565 577 959 988194710 458 509 64914572 777 389 987888652 514 636 739610408 980 786 503290618 358 990 79512920 610 859 556221482 682 427 247595615 689 457 444126429 19 527 140741254 941 66 534757121 289 671 601235735 956 799 731079893 507 414 444516117 442 62 690988124 119 998 907002533 854 609 333219490 758 941 242867740 598 688 967135228 813 451 921416480 903 824 589389789 952 95 679193805 903 289 715953742 219 79 504452243 463 872 731965312 906 990 651095257 231 903 492648473 528 600 93485418 850 621 857720068 439 458 960371842 799 369 871936558 224 682 231907396 793 511 848656804 349 970 929236069 596 2 92883557 254 313 262213802 177 132 163122121 433 159 916123027 854 262 132905751 535 610 173513872 661 312 449150478 791 456 840977553 261 928 758408681 969 856 708147719 677 952 784191297 254 693 102478642 488 104 52879951 98 258 668218007 403 872 105748665 75 100 130389763 270 592 405930540 818 788 38602920 757 613 438750801 45 637 94838241 91 756 591329586 69 182 262862680 251 252 918389798 337 248 700910930 668 271 958502273 112 162 449561457 550 710 603638695 691 415 794050583 751 540 652144280 144 57 851966050 483 562 365393835 120 668 226453848 752 357 101939865 311 588 546719343 591 2 274701592 194 100 525225483 423 310 366624512 806 625 253453564 146 414 579537752 948 117 239944020 650 378 81456085 864 724 794993471 655 649 340269215 432 949 32070512 307 536 511099062 259 15 790833404 689 832 89753769 645 573 625437663 265 378 557606002 115 782 783163412 108 737 359629918 380 67 11997663 748 388 301576127 675 448 764300448 944 622 790458190 60 592 55203273 925 173 975308048 14 411 485008433 754 470 517577806 754 447 486184124 144 860 401735636 313 348 471390179 323 979 315455991 702 569 216149 942 661 87346233 711 660 173965778 395 862 358946567 375 530 835935043 370 88 527844614 639 981 548674621 970 403 302951318 37 6 902315255 917 354 566457098 573 44 25784809 84 423 711232705 524 852 834512545 885 117 27216203 353 439 256050078 831 690 61024516 990 541 629530477 426 394 995930109 592 299 565442663 839 838 713126514 203 123 223307182 699 128 845657078 596 862 388522342 860 340 90088769 935 144 874029392 158 226 38770797 706 3 23817732 583 337 893585124 819 395 775191312 591 325 660902213 225 64 4667702 576 748 88964349 450 914 276379702 989 359 490861527 295 997 769046871 165 108 135671353 301 754 566561726 541 300 355043809 427 261 372683120 668 391 139572508 950 24 239007481 780 591 121345785 26 24 250810349 112 421 435411466 686 894 337911048 289 193 209168212 811 581 467727354 257 96 820284340 944 515 434854345 538 889 591797464 102 614 236945201 254 711 485299199 43 493 355178135 820 262 382863429 733 790 109134354 151 157 322303190 664 737 787044165 722 674 328754643 277 876 753292117 469 149 175932306 194 770 218447686 881 412 854171155 893 7 672592294 722 306 700052960 275 990 906015515 796 765 190282767 339 672 110161816 957 10 679028327 716 512 920239660 613 971 575212384 810 582 313077404 816 414 192754584 709 986 20381081 626 720 275541386 906 812 621131027 557 542 362175702 69 415 413387516 228 27 431242515 455 404 757152729 109 94 440545230 672 226 956937574 700 263 452854517 50 105 538779026 674 268 687304339 964 806 905934409 824 884 140835794 931 989 759094392 770 276 672290165 468 144 758851308 361 299 361410416 177 48 231090888 483 364 792205036 196 807 842961287 810 260 657416693 164 918 60969267 345 220 750422645 253 263 439125682 966 893 721837994 555 357 174313426 720 232 697383264 209 758 291961520 982 62 715092209 750 823 885561102 719 15 143112536 49 720 677351452 314 17 33909169 689 975 36521391 372 918 408338685 791 851 453451632 971 386 972111747 857 512 1643363 909 594 180318936 457 853 632538854 133 226 480380323 210 464 525658509 109 511 951913902 416 515 858719325 549 123 414264832 159 188 384910056 962 710 550801734 631 892 832660697 200 243 684477135 354 356 271660239 119 976 81568792 940 913 915665007 771 118 224999241 344 558 938556342 346 665 181952166 593 543 802160517 595 156 475845832 555 445 405925436 951 297 924228809 299 322 570378084 829 542 767595070 25 916 903396014 9 405 448669926 509 797 16258913 402 851 432852721 783 828 980293566 528 846 612871221 127 13 777537597 975 643 493157369 886 819 733816474 242 611 838802799 532 111 674206542 233 117 606633374 855 541 493652837 623 702 379334975 160 480 697493443 68 611 677634644 311 918 989059072 110 417 472991462 717 74 408631568 325 323 895335534 965 620 503910462 745 735 672321614 462 986 441701839 455 21 733520075 898 691 422737920 97 508 734401837 476 575 883239429 115 138 420467795 595 430 301367086 412 988 169260078 509 581 230682788 123 297 11771276 105 760 495221148 942 67 175270811 974 541 980391450 296 311 393646462 421 354 930210022 89 204 172986418 566 462 718633544 188 197 771901557 63 57 365520590 131 433 930728852 106 756 615271869 83 247 925551773 951 512 140608684 549 957 324757739 518 306 416482953 782 900 580960797 961 306 45068161 209 529 449318155 448 19 871755300 105 663 23399845 259 314 942159476 448 811 987421136 548 699 453514343 325 510 363419293 21 857 43643570 108 686 499691247 640 534 316988565 789 615 667197754 126 141 910066083 848 941 814764844 830 834 46723035 107 553 417686470 193 47 381218904 535 113 841837840 302 186 668731927 75 627 667308482 651 627 392913814 687 342 738050717 129 764 837294095 862 376 164965673 918 858 824957779 373 273 857284563 407 39 122344971 807 354 194944798 591 654 608190106 23 629 590655157 5 485 898927825 921 322 951074857 475 246 831701930 259 713 201670466 358 608 351444242 704 168 87641400 482 708 72121817 690 178 719839494 961 140 799207160 746 966 602026756 66 317 725258892 614 360 285888374 988 653 517140297 503 762 109269499 1000 174 423163856 823 126 51945520 51 1 554250432 298 28 715878257 143 291 352386714 122 478 907783833 585 998 541821594 530 315 855179816 217 714 999809326 920 560 668475440 149 296 185789148 751 364 930539892 222 416 571183478 745 954 609523887 368 866 593892021 727 24 795487399 346 927 326619361 327 347 894548618 214 347 313218530 469 668 134228497 375 716 499317358 5 795 265305559 231 30 303327019 545 738 516630307 634 639 529364249 143 616 549987394 632 524 897848951 61 889 301175588 913 545 106915104 311 877 261192850 476 537 853184689 302 218 424782381 368 157 129366088 645 338 467237248 564 18 307487951 217 415 342654597 208 550 789575628 509 934 379859467 836 531 853709403 550 833 864897739 591 197 582634045 880 839 218958161 438 40 698059237 257 200 423521707 403 911 370517214 521 546 655701646 162 739 102890277 442 411 712261829 556 954 541554937 63 716 861941467 68 718 334478174 240 926 456822573 72 778 955356032 650 611 466643809 695 313 300126709 223 535 844386615 235 460 490018407 49 392 199112049 865 316 512060969 703 738 589018910 917 557 359648942 310 460 624619053 154 96 771628091 689 855 685327801 243 3 333411899 539 85 334810615 25 977 461324635 164 314 452473165 82 502 430947965 969 1 760289258 439 101 147989199 58 227 462891770 652 872 690714040 608 365 927559997 198 380 480988894 39 455 148448951 1 134 508557110 262 658 77206885 79 121 723374011 265 384 357978163 370 715 671240191 431 160 241016942 789 558 468451440 608 468 374117130 878 410 994951460 673 429 809553452 464 149 786957194 670 897 668027666 824 964 8466264 801 416 45844430 476 589 615502694 174 986 996095020 187 449 96450917 456 162 569771009 581 703 434850878 17 521 492232821 693 464 133430070 175 19 30602562 552 784 555503051 640 98 531862193 748 797 705748261 840 223 495569538 499 793 780916107 793 252 255245165 669 241 10063152 503 764 376472665 929 135 662883675 994 760 53743050 79 587 538735163 792 123 595141334 293 734 199950275 474 808 335410585 539 895 626922484 116 305 110097685 203 798 136923861 507 773 667695300 187 156 62240898 173 843 109180629 156 872 898456351 101 820 159121737 37 436 986967540 592 333 441395750 486 116 98233974 819 50 363108442 742 447 737630188 824 638 977542521 384 175 930821957 74 899 969041104 401 531 578467522 467 786 206801283 148 336 979642800 663 695 258432302 697 445 110296264 996 233 67941356 622 389 334541010 238 941 349976238 39 297 351655742 798 149 927724033 151 19 176934040 832 371 211467101 577 602 99409185 723 538 677555445 819 355 932351141 571 468 770496236 723 57 638564865 130 768 874706795 138 706 407562602 712 1000 53422787 649 26 290804374 90 755 981033565 356 209 121503909 287 284 773643198 44 877 351766242 503 620 984230709 105 562 857306828 603 6 774397740 684 35 161447436 334 202 856743696 749 220 106380536 440 722 183884343 460 634 861174852 438 662 652909734 822 769 564165667 746 741 597634405 940 430 55007222 838 232 500031165 552 251 283988597 473 755 872803078 285 352 580963470 108 401 691922548 464 557 745005817 526 675 508793911 494 807 354942852 463 659 645549064 301 416 669873453 610 793 79015475 134 182 288745209 383 49 57323813 391 409 818108627 601 710 49356818 975 324 634793421 934 593 693730724 705 548 868364392 484 315 8178574 264 243 732784648 441 514 643086812 639 489 795648703 987 705 870768457 753 354 48031736 857 315 583757716 324 224 174462498 893 661 627560872 262 651 902322428 60 129 862208252 420 607 913799925 603 988 529251746 571 327 978627774 313 130 463162128 718 571 405794614 791 193 771312780 382 675 278865030 409 437 300846698 805 309 201931054 345 469 385767281 857 61 277104654 363 866 528956489 570 654 871158764 268 636 725248919 588 570 317448722 947 616 245105030 499 209 671710021 812 663 168412372 691 664 995198666 310 75 715056513 937 362 300497396 714 50 818896629 340 908 963832809 577 815 916868611 187 601 448399949 76 933 357112326 709 452 127857569 615 538 47913418 21 501 270810109 89 676 567453007 266 248 422789640 376 742 442128298 803 737 501396533 850 889 679684215 672 179 56759876 326 910 401867379 241 794 424992019 229 187 579060292 727 232 412912623 973 335 8838877 989 546 435176556 14 280 86388290 711 306 838081211 468 516 120805917 219 997 151753495 32 718 527490603 808 450 780159267 670 989 114712277 775 764 536522441 136 21 980002196 757 805 666312780 877 188 666209804 422 667 472592987 949 96 571367871 647 56 737738592 771 258 902457338 122 432 682985214 376 92 884991961 63 300 130381885 367 141 392992493 597 55 36929787 647 317 162320598 710 516 482372031 662 886 894803755 811 16 885324386 646 364 460283285 588 893 828424720 462 275 579706980 822 751 168820158 690 293 230260537 934 569 885965176 677 805 445777694 443 302 471348827 65 495 24916956 711 294 924920679 93 827 984919036 104 950 858443195 70 26 885597792 415 234 761032550 465 150 308542817 372 181 86726345 905 296 592965782 865 181 356955052 42 562 335684346 600 561 23888601 51 735 597898563 408 198 744314535 748 422 235528755 317 5 983984451 594 25 480190323 437 307 659886396 605 90 593942326 652 608 235897177 347 34 604003988 736 119 792615821 731 790 831247785 229 99 58077709 16 266 96232349 717 874 510120181 122 885 818180441 910 975 810054587 105 837 686369397 897 219 214491994 560 715 427143299 622 322 817337326 358 845 245818826 512 897 959844237 773 445 812770764 344 885 352226514 253 478 374020618 109 252 495401509 926 551 801151181 293 263 949531238 65 271 599203194 173 123 220151746 136 876 880501528 282 109 498516909 390 716 229883828 321 710 249746965 486 312 559849151 754 140 106022857 533 267 916137011 196 536 15681521 722 115 295022005 255 185 906174147 872 765 844654163 156 995 867797303 912 681 995351633 142 302 947227014 269 839 869639824 558 589 641796875 14 146 790123606 446 941 418093615 943 101 735762691 823 719 523178505 819 120 415413919 773 173 319926669 752 447 776848359 480 575 138213241 110 21 504367791 85 366 104147253 676 60 494479815 636 815 629311752 554 125 503590564 656 903 316115825 207 500 507245380 500 408 332861594 574 10 622006773 636 628 150440933 653 918 873027922 890 715 799286472 102 242 146275976 865 796 325957186 195 407 213937742 682 672 562600723 233 998 630758371 1 667 30181455 977 285 974547816 137 823 614864367 747 370 407802583 725 832 401374587 21 735 26004675 908 408 975932163 232 811 347992228 935 900 902908084 828 860 637789209 985 953 670429738 112 581 810433222 412 182 139979824 935 754 420343237 182 269 974105257 712 314 206689527 829 137 718705684 719 350 643253531 340 801 273532398 522 525 98981901 631 88 711565267 667 911 590023689 682 751 952792913 129 628 490967445 27 209 527886124 77 365 290490454 37 307 699008489 920 288 879084035 688 289 328123824 817 195 683881030 939 238 198998705 110 218 12740624 747 946 666559607 795 468 437211391 116 252 238253624 893 487 483364661 394 221 104754054 272 707 631359773 806 141 964655444 373 915 271117538 477 836 53623826 741 914 929773040 943 254 338914711 172 597 514728333 419 236 593590872 545 398 209207971 427 904 159693806 142 316 113609422 33 106 968697315 849 677 967224968 582 557 86399533 49 43 506946811 513 919 578775375 213 113 36106288 710 752 16138591 924 598 954006284 27 922 354810808 66 548 821892537 917 353 827922640 609 24 100462113 950 68 538709229 981 955 897712037 488 254 356569928 777 443 25213137 393 201 897637263 443 827 249666408 178 931 47264761 939 896 382280461 376 748 98234915 270 422 42860987 188 505 803398249 218 985 757456324 875 682 60180989 695 64 475649865 619 363 550865609 747 737 755046470 146 474 127863714 359 323 721960996 297 525 896936265 197 167 162134240 593 507 186458759 717 617 658166283 657 180 241188066 99 237 77980462 177 22 838380969 98 606 203840327 701 777 487675228 957 751 947826066 837 649 966138240 165 757 180827377 35 632 940368120 115 202 872446470 473 764 459387435 898 774 856729137 667 945 278357228 644 72 474353698 852 946 552475489 375 402 22176939 879 665 160736532 724 390 592046646 282 48 209707293 147 672 351343519 179 699 700905403 3 2 37116884 417 560 272353400 820 209 574669930 662 933 782311708 786 608 342836364 855 851 631846464 639 806 303703615 953 601 735556849 303 240 269212629 495 364 71049976 709 305 717253229 996 31 353531035 534 639 855731135 140 347 882717635 748 849 40390454 856 126 927294229 357 732 305171132 435 488 330044321 210 750 556442651 834 272 134504556 997 512 694226905 784 577 91460313 366 110 501580263 113 920 356151111 579 568 51023302 26 195 837539211 607 438 960091576 810 36 385482209 767 17 228279308 294 365 874108929 306 566 150554425 566 649 573498946 341 52 502829800 999 225 380641475 58 220 418368777 324 772 764766880 990 552 847072635 98 164 776299796 200 37 719336971 286 914 707510690 210 771 44440002 499 741 978569925 526 642 528230809 203 175 417695783 815 940 191797377 157 931 905323296 38 54 383703590 361 176 978525965 7 96 754846517 456 12 587785753 176 435 580087499 314 886 691500447 935 600 994076970 542 922 471954689 338 441 715056015 767 134 171429648 603 236 954145718 689 476 845010254 737 940 291355103 19 43 932401242 61 304 441712129 37 840 730436387 371 330 506374514 827 934 514422064 110 729 233663027 307 160 15067684 907 374 846262874 342 233 293675747 599 174 297506292 952 973 860414359 667 522 897563681 794 907 304104391 244 297 445103672 62 270 63269662 823 15 305109489 380 754 747942310 16 8 972979456 750 382 22672702 894 35 240999148 771 17 96863712 543 316 17166515 177 478 915498606 151 436 820894386 348 156 958750857 692 223 128112491 644 388 522555206 79 117 632598409 653 407 642279863 786 538 385074830 846 843 75399519 924 672 930898236 638 637 809495309 988 187 328623458 96 726 705874895 415 835 608331119 345 215 558339424 712 642 475305536 793 532 929015289 920 310 193965867 472 414 946251239 600 405 850261323 806 335 238917453 803 670 76433530 543 81 942826224 95 32 41465229 112 327 895127867 859 179 695358004 209 95 988638049 732 780 122258291 173 225 288033091 431 363 940776751 27 501 750115566 829 228 4315646 874 695 514303879 346 274 286982790 277 206 556392086 61 936 708718207 30 799 326754689 704 490 523093651 656 460 772291212 741 827 932624427 25 329 184111643 561 501 574627199 132 549 379326177 152 437 47180845 246 281 394958312 531 59 587512864 115 221 719859415 936 65 447413033 306 575 100097158 945 240 58583919 71 82 987438902 171 918 912054783 242 562 74360930 805 35 255076223 169 855 431821071 247 998 247649534 557 721 871832940 918 275 284709624 410 742 35060868 771 770 531180314 77 850 834370072 383 377 569295871 676 802 295261773 56 370 934717384 551 764 705811920 620 846 230070537 154 33 465103891 664 859 365714583 779 884 703899078 938 723 122996780 730 201 231118954 290 607 637755110 719 708 696323442 415 546 490495256 970 507 385775606 621 864 586319014 134 983 105524277 780 893 731541648 679 25 796249840 668 309 919985159 70 157 208168394 316 533 128841813 49 381 801868492 162 681 62577929 783 946 527648348 863 458 940318020 982 183 527006805 566 860 299606359 139 560 277256604 69 502 670734370 739 368 849590656 882 116 246342679 765 770 373788424 974 541 557997994 439 703 707464334 468 246 46811505 490 256 874527014 643 514 465118259 385 242 260013440 390 253 464364788 291 734 148631567 33 996 994364822 547 236 688372718 822 126 950082846 937 207 847699495 604 99 358395364 468 402 568049834 263 966 75609643 661 535 616518870 441 169 687202544 98 162 552069379 814 786 458397310 383 567 507081231 928 305 887119636 814 56 382339984 276 844 467726543 832 191 695953199 544 455 371993234 450 807 823007293 359 982 78104909 866 94 893105437 426 477 84829575 496 941 7333835 345 988 228615429 178 974 530017040 967 203 254534471 915 916 660816133 356 762 179362439 722 219 108117761 287 224 297019901 235 19 807656980 304 661 807621856 461 842 718151338 88 901 507185720 949 149 618070516 334 107 793921991 50 282 971409071 802 156 210869198 130 37 290522215 92 965 697404525 128 14 688302257 443 810 385510030 336 299 455356494 254 139 715232279 766 157 936819181 358 738 114816695 676 962 232425454 835 420 599895156 605 943 881470916 59 182 302102261 687 169 900672689 784 317 179928141 532 854 219616415 894 163 130333609 475 610 386274797 222 949 302580122 332 877 585579396 849 553 586710993 377 402 149437182 302 120 734226468 682 99 306477060 546 177 26420060 22 241 110606301 197 703 529121687 280 219 613470417 718 819 2810394 735 63 353837783 704 430 494311559 563 289 439660152 190 278 18212943 222 352 706330350 883 139 861088914 681 529 3085924 735 551 358753705 882 360 230235157 123 494 471986963 18 20 981969788 39 752 399022109 682 402 431066774 37 122 131026057 870 293 667106640 734 296 253799182 798 636 443063725 759 542 52572454 183 974 211219273 156 866 404234390 556 551 929102531 427 410 402863351 578 809 179726390 922 280 727915285 676 424 380419929 102 319 385925474 747 690 527350377 947 234 218894028 991 564 606628935 275 833 156547188 733 565 961627058 371 525 984786057 255 116 860323063 696 215 160149011 871 921 859335900 131 702 214486486 509 578 168708523 880 804 539571754 78 216 825375130 851 318 251737756 894 538 928826521 596 473 672788461 76 467 886202235 224 924 34204238 642 634 225249171 645 338 298872934 839 943 47732059 302 790 777787935 493 962 336420171 235 387 312781518 387 221 480323833 501 645 500439721 591 257 310163830 641 639 639030193 510 282 24282332 633 141 619176398 563 341 533749335 815 242 876774853 739 89 287622796 723 324 774658804 227 394 649980849 823 946 993457101 483 747 741417243 680 800 131501848 764 460 569553960 610 496 479000185 478 608 154083202 415 267 466195940 561 702 885860469 607 161 292756338 590 366 819328498 925 820 173266132 717 766 928080067 253 973 62177201 968 822 377925728 760 149 113444493 371 103 455694241 203 828 229583873 89 623 407143386 214 823 228067553 904 372 430189418 850 561 122508736 141 464 292362738 781 146 253684385 856 364 393460251 473 394 288779212 140 795 741728462 368 547 559683927 806 134 196758588 176 108 487735549 164 854 56425912 631 19 410911979 909 202 679122789 176 962 823577072 296 429 491149680 746 225 737676303 224 981 255977709 999 15 971436554 679 787 523909557 252 863 140024266 866 981 656441365 248 607 482136438 903 211 758332119 87 953 740742055 964 279 587272157 676 230 853082262 635 3 756706802 651 422 953693936 81 622 487479788 486 293 319242432 740 74 925451145 264 950 53029120 414 292 264690281 407 243 569414500 590 764 746286172 729 351 983063800 583 717 634176233 944 733 307396766 948 373 208374205 12 914 627355873 768 27 270630029 663 373 41307159 612 100 564453873 486 748 357776152 38 181 30445279 177 273 374099945 173 571 213095028 45 370 669583403 129 200 378838130 328 3 79909434 767 954 893454179 873 638 710764620 248 58 646309285 355 736 914066035 641 274 542805510 520 652 79473194 247 692 117581492 118 208 30525738 704 319 902629555 710 652 445440693 56 126 558601466 862 762 307986664 9 713 858345055 26 202 383659299 910 891 455854758 338 604 796923445 209 803 941404317 31 610 352112332 572 476 848638994 493 577 690108191 382 513 373319867 534 277 261961055 802 665 123701452 226 510 97433447 524 158 6784416 154 946 157829666 79 778 992249017 594 922 691397346 676 143 581536170 816 395 828261912 342 533 104547403 987 246 970205580 893 434 958520747 92 648 148590550 434 870 478255653 145 52 250753015 576 634 547524492 207 745 616529227 981 960 92357436 60 842 858507719 411 465 184074826 514 988 711200568 325 821 620439410 423 920 858265146 558 179 772995294 852 667 376225568 205 226 99291822 709 931 929821466 110 395 205005062 557 758 84665198 474 619 777104323 125 455 853735108 652 91 460038584 176 370 251766145 675 871 428387416 792 717 392877963 866 97 19226806 719 8 646941019 100 88 522128776 891 976 155945246 932 888 710566102 1 913 719881408 817 295 763627486 624 266 455147206 773 302 993130768 623 304 768677003 210 824 919158997 511 57 969183100 759 291 101073687 575 157 990620785 280 550 436222364 998 273 63253271 556 907 477781366 384 662 167796043 703 647 109591503 838 420 668419280 846 282 517432150 254 696 102841782 928 805 68773596 658 630 576307604 378 305 59159917 904 647 295336571 92 622 102594655 734 237 740050833 635 215 206013192 172 989 955657277 256 659 411764576 984 28 553660178 753 351 404407566 83 710 375502268 812 344 108968433 417 574 140911486 918 118 5432934 180 124 957684634 189 451 467594337 663 484 845960974 159 867 704875168 418 306 420619874 155 831 93553558 590 695 874258934 179 534 264000249 843 567 431559344 214 173 859356388 387 575 983412936 981 778 871973268 617 766 14719537 735 346 320487192 946 171 325062099 346 47 669714722 251 470 179326021 611 65 52394242 873 522 291374129 438 162 211757328 505 71 438988408 637 436 94527996 178 171 992404471 913 126 369956529 90 557 744924641 512 253 688999772 252 306 516074881 969 385 62354217 949 494 400897915 380 804 68152788 647 233 857304306 388 742 631590040 703 449 895423792 406 323 899375796 36 91 73457681 202 453 333175292 85 308 889214386 267 131 745842718 209 382 730596246 317 62 216617657 738 796 235615413 327 713 742657840 633 144 478328457 269 295 527538586 637 687 113569677 398 655 216601056 369 327 115910795 143 951 209404172 239 274 955351997 837 329 189728405 760 706 97506545 473 138 681552146 597 86 623700047 305 109 374608420 68 27 592939216 217 970 274002428 936 65 739756044 420 434 356765028 914 215 983176931 991 864 665827869 788 36 476481500 754 307 797636634 497 628 856201427 430 865 66793114 851 475 820485814 687 73 265505662 126 798 680188349 632 708 777899889 931 150 87843732 113 245 857115341 760 54 118042760 496 752 525359125 404 84 868397637 922 129 674382666 591 235 326179343 213 996 441426660 681 263 472609462 666 362 632799132 440 224 117505319 755 581 861783274 907 998 720348769 315 756 554288257 727 292 641190664 763 563 532469885 801 379 396894193 625 280 52656252 810 594 880080904 925 471 236994306 993 704 327369700 878 87 858010210 124 988 390704779 435 964 106655719 122 69 832760598 72 862 106405568 191 675 645109663 223 780 331957438 480 777 764527991 120 663 21649145 968 778 769655430 900 903 212792558 58 773 111243309 942 266 30367503 823 836 344045155 556 198 988890633 571 193 294957769 923 991 360833794 830 71 616140634 129 595 351204390 593 194 794424200 829 89 16491186 939 114 116833480 420 231 383328154 238 411 519015195 270 656 11981365 70 217 689646352 245 709 997276767 656 425 238583479 511 153 211493973 289 737 833169882 167 111 968621307 484 808 236125089 403 16 820733457 410 888 772523895 876 55 429526087 711 660 159294324 613 707 3022565 924 149 168989648 951 426 795052917 265 481 762993464 896 967 370841680 991 515 579869170 20 701 234100390 37 938 126203354 811 514 608829568 343 592 163882614 48 599 992754287 764 648 425408724 581 957 954294641 995 517 152260840 625 921 758700108 343 129 350105976 533 854 284468842 800 586 689142307 605 859 411868881 686 684 55394106 107 641 526975417 452 989 697110701 675 310 681581578 496 801 506725411 270 602 626830567 843 561 98491225 145 856 255547845 632 972 810750994 337 165 174500835 40 716 855894155 254 784 681269456 389 573 45029320 425 793 787939639 770 439 731579295 765 898 619459337 586 86 437780563 773 781 198435760 891 445 431499356 680 186 602099207 980 346 27298288 302 155 811584414 287 556 833196596 236 388 912855844 182 844 34896065 298 579 930490213 86 568 325255812 141 31 987268907 975 300 484186068 203 44 719716921 836 890 576110525 38 835 577542805 341 600 465423078 233 754 820049378 719 113 675307215 976 403 978573921 710 798 273002357 755 678 651551224 113 733 69797462 984 500 923097305 335 869 442317179 211 1 276335304 875 225 31257190 381 865 153829749 348 197 95502372 575 431 949170669 834 337 241104070 780 177 361236099 893 750 292966342 759 42 305081806 444 712 822059363 223 770 107185549 274 254 440255787 580 697 990235230 815 89 195773732 823 619 392021445 800 322 98263318 261 388 246719803 104 355 326168068 823 920 643562697 359 136 829534415 202 369 977464083 669 770 404830013 780 136 235991821 600 767 459709928 89 640 603526694 665 244 903094394 365 921 157863828 571 898 35159427 530 285 187380960 26 360 748212053 582 49 352086287 532 495 291828669 705 257 613975417 77 103 479965091 818 283 872631811 304 759 562849881 912 53 424668664 313 972 672116938 851 310 90468790 848 450 712363271 333 824 173574647 609 486 735180830 513 900 299774207 937 231 783028584 471 696 211937943 602 976 731390 929 505 644310071 542 428 856546503 409 316 586629712 663 85 37635724 405 898 806709195 441 702 550222459 82 527 845489239 745 280 968771971 237 894 936215853 907 179 476964954 611 564 852008979 242 44 629638012 569 839 544299213 387 268 537924340 862 330 670675336 505 124 142742634 220 75 446568270 339 990 877933054 506 321 178865432 226 262 252144532 733 342 472877960 455 397 374960095 974 888 265932406 364 711 310987117 47 817 433032613 188 31 822582491 375 903 520691123 834 675 715121090 72 327 180007972 776 540 922480163 642 934 532651005 824 923 101724114 203 798 484112143 843 965 883964060 222 47 645832432 542 255 136032495 827 735 181404250 731 85 225144234 328 768 337284652 842 555 959238549 594 904 556375188 872 836 29982673 186 636 909766463 892 364 801548658 529 680 310051109 556 333 371446692 250 913 570496558 907 516 708479251 144 996 197018798 629 230 914136864 749 327 129907008 687 148 502638952 635 748 939964957 71 934 222975611 123 584 938948793 951 81 944355304 985 967 997579665 20 161 104457587 175 575 394623006 146 616 533442444 918 729 288731229 791 345 486932400 483 642 205263504 257 442 709460042 32 673 215865419 892 3 127069469 851 110 717361219 523 227 193330840 647 270 539091001 490 259 758920220 373 311 469478951 601 586 655933436 578 205 178781937 917 453 204150434 864 26 747856212 814 917 304900988 115 883 876590502 532 283 791927839 124 177 632472678 874 856 286595510 533 75 558265669 813 281 449619670 794 129 773478347 217 725 901033303 688 676 316744891 54 441 903123919 999 886 198190169 973 161 59548884 705 871 760139776 242 403 926623517 649 724 292847413 568 582 584223470 394 917 214192302 207 731 532864814 754 226 961594008 173 912 948020588 315 147 98819803 125 16 330309050 342 829 841914736 584 342 593421873 675 741 58539726 828 894 874690953 15 239 802771075 635 836 665701936 680 775 697596560 339 820 559212132 876 161 592988896 478 128 702830524 975 533 962128510 456 982 34667847 222 734 996898701 44 47 4794883 699 150 596150782 134 874 501170726 617 341 597631127 613 471 658314440 428 36 625368822 737 786 7661721 148 104 941784901 398 176 276980467 66 43 949843208 10 32 902946779 646 155 769256824 315 515 272234294 723 643 601608507 542 419 396161357 54 290 632112160 989 760 564850164 773 590 708733916 539 581 791111982 34 383 285189832 100 700 832153244 477 276 742666333 800 37 794105671 426 476 271742115 362 459 76080521 512 484 192836625 726 200 334538786 747 129 239509870 414 291 54070612 578 723 981650748 14 412 588559938 805 272 792448057 203 719 242692495 798 180 912752102 444 622 436166633 126 779 926837698 405 36 90021593 520 112 913217767 908 801 995765218 265 425 968767781 366 817 327665870 200 904 958034889 653 222 396224790 144 479 556000258 37 80 906678144 677 403 582627217 952 382 721748164 985 930 779396443 796 411 886101482 653 492 544494518 728 882 460892821 911 947 158538622 970 128 271655548 669 928 447554353 787 576 522669813 23 978 424136841 999 991 12275185 654 433 475131721 121 382 640285819 528 372 818908534 545 671 938988207 433 406 903384832 17 706 976179357 170 799 579221854 373 540 397684286 882 101 525111277 992 2 84551469 255 329 53150695 225 802 611181315 388 10 296767480 355 1000 834734640 838 364 645088846 472 751 201020613 623 967 616995051 17 426 406223843 371 343 567989263 889 234 507628522 12 532 753139561 29 578 72263814 626 101 373742163 818 419 28597340 417 739 165448929 298 627 888314575 966 225 127035269 438 361 117311852 559 398 703283013 668 432 805284324 195 272 751099960 721 755 736318310 927 913 388640502 213 372 343903984 567 352 72374937 526 870 270137262 65 698 143898803 257 272 374308185 618 663 24639370 572 48 706098089 951 236 478781583 906 442 953084765 586 453 258532900 798 662 825987356 97 814 837629835 83 322 884203892 699 177 963861205 557 257 435878438 981 892 673661439 771 599 915602367 261 505 473736616 807 186 639471081 842 891 513283072 639 430 853053764 716 563 728640645 785 969 477576272 1000 450 248853520 819 255 113087628 271 867 538428801 738 588 10513466 624 639 495920389 334 819 415134941 914 97 179215585 242 267 86909716 284 683 932768354 491 655 818140013 220 416 896098714 692 599 605460237 846 91 606892541 770 970 897385807 965 903 404195986 590 670 734796457 949 457 669604436 994 374 169375334 880 1 949976882 979 812 860095229 537 685 331947595 387 37 730323130 406 774 997592128 84 395 637744981 252 55 119246766 694 29 142577967 945 283 665764327 504 463 859571548 463 327 59489570 946 159 416820573 1 634 845367253 721 930 277413170 661 122 414567741 275 79 53794379 276 90 713068198 407 463 634976430 103 291 524764918 614 117 32802 292 103 592397301 568 661 816826732 704 787 689925550 7 193 501417662 319 758 809792478 5 311 186290867 673 605 450150767 476 424 529343360 130 594 492331496 424 960 437909081 49 694 66335528 318 229 490640315 596 434 816272801 768 81 982741003 624 848 352709645 437 266 141389692 621 629 843846003 335 132 524685337 951 139 272465847 554 33 371727045 768 22 732453943 100 203 703663749 250 85 198499623 626 183 12359282 297 440 396572765 837 155 654502276 595 662 864830722 2 40 884552048 46 145 29241276 111 359 515659207 151 61 627298922 883 262 828078683 889 704 965430385 420 83 90693848 724 715 178426364 167 507 308265080 615 859 289834649 415 625 176488762 278 654 226759976 542 141 814371412 220 465 992675534 377 254 188537060 629 376 524609330 547 250 495218652 355 211 869492684 391 233 425888562 602 571 454881444 783 530 274467410 802 331 49748717 319 127 90182318 337 636 226469267 860 475 489840854 707 542 206702103 761 675 888470412 541 268 179672888 952 623 537431480 991 685 499074642 895 450 603620456 424 629 980798949 787 249 307071337 892 58 45070759 39 766 227096611 861 158 214965883 196 743 613825548 351 826 130986414 74 510 797760124 474 863 240447717 504 558 267696921 152 350 111067461 321 38 733158115 979 102 635951503 48 957 926968606 979 375 531762270 973 766 329213590 558 980 662482822 567 510 851061370 821 312 302546323 728 216 36342660 673 43 624537896 823 348 606700812 481 448 96040784 438 779 499922164 33 112 512729066 218 723 542515491 601 77 313441398 979 924 887690097 423 15 973558128 419 46 319127937 441 879 328784207 331 829 477749518 597 496 685035165 527 494 751288591 737 130 826654128 916 947 758568189 548 441 481044249 9 754 556055667 728 755 352127275 584 454 188320896 921 277 579771584 53 3 907328235 493 438 667103713 899 916 759284860 373 897 212755151 50 515 372959560 492 807 473038238 832 95 2493172 864 907 58215923 137 624 750989127 344 449 226845919 506 355 986804230 444 875 50152136 808 590 669942281 720 134 38454793 699 307 130913537 446 409 843525636 105 339 198611514 4 123 95741224 690 554 879332252 8 67 478893756 230 309 71111429 254 673 621827995 193 721 437791203 130 521 138636000 543 471 714731576 292 877 755147526 284 971 724153827 662 714 554992457 859 382 922454390 672 683 642231950 659 468 228472241 192 61 53507263 881 350 580613789 738 931 837598326 579 396 380753927 848 549 742276326 457 231 485858789 392 77 465503768 1000 920 451979904 672 547 860400397 193 605 6399005 245 401 387249092 428 412 738550664 768 294 833285260 568 17 292757227 116 378 368632457 187 879 226162490 341 290 816555087 904 544 710339237 771 802 778741083 27 309 871651418 249 815 51253902 762 675 914403438 536 910 934629606 94 530 989639573 68 876 640706686 207 404 698561101 274 356 557985034 515 406 410686706 230 767 868156158 493 76 486349464 797 192 288452837 206 184 146884499 636 153 936105028 279 928 938724983 589 420 549728890 385 574 66492588 501 551 246869725 812 788 978966583 275 184 168639224 974 847 958466982 63 748 953967053 385 500 331148266 508 31 205378525 415 885 98488178 555 289 178994625 490 396 207343269 933 748 973395968 304 99 388437892 230 726 284061924 91 678 398237156 282 580 157445058 272 755 358996271 358 398 886477922 63 389 433957798 530 609 864084908 483 391 181498548 274 112 492350076 374 316 378395115 824 500 198568275 725 217 402049227 163 793 323298995 903 640 562603586 628 485 788739489 95 262 995297385 316 907 24221471 908 606 667392091 247 985 220927371 700 5 541015226 117 356 457650849 304 182 6557682 839 112 649506440 275 968 342813170 862 543 797323107 6 483 16936280 838 871 62388469 766 451 372289436 457 545 539254661 346 295 759910967 741 580 3170766 130 934 413361691 192 925 382848622 468 862 284188998 715 665 676063895 943 601 740981737 101 724 768815193 946 540 244020101 825 741 28935118 114 636 201850330 236 854 759881597 28 318 740278302 142 873 528054954 379 203 994022443 91 502 641935654 468 6 188335207 557 361 92849840 288 325 263233166 689 439 350448827 371 239 949614272 970 766 83936207 980 782 138785339 12 507 498136712 705 955 66515280 775 332 473851671 555 412 865996185 274 764 320540440 539 70 485980921 52 441 884643680 226 593 253581917 323 762 758667466 702 671 951792517 286 409 285697382 563 370 436833559 840 341 49287792 63 44 8303997 985 308 389587603 437 814 35560408 468 289 729836955 598 331 121315311 197 15 179394401 465 396 914975322 627 50 44093593 874 375 134862802 282 430 415824071 871 450 709619883 885 445 152259886 810 791 750195748 614 376 320210772 965 243 32724733 664 606 96218943 730 180 192308404 67 392 293447495 604 392 611906440 825 969 657016751 644 932 229258527 498 490 628610146 820 767 811926675 540 711 587489596 686 538 702967575 60 869 63032020 22 182 321274828 236 241 644305036 782 461 740230746 32 832 712801443 370 77 826176844 381 771 106186123 731 317 963508912 545 231 299688006 162 720 205550441 937 774 134629507 415 642 953645944 952 638 705592149 348 562 485342151 983 513 941202885 583 579 626234478 245 289 693774276 173 757 409897774 63 743 426482521 354 688 730291543 87 938 788523164 596 934 450491173 567 252 494897761 540 204 531826994 731 754 999274630 568 455 249982984 344 843 442453775 458 110 879191965 817 20 229231208 695 860 840136383 666 67 60089838 97 223 954395785 374 733 45886518 968 162 224453110 15 709 77201140 136 424 938868849 349 253 73057343 895 259 160690563 779 865 309558748 990 333 237662721 623 218 994446623 36 532 699155731 180 154 493607682 755 699 247852544 501 660 10797041 445 206 542615494 278 61 171138382 115 555 703294041 411 335 910892901 35 63 669366454 432 4 658324255 858 86 782797410 198 880 547979275 266 952 891204117 844 315 507798013 431 633 985605452 102 165 617598511 519 586 418296872 411 884 261409729 191 45 34367592 465 378 86988784 666 785 16479799 604 976 239224711 460 748 707975698 783 855 666547851 339 133 182772303 410 44 577232668 72 99 860810015 702 648 961379195 588 436 525973827 220 707 183692086 882 951 514158501 328 439 449499723 707 422 15794595 606 437 222474868 886 50 252873128 115 756 239298479 4 523 462014000 646 771 187320950 790 516 693093676 93 710 701277849 105 249 395355032 989 866 686315051 328 383 534759039 753 903 242487634 849 633 96784142 867 715 378385589 528 310 612011423 634 552 100809743 267 993 214962259 844 327 920269331 883 538 562662979 467 528 897624087 54 108 415010003 502 79 170269038 727 563 600174253 367 512 907139665 900 981 811253197 614 779 52628817 258 447 378868700 614 686 921483139 147 279 353774947 108 837 151251757 419 815 854155833 590 898 933237391 469 941 50824633 563 151 550326405 107 153 913484879 831 940 405172594 287 96 156317565 255 201 301364095 692 586 587519808 750 335 416034706 299 408 682822649 794 561 964429379 127 290 890109643 485 904 150326045 821 653 252130324 305 243 688536299 359 443 52576312 291 102 608083276 631 191 909423374 702 735 134624954 744 262 483732999 109 452 628257566 654 28 923073332 770 636 415501739 531 90 293421406 179 856 964190935 521 520 488538431 458 376 943118522 526 955 343174402 878 78 940705852 168 961 320520881 535 704 959440249 109 623 671702379 588 366 202874010 130 858 358560113 100 689 787862891 30 962 452306215 735 689 744075975 368 486 638471181 277 918 797215483 462 437 203181510 708 945 734727977 220 397 359957643 400 966 412770313 29 124 686401682 452 284 761412380 668 379 163883174 352 162 295725342 560 977 850850121 981 839 937668577 866 10 181479204 788 635 201482852 243 309 144042797 573 294 25829972 756 849 459042524 243 922 114725429 30 109 761822580 706 203 348360527 92 643 69332933 605 661 969333498 597 136 767316151 889 106 370697883 270 268 891103270 831 714 994675140 719 954 722985142 523 968 848823075 839 888 297589954 787 489 123215288 941 550 226826754 687 969 901595119 954 766 603527453 938 380 844688511 658 310 977223651 183 66 862813384 587 584 599520012 572 7 967686687 731 237 949992744 769 690 2843183 186 488 472514410 241 936 964212827 550 136 50147170 725 934 531928065 256 254 5195177 746 254 614738654 609 842 85151298 801 59 923950273 906 847 68005150 752 612 25950133 69 714 196651747 779 17 792323961 394 515 593631815 107 135 999289789 786 424 964450606 550 123 248270022 684 813 8183343 409 30 49119287 86 962 939675842 982 867 646238422 818 427 996077719 400 870 494087684 424 535 371616172 41 549 92315493 155 491 738556728 479 702 631000531 299 710 706211662 808 763 464282951 148 765 379610705 183 870 168712166 254 234 748644865 315 566 203500726 690 599 781173054 741 234 980523573 401 224 556383226 192 418 749957527 751 524 770115467 184 389 637862910 521 23 91911463 457 345 49871088 243 291 426499547 594 356 970167062 950 282 693713827 674 190 475277382 509 243 301699487 777 20 190668784 16 535 653045791 220 155 169852259 907 89 909487798 667 859 113184717 264 662 674136089 228 620 383005497 66 523 981510369 190 79 368247860 606 920 765148116 534 461 980434491 820 26 495956989 756 559 151643823 485 14 184916966 503 361 94385204 773 333 478314071 621 945 254514354 312 81 746541102 400 603 611335206 28 135 136767864 364 691 593966981 60 48 482872101 745 932 404739639 793 238 188775900 105 278 334692491 863 504 566394996 980 15 567598284 452 806 586320476 161 371 908325545 392 796 893526960 330 433 749592501 332 887 908802060 76 345 285593562 777 388 635460673 511 105 399392171 220 483 210755421 458 810 855950862 695 610 43340746 580 780 571935506 686 400 53172995 350 362 277027237 203 228 3246853 679 591 249998982 565 293 977118240 606 358 850525072 803 913 82726490 164 430 506489513 535 803 672945173 101 864 634851374 307 643 935011816 76 299 815097770 43 274 397981175 445 683 783640053 133 560 869630031 152 485 978910428 339 781 280428526 652 846 641059057 827 220 689002093 298 941 539805290 529 682 516343259 89 601 61089538 315 665 512986419 976 716 917147875 342 41 226335276 522 635 575942545 373 226 153084239 387 819 428976892 130 61 142118366 185 889 187155128 322 226 216174804 77 459 237712131 126 302 42121846 424 152 109304300 524 371 534003136 427 787 549369960 897 111 620596984 402 191 504301670 110 646 45612273 130 538 68236223 76 412 526024924 1 706 628467870 476 137 646042005 748 570 6911075 430 691 349011771 692 467 398683611 963 290 835013874 950 370 879176365 283 125 548652753 352 273 870773497 630 243 602898516 573 69 304846312 781 413 670421308 941 558 182636944 73 663 812751858 24 604 75465906 868 528 370791461 789 705 221175335 342 825 222673948 487 256 635629893 268 822 108619314 621 504 323620037 363 472 812177870 299 956 687617219 236 373 477375077 250 694 306175771 887 955 118205623 197 877 726713509 935 219 383251701 513 330 126471192 905 546 772080922 771 753 175166910 120 995 689830723 1 612 753345121 355 674 616997254 450 267 917229069 267 269 838753336 687 699 960032565 321 795 529160913 951 760 269074321 662 821 828703011 541 979 853622960 432 199 294365637 675 864 241519693 244 251 858550752 78 516 552008433 887 973 561183565 268 316 187102853 317 467 515001847 774 296 832218941 439 684 717875457 846 803 363048286 330 488 403953039 300 494 748907310 497 236 693594965 313 675 69025478 602 126 964942114 192 538 823866374 738 252 436382604 346 121 842874296 780 212 175006888 756 458 781671179 471 930 218009765 671 241 480958173 996 978 752556642 70 253 15463879 596 386 855953868 336 943 739369475 238 893 146231700 590 672 612298273 255 678 985505818 380 678 178449924 948 358 936157438 927 429 463594629 318 478 553376564 32 140 467566525 241 39 528255611 347 883 277820588 507 826 171336041 4 373 878712069 138 264 547930966 724 362 464530269 554 656 879226000 448 479 36354192 384 281 663640177 641 10 989064963 679 565 600673372 10 532 910076892 291 950 329005578 415 911 540684699 303 623 970352507 622 528 244965915 357 162 423977139 441 589 894432114 237 683 838098528 536 715 634410153 672 52 71328502 645 485 941268462 389 39 772384028 823 481 438537916 450 701 199234621 633 28 332051026 49 65 912449018 676 10 566337065 521 748 166948800 942 997 394501610 93 100 407231175 674 491 694131086 811 560 694087127 647 611 649945316 500 379 345788087 580 883 7701330 757 473 870419367 501 399 124519216 973 715 510313890 455 77 971029747 845 638 555696527 544 132 642509770 609 882 733649464 45 524 277655432 66 387 7324291 195 844 106200061 478 203 850669198 758 872 118554047 123 860 486626972 653 456 116455334 22 503 480725319 130 173 438854538 83 783 421146694 503 43 892831125 28 244 295075577 43 515 388675900 655 977 819660880 147 942 381510139 849 583 657884484 664 568 894557746 692 261 224468946 794 947 850734939 171 589 426558810 180 554 461373058 271 145 779904591 442 101 141809844 917 81 668695825 102 860 171793442 133 923 222106897 437 476 790820916 826 13 495601816 419 511 370473400 329 678 362702831 118 317 408151460 568 623 910763856 65 755 914373946 822 562 992801790 670 33 154666664 496 744 284515810 35 350 273593258 203 472 986524333 53 507 383055393 484 550 240214714 185 663 631669866 169 25 265210004 999 63 850576776 939 556 116799837 603 74 587104846 326 985 559181462 477 849 606087215 407 744 625110175 892 225 931117268 115 711 668423267 44 344 45958961 848 657 929701121 884 801 69269882 184 740 596952664 735 135 402432523 278 374 953457480 370 903 38976168 603 914 685373920 387 261 885606037 774 870 823478279 640 102 598352405 813 755 693917563 75 796 45592103 561 623 404134156 780 399 551319147 436 29 917116833 797 970 160652891 733 584 910205553 672 857 335559733 353 460 378184547 323 235 859030749 761 100 260912155 139 294 917685029 546 477 4252868 757 663 277515668 712 213 76091191 961 435 460436952 549 676 426537189 566 80 944173895 640 844 100295698 743 964 670563771 532 521 417262627 335 184 84117240 416 92 756836543 521 26 7595249 928 679 595685221 324 701 695367732 546 101 290527652 250 497 963283643 646 47 727525985 196 250 13251905 61 510 419810625 970 643 616076507 478 967 238193616 985 186 946206106 750 63 741165945 546 255 597943595 168 786 826335268 427 612 222125378 413 951 497334836 737 648 657596539 489 812 81947155 642 82 162139128 392 924 204908255 948 833 769359898 332 461 542364176 599 621 408576913 713 80 106810434 487 91 579857293 985 438 61993754 56 102 254310626 850 299 216885553 446 548 326057336 1 354 802779663 252 394 428170171 545 437 106191692 340 819 567194970 825 697 333120759 562 724 422769382 465 414 149327719 281 50 558359306 953 314 709440161 981 202 344323945 122 847 158258108 630 183 764175073 385 476 32384614 334 947 372154559 494 542 900888348 722 441 390710402 48 863 696861026 181 649 268186819 840 47 231024214 722 661 766513773 986 536 725298634 288 824 342807762 13 961 880972052 450 460 753432645 307 38 166962009 720 723 726791579 190 867 257589174 965 27 833251932 565 925 117540246 436 934 258635018 662 600 555854737 265 647 357058217 358 859 936811049 462 945 910028326 266 537 694475675 164 796 64658664 348 13 290062486 959 263 667763696 793 696 887786210 427 576 699243313 633 911 667321900 660 208 889885288 470 220 925200017 695 428 550339799 24 425 960086051 448 123 797917364 790 744 883364544 28 303 823609706 319 286 608053734 468 785 790964461 653 923 389092176 706 164 424868630 848 791 347253038 889 73 466018382 423 870 173351839 564 732 60475755 953 512 698733836 902 616 267157485 148 534 684249144 856 970 508394377 965 572 901146581 503 657 371268786 566 259 554885065 218 318 378019522 832 21 732058345 960 216 922058354 491 625 20312015 1000 756 191466003 594 508 653842466 804 864 266874200 628 551 633364292 455 712 790089368 216 726 481776153 562 326 647673149 990 425 723486435 199 665 645163810 6 826 520412469 539 665 842623201 227 218 690546401 471 103 490415902 342 103 447578302 692 200 849117922 201 478 260290447 863 541 648852674 704 132 278471022 141 738 380218459 34 796 928557790 207 398 773915812 215 559 65596440 782 995 62231606 77 315 300182311 39 818 979211068 72 87 700271059 508 926 774462472 99 484 265296941 381 102 230528058 426 557 159516463 338 224 964344206 493 850 902286619 321 924 557014851 714 521 302702169 862 468 447404354 507 88 613807011 433 491 426011167 763 724 499929694 131 370 270286291 785 301 330620653 964 614 543410572 254 489 287415785 424 534 14266951 520 298 925651818 43 508 970537485 572 346 27039295 160 35 861431273 600 169 105236275 467 182 712454436 277 871 93533299 762 406 253118468 466 756 776871795 371 240 566961302 895 622 299757738 328 87 568745135 440 138 543686242 918 25 301647545 373 251 191460333 882 897 125078999 476 85 630742722 70 54 767566766 16 257 374592888 148 168 60615206 229 444 179983758 332 699 108514916 967 745 185969447 48 562 274058486 831 169 3124205 803 507 490732659 161 668 823490800 565 395 687325066 927 172 206204087 635 927 429453606 820 942 398374307 666 537 179695200 887 782 143974686 748 454 587796491 260 44 666173771 271 447 977157531 778 991 829461368 278 564 834560365 737 186 396775570 138 869 900011471 737 385 507060646 9 609 82903006 12 839 653132670 189 448 731915126 45 986 676955346 947 463 189122042 297 337 96645012 327 631 717057354 525 800 365663476 127 834 980188765 291 390 125250944 117 120 505483445 166 12 822622507 693 983 433738991 897 21 192801893 718 468 931901920 804 297 465071101 140 948 115403253 639 441 213864782 355 171 484944333 209 56 210046708 979 327 144486552 689 736 632719840 642 659 683587659 369 283 489258063 950 301 431053277 3 398 727919704 429 717 7589033 104 442 630372603 449 822 243214933 58 104 759441883 446 156 923345722 465 953 501779039 654 307 769143916 228 870 494799788 145 133 649899086 677 221 888680524 99 667 982548105 71 645 124903861 973 752 288791960 665 237 483672209 869 68 754528229 423 604 513190552 365 377 719071830 566 907 284225640 297 381 963851508 959 198 962419985 38 184 932463678 424 163 374652299 441 92 252057282 317 676 329529730 88 851 253965151 510 196 272334187 381 609 622085485 34 348 213387050 152 951 190444565 2 777 683087671 265 713 420587390 890 939 695432320 366 21 805819807 585 222 987831030 956 600 233454313 873 298 104103573 588 509 653720505 497 968 225795140 925 704 759677741 12 949 655835706 922 657 923512348 704 44 843006611 550 43 147354961 715 402 694156006 237 239 332044382 295 810 398734543 980 123 5810578 140 309 491597683 473 489 563683596 895 677 750056569 195 637 195450491 374 272 138394242 432 663 690530872 838 755 864735148 865 33 401681752 920 570 711640267 44 517 656143873 943 525 473293028 622 497 418913373 303 992 905954966 679 49 927158907 957 788 442074929 649 441 886854001 820 963 119851476 430 469 561029785 592 846 550735562 189 701 908779865 742 14 716789810 475 411 339202590 309 294 876224748 178 316 281744927 346 563 340707164 463 84 854152851 849 294 154947211 950 905 352616868 193 373 378204910 960 300 795892105 579 805 946744838 492 357 633387750 131 435 927712969 899 316 971957563 95 489 296213718 707 374 14205911 579 419 491864972 943 583 37843174 28 65 302233303 416 13 870368883 343 363 141150133 847 342 282594268 262 229 56303498 682 950 676442116 994 425 850681735 824 272 849441976 866 811 870488606 921 554 315274478 649 313 395650100 200 869 308694150 292 867 364603483 721 852 120037020 918 951 556276632 348 8 827601543 72 488 610876306 261 668 603898670 334 925 242270114 363 748 329743192 374 9 987355714 410 503 86334448 979 941 604831768 704 257 723461295 261 25 428580352 909 414 902839280 203 879 718687028 617 29 934742121 305 772 785903233 920 1 201411674 24 202 240347735 987 4 316994550 645 73 523401723 65 260 754682712 22 630 354347800 922 888 138942615 30 369 771543571 983 318 594057640 116 930 771537397 32 708 628684903 900 665 331652407 588 81 777588351 799 216 734245027 821 271 362061816 321 75 300109735 186 870 405139445 67 52 484508674 532 578 851244918 255 516 396221253 134 556 659521233 517 625 856782480 273 876 403281240 367 806 190291671 123 300 178870584 222 910 941222374 204 253 959193869 925 218 90482075 513 911 329294519 633 715 658367118 919 528 986927448 928 641 402673095 620 571 640687653 292 108 545019989 290 975 853126853 201 689 639860418 719 103 215814749 945 380 727961535 300 624 294503962 799 103 358161138 751 86 329306833 274 520 821231223 537 378 940950763 153 246 784929850 275 850 380297338 574 551 857584480 74 114 91313775 368 866 926897130 686 384 812556463 257 802 546874825 931 438 975195229 796 697 661718796 729 248 28853286 128 795 732276300 834 682 197461179 379 205 964910877 699 963 869618026 367 383 823448430 385 611 713238751 88 691 920983623 389 438 932407958 71 299 51952407 380 721 319182019 772 446 886795307 870 569 373581412 827 940 600421742 491 180 398404288 861 449 616580646 283 221 5520937 938 894 387640565 839 631 56817993 50 292 915479272 813 37 461380623 254 73 988706375 209 202 994094212 139 533 144815826 224 249 573997566 839 678 56602646 234 560 798534403 758 19 343582468 338 372 458137333 55 713 25209395 882 79 647646781 49 320 490159677 305 540 163108914 725 956 534902656 25 575 529234372 434 424 681614422 184 493 527591471 411 717 40794890 222 137 276984822 567 957 667479867 25 220 584262249 148 627 440582910 148 562 915319446 524 43 395788498 107 115 95106753 701 578 296574144 724 839 327197865 841 622 150145841 878 115 283626664 39 42 308541900 923 205 69914695 1 965 528154081 252 831 309659669 926 465 568824829 382 349 398841971 613 314 524723781 784 556 925018271 466 101 780979748 762 765 291435232 182 358 859556823 194 847 905006488 888 689 262994567 801 515 458853422 790 877 35114062 492 810 42965856 50 298 184078617 931 319 371968411 822 381 686499261 994 59 13571237 338 117 183092634 429 444 789534905 405 733 943902221 215 453 780583529 577 229 714739492 36 47 192047122 940 533 317758007 377 969 427128044 336 831 946194201 839 838 274681383 529 537 235319086 410 582 749333444 384 756 767143503 464 57 7368672 915 6 927131407 39 144 164272684 945 486 453169239 555 875 924372629 905 849 802216699 751 296 251805230 44 173 168892303 217 284 354127634 871 32 552351935 723 416 541340531 504 272 81932326 22 826 529612696 205 653 184795422 935 248 610518466 601 466 638249808 655 498 12406252 349 128 89880410 657 93 499077487 500 98 200183651 306 223 553603947 754 87 743257400 176 378 120734218 555 741 892317727 682 243 807210326 982 480 95186415 425 53 115857178 153 553 965347238 499 567 443567181 205 633 943937661 597 258 759476275 776 703 315805941 666 292 368669857 120 548 552725883 904 785 743616271 689 138 149168006 48 318 86938523 777 602 618986933 432 471 979760649 156 718 261320280 9 336 787333276 919 808 85856272 246 347 161260803 316 477 371489088 288 564 997923420 771 983 789061869 507 177 836553239 37 409 890093420 550 65 243923742 471 614 877906474 102 112 778028319 73 111 809421160 933 297 111965548 428 634 280259479 178 668 958378835 384 179 735767947 928 206 675703370 112 252 795070018 262 598 532888030 659 34 400852873 576 40 489043634 420 843 608838517 797 755 348662456 865 154 606485793 77 67 292183764 197 761 48591225 632 248 652681853 453 88 836258696 289 800 219498344 790 511 58207794 945 694 570480877 289 101 256272243 867 662 363671128 589 886 133439904 592 672 225439854 90 326 649971334 788 869 82673545 240 584 945323665 6 148 624728264 707 294 735689871 184 958 733629192 265 243 389458959 594 579 721565123 190 279 871889058 320 964 580447738 299 442 112631639 394 988 551369887 138 349 197754076 201 219 912138504 176 232 567967675 401 36 789675008 72 561 398555357 789 456 861717431 982 621 75167114 780 668 933676207 356 206 117172610 879 670 112054437 744 331 733027348 581 890 713243071 524 617 472969237 6 59 170832577 756 145 802284633 4 807 161034010 423 929 348438103 558 516 301644430 958 52 390791439 868 81 69622837 186 205 378412496 623 33 925291897 668 103 83519188 496 933 542658919 159 975 18381421 946 601 41035816 691 733 167189443 684 62 134597062 867 271 228351927 740 658 185261447 446 354 849240581 477 52 624559369 752 248 611500716 138 151 182197130 423 270 897076266 974 528 973175102 616 673 965061150 88 862 733532545 833 828 49671884 96 993 396967377 318 978 97423187 310 797 763567389 199 241 775668830 672 641 705962886 311 912 125255141 277 410 196476759 472 243 343619889 109 883 973122305 716 772 855065679 73 536 187218555 365 438 426267562 557 851 757210342 362 234 688841078 661 853 924715758 546 73 712795516 87 30 780261964 595 435 718683231 357 391 758830367 843 673 257076681 607 581 297490132 195 475 568414629 764 937 149579687 501 52 840108104 514 694 659156772 368 167 418636306 476 584 779757092 828 166 96785139 163 179 63936330 898 147 981550398 947 615 632699968 9 560 851150415 164 961 87235775 679 335 196443027 457 225 238195204 873 373 928025960 630 427 687480665 620 540 534679328 593 117 765152153 183 771 915302183 8 417 143582789 799 290 24967448 909 482 59950000 341 123 330315659 873 267 186462020 91 747 372841800 461 452 269197041 929 235 95042473 493 897 40394370 281 865 937069550 221 996 903185341 109 884 66191425 521 41 5048591 645 709 167728511 524 903 724907550 592 76 414241996 476 845 622126535 953 92 133588627 481 117 251837745 276 864 85484670 519 373 306224594 461 59 21658585 237 500 848412550 169 287 868938308 758 907 518246386 282 285 655253879 885 764 59280413 603 261 407365813 792 377 807700556 396 9 357655837 727 517 930519765 973 424 384222294 993 582 905457192 739 441 273000525 499 305 302457809 527 541 627480969 488 794 318901008 647 249 246593152 634 530 689506583 905 245 136958284 382 339 319483092 199 610 71293720 147 599 654888934 909 211 546987098 813 672 796044105 634 280 320273260 502 416 466897359 740 696 802746043 568 34 764879060 767 947 737697112 286 484 955182635 494 858 887540791 900 693 40959760 936 838 179991925 863 189 718805022 338 259 22609836 418 641 363565201 932 811 186974582 643 172 24003162 326 622 344931008 700 80 358639017 29 33 927686678 287 144 773517269 807 734 660470726 687 577 324114944 393 604 753382342 171 885 475597707 849 267 750066748 978 532 896502100 123 282 918110219 235 20 641510458 697 297 463810187 432 727 55685373 942 675 701026118 346 654 584192311 215 172 757870160 226 399 362508744 824 646 337436998 610 541 651843235 397 234 402660397 915 35 206595095 1 133 764439424 616 676 948144707 703 594 694692124 568 884 994810605 880 108 296462062 677 464 329489883 337 975 884246911 956 926 821492924 572 155 105641317 45 504 918251284 112 533 33322510 979 594 841726638 615 950 326256194 11 176 402086846 788 660 456703369 921 501 762108000 160 786 987014054 69 472 5843186 711 293 694015655 731 573 466729843 7 395 365131270 390 856 497292245 500 775 605948313 136 831 192587708 691 277 237442469 72 385 351563294 171 43 661902784 359 807 962200813 194 739 268838992 631 687 724480446 93 380 255902223 191 581 474212527 315 65 899905667 741 321 836612123 422 140 958491781 227 759 202221862 971 309 420087098 431 917 683107535 817 116 735439723 758 601 850119553 204 26 664612081 633 762 728152402 991 934 881631176 557 975 399882550 725 121 239145917 709 361 365102211 51 730 78874264 250 313 282341220 832 423 269851336 946 832 522101506 760 799 370829721 20 977 617715733 527 459 339907552 532 35 669514330 612 749 337046166 493 338 615637642 381 17 186999016 328 129 621319056 471 46 813349404 883 271 593969598 83 134 220283643 758 462 516370075 706 301 58203783 670 113 75098774 495 436 248215212 622 197 174042134 954 83 734512868 251 669 940964514 327 377 72710110 806 440 700382996 692 129 589594420 479 641 598769202 697 418 44389212 202 671 546545443 332 389 775801870 660 716 226737652 580 49 834978398 174 29 378734793 822 423 645174572 959 658 568811149 373 566 867262685 893 272 961783086 742 422 119054424 295 382 891401243 316 329 912255611 401 654 459606206 474 66 881074081 382 548 698578085 723 974 712020230 652 227 820371619 87 394 871393029 625 626 35905403 473 206 895502746 734 367 215418961 551 177 971217441 852 584 737648758 330 786 895271214 240 758 668451193 199 292 392473436 4 624 388435006 716 34 673759617 13 480 332891795 915 96 846119962 132 778 611977244 656 274 311429566 694 182 825300905 354 591 748147042 268 269 658067725 585 182 460612167 46 422 394836124 594 682 797514974 364 409 557764529 728 310 383238221 271 500 207624994 341 404 159800421 859 957 686678833 311 61 293246754 297 720 93973912 674 267 67436816 652 997 603556841 936 149 223538780 837 386 586564798 985 813 888636135 181 589 369150149 482 260 570695682 759 930 583764208 125 227 559623662 80 852 889017862 5 262 356873389 399 170 724339996 824 487 745015278 967 938 553337347 695 437 853663417 834 43 517556989 372 174 27153872 96 339 951661455 130 799 724083035 977 121 268092490 115 656 77951423 944 118 401252092 648 844 764926437 264 555 125303455 411 565 396930912 368 262 649275788 30 569 40181577 794 553 340956074 842 453 433369188 554 456 174496126 237 890 388554412 758 862 159062779 210 206 234123695 813 716 6892607 387 497 168871434 878 618 444493455 129 88 305707394 521 931 457887358 395 357 629510551 987 160 379625676 167 646 328966074 537 445 982571720 441 489 962546542 15 786 616153665 50 82 572218738 255 477 97826621 262 239 332561199 743 929 858672463 427 847 814572066 177 513 415184385 129 494 478545534 825 407 424293529 213 350 90648375 472 93 114381236 445 173 299639951 302 73 762502089 162 627 175457285 806 55 587906880 919 358 434889409 728 449 567008036 988 597 916283188 287 817 746902221 310 733 444275101 533 972 16046779 564 352 206299512 377 880 347225382 225 609 631049182 710 740 2770103 419 466 224788246 737 489 606293255 453 681 819558180 214 887 69249225 543 85 168178516 90 538 506912445 690 792 196407391 879 642 748977588 171 884 48035907 181 50 923207947 30 608 394724782 684 211 131431429 283 679 563497202 566 417 476832775 948 454 860205042 41 717 517038520 311 214 775880371 931 449 748256185 857 815 371274118 873 620 525896201 492 951 575659694 911 643 982033093 43 18 162691285 860 5 278207189 506 699 325018075 123 960 331358792 737 185 556911652 647 399 66163638 112 489 345591967 478 303 743488171 688 903 17213264 696 148 205267995 459 833 896579383 6 513 685951184 954 106 582445598 514 590 907179911 156 771 391601591 57 189 900841873 30 959 22607970 124 549 993268241 304 312 12521464 686 196 169710012 518 639 53921424 770 148 17670847 532 854 256760252 144 446 349583354 41 17 51056612 763 333 939049719 72 930 493288803 504 677 13381148 711 503 115018474 912 621 676980932 181 705 217646866 509 598 737354310 810 505 864370468 696 407 547268998 182 478 116303762 506 505 408863594 307 187 109874704 148 311 758069224 165 878 982465927 574 319 565767784 935 313 917736537 51 912 394346553 355 602 325402468 323 665 746358502 67 433 523956157 724 64 31098829 395 688 934753609 654 283 487202839 267 24 48781497 498 491 708995593 515 573 316626851 631 950 301704201 745 284 895153860 18 140 707837055 25 215 107770740 429 363 687916275 205 185 983812761 76 903 309110924 892 479 259907365 691 261 822366280 511 230 603097944 901 116 197952019 529 753 268151559 500 909 364077481 267 113 363469956 522 309 56697877 966 876 299983271 453 288 296846121 307 698 135022257 386 20 188628340 87 522 679076675 501 253 686437790 88 81 295834402 487 275 804385000 358 604 133413054 450 808 861947254 226 362 878373536 37 855 19387362 979 108 661331583 759 111 82115797 442 522 838054176 914 397 66305415 567 921 950232525 374 196 89323627 69 939 694586469 974 168 146728577 650 161 347794261 598 352 183084187 536 573 28536517 812 526 802791990 27 447 228057378 67 439 724245104 8 48 445712191 316 859 467668228 381 931 749616569 188 907 488238201 360 45 428034498 683 583 887326604 860 645 404717624 915 248 62004070 746 729 637690323 313 921 645695581 396 546 855551635 904 459 621704400 391 108 203328064 71 711 597482073 481 594 793609969 55 508 220864243 15 24 856147704 400 978 41273504 149 721 25921221 115 14 196800988 910 252 747398258 551 881 266366056 522 280 729780831 203 169 791192465 613 73 404556878 827 747 756693624 725 306 193285703 306 603 209090361 805 17 236225221 372 246 121674064 685 230 353844295 105 170 427337786 901 440 595345788 455 771 469935639 737 674 173531624 938 587 809467043 477 551 918939545 470 271 598601428 179 619 865554990 803 477 734873894 144 651 906246986 783 555 419374340 139 334 527320996 852 793 261270626 363 996 529326794 17 560 748303104 448 394 600628915 66 895 839802376 774 127 231724495 665 978 236341384 374 940 741988647 792 298 308802881 973 428 443471214 172 262 186329533 714 42 888213103 268 644 936896748 113 503 83924101 86 281 289262984 271 671 582379786 189 991 625008867 24 554 183141177 179 824 968350342 677 575 279842287 177 331 775181301 537 456 776683743 243 315 590963581 564 9 827782985 61 900 315463507 636 838 766871526 201 917 844311765 235 3 317275865 36 664 321443246 727 596 890916425 107 914 478605790 376 980 727768326 259 34 847518376 464 388 519161651 818 371 984207706 585 508 727319001 603 794 753885176 893 278 635048118 594 226 647034909 833 150 290411663 862 945 3032085 103 242 618530914 389 127 853628380 366 222 134359204 44 972 771114551 300 809 717880654 828 894 162287044 766 652 602147944 163 913 115817872 628 652 551724651 390 895 931247943 182 522 876693187 503 787 456398269 798 60 604584114 989 13 84924348 252 154 415354958 336 937 99421429 582 567 631569615 245 362 802307392 478 24 41507389 130 377 934983731 465 697 259309447 568 325 301678940 453 428 848563614 959 338 521538916 321 632 199889494 949 870 761256075 914 472 183000064 5 104 890359896 384 547 316197280 377 460 264916602 228 86 605467667 279 776 254590173 748 334 843872662 789 541 692099816 742 530 845102049 258 929 878428219 834 791 894309029 515 724 308368134 783 378 186089096 185 289 395743074 488 208 941146412 294 897 510274540 334 135 982096762 438 251 208981873 800 22 405890119 953 533 895133580 335 389 308078931 461 981 678492441 406 268 145614680 234 821 93466774 959 482 76702041 746 693 247451025 912 234 334978658 924 64 417855227 985 732 655732112 657 579 8795325 74 692 564898466 840 80 335822593 835 956 409985997 451 649 517037430 961 182 763697801 544 437 234778872 588 987 969111956 633 150 203996255 644 454 943965272 702 105 558257730 660 645 980593645 723 756 205128202 839 858 628074694 537 874 784739006 998 150 567815311 913 624 35476457 687 398 688281818 212 588 480150087 441 354 449196610 559 200 727259909 848 922 150488975 66 355 859847249 138 349 89191407 905 213 97229832 211 112 331847337 43 312 269219124 107 120 938141823 884 570 134752482 93 305 158167470 347 454 350920176 665 380 795580885 553 904 404946544 913 390 120610193 56 513 167983559 747 983 722298929 49 467 716351692 996 468 5276876 971 45 745217424 311 511 147363677 648 743 772379061 843 601 162052209 164 892 417379256 820 326 936449701 928 432 892011143 496 453 9025579 635 657 496206819 468 109 455106504 147 929 750557525 255 438 268493980 169 312 99970377 580 26 381796836 764 323 570187538 794 302 511639197 64 953 239580786 274 468 674219239 581 495 920331814 230 335 93413917 622 556 686657611 942 91 397373489 570 183 279427160 722 663 582189725 693 139 699155748 577 25 771332852 303 499 429877413 946 653 473569991 222 546 511084012 856 679 164949892 346 475 66117820 518 171 876136730 345 425 716407612 173 765 298881853 460 285 711222728 246 591 802244864 900 171 17953691 480 787 698079041 770 147 677720659 346 740 749948193 264 502 805039746 44 119 546874770 383 290 885531407 766 536 433761418 643 93 24258987 958 248 261309629 642 192 2471993 491 486 441815943 120 635 774198422 926 109 999917907 868 233 52109445 835 741 522045147 1 425 342363587 960 705 433249268 879 506 459498370 817 238 142445041 479 33 681882079 375 803 789741489 233 348 116785844 380 418 600434707 758 601 787519813 352 920 130986265 628 18 586455586 179 723 503589192 671 267 743812581 846 172 10676518 628 632 534318603 262 110 128528093 783 888 746820439 627 922 140856197 743 469 41870651 88 497 855311985 363 940 660761522 994 797 762528611 19 230 896847138 193 268 565121997 671 599 312636469 147 370 812331004 816 206 604212452 456 10 998661989 549 182 615964805 32 904 546729067 184 409 481645124 501 79 208076080 92 537 117626389 162 911 443683010 331 94 754129831 290 161 555111387 115 144 376020989 691 38 236852423 344 750 682975431 453 384 369374179 277 472 577706177 681 854 387078541 794 300 173592430 975 471 327828813 26 403 981872924 294 803 803276805 844 109 411887965 824 622 548287074 926 639 435712935 782 254 553527053 197 173 55413471 240 719 31917145 255 137 451513414 990 758 692089301 44 3 697499609 459 963 979750686 669 336 429531674 224 874 360249459 476 90 902950297 532 981 107187174 521 37 468160644 5 969 486716174 821 367 139821214 711 116 680769364 546 110 587332840 906 573 884646889 488 311 602592471 167 808 328964775 599 233 237556890 586 534 661871695 744 462 709543391 763 93 204954344 769 318 925354733 429 344 774253781 902 566 22670251 556 464 245853842 969 979 668186356 783 144 505477929 616 873 32167029 243 795 281979067 477 770 669587848 146 939 410584440 935 688 84793117 650 732 74739711 464 86 784202592 198 898 540627399 314 789 833903713 930 980 256596347 140 843 630644067 464 925 202063466 742 65 38968625 586 540 936097792 98 845 3673710 753 365 134237812 797 336 77672714 875 540 906134532 497 609 773232794 693 216 613156534 922 912 432711716 890 523 19234491 325 93 187547504 366 443 723072371 831 57 751209589 988 512 846318156 559 879 210265255 178 95 937210560 723 977 743928685 934 659 90340698 71 101 485486411 75 803 524214358 165 866 484166507 419 298 107238064 676 642 699033081 90 136 691140426 190 539 720847152 503 930 727708769 349 129 389233672 225 406 75653258 408 390 99999372 428 765 326183261 694 359 995984261 195 645 376494003 815 794 585467021 692 263 986188 865 546 593205343 979 553 736180687 4 107 906809132 178 622 448454648 275 554 452898280 826 823 786988972 457 270 148006144 41 299 516457536 314 687 17714957 418 53 755088680 87 804 725985038 799 403 698027697 116 19 46374077 94 812 701936445 940 136 76142152 247 683 901678954 905 338 451305525 426 681 158348855 754 866 789877564 222 230 599128665 524 995 259556890 180 969 90864 333 831 827410145 517 641 169275096 115 199 138761252 909 212 328573556 603 512 336618014 512 838 383778199 46 349 612703923 483 426 726563167 494 313 524885996 136 224 33093159 858 907 770099053 726 326 41964859 328 450 536890757 307 627 688940855 196 490 60514498 371 300 681355146 895 752 111370329 338 334 793736202 165 439 202438982 574 607 50734664 506 40 342533579 964 680 937649516 29 532 710785171 1 85 26350270 753 914 332536104 914 297 812480538 635 346 687195032 53 15 52348956 901 152 194860005 768 856 96805643 844 621 44169445 420 319 312782514 837 435 825610836 555 745 56709652 59 341 237263760 498 531 157305528 438 637 790523720 588 507 278114737 266 155 132490319 730 146 254470061 577 944 731139606 296 609 25478216 3 603 724299024 149 992 785082818 667 708 338577567 560 962 148618474 406 651 297821514 968 548 21019941 903 958 122242358 530 242 520391336 621 711 291877782 441 272 456255478 324 546 337715114 154 522 190372860 597 972 138125993 355 867 92149746 849 803 735980946 135 343 429574507 140 52 20453547 407 427 92452627 456 827 188075543 525 171 151296921 213 391 253627877 448 212 204147916 687 859 655989239 240 557 45987172 334 831 499666967 221 705 373481092 112 864 405484369 651 647 530301659 288 125 542997137 513 138 779246713 383 471 471298206 570 548 105633296 138 429 105322463 557 790 737905920 865 23 141366895 575 989 234430413 241 765 320296617 582 755 133080697 892 862 360958969 897 186 201230011 428 192 136767037 477 559 210240070 879 660 320343487 191 579 942940176 771 111 76354783 232 510 468959268 494 935 431728550 845 382 920137544 593 183 919242774 271 529 951903458 594 28 592417114 21 291 190945190 700 316 111079485 955 243 850661007 16 384 975332069 160 253 196069239 315 521 165566069 805 408 553690006 220 985 43516887 699 795 748095267 406 768 300323280 809 306 871162759 564 93 795674007 839 641 194030028 846 927 983960525 581 929 805839638 627 553 487991092 734 207 438304848 116 882 288109501 680 458 8883236 963 600 822686632 422 741 424905904 284 153 120216394 422 355 790991581 894 53 431816511 959 552 183366180 354 631 397492602 764 983 357875859 722 906 245162112 306 661 959601158 509 198 537410576 949 113 281826490 468 417 451389558 949 27 34109410 800 628 789692603 529 929 20755622 748 230 195767136 101 14 671322186 265 990 435877043 975 555 973459885 586 163 225194692 926 144 506100963 732 927 313676742 263 457 840679309 803 291 57113268 686 123 149490086 439 565 992286237 821 138 500519113 966 283 583325114 905 918 550004332 972 537 727434027 593 745 285406365 131 751 938530834 404 292 927047740 533 171 734567448 171 776 465738473 326 306 562192123 794 384 425008080 623 942 26140008 203 934 515418516 926 472 554678436 182 275 404318260 833 451 571945387 435 4 464955929 670 957 309582946 997 871 833183809 333 84 464883592 464 688 561180014 310 567 25463561 863 640 829287046 245 39 508141073 676 109 287982386 320 832 470050425 623 257 506223410 545 498 99519170 183 834 788075102 132 706 341502333 6 74 996373361 295 668 683708458 204 416 295008386 293 792 367416082 17 98 928899997 592 554 99979021 998 591 201702899 146 790 236172368 76 770 106542665 197 339 597452940 750 910 710837850 396 620 497505829 250 406 895447547 465 259 550539301 151 230 460182989 277 741 759820229 974 351 467065991 261 433 445391662 78 162 753471984 192 315 380282447 728 818 643694884 587 668 258323299 397 818 890581006 221 563 111641750 137 809 169799359 18 337 468193473 84 744 866504660 280 324 19142478 818 361 434945133 414 522 500407226 608 557 609164526 217 498 173246974 749 750 481136226 908 642 391062837 543 118 407934943 542 932 345121103 823 421 199788207 912 145 451582636 354 75 976404885 436 163 256668206 51 67 307761597 436 869 157588692 165 677 8542365 161 654 120998128 754 90 547083835 434 553 100302031 72 717 161420628 877 690 611522490 392 250 999621346 347 233 339671489 356 754 771184605 382 578 417239964 22 678 100252509 916 690 332456901 492 430 100671790 827 655 249487442 83 173 444653106 775 568 320721541 415 898 212794651 334 808 8826896 512 569 243723246 120 454 165478158 23 450 226370470 900 66 497018310 352 24 650021392 774 53 330755257 539 28 835103401 722 578 650914896 893 632 130865962 278 82 177182383 303 32 713903755 689 882 107371902 58 632 155581566 425 642 439550858 429 525 117435721 681 351 749000100 385 301 675505233 893 279 100040961 755 253 196171263 755 846 322001145 300 783 954415707 652 250 730232261 37 752 262367198 529 284 789777857 883 234 650680811 730 2 242000876 515 221 297889017 50 539 934609377 162 687 708697876 330 597 359127928 5 551 879412059 908 547 13818011 856 647 389918204 400 376 188314211 674 813 995375654 222 721 512367435 940 880 139781007 343 177 393299331 344 992 755283998 913 977 732006834 111 26 619953486 352 48 208005139 579 318 167437626 660 967 470059256 323 643 492423481 917 289 682919987 283 57 864932314 752 409 56596717 26 767 935501511 846 645 302180691 597 18 519154518 994 147 411441008 164 478 701358057 702 23 90132250 418 550 120412886 963 275 709053121 755 489 249919794 980 561 571641122 812 785 521955823 389 34 995161203 868 528 54571525 558 614 252618253 436 894 896766864 421 360 9134321 932 784 985418319 600 49 365063607 449 279 961529100 288 864 502334734 803 983 89960082 578 869 280222419 838 557 340156931 571 643 642525344 908 281 350588792 581 820 129285922 377 762 396806416 965 394 164969138 314 545 47489230 135 784 713436422 724 109 516509724 187 143 195400439 794 656 101719809 531 344 203032084 802 213 786541681 865 742 853304749 79 915 322065324 696 716 971050469 471 887 281400598 913 4 425887517 721 601 903654904 886 24 767788011 328 476 703414095 839 541 947519974 821 917 928743608 197 706 993815276 657 586 371959153 919 156 629112158 803 770 475041364 226 272 170168943 942 673 278857360 925 159 341216326 67 476 646893176 203 214 788987638 180 802 742990748 166 547 715848913 997 805 716080030 929 185 521600823 554 492 792414585 117 446 975679544 824 357 27858351 712 356 346983060 604 996 98023226 288 383 384625898 764 801 234524489 937 641 410317356 294 893 851351581 110 995 169408189 930 32 334216515 456 121 778662549 480 398 282378996 722 990 382472124 86 145 746793501 876 592 688305667 600 93 434649264 856 405 350118749 302 181 823303059 446 541 965895712 276 106 349034776 434 968 616993909 132 645 785657773 557 456 249080257 127 682 81601185 459 132 2360683 300 764 962724456 63 112 219555891 976 359 324591466 964 681 14066165 123 740 996877667 839 687 628076633 519 834 616143066 321 775 67629486 693 462 510055415 520 443 465760018 934 244 451573294 761 77 120393726 92 1000 723069164 104 28 140442889 264 163 133408503 618 314 249147135 265 677 636818514 755 866 661233929 435 181 784368414 522 865 330048223 421 867 125944272 925 391 490016313 307 834 951496284 154 243 4002433 701 554 280865505 747 44 784163410 396 169 73841419 405 183 154836749 546 833 58703532 900 276 538473483 52 110 366060663 503 813 677928145 302 580 583231994 821 333 794352209 877 423 702027608 247 554 13761594 89 592 900711809 393 392 629029550 555 588 893048566 293 39 383356132 18 844 963965593 778 932 223165725 891 474 353200533 882 376 214283041 515 116 760391886 381 119 254346468 633 613 438214145 371 41 797623350 687 940 311484569 689 150 734717063 76 668 490287901 2 608 337645328 802 749 924891750 572 373 353016666 480 683 348499774 385 384 916872008 523 636 853457268 370 380 821611120 16 933 69558404 173 221 10691987 957 418 377184358 53 973 339568542 398 330 817998577 766 994 461091701 103 559 490550106 507 192 534318844 167 941 845535683 302 264 130727779 164 112 355670889 604 580 511268033 415 201 441385375 365 405 382281986 634 814 536535611 457 641 701510438 58 225 56834736 964 447 938975325 462 104 970338902 265 912 905691790 199 405 525901586 388 958 305107829 315 890 54057371 385 56 570332198 994 520 808546618 978 824 920195793 33 532 7202932 661 509 35283080 565 935 725528251 549 414 972485207 966 205 800252573 802 787 221772296 108 853 417821887 492 396 630747447 591 773 672505711 115 682 9982451 935 339 82418733 928 388 344214265 751 425 729373833 219 431 357840204 141 771 48305337 237 592 969588168 317 75 534325269 643 931 453461237 274 992 327661033 226 284 937214988 138 543 321562995 875 35 345704165 399 122 826138273 179 346 882346654 485 713 168233308 976 1000 977322326 289 358 355484004 957 920 541512290 907 682 965286127 798 746 635578228 486 950 589589176 907 44 645529368 155 262 506767425 156 136 875839550 1 1001 3 1 1002 3 1 1003 3 1 1004 3 1 1005 3 1 1006 3 1 1007 3 1 1008 3 1 1009 3 1 1010 3 1 1011 3 1 1012 3 1 1013 3 1 1014 3 1 1015 3 1 1016 3 1 1017 3 1 1018 3 1 1019 3 1 1020 3 1 1021 3 1 1022 3 1 1023 3 1 1024 3 1 1025 3 1 1026 3 1 1027 3 1 1028 3 1 1029 3 1 1030 3 1 1031 3 1 1032 3 1 1033 3 1 1034 3 1 1035 3 1 1036 3 1 1037 3 1 1038 3 1 1039 3 1 1040 3 1 1041 3 1 1042 3 1 1043 3 1 1044 3 1 1045 3 1 1046 3 1 1047 3 1 1048 3 1 1049 3 1 1050 3 1 1051 3 1 1052 3 1 1053 3 1 1054 3 1 1055 3 1 1056 3 1 1057 3 1 1058 3 1 1059 3 1 1060 3 1 1061 3 1 1062 3 1 1063 3 1 1064 3 1 1065 3 1 1066 3 1 1067 3 1 1068 3 1 1069 3 1 1070 3 1 1071 3 1 1072 3 1 1073 3 1 1074 3 1 1075 3 1 1076 3 1 1077 3 1 1078 3 1 1079 3 1 1080 3 1 1081 3 1 1082 3 1 1083 3 1 1084 3 1 1085 3 1 1086 3 1 1087 3 1 1088 3 1 1089 3 1 1090 3 1 1091 3 1 1092 3 1 1093 3 1 1094 3 1 1095 3 1 1096 3 1 1097 3 1 1098 3 1 1099 3 1 1100 3 1 1101 3 1 1102 3 1 1103 3 1 1104 3 1 1105 3 1 1106 3 1 1107 3 1 1108 3 1 1109 3 1 1110 3 1 1111 3 1 1112 3 1 1113 3 1 1114 3 1 1115 3 1 1116 3 1 1117 3 1 1118 3 1 1119 3 1 1120 3 1 1121 3 1 1122 3 1 1123 3 1 1124 3 1 1125 3 1 1126 3 1 1127 3 1 1128 3 1 1129 3 1 1130 3 1 1131 3 1 1132 3 1 1133 3 1 1134 3 1 1135 3 1 1136 3 1 1137 3 1 1138 3 1 1139 3 1 1140 3 1 1141 3 1 1142 3 1 1143 3 1 1144 3 1 1145 3 1 1146 3 1 1147 3 1 1148 3 1 1149 3 1 1150 3 1 1151 3 1 1152 3 1 1153 3 1 1154 3 1 1155 3 1 1156 3 1 1157 3 1 1158 3 1 1159 3 1 1160 3 1 1161 3 1 1162 3 1 1163 3 1 1164 3 1 1165 3 1 1166 3 1 1167 3 1 1168 3 1 1169 3 1 1170 3 1 1171 3 1 1172 3 1 1173 3 1 1174 3 1 1175 3 1 1176 3 1 1177 3 1 1178 3 1 1179 3 1 1180 3 1 1181 3 1 1182 3 1 1183 3 1 1184 3 1 1185 3 1 1186 3 1 1187 3 1 1188 3 1 1189 3 1 1190 3 1 1191 3 1 1192 3 1 1193 3 1 1194 3 1 1195 3 1 1196 3 1 1197 3 1 1198 3 1 1199 3 1 1200 3 1 1201 3 1 1202 3 1 1203 3 1 1204 3 1 1205 3 1 1206 3 1 1207 3 1 1208 3 1 1209 3 1 1210 3 1 1211 3 1 1212 3 1 1213 3 1 1214 3 1 1215 3 1 1216 3 1 1217 3 1 1218 3 1 1219 3 1 1220 3 1 1221 3 1 1222 3 1 1223 3 1 1224 3 1 1225 3 1 1226 3 1 1227 3 1 1228 3 1 1229 3 1 1230 3 1 1231 3 1 1232 3 1 1233 3 1 1234 3 1 1235 3 1 1236 3 1 1237 3 1 1238 3 1 1239 3 1 1240 3 1 1241 3 1 1242 3 1 1243 3 1 1244 3 1 1245 3 1 1246 3 1 1247 3 1 1248 3 1 1249 3 1 1250 3 1 1251 3 1 1252 3 1 1253 3 1 1254 3 1 1255 3 1 1256 3 1 1257 3 1 1258 3 1 1259 3 1 1260 3 1 1261 3 1 1262 3 1 1263 3 1 1264 3 1 1265 3 1 1266 3 1 1267 3 1 1268 3 1 1269 3 1 1270 3 1 1271 3 1 1272 3 1 1273 3 1 1274 3 1 1275 3 1 1276 3 1 1277 3 1 1278 3 1 1279 3 1 1280 3 1 1281 3 1 1282 3 1 1283 3 1 1284 3 1 1285 3 1 1286 3 1 1287 3 1 1288 3 1 1289 3 1 1290 3 1 1291 3 1 1292 3 1 1293 3 1 1294 3 1 1295 3 1 1296 3 1 1297 3 1 1298 3 1 1299 3 1 1300 3 1 1301 3 1 1302 3 1 1303 3 1 1304 3 1 1305 3 1 1306 3 1 1307 3 1 1308 3 1 1309 3 1 1310 3 1 1311 3 1 1312 3 1 1313 3 1 1314 3 1 1315 3 1 1316 3 1 1317 3 1 1318 3 1 1319 3 1 1320 3 1 1321 3 1 1322 3 1 1323 3 1 1324 3 1 1325 3 1 1326 3 1 1327 3 1 1328 3 1 1329 3 1 1330 3 1 1331 3 1 1332 3 1 1333 3 1 1334 3 1 1335 3 1 1336 3 1 1337 3 1 1338 3 1 1339 3 1 1340 3 1 1341 3 1 1342 3 1 1343 3 1 1344 3 1 1345 3 1 1346 3 1 1347 3 1 1348 3 1 1349 3 1 1350 3 1 1351 3 1 1352 3 1 1353 3 1 1354 3 1 1355 3 1 1356 3 1 1357 3 1 1358 3 1 1359 3 1 1360 3 1 1361 3 1 1362 3 1 1363 3 1 1364 3 1 1365 3 1 1366 3 1 1367 3 1 1368 3 1 1369 3 1 1370 3 1 1371 3 1 1372 3 1 1373 3 1 1374 3 1 1375 3 1 1376 3 1 1377 3 1 1378 3 1 1379 3 1 1380 3 1 1381 3 1 1382 3 1 1383 3 1 1384 3 1 1385 3 1 1386 3 1 1387 3 1 1388 3 1 1389 3 1 1390 3 1 1391 3 1 1392 3 1 1393 3 1 1394 3 1 1395 3 1 1396 3 1 1397 3 1 1398 3 1 1399 3 1 1400 3 1 1401 3 1 1402 3 1 1403 3 1 1404 3 1 1405 3 1 1406 3 1 1407 3 1 1408 3 1 1409 3 1 1410 3 1 1411 3 1 1412 3 1 1413 3 1 1414 3 1 1415 3 1 1416 3 1 1417 3 1 1418 3 1 1419 3 1 1420 3 1 1421 3 1 1422 3 1 1423 3 1 1424 3 1 1425 3 1 1426 3 1 1427 3 1 1428 3 1 1429 3 1 1430 3 1 1431 3 1 1432 3 1 1433 3 1 1434 3 1 1435 3 1 1436 3 1 1437 3 1 1438 3 1 1439 3 1 1440 3 1 1441 3 1 1442 3 1 1443 3 1 1444 3 1 1445 3 1 1446 3 1 1447 3 1 1448 3 1 1449 3 1 1450 3 1 1451 3 1 1452 3 1 1453 3 1 1454 3 1 1455 3 1 1456 3 1 1457 3 1 1458 3 1 1459 3 1 1460 3 1 1461 3 1 1462 3 1 1463 3 1 1464 3 1 1465 3 1 1466 3 1 1467 3 1 1468 3 1 1469 3 1 1470 3 1 1471 3 1 1472 3 1 1473 3 1 1474 3 1 1475 3 1 1476 3 1 1477 3 1 1478 3 1 1479 3 1 1480 3 1 1481 3 1 1482 3 1 1483 3 1 1484 3 1 1485 3 1 1486 3 1 1487 3 1 1488 3 1 1489 3 1 1490 3 1 1491 3 1 1492 3 1 1493 3 1 1494 3 1 1495 3 1 1496 3 1 1497 3 1 1498 3 1 1499 3 1 1500 3 1 1501 3 1 1502 3 1 1503 3 1 1504 3 1 1505 3 1 1506 3 1 1507 3 1 1508 3 1 1509 3 1 1510 3 1 1511 3 1 1512 3 1 1513 3 1 1514 3 1 1515 3 1 1516 3 1 1517 3 1 1518 3 1 1519 3 1 1520 3 1 1521 3 1 1522 3 1 1523 3 1 1524 3 1 1525 3 1 1526 3 1 1527 3 1 1528 3 1 1529 3 1 1530 3 1 1531 3 1 1532 3 1 1533 3 1 1534 3 1 1535 3 1 1536 3 1 1537 3 1 1538 3 1 1539 3 1 1540 3 1 1541 3 1 1542 3 1 1543 3 1 1544 3 1 1545 3 1 1546 3 1 1547 3 1 1548 3 1 1549 3 1 1550 3 1 1551 3 1 1552 3 1 1553 3 1 1554 3 1 1555 3 1 1556 3 1 1557 3 1 1558 3 1 1559 3 1 1560 3 1 1561 3 1 1562 3 1 1563 3 1 1564 3 1 1565 3 1 1566 3 1 1567 3 1 1568 3 1 1569 3 1 1570 3 1 1571 3 1 1572 3 1 1573 3 1 1574 3 1 1575 3 1 1576 3 1 1577 3 1 1578 3 1 1579 3 1 1580 3 1 1581 3 1 1582 3 1 1583 3 1 1584 3 1 1585 3 1 1586 3 1 1587 3 1 1588 3 1 1589 3 1 1590 3 1 1591 3 1 1592 3 1 1593 3 1 1594 3 1 1595 3 1 1596 3 1 1597 3 1 1598 3 1 1599 3 1 1600 3 1 1601 3 1 1602 3 1 1603 3 1 1604 3 1 1605 3 1 1606 3 1 1607 3 1 1608 3 1 1609 3 1 1610 3 1 1611 3 1 1612 3 1 1613 3 1 1614 3 1 1615 3 1 1616 3 1 1617 3 1 1618 3 1 1619 3 1 1620 3 1 1621 3 1 1622 3 1 1623 3 1 1624 3 1 1625 3 1 1626 3 1 1627 3 1 1628 3 1 1629 3 1 1630 3 1 1631 3 1 1632 3 1 1633 3 1 1634 3 1 1635 3 1 1636 3 1 1637 3 1 1638 3 1 1639 3 1 1640 3 1 1641 3 1 1642 3 1 1643 3 1 1644 3 1 1645 3 1 1646 3 1 1647 3 1 1648 3 1 1649 3 1 1650 3 1 1651 3 1 1652 3 1 1653 3 1 1654 3 1 1655 3 1 1656 3 1 1657 3 1 1658 3 1 1659 3 1 1660 3 1 1661 3 1 1662 3 1 1663 3 1 1664 3 1 1665 3 1 1666 3 1 1667 3 1 1668 3 1 1669 3 1 1670 3 1 1671 3 1 1672 3 1 1673 3 1 1674 3 1 1675 3 1 1676 3 1 1677 3 1 1678 3 1 1679 3 1 1680 3 1 1681 3 1 1682 3 1 1683 3 1 1684 3 1 1685 3 1 1686 3 1 1687 3 1 1688 3 1 1689 3 1 1690 3 1 1691 3 1 1692 3 1 1693 3 1 1694 3 1 1695 3 1 1696 3 1 1697 3 1 1698 3 1 1699 3 1 1700 3 1 1701 3 1 1702 3 1 1703 3 1 1704 3 1 1705 3 1 1706 3 1 1707 3 1 1708 3 1 1709 3 1 1710 3 1 1711 3 1 1712 3 1 1713 3 1 1714 3 1 1715 3 1 1716 3 1 1717 3 1 1718 3 1 1719 3 1 1720 3 1 1721 3 1 1722 3 1 1723 3 1 1724 3 1 1725 3 1 1726 3 1 1727 3 1 1728 3 1 1729 3 1 1730 3 1 1731 3 1 1732 3 1 1733 3 1 1734 3 1 1735 3 1 1736 3 1 1737 3 1 1738 3 1 1739 3 1 1740 3 1 1741 3 1 1742 3 1 1743 3 1 1744 3 1 1745 3 1 1746 3 1 1747 3 1 1748 3 1 1749 3 1 1750 3 1 1751 3 1 1752 3 1 1753 3 1 1754 3 1 1755 3 1 1756 3 1 1757 3 1 1758 3 1 1759 3 1 1760 3 1 1761 3 1 1762 3 1 1763 3 1 1764 3 1 1765 3 1 1766 3 1 1767 3 1 1768 3 1 1769 3 1 1770 3 1 1771 3 1 1772 3 1 1773 3 1 1774 3 1 1775 3 1 1776 3 1 1777 3 1 1778 3 1 1779 3 1 1780 3 1 1781 3 1 1782 3 1 1783 3 1 1784 3 1 1785 3 1 1786 3 1 1787 3 1 1788 3 1 1789 3 1 1790 3 1 1791 3 1 1792 3 1 1793 3 1 1794 3 1 1795 3 1 1796 3 1 1797 3 1 1798 3 1 1799 3 1 1800 3 1 1801 3 1 1802 3 1 1803 3 1 1804 3 1 1805 3 1 1806 3 1 1807 3 1 1808 3 1 1809 3 1 1810 3 1 1811 3 1 1812 3 1 1813 3 1 1814 3 1 1815 3 1 1816 3 1 1817 3 1 1818 3 1 1819 3 1 1820 3 1 1821 3 1 1822 3 1 1823 3 1 1824 3 1 1825 3 1 1826 3 1 1827 3 1 1828 3 1 1829 3 1 1830 3 1 1831 3 1 1832 3 1 1833 3 1 1834 3 1 1835 3 1 1836 3 1 1837 3 1 1838 3 1 1839 3 1 1840 3 1 1841 3 1 1842 3 1 1843 3 1 1844 3 1 1845 3 1 1846 3 1 1847 3 1 1848 3 1 1849 3 1 1850 3 1 1851 3 1 1852 3 1 1853 3 1 1854 3 1 1855 3 1 1856 3 1 1857 3 1 1858 3 1 1859 3 1 1860 3 1 1861 3 1 1862 3 1 1863 3 1 1864 3 1 1865 3 1 1866 3 1 1867 3 1 1868 3 1 1869 3 1 1870 3 1 1871 3 1 1872 3 1 1873 3 1 1874 3 1 1875 3 1 1876 3 1 1877 3 1 1878 3 1 1879 3 1 1880 3 1 1881 3 1 1882 3 1 1883 3 1 1884 3 1 1885 3 1 1886 3 1 1887 3 1 1888 3 1 1889 3 1 1890 3 1 1891 3 1 1892 3 1 1893 3 1 1894 3 1 1895 3 1 1896 3 1 1897 3 1 1898 3 1 1899 3 1 1900 3 1 1901 3 1 1902 3 1 1903 3 1 1904 3 1 1905 3 1 1906 3 1 1907 3 1 1908 3 1 1909 3 1 1910 3 1 1911 3 1 1912 3 1 1913 3 1 1914 3 1 1915 3 1 1916 3 1 1917 3 1 1918 3 1 1919 3 1 1920 3 1 1921 3 1 1922 3 1 1923 3 1 1924 3 1 1925 3 1 1926 3 1 1927 3 1 1928 3 1 1929 3 1 1930 3 1 1931 3 1 1932 3 1 1933 3 1 1934 3 1 1935 3 1 1936 3 1 1937 3 1 1938 3 1 1939 3 1 1940 3 1 1941 3 1 1942 3 1 1943 3 1 1944 3 1 1945 3 1 1946 3 1 1947 3 1 1948 3 1 1949 3 1 1950 3 1 1951 3 1 1952 3 1 1953 3 1 1954 3 1 1955 3 1 1956 3 1 1957 3 1 1958 3 1 1959 3 1 1960 3 1 1961 3 1 1962 3 1 1963 3 1 1964 3 1 1965 3 1 1966 3 1 1967 3 1 1968 3 1 1969 3 1 1970 3 1 1971 3 1 1972 3 1 1973 3 1 1974 3 1 1975 3 1 1976 3 1 1977 3 1 1978 3 1 1979 3 1 1980 3 1 1981 3 1 1982 3 1 1983 3 1 1984 3 1 1985 3 1 1986 3 1 1987 3 1 1988 3 1 1989 3 1 1990 3 1 1991 3 1 1992 3 1 1993 3 1 1994 3 1 1995 3 1 1996 3 1 1997 3 1 1998 3 1 1999 3 1 2000 3