0 1
1 0
2 0
3 0
4 0
5 1
6 0
7 2
8 0
9 4
10 1
11 6
12 2
13 9
14 5
15 13
16 9
17 18
18 17
19 25
20 28
21 35
22 46
23 49
24 70
25 70
26 107
27 101
28 156
29 145
30 227
31 210
32 321
33 303
34 453
35 436
36 628
37 622
38 868
39 884
40 1187
41 1243
42 1619
43 1738
44 2192
45 2410
46 2960
47 3317
48 3977
49 4532
50 5331
51 6154
52 7117
53 8298
54 9477
55 11129
56 12576
57 14840
58 16643
59 19689
60 21957
61 25996
62 28883
63 34177
64 37879
65 44740
66 49532
67 58348
68 64577
69 75818
70 83945
71 98186
72 108806
73 126747
74 140621
75 163131
76 181229
77 209351
78 232909
79 267946
80 298517
81 342053
82 381578
83 435573
84 486495
85 553346
86 618670
87 701357
88 784832
89 886987
90 993219
91 1119354
92 1254023
93 1409666
94 1579707
95 1771688
96 1985634
97 2222318
98 2490520
99 2782238
100 3117363
101 3476727
102 3894119
103 4336657
104 4854988
105 5399659
106 6041480
107 6711495
108 7504196
109 8327837
110 9304393
111 10316198
112 11516523
113 12758423
114 14230540
115 15753556
116 17555394
117 19421336
118 21622479
119 23906243
120 26590494
121 29382556
122 32650373
123 36060047
124 40032154
125 44191069
126 49012045
127 54078718
128 59921904
129 66086762
130 73159458
131 80651069
132 89201412
133 98293634
134 108617876
135 119638590
136 132090689
137 145431674
138 160433695
139 176562799
140 194618027
141 214093056
142 235800686
143 259286058
144 285359438
145 313645570
146 344932563
147 378958934
148 416467154
149 457348973
150 502274264
151 551334283
152 605095195
153 663900642
154 728178014
155 798584030
156 875368437
157 959568942
158 1051215055
159 1151802414
160 1261094068
161 1381128529
162 1511353571
163 1654444889
164 1809483737
165 1979886263
166 2164314506
167 2367038087
168 2586247287
169 2827186974
170 3087524285
171 3373611330
172 3682543729
173 4021921454
174 4388225829
175 4790454574
176 5224439822
177 5700735501
178 6214500394
179 6778011374
180 7385744974
181 8051874672
182 8770204338
183 9556985234
184 10405381886
185 11333909948
186 12335157370
187 13430095816
188 14610835152
189 15900999083
190 17292359921
191 18811392427
192 20449723660
193 22236880421
194 24164595768
195 26265651564
196 28532208191
197 31000506375
198 33663536157
199 36561201042
200 39687816856
201 43087155673
202 46755461206
203 50740580740
204 55041411759
205 59710086683
206 64749020224
207 70214845554
208 76114515782
209 82509389998
210 89412157737
211 96889142093
212 104960166829
213 113696780282
214 123127559361
215 133329567318
216 144342004485
217 156247781305
218 169098867425
219 182984408424
220 197971598768
221 214156282691
222 231623676997
223 250476882215
224 270822315768
225 292771019183
226 316454206292
227 341991697775
228 369543567220
229 399239450089
230 431272853033
231 465784502659
232 503006479257
233 543092176608
234 586318012450
235 632851981799
236 683021293697
237 737010921621
238 795206075583
239 857811606476
240 925278776830
241 997835846322
242 1076009102334
243 1160054490006
244 1250583316749
245 1347884378499
246 1452665125303
247 1565253405473
248 1686465185314
249 1816674797090
250 1956820476009
251 2107331892014
252 2269284842080
253 2443174856548
254 2630232287120
255 2831030974950
256 3046974718408
257 3278730361062
258 3527896152116
259 3795249200953
260 4082605573183
261 4390872887597
262 4722111023417
263 5077381753910
264 5459017728732
265 5868262434990
266 6307753555661
267 6778948313148
268 7284825409101
269 7827092927748
270 8409110758124
271 9032880768027
272 9702188919058
273 10419380399350
274 11188717438400
275 12012945564121
276 12896859481130
277 13843670580606
278 14858769029861
279 15945907216620
280 17111141440128
281 18358851099590
282 19695837990924
283 21127206803493
284 22660594051411
285 24301941858416
286 26059821844489
287 27941141303597
288 29955520033275
289 32110975813976
290 34418304067873
291 36886798134733
292 39528572834830
293 42354384366989
294 45377829254864
295 48611338793350
296 52070174553726
297 55768683195050
298 59723998554081
299 63952654329848
300 68473890959140
301 73306736105037
302 78472801893081
303 83993956358361
304 89894483305060
305 96199481803571
306 102936246914391
307 110133548935521
308 117822078643583
309 126034773249606
310 134806154566221
311 144173884466438
312 154176808756240
313 164857941198202
314 176261009795257
315 188435085131309
316 201429409461278
317 215299902053922
318 230102035021598
319 245899465364240
320 262754705110806
321 280740146753732
322 299926259027292
323 320395289176710
324 342226699986838
325 365513848578217
326 390346365192221
327 416830123804255
328 445066249011632
329 475174708383639
330 507269620851764
331 541486814030884
332 577955096179170
333 616828133497345
334 658251338194240
335 702398430585213
336 749433588685400
337 799553067344047
338 852942250353777
339 909822703543114
340 970403769150708
341 1034935431258966
342 1103654094652243
343 1176841638621301
344 1254765029283880
345 1337741931251917
346 1426073813856788
347 1520118478778481
348 1620216337622255
349 1726770196735839
350 1840164406634178
351 1960852222330304
352 2089267554885062
353 2225920195975122
354 2371299939164556
355 2525979920281003
356 2690512921605845
357 2865543034438226
358 3051694013939848
359 3249689416117874
360 3460232935562954
361 3684137105209270
362 3922195624409656
363 4175320635513129
364 4444407136413186
365 4730478762443194
366 5034544476794841
367 5357752688424161
368 5701240526357291
369 6066296013747354
370 6454200358900881
371 6866397781266998
372 7304331394102114
373 7769620139257951
374 8263888994623176
375 8788952320376832
376 9346639299389100
377 9938982827452822
378 10568041287902668
379 11236091931196760
380 11945450296714867
381 12698666822753907
382 13498345459595870
383 14347342028569041
384 15248583821860844
385 16205267988387036
386 17220684188195130
387 18298411023093220
388 19442144107052288
389 20655888280728027
390 21943793775054208
391 23310341650339836
392 24760191068188923
393 26298355078395865
394 27930062374804311
395 29660920216446142
396 31496794426035147
397 33443955876237093
398 35508982895303775
399 37698887375596027
400 40021044178523763
401 42483292531516925
402 45093897474264282
403 47861621802742061
404 50795725069343682
405 53906000910550361
406 57202819604238039
407 60697125182201277
408 64400528057288788
409 68325255875606877
410 72484303252987658
411 76891329866730990
412 81560874882451312
413 86508195324864116
414 91749553331159285
415 97301987377185579
416 103183681058531040
417 109413659287394589
418 116012247874963478
419 123000686358851669
420 130401688236304602
421 138238961637601383
422 146537880635733203
423 155324904553075464
424 164628371343767027
425 174477805915826579
426 184904847144069832
427 195942435213562342
428 207625884366675108
429 219991938935208361
430 233080004449783700
431 246931061734462943
432 261589069502872692
433 277099725650211235
434 293512054921916179
435 310877006363458365
436 329249240064424056
437 348685549627718943
438 369246862358145003
439 390996475600110383
440 414002285044165424
441 438334823870273540
442 464069734079568405
443 491285597581075908
444 520066665607880570
445 550500471213986886
446 582680831894229462
447 616705233430265321
448 652678120787996100
449 690708043884702001
450 730911251676694044
451 773408591229657043
452 818329419617427061
453 865808248685427601
454 915988988946733182
455 969021333652518539
456 1025065348278788509
457 1084287588979546252
458 1146866050493775357
459 1212986015778647778
460 1282845374213858884
461 1356650201217429042
462 1434620457471300021
463 1516985299633772616
464 1603989169937964464
465 1695886841760278808
466 1792949907337985721
467 1895461564957056586
468 2003723510679716772
469 2118050477305455010
470 2238777533880240781
471 2366254390390001091
472 2500853106421588091
473 2642962179798397853
474 2792994663068172123
475 2951382059014000577
476 3118582840637813539
477 3295076181710325983
478 3481370872590231546
479 3677998919743501222
480 3885524846072782718
481 4104539199672649556
482 4335668223332691230
483 4579567319733950868
484 4836931070419085782
485 5108486712210109216
486 5395004481206935582
487 5697291163449112102
488 6016200734400461379
489 6352628055824443958
490 6707519775737110279
491 7081868253148753621
492 7476722677618426995
493 7893183313967593307
494 8332412794353333306
495 8795630786316743555
496 9284125403711553711
497 9799248413544295579
498 10342426705167981356
499 10915158164332546118
500 11519023132791692848
501 12155681091845529117
502 12826882036937911710
503 13534464127766733934
504 14280364894596035621
505 15066620027762293182
506 15895374324328704883
507 16768881806556939726
508 17689516309228264851
509 18659773134405679981
510 19682279171295983747
511 20759796313418934928
512 21895230994341338232
513 23091639613223668382
514 24352237361195500988
515 25680405922183582410
516 27079701456197604285
517 28553864864374151213
518 30106828787099743922
519 31742730745349141294
520 33465919003489734014
521 35280968923262010553
522 37192687533414035885
523 39206133458073272863
524 41326620028182408985
525 43559739172555182777
526 45911362899580849102
527 48387671566942930323
528 50995153556398466723
529 53740638366966525371
530 56631294300962789660
531 59674666855433615888
532 62878674234240606892
533 66251651543618427417
534 69802343943198397601
535 73539957183792341700
536 77474148210069008054
537 81615082612003704608
538 85973422493760719951
539 90560391444682416943
540 95387759493093096509
541 100467916238212629381
542 105813852714422715571
543 111439243362064245051
544 117358424637557863902
545 123586486538659067302
546 130139247809111673592
547 137033357772567669843
548 144286267997604949010
549 151916345234154408725
550 159942839426207863011
551 168386008585212581660
552 177267083064145742679
553 186608403243917633401
554 196433380014252506680
555 206766646191680044769
556 217634013190432468338
557 229062637134090357829
558 241080971744138425775
559 253718950151766456197
560 267007934083512173347
561 280980912425116721858
562 295672446843573073131
563 311118888201320790284
564 327358318822820639260
565 344430787904779814519
566 362378250713953199406
567 381244824187582935748
568 401076723438405478364
569 421922538789142704212
570 443833170061674092077
571 466862126340334591903
572 491065458635950682388
573 516502083725022638293
574 543233715906957740063
575 571325216320111818962
576 600844524653302378431
577 631863035395361653418
578 664455530521172455596
579 698700584189111880719
580 734680497598802275460
581 772481733710907062202
582 812194855670013079349
583 853914993184051906370
584 897741786122796687450
585 943779884260171841433
586 992138897898429444675
587 1042933932746300796619
588 1096285549682807343826
589 1152320336618202163113
590 1211170879801463324851
591 1272976374589997573575
592 1337882611023177490748
593 1406042625511647836366
594 1477616703747960089951
595 1552773075417984065070
596 1631687937901048954402
597 1714546196205511164788
598 1801541511327255122495
599 1892877087720148565285
600 1988765750635888783961
601 2089430783559293266257
602 2195106039347040564208
603 2306036830189122383532
604 2422480077901947050868
605 2544705259122625026267
606 2672994600696295348469
607 2807644082971284514754
608 2948963686854692641469
609 3097278458256168122995
610 3252928814073261231037
611 3416271671032189695190
612 3587680818609000909314
613 3767548115740154555223
614 3956283939491109293521
615 4154318453361085321316
616 4362102141381560821706
617 4580107152021803017524
618 4808827928340459057712
619 5048782631815392004314
620 5300513880186914165529
621 5564590255891614746848
622 5841607164330946092875
623 6132188431989054946687
624 6436987299040919382374
625 6756688112684177708228
626 7092007469272680634502
627 7443696008898063257340
628 7812539723603706019050
629 8199361859820014299580
630 8605024410687087795200
631 9030430133585774578232
632 9476524246182023834473
633 9944296567011929641619
634 10434783436564456123603
635 10949069989681864685754
636 11488292324828535405877
637 12053639917968218140059
638 12646358065133848410249
639 13267750448450836286562
640 13919181879235595461124
641 14602081027961424815793
642 15317943497382135286319
643 16068334729496991136457
644 16854893440631312134085
645 17679334719863645138377
646 18543453860609307189173
647 19449129666542005032677
648 20398328717031722487908
649 21393108898341340181333
650 22435624143280717689354
651 23528128207405052814322
652 24672979926477252671649
653 25872647259558976052635
654 27129713111339362750965
655 28446879666413937605454
656 29826974827256710890853
657 31272956866650345426220
658 32787921536069115970176
659 34375107066182025612225
660 36037902004696300944051
661 37779850598131790272031
662 39604661422770303221085
663 41516213184525469990545
664 43518564211575912090886
665 45615958713163184303224
666 47812837207782021427992
667 50113843286166319032832
668 52523835054595257413921
669 55047892452212862240973
670 57691329795114634413004
671 60459703703532749769302
672 63358826838926577540004
673 66394776502499221673491
674 69573909664562296087708
675 72902872302380417132469
676 76388615828654253613391
677 80038407243871922470650
678 83859847078896339218045
679 87860880444894933708867
680 92049816613773049786277
681 96435341057419457637120
682 101026536799146175565050
683 105832897543495561009487
684 110864350941982090433520
685 116131272925131506259422
686 121644513036729940575343
687 127415410091186928993561
688 133455819742245158943975
689 139778131601263700860201
690 146395299218996446051945
691 153320858814073216428740
692 160568961860091589885644
693 168154395588532645731361
694 176092618388110765832742
695 184399782262706708542694
696 193092771265771895193380
697 202189226111711897173429
698 211707585885242040555413
699 221667115024136292629480
700 232087948561884742939459
701 242991121720973203241872
702 254398618967114400948088
703 266333406475390118307074
704 278819485295841041152099
705 291881926980045294909990
706 305546931181091856557109
707 319841864755658713295443
708 334795324146508699428250
709 350437178305052360253219
710 366798636231652795458263
711 383912294096212414710399
712 401812208340928806004993
713 420533947411846066510599
714 440114670860455924912019
715 460593186137635188410187
716 482010034164841001932777
717 504407551683666152211775
718 527829963804557835827780
719 552323452450631490814194
720 577936256432091884822528
721 604718746572243983883004
722 632723533899377475247811
723 662005552096412784249611
724 692622174449212296659673
725 724633304319337885755173
726 758101501538885754258768
727 793092081668771792462597
728 829673252585590768531284
729 867916223356078658079626
730 907895351821538409979084
731 949688263993075471899353
732 993376013504210951369390
733 1039043212511601805046111
734 1086778203957011124406299
735 1136673205044997065680454
736 1188824493331899650826754
737 1243332563945939316427473
738 1300302330603820363914463
739 1359843297840388669757420
740 1422069778143397525033694
741 1487101080569946177671721
742 1555061745287504653716859
743 1626081750073449294043071
744 1700296763656250699755935
745 1777848371723249068393811
746 1858884350570679530409603
747 1943558914384153851139020
748 2032033010830695523181167
749 2124474591527039252541551
750 2221058931341903552838605
751 2321968924130073281406245
752 2427395427659648819844894
753 2537537586865896529409407
754 2652603206477154067712723
755 2772809104232649890326440
756 2898381513453168231865836
757 3029556468872562454890778
758 3166580241586331907464530
759 3309709760368582228161505
760 3459213081634575370340513
761 3615369849354712827004901
762 3778471802887226827223529
763 3948823278859770050083526
764 4126741759967167515200048
765 4312558422470887022845067
766 4506618729315732885564876
767 4709283027199459783497897
768 4920927187643154829651629
769 5141943257909283985756776
770 5372740153965109030298356
771 5613744369879396045768488
772 5865400726948528722505526
773 6128173146581984359932195
774 6402545460218974902052463
775 6689022251122786565236741
776 6988129730104118471312011
777 7300416652086836467758041
778 7626455263075185729580019
779 7966842297830959546589519
780 8322200003978137868826371
781 8693177227646647052612221
782 9080450521102638183339620
783 9484725323769856333469414
784 9906737160309871558748549
785 10347252925031757630566742
786 10807072177927527242063012
787 11287028541127759376786416
788 11787991101026941998034439
789 12310865926140570034386277
790 12856597584137028768530895
791 13426170791204484073159393
792 14020612053544628020039132
793 14640991459169682653667224
794 15288424454213394243988090
795 15964073788954289212871730
796 16669151440165728229570358
797 17404920724106165573870079
798 18172698377068234790218458
799 18973856849095536848687691
800 19809826555906424071532222
801 20682098368195562876620659
802 21592226049207565677356795
803 22541828955666476688121799
804 23532594676464416519620701
805 24566281962539946723893252
806 25644723583434709575063773
807 26769829504819585415684407
808 27943589981065769154791628
809 29168079000603555300286672
810 30445457634161842184919655
811 31777977769746682778071922
812 33167985737833953868783742
813 34617926359482572528977409
814 36130346871528823393212780
815 37707901313212143578540820
816 39353354776326941039066277
817 41069588157747638868148983
818 42859602761556133302305517
819 44726525447018726296690065
820 46673613611936935422421045
821 48704260767964279465294997
822 50822001936838183275373767
823 53030519687442514757383144
824 55333649979183062938976359
825 57735388697916481664970966
826 60239897983546590724297732
827 62851513304867291171599659
828 65574750311498257531511913
829 68414312490844970522710545
830 71375098587778008974681420
831 74462210890315397230131302
832 77680963263998806093324807
833 81036890116571112268539547
834 84535755097835980071186940
835 88183560797557541232429882
836 91986558165729228572594225
837 95951257002185067431385567
838 100084436156673136019117628
839 104393154873263095525798878
840 108884763834444945888233314
841 113566917428370943185544408
842 118447585706409044917796941
843 123535067646597096938940704
844 128838004099702261435602047
845 134365392128021272459712619
846 140126599021064213886571160
847 146131377795039021733501812
848 152389882365824656777374475
849 158912684301165636924684112
850 165710789245662966661255308
851 172795655024912749017478917
852 180179209424863032369621040
853 187873869754899789494956405
854 195892562092136973919104179
855 204248742418826766666617525
856 212956417451014688725288069
857 222030167474675734277437582
858 231485168887725930636295856
859 241337218869012107568349959
860 251602759772979135051442327
861 262298905776122778243096123
862 273443469274725294805341905
863 285054989664676387618505376
864 297152761904670538746358820
865 309756867597473240356052481
866 322888205893887645522851595
867 336568527056659559313592151
868 350820465894439938013746026
869 365667578003655227061249126
870 381134375936692526785097598
871 397246368332289970114438991
872 414030099038335322365539446
873 431513189357738341509561672
874 449724380363649686705708863
875 468693578505454125498305303
876 488451901372980009108620063
877 509031726926296177160068697
878 530466742985695147939460599
879 552792000369492391738367566
880 576043966408338650166987757
881 600260582297320599575395328
882 625481320956607427192206209
883 651747248927957997503903038
884 679101088928960853006725310
885 707587286649695190691134281
886 737252078375018157204919173
887 768143563064745428648398619
888 800311775447721523640537759
889 833808763798631304523988753
890 868688668939115427628196745
891 905007808156358734431995624
892 942824760580452989280017780
893 982200457724406170081929979
894 1023198275743489967918628875
895 1065884133113462761119436661
896 1110326590316965111714104955
897 1156596955216750102370073273
898 1204769390756515881870152069
899 1254921028629006526938424665
900 1307132085624221722164520997
901 1361485986238622034138308818
902 1418069488352673897292325337
903 1476972815477315192521044750
904 1538289792495538584624029901
905 1602117988296015275572631479
906 1668558862370170348459402315
907 1737717918640713236375798488
908 1809704863766714631509647228
909 1884633773037061790736918038
910 1962623261301729448488975255
911 2043796661867199852866960339
912 2128282211042775395833095432
913 2216213241047135279412396086
914 2307728379234536134420341798
915 2402971756099304060767587174
916 2502093220328509559204234382
917 2605248563074728482467349302
918 2712599750069686686209712188
919 2824315163425509859225784313
920 2940569852138370392082952966
921 3061545792775160627414992544
922 3187432159797832271500929557
923 3318425606596482016037051397
924 3454730557174381295426917806
925 3596559509100406931656465402
926 3744133348212283906710969813
927 3897681675181716619827343491
928 4057443145019718976230417314
929 4223665819077337401252434730
930 4396607531272774981615947571
931 4576536267489925511580214996
932 4763730560593013591243258773
933 4958479899335009597452292438
934 5161085154382458839585768997
935 5371859019007003923169669681
936 5591126468511771659979419652
937 5819225235152532728621811882
938 6056506303538322465541130115
939 6303334422415120503318147609
940 6560088638808231588424719294
941 6827162849501738488346684001
942 7104966376899560246024221436
943 7393924563249359351970505987
944 7694479391424198796361848383
945 8007090125171184427199053757
946 8332233978257408278410612829
947 8670406804272575615014430527
948 9022123817842683430278165096
949 9387920337783502503753664586
950 9768352564364519472990993187
951 10163998379897794295813357792
952 10575458186334510822472280334
953 11003355767682886455850805612
954 11448339192541751606758087929
955 11911081743073435447742388733
956 12392282887424761354656070203
957 12892669280337869761305068667
958 13412995810780625321896331003
959 13954046679661987459249610144
960 14516636528392952962273624957
961 15101611599585301299900318392
962 15709850952692856996787820605
963 16342267714015315946272629249
964 16999810386029964060500657943
965 17683464193498079891036085070
966 18394252493591604582107994829
967 19133238225410724557231834292
968 19901525428540834672877173593
969 20700260803838915791661732480
970 21530635348626129221934191564
971 22393886037190287032865926014
972 23291297581431414132641077340
973 24224204240160932897261293887
974 25193991714674587776174463673
975 26202099096609112407206005958
976 27250020908622308668137780608
977 28339309201298344767664275704
978 29471575749872030090878006834
979 30648494311458162447168256319
980 31871802989569908192386424713
981 33143306663789693696397354891
982 34464879534704123685695523348
983 35838467739037994571914847369
984 37266092088564688832522987928
985 38749850884695475153017594940
986 40291922865929439003626595651
987 41894570236932147371855008853
988 43560141840167883441888511470
989 45291076415620157248561477370
990 47089906013406628827070348412
991 48959259501494374332440238380
992 50901866237340110944467952910
993 52920559842241509479724606975
994 55018282151378286753543036055
995 57198087274823541515478768742
996 59463145846791502933970307714
997 61816749394816660008362928326
998 64262314910548462119542790572
999 66803389550198200011942095828
1000 69443655550867259267130266895