10000
0 884800 273879 925769 243366 850120 393546 888000 332034 985031 984858 547629 753482 880572 960601 396696 933049 248470 863038 746527 690802 595673 476576 731515 805464 465841 402116 201503 791760 877741 378266 229716 14882 431462 955570 338783 921460 653589 516331 55770 729275 838650 185721 597103 90147 451900 528715 607365 994615 449919 631074 792791 599037 363536 991331 226392 208404 690823 60461 558023 690109 355636 998517 201949 825895 915454 322437 974719 20167 306308 944212 386825 106952 166442 648218 162522 954517 783394 550854 431997 148671 808342 214747 58911 474387 528542 646995 760757 106274 90779 695117 301146 300583 925418 701911 108983 534131 753711 713921 361163 726084 671187 464465 852596 662625 911209 226930 972196 274549 665160 336105 853174 593786 811576 345685 591851 193518 47299 872604 513975 699524 516212 26195 903996 84299 66504 415253 840804 712958 221382 193667 274580 158633 603730 797485 634180 479102 266401 41978 601533 226519 721412 756112 707049 130484 480020 845045 514654 548967 40927 869033 733045 53251 312693 138634 841917 812572 684014 455428 246599 617927 145102 946754 909911 310378 256024 255647 511889 799063 281864 942112 423777 61802 736823 77613 49637 987056 306413 940747 450915 26167 833735 880629 672154 815372 956038 439540 767829 597784 961275 197676 836564 160704 756136 653287 742556 766930 33143 869993 196965 769386 128312 873183 637776 6081 970401 582966 383927 99992 288930 931974 343620 647347 990032 434592 962087 809901 645197 209036 452562 656299 272686 353043 567452 601041 920346 278173 931677 796718 813363 244146 285588 489629 94859 405300 341116 22113 209005 469412 922258 386263 176451 213092 835834 813322 195395 254629 249624 897583 288077 859624 209156 340348 99 644599 909645 431767 670482 715455 777112 144891 636980 173951 422432 276586 167064 319996 537273 562292 252321 8658 46577 751656 824554 520137 725027 700809 405768 94464 434471 23144 869694 850620 52594 365222 261936 903237 687287 596533 557235 353583 338281 302062 986750 672550 548442 868662 59888 131068 178772 413808 429496 612026 594071 27322 347869 817914 807514 998954 308288 539568 611240 673114 562212 687743 684679 137167 596836 957946 523997 951232 424987 50951 113028 927574 613527 22276 156800 606640 741032 77904 704294 280389 235061 614375 436525 381295 839530 205265 869248 155879 938258 173041 780962 50407 744517 439552 222738 484282 158628 81434 931309 204261 596029 939195 566291 301027 846131 725621 807061 479437 474755 292585 781433 805827 698697 24880 540314 231495 310508 321040 447674 421178 891127 313877 785575 185367 526951 423187 549103 809782 880284 466434 980450 890544 508870 931529 889016 334687 773598 318307 954762 301270 878609 173787 476532 628893 971074 41670 725711 648091 894940 550128 133629 840921 784860 761345 282311 678622 382830 290846 304295 790723 173054 271957 810892 875078 422134 3462 593272 279603 488174 806107 157869 89733 965051 51186 380004 239539 625168 59226 362400 261717 977260 228867 261587 469092 789612 608875 586481 607907 931980 498439 928804 625254 533145 320626 76586 967790 407349 982349 680464 637154 225361 615369 439546 39846 874402 505444 343602 185125 168213 871275 364770 55950 223744 871751 82775 665323 926603 818570 799614 167084 943179 628133 929047 239243 213599 257209 901862 179092 989581 518246 963892 554476 566334 133880 486385 676579 581741 799065 545718 3813 131989 659077 189667 712643 888155 644306 434033 408625 977491 789801 463813 291192 266188 646976 885714 572357 658115 403641 471616 230802 220991 241679 614028 165133 103671 32719 346455 997962 81740 466744 504407 536145 745383 458956 33388 449398 52277 760352 722947 699578 756476 854761 633362 781737 742094 821719 930758 239189 430667 888514 106766 247199 259208 592477 372660 762367 398510 209504 209634 600681 285607 735316 897228 604771 270811 787868 577854 550715 39154 56459 579662 819441 214968 96899 605507 505532 157522 42908 405808 978088 366112 102059 518332 93384 774836 858644 528201 489186 555663 878439 992036 380810 704571 83987 230567 818233 735087 549493 143398 120076 552300 126612 921586 587787 798068 720677 393495 19320 878245 617413 669138 554624 93958 283492 159236 982955 156989 919205 639175 94819 558408 473534 72309 643788 93044 175703 934231 552745 47984 68055 948627 906256 469080 356329 726636 293960 630199 254397 520714 19726 188470 307325 49088 531010 175317 695325 277346 956781 419490 762655 149761 467924 331884 108485 516595 873601 894369 892726 746721 30064 681866 718257 651055 191748 284640 284785 254437 956750 183964 995846 353201 547989 894453 154311 835541 314930 399136 226741 224969 80892 722419 602730 158103 425399 586378 817223 384513 399360 725641 642175 651340 859799 151638 552212 608474 199498 229125 425118 618900 828422 99599 910496 770124 724158 147424 853584 390714 660788 920674 117423 634722 672227 463036 904817 213824 868429 605477 715369 104335 756707 594819 137140 868913 286701 622446 719558 49924 285554 462728 284986 31811 441480 340395 780907 932628 276331 710343 984641 535356 309202 661527 3767 210653 666984 57726 572275 53292 8030 964977 525564 803591 500973 865724 222791 386431 661392 551199 976036 166824 534409 873419 865269 583267 737533 314669 149235 847580 443572 464045 702871 844756 630360 31344 941573 561131 158639 957855 636725 102568 551489 552107 308930 533148 909439 990835 607907 570670 665727 321120 353467 805094 388739 644480 691259 532006 231952 711438 949313 795351 680646 912964 122042 690152 266441 936523 462526 822899 225515 162010 913917 493987 908898 196255 594066 945823 282336 712277 4894 704074 757530 507617 168643 380534 837764 544249 102841 560533 200103 135885 269225 788245 530028 492005 850975 234422 84561 327395 781594 446894 511598 668509 831909 798764 535731 888519 696167 205062 627703 974349 832874 394827 366347 233698 499690 786268 239568 323739 750560 141957 867153 716667 75496 832234 5331 406185 818590 113647 32693 943920 386140 919195 909451 417498 146078 792739 177557 198007 462489 921983 995746 713766 547714 925939 127711 387143 559483 364621 861684 27371 103886 270567 255282 262801 230493 34464 873274 887513 968954 753243 176928 219676 912062 448583 283171 20291 504875 5591 281006 907883 564795 118726 799482 493724 333027 56731 190306 702143 416868 447499 840666 372058 483511 792180 145520 647288 33995 373222 659077 73494 299945 668338 738665 746717 718506 807316 368029 845316 787739 505300 976459 195448 840318 758752 304808 918957 931833 423754 287345 513682 781727 996503 225778 149519 476273 355141 944659 241527 253033 301554 218800 447958 300712 794989 442944 149553 488280 275027 371993 685846 870851 484520 590014 843198 966789 500596 281821 501847 985438 97482 842827 508191 589658 588231 538389 243283 169859 178756 964966 266766 389599 108825 818794 253356 909923 533003 746643 191071 103647 694540 459883 362735 619009 960811 367026 739650 137553 789464 537849 468748 729386 242121 188159 540617 628945 43363 232619 70655 127904 384792 54881 831882 395892 747213 932155 940307 454528 15909 268870 1969 907857 127619 332312 324293 885658 64182 679091 352470 958557 217815 929503 410414 998492 192787 371989 272641 699033 643016 150069 211762 744121 820286 70075 122812 495234 445607 349155 533951 828329 834300 324125 249276 574957 834673 3025 411365 406593 51260 593922 899387 959618 720258 764770 258414 602034 820013 191761 479027 605210 630928 20408 536602 481904 607499 107461 319949 243027 755385 586213 279190 987154 778909 164334 340344 559507 675198 101166 21946 166469 15382 624450 868611 211983 992277 151934 96358 841893 247013 696953 793298 69049 56519 968395 373524 136588 439483 750519 471420 138998 620499 777037 958745 980344 155064 319965 388870 126205 224999 751421 475818 3134 134754 22216 258111 634145 770863 975298 542328 733352 715720 559454 271939 127046 845698 455757 822031 38370 126472 564972 573080 302455 336885 385214 94414 403211 796256 642280 708715 680541 174387 484870 45293 231803 877926 501438 231997 216475 853299 244313 451934 67510 547723 906637 492552 405952 861725 908599 478023 408651 359535 835744 810943 118902 935272 165856 69635 688847 441216 242922 725071 1352 928060 821973 957154 684973 282178 142047 357746 82014 586632 585145 844352 69796 129128 461257 757571 467878 804171 145489 789712 8761 703090 73019 211794 977438 442288 490459 820149 859485 132671 221970 571882 291217 118210 289995 379442 235010 326996 597650 807296 964581 749849 212401 91641 370690 883969 325097 652549 516521 210870 779913 117245 154681 205959 64427 591486 168867 498397 151355 888332 42770 168953 435648 458975 445052 16623 116848 334291 367760 714271 190233 997180 157989 282073 979544 158163 243513 130413 366845 959730 588153 396871 468220 111537 782495 753276 755326 148974 529549 49990 752875 732372 717987 138564 174876 206952 128577 12765 693015 754185 872997 835694 973131 199540 450283 65818 447475 261078 495661 261459 526176 319794 277616 861480 749474 189424 323218 796187 598960 812288 190662 963877 42214 890055 33776 255753 109309 928157 14844 842696 802927 36328 702855 449097 567710 79381 401747 848656 979590 923767 197487 740418 487758 221606 693340 243403 946662 656461 425884 165357 760412 642667 649158 610192 632688 263283 50776 657222 494320 113859 252906 676582 69239 802200 942580 252983 480074 15703 229811 73368 392701 319381 84334 316324 704060 899561 672217 65696 709846 749315 438133 8010 296833 417746 456279 24048 770758 109756 429447 520036 485467 453840 354120 694899 929196 850452 667602 351853 606418 736414 824650 309494 732185 798001 772548 626166 17431 645481 647107 375920 687138 979592 560512 609783 25982 701270 885245 264271 329358 497917 277721 784740 914204 187972 5812 167024 8170 89987 163552 234065 85325 131128 408483 852496 326976 489844 889140 916269 292311 93429 411883 705121 743522 421388 968973 637930 330620 18323 723430 347826 113682 486092 998882 799879 632191 393204 812587 155948 402966 917511 340597 225217 121135 147888 708463 5975 7877 340837 918687 235894 649355 253863 459833 655716 882698 37783 159251 804069 622319 984778 130394 756080 135212 629627 729134 8713 503750 701474 172414 558007 492681 741699 502259 432221 543419 200472 527792 807233 223014 609 128157 166544 776801 135521 271242 342451 861280 66017 261588 273012 626048 842708 711536 717307 669100 382629 627469 39923 932332 273586 436646 825536 44112 597958 990572 732269 217183 236399 858561 479939 468504 568639 961849 843811 528335 309836 645416 541692 146820 956940 629183 302599 100962 728707 25949 285045 883670 55464 23145 338981 219673 270049 363164 419904 520022 896847 45937 365197 996976 48276 721874 57949 570203 655691 492165 130934 829014 309195 12533 95626 97504 388509 91777 433839 976551 540283 381908 421330 522334 443294 782430 167136 95591 486777 823027 62658 283640 809907 230842 646016 356608 905024 869482 483267 195676 528546 394193 81470 423369 485795 901755 882804 184186 642795 110111 760120 163551 505734 899435 535147 863209 715796 294748 67640 319826 109180 433395 318255 13080 804496 462191 142005 158030 493484 713424 784492 104103 420661 275449 563810 93269 47296 899379 88090 978744 122431 815023 835894 537937 166220 668295 225502 197066 586596 733102 734835 520519 735754 169657 124400 77131 36990 721515 372793 267799 862377 58485 568998 80680 657426 409922 369374 902323 444478 14003 969495 948963 949174 185008 975184 467140 954208 665647 152618 553654 347379 662028 187727 957117 367698 586448 768294 684303 541642 435878 261837 182757 601922 912433 186619 764921 639641 355448 227969 509137 47434 592612 246751 687420 65461 695800 921512 233157 776441 106971 25487 538436 567422 245907 838493 125897 137107 755124 57291 87704 716895 995416 699667 707103 230365 144840 719190 721346 182388 990951 482151 277901 858187 221994 86204 285694 369049 997549 277047 977790 42393 113481 251808 189879 228996 426919 931124 834793 244548 687387 192048 31536 340333 648067 45906 105695 718171 406640 630636 840002 459101 205552 182032 2118 897639 503654 609287 58306 282944 644254 637961 946061 324345 757813 928315 557696 58613 243659 188836 932052 135253 537390 926448 753112 914899 923465 563593 259053 289219 661097 527821 929537 716053 254002 523511 140360 883177 980526 596005 783697 21974 694706 752078 588531 451352 681088 289163 311301 613735 113684 469991 416391 54549 578527 845844 631106 220611 26081 43291 79316 452708 468973 605730 672276 478741 767982 865607 625810 717798 708555 795055 384740 498444 698139 940525 426645 892143 59162 235612 419063 155504 694245 412735 813847 808711 87203 679752 139389 100543 379918 408809 152736 435539 45701 855029 313509 348928 500406 818363 73482 639781 114443 907061 500443 592950 873999 444251 768237 413662 113107 796426 43503 674698 893988 301911 838771 579547 375414 325801 806419 610242 290075 258643 369943 395834 210501 335791 296291 710649 776249 925335 606222 136548 939803 156902 916966 289707 818231 448709 513879 234384 644489 96955 453416 208638 131554 211099 516145 993157 298464 776624 940841 532224 226898 865416 13336 11944 876102 198077 173387 281158 444487 945827 392095 49525 541872 374408 692841 352290 146290 769297 352250 986289 267845 624678 160431 460954 795749 214844 891814 447807 877549 291789 841527 832605 680876 684759 970954 399749 911101 551194 291146 999736 172682 877284 449161 213222 255260 942457 168384 695594 493123 44128 639244 447076 743091 979640 233892 282698 901995 808964 637523 476909 740904 456067 112381 318677 131305 429631 351626 478180 825182 963590 126804 856713 9351 174362 850910 913321 266050 308578 85602 342757 344045 765650 591792 64809 963237 307994 566407 330301 105160 446909 880605 570524 211350 438759 842847 827884 78962 849865 769777 437358 632457 886523 537834 623626 935293 160863 466726 640759 425480 194757 929311 852403 771017 608609 235055 673839 107299 297913 512333 516162 162075 916822 599667 866935 797596 895766 579582 886093 749090 261020 683629 53380 720518 671819 836409 205069 845182 630326 724032 198104 485520 935174 285910 254327 913919 766088 438289 579225 227974 727913 66890 520556 462673 275217 458681 519059 209540 676692 329236 913498 938595 207746 620559 965188 648274 881695 994776 224811 532460 765561 965797 968764 874629 313933 159788 882223 190885 828922 236537 693226 212399 944424 773903 191760 804611 62485 749887 477330 873448 549075 677344 133382 875658 424279 766370 409037 431807 803252 263307 131260 845872 756049 530264 550611 241897 370227 598921 926444 91435 671631 233264 693326 287783 193122 558316 274562 926270 520954 666650 428987 712461 449398 148597 631242 420653 922659 521197 357498 30840 738478 486422 25865 835211 503504 307751 709382 328766 49681 195702 468129 468912 258365 29527 768400 722982 83082 413535 454268 782301 877561 106286 827481 266205 787678 124623 470409 979356 587538 855170 516415 582860 203514 655532 244567 595544 492992 703859 638673 631582 683751 153462 256684 134919 468878 151835 895807 250800 714980 440583 987802 940641 744298 741678 353951 477995 573540 231063 718135 858429 455597 936739 685328 718508 243372 344520 869200 636072 674432 902757 808065 752403 717473 294130 949873 45966 433043 547347 500989 472720 624017 262954 924638 242931 438458 20332 584051 171593 264454 10252 439812 6787 257673 700116 583134 346124 580057 416614 21529 456939 215647 847405 521118 161767 22251 373485 653045 760863 411993 975234 747711 75617 948491 445813 969238 316700 748502 360247 912762 710107 198944 142527 735911 160310 123242 437393 163902 56119 807972 675490 858558 96381 318122 483837 893013 840282 646058 555901 190060 777311 122501 323508 810322 309765 431376 938295 871583 537848 220515 655616 391385 848077 504699 304896 603164 620145 123548 46511 343654 82944 910125 787338 874377 420290 113567 871328 527235 297387 82120 175316 71780 372204 259520 766386 483761 791499 142972 609658 718850 707016 317314 448075 133867 550487 133572 347447 914581 743304 262353 504934 157126 836033 132760 559853 295266 476580 896881 170178 580947 679158 525198 74667 10419 986639 200462 735713 845455 698998 208816 252509 14863 442076 495226 812719 918421 750276 16485 880903 831524 10778 959364 541605 868718 26578 545449 66961 389031 266802 498593 997539 198259 258286 592733 952059 806360 493032 529102 887809 613581 213630 871486 348573 932736 968788 576667 213853 57744 559370 577804 450445 888944 790821 583134 861997 217788 618744 392938 696233 346633 697430 282992 838368 625012 485563 654720 157350 452418 998569 57888 449140 663740 507228 627629 823754 168616 779890 774301 466981 876888 812210 648606 849959 144504 528303 477091 41838 515770 928129 357962 75869 968857 769280 42114 763561 756201 19408 755929 724228 857630 293894 493291 859420 701709 517705 409825 797947 831381 121452 540910 584257 788273 390100 559078 305723 567484 279866 803978 862553 611030 881488 286461 295993 828380 329832 400768 491117 46460 527970 347906 73436 735615 972520 418149 815415 49255 214886 252892 139596 652210 961291 283060 504869 572625 225256 559358 156406 481314 894978 855088 146536 554391 962743 815673 329009 883648 631492 690816 136228 778970 55381 598031 441406 190210 429622 848369 93559 788831 650631 440691 206410 523360 875694 45446 615189 615936 73636 732769 106649 814094 190490 930225 673287 85692 854569 940512 860669 54000 954543 259134 642466 296237 387756 71371 529728 162546 596520 679247 745982 756098 567186 504580 185317 871632 535915 534196 619793 506278 737337 815936 975504 1569 402187 405965 878945 114459 23605 354709 128688 858200 993939 357493 841571 817588 780588 438047 4352 853046 295222 78135 532334 145459 578590 395263 670392 922644 90863 582407 756234 250222 911931 692739 226689 769731 922365 952114 670265 52351 712905 956616 386521 557708 173888 532280 813146 388177 171179 727382 23677 884941 334140 70216 627504 454319 175590 400757 299122 933270 79895 244450 119078 842092 527986 982544 933304 131923 567060 587741 646306 333834 40312 13174 459966 870336 414325 938993 787506 487521 709873 702459 985181 203505 24191 515944 173196 737154 284771 166063 318640 580208 308234 65257 494026 739965 842468 475633 780044 499241 43340 858465 545714 401205 250821 58028 839014 1901 153943 749916 24339 312535 170683 511618 527534 157999 255445 868931 31769 821120 621482 774815 798926 535033 773624 892314 866973 635679 364831 458321 385195 364232 478310 423767 776935 27742 750405 777097 908801 982941 168341 35536 383545 12026 415028 303961 279433 319657 219432 197772 499630 149866 81249 404800 445294 307466 957018 170204 477499 313847 231293 130391 54561 306543 878064 749856 172102 461940 258939 276869 885268 793956 629920 121519 622469 320360 839765 687530 659261 984684 316303 40676 298774 347231 241214 836300 468177 941996 425031 439907 949610 228622 861988 190462 881890 293191 235368 653504 55381 444037 406563 134320 438177 790467 813169 457895 935266 190667 915442 467945 876352 160163 886555 770012 523475 612683 509001 803368 585475 185726 108363 554077 377594 386859 765624 893095 576290 663986 215333 149635 652051 473888 365992 905712 494923 87892 437364 503773 977986 403515 605981 730094 265952 665800 277899 995233 73725 219668 855045 393181 534994 287269 547905 108080 616338 477711 312998 452247 162578 770504 448856 27373 245213 738522 86630 942257 424084 319175 80977 194525 971428 985649 327616 541107 972001 126611 717738 163329 102064 288313 208558 583017 639684 595399 682473 581798 863979 612517 208294 73481 515140 982775 574383 341191 836578 456931 991212 434204 195380 171121 181606 965501 604703 674811 259932 904507 895226 622652 324035 102547 721272 484429 952023 279081 553177 603903 626624 172897 977843 484147 978747 353273 534667 615030 443590 481802 441455 142623 797846 665055 512767 397333 705432 314464 623880 738770 75550 817392 684766 7639 307696 567203 16017 164457 682403 138816 574024 993583 401271 288025 152817 168739 107098 532158 342851 82018 274311 493828 324266 586457 887996 819103 990308 924875 671030 155915 700294 912453 276990 144342 291649 454600 930118 133436 343608 353173 142490 917113 677427 14501 388815 831982 73768 408800 837896 268963 607593 509847 677708 20538 285667 195916 971813 956459 636498 976667 827326 597680 788475 916405 80408 933097 968924 399169 935522 337389 331308 123596 206260 114638 295546 665345 659559 895126 225041 471082 836773 442871 282803 950411 683704 789171 979505 878975 138518 903294 570313 62945 164075 78720 607111 249900 807837 740603 57375 806050 896931 785731 735585 762945 539163 929195 456815 98096 255076 327586 155279 104316 737171 145773 127141 573378 52177 377327 506528 358135 446988 758870 958393 313448 923355 323011 3106 4951 864943 935231 611336 718527 608595 986923 142388 641135 489617 591869 704295 142179 61508 442469 188038 672151 945377 934503 425643 546914 288568 902102 371475 642611 718602 687974 77235 603385 712880 932204 489691 589672 114947 901711 693641 586779 188525 514858 490668 969587 761480 767476 191120 859782 612737 803489 207346 615058 186611 563153 426394 81411 888567 763254 546465 396056 471081 687622 835290 675348 982532 946303 315827 94431 580157 812935 759191 870058 733717 486158 262530 945453 112423 208877 783815 262112 107847 460429 467831 492044 622561 467843 71656 147089 872641 411933 328208 654543 500696 959847 159881 393379 275815 925265 96244 225480 254000 951925 363754 297333 24977 95950 113374 326301 999239 372655 304721 318243 100226 205230 831056 622268 357271 577744 908713 896162 210102 103354 430277 949408 556638 616282 131421 313997 731455 986819 764052 263572 268492 352322 175779 489859 876700 604322 440919 48763 517087 764075 67267 48701 286158 129011 794180 394978 587836 99871 595170 426140 665867 304079 99119 836926 147130 636454 182092 638921 580061 158279 728693 963301 912653 829537 3658 43893 556179 768141 38416 294897 117190 873308 28166 986015 870536 108401 304110 988139 742844 840514 156545 294445 983466 134198 167607 480123 192620 554153 321686 130639 172600 81559 926380 508319 154145 332691 317416 624313 837789 16992 506881 176605 308028 184833 759716 793814 446437 665759 5728 168647 567985 51595 817842 156674 422933 870338 101674 639422 75414 890668 3470 943504 833383 171980 245638 866245 820431 747096 674319 814430 182677 696424 232123 891370 269890 563079 515849 188278 58786 914525 880620 102734 420512 904691 383749 861758 212518 519870 235335 352859 810827 642158 900910 922930 373753 848758 720940 981505 712405 348956 511936 774735 57789 209772 74719 436844 601914 223470 605460 844527 352046 381563 473122 572718 514198 965298 9623 722736 267124 450637 681670 142412 893658 473251 203343 122056 861447 972836 127930 501726 780228 935016 352541 855046 621049 692354 94158 902477 144084 473545 953075 393219 338856 566102 99206 915121 818739 866484 496022 129420 642908 836496 426317 52859 194111 658695 468199 91294 855883 640290 169020 625147 865790 969734 932458 304914 714409 72179 67175 766281 289548 378551 2575 188169 985383 909830 51431 840323 371754 905179 121358 441994 230329 708435 498985 215806 857219 80663 245729 882109 716950 108454 201537 870292 890145 823955 892425 744886 498278 431542 138881 317754 753754 289708 24118 965744 374492 62504 818698 669226 153782 361314 687599 286987 860696 568014 22951 870565 306933 329104 800418 453181 689992 845380 411404 791653 259999 472387 344080 407097 253566 668085 252791 368807 993774 919134 495504 765169 286966 813081 103971 459541 393248 141844 2371 756715 65210 164420 79275 482560 222126 825584 486959 999389 580253 75550 706698 238368 594939 280501 990717 67125 183089 808125 982454 213648 357239 429392 45770 886764 960837 165023 184655 320898 360420 492117 899070 88823 188944 687229 242038 227861 4802 571029 898830 731108 748896 780422 745985 109257 260529 853551 936416 739997 884689 798860 340025 923681 737447 372870 400003 282493 393854 844621 801525 850609 339757 465995 79547 31859 802313 617977 954976 734125 880792 513884 928526 208273 973724 533692 343479 335966 884762 755762 592126 856532 225646 989955 484697 202930 972101 102843 753218 673921 863684 517201 807194 968354 154047 14921 378856 59029 650183 552367 720997 868193 977891 424 969079 947250 82993 861407 536758 673530 257239 496007 295547 554253 548884 348731 699643 220268 122090 847702 61221 602744 2268 775615 24286 471728 120652 353735 607815 200255 430357 913496 18086 276585 797389 660921 68324 492162 44459 154563 148056 943871 872538 289583 33066 926585 843754 385745 522024 534276 940480 465412 340805 808859 150951 471146 657828 153146 92902 630538 99535 913478 247599 33999 286024 46002 298510 421777 272134 825186 614473 612770 410541 572983 911949 850803 79162 623103 586527 69431 743661 589386 104642 496429 384221 694013 100140 692925 57424 223890 567275 451082 155841 227368 388351 35870 730778 307588 784358 400148 768695 413465 598444 102803 691449 854241 271532 199671 662264 373032 459644 589888 445428 357979 5170 874860 588792 778916 756317 243083 662457 969580 442370 358670 289595 256887 198601 714492 313041 828178 379625 103069 847494 932463 324404 709125 265454 697600 207579 599203 700011 959761 253230 823247 273857 460270 839079 741776 616388 741218 588401 500758 208209 388656 763501 885937 743506 442058 262863 333324 716891 390518 46627 837290 745428 267832 122056 86531 828077 464133 423788 679415 744586 20226 685683 266328 407360 613584 235310 806493 114877 731344 35767 268265 966808 150166 442507 767193 365759 521104 757263 838824 476915 916197 766041 599783 148304 578964 132716 716560 836151 302739 107773 256961 694147 116212 687432 96756 784645 870335 973563 201140 129496 301660 776806 160200 978826 976553 297919 26198 814947 425554 458315 404674 219159 220179 675505 59360 514952 132034 572283 399917 559628 892490 366334 789340 950887 941034 674716 340906 964109 893366 93060 207058 4643 990632 928565 570777 833767 738791 591958 507538 460574 734795 240274 285187 532493 134639 633911 664398 438686 930303 88197 283439 201981 459403 593617 332635 68624 9682 789258 806050 450313 147984 649741 482968 302615 171207 152599 72911 594444 230074 557389 460254 160883 122556 327261 648497 939986 390402 499308 700863 581222 655653 818984 157201 54173 697476 201351 458816 500718 775657 583706 494821 244108 636041 537448 574189 754709 812535 121367 703799 481867 985752 211444 442940 501194 241284 169081 203302 29588 881591 685382 805631 435349 392611 946003 850098 247651 459168 214440 281661 159952 618706 920630 130314 288735 124953 873195 864082 934845 990237 340191 626645 770669 532349 100716 882653 347154 483697 728624 72306 798445 190272 555074 314561 630236 612725 245370 338855 231839 215322 281011 753555 7642 204914 459243 54178 888057 662301 402678 558430 885793 495391 622291 403838 974534 777625 623062 720528 956446 411692 872602 28346 749649 557863 727859 984370 346280 220281 636910 683330 738789 505911 563437 565856 813084 71021 268555 598672 492338 962904 448242 720055 580664 372461 579093 223409 507001 490926 723686 623030 245618 813479 904738 905272 242852 920725 893799 24174 117154 198546 193702 625760 631045 245213 935148 364342 26987 813822 253525 230407 327905 829022 720490 732140 813423 474050 23462 927867 529126 134714 977472 422406 429959 470202 378898 16769 738703 99259 938133 859826 568125 986613 777828 263010 286032 3920 262548 980063 679975 465411 98792 366813 798833 228010 24498 860097 515808 54955 185362 475054 53115 594730 235026 339493 903809 577039 163096 9064 203298 799905 105192 198303 544356 72469 46804 313628 704309 982253 559708 329773 989778 985019 131863 279649 283257 391410 7044 432520 795937 292790 366736 458749 158962 349672 932823 293608 270118 139301 8888 659193 288995 908325 592113 743865 257712 405294 211127 305021 628461 593748 643448 549686 265647 464936 303210 444484 976340 183215 21278 920604 546836 897583 717629 530298 380791 332757 157630 476739 703803 560271 202710 992251 92955 653130 121801 838864 832814 912631 70202 739755 460048 291817 946673 276027 327298 803254 907887 983440 920201 207376 477568 662382 385057 828184 916769 485859 358438 658264 705697 436207 306098 38531 577587 422274 793037 330283 273170 185834 185737 403673 958023 156909 852371 42301 215526 608368 54438 472194 831597 217305 350096 924724 414922 133341 104934 411922 136301 11424 279500 718503 965972 883002 645905 166366 693344 74763 304686 242538 448483 183766 343045 673156 619987 329979 821367 718611 688395 128951 600861 674743 735437 147345 196458 778777 452013 173182 395788 77903 83193 693534 236915 1264 138067 138371 455344 870821 993484 698788 13443 72521 656129 725661 641618 299204 855610 291857 661461 481009 180896 991194 525425 519691 886922 402362 506135 71010 596738 107035 336451 933589 555471 227025 161177 812652 709738 303293 393102 950419 491579 924744 429071 112239 493784 988663 449670 976785 912336 322453 879357 312906 963917 964925 515124 54052 491224 434498 640713 149660 935863 343774 216410 240594 505287 683822 909539 209293 366481 977888 833910 683193 934472 977271 778648 568710 262724 912776 733313 560781 535739 235208 621640 331144 998563 645983 96808 576193 984323 686399 204923 850065 572505 481099 976855 443994 109774 133851 600534 71677 533525 538729 638103 670321 332485 452142 301081 835527 477596 643664 866362 56312 924310 428686 880200 775823 637317 89531 902238 867957 214652 603939 358174 883073 312360 814136 343278 379865 869044 767732 794519 613075 416460 493037 370177 358754 176453 78734 154866 106795 771524 49756 490139 679250 732535 612149 306522 563809 857273 561604 245619 854209 330664 967209 168831 343976 259220 569703 708794 225333 439194 818238 95813 700047 723943 228005 333800 743313 757102 481455 106287 160430 312274 582955 647275 5874 34630 960140 717322 855022 394948 693973 392202 585154 700695 191485 82238 14212 190102 712872 678484 454913 704584 828655 680588 340838 824746 763932 508301 491226 522023 396926 580168 720663 801845 184159 415381 136435 914327 971050 574187 3957 81851 26938 20523 843290 200074 622297 939707 148056 927481 761262 291407 783442 521809 669538 937451 869924 725528 647676 464546 120080 377120 630984 834609 324852 213223 801364 837061 694887 363935 948959 761044 943145 105908 243406 265863 902477 312392 478965 127928 814378 699638 928120 379358 990903 627854 794541 386636 649972 644270 887597 609681 898885 18461 497711 86909 228029 272338 715531 598763 740212 91813 407899 808453 189848 93701 571486 138660 264825 832897 524522 840596 430542 962240 668341 417938 394771 962143 640336 44477 94201 147471 82252 285212 72419 341146 523139 184383 870584 791179 339774 17032 595169 401108 818636 66904 349038 362365 726147 487328 466898 862648 488432 351711 668980 996367 176724 158293 90649 165057 925011 727775 204587 431930 951076 783809 656377 96535 642476 389235 200172 88228 999671 760595 131753 97296 595341 56814 876030 676858 34309 689537 220781 147955 326092 599613 912751 57125 714690 520294 371268 380090 740762 82531 991630 959556 368315 179700 714732 759319 292795 243338 744489 474505 924388 824989 747953 559122 764952 677976 589795 146970 929373 78660 559567 241734 121355 24282 628672 616533 494139 217495 166367 246486 679670 357993 180020 357430 708368 340171 533009 410037 134843 307105 422813 666768 557925 239231 34132 241172 121121 263517 279180 974909 631287 998736 256522 163234 251337 144000 351657 978433 176748 465158 694694 391797 65348 243613 593493 286608 143596 906719 451320 746844 317429 746284 153166 145170 747408 781742 85372 743646 518794 587402 960395 695109 519678 775664 731874 416822 209753 535065 844054 327406 154667 974683 345415 161073 857804 34757 455355 27567 794585 519852 91854 619981 422237 515386 703247 164859 792444 439480 728006 482712 119395 574459 342295 139163 41869 195159 687105 307219 582329 302081 345043 149185 980983 410690 244793 524507 227898 508434 568792 276831 396149 858014 396383 19393 853918 816942 837771 288498 281162 281026 385088 281044 678199 952820 343892 848635 57494 807954 832818 885512 479551 361911 749142 669556 398856 205353 200397 82042 84449 44354 529163 407127 384730 313810 526945 953552 117476 995335 508236 368286 756960 69325 223451 1786 770741 260334 266998 830272 744722 949228 88093 417434 784857 792531 166264 524721 201655 797674 803574 963720 416940 113378 9864 271258 515408 148201 105010 486781 346177 45724 89256 693488 898396 271954 533950 954700 837353 438994 342800 670689 257666 772037 436571 431988 510744 50530 945020 899415 261359 424263 722220 27966 208346 145774 13651 250860 82655 864969 863684 337087 525216 4481 510658 604578 93937 710803 717258 946111 230981 724223 749011 704164 410902 69385 705197 145838 905912 589711 396136 765390 997618 636385 515176 479893 595606 60083 877359 597865 87832 439886 4885 235789 344160 6527 235491 956944 434656 75400 75706 35366 146935 286480 842665 368073 743516 526310 418954 706248 448080 309560 692468 64515 339030 253770 401533 779324 160533 727501 828110 807941 287371 69489 120684 186610 63691 481258 499991 395652 144943 146504 265760 499195 504952 400334 838736 770127 475864 524465 785551 157918 977853 116001 446154 306486 696620 271266 67105 978207 780395 14975 529566 198131 267871 386651 902705 780417 289320 739443 421560 397550 759486 783315 753560 758567 328399 603579 887742 613914 879507 152111 490234 185583 535803 808682 232911 155927 638052 236321 928432 301120 813769 891886 32284 471433 868091 817692 591396 925000 389856 880215 860518 447526 112411 709516 214597 86586 259074 641572 257313 201303 872267 371983 792706 65895 214971 98677 280846 776053 986855 707810 279792 425746 352943 827325 517471 407784 172906 119748 462383 721283 488920 935120 711819 397173 750452 375031 873646 190940 727259 927729 596648 190862 366606 578936 615478 507774 535703 760838 710552 500819 596988 228684 790942 95902 813142 687266 255167 915039 374490 150890 835909 377666 903349 575072 547841 825382 188918 412559 203858 782827 12016 285714 990726 729466 534526 761129 852423 627563 818086 951235 417382 494564 282710 747386 763834 303297 77136 448519 447160 124976 837941 812152 262255 306650 756329 52177 478065 821521 673060 153814 931019 826441 986734 276253 683109 655643 419130 654171 253124 601157 298221 267938 689235 498171 322829 233096 877496 422650 101883 738091 239645 107689 473258 376295 583152 415624 820992 26816 747792 921170 877526 483429 112307 514689 429321 351939 147973 907123 560278 700976 449587 277217 198534 785193 948183 361874 82198 777791 388246 264961 126780 145013 380055 775741 705134 181898 178661 1780 122104 531049 201311 559759 263927 502845 635602 829899 542536 479129 106317 750416 410797 203769 605403 5190 517307 917165 435135 470756 43894 640249 167787 806048 292084 624025 631834 537564 439502 925942 555820 864942 525715 65125 999129 88628 317615 245544 210901 616878 758113 647167 882962 351649 403215 640355 408707 629541 338438 996316 580391 355021 924435 485983 444596 496689 592455 596364 459634 377547 484719 344236 93793 999596 221422 263668 490071 270792 634475 912740 356750 959222 551873 722332 763077 797282 205488 595702 565518 249380 422415 209211 855006 609038 35293 361510 116513 905217 450984 26667 646858 593505 90289 638392 245938 583429 8648 956285 691347 233690 142524 488452 981101 10257 638390 548610 810155 703079 442333 176489 113521 200278 441418 194841 11879 859287 637371 872629 732960 405867 221022 265834 785437 851270 49308 988479 685744 173134 785501 975363 796191 577434 982293 312064 735932 367040 22563 646578 247082 705297 596389 864314 839719 205948 750935 218046 697158 26549 458338 29376 333959 617035 570807 585173 535120 590920 164974 913593 859931 357827 129129 246424 58506 341462 360100 164855 660157 93076 832480 203840 732145 460297 450308 812555 629558 658354 155286 520946 922186 727243 21312 693772 393139 313222 426919 412638 511589 386451 138814 311540 133269 317946 300468 690572 570172 120263 95471 136183 136633 625066 278578 443976 463980 919168 644701 655862 742474 145160 454496 37591 133814 342125 264712 135919 494927 720542 252811 471521 2609 541197 461478 498113 476584 398956 826769 162530 32964 122961 426067 609932 301907 351358 714696 820707 133646 838479 865921 223814 424559 733073 817556 373517 603651 326818 403586 847516 306709 529572 119279 635336 526863 647222 22299 740244 920578 235539 767981 250505 175198 537436 657458 594077 968146 78809 451214 302456 592375 59886 935896 485296 231266 701955 751330 484019 417467 775576 276198 142258 471815 537632 158751 589316 297922 126357 356282 916827 336899 968371 502552 43336 270827 963873 987980 768581 951219 964287 194129 180036 893125 574610 173169 545096 435615 591263 847002 567509 508076 100376 563196 290679 545386 115789 878073 779359 932083 388609 491283 870081 467715 309795 377506 803800 358275 546009 850800 921850 710165 55595 35890 42002 683489 755050 839478 469729 282384 561524 217545 507196 912872 317453 157839 390997 840125 239801 754638 870080 964200 243165 590994 653136 305080 497164 137677 690555 337996 49988 869731 89061 913368 611587 231461 981213 280970 647980 22348 975766 868187 635121 978204 77718 304566 32601 962754 17376 943921 488725 521144 10697 607211 361934 270196 347227 493355 134611 532912 198741 2629 518602 993970 268966 689000 327227 835309 469892 450589 212399 527979 277101 148611 674275 896419 586226 13909 616431 540481 504077 405495 39232 349082 367593 637740 109170 965811 610099 922555 156355 368726 402426 554519 185420 874802 157750 310382 452330 818631 677352 120721 384234 522338 239312 839189 829834 900636 30579 471791 676275 242642 624509 45608 301736 213575 220863 918735 573776 671132 95892 141736 498493 772756 278377 564339 980580 599260 618666 380467 447366 482188 667051 956391 389126 10040 637499 285763 534544 515671 68128 36943 438580 936533 142716 290985 608100 889517 370319 475468 811082 367654 935808 572577 802659 386138 12485 519321 540800 686632 657039 742765 377348 518263 550888 440283 934645 994804 600725 408360 990271 683230 218939 757562 849254 254901 496976 317690 65010 971708 600753 91892 129868 148701 103080 396807 713445 881915 492564 306487 692575 337192 903661 164446 693260 29158 489599 587985 365273 43146 462539 508329 133688 241706 542642 845240 14016 112005 230440 21540 599480 280525 191875 661941 179003 893766 922351 135330 863519 470849 83592 122029 41833 698375 125238 376449 209345 334273 778693 340413 367962 300899 76769 708993 199949 928319 257489 659799 865603 783101 563727 451675 897983 867742 467401 960201 47989 867217 961367 552303 190531 639604 307647 392599 593740 907855 964667 440555 608908 963673 35817 956780 400586 733625 905854 695599 249144 914585 827868 357331 728404 343223 447794 799664 897141 565388 214344 913726 152463 137211 814250 246197 891410 186227 738528 898757 949061 626164 537318 609341 59693 226911 819620 148087 569987 307867 395210 102693 336499 564387 473781 857240 680215 152603 293077 83961 627092 470372 804066 880290 604608 727245 570912 53478 367759 593337 955168 367614 377262 782759 504691 881945 246548 885997 312928 683535 822893 146097 911312 898330 868704 310289 229879 58556 847315 184816 973478 377690 979452 818713 793263 297716 417011 18612 816822 772820 671410 632383 503426 440637 524138 252306 184524 307527 731164 407331 129248 516885 394487 460298 514434 934388 720567 493312 481427 232305 71687 329660 671729 197184 273331 385138 72989 979658 450684 919022 47228 295787 899761 770316 470725 213597 110520 686602 593553 384608 515753 34953 627599 267456 587094 588948 440487 725265 490348 169219 951725 160034 570847 729859 565190 298379 502739 155811 858961 765925 177591 812277 942583 782222 341543 297743 449999 605379 521436 555067 388667 449544 341419 919026 327717 484461 83421 976579 593743 792246 409840 44058 868588 891082 385400 254818 625513 990250 550857 725817 925391 682163 796495 94465 737222 327086 764660 173865 603166 841777 433935 369900 506099 502130 40397 453253 515403 647795 295704 417317 717418 91058 24059 405687 657505 747421 653170 667573 51536 355443 22559 929948 531195 650789 605383 494898 890390 474071 773607 283320 795315 742724 498703 485168 469735 192851 392233 960550 289976 499021 389294 727741 521446 901380 337208 918181 242382 396467 301360 165267 137998 593902 927302 691696 902776 114407 526913 915813 582658 5678 663278 612055 259315 457827 577571 55326 130458 1590 659631 632481 971569 300963 41741 524995 443292 177888 984720 115398 162126 131375 27064 445696 760494 17956 137925 244179 818982 385865 189722 993874 431469 800667 735030 990684 527464 17053 646429 206668 524535 638062 323128 106240 847565 638557 182656 649103 724343 531754 281676 818729 284003 304780 235268 357271 540674 855544 701468 954151 860962 49076 479312 856455 177267 616077 678585 560018 590066 566668 470144 607040 347263 631548 756962 548173 777856 585960 737969 332633 547575 667439 26761 140470 299776 70120 396720 812520 504744 644541 777800 954858 704825 570099 844082 449759 761377 236141 743837 238105 801190 871306 177475 81303 520609 192333 930022 270338 753086 497779 104027 107229 190172 689662 985592 257353 577531 536157 92893 71569 495183 120446 982886 547606 510375 870191 459033 758962 253687 390247 634097 821867 847256 420380 720349 638355 546331 43255 16775 438954 712904 512150 191376 702976 87841 665401 950282 833711 556152 89619 309148 589983 189019 593449 850568 461771 585214 324304 837200 101508 319665 268606 327150 243553 156936 76207 291353 904144 549169 587851 149141 981696 948777 977364 791354 622582 182074 125780 998415 320705 334602 845485 798256 37872 266385 710448 792636 97832 91661 987823 12788 586734 504023 834231 521856 723785 239103 61977 805755 137333 46632 31117 772990 694773 556132 831233 49814 710563 163107 635148 896752 142163 495004 711446 269444 372509 817168 923687 834792 706166 513173 257507 143020 439152 847294 420842 61227 600037 976393 983289 58025 25513 433249 474360 277584 728751 367259 589008 889027 605833 882373 810314 740136 461737 406337 27640 104207 927329 672371 159291 741577 237460 429501 503671 743706 292037 306446 354070 786165 973114 100068 862114 819654 599130 515525 186734 176809 98997 261878 736356 232395 681157 603686 680702 549914 795651 400637 496479 520084 57366 6385 188857 636282 338767 245087 81579 450566 276312 295090 260608 14189 590887 355826 667431 830743 475339 449551 322333 717390 978191 261394 468712 823689 727530 894431 79621 84822 892261 627000 437732 766436 63345 733175 441341 497941 161060 759474 144388 717223 674856 488474 76978 176805 499390 418839 258264 83570 194320 944657 508275 307735 555821 932897 61749 497877 701481 351959 482650 876878 952207 909556 405748 405644 729923 606432 713859 602288 429909 395239 638304 143050 463877 758961 42999 353029 425360 25672 398854 888675 197172 114269 673238 569401 870666 139076 878141 640474 555738 333970 586644 150413 515869 467057 971569 121652 130227 766269 749710 627799 376492 599627 316831 427503 560494 21941 666799 544470 141972 804451 159911 850388 584483 791769 530251 78526 491397 15201 895282 287182 731902 570201 435288 712943 76116 948287 97798 993055 188601 853498 761339 184325 69612 987571 21395 497113 299312 798023 938684 658417 7224 29558 984690 673766 647074 288427 965019 993884 367661 283638 787367 957732 387872 210559 249247 365973 749998 967534 61476 307906 496023 364329 473564 21853 394994 60589 778110 168481 972580 611367 886069 590534 923237 621526 839353 317680 920412 464228 751789 738613 523714 136507 245222 195789 276194 101816 855237 272245 235616 299372 317605 103217 266736 159884 244924 507439 549167 216179 415159 784501 758821 495042 509878 560320 227700 696398 875246 72791 300492 902783 337698 432391 36783 563055 124456 466588 183557 883601 111427 530069 532188 937995 606558 776041 529561 748594 232194 696099 819096 424009 918289 129866 376745 17078 989590 969986 538939 71925 201887 41652 647065 320473 227539 343420 112808 166863 794048 84290 343750 868738 960226 445989 958576 928158 469339 571450 385987 835797 985966 487654 843327 387890 431034 490445 975356 44175 945824 290144 724713 35978 158962 956205 675790 652402 340866 322985 52210 877969 717717 48448 916550 357944 357680 861159 650406 349840 495 9392 91925 496184 839723 456444 314507 502511 466705 299652 613011 665422 183808 220883 1930 270147 555569 545318 84948 320607 142777 832044 802271 355074 571865 141154 83042 582316 788632 824691 575158 286631 343872 432958 295836 477764 586930 994996 463618 714510 660101 477249 46040 500084 536129 838310 68451 872737 773422 995854 616912 340805 763069 648881 707849 582298 629721 875686 576328 523894 464385 130461 327927 265675 521726 569317 97857 670950 699103 82796 962279 479830 207867 683129 910271 14674 99463 251499 150502 389115 264427 55460 236355 660953 897938 604119 997499 691875 744925 984930 144357 895541 509572 210763 21203 726318 914639 861980 996690 829431 597515 78700 770917 72538 8904 410403 808878 362802 868241 345669 865355 176928 421412 818927 110219 960288 235724 788866 291713 714203 895892 376862 553213 286675 975487 533902 462609 436511 787885 693856 239864 826648 399249 930160 60757 545166 279746 919357 92224 314102 319530 326519 611659 213125 438863 412625 192081 826773 778869 77323 246545 907311 840969 230884 722000 142514 331284 793 213183 335258 938179 427537 217890 138384 946541 603119 217543 158341 748081 277114 587627 220740 62564 393448 82776 423630 947958 491178 880200 86590 95522 471184 819081 701210 978104 473194 757997 490166 705745 936120 596710 517160 974660 118244 496972 629640 39370 449224 985622 113992 873109 370825 333084 993384 525091 178978 767483 270237 523836 376384 11209 286072 718002 635744 470700 284083 328843 766652 199440 494635 456028 937691 948902 993482 102428 664267 397404 979931 824091 370182 535553 258432 564281 267818 643322 18752 640941 182836 835117 79871 874109 825638 253038 190835 948914 906348 631241 820283 497989 114871 939907 378494 193389 137565 685983 435701 852099 510842 472895 290105 641245 790118 953608 250691 497452 263014 888494 193808 897691 363081 809677 430272 332281 186964 301959 317019 601512 397100 974265 721805 58003 813680 396965 588064 642201 972907 207550 453462 728459 83279 240944 241410 434771 877145 138086 633571 854257 393870 248063 650257 835033 628426 214828 816419 702155 224649 278809 246918 435223 905765 240749 74503 623031 299633 942272 513791 295946 94023 684386 499089 350166 854425 10570 63035 439028 953880 312067 817275 19449 74313 626924 617259 164034 352849 970584 71807 144742 644393 251292 96056 901230 872466 562698 219188 4257 790586 401773 104059 704888 301680 736964 718537 587188 507646 449014 203322 910864 246414 36364 340535 8474 194881 392905 450064 434902 876994 752224 745258 756835 38480 361499 638730 958237 908796 917326 363333 324613 867836 92793 403884 181192 489335 26081 761792 391920 182962 288382 6538 821874 997911 847333 540757 912995 447906 796968 712110 670713 968161 17235 758667 597593 871890 613626 886567 265337 22511 819647 826037 547906 558169 72271 523749 772878 831433 347444 40532 318420 401870 682479 753126 488827 595005 691487 939768 238430 948343 590751 500909 220181 598523 680113 647251 662087 117044 870117 273134 873509 544686 67608 34179 922025 76743 372494 188733 527390 735404 107643 599564 930026 684873 785024 990526 652664 527508 768659 123493 528735 965640 597623 99869 321067 461814 383161 339809 477954 194584 206974 686594 98124 352300 888355 508350 412924 458426 378749 642860 671799 611433 775898 909218 539463 537673 516422 318443 847208 144504 705467 129456 986673 990232 8728 562825 75564 957642 697980 652873 23190 634895 742863 11396 166767 664404 104409 448842 84353 431620 744652 360870 777479 827393 168304 616652 83520 439768 453261 266727 98449 474210 425640 828156 603197 567374 759556 364738 680205 217968 663241 483386 967874 759572 535786 945738 506689 515312 500957 293349 232689 720758 632013 27363 647143 664315 608613 205088 618649 798255 619095 437820 519512 405662 303532 696474 625568 353024 20057 740460 996421 205942 765797 608651 964514 587627 986373 640568 476549 991407 428343 229873 578515 715145 948885 817622 304612 548519 652134 324341 509345 571948 446103 803017 864453 373229 811671 786207 696440 417518 921251 343655 143990 625223 658663 396730 966413 507018 22253 94514 181883 3893 24312 431245 337426 923942 29616 261464 355986 642915 220071 961564 49163 528264 260636 394471 235706 41760 874601 92268 533005 594615 257201 984191 97962 36876 272002 742670 313236 986271 288416 795279 685620 598495 557280 793669 828368 732600 929652 282092 461970 706082 783287 745190 332406 138317 670523 787713 788939 312670 410052 185767 325574 195422 748571 580838 376698 945195 517051 111134 479991 507544 681947 867048 141991 878248 854087 831376 664761 665003 640320 482526 875143 109283 771330 307374 173818 603574 196989 405908 406069 584360 72872 348591 523739 198454 15765 675275 236281 150909 704768 70142 305192 67247 854916 84257 194196 270687 115554 800915 202040 751336 438976 639191 956789 50243 122880 415425 241705 301982 403444 143334 593523 938617 640568 241546 535894 702784 121201 759961 771346 815309 816097 498476 927198 434684 47133 660599 138785 958835 77231 43213 701643 35582 106836 424887 432058 358903 937682 552412 716404 881002 732601 988318 969255 141159 974161 906233 201890 647171 977373 251967 140513 868580 912216 774683 144975 817506 895726 714817 811507 213665 958319 282821 925916 271848 985265 390835 415219 944362 491349 506133 515476 922666 220213 4983 239651 736072 475858 371231 852422 767038 11168 780887 879120 441707 521273 141563 470683 289295 190898 494758 783937 621526 196847 605484 85316 781463 420421 612810 780822 834556 357494 626837 378419 199856 186792 908500 726586 216673 749543 212537 151057 593109 240221 116350 810862 537051 79364 600997 172218 576432 330216 181579 926917 715827 764681 576546 487868 853108 37049 731387 363058 638980 490102 239367 358747 605268 759977 7184 278944 681502 773793 238628 612200 617645 30020 259143 165754 988249 645783 587933 999708 311686 558788 655759 722056 598092 868418 877 669290 268291 784879 467269 84977 494030 27366 455639 360215 331448 746885 927629 571535 190542 371162 454423 285074 949478 23521 377536 170111 903522 620950 6076 410245 943570 452302 198803 55488 929793 198905 693497 380215 34470 452818 985135 482257 934541 943558 414836 63846 392425 582111 381907 643201 515985 61753 605194 731610 744167 302040 93371 560755 310765 776639 750338 259926 694250 894175 936299 931631 448695 331159 688413 533779 584833 848625 286291 802689 36338 511237 493918 369153 820835 848666 526034 871953 212283 802927 21408 413836 319003 173767 482379 73453 434474 981118 361328 896480 525038 767107 855103 187007 754485 487187 329262 127884 110567 39000 339850 905847 624033 169645 106513 257544 292746 534392 652113 905834 671389 204616 754752 18694 531641 998580 824101 499838 328537 718609 424515 742550 590990 883517 218268 589635 495952 461889 555929 123863 950732 117979 849075 26545 786593 5721 293108 42888 366815 534074 908945 910667 89161 890628 620916 205857 191552 664377 736946 746412 879389 289951 169671 184343 465191 226573 492445 830155 638457 748166 370631 57149 485204 704180 209971 158531 406847 624255 691449 2647 633079 168848 550232 800235 911486 171678 672373 41714 183742 512451 864587 393390 42442 730707 95478 384531 334668 219595 446266 261561 672099 134568 53615 484077 821503 894341 166879 329484 732545 344312 724269 992854 156690 397869 535048 38980 28031 900751 827506 881060 24892 693791 798178 498185 682518 111952 520152 105084 650793 362059 465383 502352 888581 265585 199430 355144 314663 409235 813203 591111 395170 955035 148286 875976 158362 320258 510801 494214 973867 612103 462105 208818 515159 820983 133608 445225 846569 331804 518983 457110 480350 497464 487528 806714 839183 327530 538187 514657 802205 889804 851619 783238 124248 335400 951895 759088 693251 172275 886301 890259 830602 287600 890650 285131 769604 296459 514943 981039 866869 961582 636092 629399 141351 934668 332057 426683 582876 505022 60918 125396 102452 50443 366171 683899 668636 172306 208956 81999 44327 904575 811169 459661 535695 881364 936107 681487 712634 38129 606492 525164 784114 714653 783960 647988 179869 371387 815843 934301 851379 361128 782304 605806 837973 646856 586971 39547 771051 783557 94886 777206 892793 548657 90174 416150 473422 587005 267150 897579 14124 173869 32710 274955 108651 523226 241075 950118 941642 391478 217913 142735 924604 436292 610114 608029 93310 206659 820673 930700 649286 534297 427457 868562 870240 970322 882137 834911 282675 430667 20960 790893 528962 599993 949072 329892 246137 335005 270067 671582 665898 1580 118371 301306 894362 249004 672715 830441 843769 44907 889526 275622 629080 149815 822876 689960 237476 737233 653726 465327 319339 472999 496497 990428 656048 101658 881846 414914 111088 345445 369778 955354 239199 865074 619750 55961 719800 538340 296445 129976 76764 770732 897009 893991 752296 888806 474933 142840 668311 294673 554186 918029 174838 778365 158248 650742 650581 446327 327537 855009 226772 916922 37437 661908 291795 743870 910979 9549 102162 253533 789659 19265 388987 542069 506022 757234 154842 805972 673069 576696 235431 238952 400007 422495 711852 904884 186340 825027 574168 785282 478369 430492 13424 72288 384844 735150 541359 739746 192534 850268 484495 417948 421049 899117 478180 66865 246044 335139 582245 683917 174172 257066 795904 903721 633038 485745 210663 324793 59243 378008 928435 42087 148301 117130 525885 52349 356257 688698 936265 9350 842576 456300 33451 238027 653682 402420 553403 823867 496400 525535 458525 698913 312107 389638 238854 524525 702449 562986 332242 648759 828996 193311 817312 480818 378901 249110 748810 371621 843056 232439 749868 631431 357129 714475 747271 873754 296581 165522 208500 679834 602213 734478 449099 114467 975778 41830 108896 992033 274265 412460 827011 664623 518028 298158 340778 412506 528390 716596 988449 564439 207861 426863 262929 857953 192552 441765 772965 982513 562822 45273 975638 138898 460251 49163 897119 821199 67069 821630 572523 400950 915726 604958 227137 130782 216345 880064 983422 641805 179600 416731 496725 663876 493662 222407 876004 635896 157326 836745 733298 317928 53301 28628 944073 686949 632826 476852 968865 480483 912292 48683 931200 65870 313361 227726 366665 378808 749798 621910 607745 675994 564933 690981 221207 86725 982185 824792 715452 43782 671887 231589 498371 823421 808453 372366 688174 258301 178460 640915 951704 640695 743553 629464 503832 541256 84945 664289 565092 267871 847436 322139 522794 493076 558565 928738 971732 632426 266480 494109 592468 228572 896857 434554 722242 118004 19542 462070 147185 251265 448904 631211 308813 591994 95913 959371 44440 248911 993344 277447 635566 632644 838178 911299 270176 155462 571233 513626 567748 328604 700390 704764 212555 73959 695491 430224 955250 275584 80184 225644 660354 848135 621868 688077 377125 3552 482102 81781 516200 39009 935606 916222 479752 609244 414769 124471 733734 827467 739419 879801 934569 900238 446963 223020 614458 249052 282735 799295 698696 804322 688258 127444 725034 723212 360439 98212 756647 610591 144004 789032 715793 68599 155068 538335 768460 80364 76116 755218 874191 545479 97750 320253 34451 380370 9759 220123 178379 545891 680548 698926 183140 778312 920469 596494 900020 779023 484056 946577 39623 49732 231440 630866 847080 901047 386336 845116 502266 782758 61366 158661 267253 930014 213854 865590 733682 435151 535384 26525 492440 513541 606466 967674 321516 366754 671554 914600 963166 437070 715145 28635 317328 3666 919070 35507 252136 324616 250333 366149 996188 625839 733141 322104 580193 55898 997552 38837 220685 151805 700878 154850 254211 586398 533218 239103 801497 701164 189648 840037 250387 226302 2067 398362 450262 152899 596553 581748 3819 190625 201894 577668 1291 644740 764578 871957 103904 114610 181588 925505 708098 862652 927381 242478 955954 169319 276326 382761 691415 992545 175212 561477 481433 61667 913132 907479 507507 417710 516617 70098 375798 714227 29380 351283 890586 717646 164169 799714 758394 760470 104545 104028 157115 178733 175295 635305 879645 690992 617886 312608 33255 291366 37924 929282 609655 246512 808786 288363 793389 691798 991129 830701 922862 381751 443523 296012 141276 949629 111491 317364 800005 101244 578181 1234 722843 851992 931261 476094 513245 543889 280102 807482 555295 881154 472154 34210 549781 825863 843078 492713 710389 885973 127198 936180 738044 784870 677302 171145 681927 806268 166684 225903 346410 146247 683472 806539 386041 241706 903721 923493 79520 651057 824086 607275 456866 470809 667209 987496 168907 672407 559426 106439 680838 386453 562687 954114 884863 262358 361434 192133 108631 792223 917969 659403 634027 673526 717288 889832 757196 106888 684716 912490 823346 830118 349919 924339 489443 850017 42351 563338 141419 626684 174671 23688 324418 750911 500605 55099 831662 491658 216024 730555 66816 278758 819345 960411 326449 216070 235309 609932 975828 448605 179916 410266 353863 876664 916730 314477 506556 997057 666780 704867 886088 169787 406555 862920 897270 531980 823305 338396 29656 916048 292407 736469 539713 876744 167177 508757 54716 897100 820362 783494 364566 471888 212669 635581 220788 350899 201926 841861 759599 333221 909329 108338 999382 291962 396136 668769 961996 809840 119917 852939 343024 321089 751076 662115 42864 109650 607410 115651 930053 228696 380125 431742 615009 801864 791627 952529 376841 486726 72222 561479 951047 62735 932201 758357 584518 751936 226683 803536 314346 671649 152630 210111 164832 693269 826127 605867 164341 250339 418236 862551 554788 883362 126571 305170 561588 264199 866275 902563 395663 34977 850143 864661 255601 70598 193216 954326 972062 366419 577113 730413 378133 979163 808704 886991 183119 617452 88745 464345 591316 633750 286129 577708 641981 256473 724293 946861 847114 249951 998884 960968 470161 703249 822037 458238 789743 225125 210209 51920 708636 458919 427998 906840 840015 799960 120079 142584 42602 539636 517324 332359 866291 145915 704966 285766 162403 476122 653245 945396 130127 797988 426078 764502 250050 319333 103377 763061 102256 928400 207038 434288 55660 954377 491099 645977 875402 528656 947241 78973 720033 791507 777611 653055 418191 809121 462085 471442 518258 842136 616923 542132 89634 668254 760766 781020 755705 798322 12750 488847 562022 953442 145727 901005 444691 4231 862588 141675 108494 916552 646675 593987 466858 945307 93349 844460 266120 265763 838801 230 69439 430292 134516 941125 571305 286270 904094 758428 973748 495768 836457 220537 955341 310422 949855 146188 615462 473620 977334 640811 195451 942217 463280 849953 934602 663323 326526 414417 183143 735298 536353 475345 901312 64488 533674 492605 30206 24774 527697 967900 303353 438883 686415 687951 260487 41718 622377 480046 482074 839757 978551 142476 679303 497885 986554 869019 584783 845393 353240 768791 810683 943016 350919 960883 817505 903766 569606 910587 827432 268663 434937 282491 11862 930034 752748 28503 295161 906185 823020 473253 367744 342561 708504 535101 26625 576312 552814 494973 499855 476516 468261 105548 54368 131653 457970 626267 305225 32625 956941 19068 276437 377407 925154 992411 170855 137740 607659 753348 405763 843361 348527 411677 55792 799592 685724 831921 864658 197778 370752 300252 667905 898723 655536 587622 671183 274084 647471 744227 31627 934000 972541 554321 104268 655495 500621 757587 153326 448164 273592 246942 647631 522283 741490 681746 273347 418156 203040 448436 908451 260859 932919 655200 588647 836843 412205 906678 438463 481515 348655 147136 554369 982181 331643 414909 135062 541484 761589 290601 758386 80860 587750 866459 319606 329109 649577 544139 38469 254316 794977 156215 378559 394090 702116 815491 607132 289565 698863 75910 964154 280782 964762 538532 242958 370302 647205 721464 890099 983241 407797 80405 210031 942931 853110 667241 189213 597863 631755 871114 533758 343597 168255 192481 914450 653204 337686 690268 107493 798188 575823 720461 367935 176375 823241 224555 852182 232153 766905 356068 635429 841910 112140 791326 676658 746379 562683 321183 986580 743574 92915 137079 923701 436664 792986 575212 712009 74183 288785 322595 90552 124704 222382 469976 265301 26455 642266 410527 958659 237781 496285 44652 766566 656005 101473 667827 156650 129263 355289 189001 483209 236968 771336 593379 952998 664831 855623 744430 580613 991091 858326 947839 238342 776184 267682 612798 179788 97769 80007 716712 202957 804989 934758 528343 672215 550157 868409 428650 594795 531427 325361 242298 728727 141473 724926 763608 656489 627241 688259 756494 327569 464155 113416 58185 559908 152305 184445 507846 545042 533552 554851 177354 248187 932211 610321 195029 180738 174182 932802 324185 590786 963860 673799 94914 93357 797267 363755 695365 316804 47878 854211 714382 178290 387916 808423 445427 517464 707327 72368 927392 615021 765259 545943 178872 854211 48677 713136 279600 618241 943375 686911 466637 814137 834172 497931 352324 549328 390060 915205 309715 802526 249148 730285 705987 219877 835612 375310 433430 201661 584064 310430 413513 687064 165164 129479 711595 128544 457149 216346 502335 538068 158015 411885 616874 216732 823970 705228 830788 431341 343842 912308 487895 906971 437939 875265 411169 409634 419217 836584 973003 177262 810454 595651 147720 305487 981689 690311 582084 748142 228902 409094 568606 45646 182381 751608 991280 479516 673874 903006 213443 377923 215064 5528 612450 441142 435178 40556 141595 437708 598387 540207 529163 190714 486814 481458 192721 967464 514592 502988 834303 11683 239255 741402 705282 594360 171039 568661 671657 57959 299714 467152 877986 842010 706163 487314 817823 584234 909182 983839 126161 575146 216662 226297 758062 154021 591213 108453 274400 834758 395519 632905 589406 951258 83802 397119 215334 72028 383464 779393 473001 794944 376593 601924 647809 194598 522226 950270 445040 597960 442000 909116 906306 947429 40767 437874 481128 191565 933515 234800 555675 789694 763104 123784 767269 394388 442843 20745 752081 67770 890525 698144 178849 596138 812591 697205 31455 323840 118929 775223 523520 978543 85209 943478 764149 221456 128122 422005 876549 127650 113975 74313 848566 763375 808215 441074 237632 161182 278065 619439 64238 775873 263714 344744 311696 681437 697569 525171 115330 274117 180322 501745 149202 544112 467282 989428 890370 342608 693087 771529 536832 50546 134351 327827 677388 720011 970927 235221 328838 388067 579796 378429 394697 726872 418406 575556 627004 874378 323793 348488 88716 687492 331371 837693 72542 541204 708286 872123 786909 203697 177142 89638 462267 649629 798417 487362 479286 486399 737059 122565 177194 867365 282993 720432 563713 734532 789674 541736 813820 108117 26889 91081 733947 37914 529811 528857 692691 626074 303100 351957 862361 514997 134930 524219 615911 478065 907563 946052 363136 773980 808349 840826 474371 151101 306095 843921 376103 693198 941286 643456 225372 359868 860770 420745 41290 424173 97037 635614 48763 733389 59920 231723 973042 665532 175529 986713 212121 267738 382970 600096 59280 294344 599269 158652 188957 393058 95435 199232 258348 500399 685007 917457 771384 974715 694172 703150 829177 65285 262989 573025 128590 505632 843705 506962 988999 890119 991911 602810 612311 323400 2714 165715 181526 918703 668685 222566 488359 99391 202576 884972 825302 20989 774551 449182 779409 753329 73498 215997 122292 123282 649694 478812 498717 191726 93876 242569 981826 43950 960259 905427 603222 958553 276221 563329 450187 335459 305910 788458 836194 962717 190740 463613 188787 289800 8848 240510 749892 699312 302073 303913 137185 449784 984301 642623 170194 779124 864203 655344 788741 680629 256054 608034 174855 83435 30544 949174 422095 364757 331801 787650 113740 310987 478580 519401 791984 252532 180189 238204 567286 46260 33099 581299 214651 814102 106550 47664 765856 909069 836295 513812 339856 2428 482648 583695 530124 524979 583061 77615 727910 496435 950657 397737 427601 754850 379517 124201 702293 851225 24228 750667 485628 365991 299589 457181 501911 725836 161714 384739 980508 67304 338584 725371 205668 262733 895637 708043 392577 361466 265549 28964 623556 45537 625675 585653 911848 304215 398103 103264 501076 801974 83964 984031 576461 603532 790213 777567 716223 685264 167599 127472 369883 539789 453730 448048 954835 526429 178059 166252 919862 871313 399702 191798 211043 139100 98717 196258 805310 335024 202827 661407 180664 991502 570646 815099 87880 148427 955644 432810 553415 174737 602157 881773 899381 923540 286511 993411 185399 668948 327830 736528 83724 721505 918438 705424 35717 115893 668932 980506 884095 223514 626061 219566 526780 480446 817538 443674 479752 14251 697412 228166 633882 783422 359303 335385 841969 184096 960694 642182 22986 230693 182010 806546 580536 774173 822462 309971 358932 691929 597596 126964 184185 582746 191672 490279 602958 513208 911999 239155 178356 175439 353790 771710 807363 307182 475948 935027 622373 771001 914996 248369 875053 650967 917045 716932 287696 121520 729124 506686 205147 774280 8611 589592 196311 611663 570337 479471 103389 597165 651065 89063 926717 442275 385959 699665 540410 631420 903246 962602 140722 22162 169160 183883 599254 195652 18889 253005 398099 591449 108663 622156 830445 942492 818434 636482 466736 54198 398936 756193 987371 343175 450853 30633 234515 258106 116026 411499 376895 214739 689443 637309 777659 768073 933633 486318 749006 524019 471345 251142 810801 577096 35214 684615 870264 535070 470647 38654 76628 826375 974087 442710 372967 516942 116870 868341 418773 983931 893770 249557 671172 959345 795498 446192 949623 974537 62424 738373 731156 681254 648487 579517 724293 130321 666544 176535 860238 982811 14784 279222 352827 383665 165776 368123 750132 788048 974136 775415 82612 368608 642312 344086 666300 459783 342882 111561 527683 246532 846315 69144 364765 741704 615823 133480 471561 282049 772521 467557 852726 723972 169759 308972 639529 585178 135967 821400 993512 656836 981077 470772 192850 951038 619518 332848 212321 492223 70486 337810 537705 761127 328736 532487 946287 613302 5054 280249 463189 595231 670502 759723 503393 1703 629986 365110 400731 260125 283083 349366 647432 639168 659701 820809 937052 254312 899917 576799 515821 599937 94746 98947 274621 150845 17032 617023 907907 320138 880845 283309 957965 660446 386189 430179 114309 441623 390759 478088 881664 740552 690749 688469 104221 686477 503928 90279 585315 474992 286443 296012 56797 355823 147711 54053 465972 215080 99597 730865 723132 691085 99115 247516 602544 486797 834224 802468 762339 504588 312906 709796 732019 64675 114828 779638 922618 113414 34006 434827 611732 659719 727986 210246 762272 956534 972539 43390 283396 614906 712283 362493 519903 538533 496976 115227 214115 999242 884802 104340 24189 640816 87714 803281 264327 128205 307774 912788 57216 369861 576945 408514 224858 425065 112575 991480 515263 206933 783528 110154 963245 977549 904098 818836 573189 88766 194837 934829 914859 62959 300179 164163 774887 805818 134035 713033 22849 660431 921949 630146 412941 763490 436060 145573 653538 896073 446907 223042 134076 403886 307666 681819 957668 217755 941167 365143 806660 96322 973896 272993 410328 657477 950853 164297 898056 158836 118695 866055 753796 258374 825785 502213 413898 627238 327092 755724 485271 438535 804131 829313 407674 602341 943249 14951 703735 1527 940462 999735 403910 959045 132960 392863 347123 277487 910340 747852 708497 685412 234481 652015 709102 847652 657043 67494 911229 704546 75808 204737 487314 993393 434895 679975 736103 60199 80090 228765 874224 439245 924269 642383 291545 187612 93933 193241 400222 362155 266266 198210 319705 592491 532062 567123 597751 288397 49935 410152 526690 125894 842190 533934 273924 765963 114134 399024 100176 965523 467021 318593 873108 798645 410355 142433 927485 58766 453599 398591 607345 830951 348853 211090 689791 800097 81176 490066 832081 202653 745474 268047 174523 112491 512130 993065 747069 571779 256586 205190 60047 417926 885584 935096 482225 155338 692066 401443 6069 901843 455389 613233 25504 890722 671846 921827 991626 237085 551925 910480 276126 994319 755755 470799 639670 688152 584325 669245 562130 216870 428523 553439 909955 215206 123411 479012 140986 560571 914839 121426 923070 332885 480991 490234 109670 548749 776293 381314 847940 612387 270299 430075 142278 74522 986580 951961 854019 246015 834075 118570 582768 685772 286010 412354 646033 548031 981852 163720 117226 452987 717848 812955 801281 55724 15808 813723 326656 254132 416789 761149 281636 847741 56017 57136 787292 523510 757637 898493 482691 84005 784105 793166 475119 45232 569673 150320 20941 590827 311190 949568 291784 417830 643576 583811 401082 292043 433496 49364 844131 994270 984979 215647 517922 128113 364041 196250 905318 215098 548961 190522 552475 311819 421691 551611 668309 284942 49700 715411 75379 924941 807683 667563 39082 223903 0