1 62 95675 661962 538587 56694 727294 755662 301911 147933 592339 740896 928138 672833 923605 771295 501606 385926 459970 467069 873085 20313 382000 529286 830244 434295 276419 400307 161343 349457 117653 400936 962268 834112 422294 95502 459750 916590 858422 469715 885013 826049 235358 480819 541807 772567 815454 616010 275023 239122 454133 862292 669885 209400 936336 520811 663767 716024 767495 427688 313845 826088 697909 127507 177135 692433 92570 693471 485123 249303 738762 618973 566607 813669 642655 107694 102215 190094 84953 873745 72486 51184 930921 289716 769777 600157 84165 336065 678672 189943 58581 675412 741373 83510 544855 70465 175985 323330 292142 414177 594634 925933 62315 582099 166334 68599 161194 756782 288850 657919 818505 969969 23558 268626 310828 641821 113982 977876 931028 458701 405998 658607 336445 719169 794691 733520 733535 975027 550338 655162 680400 810518 28399 906367 95393 933315 498164 938513 492900 893707 837378 423037 606157 261547 55811 79413 316415 479702 573001 713950 240637 80332 147569 280903 794085 91701 73857 64290 907126 20077 216434 945444 771968 846771 12968 358219 728032 913083 862686 211852 613521 662515 417323 151989 846230 951734 495855 173742 860861 481091 818681 725972 540873 319631 526843 468148 238147 439353 991325 195722 613778 569409 398317 544150 108141 205156 367503 712068 986086 469542 461337 190868 284602 2586 926033 664227 297547 490706 215243 428455 726634 287684 864501 786701 440786 906359 29910 82378 378200 407233 9180 737067 843047 469256 489460 204501 415023 708576 813247 523248 356542 206421 484168 992474 204753 865736 626595 918774 67059 975869 704935 606068 749831 465501 789184 805763 759832 109050 859466 753439 494260 370460 391465 670603 209238 61992 845964 21252 107755 635517 215361 518907 140647 592225 539454 166580 550069 201624 259286 528988 103500 868711 639422 941789 895097 252430 215683 102648 111416 705483 525754 86901 751293 951084 523553 274482 45630 684824 420183 131765 681669 924224 759494 87465 217138 339489 995742 746133 247816 826872 220841 300329 410313 203387 802548 304694 780581 643116 26634 376206 95707 208850 603004 618085 282007 483367 211379 880090 917550 373198 320494 189952 501430 13889 348119 543257 290554 884203 561247 933470 741876 232209 153893 845334 297197 635603 338365 992329 227004 72532 884426 273595 862527 717907 15104 12376 941064 558113 662272 526177 309474 485933 804540 55932 239751 572690 415458 669811 913982 616493 193664 995493 548692 364446 797129 393671 427564 694333 405457 342829 767700 567060 772949 95972 608704 948407 880481 490862 282798 249395 503782 830583 597950 750329 488464 835240 85173 279073 932872 175636 530856 549089 19605 915524 448216 163853 91422 935411 92427 314014 550474 99459 357335 555207 671217 607332 172603 3592 769589 355130 662002 275294 247109 609876 360702 422792 236125 18099 836724 728772 610880 617206 997715 598568 955001 361211 534692 911778 418822 684968 295076 528526 702932 396272 345102 482415 968956 978239 598348 41182 370754 441252 212248 385763 976975 574078 597867 213475 196177 238477 493942 408109 904477 964427 286521 924620 829953 198964 826361 493643 732749 848091 341 744305 957263 335088 480922 261844 75154 376666 802030 51523 776274 503060 958920 671675 257255 354321 286963 337116 820591 456444 388462 12496 191117 353114 39812 103971 367939 77979 397521 104997 116745 314153 447027 311949 520323 493931 43317 448425 100084 39527 429213 325356 975476 303202 50705 606444 393070 829694 447388 941274 682853 392756 467321 609607 281476 997140 918341 640308 595770 288535 187371 448813 821548 289960 376958 358468 601803 779024 328420 125555 830750 590902 753638 120243 138122 65444 586974 905569 221129 491337 267439 120850 910427 74103 95218 218052 743347 868083 907643 243730 901656 366207 414150 651065 203339 531976 944085 176150 221119 965071 528928 356562 489568 181557 925225 461669 430866 652701 473483 89078 276917 124982 199442 968560 997090 647074 559594 903406 360154 437621 154139 298801 124794 934693 887211 914014 302136 65660 446413 412205 143553 360509 186438 451294 676348 418189 462100 813874 408463 105937 424662 366364 559749 716058 56299 789038 938963 283234 209294 996817 215130 665490 272445 114686 58279 600802 132975 846384 792578 798298 686131 222087 703740 991297 323728 811755 116500 244054 850224 832341 535679 917585 623365 561451 87138 536982 636259 636620 172727 975703 426576 270046 12603 109207 200666 71459 183673 781454 984310 978386 412868 273557 662427 464831 169308 873045 377052 788685 66165 700360 755456 888409 409011 665237 807293 376045 686538 188969 662568 368980 920486 623911 115362 570579 605713 871905 658021 997767 152574 110912 966847 676924 221732 128955 839952 2453 908266 220099 228948 236140 881625 508759 117948 627237 348546 563818 220888 718604 493267 389870 295220 605160 29921 914264 743904 18190 136679 243327 330081 54915 97444 217267 568841 200048 581535 579024 553769 820978 451569 504130 465546 560348 777469 551852 99373 843992 805338 505350 359322 338560 374802 434645 311406 986986 84753 767375 651931 781616 364496 57788 909768 571859 894779 887596 704399 919818 164890 648745 368628 318564 49034 594380 578620 457803 117920 670284 570368 484069 54537 61019 70035 327288 642789 279960 246425 162355 816491 776654 536288 300082 340002 714012 85639 513106 975680 984790 459927 141087 280142 403596 524660 211068 570367 195780 468588 215892 952844 856518 121705 112904 820413 119294 639162 786219 480173 749469 875377 407312 706346 689633 310149 73363 384913 915514 424055 641 867709 818625 488322 877250 978451 253257 896638 235325 538742 609450 632399 367462 21764 67441 958003 218810 55471 668794 800360 598317 706871 35587 681860 225240 952559 95105 967865 459668 87081 53107 390674 684851 440619 826851 752944 496030 868663 346229 391609 351306 217774 172918 782080 822582 600390 668462 301981 147352 550989 208913 276189 48385 51842 137992 789006 338363 546533 129970 46099 364727 393146 537607 934597 552592 902214 828109 84839 81062 885808 716381 577805 51145 177558 23472 73821 762969 965022 110816 78032 869125 530980 44282 535009 174070 876370 443853 601129 480391 2929 570397 311351 914765 270724 325716 50518 608457 319285 370525 981215 914159 876930 256913 831035 426935 190766 23800 708153 946769 932861 894430 322231 177256 718828 596977 375153 50131 105027 235073 533822 900451 405834 290069 260466 976463 440778 964585 863802 989829 756614 805467 157494 815725 374551 501328 511057 701688 865433 596315 34592 715010 394348 684076 606726 618354 313965 305882 261778 496697 101074 543896 575282 557273 705498 22720 624097 899888 344152 32250 550500 644632 421047 294429 843531 246843 665572 912493 245902 702193 335541 711634 304064 768257 937681 399080 170005 446942 927725 746975 366749 754770 159936 656883 980882 792302 346479 155673 739455 419388 819460 48982 312500 609008 981193 958572 422394 729297 501732 616273 363132 565851 756952 146568 866947 414960 586539 765123 652849 982128 127169 141582 550162 407554 60508 149562 510642 837770 416858 836085 903872 689060 389386 221044 696214 806752 526982 895406 866397 5009 482580 149661 528776 572781 241311 859465 532127 826367 934418 553463 70800 745109 496672 145361 143921 772391 87559 821892 168292 552738 395386 488813 748641 732297 261577 669305 67013 909555 503675 87334 416934 690673 572515 466374 395782 602431 741086 595495 57335 920024 414311 164999 753764 889486 170820 357678 661744 485805 973460 597165 484642 912651 478463 578427 854629 468121 570467 437230 158010 635401 73074 66126 27663 956549 124833 232066 988427 454317 20890 9504 246656 832865 333417 571377 683644 365304 354535 530799 140571 172870 561642 516807 242199 439074 937372 561855 222439 832593 413282 966397 539359 377674 150449 335989 35271 387223 581700 540586 889766 111561 853744 517349 486834 945152 410813 891042 647238 920849 747688 634191 99094 40858 965147 744365 129548 311315 500104 345898 110721 544316 376046 817102 318530 190801 295016 972933 570830 769721 161309 835843 296729 609323 859246 217847 671110 499805 211372 955505 784785 249153 793339 323398 571903 543113 683783 943720 958956 124360 326125 56507 173912 267129 902589 427462 814909 585977 172278 246264 865274 774131 334139 540914 523350 733631 534547 287237 783502 155992 632676 717836 192774 138088 672422 196914 575808 68186 366031 930722 178209 864809 584940 399964 704365 926333 653058 273047 656981 981660 456176 620516 190096 75345 567301 978992 371823 654128 372152 463058 814375 399569 191382 522567 206463 990641 452659 889164 115832 616890 861628 851574 363447 184251 670336 94098 535323 850922 35434 726684 47024 673408 784892 507172 501456 951627 328689 881936 403668 640369 461465 950749 395523 325095 309658 569560 278156 264690 490987 400646 279874 934889 643353 690077 496686 80660 928695 545947 250154 167984 243265 682035 246457 34514 501942 575596 225384 426235 999792 904045 730314 688427 643374 614992 601433 577302 792199 640044 238955 923628 817555 269095 851524 280709 371382 51536 830708 152907 720322 418770 38552 844047 632747 382624 36833 801092 342021 799783 266773 248795 401791 169679 835377 196108 509506 219237 467524 563212 428708 295736 38100 937160 894543 954309 228637 491497 650335 835005 342237 940534 1707 780921 989803 795931 180254 974068 578352 534579 860425 925387 359224 935714 862935 801075 261131 649422 985765 964109 55340 485433 161580 349510 845700 424613 234779 537107 319625 849555 874919 347434 338629 663721 540612 920829 697245 647003 221317 390040 85700 57426 781325 828441 29562 840794 157436 220382 145942 673106 654969 937317 912646 880066 282696 270165 169887 68182 107896 200827 743372 76874 177861 179736 450067 909951 793712 876914 219743 342307 818733 236667 696759 854787 210328 300725 836299 438146 456002 57352 229325 291732 395283 638483 451969 37346 889686 919859 176742 264018 451002 461269 832423 161862 451955 763913 377422 622421 607489 830729 649026 393187 878256 537127 82367 238582 157847 380060 273696 240165 517725 305012 976061 628193 160128 384518 362923 129241 614754 100922 506437 57074 980629 459394 139308 99373 954776 470061 767842 233756 310286 468923 220491 330807 428352 984642 940758 55793 113299 286080 784675 39234 562823 418423 195165 339221 795830 80841 479690 999586 550330 607260 364275 984507 38719 88993 710384 608 315078 929614 844410 695661 512474 209007 469358 673291 627349 81968 788124 586470 525301 158292 799019 284137 31626 807530 10460 550650 217070 387540 199890 274545 172898 710267 446839 852043 238936 606275 349372 223473 899321 294302 928852 582464 188989 80554 524488 587964 414739 666159 197099 770232 615596 141487 954570 459942 22724 133595 994860 356731 792073 152291 127151 547814 392573 319270 227547 882910 484119 184446 209089 55246 365574 46126 579870 765950 804785 145373 141558 438061 339153 990783 807420 552264 160697 847394 780344 128502 880979 685776 493026 593154 204225 532531 588228 159399 164989 579774 84897 186080 421814 169044 720982 106518 13500 252257 76945 841178 267489 44830 18691 742147 55842 255866 979669 627023 958226 285478 50781 474143 311700 574784 661030 539994 468297 661518 26321 779132 146509 228240 809246 377743 319158 168675 997210 97877 566211 341709 900200 603334 942420 915623 660034 143680 221330 222946 331936 168964 697981 187787 588342 740013 281419 107811 787962 413175 836343 226391 24171 276911 295773 411693 641268 944633 211692 628483 141247 135424 95365 290496 589879 402946 738686 877523 607386 421027 840099 483572 206568 124757 992400 572474 781217 109564 811239 588169 179433 173829 932124 989408 482408 306805 468918 649270 319717 94480 450862 616830 800632 50604 173861 408731 743831 416035 619975 196903 849129 2106 399398 322484 45801 256219 741419 559613 710801 329004 698580 736294 451263 321703 385744 490885 994878 28177 407755 413485 97960 999320 500953 624427 904066 889710 263580 387410 605930 278374 734564 429557 160567 330645 887190 285629 342858 924337 756607 156239 17433 255614 966563 693071 963278 191977 798791 113029 996013 531594 928943 666667 13831 350931 143179 879454 32226 220449 792283 572745 928453 440720 443292 179253 761320 177481 663147 616704 986467 119435 562051 152789 608531 407926 995987 368116 761366 182601 143795 288167 609079 169871 501347 258621 774301 675146 885462 870707 857068 139993 706305 427834 753263 271200 88641 582797 419354 56036 607316 673897 370709 994087 630452 745933 517185 508920 813931 430725 612789 882977 578368 925421 164001 52407 993618 845431 159387 952569 444936 796581 544829 876129 615767 84716 265982 25202 26658 196631 494614 822230 873949 432339 349767 793103 551229 628328 979069 613842 792793 404681 21071 638046 47796 730862 799093 939592 622336 54585 352103 632957 422782 100569 420312 643468 572310 605527 661649 520137 963064 631785 246912 289002 712375 602311 143682 932273 426038 95197 442303 710660 222632 125370 908175 207412 415584 290438 145404 948842 584563 104053 591601 92780 225333 450502 461638 277013 762048 170872 771682 113185 791346 695759 722869 512829 431932 696022 54002 221089 235013 64801 988048 45118 468332 299892 841940 154014 561475 396556 876658 157302 737664 475347 891371 835906 957818 879526 405793 14603 336404 10890 985623 656083 866124 408583 348915 940496 561521 482571 191595 2714 620212 339294 502169 19483 773408 444623 386889 88292 969213 821297 785952 330589 790676 47207 692429 728564 101857 672621 743131 779695 421936 257613 437195 571216 522489 212110 261686