1000
2 2 2 1 2 2 2 1 2 1 1 1 1 1 2 2 1 2 2 1 2 2 2 1 2 1 2 2 1 2 2 2 2 1 2 1 1 1 1 2 2 1 2 1 1 1 2 2 2 2 1 1 2 1 2 2 2 2 2 2 1 1 2 1 2 2 2 2 1 2 1 2 1 2 1 2 2 2 2 1 2 2 2 1 1 2 2 1 2 2 2 2 2 1 1 1 1 2 1 1 1 2 1 2 2 2 2 2 2 2 2 1 2 2 1 2 1 2 2 1 2 1 1 1 1 2 1 1 2 1 1 2 2 2 2 1 2 2 1 1 2 1 1 2 1 2 1 2 2 1 2 1 2 2 2 1 2 2 2 2 1 1 2 2 2 2 1 2 1 2 1 2 1 2 1 1 2 1 2 2 2 1 1 1 1 2 1 2 1 1 2 2 2 2 2 1 1 2 2 1 2 1 2 1 1 2 1 1 2 1 2 1 2 1 2 1 2 1 1 1 2 2 2 2 2 1 1 1 2 2 2 2 1 1 2 2 2 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 2 1 2 2 2 1 2 1 2 2 2 1 2 1 2 1 2 2 2 1 2 2 1 1 2 2 2 2 1 1 2 1 2 2 1 2 2 2 2 2 1 2 2 2 2 1 2 2 1 2 2 2 2 1 2 2 2 2 2 1 1 2 2 2 2 1 1 2 1 2 2 1 1 1 2 1 1 1 2 1 2 1 1 2 2 1 1 2 2 1 2 2 1 2 2 2 2 1 2 2 1 2 1 2 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 2 2 2 1 2 1 1 2 1 2 2 1 2 1 2 1 2 2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 2 2 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 2 2 1 1 1 2 2 2 1 1 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 1 1 1 1 2 1 1 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 2 2 2 2 1 2 2 2 1 1 2 1 1 2 1 1 1 1 2 2 1 2 2 1 2 2 2 2 2 2 1 1 2 2 1 2 2 1 2 2 2 2 2 2 2 1 2 1 2 2 2 2 2 1 2 2 1 1 1 1 2 1 2 2 2 1 1 2 2 2 1 2 2 2 1 2 2 1 2 2 2 2 2 2 1 1 1 1 1 1 2 1 1 1 2 2 1 2 2 1 1 2 2 2 2 2 2 2 1 1 2 1 1 1 1 2 2 1 2 2 1 2 2 1 2 2 2 2 2 2 2 2 2 1 1 2 1 2 2 2 2 2 1 2 1 1 2 1 1 2 1 2 2 1 1 2 1 2 2 2 2 2 1 2 2 1 1 1 2 2 2 1 2 2 1 2 1 1 1 1 2 2 2 2 2 2 1 2 2 1 2 2 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1 2 2 2 1 1 2 2 1 2 1 2 1 1 1 2 2 2 1 1 1 2 2 1 1 1 1 1 1 1 2 2 2 2 1 2 2 1 2 2 1 2 2 2 1 2 1 1 2 2 1 2 1 2 2 2 2 1 2 1 2 2 2 2 1 2 2 1 2 2 1 1 1 1 2 2 2 2 1 2 2 1 2 2 2 1 1 2 2 1 2 2 1 2 2 2 2 2 2 1 1 2 2 1 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 1 2 2 1 2 2 2 2 1 2 2 2 2 2 2 1 2 2 1 2 2 1 2 2 1 2 2 2 1 2 2 1 2 1 1 2 2 2 1 1 2 2 1 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 1 2 1 2 2 1 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 1 2 2 1 1 1 2 2 2 2 1 1 1 2 2 2 2 1 1 1 1 2 2 1 2 2 2 1 2 1 1 1 2 1 2 1 2 1 2 2 2 1 2 1 2 1 1 1 1 1 1 1 2 2 1 1 2 1 1 2 2 1 1 1 2 1 1 1 1 1 2 2 2 1 2 1 1 1 1 2 2 2 2 1 1 1 1 2 2 1 2 1 2 1 2 1 1 1
631780937 388568971 291338961 595680219 832389067 381302895 759037516 58136814 372291055 488965758 641340522 783092222 155789291 501925354 676424476 446247524 69551669 793856499 422778877 791043863 130235323 418507395 331185136 410968673 815381634 23441133 214497186 61275553 982483643 505578168 547227854 927521104 588649935 82007034 489979090 16139797 326449312 440178063 361260573 276130130 230623002 548954805 181154177 133125817 785874213 97376411 381479712 612164771 826591180 633288046 36071873 676530484 922505838 211445547 725091523 588966267 760340191 377662724 345208259 160718277 417519976 515380918 296515999 635110535 450536108 90051370 276631000 445645735 565429831 894140112 602702315 318150579 26278362 439978915 678774275 650475070 966433691 22537808 381318485 681269071 425528103 697625887 894650985 443025696 438446697 317019945 151773897 966259420 74531895 510836065 53809147 582795515 133861176 491528742 961516485 950789901 654956757 363920185 149087344 122995012 237433397 860298158 843609482 247493164 224885686 59176034 925191832 417157076 783019621 780051413 417640494 296363037 802739409 786294041 1676133 12160469 961934799 673786443 626717643 830231542 288627114 364257827 67504503 386356976 495802328 274979289 917737878 422869791 707865694 60613773 231260952 432828102 586917510 875644942 904097720 985050729 615824865 458644941 390347189 336682467 201525555 22873847 636935529 61944916 596162385 294153948 59431990 522836233 665408950 516790453 980593976 579994625 328727926 950029468 16210477 787664099 877878806 561717747 976256479 535571506 167367580 230820557 232070624 579582329 868024184 498610660 351866895 179161070 866180714 73706435 6982419 764613761 614812455 424794293 449682094 802003146 780752720 590618443 353937773 529706073 665578897 970773033 156991568 844599264 912279339 749237961 364169489 361951081 912085087 749741297 584577271 648534055 697927532 196751588 111806487 608332772 631544044 486092896 252141150 245663573 45390843 57453861 199750302 452230782 542405761 583616265 151308893 831802258 28611075 916646115 438496565 690603604 323475725 497338838 553759268 783176757 829882738 334520903 832643474 129156035 911012293 670290579 749750043 205912981 357182817 967734206 268870516 576471096 653053467 779288270 732674523 104553644 104777849 363839783 825802460 265916465 55967115 715419347 556941790 973230043 755827601 106711473 690236802 892570564 951998452 559600056 957561591 258193674 464873304 88867862 384152540 773859906 986680039 956200283 975112286 505999312 549713834 664661698 631948831 446649029 951617998 389854374 16699908 194087506 850593031 550117085 795500929 787584431 208190893 200962965 89717539 161057777 269096565 263475666 700829274 76395488 709731163 827901971 760231318 946528640 985707196 153484705 201500052 504446114 889969975 780479898 469407264 811401337 534890032 695783187 29952395 4679401 408686540 314752919 811470185 458231833 738916493 515457071 580174927 963989020 882759631 4394516 352088533 67600594 445933631 792032083 96541888 845352829 685596718 353605922 123339622 230678900 192296430 597162980 141481294 6054179 685971040 231520851 81497578 936884688 748509609 173586234 99429450 843056429 475922533 880604614 147153441 643016084 841563306 315176132 203329757 514129260 408407778 788809453 1406480 797415285 256779747 256243586 406642249 457144073 122945667 50152700 914115935 383587699 2684257 135350381 419961446 150294267 5162440 804782223 465153426 143629452 998981670 974110328 23746126 815481095 137141192 3540191 249484028 802110412 149200025 108730448 785563039 24233003 965542666 288104687 767124527 201278471 126290294 175191334 176813346 237935915 860564407 47523369 501230785 55467432 602212261 194929866 49061537 415032494 909589558 652253712 220990685 242715604 767460477 346583019 258340732 116937472 762040492 371102486 31574922 512498544 72717003 573110245 733709804 339200544 137835079 80442886 886943432 560400982 345028188 390194176 281391459 609958000 308999246 754064231 85468544 965772295 620860035 595571084 720477428 727196121 647384628 480064244 244895082 971884561 59317855 566846156 281368215 844745228 609179530 912743803 445185047 861327498 281779603 848936473 333155762 335915701 198540989 291057438 65389305 90716814 203149585 689012628 37785867 315972410 745095596 728548099 188027195 672711212 119107565 489423494 769512373 37467481 582408012 317099334 160525627 169392140 665644985 621425416 495438085 381102836 747197542 151520817 163379864 566169291 841432351 835115139 430279364 679361735 405263603 860186553 220260987 872910957 549679575 312262129 738987482 46615855 711676203 505990150 46210935 795325640 852052293 97669248 114871319 178677349 813531949 808472167 609858992 214182846 816578497 372442160 247254894 979091949 411990694 310138840 635911721 961235107 843291380 413079526 50948741 302064212 717734246 467163591 235047413 150617934 981428761 621470211 446403294 400836841 667087931 240347493 647542401 598545671 368026827 843588762 685296632 275389222 983551544 156496273 887442535 912626797 259180742 531508780 166370983 226803720 905240133 423911172 318167285 708984139 867473634 413316398 21020503 782804304 847634287 826696587 475902025 708189002 71198656 835587427 523084595 171246239 483959563 150063392 837217754 546601819 238442690 58127957 848161786 143315987 12569052 661978640 332541234 391174586 760120420 367593668 834770453 358983688 718407730 718196415 713013441 770084246 929893675 171079468 711934021 860097901 945676357 207087568 251829524 713251591 832510050 494995789 237162630 268615086 944251195 26285180 837301697 854007240 645549760 959871987 834090538 303263398 728284265 724695574 725005859 173458205 345395819 677599904 725195295 600115 18083250 685576933 145174682 813879910 705515136 853424870 873826358 668343411 564618976 910025118 566428693 326323934 911090821 541441261 985136791 384886693 812998868 775170733 168162229 637136273 433249262 868309117 263767968 723831638 940111571 786647384 636501189 494034023 925380866 89305405 583128339 824165768 905473690 870060897 965350515 337599057 999437766 927635806 722364632 717093344 26652624 144170235 762244106 74826813 462794713 734152038 201078053 821631618 278506350 15633471 76981234 824047909 514408874 497702456 62453667 826103391 296062682 909997777 526994014 598579403 696632107 405997071 47163582 855163390 65049482 130699963 845614397 594593166 9976664 31495364 702886113 372247887 936898971 715692265 226077945 746027456 427088368 922467783 134281784 696022641 863696976 565271750 260846756 344368062 355150477 504036190 133476917 169984230 491610368 460695314 209246376 390728127 936961621 577113038 393825735 48937618 106522174 471326520 90707438 508806181 153757818 181549724 651004667 682585258 741930743 36639200 993437934 558347903 78479258 571366930 452484092 874506593 995147398 610556078 166171366 471896441 240686157 542246101 628685157 839892671 73824092 831124426 103138452 613506655 671133963 690421444 88917023 224537062 335879046 706708043 416674691 922246882 272280221 794844686 661820437 727919128 110345535 114958625 525538646 382330561 697189059 160070589 391620495 423390435 813090353 412042588 229802786 376532816 242648038 684322106 28208662 753077338 448006766 19568160 97015254 432019909 673234499 198820901 993269429 675610121 15410580 222458345 412088792 380501725 318830110 579587763 713593575 461596751 171751391 972669913 587457248 181888941 957733520 529270668 515465246 427979968 525748482 919548142 440017363 202233335 499648438 324999767 940829770 122350733 590625329 644455027 6824688 789265408 764901847 739304711 717191571 728549380 703112673 333500776 619371505 939207016 276285071 292733754 153369476 863800468 966604795 692172513 65271921 341269204 726687032 294841265 125352049 330755195 701403385 644033264 174785250 224980253 571880137 540609565 755615859 134062427 357589965 66572841 157555898 13159175 810013572 93643307 212732276 773034134 407997599 687734771 517378818 449486614 13177996 660768775 753517326 893502465 897322311 753199092 617073919 467886817 725162457 458580572 379111592 217121158 287827739 274681221 823302952 120209653 767983243 63925900 269396898 977304046 559840502 640574671 957989362 716465881 493665366 408404850 25291229 299868674 623108347 761542657 12330646 969005397 402473623 124737611 809241547 744307418 896538347 478400757 840348059 620908956 55258354 487554327 329830061 363570097 65275159 849164959 687442654 384717287 536862078 432427303 32531552 840822150 309825425 793084826 695989893 390035688 471187562 39624322 411340245 184464599 94307710 914605938 901250120 328576371 466502314 266734338 843868504 482335583 968105475 585874707 906266219 621998378 647169259 315510112 777362971 93909616 755088417 344460412 922093883 5257646 440978319 141705618 226534743 659920793 864262341 884972652 470124721 843303880 305099853 954676116 718395426 511670763 466562701 352321187 630281101 272157733 267107093 250451059 876935933 506872690 565066056 106951344 486856908 217698588 473492749 222704926 431912604 705565524 791031462 654535347 569830106 99727167 787642537 335520007 292417600 919828655 623797265 413242892 342178840 527890278 728530494 870973010 744279331 3446053 212756005 41771131 202589458 505660420 96190970 913320760 345406240 392593115 191035236 485429284 458946052 584626339 138491828 638987406 932898678 502523265 205784294 628541650 539591795 363158025 844799642 550630567 258320412 207136691 834198243 463590462 952962975 630036138 54614076 945869610 425401370 983588206 934709969 772267335 53801467 482337717 515320549 184170015 133451281 903604364 541783296 391904171 814695656 732140692 270618401 37653286 726580991 84568480 293732450 155119377 262231304 155412511 268872909 521519868 156630259 447609353 377130106 914488436 100973188 588091920 898854730 9153790 530660865 926663695 17926668 544276675 798585790 950807599
