500 30
741719510 646445985 288528865 130324436 1022674617 794527463 415832068 696488643 894375667 529476111 616320251 1029690979 734912409 248189699 172160308 945539459 847444438 515073105 500736852 605995961 546746534 277230057 733100842 50105520 173158903 749974153 936777435 482380146 488416539 835778209 769646594 381653226 846275260 1018651833 586148047 594631957 181507620 1002995644 289684435 680841141 910339829 76779779 489291223 18730544 182552388 1043236941 1072216722 47225708 354017570 1041237934 574761007 378591440 850584098 491921789 468744355 559763954 58805638 960561520 849768230 943531458 916837050 372890519 252485165 579700420 493522799 13324996 270130066 368294984 666003661 421772070 753110404 168551007 361174168 178037918 503417291 578751551 376847173 559169762 490513418 1032194069 109008556 902178535 198829705 695460603 898537098 503999581 514613177 920517953 285979240 921631510 459611383 519992417 662649662 867015878 283573697 649837198 923403319 236390213 672314148 154925331 754036855 601677541 872421347 860210290 815684294 25518036 118319341 1015011399 486836971 490309866 291192156 1040511498 882303805 397105631 428453242 1005342130 248050535 343043517 392713720 723720377 294174092 1067695832 112517146 693744050 437172268 429548743 944404518 519657831 925135428 530255865 358357057 109644476 934234256 292802544 335248884 468120318 346358429 589783145 104696905 640099915 580999561 462572446 958762824 610977776 462822992 854570683 423198061 535085177 475506525 721347707 190375832 590204786 641466749 938578002 382602630 920871985 898868136 710362604 262245094 738096817 266747516 34708949 921906443 865226231 526842846 660093695 790920462 833758449 780816143 577894111 341064602 805751552 345135905 651226458 1045244848 849311376 224099207 209377859 867480579 85027065 90613392 90702355 1044468148 193473971 556525929 331123177 302719170 987563889 115667096 875100140 683126462 644993923 635330812 1024353252 90647781 902181441 571788872 902649762 58400608 1053697316 811696947 67986667 284554615 432307446 742784309 682879563 248136826 727150150 698990421 88298406 798391515 1767738 320722683 891424665 778830661 280726050 518672235 923917004 217700036 931524064 579854014 58874014 881044526 207804858 888922220 957796031 323146027 434271416 240409356 750299630 855228574 606171704 1607867 199121043 489480731 764427832 827806430 959743339 411331610 511275223 533004760 210118964 713771979 979057330 969566036 335342711 417924976 190955144 260972874 338972107 132805533 976063996 541019069 458950762 958181502 806129325 799079814 779738068 982232703 934141225 43372767 277414647 355886305 762668109 944179853 137260416 59432686 644182966 469278561 371159031 822845003 368403735 836409247 938665971 259494574 971183487 261443764 114984520 458032174 770384931 205469726 679133197 145870720 671403860 461136672 527990478 178651924 196339623 477714881 1072361489 355828034 666841929 719017975 166739088 754000706 212016379 1047360075 991768957 343604424 121304703 471089353 258424973 1069558230 598431639 642021759 944298933 281945265 867997564 222398698 651481560 998891747 1067461275 489517131 178132774 423296525 649757671 793684577 284813052 591519481 176063701 625099396 517581278 366335947 172178631 691157556 956791732 664870557 971027385 742633225 314832994 302832051 379259414 327975754 960083798 481738635 969369775 198825819 20452018 580418730 207735371 149326305 1029528356 62365667 612329409 330973244 230321804 721238618 99011687 978338334 284476470 527347350 397360772 662602757 1068142175 908553686 940823514 869184113 822418335 920637693 465954919 107932032 496797815 597693967 472807671 1029618568 76315092 331150075 1050822430 909550378 217991480 888917539 407761401 31765951 539186019 944138057 571882688 328055302 814760312 851430174 170512849 203202649 715404744 392481563 125655757 376959120 712454462 802628303 1050604767 641690710 268195244 961090954 528178482 705046207 101065191 788758318 771563420 813981289 723911158 544177463 563910853 837713241 1005170933 102193847 92811118 756369162 517342975 750516996 498390596 978978820 847214110 686421974 317593157 930297169 578675072 735980263 921256160 988786982 138803831 891043270 224797391 1063608357 268329970 277959911 440457001 720909343 739729363 740186415 875271559 438800525 12543674 358981629 202081901 781108127 679118423 19833215 553609095 347557632 795271220 1051757052 1044959839 1033101719 591698455 521613323 639292368 644444230 818469659 409903931 785281434 528981843 17874267 405914004 976230214 747789489 887831556 245313145 59013335 144646306 385760727 372528201 608790508 814253230 98197341 580671992 705118945 393117483 352937981 776389818 640208931 455330143 414568960 963740138 563716410 388215294 197861679 491251227 1032733800 1041283064 819388475 1062303577 216875450 747580591 189166968 189095263 986420859 322499234 461442717 817305524 96004159 923023452 438773664 432215143 67559170 404650236 547389013 181609000 121860051 535099274 666966745 401679012 811485849
0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0
211 269 481 287 42 19 318 83 441 321 388 122 71 279 316 158 223 497 451 352 261 286 212 268 185 199 220 216 196 479
144 494 154 413 163 468 493 207 91 367 120 113 304 204 185 319 276 487 220 92 321 229 403 138 146 223 257 148 86 58