500 30
396525161 730488792 1070296808 1038120642 836361159 525804317 198381177 326381967 271274865 454980465 1004597166 245568040 743253949 58671044 323749003 174979889 859234637 1022712333 92827877 183853577 174565035 532752030 672886470 808732531 417882843 764705738 431992315 624223351 389029448 161658129 667725326 2369700 655959932 1018907343 96429637 323054524 920890049 352165359 970102493 48065588 918181555 498222031 770524413 739599163 376520066 785559371 509816047 513862522 616889836 316661167 954115059 165973466 809373429 316601881 987833216 45091060 946679958 1003428179 186062429 737754119 313569243 534213271 342267067 423798037 267877276 256289095 467622987 665653390 476968009 404298914 138912447 381433656 457739628 807155566 361730985 135805335 319588015 438565813 65633771 216308521 592288601 776630445 1059819000 235088609 899236889 747433877 922658639 71672121 338553627 986964169 898391902 436368253 37281578 75366832 1042029246 611324638 319764815 75177099 703767135 189349531 293946985 66371850 385741990 768788984 528624253 543380293 265399409 413117246 789601255 678639033 978564116 1039170576 586791627 678472134 633393754 486225217 1008118820 151738844 488285686 123484130 353302953 659869383 1002254207 58063166 647692766 899926040 689880562 451808358 256038280 1005290025 504230285 1051908018 171564646 273941739 742722902 430098894 283113276 602187744 990898876 742088847 1041868394 273553251 787294281 496357370 194067611 560818891 15550085 444979523 267813037 918406455 190176532 150047828 1060495846 579141559 781973063 522136941 370580810 147283354 712781429 887341310 944695823 96010128 31640645 13119922 98732598 660427884 170296452 364067375 792045329 407848054 671554262 898563446 928111428 844209926 505267496 653448798 146545518 792224480 51299065 327082100 819718717 488421269 1027140851 518618164 15065334 854636072 19143847 827897137 887354844 1016626391 950089125 306013656 604844472 843130612 953431676 772942698 122642813 354047016 654763131 791948170 144581587 228574268 427164894 938224081 79258164 27467730 314308967 67316887 1070804246 632892700 129694646 924182752 11341263 206990133 578362836 817106587 450724506 164691712 855527857 1046834308 851969472 20063483 978816831 396530257 717699500 23496598 518817213 501212565 713806412 1053853791 150533425 858812016 353972122 769300392 16141935 225881554 150934377 1071138239 1070808526 492654644 977952212 221005187 168195171 358472510 459499567 662368001 516947414 177516497 778945932 262279889 1033327820 765027577 773009000 71124426 536886318 335226465 587192035 507151326 1053221694 311335995 3698219 399622712 320850077 243850469 227708198 331772206 947747175 275572411 1034505151 532584043 591260173 114473296 177160162 67087543 320780717 86034333 703293715 917462345 496482463 263985041 875006418 1019921917 490994947 356563545 65693403 167445196 723384204 108348534 707706628 182673197 719243364 306595317 1020966190 944406759 90117538 65969833 929802311 667897942 205874251 120184481 225349064 604333776 333573944 995775168 884178767 664684216 117141417 924147642 1061242576 200755049 943707470 438928579 246778321 38159952 800776246 317435287 989502423 120193705 311794444 376345239 200047321 385977065 640247422 772735185 1046720318 216738364 520717452 612611842 967661596 490199046 745009691 185133801 957522216 882715169 614145539 191158966 113273355 229106159 373955167 1045098760 732316126 845380079 38692926 116944869 26582901 402138438 440332397 358127532 959220826 878975462 221706691 871550731 590305102 213881136 458020228 622944108 346539770 261896397 625641746 443529406 603335426 581833003 564296762 1029504146 702580059 610898915 355407164 831487699 754848150 697490927 304074963 1032636797 479530495 1001205979 549422563 410658310 503129521 691104396 837542249 880981625 577292925 314853297 731286917 1018226781 708701506 491998771 776398621 65935376 869088201 517064020 887415064 225406976 241790457 856421654 1015199296 280286218 764983705 361708034 369583293 363851067 295432309 763280752 1056017908 85453908 508774932 932948657 840632859 872012927 1039750775 955467402 374811385 733951841 827124691 626834098 250491892 351954468 967650557 455486181 745174118 1028267822 410944840 466498467 255804555 143780078 548688261 37100013 436156954 797172196 240056398 68969095 530429939 336599540 423876559 383123383 992693417 802055735 1069228039 268581479 1013332703 341933327 998187541 553613583 768633053 429004385 530905594 321652968 727108523 438001368 544192185 741258504 623287517 783512421 179508076 29576056 272676356 50572211 693728458 440285461 797795823 746343427 682357552 983359782 363717721 50408761 451247362 382510088 631106824 777434773 347928713 998703065 609646387 835367175 1070552996 888183266 566800338 937330281 602899424 535968985 364178785 275565943 835536677 420879736 787653186 121023347 130672306 983067385 739936915 905790699 158803171 257837964 523546141 747365334 195003605 252835549 197955814 302608367 902518458 23814451 232554216 10204512
0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1
141 370 344 31 264 172 450 246 496 466 391 368 304 39 322 406 119 184 313 233 18 122 467 369 52 43 204 477 486 262
304 284 160 190 467 255 373 55 242 59 341 91 233 191 459 130 197 133 333 235 208 306 430 54 307 77 314 66 461 273