864 354 807968 548518 848833 708719 559967 123348 519448 630425 464643 199621 797571 733825 703555 475807 870795 919755 339822 115121 440679 74603 855639 549011 709936 685850 31416 414504 643707 838690 428370 793729 661081 864461 664574 702080 421089 560647 207550 684482 511059 517311 290199 195479 94627 460084 871121 851775 597161 553605 40338 186875 401276 191322 528983 768993 963212 516373 414491 435910 53965 96877 470919 947291 891349 35025 721847 208691 551391 135344 796153 630447 436364 690604 780200 791934 777557 75304 945237 325956 45036 955586 396930 35293 373116 441774 822125 159171 870212 826995 447484 265427 852917 61726 689119 450500 789595 643924 947339 515450 878737 817957 886149 736803 463497 698621 823112 625609 945638 658786 596849 911100 740109 752491 351479 665203 71809 665495 630181 562048 6156 993074 152764 692711 667464 111048 681227 674066 99301 999784 468065 910614 957384 357667 265025 545486 376697 303952 405257 604969 729774 357126 200034 947467 690312 979031 426474 422951 991251 621684 348987 364945 605770 759972 515241 645202 579143 22399 676585 222810 740105 384996 106110 416741 432917 3525 552544 494518 568514 808146 118382 63990 983203 101939 546369 746894 234965 26893 57751 707539 700857 902009 340672 324111 444593 876413 727091 877656 78243 289387 757067 35092 900254 620441 80649 692075 341844 377469 361490 750706 533022 886012 339942 393094 306988 352833 847500 557215 425045 121311 369248 517499 137869 446481 243254 63241 616333 736791 681151 437017 947105 821357 407740 420351 293120 177643 968171 187961 475009 31955 619838 153577 428661 612181 612877 863695 83142 869876 336062 876345 270462 478592 576080 855045 984407 272799 322910 802918 27086 292277 102414 779697 707106 488551 221389 261023 9399 354172 229512 84287 466810 686814 743376 615140 262757 748492 264430 989828 753235 726430 930489 733866 967831 37825 918255 282578 887526 219379 876612 365803 441094 578514 802416 178284 210826 490048 135878 269935 108292 363227 132334 667394 692213 676257 376105 144871 606403 374838 826238 630126 468060 780174 844933 700739 71490 66322 738842 108746 987860 913931 362303 512877 850485 681351 169684 882217 528274 171828 114361 364402 106699 563311 428300 288186 901570 807199 930170 258779 263766 801110 158473 221150 758171 618338 870716 906932 948639 791146 861614 794701 292790 78566 526151 321532 790473 365018 818410 950583 668910 62389 75806 230033 628478 43861 470319 245470 945941 26300 414911 823833 58289 764968 694364 985209 282404 657030 368738 985308 923776 717476 494534 225145 506060 10595 142795 20551 392555 577021 800902 363538 734486 769942 240780 293019 741172 238309 11970 502346 905971 728017 801574 218130 381858 386753 991859 849105 26471 680599 126760 546441 132745 410767 349615 47590 726150 496773 401864 932671 878553 385848 883204 229911 528098 835234 324932 700598 911900 308476 829319 831774 833162 462431 945328 643186 947905 348038 428716 396949 687870 827479 317516 428876 836890 249709 741090 437787 473737 502419 947225 75707 181793 250706 625880 476013 79295 147156 73738 343467 669104 969150 869677 996786 708847 724898 873404 330683 218695 819724 89610 849942 584527 161964 104783 204344 444261 527429 554522 432859 758067 702373 974802 919788 670310 596185 38825 954474 637308 694609 188246 234416 992046 55093 556242 221804 601476 386616 208338 752299 996335 510875 938974 747262 141496 497001 808245 736771 506335 261232 895736 462667 727421 864582 191684 272844 887813 267130 788750 305233 940828 782495 832194 387355 219604 305782 284917 38949 561298 945371 89118 141977 844334 601315 362489 912711 336567 911342 591108 212642 93978 344304 327617 913879 526497 75842 309618 360134 767430 973428 302129 624876 147425 116902 781189 492671 514909 36152 846526 1320 357574 271663 211090 263290 86868 903486 381589 431015 948936 201826 395954 68170 674988 293778 393966 988184 568084 122053 678692 850641 13214 246840 714186 275620 783655 547913 417692 432573 454917 806460 1371 508689 621947 302203 402269 463283 419215 978915 235615 986528 612223 210691 961690 444512 786851 674562 306047 81479 879494 43909 200713 49242 228639 855444 752725 107189 234430 965324 864040 457830 824841 155958 345919 945735 583124 724000 21350 439258 109497 835280 209368 663991 701909 274772 840390 705283 499414 63366 375175 725916 221609 662268 666134 146683 190320 57533 730275 211621 738901 971483 209707 738041 802426 883043 787273 342805 440844 177797 763792 443633 684913 476932 368227 655209 134279 801471 28943 467784 307293 452620 32091 170920 343845 954736 774592 719898 805187 356595 853377 254638 886937 674370 542530 112114 748446 841687 819534 559633 433726 974145 905457 84453 977742 885459 328879 983507 519779 12463 491777 576356 455714 546772 221968 162474 631787 922616 61338 572440 212118 524166 444271 844265 242213 873567 525724 543364 151817 112584 797798 665731 932920 22776 907984 712437 125185 950416 24763 17067 51008 839386 553949 632636 179647 22928 5671 181464 741791 256165 998861 472018 997840 409832 100048 339264 20618 825629 818442 756032 730383 387798 547792 993844 357218 578826 385562 296184 127991 329447 614694 61203 262452 469145 463323 561508 879347 95908 937800 221305 940350 928800 232106 907215 162885 615141 906028 985152 723141 925504 600753 828191 427211 828414 214344 192814 214342 312106 222120 560642 301363 20907 992261 963534 953447 526415 81813 84295 552830 979412 712167 586799 414197 329055 633397 968898 975718 190153 227762 971355 228496 76911 397528 67381 518123 632832 935580 785644 92204 532092 345617 868954 686367 351348 802919 613692 948332 180306 598759 721802 512334 300027 411316 874950 515292 303977 383457 127742 466150 762690 976917 400009 794120 966051 376029 8656 710706 251896 637381 144819 593208 689218 987804 355639 802707 833007 388002 582177 385942 750332 131144 167989 415829 864454 980185 259408 401635 874376 942181 817289 846641 773597 633847 235865 354376 825436 579691 531911 493691 487109 108465 582762 334038 984030 583582 43691 767350 506864 916027 328748 495552 973435 284475 340274 54902 918675 126008 398283 795971 808994 622233 133049 820082 117673 947608 371653 33128 762928 377961 851520 269980 169232 483710 854805 707235 709102 902931 683064 587727 228602 98770 76940 606918 288926 251611 969718 778122 55907 558935 912823 929805 463343 980574 643063 233012 832824 111144 241309 501812 31347 770859 463533 658280 815479 617621 180799 694503 38450 859485 622948 528522 84265 503630 466080 424787 490819 68955 586678 563485 180739 358860 663440 943519 61728 927584 869856 762671 116358 707510 127657 97080 751764 513618 48307 1221 132462 776242 256638 241040 944979 647901 87951 883708 573328 834877 714986 681680 722670 556091 424849 671344 204177 294385 417303 162499 341384 599946 542508 551858 233377 382779 468944 987505 604923 930930 964144 457668 288236 263667 5686 199388 123667 178847 919876 919671 765913 482637 32244 125359 796767 967682 351552 507562 294465 615166 650097 557204 199092 682072 179135 479223 1199 404270 527567 405322 610422 995299 306887 934639 555282 473432 554893 122624 610833 902832 984730 655561 400010 269547 976728 888631 773786 413807 841585 827647 35033 415391 820642 322858 206080 336637 726791 625021 895255 814794 130458 397035 102312 338733 712886 423601 553420 350449 576781 589846 22259 986323 480631 201646 458030 546824 442525 985440 498204 125552 427581 219819 524844 480630 778478 856946 390102 899406 171613 972157 771980 500460 123742 227440 779846 601686 860605 66602 311951 779853 593950 627900 967324 480370 848785 11604 386802 913918 224028 566478 187275 407089 887659 68981 594329 482113 603171 771096 774956 283500 572470 711878 85060 765671 581806 516111 903246 902175 656236 241403 257046 738790 207576 201261 300920 131244 333836 914339 119045 531512 990651 987309 346065 596907 281202 157182 291017 876342 580893 673084 559755 959844 811706 329652 248873 587212 658955 699317 433392 381736 327716 656724 948130 6141 169246 682665 782634 481884 45085 521306 675892 312406 113909 14747 961267 986170 307120 496510 685010 561861 735464 330433 81693 98127 91755 942727 458825 29984 180183 919215 920088 875659 385055 379777 61059 760645 866648 937834 863778 364973 950010 261002 536011 935435 737521 996872 390745 736685 713865 320176 330256 630414 738067 698915 98232 165543 625727 741409 781179 672783 350469 674420 211130 194229 864693 370481 998641 647765 191868 496947 358953 249837 188294 461895 271834 749185 173616 890598 833025 507646 72392 517829 280192 696225 769269 322730 37171 727666 895715 293496 772631 365263 497609 307294 404914 288124 591863 189513 441561 974070 359879 868127 272799 889527 670045 925988 759071 178251 660939 917791 410555 9248 699484 670096 332810 995285 666221 343549 366739 955336 476352 521711 270988 96825 906447 361722 616436 258620 3246 189057 665062 538860 836479 166781 946503 923650 85578 475324 436930 652185 538026 242061 197458 564422 893328 994353 864187 725928 494252 894931 849887 177073 121719 682554 214085 867908 159138 868227 97538 669786 522482 801993 808335 985132 962869 470021 972251 785927 897960 447240 219192 516302 324472 678675 569203 470033 629480 660750 729412 533962 238946 978387 165832 925860 48322 921183 449964 889394 270778 345499 804659 380426 160049 440210 156617 692119 948022 735469 573395 657105 688706 479851 271888 683023 338760 483162 794520 559216 215498 699245 695116 497646 149575 832260 676774 749163 897415 951626 191716 338633 557726 928757 401718 229959 457452 929519 716277 589669 787202 5910 974546 421994 411089 335198 539341 5605 229096 942855 352384 988705 933018 810044 262903 576497 433653 87129 991795 275829 994200 588970 595437 733558 277507 705771 840911 789454 638904 466977 994808 256147 391334 230001 892695 383718 198375 672265 102530 434761 699554 487981 390365 282732 25085 109434 664509 658961 550498 142282 557031 518592 398857 54946 689543 158823 376025 984392 187949 187015 693281 777382 324597 668659 930934 625392 705319 342252 281498 697158 33094 452029 438158 319555 816196 446259 905669 147680 572662 495358 271045 528265 226002 695566 236587 695803 809387 529766 582830 268348 969031 849195 664686 918022 660171 841591 489736 955179 768271 194740 242624 463435 11453 327726 171328 55251 335327 625384 222021 943232 805071 832182 986220 480737 564770 446451 326104 280066 965373 185325 532315 89644 418254 728737 41737 709826 854732 413326 241428 267340 195798 368216 968871 103547 30779 893665 664388 199856 204646 185132 398035 592878 859022 353323 419350 627906 401916 538301 102155 420614 35206 190134 39088 373173 576737 840676 814794 80988 547518 217234 532663 597106 957442 911579 699729 652664 50461 722111 561033 748745 727663 937691 342029 279681 332047 534181 572214 939148 384810 641299 739878 616350 256193 453124 537024 877953 721555 696038 861550 399218 358288 100600 160166 20987 245377 156558 738862 267677 301286 118092 248439 791503 852264 815662 488971 430347 296846 18665 238413 197369 41548 23804 880537 734714 733360 459034 744231 591298 978808 7791 519848 479481 470343 253686 507950 145220 483885 544000 145299 908638 956624 674626 842033 449695 270570 713456 76400 986401 268921 36563 534851 186009 980752 369821 230138 673682 782670 123156 849678 943021 19495 353811 650368 721470 501366 624573 309820 153761 679934 315999 50667 722621 471315 301310 527783 592292 146630 223564 771679 938368 872744 252834 305740 625911 162720 487018 432198 336409 162287 18880 552316 270849 169710 88132 284791 192909 343221 805952 403976 418696 153470 339655 671637 790239 774340 402231 648906 774028 399554 555252 516132 417340 547835 812637 663957 492284 804275 955710 26848 228885 50765 897902 798066 119478 249801 157486 707007 217037 140685 275941 603041 669498 139528 201322 769919 835919 785303 687615 366667 360466 780695 988643 551715 147332 662483 175641 512828 550082 421492 679506 319510 333266 51673 470188 886658 640797 77558 671138 186156 131592 822958 684300 812063 442739 332133 352296 838986 486490 631788 563676 26155 804016 980151 727306 160721 478520 969933 401763 495453 938391 312958 328708 745569 856125 484670 276778 289233 187064 172346 568916 237528 113600 489786 990701 970568 939548 454229 642397 606637 18239 447797 77568 642504 734437 871648 209674 50064 511359 724180 155044 365400 843071 489877 404568 459334 982382 749609 151963 782072 286531 301542 196869 632297 653386 557685 20266 786964 34488 785937 977799 954385 518171 368421 11608 3941 253591 283874 590909 869146 417529 765442 16893 304119 997461 525452 677757 213783 522151 655645 770487 750875 935153 115247 925606 494583 245079 528443 338542 426751 786834 184505 951619 114951 165132 329642 976404 904365 961105 689192 848137 74356 985925 996519 710357 451505 200552 223917 775092 576892 333623 179551 865104 921550 799535 954755 836584 759044 196850 139810 412460 206617 125962 262610 588785 264462 170817 287712 100205 300571 531969 293861 86916 970972 623838 16791 149179 563611 153126 718896 662355 843479 684502 814976 955187 755474 222805 602681 339805 408193 676385 417709 675008 89531 220037 226288 503188 494191 549996 798418 830393 947757 825844 753521 100713 285689 918469 136070 105794 24953 302212 17813 667940 7866 526273 482276 857072 412337 333140 607989 739599 331992 450819 630161 743522 816607 257477 729527 546786 641811 496674 658235 528232 646731 992349 189218 325747 656797 808606 277004 57607 870861 968244 497879 518528 365374 600580 314496 671817 351392 701927 573233 405942 627222 7256 331582 170640 136822 581165 888253 223270 137096 715547 346272 34643 68859 915107 934888 856744 892659 929621 575046 115434 708096 191742 655479 591172 85508 867261 773939 362583 478316 311800 921482 832437 11965 431566 460538 550708 163584 968262 371298 948474 859300 877794 59223 595657 571579 145089 633447 459513 722935 886942 225156 841334 154145 985366 906218 519074 905528 457882 403820 875629 687109 430174 773603 533827 774392 424009 265153 437223 227686 244329 192282 434301 907254 417977 574309 494176 161864 250428 687086 730233 872834 333197 798597 46671 701770 178638 491460 115867 998868 978651 478816 922952 764005 809713 425251 424398 824728 425374 144746 363785 315596 354203 153020 431111 167875 754143 737349 172515 575652 471840 230046 216982 643789 525206 812527 335144 850829 519869 444394 508450 964340 590027 572359 106934 618328 585140 163693 480053 406731 789772 771739 769712 916233 885912 296159 916826 250536 275838 189393 861160 875139 404892 228723 426018 821205 241845 905944 203588 617459 267827 870943 14241 594007 458317 990866 986026 31943 684573 77985 807915 955876 637673 61632 512370 830371 633842 774167 69210 816827 911397 6441 542557 159752 280945 512353 466444 88137 669527 46979 497227 398002 574926 330981 358010 256137 949207 563354 704728 337080 438288 550593 172816 834499 788401 248835 441155 445535 955231 751141 427980 319328 49484 472770 109737 792510 183915 776028 355948 879522 367939 148474 853927 72716 595437 959497 281873 337377 877634 469943 71995 188586 816343 695599 515245 358353 890365 869147 715183 698684 876879 475154 25292 997943 332333 284305 256959 555416 573816 304644 628122 893609 566915 319862 462416 647508 763417 122828 330982 446725 153181 398358 247426 74193 163713 306502 162592 925486 651574 396834 125422 854632 918949 570476 137559 432782 917937 357360 547168 227395 92616 871383 565166 843612 986068 53156 173284 491534 648882 664076 182918 759395 393630 377556 121356 320156 840099 271250 351014 453509 159367 886010 265724 307557 990354 105549 923106 338369 264049 121773 184986 787702 271881 623396 612111 10545 820359 50151 325604 359496 95485 730777 575773 972313 378844 160343 97571 996114 206173 381516 321553 946296 501248 595145 188996 659764 650502 611310 586516 550374 994258 576457 802152 233021 424615 842207 767375 377730 434779 106651 992993 413928 508459 694142 591206 520526 91246 190202 2931 989640 330569 825162 225803 44494 253495 667297 655573 895479 588674 189659 95313 296625 663452 199842 192508 948466 638733 227965 345893 837180 245560 947226 442763 754002 16931 523414 113513 519597 741119 507649 33015 542093 723356 117116 849108 810427 316801 26577 279228 580822 56127 464031 288251 464941 16936 770717 95650 381664 129224 732039 976813 128423 864591 1121 956502 52583 873672 563965 451387 859811 572749 267368 526336 261534 265305 921393 304560 32383 17223 574964 260083 324859 861388 489960 892203 739014 901585 801539 512063 298494 841091 790512 765559 412441 408459 863147 952425 164089 764320 292050 676378 910701 113935 734488 818039 63967 828362 624218 470470 733114 723397 863651 192610 61170 644155 825274 3784 726347 672346 198786 427320 76119 657750 485700 621674 465334 163202 35174 142568 15470 718954 924533 734747 277851 74416 145849 866247 619881 266605 410520 38728 503909 47790 201596 410018 938163 312815 370586