1
5000
107897 215794 323691 431588 539485 647382 755279 863176 971073 630144 340791 209091 516811 398120 136392 129341 673185 734988 352823 505518 793321 4748 158959 834739 336121 608001 674209 631081 195199 969269 695324 556499 436911 98485 913231 546683 803429 291845 861691 167620 542901 258838 103733 194827 459112 660837 498986 275214 208455 112771 45489 153839 32660 86843 206230 399594 541183 458862 627674 662170 825114 488295 515816 646822 225833 656158 512658 448890 804744 380522 757696 580913 949499 836633 641378 53141 516591 391818 784752 790798 356108 978578 861687 210963 621324 389545 432727 101356 361307 341030 669317 841246 773003 751418 730376 552079 172119 782510 970629 527066 563093 109411 415516 413641 150417 767857 884514 926673 852493 964249 158001 864934 921572 24535 594879 899642 792580 792890 356963 589086 68199 472363 285362 441188 183433 919326 907493 506017 348154 949688 722164 891248 930119 384270 202641 245495 144138 812608 273492 343200 234513 759186 759410 851508 853106 28376 172817 273868 485452 662510 930673 971882 307895 234047 412420 119668 54336 959601 772084 112413 217196 537169 47632 956411 398668 180872 217332 302957 310445 623836 75408 115050 369747 603443 880287 495468 658747 767073 186225 344965 654179 949174 232310 502586 188236 977255 746881 991942 719850 137339 428003 361643 351550 533076 17628 982016 217208 887239 240227 246369 483474 166184 394401 836703 100316 476907 947961 697905 291091 853441 262712 864382 627266 443918 494978 818788 913717 39898 467900 887010 841237 766390 577356 743532 866471 818322 114313 330254 484752 763458 821618 392717 190274 797112 978339 610989 789895 137724 831178 403662 991542 486003 636914 660242 158172 631951 835153 95932 845789 715949 936321 385116 278711 419985 959345 148 413208 179657 656602 451372 312132 121872 978152 380538 110922 799997 260506 546284 802783 872002 692315 437039 124559 973100 596140 161686 675344 435746 273936 280592 100645 503316 629977 634888 421989 584091 819877 254070 461462 205024 291461 899883 91578 733501 984383 833321 176418 440926 449523 570798 904386 560937 894764 281480 364144 791027 393212 772556 758438 863001 279512 931669 795545 658424 876994 745374 529538 759139 658821 863124 304705 847621 362826 152184 678954 719614 242310 831125 215116 108941 948750 309113 514886 795227 390706 64187 750343 403424 40763 916 980294 194230 475939 144730 156823 464846 393984 240628 604390 936297 513320 253534 514178 265074 688304 941552 737707 450464 617107 927854 260011 833467 827616 259307 599636 610731 76039 181104 462951 705417 10601 466630 637676 977756 429229 824270 111929 591108 44266 872673 348304 811369 884932 861245 450304 504612 161561 541438 1532 385310 734685 710208 6476 373057 617960 4479 441671 684147 237846 863270 441091 309984 744852 377715 307649 148105 111341 272879 710418 351878 903214 45651 819046 474559 817303 413210 59052 995958 266049 755904 806270 372742 173729 649219 513548 391528 477304 885866 608020 138430 123064 981543 288391 170810 523355 838590 441915 119355 507028 684886 690800 488869 92078 31369 710989 973025 616601 276343 25395 96929 294483 857070 570626 333227 512896 484882 29210 788470 25434 22579 221473 29749 837497 962440 940742 400339 879174 920589 676994 976358 959263 716345 482633 195336 337407 609073 306248 225963 608772 994664 613627 817810 815598 594261 494222 21111 984102 151068 240199 641366 154287 469170 221357 250145 144219 595220 151708 915697 657643 54922 932164 672418 117944 773939 889904 892116 649048 648553 255470 983289 446687 52346 495021 12627 632128 944981 438250 218674 385712 143559 448600 480897 589670 297225 426521 835084 108316 437107 633641 114869 349783 567620 38373 566371 886462 696585 617872 286803 204081 639251 140557 815045 344395 863225 204798 596276 170380 985975 781987 684755 470063 392333 577411 928060 176521 711693 325137 655532 262253 194777 225225 696924 708615 41948 491569 847870 477014 836682 91346 430879 417640 46510 968775 808942 291660 183790 566288 603969 835669 373874 176239 9318 53717 795811 84869 38828 67124 362109 544905 358261 661428 503313 422749 101751 728861 388201 145515 658926 317658 952951 993380 943345 875685 409135 776325 404032 713798 366838 568995 600636 9615 32805 306387 559477 420603 837907 78762 352215 217140 621944 70099 846553 351135 679112 325559 885300 720251 68754 899490 457902 904696 900144 659445 691742 595536 10439 347801 284907 395903 935880 396574 624770 978406 805142 483823 61148 105854 565497 811029 172396 240670 468937 929916 322395 983877 165696 73907 39091 530122 784679 784165 713689 530671 242113 65654 996553 582432 797508 657795 673794 668734 134520 419992 747995 456734 296152 279612 578190 407078 549646 263970 342825 603954 377377 317592 325693 625682 624587 165629 462429 685874 771535 757303 76031 308310 250755 963632 902626 687251 703250 66508 453616 596137 201586 506813 343530 488300 456158 58853 264764 973832 495758 711005 275961 266021 295309 327387 391679 95117 358957 815181 277178 380690 584501 34727 392567 830225 712776 655395 660704 699514 858 866886 312832 687152 503572 113025 175604 225738 221170 430721 24984 566039 668573 458879 126620 650799 670359 857691 933370 605229 336044 236388 188025 865360 608274 557938 124242 269784 406268 961587 459531 342876 16508 630518 440936 118498 554290 387877 77070 652514 183954 146750 439618 156050 768249 353064 551108 844036 906395 854946 439679 836137 190864 127958 19137 719578 350209 194806 835885 281040 261479 851584 88900 574008 816214 62264 225391 729578 664954 50695 359720 357547 453155 201342 770378 152585 512818 734237 21932 977305 940458 150578 44237 84089 271182 933394 418938 785471 417387 760442 450460 296129 383688 864315 719142 52714 181042 591267 399732 687937 958266 24702 653362 209863 912420 495890 487510 706531 460524 894397 622740 138298 398535 462021 12317 608661 204758 427714 541322 729144 845122 177464 214788 395592 581294 129461 750517 555864 877357 479690 147778 372204 959941 909196 817753 893002 373590 485390 364543 191811 904143 482095 287703 505705 125461 552127 71832 760268 251305 70802 803065 156115 456527 673229 110390 182022 778345 504300 926409 218072 8493 321976 37652 423437 163530 400003 283485 495679 409098 918900 620277 255229 538052 369063 252803 734165 161848 755830 515498 781942 960249 696529 155330 824561 890851 162601 829873 808526 974271 640736 212836 362112 151788 23593 205326 805952 250588 833404 5507 233678 767319 303315 65613 793103 17391 990152 616846 891174 251063 881873 315478 847191 744286 546499 347585 334366 732874 304594 526370 781267 697493 638198 833599 938296 591969 966743 238489 227239 230505 127986 617089 494440 85272 730332 516637 568006 754230 853317 633404 840634 888502 870629 627888 153506 932694 605708 503937 77052 957307 69181 953306 380768 584570 31372 426363 607346 573195 262500 347462 840834 346755 928100 121129 174087 426229 305987 10216 324991 703944 917479 623112 17464 564334 638201 303539 409604 95168 451338 927441 746495 804305 922609 27277 13916 594418 32527 110224 715013 894581 274526 650068 45841 176935 659829 449813 910128 850002 901919 978808 897348 395901 129370 647182 323874 385108 469882 949576 715020 354131 183286 75335 615271 676670 395121 228100 741529 835351 853678 641950 30592 840927 711948 182724 326 988107 313703 472367 976511 555381 718929 142910 65739 772639 708855 852625 146373 946444 749465 687581 444085 170791 388144 963566 449677 784349 603503 141559 410131 751573 647828 360564 564404 978024 898918 321925 947120 465496 63501 137773 140109 413983 22876 456543 650049 947716 29063 171755 253747 797790 997739 9668 439386 582304 895431 516807 668448 582250 465184 127402 513327 893744 706716 836360 600692 428314 205181 95470 352149 119282 386196 856495 777324 414335 706024 209336 386451 390597 209590 741372 233854 985984 395181 754329 697125 256061 838429 829991 7349 630087 503812 336131 781663 251774 972439 419273 811717 239767 264428 946176 102437 857878 225380 619295 468999 343319 262217 758127 29737 593193 456283 952866 194179 417185 860039 825397 29092 41375 296462 104124 373503 430252 410799 215431 130424 352729 889524 633239 661789 993280 476410 49563 434699 379076 468308 284651 737234 984943 668605 126869 859399 424152 456189 998108 617583 112306 340919 980708 611363 243220 677604 517556 679387 932546 223434 675037 661038 956521 68612 906748 302314 630454 819785 100668 526306 79086 976108 35104 534827 463197 203378 604524 556702 542517 888423 847919 44195 387745 600751 202595 499057 455530 312929 820790 991273 149641 205137 463884 497464 116820 629291 163896 670145 969001 200866 281401 572308 15537 546530 395236 182830 391177 519025 664126 948855 156086 928468 50218 995442 242097 955112 394667 829749 497948 458850 782006 756458 961923 535676 44129 418588 341399 65347 452381 166436 925456 608196 593476 226517 296367 445764 13480 320836 128471 342989 232783 801023 828601 779879 709493 504694 9424 776613 212116 3489 559717 151908 723617 264362 650490 450883 178568 790332 49151 74442 912890 419988 582701 161512 245058 212392 444697 956412 26251 25543 141263 965611 955677 641664 695135 315437 163705 339184 564915 167896 992575 201487 566999 33534 802239 77446 385450 158467 646143 2824 218109 859330 876808 220250 876546 486727 834383 435433 99576 228374 843421 861796 146383 364089 131135 711268 361171 47387 791416 30519 210844 33390 26885 493660 920715 263931 712405 635649 945990 998327 846975 876013 931621 536871 656398 386598 43358 903549 894141 197984 720565 925174 962509 908871 595815 220972 396113 172491 452106 108672 776998 487977 976517 447699 874762 687996 865395 380855 85479 639616 122721 529711 95531 291926 199156 677024 373629 968057 36094 14826 347750 367914 755994 546938 687521 516531 215410 537056 270763 560309 136978 545670 669834 110584 643420 34152 227939 450600 14064 501465 112143 978900 899738 24099 965735 809020 307926 308421 103248 38243 446251 902334 838562 282391 893529 780353 656124 346556 829946 292259 607954 247380 471239 918103 396316 783606 480400 639567 799030 527836 471125 930012 437219 71703 34027 225088 312432 409128 899150 601996 784246 418753 343357 346178 616146 185244 72761 134503 832770 754327 831195 52576 57400 930593 45770 448047 422317 607285 109992 445081 279328 287005 580283 127547 50955 461176 956690 799437 702151 904460 482110 101176 609349 474920 659963 801233 283966 445313 903300 551882 314488 654266 388394 340000 511528 300833 269007 783128 908956 720453 28146 306132 367842 121661 608144 688607 380210 575096 804586 951760 805242 444562 977838 428779 185114 643493 377755 24836 127195 113529 612566 434305 567629 404783 814453 527632 747589 805080 575074 282271 907256 623007 16850 443428 312333 335769 568297 508819 544115 422229 114883 714400 830230 710084 585064 934440 314295 893725 437685 420788 515661 270936 706329 375870 98032 243461 949889 346977 84299 672527 65956 896802 132368 977649 141 222891 935497 916205 432944 112471 778755 18609 142774 548788 100816 570660 349308 670324 706865 413912 479711 705065 61712 677157 459750 966694 88008 673443 100775 547208 170954 821594 237114 783678 616319 570812 888493 334233 177981 389203 236224 931586 43948 115880 546919 639565 30388 463480 49710 478988 281182 203432 381430 723992 554578 312906 967137 994312 249309 461276 395031 92747 737295 302187 302706 957328 715410 12734 225782 25565 769542 979018 877429 716619 556242 717437 877337 801950 216760 154707 438796 799271 894928 809596 511619 15347 920799 449512 357932 733251 958275 874848 502831 476132 543108 546522 268852 475769 170756 8688 128270 940842 367371 653844 732529 88811 561379 941737 295500 653184 945263 18488 363803 865948 881639 352432 288005 451199 808610 130007 331428 78699 628652 359869 341322 912556 620351 684719 608847 580363 7506 857521 910990 318985 878163 558192 2112 270155 969116 30729 282929 632056 734529 337852 359690 283053 651971 164072 215963 357499 874773 12184 990345 444323 346185 544301 568490 82472 578251 441966 853138 899803 87826 971332 897400 615212 794001 415263 510253 186339 840917 751732 488991 20310 641910 23759 76835 382396 928051 532666 635211 283657 697489 405642 196136 950062 442939 467937 178630 68209 539500 66961 21480 219701 239827 452037 110913 738119 381270 982313 387757 792803 523800 189812 539906 954638 320539 548713 277580 614077 381265 962273 219560 428962 815795 496516 577073 923683 994443 852740 789081 617341 986183 137483 725478 322738 154192 168667 963285 721564 405101 794264 228752 206883 350569 55721 165046 739679 960720 605705 28024 613083 303608 800036 436764 443957 66247 133257 401952 102329 190638 920448 347007 882081 91644 707971 396356 239276 167631 439693 819681 375488 406679 893151 577456 343515 976861 668151 505183 226762 972650 79291 268152 953670 467451 71514 610780 445436 721732 769921 988636 646175 307234 976372 843212 663009 92243 315016 713321 266384 536999 268537 726067 429104 600633 939079 174145 849283 33102 482273 353976 191521 239228 264741 925636 76636 4821 688446 129132 729537 353158 468423 674712 458654 566879 110117 768384 517875 559715 371889 398387 873524 323018 259769 230239 585984 458557 29347 71441 636490 117246 849273 314394 498282 986975 952878 147842 848587 923975 889948 886934 624533 574575 619011 924655 733855 687750 504486 877702 791582 341650 682136 331835 863720 365236 110111 977074 8766 86671 992815 136901 997678 673809 62417 675760 334503 408815 531431 866251 462558 21170 152264 56726 621562 246990 978061 398378 377502 188054 175087 814826 642621 85334 79399 983929 456441 17176 440923 273498 444509 391972 395339 527320 907565 49169 381736 263954 500294 82624 615060 659385 104033 761385 707299 52687 389046 658536 168199 390922 636993 152939 659110 683450 356217 9545 384004 214341 99547 403380 668279 981527 116399 577341 292787 68897 326844 989707 98773 428864 183634 481060 443343 844088 513141 224755 985408 594096 10345 525598 638880 487135 792409 649674 208373 702275 850533 631852 419231 219181 941667 889539 83777 964886 384161 436108 911899 124532 229232 291621 206629 659121 231625 508596 897313 305578 337338 773500 140413 693951 14813 376221 262270 149622 368677 24952 975895 427189 545176 120295 219060 989067 381787 181469 611829 353112 181370 620073 718079 674794 506799 322126 79051 98495 229486 493307 392068 591921 952830 533757 529146 775603 454882 105785 568135 375290 438533 796449 234839 275619 972073 408388 341566 530320 649599 758004 18019 21466 278793 343290 934905 740035 988678 789012 720610 317100 702710 171500 286147 196869 942021 154850 956536 61952 380700 958850 355078 523787 617798 132305 533709 807162 813184 990195 388542 697744 25895 571484 871449 931115 126901 850437 760672 928560 828627 54558 619583 971090 400141 443421 913156 740450 675047 415907 115890 549252 977871 137719 769116 886639 813447 768446 506561 24903 126647 771932 681362 692523 85424 810240 736944 5365 549710 331571 918929 322171 498334 789132 651651 814901 432185 621408 537490 919519 911598 956577 488885 118316 871828 478091 815814 517546 746270 998998 55648 736096 452496 597433 149866 648579 644775 571698 255758 74439 626568 122706 808212 744675 893017 603688 140018 111223 802610 328134 506940 759895 393106 643693 674132 669396 993310 44025 961536 137963 437651 406811 511725 225413 570232 543248 904010 490612 396625 620348 411495 130758 893064 907846 316405 75443 972642 691751 177179 985226 94571 811649 548076 554499 889095 858141 938730 682064 644380 38296 70917 691414 151005 366134 923904 490978 841894 735543 68875 437484 464584 368156 831 486537 294406 576072 889172 682455 440740 572347 781796 618150 875474 74788 596252 741728 303866 228534 8532 714157 453639 581551 201909 748743 176750 162656 986203 490878 613292 503384 940151 561287 108448 380401 24627 960715 339991 395093 324432 490639 58015 438627 828967 378523 644462 809343 959578 76929 136004 721373 954650 792911 278169 679783 884003 85827 968830 6485 490830 78111 318523 211111 118682 5526 913038 81226 709713 396041 239518 484930 828569 550377 765356 396414 691228 787381 961329 405689 712365 556861 760207 385034 698096 430246 226616 579484 265150 959401 97685 668475 46388 165898 741365 233672 128532 63526 37430 537014 467990 105902 710334 510406 443658 549822 235990 884769 189139 146322 210148 656629 44813 168501 184276 156717 269773 22693 908088 118270 26833 183953 47286 999241 205605 34176 447596 296753 690299 782917 969138 230023 172287 749185 755221 967443 154715 8957 412156 815959 271719 557274 532668 938728 817293 906616 907411 334329 477515 636610 994307 414058 287390 654791 902791 811702 729148 130008 635543 600523 567216 47924 524213 366797 923763 501172 597355 341719 183705 810338 338766 593461 861512 685398 499238 673793 470867 67096 795246 543364 900169 813880 68147 786946 869600 114002 32939 35946 531119 663991 339840 79805 34896 96809 917223 296498 562551 688065 66608 208625 259199 788413 557101 209874 701221 619051 883823 199336 779219 431997 568640 237264 629174 860212 895562 138543 154051 482381 615854 681979 29107 808854 55169 565063 297677 619380 241239 382478 710324 415299 62531 550807 658714 970617 117592 405761 555800 304296 191355 792731 231957 650831 40007 19341 154493 772643 231665 45112 792942 983787 784898 654141 664908 289332 419776 36267 475936 847840 256938 882542 845106 678034 696995 22023 93447 940642 312226 440025 858116 360653 775314 778479 154401 388825 588273 908508 504038 138221 526090 818595 571503 787845 230854 3312 324710 189126 894707 515488 336502 297309 175529 11187 939086 630493 86507 955046 999520 917296 923824 802075 60115 611233 669741 113011 548845 138579 467371 546718 930097 929203 317921 576241 671438 310137 903433 665740 674139 629888 313405 838201 891778 929230 421385 678143 168976 60755 589893 660399 567688 404153 749105 513497 56338 207693 826613 555612 717853 754154 117589 267083 200224 846961 203532 412869 848413 116772 231719 391030 170413 220268 245115 848144 671935 311627 802810 104258 26920 88281 615733 605782 290478 408777 555587 651052 630466 229922 335571 861661 645124 608595 429772 515675 645587 863627 993185 324151 211233 775539 816873 399161 350875 654980 20110 401523 545479 824345 893073 891106 460935 308081 168685 503312 283452 304018 997130 249335 363561 744681 880912 988059 28345 824971 601910 820016 265274 601824 594368 380387 778691 751804 354826 681626 221552 776701 54242 15575 462761 709021 239853 400630 911521 83108 885858 543022 639451 124359 673933 372433 324338 862075 914965 687378 887388 317344 172215 285224 104627 273123 473413 477170 87921 382665 312651 648877 894536 544517 882798 817077 651669 709614 457102 227813 871592 348206 306351 670404 833298 713084 363464 106668 221162 797963 67574 115342 628756 603378 42444 470844 505939 216016 485111 875822 566210 662295 178443 719134 316788 896680 782379 204868 981950 649603 582179 217677 52686 459104 500065 664692 665406 50246 936589 596074 107420 661585 763514 673803 807169 809204 923836 744606 907606 967333 165374 985856 736923 931476 932831 138043 764075 813787 166161 545759 347539 119816 331982 355598 87238 916991 687170 330802 328680 628753 852761 815807 789845 823934 48995 275558 616630 302611 180245 59272 475692 626784 651862 329924 242676 255916 547201 587918 49910 636041 960509 32863 644283 867671 938734 541037 62436 340115 221931 306163 108783 866402 668765 671222 619412 914288 969484 305392 442703 921999 378094 933521 762091 518881 53309 242916 419362 584522 551618 175844 278494 560075 220420 536699 861389 977197 463676 584644 302391 254507 993352 8318 970692 599938 825165 919711 638625 645333 678695 451704 344337 397907 599684 145931 948824 698304 30205 554933 606339 483030 952699 607902 260447 73621 908981 128737 26901 664546 44408 948442 553235 559976 24905 895134 460932 356127 275347 485034 840983 998753 455036 338138 314703 853 792416 109309 104498 882350 990446 549555 507916 660217 505579 732393 735603 347802 928914 536726 292047 700319 313110 789063 562305 94021 769879 473247 23087 269861 53525 2622 34392 17427 369919 399343 475607 773104 615103 291215 129632 624737 930293 975673 291580 491386 5850 696777 482097 992867 860118 466473 138545 376101 984559 416275 347075 889278 89326 636183 304345 212189 169893 512580 306352 4379 512422 438797 223508 772624 580254 899688 777551 649059 224359 972812 337183 270983 646231 123091 444557 220418 295549 450478 801369 329444 866707 358564 640009 917824 281269 718157 149769 889953 216887 160993 365877 750850 21209 83278 486154 350358 907285 894304 298802 986108 31415 65642 804922 189478 761422 324139 489917 720677 856545 289196 474130 995995 40216 560744 807344 927250 214657 328044 860593 43505 482442 383270 416027 911296 766617 762399 480388 459922 564017 456894 216215 434641 864194 968603 267839 552626 30138 637198 616655 54673 201188 64811 79236 194525 690481 17472 273003 7429 72157 938665 401045 39825 107718 267884 825689 853760 831226 681164 397427 620676 555838 39871 776281 718031 373690 699066 27806 390519 32218 835816 365958 134360 717951 163296 976935 84537 380414 792002 919162 972195 237877 779421 200541 530672 667136 135726 410449 358975 923179 326077 674116 372233 75218 120013 848775 555449 686968 347423 28289 260412 621208 223511 545063 326221 29914 746414 206850 630985 852913 622833 943005 835476 141282 397863 126125 780264 79880 57053 964909 1893 198249 57321 462857 920744 698352 118978 833554 483448 712961 299330 939218 40289 596220 292991 226349 988155 641855 111931 140339 420088 700350 323003 474924 159043 443889 86896 17469 237155 277855 271936 262083 844267 590175 334058 223829 124810 927269 449547 143983 984529 385674 812254 842345 994037 122677 711802 530911 767949 699975 423307 595828 228690 930423 648151 754367 255087 435516 956918 88630 67661 164413 325054 808670 486791 277748 355382 464125 321269 531755 425945 676489 529558 827498 655277 429042 391448 576211 400560 716081 771641 544781 889779 404673 872534 558750 226114 168251 259064 688030 578091 944222 270388 678764 597563 547789 639956 640930 482501 821091 220288 282429 50865 470477 769882 447973 487686 554821 632231 62269 757879 446894 206804 398248 837532 294153 642772 317291 865994 91429 226992 720462 415248 24265 141637 253769 870979 835268 424922 913905 527382 765377 553264 947170 537457 99777 130914 513054 243112 925896 993892 784777 415918 956272 165981 470198 830659 239662 559416 154172 814298 335644 544669 85499 897177 190780 29098 751946 351710 831870 578921 279372 16311 141792 386266 895043 349550 544800 712123 938936 320172 46833 62865 197452 886446 945993 535353 507728 160545 218317 650327 587570 410731 998111 946763 885495 333839 624081 119687 213343 789147 985883 676225 673612 373667 230052 507284 858875 154681 413013 759830 801361 813285 163940 510070 152522 984966 410664 327371 18664 908 332161 836709 899886 624800 787318 183245 167605 91986 988709 913147 283253 812247 931952 33893 139510 425048 181215 558112 233588 127138 659374 901114 91003 475310 34674 110656 370018 884640 883005 851569 412597 799712 258352 131065 391389 542319 621373 393813 521724 426566 216562 899097 926942 665241 603052 588506 54587 506733 138347 88012 454137 276643 39283 769100 30649 58509 195064 302169 956907 469486 718562 500796 519780 427977 249126 228808 374623 635366 817749 739003 900385 456930 21628 228740 641915 120565 800094 818419 844402 807645 264350 923634 495674 864586 338830 168860 346829 321197 303288 254402 962213 121843 775292 664976 991502 178283 150469 834195 259071 97070 652145 811744 257051 248049 400690 629933 646194 82488 154314 375427 99216 363420 555144 561453 827977 938439 968909 239718 372441 269372 886059 391509 440296 882715 624617 94488 163533 377954 309278 596728 288543 117887 593465 385695 952388 66655 966867 933635 925380 248418 667353 840648 117946 512338 615474 970264 820140 114028 167095 441288 16308 905059 345384 458448 44968 905544 570283 681784 205238 452295 966870 69755 347847 552247 908746 20485 669938 131278 314812 650114 882983 834799 138716 503696 840945 704594 651692 259542 625125 884676 907612 740681 284572 934560 275111 213241 136380 316609 743240 478421 774399 678820 640828 223306 230572 808699 753685 481677 2513 771519 621459 663486 932784 377856 621666 671323 419108 56392 7370 93509 259303 731955 295433 25871 175680 430717 390261 639382 621224 599014 334038 521210 899481 279983 207431 546378 921428 546398 311226 44402 33301 318878 995182 338600 467555 652371 631764 426734 253168 505396 423911 355283 617555 75399 832816 323176 559188 57194 292672 847262 438184 979617 672731 405041 591491 680753 1698 458699 964699 241055 740459 811187 960072 85532 817160 763537 707261 723021 285503 930431 338396 271001 264684 496236 978377 622143 394539 974819 612478 678642 278565 617590 59341 221847 432751 842699 970628 551494 61267 103169 846344 753682 855254 671099 539858 128804 440832 878702 162805 176364 620991 853846 796274 80447 232662 453519 93783 926082 504103 810092 799815 970148 312097 91418 967706 360006 15865 73155 461826 378594 284256 24804 449208 385105 29331 35623 51067 687182 864305 961124 241387 313698 118809 812477 781777 919023 148854 258151 76809 457846 374529 667898 325689 64024 320838 259600 370777 473291 707929 336801 228575 580871 973399 588013 418363 342654 940515 498332 32009 852912 274725 255420 431809 961607 473130 841836 772712 299946 856862 75233 671110 219974 321584 948155 568769 909908 481222 989681 941830 302199 636456 769255 634419 529854 528901 387078 890042 579986 569136 785299 493890 580845 561617 786867 654970 69210 676773 256417 561265 736346 247099 163877 696140 533773 755437 470469 347055 821171 772710 248777 507361 391709 600297 807182 101492 581892 778940 481797 652992 399122 762171 951520 230667 451211 318073 595846 799282 937050 840924 759460 614907 5086 420963 434230 541833 842612 577624 244913 711987 834194 878852 713532 748653 646777 364903 301935 78090 837163 736913 867000 452364 926943 35831 729267 840712 592636 102583 606864 710570 724398 501926 560356 308347 357317 449289 404063 209650 369035 441386 55283 266951 887363 664059 483712 57301 232592 951629 798950 776842 146990 776278 68375 396566 591093 158288 500327 318830 207240 243861 200338 470720 556293 823566 437523 108894 500529 107147 703211 192644 893635 635682 45509 956546 360303 835892 428872 710525 926259 894336 314446 208387 418122 33761 702041 379292 405898 191186 760859 575656 395040 544324 268938 538901 298298 450053 414841 193396 731357 651990 879471 183618 103556 327352 764864 666722 958788 544768 679881 823899 177122 274052 992628 583220 712629 823756 574730 392678 292938 327564 89416 442685 855194 819549 12570 368046 51093 219296 286927 774589 524968 270553 839450 298611 673213 310184 974306 44293 894242 51730 393100 745 40914 481551 68345 982251 400279 284144 683875 135276 249287 253798 433843 173270 335210 935013 238875 690139 426433 403705 74910 425800 255590 853990 26018 344651 486963 474866 328591 254278 570054 362374 105686 600231 262627 710963 996673 818740 300908 908251 321578 184992 72862 570187 617404 189405 990112 418851 933776 973386 926458 59677 820959 427497 48880 874628 773391 598767 511357 381439 212455 487908 600386 877994 803191 201285 205357 856880 407411 596342 330754 761410 249666 351308 495612 604286 15322 69812 351088 350369 750020 426882 612545 841828 570889 538179 299118 698462 974470 151497 628991 139429 262236 222985 194989 948723 969763 434393 550214 74148 368010 441770 987334 862827 460491 153029 712861 654535 320645 796728 926145 614443 788897 75850 168378 302144 107296 646590 836101 77630 265520 604297 838101 722644 858908 681002 189721 805866 727290 262225 747185 146931 951264 780553 413817 229636 432851 990384 637200 301044 53883 458516 446670 955075 864093 737821 559448 856934 976008 285066 448003 582062 259530 560936 824170 561833 984148 86325 783718 51913 313322 897709 528805 996992 19359 79577 107115 240338 395436 18043 114183 309677 715705 985301 824158 572919 936627 2155 86424 844531 149667 454519 619955 958093 307053 693833 765319 424819 142718 46011 326977 799247 177937 758079 805649 212072 664932 835346 920310 137292 64922 646096 419209 874960 921980 8384 345346 263003 816359 576265 457953 879502 584054 218057 746858 418744 262781 584120 912919 883550 15445 711544 11978 86778 31948 491379 48189 792514 589317 450470 959752 978000 914154 434596 473703 430492 136623 507712 441523 618068 454413 91733 246975 687187 368043 861777 84199 100453 759165 521497 601200 486632 245985 376311 392893 703505 567417 795729 142842 460480 839946 359143 978291 567418 565037 57744 515169 296929 33686 375609 147857 67834 611592 962321 757631 816234 859585 1395 947952 919248 812526 661120 517532 144262 584900 477167 514559 818372 394985 332736 972090 60993 714019 606886 929194 921911 833485 428811 477591 293520 604601 11661 21532 865980 707426 944915 617058 101283 609550 33916 173266 546206 988949 657747 407870 397279 340367 906385 407952 707042 411242 799610 171126 624424 45972 1620 542859 927797 96187 514345 728570 520934 86150 242661 195327 663316 738142 730933 37103 506563 564512 97910 166418 893305 861723 799446 141303 151743 795645 523192 300506 397868 809545 968615 24639 992333 368310 938794 810720 665762 971184 531134 228473 970380 47130 17113 930668 859160 437297 572732 813240 392989 183989 560721 743790 474835 4278 135584 929182 109056 415568 117807 250809 672720 702231 939692 64614 141001 271789 353291 157300 427257 346434 508487 69035 913430 558268 273993 872652 251536 680538 922799 993632 572925 771082 947966 118234 646289 965992 6219 764601 772157 351919 960637 606610 176096 765917 313936 905426 63898 301698 914396 19329 264184 26222 570116 64455 522762 760460 386965 449633 906926 560685 998960 669255 120606 871401 492163 873924 841890 895247 341101 580244 515248 4033 151511 718129 65446 916078 64118 784537 639350 184350 703663 656885 693093 718966 979015 829959 794418 188437 538887 936623 54601 926155 316217 91154 818081 763263 823240 143482 791168 123946 913805 13072 502448 208781 489801 535046 863541 465185 367251 47903 748001 987735 980964 892533 247249 65895 12182 850197 397249 649917 138941 871767 995999 41233 961261 754270 34016 997642 132469 178465 706533 459044 743540 52241 480014 569814 729844 404987 134473 741653 323154 587387 197042 972598 986854 461714 259278 674315 796578 761807 922178 476732 247921 31833 868829 106410 766008 89118 206766 608269 724460 236635 419872 473671 249606 922958 700918 993105 219754 173373 304088 649015 57463 131381 29641 660668 699503 805440 620177 363367 950125 568470 81987 550662 801295 243028 674547 607977 466306 668545 189908 935319 916812 847597 184671 197228 993211 348333 222509 693211 85502 432326 610869 116579 19760 918734 21558 962308 765102 501703 394784 543742 776428 140236 800493 567360 74215 699162 836928 474524 853652 186809 56457 168248 142592 999820 676327 574942 692145 566734 699130 116529 364923 989538 995205 20891 596576 678933 834964 530908 690183 513534 757543 796547 823383 567978 71682 851750 617530 918733 545133 76713 944447 485188 664807 559255 308268 97416 171488 636464 51050 446117 649447 941222 95765 694432 892828 727681 862368 899425 23761 418286 477651 707496 884961 538795 446550 104087 247905 673832 877376 869356 384171 721478 783023 192751 305274 494845 875165 659577 745286 864377 251648 971496 876624 694870 736969 699565 115853 871950 193570 588925 259948 29887 23956 96104 176235 693070 882668 814596 740775 268595 617176 313502 640254 478977 688572 757382 278995 100899 382753 793561 676769 446884 32867 119463 533793 252942 209725 637788 742071 862850 422927 617506 499179 69943 97155 664087 552323 986530 579904 807782 65770 450180 647327 535774 909963 16497 116244 822188 595121 900072 369516 633283 547826 279635 314914 737828 138148 418052 672244 927403 217593 708054 475316 563633 481772 430774 815624 88316 605502 147138 637328 880154 419510 301421 628494 976996 387329 670272 889511 177075 829506 640353 885583 352214 778066 744859 516677 568702 796493 289478 407345 741347 850773 73121 277892 792885 435694 986323 654182 450156 740494 669690 133662 603548 870473 141416 476066 127585 998220 834227 64022 896945 805841 276273 473499 909976 913721 244795 922262 820149 321257 278531 956791 871573 779032 891979 731738 692262 481676 68389 895411 401509 245214 259423 104239 722014 706212 631895 180944 274439 818620 377632 489166 257882 858158 863986 934826 915073 447469 986282 855504 88946 549438 140060 966606 588623 608471 473343 777058 399773 324000 543512 32977 463358 155614 149295 353992 359492 701650 584977 904637 200422 944899 262045 665132 888057 191578 107046 341639 287467 339664 501714 441887 977913 100015 132219 525745 584025 347519 876775 888863 721668 291768 102882 627542 499091 232778 603483 911090 663127 587320 782818 38154 185591 750628 442943 364847 450628 769664 175613 402968 186514 800799 200542 126400 739854 364617 23121 768906 90923 918788 432917 515450 497453 151929 262092 715008 395734 231254 334698 611750 392124 350331 395324 482887 454539 735496 135555 66970 150269 121109 991199 222464 510138 138029 252340 228054 431617 249644 998205 959527 889560 773747 139943 997094 685232 785933 649124 805973 381461 553346 646572 291519 137419 940503 428785 527968 881979 599833 207372 621833 596019 732575 978149 766598 318854 988425 859040 672952 35315 992787 777837 493324 512668 856933 84107 904725 188764 809810 899171 479971 225020 346217 783995 4287 793318 217388 215207 202095 839314 993689 34297 878719 202433 30613 902868 697213 609126 896560 220889 656713 382318 768710 305226 123625 976518 683022 904427 373815 868564 797929 443447 324714 760488 355204 504913 931980 995219 333838 14333 352141 134078 803660 813305 242129 240294 938538 170844 850871 513190 998651 533738 269674 445945 272946 355421 995382 834022 839594 417596 672846 255655 633279 857596 104090 914380 510720 26269 455539 133356 782550 755086 71075 905221 145197 526858 734003 545135 531060 806154 151667 727148 936018 975561 112623 930463 344489 165114 250164 563208 536258 730204 879508 633351 395558 42390 909544 600875 683164 375874 790184 907890 779984 782083 738010 626768 603997 78873 42248 409633 943563 219126 369901 732736 310018 859210 286721 181401 996685 720583 248568 353494 984414 480909 81083 231196 792709 332910 74828 77903 95804 680652 61379 628976 703660 223839 511233 137028 71945 955745 524161 445948 961700 195384 528465 922691 176233 735104 341635 351335 834720 748267 274547 129795 76444 136576 799401 386303 697143 322070 322240 704736 342273 420930