1000 5000 2 1 449066976 3 1 181704111 4 1 54693114 5 3 874190727 6 5 85446365 7 4 663572379 8 5 125636275 9 6 93704040 10 6 897023791 11 8 14207038 12 4 672366002 13 11 260710539 14 10 169301444 15 2 120127325 16 7 602253759 17 2 163904393 18 6 526526695 19 8 409869298 20 14 305989513 21 8 181447137 22 12 505658939 23 6 525603669 24 22 647961177 25 1 612160471 26 2 218144211 27 9 461913073 28 6 863708280 29 21 255547180 30 18 950267612 31 7 53168789 32 5 944811124 33 22 890387269 34 23 125579661 35 34 560606380 36 35 109757128 37 10 156941097 38 12 645199336 39 5 353748352 40 12 681483456 41 32 710207462 42 27 964695904 43 7 119909391 44 16 242710953 45 1 683331559 46 33 13369917 47 1 233013017 48 25 880185902 49 33 927782299 50 33 564458260 51 4 397123206 52 39 423083953 53 44 296372723 54 12 300284554 55 21 689055425 56 14 424114514 57 4 303275126 58 33 443503303 59 30 331809268 60 31 117575578 61 46 181790125 62 37 612840608 63 5 274761367 64 28 504137044 65 35 622617166 66 62 840442057 67 65 830246192 68 66 609518624 69 38 801771206 70 28 295326008 71 16 977478079 72 22 112232479 73 3 155609684 74 2 12993108 75 61 314922355 76 19 473354603 77 72 772090667 78 76 16641418 79 36 573609420 80 18 410719031 81 32 456490570 82 26 992333223 83 26 414868268 84 28 13062037 85 35 946225547 86 72 450471160 87 74 630771361 88 65 430936402 89 57 211578903 90 2 143288890 91 62 127391084 92 59 801707873 93 78 63199223 94 73 44115020 95 60 377886184 96 50 470719467 97 78 667912609 98 55 106313546 99 54 827549443 100 65 926729247 101 30 206619483 102 91 190160028 103 79 294056444 104 53 853773285 105 64 805872894 106 35 878536767 107 31 881842411 108 96 200925796 109 20 239845359 110 43 484931342 111 93 75645665 112 100 308454186 113 98 510318806 114 29 801807248 115 59 646387443 116 37 873441037 117 111 327168796 118 87 336558003 119 63 16636265 120 15 655399732 121 36 785227026 122 91 970878139 123 44 242361820 124 122 665155037 125 55 415629977 126 112 223766325 127 64 813079395 128 15 666164322 129 48 964626117 130 7 438864697 131 22 20243286 132 67 533348869 133 109 889178741 134 53 944806550 135 92 245208158 136 106 608603315 137 111 37281974 138 129 641538499 139 80 670012478 140 123 129910379 141 102 860722318 142 106 133697014 143 33 187554999 144 97 525120897 145 29 101306273 146 61 8175733 147 91 855975129 148 16 763858320 149 12 316262704 150 54 473769909 151 76 364415127 152 16 700347181 153 77 498826797 154 54 707700141 155 57 126554403 156 80 881269058 157 109 7461300 158 63 849430136 159 119 277145779 160 15 545940214 161 20 647218329 162 25 335873385 163 135 99261509 164 86 998558540 165 164 876205709 166 66 387946133 167 34 167289992 168 45 572319425 169 25 158917860 170 20 861206475 171 113 339536512 172 142 453905024 173 156 929139084 174 150 133248727 175 108 712139216 176 132 822115901 177 9 969311763 178 33 813869719 179 131 924078891 180 120 659446987 181 1 225103815 182 55 764149763 183 25 8804921 184 18 358084918 185 71 387014469 186 131 854714037 187 136 973455945 188 85 384986219 189 106 207363336 190 55 536975623 191 161 623158145 192 129 814382887 193 54 312669369 194 11 712774606 195 129 958521236 196 40 455720914 197 64 503859312 198 116 860988362 199 131 541474076 200 112 431132005 201 82 519976257 202 115 924834206 203 5 309936024 204 135 176521771 205 10 533091135 206 105 966750551 207 204 709141491 208 132 259913817 209 121 749788035 210 104 604755024 211 54 417794371 212 118 992082008 213 187 415478613 214 180 731778487 215 72 384353397 216 35 80918427 217 41 558898410 218 58 190485179 219 78 293175756 220 1 335237907 221 70 603698434 222 69 308503978 223 193 93949801 224 109 871491625 225 203 885385011 226 43 82683415 227 193 178006320 228 75 693272973 229 121 936416392 230 4 548169994 231 31 877349906 232 203 945119280 233 118 684979262 234 127 646211834 235 27 552222486 236 217 680267589 237 222 789601777 238 57 539498088 239 222 487789243 240 179 978072481 241 162 328286476 242 121 102475222 243 41 190376860 244 219 137756364 245 204 395044680 246 87 592520062 247 9 690939872 248 111 499057357 249 113 741388098 250 7 28978055 251 169 487819364 252 109 951917943 253 242 684684937 254 183 498823874 255 7 195279362 256 109 38371766 257 241 282089714 258 37 323202267 259 120 769857582 260 29 219239747 261 4 781212946 262 92 990158411 263 119 698218218 264 242 558486111 265 126 986791387 266 61 503355013 267 64 278027456 268 10 526792097 269 258 836826652 270 26 976338100 271 43 856614401 272 115 97699354 273 88 177801270 274 153 513276320 275 176 16160154 276 171 673038276 277 249 753250578 278 194 164812947 279 191 812118334 280 60 900712488 281 102 781696167 282 20 343365748 283 65 277269433 284 120 926518245 285 12 160173465 286 222 932235766 287 261 348995357 288 205 780001225 289 279 233390638 290 284 433180960 291 178 977421635 292 3 711714512 293 34 89529835 294 276 523961263 295 172 25455703 296 59 878453825 297 112 997258333 298 133 253257440 299 288 200214698 300 113 283365169 301 66 508793384 302 94 705388447 303 202 607336498 304 119 500458056 305 289 681765700 306 70 479831540 307 81 374369389 308 98 466878666 309 133 637250399 310 283 225139986 311 121 945514703 312 180 529039081 313 289 364549720 314 49 384652786 315 301 400189357 316 20 236186828 317 10 640837832 318 223 880804901 319 14 392983821 320 99 230426851 321 134 454553837 322 245 115036867 323 92 913894819 324 202 120039858 325 285 433570848 326 270 322403351 327 149 803883601 328 25 899749958 329 235 245126477 330 126 199731933 331 23 861153566 332 128 681719601 333 112 816459511 334 19 985628665 335 318 163578075 336 57 285308410 337 268 770416910 338 311 174470021 339 219 273280380 340 156 48833127 341 200 767664527 342 299 211008546 343 112 240595606 344 308 528204885 345 165 681133816 346 306 949563133 347 242 772312588 348 236 934808079 349 126 145575830 350 135 849280119 351 277 798970445 352 139 591196428 353 216 735816107 354 280 81331375 355 268 796137173 356 306 733712004 357 175 893748236 358 220 237566088 359 219 261712356 360 265 333452296 361 295 670137638 362 330 178676796 363 71 846486795 364 337 184984554 365 350 525661671 366 320 832624253 367 283 438011363 368 224 585106103 369 251 251034819 370 74 979997474 371 200 618423980 372 247 739320726 373 259 578558554 374 334 960221323 375 106 436661998 376 77 945092369 377 55 885110483 378 225 163536436 379 208 739949325 380 356 337491285 381 249 275440574 382 233 700869624 383 259 758782979 384 63 526944642 385 206 348449014 386 315 837250538 387 254 676144683 388 29 971980279 389 278 461246859 390 306 122914651 391 152 676195984 392 210 335352811 393 144 459565654 394 297 866933277 395 322 199605690 396 118 574873978 397 296 564391306 398 353 832567245 399 114 879462237 400 16 492904913 401 272 413356194 402 157 403087846 403 67 439156329 404 160 447776306 405 4 356995664 406 361 254093826 407 172 964523029 408 313 523778531 409 118 100906360 410 123 204129429 411 287 561674835 412 326 182945659 413 374 440950282 414 92 315709127 415 392 326537970 416 209 676576497 417 276 919587810 418 147 586425614 419 5 404178759 420 384 397992861 421 181 751391083 422 20 406655540 423 78 187295125 424 365 395476131 425 384 865617702 426 399 707412201 427 302 228560461 428 121 938606651 429 386 458420437 430 279 304351809 431 331 445379410 432 385 719740339 433 170 392891398 434 179 741327284 435 39 83278312 436 199 764928939 437 141 95311901 438 142 383989400 439 118 419319406 440 219 743241990 441 326 139026528 442 403 782536076 443 42 582946174 444 69 879471434 445 85 57263662 446 389 574887866 447 86 68456392 448 231 765603258 449 102 638994692 450 166 331697428 451 62 982832295 452 124 451502837 453 4 700059324 454 277 950386466 455 96 598891490 456 278 421045755 457 125 39097463 458 236 41909941 459 421 764712298 460 142 937822275 461 208 628269993 462 32 41606518 463 217 388917206 464 299 753531885 465 423 592203976 466 339 832330070 467 228 278350057 468 417 765151229 469 263 72345338 470 452 600609674 471 329 478449904 472 159 641097099 473 464 485432328 474 47 903366266 475 371 345991364 476 435 842680809 477 115 535089748 478 30 827807491 479 312 494288998 480 41 303786226 481 180 444387599 482 424 419392739 483 347 933767910 484 140 267912727 485 482 443203077 486 212 245038759 487 187 421068132 488 308 718706508 489 38 569794319 490 450 256888977 491 361 527957479 492 219 925587593 493 199 770848362 494 248 466188783 495 4 787842209 496 308 13128854 497 188 934756146 498 317 957887619 499 170 161621699 500 109 11038109 501 300 740567348 502 75 14076888 503 5 874600310 504 8 767380901 505 153 595179339 506 222 757493245 507 105 808794647 508 491 215441573 509 191 164965486 510 143 110535771 511 370 340850912 512 223 576816184 513 405 98948444 514 485 461327521 515 362 312291886 516 328 816054616 517 145 676229866 518 480 654205541 519 105 354753939 520 384 817600302 521 113 104315137 522 273 185204553 523 343 568715228 524 9 924296203 525 342 360751455 526 224 92531834 527 345 566534695 528 275 593989298 529 96 195040687 530 429 679117163 531 245 756801052 532 483 227274507 533 154 849018666 534 71 387956494 535 157 149694651 536 366 848730187 537 385 246710686 538 4 971330668 539 281 256720882 540 66 267810352 541 79 327076526 542 226 509819148 543 100 305136345 544 277 280028138 545 377 390892898 546 484 154429863 547 108 62072338 548 72 681657224 549 390 143082533 550 194 492821586 551 516 104870114 552 495 447487883 553 11 585278166 554 229 227152940 555 522 991638562 556 477 34258213 557 554 352382035 558 77 45870919 559 137 947769409 560 44 958487843 561 170 513282484 562 28 895721674 563 551 510207994 564 152 581131869 565 50 367558822 566 466 837601366 567 361 170247206 568 543 266012596 569 562 385566461 570 399 693099024 571 454 934035834 572 152 516095081 573 543 961286756 574 125 924432161 575 158 69477916 576 566 216838437 577 228 529289940 578 36 933963201 579 264 109290104 580 308 65036122 581 238 3421016 582 224 105853950 583 369 603920975 584 43 290079718 585 483 864068472 586 52 786144829 587 104 547472408 588 94 451422931 589 247 244451867 590 186 80438404 591 17 426462792 592 385 780405734 593 179 562941437 594 33 715594201 595 363 788016648 596 289 522889491 597 358 408468600 598 344 18786721 599 243 240532597 600 465 15459076 601 545 110101002 602 559 998999645 603 518 581066019 604 595 188781615 605 62 141739466 606 199 636192529 607 383 238106050 608 590 328497669 609 421 655290460 610 176 268633559 611 425 929815927 612 297 66579682 613 293 747802886 614 40 899381649 615 228 897442695 616 55 335130736 617 437 826102861 618 65 628071748 619 209 39822513 620 116 302035813 621 568 683408055 622 21 384235644 623 262 4909014 624 87 400643159 625 564 134759594 626 295 324151178 627 23 145931514 628 474 28337476 629 477 156042583 630 56 503835360 631 292 616793465 632 504 875447811 633 408 482926557 634 431 988742045 635 387 997346050 636 249 967521325 637 399 916068954 638 148 351099492 639 495 81246596 640 232 118669716 641 275 317688301 642 540 54582794 643 297 413043785 644 438 545281886 645 7 527691463 646 533 503381382 647 110 348295716 648 292 170600353 649 645 54830144 650 452 77097880 651 543 313885332 652 453 444008989 653 627 940145362 654 85 270014077 655 390 535313165 656 640 221002305 657 483 373400949 658 388 217846826 659 373 365758687 660 607 886248962 661 593 886352415 662 294 572045609 663 41 743442695 664 582 899989758 665 567 2790871 666 502 608190746 667 110 841047164 668 169 161891947 669 415 941033096 670 245 581726981 671 394 82414292 672 464 63019652 673 183 28341323 674 166 5820534 675 192 824414371 676 112 672400692 677 185 382065435 678 618 465102642 679 15 592512470 680 503 500267177 681 407 820717917 682 408 128437563 683 467 858609373 684 215 899011081 685 567 558405242 686 586 153868970 687 509 567211420 688 260 457897773 689 338 369845765 690 2 333271296 691 542 686354077 692 663 107646374 693 91 848660782 694 420 870355179 695 177 209485153 696 439 672494225 697 296 314385125 698 404 298714652 699 126 420279447 700 368 522900986 701 473 239170398 702 326 231692569 703 347 992932795 704 266 970341474 705 360 533364526 706 402 301667163 707 373 155551357 708 585 593553576 709 464 340599718 710 496 865102863 711 22 467499050 712 669 285435556 713 608 793632935 714 612 601426404 715 268 611509010 716 389 186672469 717 467 409087796 718 114 326081654 719 142 363394687 720 542 866036014 721 572 80364091 722 276 926544636 723 89 116996737 724 661 214067050 725 165 688977946 726 345 522741544 727 243 589698176 728 65 547842830 729 728 640371236 730 439 74354726 731 231 951185568 732 536 169665983 733 224 411784416 734 717 498755106 735 35 287533745 736 423 872372378 737 129 275352806 738 608 422015506 739 212 412924856 740 283 250700610 741 407 83922213 742 641 672353758 743 563 541140993 744 726 255595065 745 418 176039305 746 416 492300082 747 16 590316573 748 567 47532145 749 739 743028133 750 425 775179126 751 141 135553554 752 362 603530825 753 130 735216117 754 125 175620521 755 652 960232774 756 364 712665692 757 59 264507761 758 559 744489089 759 475 599675260 760 559 161440579 761 329 709668534 762 309 122006719 763 597 573441293 764 638 281463221 765 316 52161065 766 253 459659867 767 618 116168245 768 204 765090295 769 671 862226776 770 261 537427890 771 464 544248435 772 685 513642099 773 323 496121225 774 614 564740248 775 242 333050314 776 519 649370277 777 620 300738051 778 398 15410745 779 437 610035657 780 736 727145288 781 712 441737239 782 348 274969898 783 731 135121389 784 496 827100246 785 52 479794270 786 100 873982698 787 760 673772535 788 187 907237562 789 365 608638865 790 728 192004997 791 441 944465410 792 451 753353385 793 221 166003833 794 16 982686473 795 752 597631439 796 640 152384199 797 516 293600574 798 123 823975880 799 256 158892223 800 82 682946877 801 601 403084877 802 257 389023311 803 41 352635068 804 66 968013849 805 780 28942190 806 191 250052310 807 111 250555866 808 796 843774248 809 744 159139602 810 79 692237936 811 500 848415536 812 2 484920563 813 561 617832993 814 626 444699677 815 682 933709266 816 207 301619814 817 129 216310458 818 378 478473903 819 507 875833607 820 313 177320722 821 108 332857979 822 630 718264891 823 622 456117458 824 4 389671137 825 183 673414550 826 261 316470296 827 729 35977758 828 509 56871857 829 325 286227087 830 263 733472933 831 532 967253914 832 336 165532131 833 698 55831335 834 638 147882686 835 241 999458343 836 755 417131003 837 343 646357912 838 309 518155857 839 423 439568850 840 505 846506354 841 274 919282147 842 628 726264416 843 545 596642644 844 11 428838903 845 699 534471288 846 701 412579696 847 484 56536513 848 139 111961766 849 650 742832575 850 153 775657448 851 640 16327987 852 125 223575149 853 210 132770316 854 773 637892901 855 485 273373430 856 833 248025271 857 684 338466402 858 832 848303509 859 666 173220601 860 730 24678862 861 261 738636994 862 407 57851370 863 51 820718277 864 695 830471485 865 474 217053611 866 339 136595168 867 444 702816491 868 542 579736433 869 613 328737571 870 584 37310852 871 343 875261151 872 124 556063330 873 741 631619805 874 518 423181063 875 447 65137200 876 190 563630011 877 713 793245726 878 576 160407307 879 578 702320212 880 632 748411116 881 330 419603982 882 72 349647475 883 777 106538123 884 323 98031451 885 801 831420236 886 774 586444663 887 211 591356236 888 805 743895594 889 685 644344213 890 762 806147789 891 129 600433528 892 561 878747243 893 777 42636954 894 50 699880190 895 721 55479491 896 814 148371751 897 649 301196558 898 2 357921818 899 471 457792246 900 787 584225770 901 324 371463750 902 399 509931685 903 878 360161982 904 636 627588404 905 82 348663526 906 303 936388063 907 805 729381935 908 196 567410496 909 279 882246212 910 468 907373765 911 758 935040620 912 553 709830870 913 191 379792939 914 823 30466657 915 599 176108887 916 640 668686941 917 876 614810042 918 479 126493007 919 710 991619335 920 321 215067812 921 258 110853799 922 575 672016044 923 300 826914959 924 73 79059670 925 410 639979238 926 317 700760440 927 347 295065659 928 1 267338278 929 553 485427513 930 919 898165440 931 548 301642044 932 397 248006322 933 90 110899378 934 1 173292451 935 734 585883710 936 621 460328659 937 462 108904870 938 481 218940442 939 447 987897217 940 718 690534812 941 775 687862749 942 531 281633088 943 839 900084017 944 180 650724666 945 520 539781706 946 831 957635099 947 634 677207283 948 509 690136822 949 618 587990917 950 773 917295137 951 865 325061996 952 915 797511069 953 592 322917222 954 250 983430460 955 210 889498624 956 556 454642197 957 446 256247916 958 445 195629702 959 705 244713517 960 143 110591173 961 777 704506 962 11 976975143 963 900 128614496 964 333 518383285 965 391 317974594 966 534 41661081 967 582 208055985 968 78 657648218 969 879 338866591 970 215 909899732 971 530 558295022 972 102 462744548 973 694 27282533 974 402 365350069 975 686 937119531 976 211 424360455 977 404 300339456 978 621 744685004 979 564 750210555 980 733 468160483 981 618 334818051 982 719 703898337 983 709 908342108 984 47 593313571 985 849 695669422 986 523 272270034 987 50 661812067 988 243 502551488 989 299 238192261 990 360 670149316 991 121 869792684 992 337 666919378 993 731 664191840 994 496 870441684 995 208 198814919 996 955 965902677 997 339 912835767 998 345 905030440 999 651 509897774 1000 833 829728408 946 444 337598975 522 960 907887807 96 72 659919013 729 773 579902105 894 184 837408671 189 173 165339879 954 993 400988245 218 877 525862419 254 802 755018017 935 293 683774845 238 259 825138132 636 535 688369162 281 937 97090000 13 941 18175139 358 740 690788474 228 416 769134020 235 653 509753006 746 758 425887988 380 18 455985431 475 755 985624082 905 68 763696183 74 180 153778927 690 573 516226534 164 704 161815968 471 607 262471689 852 412 22549819 438 579 873822138 71 906 767270033 13 284 423960689 449 85 166742953 377 418 336432380 923 298 933267578 394 592 746100907 160 318 938871502 49 100 190078932 960 314 62036322 553 663 281800601 126 410 809362308 916 844 6925688 289 302 769009794 603 89 744371197 323 443 647540977 720 700 314603726 960 881 916828454 857 234 129015302 475 956 865941138 28 454 788236089 190 889 865827429 398 3 135875075 599 299 721138479 380 595 671310303 141 397 379043344 696 984 173929638 259 453 810037052 482 440 802468072 203 615 564255842 977 188 21656475 673 853 228601248 844 151 68644664 949 314 38209201 1000 296 234071210 751 376 531855048 235 830 437344576 289 942 864885317 484 163 686621422 175 860 735726547 214 75 976148708 970 718 351195954 469 415 543138807 385 241 11209692 205 948 870301800 229 937 556078627 909 163 227557834 145 829 571189393 36 207 781304320 404 232 726445979 886 30 879884143 993 28 526683448 605 62 521499340 877 428 741557229 500 593 736785842 966 232 271383624 924 455 141969236 362 641 159839383 460 569 629991967 139 961 301751035 423 212 112319208 822 769 232358847 401 487 672665188 931 571 310423614 761 450 875658637 184 224 2524840 182 130 585304334 580 415 978207698 772 388 80083683 255 292 263074104 390 154 707248545 684 445 809740990 981 859 958698291 687 530 881158857 65 436 537756432 182 415 468579266 399 335 723268736 989 952 235922583 159 656 53444655 848 322 472161325 666 796 299001304 400 484 311192889 797 647 124958685 53 526 287693810 545 791 637910819 796 456 758899614 11 212 557076550 981 691 743999199 777 689 669959119 637 573 497539311 360 949 68532859 679 269 371762182 325 529 491584064 613 795 136326204 866 352 478894213 987 442 167525360 978 329 453772079 828 124 92657202 506 471 764708946 961 600 691085909 647 694 564342075 958 251 582804973 860 883 598537578 842 339 735703667 65 476 384129715 973 312 426400248 826 33 372160093 134 632 776538625 587 973 880867719 178 75 249264972 539 481 21901867 396 713 186675119 573 685 763188751 737 297 445606191 495 41 313249260 931 838 839750665 658 908 382915070 16 201 789520076 538 348 792803918 400 380 885909261 464 251 436605516 258 649 875828395 636 392 236503216 835 432 646191016 385 231 398869054 253 885 636690675 565 481 398717709 415 622 167346527 257 187 259270214 95 747 629925166 743 78 923620348 143 111 548545109 723 108 200846637 464 167 478491748 8 942 855984538 892 917 810039987 647 800 932685094 333 372 206522022 564 964 3480697 39 70 819320148 167 961 398347748 287 824 161633626 893 287 187275243 157 490 815168963 644 689 369262046 972 472 387499119 993 141 245484591 328 917 161524475 892 802 871680702 313 797 667150287 635 122 211448210 730 47 396024013 949 973 121266706 84 401 959415644 255 202 320252980 372 984 724090035 789 402 852919570 480 12 885774303 294 624 829346089 856 397 623562918 296 574 46252632 236 687 504489027 733 551 365404744 58 155 278606881 568 761 175499023 814 586 993018715 349 72 600797598 715 716 846215827 968 387 489135528 89 922 410206895 165 490 811524225 572 308 867611467 351 520 570238006 603 533 896327298 976 127 906923726 475 879 705600163 257 408 152063693 781 242 981179475 846 759 313130835 330 71 955261232 607 197 544147448 930 681 332419711 61 817 910789795 281 745 327792312 591 54 849803210 516 293 568089595 981 613 720677345 197 324 410200348 837 720 563744342 419 984 624059233 209 771 930917607 169 429 520518144 297 384 487466540 200 250 73510380 567 947 38887978 784 44 986843692 173 225 380436742 740 329 574826168 737 58 295755219 337 3 84094880 308 123 479866178 938 60 81666583 429 569 497274814 659 900 533769448 616 306 418075118 109 593 980795393 765 732 288438776 381 720 933269327 846 427 63507673 254 931 363446391 978 20 811440878 456 73 646460784 576 505 332987175 532 405 710953545 757 704 135214063 587 162 575003120 898 165 570783742 114 901 666718582 202 252 233078711 348 608 948186739 211 867 760311928 132 772 632824905 182 671 981331151 266 354 976569636 595 944 618521414 316 449 632525692 396 563 877434488 806 44 148123914 839 891 719685225 680 335 520234730 231 143 325120747 75 574 611152571 203 319 23263991 895 755 648695250 174 797 715288511 872 709 465211545 632 387 13341008 495 323 285897634 952 301 476457881 38 622 465222386 320 671 976898491 589 861 613943677 610 89 311176036 7 526 304527398 388 488 949278897 288 562 493447914 273 647 122241030 441 606 873455029 395 409 51782780 188 742 135256300 991 67 672267722 262 333 626687381 949 812 766022046 865 775 998971377 29 394 163874335 75 470 429796980 570 955 737787823 166 671 663446535 440 3 721401070 198 190 568136102 5 245 642759784 958 532 963537531 149 45 731878093 724 859 484252366 375 105 178736404 929 88 236670208 405 537 104664658 496 264 61630924 597 421 479135735 89 256 268640325 542 479 447324279 261 432 103150500 141 90 131172051 471 288 779834784 884 185 526948961 236 306 466206859 856 369 971027697 197 960 776087214 994 982 409256134 364 75 962601622 651 505 597061960 241 306 428973896 558 91 13474738 377 395 265646910 702 499 636134630 872 419 412448645 992 540 630270643 707 627 75938983 848 564 26415528 781 313 221351563 123 49 368475000 473 953 730613868 473 467 223049333 721 361 96628397 63 791 100110536 685 358 815661656 174 758 464820888 426 458 558684082 55 244 207384431 193 197 958903278 131 531 242702279 49 400 687991211 377 429 701396589 814 299 748065711 185 526 143857078 746 86 370650486 527 698 780797863 538 421 569801607 657 731 657727786 734 402 783664380 658 342 8933564 799 272 180580525 407 495 477480415 710 941 825049898 339 419 469262467 830 548 185385724 371 302 902762635 963 212 304925708 450 991 42306662 370 554 990685598 77 170 934394353 293 199 215121930 245 977 306219807 204 462 950961931 663 255 476037117 843 605 80092759 533 382 934637600 694 151 792316957 448 128 190001096 898 77 4865883 799 486 330344935 668 347 493799113 452 845 194991831 779 389 98712911 528 218 776656590 541 320 95125713 394 303 265147543 917 302 568964812 866 333 733490065 146 100 852163827 7 875 792395718 922 459 421943328 495 845 562189024 615 647 598294497 479 567 144412465 767 812 506277679 159 438 649690431 407 548 850974079 843 587 162496183 313 369 429407793 331 53 211098358 812 555 701391760 756 381 92546645 629 668 801259128 6 324 261147609 363 922 894740825 959 941 386180235 905 590 244198803 244 747 375589632 266 323 286765947 173 809 367298593 550 49 710659272 953 991 100545218 345 621 490717356 113 16 355545991 625 387 514967370 639 500 396823031 525 92 243330012 844 62 320043560 533 274 278001938 88 155 104014920 590 59 57158015 826 453 969674932 602 223 325777920 494 124 599778808 659 367 716785135 151 756 981236632 329 665 846014309 152 428 465755868 259 643 901055595 585 222 968135629 886 479 916788488 579 428 58649787 961 125 254629798 582 272 849390341 178 896 540288082 131 211 280080597 128 769 368748413 35 618 287437553 36 611 987387566 629 834 543669726 12 192 844917456 199 527 221274480 305 727 726385514 46 789 163504511 611 369 63910158 156 316 735459484 45 369 371862298 657 335 610617688 636 619 755546335 618 118 746384067 137 671 885184395 515 959 173629955 501 310 943472680 178 635 954023271 191 584 955567943 961 293 7631137 384 408 359569506 760 851 538139891 763 114 955639021 597 841 406016238 557 731 245293784 190 96 79136562 210 125 875286903 382 59 680246457 173 87 983012122 969 431 759214337 306 586 48158995 458 11 743986603 273 620 409527792 399 74 300587733 590 757 862108517 122 540 169017380 359 425 409768063 533 641 543198752 470 421 391159697 661 968 882558420 519 302 357901604 282 822 515184540 137 829 132130685 85 757 102059780 857 926 97843722 355 43 316994488 101 547 936850501 285 854 186290349 796 624 366023246 450 579 624682680 158 388 799743007 656 553 137508435 642 982 583359005 704 192 514260051 667 233 963668322 665 3 725178615 242 76 844785118 860 827 811194577 966 857 180978066 411 432 607261985 629 426 931746297 311 777 735469427 569 564 298180818 494 998 94488193 87 431 427038907 464 94 34779122 845 1 881996330 977 902 531320150 933 490 298949036 437 849 794003192 646 615 745918287 887 108 931596730 845 1000 706114014 792 226 544960261 299 409 108204685 269 374 477767707 97 792 116418930 285 163 903841379 804 793 913441752 840 638 81669089 130 94 972592046 235 582 506378139 361 964 933220082 366 725 158683180 84 158 277808669 416 771 545298209 27 143 69120189 360 802 411778539 884 481 404764113 894 409 979696556 380 107 588876443 180 339 258227286 746 505 13145939 468 561 101431785 548 623 213486235 517 451 77750625 299 242 137908415 379 765 544457568 956 222 194503818 275 182 355045806 705 758 432163879 112 835 287915923 704 73 817459677 80 558 719009113 844 815 643384809 348 84 741734027 370 747 796430248 169 48 587625146 130 708 391924734 366 25 226427941 749 274 859923056 835 932 909357214 41 958 686566747 513 924 161397692 944 303 490630425 702 304 40864819 166 136 539291172 337 675 826475899 456 19 713367159 146 790 385397110 746 712 116230310 823 121 740306611 639 178 351363634 425 69 940425075 321 978 555677188 408 489 635460479 986 785 767784659 851 728 831970724 806 349 694049963 802 276 63468671 78 480 993415614 437 430 97940971 766 940 381845934 126 583 219593419 949 495 110491810 200 607 524470073 494 737 294502882 761 830 81892847 200 919 533501151 774 873 754299236 871 735 543158177 530 674 989436710 105 314 142077426 642 74 86517210 23 796 257352700 874 135 423854588 834 722 144006138 152 516 193183542 712 377 593713023 341 351 570989945 430 960 396802133 815 880 492799400 632 946 502914641 546 998 639671043 932 45 825529294 115 158 468555199 160 774 636411980 772 913 368235463 854 384 288591439 288 932 366653882 467 755 466729101 83 523 987735579 713 920 23152739 530 619 171440670 551 741 938454525 818 218 843411638 617 715 591834620 835 825 796167166 587 116 80630016 635 134 749972461 470 100 1115642 348 170 795458391 921 911 985333968 73 173 801367403 347 800 637179048 570 743 318256587 97 46 538862450 687 90 664854337 482 668 660719698 898 201 832216172 310 1000 107931397 256 561 853811584 637 692 69022769 647 626 420756756 819 354 708369005 956 704 635078952 903 351 811290717 506 536 959426172 931 290 387340965 758 459 265156657 959 730 766032646 37 514 327764514 435 407 399130005 875 403 300446911 335 705 878805572 730 979 598483197 538 550 308370520 966 146 916747574 661 992 948340010 788 516 594934883 804 796 523130762 21 373 975905547 950 923 138482909 663 104 295590033 236 906 777343307 808 493 1852884 197 136 543729431 415 741 764188596 645 528 403915644 652 65 538249818 110 282 56015281 147 994 396654018 64 69 212077171 566 868 677878260 363 444 962354888 592 870 573787914 500 123 137730401 747 34 638481349 561 643 154803986 912 97 434660867 79 87 743579955 529 908 650441475 358 911 577159004 625 476 79215343 28 325 413120823 807 620 796649886 693 947 927579950 216 727 865767594 122 321 86731093 532 434 415634455 849 611 804400895 701 376 805896961 873 985 16116388 690 431 257385576 1000 699 607987366 636 189 733474118 617 721 971594185 19 148 451992291 706 282 9147353 327 25 731091641 710 3 340456462 921 20 510576070 927 999 263605507 715 266 650685654 319 149 749021540 636 714 991670770 849 997 855525602 14 613 28982567 407 231 465558507 362 214 871047957 993 600 263015958 712 822 110217439 505 20 48401249 968 829 158694171 983 524 405570399 107 862 884792936 413 202 534262106 418 763 241678586 149 881 185790502 605 402 789348334 169 965 282905634 58 535 677959889 246 891 137030176 350 227 597148988 3 209 508537457 999 647 92383724 725 439 453348598 724 312 800675163 740 171 890410901 64 464 224682070 905 34 124270190 646 176 874929799 840 382 609963288 950 959 499433577 878 535 625015928 15 469 565482114 729 556 649758813 354 160 721453273 336 921 904471589 417 856 356522684 884 842 597238491 759 82 565388293 427 116 501806502 410 637 653089830 206 579 716446953 47 662 631081296 17 698 977294944 811 537 238119768 109 404 740835452 320 857 506255790 658 941 89964537 623 874 223252007 643 889 900969529 648 257 486265065 600 474 595006081 114 979 416676448 217 674 591682940 115 372 748683263 19 374 201327245 147 206 992526404 543 823 859443365 937 105 463281089 930 161 252726564 825 152 80272805 870 475 437322374 734 167 683295933 464 374 181405067 138 701 815267947 506 515 920411402 786 303 984252259 520 671 159442504 300 673 702486994 835 837 514748466 338 707 174084401 303 269 234322283 356 902 551966840 942 651 915192388 778 735 797353816 229 4 659603088 599 452 772165923 932 551 270285555 686 365 228035638 208 530 876330769 664 742 962588982 926 21 278387996 149 679 224637710 317 557 548431051 269 534 113544877 436 58 93170836 17 643 739537633 814 473 82698713 84 448 213573453 971 32 546268547 16 20 422784627 863 220 706876232 646 533 126056467 844 32 707408882 228 45 21210180 243 871 631847393 818 62 34986024 239 335 448910882 90 648 497495144 356 361 527483558 631 595 646024284 126 476 774558078 176 601 988874589 374 84 559708382 760 559 983107937 405 172 296362812 162 412 442398564 936 509 566821967 737 944 337049627 403 307 368468865 544 155 24814601 332 530 688188637 71 15 598007107 560 501 439214193 602 92 304853408 768 314 972488162 961 426 136845022 390 57 994637503 425 275 937529138 361 637 512771177 33 141 253395067 839 398 582327219 996 275 737403038 171 979 528464083 656 982 502677458 669 663 129859684 345 678 64218564 823 749 655186077 330 680 62783487 816 922 800101921 310 976 829660640 11 540 63630381 259 793 393198119 277 890 540609692 85 778 856400906 523 24 484853550 819 551 41798892 286 462 102386374 308 454 649420269 867 689 992839397 735 893 652510178 100 908 648830488 170 553 53738630 321 775 905477448 909 217 487389649 851 238 75724586 359 681 689853789 804 146 734531103 764 713 540350022 936 462 934710921 18 379 705938654 199 779 594752147 629 245 599504600 45 639 979679975 212 918 862164209 502 15 115745493 770 193 837748827 413 330 964209087 562 489 761785925 506 613 67008775 391 121 788279584 348 392 288128007 560 950 116785443 435 147 593659683 25 546 130894798 447 642 387441533 3 142 351805058 144 624 942145822 980 313 531653067 927 307 504959879 456 33 621724351 745 381 256105978 558 37 195979900 987 676 331152926 246 290 129349673 974 186 789695653 787 280 31134970 632 844 613002739 997 564 806132092 474 221 598608271 196 326 797096238 257 94 740648267 605 572 924048281 713 216 976174250 996 695 449495448 871 947 596857720 8 359 398013537 779 375 526445236 125 132 174189286 279 848 535004167 308 974 492211965 231 300 946692983 468 479 43386215 450 65 269540090 118 481 78026106 917 499 575091172 213 793 930603868 998 788 72166518 90 219 297025333 783 384 737778037 467 185 261553880 96 859 197970385 826 178 490583438 365 2 646228948 281 580 11724466 608 411 702598374 422 729 293414032 650 890 686611345 597 696 376640148 8 755 190327313 552 254 497523763 194 174 269528292 393 260 813558702 220 401 619193020 940 722 787332736 596 529 512501990 771 633 904232541 88 189 197778868 598 993 894994681 611 758 300650957 507 861 407585653 264 353 56932279 846 261 689102985 600 982 837483709 842 28 209814732 987 955 279411285 234 655 656747558 577 397 354173165 687 898 692228769 15 618 423898044 254 788 660896422 355 722 554187942 56 977 77416970 129 834 307864842 47 165 802845683 735 342 207722468 380 758 564523849 813 630 186906912 793 15 337315931 421 655 450219079 129 704 391262323 129 277 482355447 819 439 797351423 211 369 670045542 924 223 417311593 46 790 92879470 993 810 324419260 233 727 28276520 68 91 295173212 521 685 33237507 314 701 478711541 96 961 191085153 325 179 246611150 954 12 787110886 3 125 551710227 743 128 484131817 518 655 992962697 864 975 142738215 200 305 214132446 299 761 439349719 350 670 429825016 495 105 1207944 905 91 681051147 347 236 937995724 885 140 883595062 188 793 516004784 915 243 914698693 645 291 722563399 500 764 216470692 376 689 612175675 542 836 244245031 532 396 991848961 30 574 685962524 704 956 709384926 278 779 861198075 473 93 76082676 225 409 778929038 355 413 684892028 483 860 184193847 611 412 537244641 468 3 282955284 367 517 873110270 466 969 430053607 56 471 587343434 950 937 973587461 287 410 365882308 274 250 222251206 155 276 552236879 693 369 601934759 730 290 579323988 429 931 306558507 891 335 190328418 698 766 136019229 296 467 39855326 823 282 777438161 176 793 415965059 750 672 670710671 402 894 700702487 952 380 573025823 681 520 109688392 153 795 327312624 460 441 582914683 632 629 183065407 289 846 500641695 128 943 463119644 83 530 329855201 136 447 308161153 946 220 795060215 836 16 811093257 249 65 997503134 515 583 918807796 519 44 494337282 63 820 736898432 56 180 244023746 919 234 737179638 692 200 60034293 436 466 238124160 388 992 911975413 156 657 987568263 420 10 419964554 353 440 828275759 104 766 307284138 387 319 492611697 744 982 702477542 478 451 266237832 670 996 425583538 972 214 404109446 458 997 978783393 747 169 372054302 8 933 5488019 151 213 554616 382 952 909039 224 830 318791826 749 512 802013252 453 294 40110737 22 136 288544996 845 655 300054982 549 809 191410087 296 198 622479795 57 913 567484717 781 41 850506680 67 196 805025769 900 584 919285478 924 734 121456778 901 431 648197375 482 47 362172578 37 62 545937158 201 165 754915038 671 378 24928019 163 699 558214426 722 703 413858788 988 884 433932791 34 721 121223534 912 281 42259933 144 708 718194333 813 454 162698276 714 882 36639358 516 574 562464322 45 1000 92633957 970 73 279806242 739 23 453793623 117 424 443746592 521 297 874602273 532 10 951964950 653 601 772424501 1000 209 643525774 873 802 855423195 23 99 607053759 327 300 392572317 133 93 607213528 626 488 793805683 734 303 437484013 516 397 841910474 10 675 591167929 454 848 844901965 595 507 339359773 544 498 992627339 261 92 753083425 938 387 581295213 702 592 573468125 845 962 970153564 283 36 514707625 969 51 691291157 430 971 212849852 721 689 250502618 102 114 418557851 44 668 66518269 547 987 723264280 163 371 80902149 340 352 51421895 256 399 343802498 306 482 864577291 18 114 25567611 676 870 288484862 249 312 494793893 708 89 109345702 692 488 69935432 171 980 907297258 833 645 515163386 49 289 917370052 534 710 802386106 435 263 399328410 272 719 805742535 204 622 158212597 825 922 822867868 645 974 411293975 660 79 42681393 289 312 666278281 241 133 59034696 703 766 288886368 803 540 16418223 409 405 206749557 986 583 229993810 636 646 173031101 24 414 592233929 675 904 557314958 263 747 88050245 949 28 147422583 31 985 780841425 77 506 941275432 57 100 699291161 417 37 213120218 459 561 908966925 421 496 861634708 80 70 224478589 70 116 350791018 809 657 741819246 895 724 550921364 934 232 136494510 369 554 914306961 753 810 984052205 855 529 412010493 529 152 543001848 140 155 593582821 501 677 639057646 549 852 138881930 491 365 388237123 614 790 826843042 622 570 313865044 254 262 770989560 494 707 773021037 388 152 933782516 467 408 90971325 914 207 634149270 409 450 613521419 83 302 39135187 362 786 750622919 843 916 995842115 829 413 561941956 349 32 456950736 16 147 466728707 107 491 774305223 496 540 810771892 690 915 687073436 889 538 907794269 954 890 338159909 772 461 605053960 982 960 250396628 335 283 968975193 465 558 294067774 625 20 44335373 936 229 292111998 871 514 244784256 945 315 74945346 236 168 565424571 538 194 952216285 689 402 845028235 527 364 998603148 975 244 70872157 30 910 556128116 623 493 455228328 119 968 587963023 635 561 694950127 730 503 54324553 539 54 798952849 588 152 902429660 791 978 540220264 90 48 38879128 493 185 111950065 313 535 752045807 816 379 783499403 917 653 773094539 891 659 825451647 918 319 995315774 580 135 964446249 866 819 502754474 290 922 526021957 394 397 705040433 804 316 18678106 773 390 855660694 233 474 777573401 228 690 140614218 897 765 854608354 688 375 661364574 634 743 578861177 230 660 837568086 728 300 362500014 443 460 893519100 497 507 537407296 676 488 834256382 793 246 773322056 266 957 582189993 52 101 878022159 559 818 289349933 211 721 707274567 484 237 734416552 50 537 175291584 160 949 622585709 273 502 641506685 367 857 454321825 443 321 708610158 688 427 406201805 905 173 347414534 46 465 235181870 850 446 306958843 170 668 57827787 83 369 624458096 365 407 136550682 810 946 187167316 938 875 26613359 140 340 159693621 471 84 37852736 341 706 326339367 933 957 98980456 743 810 732993323 335 378 572458718 196 894 207230452 993 621 6164087 244 859 76566638 472 728 549875196 215 398 182405072 183 150 602025946 447 314 392451843 674 802 984553996 193 956 145055112 133 820 809790949 862 446 130015849 370 202 42854497 796 977 247765211 453 243 725384724 47 625 853950806 865 696 425149054 615 804 657143052 73 572 644292717 164 724 98214818 884 377 866323703 744 435 39835694 588 130 631398597 513 418 157372432 797 897 404006039 288 827 509348703 907 501 982395375 866 344 682198441 631 727 952499335 595 923 547801365 591 661 384585574 670 163 494029026 470 732 819919055 778 974 32140602 670 294 10768142 776 995 129880326 169 799 841104699 19 626 440439607 493 701 720776391 956 492 566497404 392 845 700307620 109 391 784154198 957 291 996024821 740 460 352626814 534 803 391236320 436 647 275802709 821 337 947846857 70 295 934068881 798 512 542776341 483 134 449676806 993 739 191252301 886 159 816600216 68 846 364082912 168 684 32191176 993 213 763700388 158 540 381649260 378 751 226654582 397 865 100265910 526 9 547060082 337 157 749561228 353 100 515576823 681 767 93764514 197 347 700370089 485 129 539424049 847 256 921391445 106 203 756501881 233 889 706145990 334 464 985542117 718 890 462763223 43 577 834682097 37 164 669556730 78 379 70599200 400 519 725920965 512 498 752388469 652 349 478642934 768 109 181646460 945 259 567035885 52 313 861490386 185 551 395304320 303 71 356307087 980 79 54876847 290 210 292652760 395 509 127616555 311 597 479154490 245 252 155899979 112 534 157311770 995 16 382711720 771 698 100923752 91 646 210860171 907 77 622865167 906 584 539209527 355 985 530346047 254 817 195296652 184 658 247992281 813 306 830019185 622 829 270447002 446 408 689782531 612 163 994338106 689 999 170212789 441 557 606913152 798 912 174336188 144 92 466250199 69 102 509512752 218 200 821589907 527 384 36975945 804 730 956464015 895 814 48701573 244 402 63235401 780 912 448790724 86 729 74805497 725 523 418393149 265 383 322914606 328 92 668373628 171 566 829369677 698 784 939801070 41 893 442290386 624 778 353232776 842 882 149026472 612 360 606758866 646 397 1135147 637 449 609447945 979 831 90782658 369 814 626785767 405 434 657688615 170 260 280016793 972 241 923766287 293 251 786879998 1000 612 370081671 267 439 732292018 466 328 304973269 547 890 132310152 631 172 283043338 598 875 890158945 884 515 658765839 375 31 585667008 66 778 902878768 675 399 428570505 40 915 640102477 114 353 676069640 96 999 587924925 131 638 591747731 578 384 616127797 24 957 43802802 775 710 617934834 552 508 681507149 633 489 783247988 919 54 123934835 849 597 507795935 536 833 872385604 439 755 573531468 974 253 9752034 438 842 415788546 515 89 989048006 899 432 40619018 468 797 96748917 48 797 604887696 974 106 750771882 184 896 985465339 104 976 984065990 921 665 644331602 398 819 246222093 914 846 412140630 873 838 123448330 69 971 741515670 624 643 192792900 616 696 418333566 93 412 513633841 565 660 122854016 534 944 281054544 625 70 7536025 305 230 687644818 174 620 845138474 688 238 516385090 56 952 544166227 202 764 764131442 177 95 782674851 820 186 480765971 189 738 966304627 449 12 181002927 693 526 174213863 851 722 655971449 113 981 269066712 804 353 565671180 748 491 406341378 424 80 538214856 458 328 629443819 497 269 29743325 640 718 912766880 1 945 284810963 28 946 440616995 533 837 248125327 517 651 135055915 378 897 803329257 739 852 715042883 384 723 771445085 443 108 894793461 713 882 135540165 912 444 693598833 471 515 450639035 428 430 287239522 599 977 709650147 109 822 167898701 535 617 487309414 415 651 439696866 884 543 531333822 238 100 473677923 308 932 518832303 380 445 210672534 551 701 539034661 823 652 61263518 726 19 905580294 988 498 598492921 592 57 613393835 444 173 779884571 836 221 531081570 815 807 384364744 144 64 847121585 270 580 328013460 156 900 352155592 821 869 902021886 770 307 233120702 636 451 569017199 200 412 924437060 794 571 750039223 255 207 784485370 575 302 237451670 30 469 444174014 716 83 603306794 973 94 470882206 924 37 304257056 955 101 355746249 551 928 532648657 416 886 196364683 128 641 28741184 500 181 776018124 359 218 134387159 265 174 74776901 445 681 68851369 518 108 969411321 871 980 440082976 118 363 779216678 758 958 588352605 376 21 903207271 893 313 875225605 119 634 363666060 825 500 92889084 329 475 240773358 641 72 282717909 783 445 508895067 774 497 705332648 15 687 337953944 694 118 633513831 915 578 227742931 569 910 202474953 395 515 25176966 217 599 415562957 469 371 717266106 250 447 502447830 349 192 566436638 62 534 123839685 258 118 809047646 153 516 856083229 931 760 798605496 31 866 577669835 122 973 137519836 834 863 747190324 722 554 67509219 995 28 596904891 843 662 329280131 200 499 283642619 794 227 274170516 459 933 575071524 89 862 41920552 741 853 225547095 701 287 867621791 297 381 430855888 462 963 638193357 179 718 366832380 421 245 44337544 260 748 882978049 520 5 792752715 177 302 520390871 276 793 124332037 719 407 221553808 848 618 939640740 810 493 771641991 939 90 96442356 924 938 440683677 604 224 927817903 866 277 50036573 234 612 214474124 938 375 636373128 914 255 925092225 345 59 162132603 539 861 543375772 804 740 420510903 331 171 950961084 410 866 734463766 817 19 437835108 946 123 756380255 157 962 569173049 657 291 915437402 553 808 903633566 99 636 231094379 593 280 724286054 958 401 850142060 998 277 434903337 202 513 275080744 13 95 776179789 698 37 282152056 678 317 637349683 462 569 737748866 53 967 357411905 815 291 538962638 759 237 147382719 273 326 948639540 851 244 504794444 726 24 861351827 253 147 763621726 213 486 865498357 205 290 876403214 921 943 479173919 592 148 134433946 824 479 589287094 159 666 986261684 303 85 594485546 443 141 370669752 997 465 346650111 605 860 812823225 918 17 953784022 288 750 409583445 991 371 911353486 689 577 612549033 691 661 396752684 341 649 870707814 376 351 385631286 803 174 591900072 413 779 906662902 805 813 314367948 967 359 381987105 309 264 817724180 264 461 610850227 896 612 989949379 720 347 782981436 345 382 406909626 699 832 802258821 895 788 931763395 737 720 497690251 307 769 867261331 587 262 287800202 469 609 10614769 695 958 350562904 448 230 300418504 321 326 357508583 685 720 462915147 198 753 20996906 699 908 122074482 275 361 622848288 443 770 345131966 647 318 271027524 570 550 857394444 222 876 87376040 137 28 196612562 482 185 742767140 915 927 223062599 500 575 885434241 389 603 317394569 393 281 177585005 139 804 868796816 741 416 950641552 326 935 707595683 845 620 175005926 691 496 756395529 14 199 685416687 482 326 773704010 903 293 331601312 844 467 468807591 9 520 717584034 556 251 82753890 619 188 971269466 19 601 87424216 802 42 699726905 32 45 34519052 271 497 124339217 297 204 400923738 716 15 588415551 695 731 156251040 482 238 666018324 896 715 580597142 668 66 356713882 710 270 931627581 387 738 260818629 425 53 869107853 508 151 587269397 549 232 383584588 820 707 489765924 793 571 389829672 979 971 429227365 465 826 405180391 440 735 230530481 497 533 949139648 638 30 83249689 792 815 626020812 53 552 82733220 873 150 838189748 974 136 392752013 234 100 887281336 890 486 41341279 136 29 741118762 733 911 658171542 826 605 84168023 84 492 124946825 716 346 992840160 399 166 228718761 200 334 881920297 857 952 218732426 990 854 617709585 472 20 937592398 691 900 778311672 381 874 732470912 966 718 65325337 476 949 8033840 42 279 87020997 287 944 47120539 840 140 454063855 979 48 575586480 486 870 214644047 52 683 225609541 621 762 648661313 171 111 300404542 499 129 201831858 577 648 581309178 274 408 364903297 176 24 711157885 577 605 190720422 98 630 143692700 815 860 366451588 754 64 638964679 10 748 715275524 691 404 90044969 707 907 27791242 76 667 934298406 384 723 6800276 714 234 205801422 526 451 836747554 360 298 949016694 297 942 990615707 680 868 783058864 684 121 994152235 931 401 167540150 644 580 353675519 14 114 417597997 389 556 2749661 767 824 291046695 714 130 133532032 281 571 686729171 397 455 597016051 443 198 633462092 47 913 519796777 686 731 938730156 56 152 84053538 658 374 731205831 352 31 756301821 841 120 733407586 676 357 440776143 71 194 939742812 1 781 424068295 273 938 31426072 530 353 69488301 805 375 648629019 669 519 364857629 803 794 860845871 531 452 683701899 905 687 134891652 251 217 225403072 731 194 185971057 80 602 911016071 712 956 165065772 653 52 968032769 728 554 769965250 751 334 933917375 643 125 803970002 847 157 62095783 905 817 132402102 740 622 432426516 850 448 555076807 139 528 218771595 255 33 229342775 849 50 837871889 292 699 443013642 257 638 626212349 503 243 729386529 939 56 448666510 939 911 771089347 878 164 976120065 583 475 48765059 850 34 141979469 975 453 562269314 275 71 179902082 423 335 40459445 171 838 36864453 703 471 321469587 622 510 61132759 300 162 228686972 105 134 452014327 640 288 290816297 2 331 81135855 620 641 436941678 263 403 768268584 233 334 378891053 134 163 419076453 137 915 41415150 405 33 825731132 119 46 244416520 727 371 817093802 608 972 481300313 373 418 471999061 931 790 793752849 672 11 670147486 910 836 831989858 974 38 512441246 355 162 558330648 528 352 19849370 178 810 705619824 462 112 10115949 873 874 926770559 173 630 343734036 792 934 914260356 487 208 252303391 679 367 903881392 504 788 46273830 90 172 236747107 900 740 876721823 957 150 73534400 974 560 252188044 919 112 414836654 49 612 551532401 986 698 513242919 129 770 476886709 239 189 685071703 847 325 908131091 205 480 917709894 462 775 292209078 978 40 41164807 294 824 995100022 465 41 308488898 423 155 699230903 899 83 787654456 884 646 228159754 589 642 259618470 734 201 140412525 356 604 531080526 697 247 457656269 290 130 888664452 684 959 418670779 963 10 85644277 506 479 512351801 225 62 960126464 689 595 541490637 57 91 156657660 63 945 468352906 441 365 611533735 814 353 678115451 233 458 919496668 168 374 279729408 904 791 692736404 203 164 667616044 124 965 536337252 909 83 903103858 621 172 510463004 85 16 405345938 504 642 831669254 89 68 722235300 968 222 982685509 575 671 346299205 94 432 104578778 53 593 474540405 248 291 890308909 858 136 712877196 715 182 709110390 191 742 306989957 342 155 171702368 584 1 167757728 816 994 716305078 601 669 299972266 715 732 85640578 77 384 256798657 31 209 481263070 923 243 465819790 479 287 834308452 130 741 937707698 179 842 442528053 894 867 755768192 682 231 192947283 389 815 541482410 220 755 237217378 444 665 500238312 860 159 380832608 578 37 769417999 531 897 178071808 76 162 24770322 747 837 746642532 237 895 364294964 415 913 582592003 329 717 468232393 907 489 757951885 225 733 267958275 518 309 838131627 376 602 434811008 135 449 793223672 231 348 752599738 180 923 468189835 431 186 738467587 878 633 598330574 545 385 347319061 872 619 504032650 344 476 229058395 490 477 879069899 814 561 400211002 304 313 845909730 447 576 445174178 476 832 798381626 659 258 677467546 324 946 653442975 210 106 227214148 131 798 342091780 43 466 161974282 731 178 521456420 440 391 882006006 312 639 271405469 73 247 230723968 627 852 790920122 683 53 626554132 327 143 844102843 889 156 155345207 816 85 723916796 700 209 845054510 451 888 36931429 154 333 176877055 471 362 215893096 913 322 855283694 879 386 477185574 507 911 200943193 978 1000 951253803 676 446 341379282 63 481 638746834 888 654 65073860 965 914 440119613 816 631 392327992 387 203 943614053 709 328 748623653 601 388 859168526 184 846 401491404 781 983 832133713 519 766 178733455 281 721 418362033 663 493 615205428 680 40 791855509 661 153 916481395 53 963 852549261 769 549 331129412 685 287 767412837 911 244 682746762 854 596 622174587 487 485 982736479 645 925 385257651 788 662 946682366 168 984 108483882 409 814 804470495 582 813 736352680 110 588 722696431 21 941 65031605 295 60 518735347 760 553 399694556 465 204 495835082 27 76 124791848 684 689 831105639 860 459 728362865 948 757 885701118 735 990 111045821 502 143 199957566 596 360 197545785 545 930 611313471 805 484 193471025 126 844 799117129 575 290 598811426 323 402 645468672 249 725 340364883 438 527 354090260 872 635 163455935 575 277 374428857 584 400 113425894 76 95 919362786 484 709 521373118 412 85 586796564 108 293 241849766 536 825 643402362 236 454 937638407 367 483 627868578 143 806 833899082 309 35 932898009 90 839 974842487 930 621 848302825 771 627 123831023 603 658 200558954 662 293 463794080 881 393 285072990 154 665 229636276 140 220 165034773 902 60 421313395 245 567 763261700 753 79 583804518 206 560 77010410 723 58 245196388 616 985 115067360 114 182 695298168 257 897 564835462 31 501 46786071 215 803 434198828 834 309 725335025 574 537 342436642 390 611 336451159 540 364 198492740 814 128 760358114 692 684 440689636 664 486 747184168 90 36 279586031 749 180 563130742 377 205 493416102 716 573 448519043 443 301 662268181 516 125 135458107 135 778 897291725 315 141 848049606 748 192 523596079 67 255 460376683 921 634 314707032 966 175 96153206 762 352 643008190 247 81 186936927 288 687 981212531 570 816 647663331 515 353 812182501 550 561 848192586 378 631 937506600 808 47 807391284 304 38 510623891 292 53 856409085 475 75 498793450 252 10 979826035 910 302 47399270 818 257 228634054 692 978 713362324 343 184 465058934 708 270 217327674 483 665 754440908 491 441 978086790 90 149 908918541 79 169 311836178 741 905 139411678 862 776 200414982 48 529 6553077 420 710 164797043 20 611 533446573 81 953 132942919 228 78 567146724 714 855 461369396 864 683 334511517 233 374 943361198 914 199 250904099 789 666 741537146 366 484 375276540 103 983 954068370 47 507 335104887 988 561 172601036 231 390 153460356 549 205 125767551 173 675 276561101 675 391 395677458 938 947 494369991 805 389 949663911 822 419 500512532 490 39 472769721 262 418 954554220 981 714 952639377 790 166 440349669 197 401 216486243 125 743 656137030 699 742 422474905 964 648 585643321 828 702 893333030 965 496 839844719 836 292 965719556 451 305 85114569 892 582 91071341 20 163 746309798 457 918 445994981 216 211 1304053 167 161 325619257 513 458 559820480 754 532 798222004 167 360 806679806 352 305 47828091 972 368 291341571 141 282 276249602 698 716 762755798 705 801 102273939 955 768 29947036 715 201 417341104 148 33 451662199 384 642 748618876 44 935 897465514 253 988 17856375 475 129 76288502 879 261 18986228 396 2 980812629 909 446 438136386 417 763 326677720 991 39 877947232 247 101 345891018 345 721 990357851 205 884 913612707 584 226 43073075 331 604 238386023 482 313 928599869 463 711 594338339 206 895 885993202 534 415 795759816 620 151 127267383 157 481 712966079 403 501 966640417 202 216 654411121 277 381 270908416 563 626 531279217 651 972 494397395 63 273 440026664 922 712 898640163 61 55 172303262 67 604 353816624 966 347 290774951 818 493 892929897 930 998 174112376 149 482 756828076 349 321 195730725 399 106 355812120 640 153 995789045 319 574 953246017 353 637 144446541 773 76 504091512 681 235 907063745 419 166 928132541 7 555 966657351 170 77 948944897 182 320 275434037 36 110 507490011 396 558 553234362 440 903 946806705 583 330 622265787 923 331 207382928 108 732 507700491 506 930 810543805 711 174 543983793 73 271 471711935 898 862 211661632 100 632 958820113 484 212 657242044 748 484 49356915 425 402 178937977 6 499 864292819 687 153 755988495 173 791 831073673 45 432 571051540 855 875 671984196 137 807 190985106 785 870 663124086 302 25 936955274 482 356 453185658 378 754 114502648 481 394 920675834 421 794 479670937 141 793 773469590 712 802 336790136 90 305 67672521 343 693 232839553 784 812 707712248 550 138 346660729 112 848 918936910 183 207 875530113 516 793 704847084 657 992 743497898 262 562 291221503 577 361 46266407 712 53 65932788 125 828 247307374 92 862 998368412 309 636 498272311 217 335 510751212 226 907 484845791 290 55 449450797 864 908 505945082 791 539 799719879 886 455 378090962 14 427 800753473 273 245 315246178 651 664 702029169 269 781 347262495 566 883 220066716 641 265 715263448 287 687 16718315 965 979 99439294 640 945 890137318 410 648 26414084 794 265 482293044 548 281 585284921 975 802 715306727 960 892 942149833 310 92 499889014 110 879 848885389 801 577 896436974 209 967 880954178 691 893 358514620 776 827 305297970 466 528 726669290 581 397 554911361 26 938 658816322 888 86 990944506 655 889 998841324 948 395 895690353 842 710 226812608 329 318 703097558 102 214 30268697 853 919 789561674 904 761 472945067 455 7 941244415 566 817 16999216 338 89 418763160 795 6 601343638 480 361 588022736 983 745 661112389 606 819 168492386 946 153 279516778 603 484 522084166 401 974 12826133 379 994 893664882 352 237 207860319 347 295 165890665 51 296 672389647 227 52 700457836 982 620 350360299 662 467 857238192 135 993 828324657 814 534 140610516 8 807 906347499 810 311 214992111 282 435 171972980 26 559 392837693 652 40 876028418 344 364 228203828 442 863 660031700 119 733 556559374 300 949 189389371 306 109 394275234 465 194 858333373 644 17 399900879 672 803 186791624 707 792 641831696 561 488 881670501 392 124 343703118 551 560 538685808 679 348 661028639 463 978 119727178 164 597 705444089 848 978 35635471 509 911 192326822 780 412 298213539 171 499 809725951 345 377 839146459 612 115 119982415 206 109 602175344 329 687 85151403 946 334 943510446 43 459 859264592 181 431 465982215 418 441 713593903 217 313 96627544 130 523 33322561 965 829 592107740 769 703 470569914 700 558 373070513 402 747 140895615 584 593 444108235 392 447 721127567 140 633 38761373 951 870 857074026 589 659 556088647 254 16 545414937 20 704 106984849 311 791 999959611 317 857 958762418 743 682 333997080 8 37 283421714 581 846 397746036 805 313 790171776 350 410 39060511 704 107 764117329 377 444 247937728 272 861 375649353 147 581 150262614 535 343 320940454 934 29 475404782 203 502 413596910 8 16 933422637 234 242 527208601 60 45 215892283 336 966 568198594 207 338 325795135 967 345 108784243 248 370 882391186 51 594 585902401 711 658 120147196 729 424 569961597 135 653 619323616 306 52 202496966 42 966 1443075 536 549 420664433 44 207 83484673 218 16 789481265 703 77 189965359 943 273 750248709 297 880 261102145 362 816 470309941 657 237 354012802 358 76 628892669 986 587 927765527 353 637 135934922 324 589 57927423 161 415 483511372 834 107 598350054 764 90 624235872 273 33 753506236 186 724 972140368 899 962 28327558 664 740 739901106 488 846 210934466 632 832 248524679 375 519 543840410 949 679 145849413 742 399 136364662 680 865 1590008 690 593 189871416 936 538 633133196 170 43 872621947 437 30 364403651 893 798 618754923 775 888 665052835 342 209 751031606 466 30 856236015 181 226 854776571 241 149 475267876 381 634 810865442 786 518 240192059 383 274 108123316 616 866 383185499 600 530 820898258 248 643 829762662 860 333 756234112 577 773 784366600 447 982 52148128 852 916 125981289 724 82 92296073 979 736 298788770 758 617 573474463 973 403 985344694 417 757 213459030 431 833 590352104 242 765 469151933 352 934 149443694 628 171 455584592 719 20 480308293 929 893 373456190 832 699 726243713 632 108 689394607 624 359 225892167 579 520 126906460 627 850 469943747 573 993 495587390 479 247 206665813 519 738 85341953 788 913 611911273 758 179 970738007 967 449 34867658 462 423 409925302 783 509 318816805 588 627 82569917 48 442 455533836 654 837 250574051 720 142 803849356 242 341 904014572 817 860 15281173 880 973 921346736 59 21 79557002 824 488 787584446 122 190 882327377 370 361 33606266 728 875 228875883 124 353 945042250 45 693 678868426 399 610 259275509 406 187 223610468 507 7 302943410 508 549 111275252 125 95 995639436 644 634 567360209 153 89 216435861 276 369 439629530 759 724 399005716 726 641 428395121 153 923 632469781 63 189 833361713 613 783 71698873 21 847 392545929 295 792 455050058 840 800 488012448 8 498 629477475 971 853 131727434 748 224 977309194 112 418 217210949 545 812 780164496 780 152 809689212 235 812 764677632 354 777 57796989 757 200 515074092 79 997 618690607 211 737 842474841 388 389 913373748 511 20 6853231 48 681 794701383 32 264 23311574 672 882 805900175 869 743 876459238 424 561 915312782 631 606 383535062 47 45 687101988 475 625 173122105 115 49 481109722 614 133 647750643 834 27 476534335 653 569 121182656 18 410 788621678 686 367 944975592 243 982 902217072 173 167 188802953 736 70 746186283 249 977 470171796 709 497 854519220 167 521 712599207 417 350 619807103 361 810 528785463 899 562 466035049 309 900 975414003 977 902 783759869 596 217 540273274 594 359 578541746 990 113 210255984 825 917 830964071 127 470 305234628 19 600 862179393 890 583 358321635 582 979 35445106 993 757 997107209 445 61 544224307 946 386 776974523 956 378 845499314 285 339 628708160 415 809 89416080 689 849 907701583 90 79 943567381 121 341 337878718 48 176 36026027 75 845 562322769 560 181 421016680 4 399 300924152 520 412 254077261 97 81 386132614 383 474 699006537 507 638 562180159 313 978 191718345 592 780 450543606 711 365 152802509 955 491 987334079 95 187 28823736 752 406 321220494 987 3 248547581 950 953 564383285 361 574 312913864 759 452 941904733 8 369 937214919 428 45 580145760 528 50 480493170 920 518 945794264 857 330 176338008 771 874 639359789 58 647 82954383 413 13 772666771 876 874 70876668 11 17 32512684 228 849 42529223 554 546 436303426 771 528 930761515 736 294 932596643 799 137 369138393 46 606 172289195 350 870 543547153 817 747 93108019 53 961 779538586 826 154 171097575 456 55 230924258 732 458 240463720 226 306 71139735 754 510 891385807 455 58 10347999 999 712 613434473 433 89 746441042 88 1 132275515 777 56 387991626 663 494 21964293 10 963 923702794 120 578 592249564 978 767 546255452 666 673 377576300 564 719 106302767 567 476 991805257 736 773 245881093 540 581 804695047 721 369 394494775 136 856 642909648 129 106 182783403 79 801 329818259 459 120 583040150 596 683 326532942 512 869 806034885 602 707 228522433 821 449 344899071 955 45 146226411 753 696 549947515 489 910 629017589 244 1000 911058675 785 717 787477204 176 91 214458438 570 637 915554191 250 152 253006278 548 982 96645989 579 20 642936376 882 800 95582482 767 894 817860922 238 865 727022153 741 454 23925880 245 239 266323016 818 14 19155991 571 983 788951821 221 998 321688652 430 486 691486179 398 410 260270928 563 357 117359366 189 644 917704169 332 563 763210316 699 729 913078126 162 692 352985971 437 71 605160949 552 860 965397412 875 918 756204403 22 791 96388875 244 259 98954924 820 160 128638384 139 213 987443047 223 232 526402710 460 425 855527098 796 748 529847204 609 662 861192793 123 414 302315738 408 864 279590185 406 943 689502066 249 770 81227639 629 928 980910828 144 151 883919981 785 118 423122887 388 976 680848844 625 948 508994320 574 689 955529911 59 121 291883894 784 213 261383713 176 657 249803150 441 861 578736768 598 854 986694380 105 884 745326792 103 994 858200342 283 643 265027752 679 638 642187178 310 432 437392821 876 767 708677145 433 420 575159199 241 366 480716769 366 588 154507743 127 64 351107853 480 326 90268464 611 118 338731111 415 245 472188516 897 705 955315078 627 532 576062907 991 581 859190705 611 687 490037323 622 795 787073912 987 859 530464030 130 314 295800425 420 364 548173575 300 52 405025993 707 7 949987171 888 599 689009181 403 11 352138399 596 18 33716883 174 891 220583302 927 906 152666253 29 122 736939719 568 603 16434725 116 674 557161559 415 68 746597714 730 529 841274815 745 170 248395763 811 781 177714356 895 249 770298993 431 16 556489638 562 491 215225878 373 460 954690536 721 819 946064841 744 309 288587309 779 973 335546316 45 861 930486274 221 33 696951939 610 639 695399554 147 840 804437772 230 197 624463564 324 462 209276966 978 811 968733054 416 51 570491351 620 681 804868886 286 669 935841518 437 772 558991136 91 9 78388769 872 805 388856011 273 5 517843198 348 399 799775172 896 456 944078474 641 790 49105345 982 552 116530425 475 402 682320262 947 627 19749916 985 549 687409754 729 948 807871310 447 821 837890638 300 160 705277105 484 742 408985229 816 804 538350128 334 77 222170881 725 943 92352910 560 725 106766946 448 963 680139323 479 276 917173111 115 149 998774526 532 438 755102207 453 783 394468318 184 459 709690733 337 420 151151247 187 554 979166277 184 693 3462550 892 274 572516504 675 313 785210895 957 24 54792390 741 360 946869672 955 618 505622294 867 920 150581471 487 29 507462113 99 469 508534254 815 576 272607503 293 400 529217520 896 653 392377736 102 402 715222492 350 778 443455744 722 390 454669150 49 193 987925981 299 497 409904891 16 698 21055877 370 637 711207827 411 158 966045655 860 327 791085813 917 73 929859160 781 772 548713735 530 981 204478521 965 886 643095784 419 441 278310717 512 708 393927785 637 694 458183721 209 756 907622103 995 919 671728173 763 166 976413433 890 562 528965804 927 177 644157086 613 380 211558166 877 761 585813450 147 709 482343191 843 138 830247687 195 499 90003769 423 543 884657973 74 210 471054124 327 241 226252782 743 729 277304144 308 118 162067924 846 250 390244208 331 152 752314854 28 511 408242505 755 442 533040944 383 731 961533887 34 228 45407446 574 824 482477872 947 77 17844562 434 546 404031627 145 293 510460759 550 695 756232234 770 752 467306701 183 1000 643614840 128 652 185601159 876 974 991382102 430 994 971466442 770 365 574307706 327 285 429954682 144 880 29592026 765 845 341840463 305 769 550835773 54 709 411838819 791 842 130244774 83 119 397705039 872 885 607066074 817 507 468344832 360 921 653209578 292 701 606943403 567 233 138434083 869 606 638580464 112 393 116026272 308 436 31127285 79 288 546605726 90 85 679726462 481 530 119922097 736 617 595768185 311 856 284287705 759 44 965828985 820 479 152725905 924 395 141376094 231 2 148775262 730 376 453172147 761 814 29182439 412 214 80897375 162 694 979486675 952 179 800136603 498 219 268848491 194 519 806868929 537 276 884706409 423 727 570353433 71 64 535940189 91 334 633905191 6 676 27160752 999 251 478789093 556 319 870281953 419 204 890520269 447 600 708385175 601 353 843623290 335 558 179502617 478 632 626334295 730 616 947901448 557 818 457770517 111 876 835865864 34 784 965000165 211 669 457659779 150 1000 352667918 400 378 53833765 754 683 739524062 517 713 54968892 497 228 772719700 24 129 928314976 536 811 917738112 522 702 240553596 298 275 786649744 345 853 346482966 770 7 380331716 139 676 407669335 116 930 276977715 24 77 782572623 63 923 191751714 257 188 397154927 576 12 420856033 986 228 13420722 716 143 557665213 93 776 441273295 754 486 632339810 498 590 580593441 458 261 83231709 912 604 543261713 866 742 751441028 316 992 385882612 245 710 238835380 777 474 770728405 790 1 939056892 858 989 839653881 149 860 284752589 713 620 628323181 136 832 4517236 186 715 213780434 669 379 806606269 478 495 751283178 82 269 816889984 262 653 696906250 48 728 727258961 873 583 840093183 528 822 542157836 413 568 464350659 684 796 686142118 661 458 657732518 803 559 726442478 201 577 882192683 542 741 617087268 319 774 160496172 377 227 634914933 773 283 401568281 928 382 390184074 805 333 915098263 862 487 888589978 647 301 94221214 771 450 248318820 318 389 90836715 892 717 502605127 151 693 51966090 606 941 695153864 687 36 799891739 486 388 103851944 282 74 406532648 776 505 356738079 552 226 810081836 238 318 220520833 433 747 609769878 731 811 578849981 69 289 775134584 138 306 21818751 493 150 851480464 241 319 691649307 653 826 370482809 885 790 275413258 886 498 625547849 532 396 935801574 946 791 19151531 638 759 911754593 176 604 499302330 347 737 732236193 807 21 396149191 972 685 924235844 720 448 426242360 446 235 277154160 842 445 256636045 570 121 390205243 633 796 834190332 467 595 345320812 582 259 361792561 199 555 197414877 469 937 271877844 571 543 216657241 813 650 185663649 502 694 451313412 6 777 597667983 675 953 773410248 574 773 777427180 461 277 243064303 813 564 733877305 671 495 532715595 833 95 817280521 631 556 377792346 751 292 80846380 205 730 877438320 613 634 486374579 681 357 891899628 541 667 122135761 724 831 25596801 800 644 184020789 782 584 428974037 849 217 758751062 446 920 363583721 768 585 453426358 710 918 555535863 595 787 16780 343 936 393022360 110 327 233038724 295 563 542516575 889 812 690228705 726 826 169016854 428 197 655523098 567 52 910393543 561 115 460411736 513 10 369627146 821 525 133167790 734 383 986971199 759 689 384870799 51 939 235336823 168 190 241427701 743 179 280590557 271 260 522218072 548 230 341380562 166 438 913050966 102 135 988046819 497 549 648018715 981 231 875357701 420 161 627354346 341 735 663203029 861 67 223016465 544 730 493305389 46 672 40999246 492 301 113248773 458 805 243590020 693 867 887296738 593 838 806026830 641 747 116292327 807 239 412894739 713 905 642794033 188 74 456778360 424 98 117863944 407 377 309760616 271 665 793679245 370 898 898037109 178 497 241085098 810 954 53214118 525 304 792366427 3 306 384042440 501 681 889701082 604 353 662894740 142 762 847060138 430 17 154013681 549 32 167535915 399 990 581764456 966 708 972168631 504 576 903134430 561 78 807459237 65 66 637957236 97 464 182693657 73 26 806156395 673 213 938648411 858 691 20788343 416 937 113903948 384 420 726401932 778 143 823787647 271 988 918884861 323 102 770662156 394 460 911505747 592 11 331331246 640 16 115077561 412 765 451581192 60 950 859774330 125 801 936595080 167 397 675738059 9 843 916318983 395 415 452186832 417 319 272413471 716 564 890295763 529 581 224796170 458 579 212416079 883 667 544460994 488 395 626707916 639 819 448152875 843 924 144404638 414 264 284266834 355 640 562013452 25 517 88773220 346 779 656000935 595 361 357809560 670 66 229243041 913 31 560927708 136 352 90491754 527 492 48958498 779 578 949053328 56 404 915907280 933 262 230682775 921 575 906517234 862 467 865090366 193 286 256038753 770 662 786432396 950 786 196047929 931 215 282428862 38 800 975265728 84 834 148248717 19 56 548316606 922 808 60148201 852 552 96025939 151 319 69019883 443 134 601956107 283 132 858589674 280 506 78625839 694 624 147516466 62 224 666797627 12 134 232444253 785 990 933040958 303 296 693623327 559 684 630088476 944 283 669570098 51 351 342993036 196 459 565650826 471 545 546446000 38 293 638071211 674 270 258705152 682 604 218822185 939 303 37946529 991 925 154129316 628 875 203443870 749 555 169700522 599 528 61810318 727 484 569579511 963 733 309552253 544 298 440899872 887 410 659425499 579 689 449655324 420 643 437240885 497 34 924856980 526 903 462815878 263 850 211284138 117 730 775707319 483 817 387439949 3 162 431409252 726 431 971679852 272 62 192626580 374 243 217777186 657 890 712620041 388 501 983128803 298 390 144413653 382 283 935963263 747 65 518541602 890 938 889126847 27 131 243731952 865 716 201066253 795 16 270844942 123 239 69099699 634 524 262856637 437 715 529765562 272 821 324661413 617 377 352735213 973 673 88209081 994 1 627549095 596 145 191541917 673 225 143271852 31 723 707918305 952 644 994276375 567 890 967175717 337 877 295140825 695 549 247870646 678 396 662609615 21 758 128177893 310 516 282958286 286 580 46107827 197 64 101132504 775 417 453375323 842 463 192973662 916 570 585344404 972 78 946744002 711 183 795509919 613 343 540236040 589 925 861993710 552 977 633205645 918 567 7067492 83 345 947630317 137 494 331089154 745 687 217372783 800 216 790216519 276 638 811271126 85 447 14506950 398 703 634803534 879 202 38810833 35 311 671568265 493 890 193048843 56 449 223691710 982 773 719050727 479 338 827287952 562 676 453486835 211 336 525180466 879 560 479806634 337 858 691171135 804 291 522037350 461 981 83277021 424 648 126533489 390 18 929809079 161 392 935482895 797 872 456267486 10 317 507876401 228 896 391030599 441 137 541621038 582 928 251307262 164 340 731870832 775 664 2860140 667 327 148504154 775 990 321214156 77 524 357394364 984 190 694994738 795 962 280196921 387 926 33435286 744 196 440006297 225 250 195749214 426 234 885541449 521 89 554287779 105 679 865381152 119 974 218112057 323 728 523193764 887 516 628118448 505 840 462430331 941 934 358411442 89 307 218130617 538 989 229374307 339 468 32445102 886 710 158595734 857 227 271685367 925 729 384908923 271 444 695095210 993 25 498536442 426 855 453713206 14 918 62853849 42 562 766987193 654 938 854360263 345 478 389573810 472 344 893503832 734 773 941785486 385 276 527128563 607 962 66713787 466 788 48850900 825 127 745404024 85 948 781509167 804 992 526500353 919 327 195458694 496 87 18928679 17 922 655418332 623 793 161273481 49 410 3845288 548 343 945712772 831 981 491130637 857 399 483643456 301 223 326510743 962 940 873828781 252 471 915147420 890 751 53038805 805 652 761659637 589 702 51371790 996 998 785493332 766 508 439160713 120 180 813460823 642 201 882513869 998 537 503767491 365 338 543471883 107 89 990958486 76 890 799294356 865 333 298776248 151 140 711768560 92 880 609374605 478 780 691864539 324 423 752859094 16 487 942800150 45 569 449626088 257 794 637461861 453 53 102771246 7 673 891820425 702 256 558681737 872 376 212269238 185 791 227700590 163 97 582072167 440 346 913743463 602 314 808652730 549 775 667584736 713 759 769651148 933 891 322211735 383 377 238351910 151 266 449048277 99 239 319772686 279 315 648056997 203 480 473319128 220 844 840204333 497 63 836018273 270 466 235863633 961 47 985442319 258 818 722017649 491 86 598276797 853 136 150782469 135 768 326813072 761 143 124399618 395 938 286936053 418 336 14165000 157 946 557211178 935 305 389584054 340 854 224972123 257 46 760069891 269 140 971388546 397 653 180088320 347 294 454191526 350 431 333711290 662 818 841264679 649 589 15628520 473 86 20064819 108 291 831831787 545 480 177464888 126 339 984543124 387 244 613225555 599 868 734905019 138 676 902769927 499 424 50064628 996 411 590410174 72 55 847126253 982 972 256958388 616 347 62917108 69 972 7476451 884 419 226000440 352 62 136073683 536 438 680185722 74 897 997082941 214 572 876988587 940 951 474378163 377 973 485493747 429 320 908070805 686 866 981733458 659 27 869774873 540 180 373262360 820 831 402315212 155 972 977717484 15 130 755049934 136 260 387338579 668 785 98260137 839 902 724971991 499 377 445748885 9 932 943469693 550 458 377887909 162 560 837052980 220 361 434991240 413 979 960932107 571 796 266199478 197 560 59112132 887 918 475555866 990 464 649121717 487 512 933690115 331 726 315260955 455 968 254585767 351 722 405281790 97 421 245556198 287 521 54327543 696 669 495427824 93 698 655123685 723 216 723749653 308 694 916572476 277 905 621222217 131 524 991523129 211 167 116272429 142 159 312800000 947 371 679584803 114 499 163366181 783 932 491288921 276 116 557761309 666 636 956569239 841 978 560023276 918 235 394445451 696 184 866425910 817 209 828365486 478 551 438431982 425 777 525896490 825 368 673785001 477 621 736577013 97 205 430965586 977 58 638919489 529 399 44394552 636 895 561600573 850 289 68325602 126 430 10999415 810 378 234915821 349 168 140139677 497 736 842038948 402 480 695286591 153 161 191541695 741 931 764693273 220 97 859169452 85 308 2636782 297 805 992357686 511 365 983400988 656 999 760659856 847 221 557559531 104 649 982900124 464 416 168997810 916 1 741044454 719 340 598451994 797 885 614505989 266 159 865159605 349 253 102748108 128 840 298221158 489 420 303917393 110 887 682471239 76 859 243713060 240 827 657836635 939 233 174389593 89 240 952170972 883 700 91938328 126 722 981535993 269 351 473417161 980 133 612578011 173 131 56798697 187 858 914162815 290 185 755809251 158 814 285254289 997 659 452514315 851 583 500129118 666 976 462801773 33 317 25386439 516 849 724249906 891 263 697445030 91 835 671601615 850 748 631458794 422 224 379212449 55 993 810772118 375 411 961090836 967 489 304484239 447 668 74194270 235 100 200907050 20 904 32489299 803 939 937666905 2 887 887381219 357 499 716856683 100 589 549734170 384 692 45410101 289 957 951775570 126 303 20033464 454 753 638746155 132 363 252491493 278 361 683878380 962 663 158075154 302 511 345668517 691 56 762541361 499 798 979031200 962 369 341254764 989 606 493551148 784 251 31287262 284 492 116122298 993 360 938245421 410 812 151145063 371 904 276551956 788 606 555615191 419 131 898459092 136 736 301415087 713 61 805818885 571 588 836385428 707 855 336784991 593 82 87419699 748 48 331022443 809 660 142930652 792 329 495068693 933 584 682022946 762 582 216571112 619 344 282371421 453 256 28497202 168 499 228945602 240 978 524591974 909 476 69537762 368 134 547261082 610 664 26959497 871 862 43423511 195 134 459014548 146 981 272504654 815 613 80885258 251 360 514824925 758 166 850050644 609 532 565233868 218 376 937462329 460 310 519846280 804 73 677399562 12 712 254415482 637 37 40032723 243 517 881005902 586 205 666711332 301 580 857964838 367 451 141683785 725 315 316975769 212 177 563485466 686 467 315384947 314 44 955209068 563 376 641461509 719 114 936024593 820 654 618293117 316 341 363919895 120 553 200992609 340 873 380339002 11 586 761279091 748 122 889163355 64 936 45744673 387 425 920700574 91 407 475785377 967 860 210225685 258 407 980671792 281 128 650515617 844 257 66029215 948 661 910815405 42 640 535375644 205 362 952405165 727 297 344100441 296 227 504326949 409 951 516961106 368 834 360896990 243 475 966877681 127 995 901916614 296 431 532735112 828 617 404544540 274 371 472740288 230 633 14576825 560 634 326736310 762 23 664363677 420 774 510846333 958 761 844748961 814 837 938556946 825 447 90095019 499 87 872714666 261 18 772548312 646 43 165215974 288 175 380579273 933 136 636819381 90 491 683144374 630 635 504984881 348 412 969256022 945 632 456142267 719 897 643840617 526 280 682324748 844 427 199989377 983 751 118862564 48 27 565060658 407 227 293594655 392 979 352041081 350 492 362710969 292 678 465335805 336 918 971810143 500 632 687339220 336 753 243040350 637 756 736759699 735 445 878183229 65 649 946468026 548 989 293072806 298 993 792901566 419 378 65556886 159 64 367485820 270 371 295784761 170 178 496514360 220 622 28677597 738 23 398204393 410 513 838574316 659 879 3464832 775 276 710005765 87 438 623948981 477 366 930653368 368 146 296082125 650 408 167349095 464 715 928208708 21 108 998724491 150 716 94412675 603 64 968924894 786 952 474023305 726 374 824780279 241 388 836694277 423 655 403636545 237 461 726169884 223 310 515557641 667 572 392197334 601 419 971218286 229 908 711552227 575 54 314916857 974 979 710164197 843 505 627606993 398 109 552196544 540 743 789189074 14 24 905390458 901 123 874990137 435 108 272089923 387 904 957306329 490 439 48259062 521 119 59256358 791 283 515354467 8 331 936357512 554 336 321810383 769 591 651590295 854 757 44778711 469 442 49735744 732 774 24052980 430 314 867327833 220 923 307926930 48 338 208561607 852 468 823354400 967 142 815684777 519 981 590011326 468 526 614063311 848 192 309651685 346 7 911113701 222 981 75986055 562 909 316449413 17 34 433552656 830 681 859105793 387 619 684711138 783 47 161463114 957 457 568027886 761 61 528719172 937 280 478100081 982 390 666253659 350 944 14078038 557 937 272484901 201 355 631043414 759 815 59320004 522 433 907884040 334 369 721900927 822 711 839051710 12 808 837422433 963 875 459487024 620 448 379673028 94 668 102311173 336 879 619763493 908 304 249216567 906 745 346278519 532 68 557716262 725 120 303787303 591 230 358102811 15 413 744577178 699 507 812479948 737 188 730951714 75 72 152334138 22 610 118782123 11 397 514914583 207 831 465660991 834 829 145527939 396 22 615559215 295 121 235537311 895 118 573378654 813 440 215516805 101 140 996547051 626 369 241669772 987 332 278804448 32 11 433202724 23 877 615693994 883 746 566274849 741 869 391560770 751 979 729384625 202 797 96605811 17 281 677067161 972 64 203573576 47 516 766135334 345 612 618719538 135 998 82328743 998 412 368088897 561 219 50662490 628 369 742776503 578 69 621824574 357 839 100495136 685 220 20910786 384 615 832461278 243 374 577625386 910 650 258713580 476 83 740000108 336 324 300055503 610 454 172638548 652 385 316943625 770 129 902006628 467 333 453335509 440 564 840774508 736 575 266876084 150 436 979814712 469 678 983489896 365 439 795568187 309 807 574968124 48 344 670921606 682 434 214633510 870 455 779136713 958 399 504646244 48 658 361329636 736 790 263500650 696 530 732568139 557 867 851983074 502 794 913461780 221 35 378774314 505 399 113762866 272 558 255463203 856 404 113182294 28 856 235986891 313 469 237176461 382 106 396773436 511 873 16930086 575 254 542489491 430 60 674666699 581 803 946029887 226 313 234227723 747 717 544469451 409 469 608994227 19 667 933664261 236 51 373216399 834 223 384482487 957 196 783560216 373 491 303900181 29 508 613769406 542 428 182895636 123 391 680910494 113 316 218051388 98 528 413987853 922 795 731256726 766 42 223602454 940 616 238324431 726 587 370512113 363 961 262097386 53 469 435806181 464 413 934087937 312 487 659024942 220 857 118824494 236 643 445657417 178 842 103735655 200 947 58330403 69 352 153696268 54 434 372162196 664 873 835946320 651 368 273536271 730 786 805776006 946 989 623639827 736 901 123773473 675 760 952079417 724 251 919850602 438 996 261050987 584 894 309839058 824 194 450785444 333 413 609150688 817 578 398880667 158 540 638623819 172 703 153459523 279 776 86202112 627 614 674343765 835 877 677888411 735 853 417484552 516 249 490784344 47 522 865373047 454 460 442232818 151 535 725326679 827 284 377457035 932 125 377228032 376 736 824496238 599 563 644924223 285 852 984524663 462 665 945539807 826 375 867478479 110 588 897263566 329 785 716886640 616 482 454536682 544 815 738559498 850 441 870467706 528 567 683415434 277 522 737757456 471 911 408474660 845 47 226810964 259 519 812650678 469 985 753518756 24 186 367710048 560 373 358789917 325 899 86335391 566 953 361773177 324 776 45122884 308 438 976387003 696 702 533330623 641 394 5230390 212 514 424383690 239 207 554762858 403 809 282804082 548 568 445571760 879 738 158799729 212 469 423822413 499 942 367066420 535 106 871076888 240 784 606457424 815 333 946585937 686 400 601911182 726 720 875926468 354 322 566207486 2 358 508075731 735 784 510485000 725 586 583297289 253 821 438785858 151 821 159877582 764 235 589443161 818 401 605472144 418 938 767253224 665 981 902568269 82 309 821834780 593 830 276704466 612 807 609339766 871 346 238916435 725 641 840600782 127 888 276387904 938 386 220310075 765 418 788039579 644 587 536497213 231 943 946104683 60 378 783426447 619 60 847426064 946 752 596200980 956 43 743483950 11 631 686089256 303 551 850361193 526 417 766264919 47 251 738054741 720 833 481092568 373 567 645351125 66 305 958255118 699 674 990843066 73 5 793388773 971 372 885137318 132 78 815351379 852 457 674528836 56 12 499701729 627 748 779783298 76 479 430286456 281 807 628172107 72 813 543030544 667 777 609078296 985 523 21761294 322 517 110112584 815 587 686716663 485 705 922077738 425 243 690145274 950 320 772834385 802 40 429640204 446 675 43097784 236 623 790844318 953 404 1915378 566 842 604660329 690 634 883442195 345 982 912212620 979 24 700261747 311 858 414740977 664 451 685018489 147 399 308484464 195 131 791701990 864 668 441249711 992 506 715563753 293 871 751338804 789 459 467882460 181 491 764234940 832 548 710685182 575 857 946492434 461 822 572368541 467 504 592804555 492 93 29298001 499 4 726054689 271 458 648330189 751 537 126991400 870 357 592740653 202 752 33868923 560 2 520188254 803 897 684792822 211 848 864654271 881 898 734492025 797 684 783420520 335 340 393041898 860 326 400191719 891 352 308680267 353 531 76043384 275 630 664317354 501 786 928352538 857 771 985745450 192 125 853912564 283 788 714652162 557 313 52949615 428 70 2748316 930 826 521287406 492 255 857727907 425 301 176992012 397 60 975097358 998 267 878714789 118 36 82011747 672 227 342774010 681 916 93833604 485 431 6540672 961 453 443233556 449 588 426433097 809 710 605537983 114 393 964024109 182 498 565608908 547 524 567113883 325 845 29476559 727 786 770795618 628 475 39621692 552 725 89465895 539 342 107829506 751 946 811552390 697 410 216972986 622 532 335194799 548 574 901451873 583 790 967343165 708 27 414101423 936 371 523068971 328 394 761457917 422 854 201614063 20 200 948510737 204 952 238013545 409 661 402537542 212 513 462693470 224 800 796279105 716 857 732180592 686 664 854878656 395 338 443574581 150 730 465743370 172 582 926925895 364 864 351413005 22 548 836645636 621 54 632198482 872 216 338377672 394 708 633414656 257 795 858903011 500 866 636855611 470 187 736688745 710 906 305226344 253 161 711867488 907 511 11917238 230 978 873133194 163 54 899619183 745 186 203796967 388 247 702011922 640 187 629997172 481 847 473989519 299 74 869115965 785 547 723653183 421 273 364010872 692 179 932141 386 912 9739314 101 409 723280928 202 412 313396498 768 652 198773990 316 472 295465884 625 693 988855358 510 279 769109435 773 982 65192255 314 800 727920180 750 586 72414704 270 858 914005534 174 266 840107795 106 167 743941940 849 62 874883927 192 639 197487990 515 805 638355052 580 374 784765228 338 320 350683805 829 23 2117776 337 39 651445215 285 322 468443341 670 562 266399758 652 70 106963414 890 255 581299327 305 690 377712179 77 364 173777005 266 85 358749429 446 933 481068827 952 8 362353388 634 602 301776039 325 626 92750041 418 394 136100692 21 919 78923708 8 361 737557328 480 606 505844944 345 166 648831915 643 661 569641492 49 977 94583629 202 779 687685780 757 793 304973541 1 902 615143539 704 207 722745411 924 264 503630175 116 237 503743313 147 589 586425303 488 152 796867250 368 836 980219822 511 154 517754798 64 455 561187527 858 204 254535093 58 944 685231918 485 652 111834317 331 33 787770917 387 701 839858161 197 827 951393434 54 892 992851788 44 579 974907767 975 723 414046224 641 827 788647299 597 316 870298574 469 422 284982096 304 762 137417591 392 629 100199319 37 492 618026006 215 722 402803774 529 945 836444125 44 209 947014077 799 106 534097191 812 398 792614396 821 912 471513841 816 958 797191408 135 526 397770384 780 264 240482554 961 303 279273930 2 603 665249971 650 970 30023448 121 183 621106095 445 809 943006246 271 282 363910136 562 934 301832928 880 230 936210065 151 336 752190227 488 675 469761718 253 493 444424959 27 912 254929101 908 330 861265244 62 943 216193760 48 306 162064895 182 231 268603800 372 203 316088720 550 969 750804129 345 844 737646254 279 594 147786543 711 685 987360657 853 409 239385970 29 658 394878852 676 738 456677652 434 498 95999947 22 593 770585812 594 562 400818623 382 47 719528241 632 342 84036039 975 751 168518625 66 38 103663164 661 745 600876611 38 843 475792335 795 965 841757886 677 602 558854135 205 667 948263112 347 116 346971217 57 840 223241982 783 251 938529189 468 445 317757375 71 769 500116091 374 699 872608155 547 842 821375418 540 933 245361072 634 343 48553573 492 927 221684020 805 152 701397548 934 411 808069797 274 793 141125983 111 581 695399012 112 650 249712530 358 230 256877536 754 581 526267974 200 292 30909026 147 328 597948103 492 746 202241828 551 11 123217749 945 654 752464451 883 799 745866196 105 805 434998943 448 246 293530276 609 385 593130778 955 791 828037953 704 495 360816397 811 294 358474106 854 960 740266897 221 520 574245751 349 567 492336203 874 380 339196665 603 239 972395685 177 86 999067742 711 533 775257864 330 113 825594931 116 258 721471088 197 761 833299345 267 394 490894750 456 960 913003258 283 966 158671881 730 250 420331782 846 88 187185284 411 375 418508925 748 168 473822748 648 803 763945972 907 153 984074543 312 340 369520189 219 816 988210663 798 116 669635428 243 173 910663144 756 631 682670709 317 134 173687677 629 918 751705174 629 81 450339076 718 16 110725819 996 698 428847388 243 13 437095578 50 468 70343231 943 538 439374984 504 51 915308332 420 358 257620535 600 708 431306086 339 856 442400104 465 13 65262741 97 919 529971429 79 960 188195725 995 430 149440291 837 42 355235491 243 697 763917335 428 302 95659782 965 664 438840191 574 977 886596947 865 977 931525549 220 658 645304516 440 151 373455226 741 751 554415436 571 446 491768420 39 438 79015378 27 906 864484695 324 448 335837874 250 466 839200352 389 777 280731316 341 328 478255914 345 977 481824246 86 776 850922036 966 615 594051374 595 738 776421481 195 152 135930348 828 843 294473144 145 536 969037103 807 734 856634844 395 35 846829725 112 205 390565706 162 884 11437506 593 518 226289561 665 805 659899555 846 672 487525640 598 175 907772176 802 754 500178887 584 498 632594150 739 643 502729366 114 59 229753203 357 269 938527894 613 835 26851300 848 164 198220792 806 466 352920369 45 992 623364935 93 520 486305106 115 48 354941089 649 755 721286030 591 923 810429492 971 126 554084644 90 600 9470196 95 631 239648415 497 985 821748494 941 304 351330469 56 794 871572238 60 264 870031738 503 549 541517705 19 338 993098132 1 271 962663848 411 654 751262718 79 496 85395861 931 697 827160635 370 824 609139533 593 370 679866049 481 513 4813653 733 843 898056900 3 126 215304574 440 449 104255932 794 677 234527701 284 471 573724885 18 969 352570514 166 245 900425356 234 50 841532408 939 582 881683132 579 225 775191140 213 814 565363451 265 519 970615628 135 673 437152055 127 511 696184565 966 891 441641321 889 147 343750123 392 184 906323204 997 662 394044124 890 752 796122025 964 840 753855828 389 988 814470045 255 492 602915510 349 695 57791277 109 643 890718181 672 979 730939204 331 396 515345871 866 920 731269654 372 50 575849115 586 189 771120111 505 416 267907663 864 457 601901344 170 199 621992147 462 992 84008681 303 552 250462205 677 892 390545245 823 103 166133227 579 377 333277956 136 234 77655475 393 148 710158432 807 899 343815993 898 159 884021887 68 218 33669911 895 837 68371839 272 955 846121541 205 583 430168187 270 505 325455255 647 872 316181520 579 332 493784996 180 705 369153664 900 992 925432326 866 337 54686347 692 893 222554674