973 573082003 138132368 730617518 151398023 889678713 919814855 774211766 879848796 167320112 109803732 597316837 122138192 927891673 677082853 217900414 376856883 934115075 214209414 922750857 161652342 46741650 588146259 512547518 518566258 380920031 625395835 426329446 132682000 911354811 293362583 747583452 220872563 179027552 669465039 65234124 935610153 662642892 299808283 351099072 579790910 451177937 129839004 324642575 702253648 261823386 390204085 272733587 486304239 748609620 160335145 61924179 802131239 880056325 375642220 53737939 932492081 187806435 324552144 508246840 257102266 169698557 794751840 165984037 152820549 894823593 702237160 238340926 322645712 969130541 823931806 297268106 202121939 434542007 335867398 899277828 66027592 185673509 443959395 771182536 924558010 777643821 349888129 846011868 293628134 745221169 125209409 438699072 857579591 861507928 115586145 696891910 414839208 591203650 116427720 74822248 154791940 956286470 457247590 817598330 21148037 574548761 965677010 907507010 997524527 108579420 999234818 111357877 765911875 314242028 508513154 644371706 27594455 334140946 708060686 338781593 942119223 451038869 920395657 139287610 368413835 105290266 325148359 804570108 676481307 131122724 317546498 608961241 99657947 827248693 46490515 870603471 164414875 818146072 797522030 322128010 848633074 287102125 500739339 365921932 220503586 512163650 59895677 115076347 472618339 875413562 293202527 546641679 797426177 288236144 526939759 935652443 498219999 53264303 999694880 19539792 77289872 556574835 298653686 339161943 626620174 920952113 945457276 115342751 857344412 596921199 156134260 979796044 569909381 188052881 490482302 299517108 263996299 518734667 808460741 508782859 133638494 153755604 18097825 434637486 100634715 898640748 831790632 803797200 33867823 991442424 223992422 64543788 46561309 666855452 102472822 558446557 175564284 857036094 372746263 590877384 127985033 272449264 520147212 672610501 166536840 61540735 899958581 643481849 850919894 640437660 726127296 933685225 637410040 35794413 399112109 873654470 14178743 241666883 501076533 458544854 578169240 586119378 536999759 929501815 397226648 597558702 159960438 198804204 536887749 847830762 162217508 439335501 235350796 804222324 119855322 127852280 947453934 15949264 582124820 556763153 221967557 185190214 990396650 92207398 553746408 571976876 12690379 510303182 802651238 517912435 780478237 964621506 217632761 96780553 204665945 472320656 771917583 365110150 844466301 256020557 148795987 247376784 389243276 339131454 213292273 692282925 44075746 178127184 575127723 81199166 367767004 527832630 82743281 159235916 120339999 43380842 18506718 901125919 525885564 672795379 360616610 956191741 644643680 490381542 934667521 981821079 764235738 206252518 636369173 980543576 634967348 969463854 710534114 972276858 167978810 757232547 511473016 138927014 685758443 710549990 264858376 352757198 595943415 939352908 908352967 817377968 918966462 990994352 6082819 965275104 763320892 106086737 59917894 509685790 842596749 555797584 786218676 653786920 514021619 214657261 199806341 561287781 652629151 114734810 830777913 325516380 329811520 477657424 119320567 910696738 848290098 747538414 957671017 154546834 169988171 493195500 757398666 37827866 89040987 695525227 310984964 697810338 516716498 847220305 505933835 765865435 86452722 815012338 237028493 380236462 117316297 238359258 121963808 139780086 949135470 200013140 385261883 512141679 527970009 618856212 642145787 568744034 867663564 401933567 464813641 386572518 654390140 395292472 643305756 242650167 457294714 126236574 108495866 156697241 466992685 322574576 63260735 519774508 886168293 105592153 706133187 540573667 796177799 798204731 829430529 982749008 545708466 2209687 268491398 590483699 716759383 215244415 216472768 444844939 489227046 113878430 246695363 218382518 170029651 163395808 355948528 475495407 179673839 97388796 389428534 5574430 857960219 961848576 227165328 616506636 126907900 293602253 287940393 116672339 928791301 102555813 361138542 824191555 749987649 646236690 349745598 550977308 87177728 510066177 286872392 11469143 212818170 249729477 181124171 492194008 369406403 920504276 569323858 138278120 761548560 594771438 891459564 928454113 359203320 128184125 978501986 709111834 296863441 90028747 408739248 603183810 196623767 908466924 353027890 332572854 318571821 57798720 868514819 31847181 612566590 476731939 706707830 455879306 584518829 85566161 475613001 248292670 801379406 184935895 164944001 815315858 665284683 406944725 471062859 218344313 57945627 173268278 801541999 966241976 37063057 978851579 39095680 388229307 527050070 505733354 352599650 869393248 358869076 267346660 257113273 649562066 29321778 770844840 403359558 227829043 570731350 281777038 794302703 95863841 894221998 339237540 237944094 451157444 877848443 204110718 164414817 561324830 389090668 454254940 201205994 134801173 107665982 245446188 559331466 275311581 86249574 226754848 774193504 877933877 523969712 156699138 267501073 545324779 503698292 105432302 639174695 854966766 751307473 485195858 900913811 213382679 61650864 774118229 501827545 238024068 155197373 29503020 997788550 125245528 109315249 993636328 904088661 711069212 63103503 168305750 152757473 400389848 992193808 803393554 968425514 509820793 761456276 690045105 157508441 49482274 721399649 873756277 222047667 388974129 832832412 724006035 212941702 359567290 493280615 897871655 774809529 4140067 811763573 166012919 895861476 139422066 853003809 591349900 831806963 326512383 513207147 656215206 245005111 503688578 99929606 935227210 641465020 884443216 340652576 73247043 760069494 14165132 855229807 52934853 722004253 620891456 480555997 106914893 639351245 65183288 444763819 632371938 344834715 956288381 768033929 251883073 778997965 331944020 691132244 212220640 601070122 747098857 667291592 163337776 235553599 743574057 682017637 736490940 38667125 502013892 238908629 806014474 54445007 463087277 588118415 341963860 148470541 205117631 448452618 727666978 48327472 724087795 879538894 88451681 993283052 160921186 413778721 677822879 892452719 162882536 418495588 626405067 316007383 247745167 210248877 579353331 382867980 738776997 70604857 930687849 848040234 309712996 417543853 819463271 608853735 903506392 715894060 727922877 74864556 580703830 239865272 986306667 99619653 331275197 355073317 70245473 777606807 824763035 930966735 329629327 864142439 483973559 322185222 753492465 459580387 536636394 516716089 317723169 550654088 9406282 418790409 31332209 492737529 257052104 916623874 403517068 489296608 660403632 581611180 393654229 335407903 727123008 609845145 396530812 713633149 397349963 173292263 261710515 537766687 299646285 822350017 403810611 7935855 551342761 877327007 499789634 861326827 543954835 328565159 9151656 347034652 808294307 399246050 886693460 961686986 961020311 537221812 974512963 559381303 975738387 415970730 820876772 265769341 400492406 380224697 769939273 946245175 26140763 115261909 207664711 858695025 380918400 432285971 654446728 234202557 191676868 323799763 232438484 471195814 704984954 218531252 20627511 949289664 121365126 395885518 175293318 534086064 410450963 348775584 965203717 886315532 447264802 980016950 334369561 150872038 756856931 712507848 728706338 145960428 144497243 580348814 966376278 6079028 160609036 898849780 320745998 900575022 262648143 525802175 965860835 203309245 136284697 489991805 838588319 328680906 780251016 448158301 473768533 414258774 577389619 75875994 450812924 36377371 96066784 605816445 140257772 829994860 618724116 119791367 378126844 522119579 416680015 892271426 852571650 384913445 969116227 484595093 282731811 981102981 63475331 121073148 312524419 460214811 618272033 353815633 12359635 448179070 177738596 810327774 558065200 23767411 961834724 570625709 568943392 22548576 428325830 333347943 505091061 51120482 658040581 587287460 175261427 657262855 888757019 969168363 355105893 967779025 565160697 86650858 740495860 729484267 708049260 341169254 835288369 107698960 769764803 81112342 700806135 396928964 768863422 203295472 989858946 149560542 472419902 274711581 20506914 26699280 12599570 288662542 78483571 317637688 474017551 48491273 399045788 318289146 500226136 480428961 469198809 573435833 701992629 711029473 414640706 364827032 268090281 401628837 225949790 352040248 462457536 121162278 953190775 189458261 488212025 95001066 65444395 26431974 234050973 730199118 577760773 527516431 761176809 250725970 419788057 86482347 36677151 520965770 816409068 530323109 334887347 755770085 931401410 549434655 437364178 430007330 121172286 645105050 601990168 575062528 674463547 628538834 250054043 82309824 344611772 454390641 618125185 104258304 659004752 390798833 689784202 956839630 971864492 405526780 976740829 63585458 201976318 529902643 598005684 682730775 768259573 880408353 908480386 163904747 716822886 97232999 501731740 376902641 615230490 937550263 169048005 486432090 212261496 604496386 442529592 188298929 337284839 281806140 234013219 501659867 950456022 356281081 93240922 2334268 389626243 274955517 551263397 475016217 609602553 722319947 660317071 273409310 581769332 234678794 786251190 372816081 118855205 908900450 95619931 206162881 3773536 617042319 998982880 655863500 30963810 509252217 95446477 142875218 84939147 474052083 733952204 886971626 59193046 544683374 234888390 539004347 701645185 723351706 1794249 357301939 512323148 685078451 306604570 169094847 429285848 610504358 425750707 119191762 52606174 530437577 183599740 204 907 907 380 907 105 105 241 907 743 907 440 105 573 380 92 105 818 907 920 105 679 92 811 907 342 92 376 811 22 920 954 380 726 22 644 811 767 907 427 743 55 22 201 907 799 907 403 644 430 55 858 767 219 573 938 811 365 573 659 219 90 219 925 726 347 743 453 799 350 365 508 858 278 644 327 679 662 90 168 662 423 201 426 278 405 90 66 818 32 925 183 32 611 811 666 347 600 342 243 453 647 278 783 347 862 938 357 219 949 426 619 659 227 907 590 243 95 573 483 858 213 55 412 483 89 811 874 925 868 590 182 862 114 427 623 105 296 327 28 342 656 573 469 938 312 453 486 114 171 105 111 405 849 365 51 22 8 486 580 55 390 32 953 350 884 644 338 405 267 350 876 573 897 376 74 423 929 647 918 918 620 296 317 726 40 799 690 338 320 783 353 666 886 357 256 679 233 886 397 938 919 469 332 874 181 213 552 342 335 644 223 105 385 243 84 22 180 611 717 90 475 611 786 380 819 92 660 949 146 786 438 8 313 168 534 811 812 849 813 440 153 146 579 180 340 90 586 183 756 811 1 483 838 486 603 619 34 884 463 182 917 508 476 876 128 767 361 426 873 89 315 469 270 953 458 656 175 819 661 659 870 620 784 338 425 920 447 168 583 365 550 278 525 862 400 783 667 84 355 296 808 469 911 579 569 583 246 95 657 105 842 811 240 317 522 919 719 508 781 811 775 355 109 180 937 175 110 954 64 40 368 313 386 426 565 483 125 917 543 849 431 918 42 400 649 380 664 842 778 813 257 332 805 201 2 240 23 483 253 870 104 679 900 313 141 799 170 719 837 90 59 400 478 953 498 858 487 469 844 805 333 458 473 333 896 256 294 907 694 40 121 918 736 105 683 447 306 223 673 619 772 253 94 125 9 42 76 907 504 525 887 141 890 110 639 9 630 778 220 778 737 76 770 201 414 786 652 550 559 427 85 486 696 639 143 897 299 121 156 66 179 917 712 22 81 179 212 427 235 660 706 623 594 583 702 873 718 813 432 111 281 414 238 361 435 34 595 862 336 718 785 365 298 405 242 522 449 365 226 476 433 397 966 647 864 170 803 525 102 887 663 783 759 886 372 299 628 22 557 412 745 811 303 84 800 783 133 267 507 294 91 84 460 42 19 868 531 355 477 34 420 438 880 737 318 868 963 168 295 803 199 786 49 473 797 412 97 143 122 81 923 201 38 487 229 475 722 226 555 778 190 95 538 483 643 696 484 278 300 504 35 475 174 925 761 9 512 449 124 662 707 555 27 954 831 179 936 240 409 873 570 702 774 620 617 318 363 660 809 281 871 327 268 737 132 233 885 110 724 679 154 652 587 896 970 81 56 181 222 143 472 504 260 508 325 201 829 453 21 174 755 706 589 405 777 124 654 722 607 385 207 64 275 617 309 121 112 229 751 777 547 405 728 397 599 235 468 260 576 603 955 706 597 204 100 706 492 425 646 673 945 253 185 153 61 929 503 336 869 654 382 246 878 579 943 589 913 153 436 204 960 303 44 201 627 770 139 219 86 463 558 190 457 473 446 759 304 270 895 666 308 168 850 761 891 552 135 829 697 603 856 580 360 666 408 880 608 897 389 109 439 204 847 132 272 589 564 435 208 864 455 61 367 803 677 281 542 818 194 923 364 190 698 143 916 755 715 368 853 156 749 842 727 809 352 318 251 156 276 298 379 390 502 690 766 246 828 438 231 367 130 547 852 884 326 468 532 294 442 357 699 199 4 649 621 342 197 51 348 644 791 425 142 654 610 847 96 436 123 508 950 811 863 97 973 246 202 583 211 130 41 749 236 379 909 702 301 557 883 737 629 146 205 44 860 858 147 662 672 109 889 761 248 183 926 246 944 555 140 863 560 425 434 767 266 174 269 538 935 4 157 76 443 863 668 223 741 925 877 147 765 668 584 21 152 55 448 944 188 51 530 811 940 673 782 270 515 213 857 44 343 443 602 812 572 304 968 791 701 32 604 235 29 348 419 56 163 890 192 492 462 295 614 829 635 204 834 347 359 573 711 303 835 602 537 697 908 604 792 498 373 737 872 389 921 257 79 512 738 607 138 276 274 677 474 397 265 767 540 361 505 508 316 860 691 628 636 719 830 852 261 147 544 197 591 738 169 949 692 726 366 702 311 55 351 76 464 799 506 856 622 128 739 157 776 597 513 23 255 599 932 34 681 945 394 156 568 707 20 474 734 84 344 434 496 696 53 139 804 791 5 61 551 724 136 560 155 797 30 602 18 446 536 265 814 32 500 828 305 408 416 600 7 862 951 74 526 336 479 340 490 157 942 837 271 267 801 325 678 765 582 580 519 636 145 584 228 890 616 856 928 791 166 353 480 805 648 717 898 913 959 138 561 155 286 776 748 594 962 22 113 954 371 462 744 620 605 889 161 503 859 320 280 344 131 654 721 561 329 347 641 197 665 152 393 91 773 766 618 135 210 492 387 530 407 153 626 389 593 243 196 8 75 868 556 276 186 21 107 502 410 275 562 463 50 797 674 701 700 147 750 814 910 138 82 44 415 610 899 584 45 641 3 59 411 590 116 45 687 169 287 486 101 376 971 38 494 185 258 280 924 748 383 667 178 79 675 701 39 715 60 352 865 79 297 699 465 194 346 610 933 261 334 60 768 125 601 570 87 639 167 863 33 505 118 336 740 681 103 683 533 272 160 336 879 602 941 808 195 739 753 89 63 122 31 811 252 103 117 896 520 586 686 21 903 220 554 278 836 22 485 661 735 2 902 945 730 842 521 877 848 333 108 547 914 919 288 659 841 235 399 618 567 141 952 195 370 23 888 719 388 741 396 275 581 759 26 407 291 433 650 74 685 924 541 672 177 473 200 180 875 436 173 443 906 177 217 618 422 248 509 650 511 251 224 125 930 152 523 685 764 7 642 117 823 326 671 300 88 460 684 868 714 936 653 921 592 888 640 336 824 192 651 800 283 537 58 600 758 685 218 920 827 862 854 207 307 679 577 50 234 702 548 346 788 550 816 360 52 360 832 628 585 759 375 438 763 544 119 468 826 270 958 730 947 63 221 407 780 522 73 580 825 928 279 570 546 190 598 287 285 385 191 647 444 730 456 608 413 937 98 960 709 690 290 169 578 476 676 474 658 173 810 640 489 88 314 498 404 658 377 907 77 589 43 45 65 474 172 744 54 255 401 953 321 908 120 526 127 56 689 45 631 706 527 955 972 809 632 246 398 325 214 59 725 818 47 919 57 610 615 884 769 824 384 287 499 338 518 480 482 271 794 242 354 100 851 404 302 480 904 926 11 531 969 667 633 89 754 357 337 182 843 818 901 773 771 39 833 318 293 889 528 622 481 55 71 593 710 627 264 256 752 748 688 513 198 34 37 672 25 758 553 463 445 565 369 33 203 71 549 590 893 604 230 400 277 457 934 874 284 860 931 725 912 71 806 241 72 544 273 947 215 859 894 4 322 532 16 853 378 416 840 43 796 30 882 169 491 622 263 448 588 777 137 595 821 376 324 591 680 399 24 949 693 4 162 633 495 460 822 195 392 231 466 592 497 701 566 943 967 448 126 522 695 111 310 826 15 79 106 821 206 969 78 233 184 281 965 154 245 568 441 828 961 107 374 508 574 836 802 718 328 161 247 654 437 502 747 75 731 719 905 139 703 703 471 359 655 210 262 550 732 764 189 77 529 685 563 600 957 843 892 146 134 572 323 783 244 15 545 862 682 700 867 683 645 633 793 353 36 351 292 321 729 340 501 163 716 776 790 28 158 211 535 768 470 646 798 377 17 550 402 27 762 123 356 550 232 505 817 305 429 917 62 717 99 269 259 509 330 29 13 788 789 586 939 227 421 901 638 113 839 37 795 480 815 818 165 824 670 415 517 579 239 664 93 121 250 458 454 376 779 258 524 347 669 356 216 535 704 346 10 771 12 664 757 472 705 921 452 292 80 347 723 660 362 530 339 683 514 841 820 269 922 962 69 388 624 281 6 647 349 624 866 660 881 446 613 815 459 792 787 776 467 820 159 118 254 8 225 75 927 917 289 195 151 866 209 41 708 116 539 314 948 973 176 561 48 859 510 491 861 861 450 239 571 544 150 235 596 836 249 490 428 382 331 515 713 473 760 759 391 827 83 568 424 211 742 884 493 610 606 747 516 601 341 932 451 776 488 71 14 195 625 47 845 154 395 192 319 476 915 454 129 341 807 839 612 62 282 429 237 716 733 514 67 287 70 438 187 494 417 142 115 663 381 231 406 593 345 45 746 411 193 426 164 41 575 535 956 205 68 366 46 36 148 624 144 460 149 970 609 266 418 481 634 572 855 660 358 706 720 855 846 835 461 919 946 92 637 243 964