1 0
2 1
3 0
4 2
5 1
6 3
7 3
8 6
9 5
10 11
11 11
12 17
13 20
14 30
15 33
16 49
17 56
18 77
19 92
20 122
21 143
22 190
23 225
24 287
25 344
26 435
27 516
28 648
29 770
30 951
31 1134
32 1388
33 1646
34 2007
35 2376
36 2868
37 3395
38 4078
39 4807
40 5749
41 6764
42 8042
43 9449
44 11187
45 13101
46 15463
47 18070
48 21236
49 24772
50 29021
51 33764
52 39445
53 45798
54 53337
55 61812
56 71797
57 83019
58 96209
59 111034
60 128346
61 147863
62 170546
63 196097
64 225721
65 259085
66 297605
67 341033
68 390996
69 447282
70 511909
71 584673
72 667953
73 761748
74 868819
75 989298
76 1126587
77 1280961
78 1456461
79 1653749
80 1877565
81 2128951
82 2413708
83 2733283
84 3094591
85 3499880
86 3957331
87 4470004
88 5047878
89 5694986
90 6423264
91 7238275
92 8154214
93 9178357
94 10327958
95 11612305
96 13052093
97 14659528
98 16459322
99 18466998
100 20712516
101 23215409
102 26011642
103 29126132
104 32601918
105 36470225
106 40783112
107 45579345
108 50921445
109 56858010
110 63463938
111 70799388
112 78954723
113 88004026
114 98055755
115 109201558
116 121571373
117 135277694
118 150476926
119 167306525
120 185954023
121 206587931
122 229432736
123 254693771
124 282640589
125 313522638
126 347662638
127 385364045
128 427012696
129 472976249
130 523716866
131 579678825
132 641414425
133 709460960
134 784477649
135 867112125
136 958152087
137 1058376639
138 1168725231
139 1290135201
140 1423725748
141 1570621861
142 1732157561
143 1909680662
144 2104778775
145 2319066450
146 2554431195
147 2812803109
148 3096426547
149 3407605543
150 3749005205
151 4123374786
152 4533876042
153 4983784111
154 5476849469
155 6016968639
156 6608585290
157 7256332875
158 7965471703
159 8741503662
160 9590653878
161 10519448138
162 11535245698
163 12645782001
164 13859749761
165 15186307198
166 16635717808
167 18218812998
168 19947699461
169 21835179368
170 23895522201
171 26143842992
172 28596952057
173 31272678475
174 34190808635
175 37372358905
176 40840600900
177 44620284109
178 48738764436
179 53225162119
180 58111608183
181 63432342843
182 69225078200
183 75530038774
184 82391462048
185 89856564628
186 97977199144
187 106808752889
188 116411961963
189 126851745316
190 138199203164
191 150530368441
192 163928414354
193 178482332886
194 194289354807
195 211453560389
196 230088547680
197 250315956332
198 272268416431
199 296087999086
200 321929454805
201 349958599804
202 380355889647
203 413314722507
204 449045392095
205 487773327583
206 529743441859
207 575218322905
208 624483038806
209 677843263900
210 735630598885
211 798200660894
212 865938947244
213 939258913815
214 1018608463153
215 1104467999870
216 1197357623716
217 1297835205009
218 1406504328214
219 1524012426442
220 1651059585240
221 1788396735631
222 1936835427232
223 2097246144180
224 2270569120718
225 2457812841621
226 2660066047950
227 2878496440020
228 3114364025766
229 3369020122222
230 3643922157645
231 3940633067671
232 4260837754684
233 4606342927997
234 4979095430878
235 5381182668006
236 5814852970537
237 6282516758566
238 6786769223611
239 7330392325232
240 7916380086897
241 8547941640293
242 9228529387685
243 9961843319450
244 10751862432637
245 11602850498434
246 12519391151165
247 13506395422543
248 14569140879131
249 15713281263914
250 16944890224365
251 18270473357000
252 19697017112071
253 21232003710466
254 22883465779542
255 24660004652678
256 26570851499255
257 28625889481147
258 30835722203727
259 33211700421375
260 35765998623875
261 38511647050451
262 41462617482800
263 44633861308962
264 48041405697350
265 51702398726896
266 55635217125928
267 59859519591319
268 64396367607268
269 69268288088254
270 74499408941334
271 80115532520374
272 86144287651392
273 92615215548964
274 99559940443623
275 107012269671779
276 115008385270922
277 123586960410365
278 132789374435737
279 142659848054649
280 153245684861345
281 164597427827804
282 176769130664415
283 189818538763686
284 203807393972938
285 218801643503687
286 234871782404976
287 252093094202251
288 270546035840266
289 290316514603401
290 311496320655853
291 334183445333611
292 358482567358270
293 384505418011740
294 412371327785563
295 442207644999040
296 474150350225224
297 508344535695864
298 544945096100663
299 584117276793138
300 626037450551972
301 670893744011242
302 718886910852387
303 770231047013299
304 825154572473351
305 883901046827021
306 946730273232026
307 1013919227837032
308 1085763300794120
309 1162577354653704
310 1244697119618081
311 1332480397567239
312 1426308630741763
313 1526588270649312
314 1633752541318552
315 1748262994652948
316 1870611492496475
317 2001321972290619
318 2140952675029509
319 2290098148604456
320 2449391751583287
321 2619507924918190
322 2801165005692413
323 2995127801204965
324 3202210750844159
325 3423280841389897
326 3659261159280961
327 3911134190630817
328 4179945811919513
329 4466809023034261
330 4772908430050276
331 5099504466229871
332 5447938426445076
333 5819637237628255
334 6216119112268812
335 6638998936696264
336 7089994618998418
337 7570933172615236
338 8083757842375279
339 8630534970089496
340 9213461993225503
341 9834875188976496
342 10497258651141757
343 11203253021657266
344 11955665563062468
345 12757479999368735
346 13611867816334388
347 14522199347368948
348 15492056449263822
349 16525244986042943
350 17625809044378588
351 18798044986286775
352 20046517388861703
353 21376074856138656
354 22791867889216282
355 24299366671288871
356 25904381097455178
357 27613080771950482
358 29432017454945903
359 31368147538190997
360 33428857195870122
361 35621987637430319
362 37955863281926295
363 40439320121545090
364 43081737277348171
365 45893068844886821
366 48883879230427334
367 52065378894802301
368 55449463914202593
369 59048756086498669
370 62876647213455253
371 66947344086376888
372 71275918043500096
373 75878355413261942
374 80771612962931871
375 85973674444216003
376 91503612621573019
377 97381652637723297
378 103629241388484294
379 110269118510029529
380 117325393953172114
381 124823627485732687
382 132790915418307528
383 141255979615692274
384 150249264434015210
385 159803036350607861
386 169951492290962585
387 180730871112263933
388 192179574634246834
389 204338292350103306
390 217250136623301045
391 230960782157515527
392 245518616984460584
393 260974898397124033
394 277383921538922323
395 294803193694742724
396 313293622494479706
397 332919710672142236
398 353749766120266934
399 375856119463711048
400 399315358454251031
401 424208570966333781
402 450621606498313249
403 478645347491747894
404 508376001011441157
405 539915401612849886
406 573371336617514479
407 608857884109497937
408 646495775601018068
409 686412773139706280
410 728744073576555338
411 773632729206274464
412 821230098318292652
413 871696314278646116
414 925200787559899681
415 981922728718159911
416 1042051707666354994
417 1105788236599582824
418 1173344392912752898
419 1244944468789376756
420 1320825664864982694
421 1401238813934681367
422 1486449153236830355
423 1576737130549448270
424 1672399263832090294
425 1773749038880573460
426 1881117866015562764
427 1994856079468585018
428 2115334001855072913
429 2242943056569705412
430 2378096951951026889
431 2521232919183944291
432 2672813029350926563
433 2833325570697803952
434 3003286513187917470
435 3183241040483574407
436 3373765178200840579
437 3575467497610305572
438 3788990925532072859
439 4015014638595169189
440 4254256074634467662
441 4507473038370417274
442 4775465936304596255
443 5059080116912930960
444 5359208353388661988
445 5676793443919153150
446 6012830969219875327
447 6368372181193808806
448 6744527065078237497
449 7142467547796076780
450 7563430897707987931
451 8008723287301985976
452 8479723567040500654
453 8977887220710888577
454 9504750553731132474
455 10061935083538040528
456 10651152186982861665
457 11274207972622810420
458 11933008436543115055
459 12629564868362059914
460 13365999570022810574
461 14144551852773135994
462 14967584379204988195
463 15837589814499162252
464 16757197858311351880
465 17729182620211864205
466 18756470415004289245
467 19842147939607660290
468 20989470913088128493
469 22201873140316608975
470 23482976086471188211
471 24836598921705897127
472 26266769129244808982
473 27777733635104716866
474 29373970559209415144
475 31060201545036650259
476 32841404774533523533
477 34722828624476321836
478 36710006078496211770
479 38808769850064576900
480 41025268338726085025
481 43365982374100246353
482 45837742878598335643
483 48447749402763387217
484 51203589673486510723
485 54113260108543754838
486 57185187447743339114
487 60428251453849121859
488 63851808844356846861
489 67465718407258761081
490 71280367473479866868
491 75306699699335356647
492 79556244344219943201
493 84041146997384264735
494 88774201952489280165
495 93768886184670245264
496 99039395143322450035
497 104600680316592864216
498 110468488796475760615
499 116659404802188904846
500 123190893407627270315
501 130081346432802636519
502 137350130763289902067
503 145017639060378882252
504 153105343145653633638
505 161635850026131902269
506 170632960864935700220
507 180121732867829111579
508 190128544413533484447
509 200681163403167712476
510 211808819181541934394
511 223542278011585265867
512 235913922481432898196
513 248957834832467809757
514 262709884616799891451
515 277207820680639720104
516 292491367913402891752
517 308602328768461529542
518 325584690029266585950
519 343484734837719634024
520 362351160495172155312
521 382235202065498134796
522 403190762330333224546
523 425274548140297684718
524 448546213755263200340
525 473068511233919277240
526 498907448512214908344
527 526132455249589700164
528 554816557133004008437
529 585036558738823883416
530 616873235697181473194
531 650411536282829633897
532 685740793236280783683
533 722954945966253309103
534 762152774001409034532
535 803438141872798937205
536 846920256364566892155
537 892713936348546981400
538 940939896215732526810
539 991725043158606491593
540 1045202789399190926410
541 1101513379659752559692
542 1160804235059819159193
543 1223230313784546412266
544 1288954489804433250113
545 1358147950045114679652
546 1430990611391866757165
547 1507671557987430803799
548 1588389500321341655692
549 1673353256636158959050
550 1762782258272058944826
551 1856907079549483172892
552 1955969993945246498515
553 2060225557244393390802
554 2169941219568642450700
555 2285397967055533878214
556 2406890995247091498521
557 2534730415063974624527
558 2669241993595647154111
559 2810767930695469540583
560 2959667673797782538727
561 3116318772071100822282
562 3281117772527193583049
563 3454481159338744193501
564 3636846339205784837307
565 3828672674176886579752
566 4030442565004851253327
567 4242662586612457060451
568 4465864679008413651077
569 4700607395416374841275
570 4947477211240405941195
571 5207089895836542087411
572 5480091951021768955912
573 5767162118518370868638
574 6069012960599830211263
575 6386392516387968733200
576 6720086038431809349697
577 7070917812295334565322
578 7439753064180788875617
579 7827499959620550822549
580 8235111698695130729257
581 8663588711147067377131
582 9113980957317160080334
583 9587390338643453759350
584 10084973224159435543166
585 10607943097139793317855
586 11157573328885049527375
587 11735200084241980378857
588 12342225366454962024454
589 12980120206438237652451
590 13650428004721172246117
591 14354768031698480685707
592 15094839095152270531900
593 15872423381273165796137
594 16689390478925284700881
595 17547701594035966777874
596 18449413964701464976624
597 19396685484607136829334
598 20391779546274421205478
599 21437070112520516095606
600 22535047028645548131135
601 23688321584596831284815
602 24899632340715882753104
603 26171851227265084341389
604 27507989932526778208120
605 28911206590710064769987
606 30384812785750182074122
607 31932280883373693596075
608 33557251708920405324198
609 35263542584542203573259
610 37055155744799848461694
611 38936287145643621251788
612 40911335687464235713291
613 42984912868695338843539
614 45161852892466254582004
615 47447223244423593117412
616 49846335766192500449885
617 52364758244387982904592
618 55008326541793424054595
619 57783157292577234372098
620 60695661190500295535173
621 63752556894129985299416
622 66960885580554902439500
623 70328026173961653598337
624 73861711283333577312094
625 77570043878197361411071
626 81461514739686791366848
627 85545020718653334151522
628 89829883841367217919998
629 94325871297602817974217
630 99043216355215048896811
631 103992640239348601027005
632 109185375024263234864859
633 114633187579574809307047
634 120348404623112769404693
635 126343938926188803524479
636 132633316728066076081087
637 139230706409786301509447
638 146150948489135878799690
639 153409586991671688658611
640 161022902265018006662841
641 169007945296554564172884
642 177382573607614487328875
643 186165488789986656440664
644 195376275764266593804541
645 205035443832042701186398
646 215164469608450644053090
647 225785841913838220233360
648 236923108718674926500066
649 248600926227817381419919
650 260845110206531644237058
651 273682689642420458008628
652 287141962854646573809882
653 301252556153363565102686
654 316045485170521887638344
655 331553218974515716803634
656 347809747100468926957025
657 364850649619040751983919
658 382713170387108159198820
659 401436293614556439628492
660 421060823903102528788811
661 441629469903751795888540
662 463186931762475585454059
663 485779992514187551219717
664 509457613609458783173620
665 534271034748731413570788
666 560273878224616505125121
667 587522257963027285530847
668 616074893481283044536465
669 645993228971350719047043
670 677341557745433622134957
671 710187152271038215030854
672 744600400053458781017091
673 780654945613457479843765
674 818427838840607696876388
675 857999689992554222928407
676 899454831645138224260934
677 942881487888103871736474
678 988371951097934518784078
679 1036022766609158148933830
680 1085934925644570338018617
681 1138214066854684219235809
682 1192970686858253322382127
683 1250320360165695142636382
684 1310383968911370197010712
685 1373287942810831275430575
686 1439164509806048116801750
687 1508151957852016617279549
688 1580394908348000725133615
689 1656044601707375576628551
690 1735259195613027948428854
691 1818204076496387524912809
692 1905052184834511550266215
693 1995984354851251513623580
694 2091189669268468968816346
695 2190865829745462921458719
696 2295219543708545326156981
697 2404466928265596911750811
698 2518833931968308099352736
699 2638556775178531070771326
700 2763882409867421257780409
701 2895068999670730681349305
702 3032386421100551346426602
703 3176116786809605001788814
704 3326554991886119553454725
705 3484009284154413600982659
706 3648801859543610470183947
707 3821269483585452360033158
708 4001764140195216691390015
709 4190653708889957145767298
710 4388322671697456622978170
711 4595172851011396965937105
712 4811624179753978901968271
713 5038115505211487380329473
714 5275105428021054995215952
715 5523073177793552498442176
716 5782519526977819611206478
717 6053967744580839914659132
718 6337964591486808446518172
719 6635081359130472329056902
720 6945914953417106790590074
721 7271089025797319203602497
722 7611255153551110654623252
723 7967094071355247910845880
724 8339316956364153328086263
725 8728666769058366537414202
726 9135919652281419904628342
727 9561886390914508305234281
728 10007413934816522703272108
729 10473386987690764208752028
730 10960729664730069016552353
731 11470407221931592519983573
732 12003427860176028812733036
733 12560844607211943211165397
734 13143757280903491749485381
735 13753314537152759057046111
736 14390716006140635926379656
737 15057214520590902722125680
738 15754118440011074656353039
739 16482794074932893627081562
740 17244668215441628868190725
741 18041230768362133212157385
742 18874037507754543565021783
743 19744712943461702206034975
744 20654953312755359068359599
745 21606529700228837459694328
746 22601291291410350460946646
747 23641168765684338356000310
748 24728177834457814217591604
749 25864422930635671873480977
750 27052101055843355536693204
751 28293505791977370853682968
752 29591031484065234653959187
753 30947177601575104903841008
754 32364553285745105853797299
755 33845882090679145075898715
756 35394006926416588261599430
757 37011895212379785783097417
758 38702644250097109928604582
759 40469486824317498062074018
760 42315797042161732011634941
761 44245096420197747388713226
762 46261060229894740728348841
763 48367524112178823404135081
764 50568490972421554465687388
765 52868138167488966769971727
766 55270824997131481071458455
767 57781100512322269184663052
768 60403711653851935220426045
769 63143611734848235422084985
770 66005969281640974734250450
771 68996177247789798898747552
772 72119862616898983350463026
773 75382896410280927109049148
774 78791404116395564454225714
775 82351776559474113177276399
776 86070681225664677205128981
777 89955074065565905665776408
778 94012211793012417696473769
779 98249664700556064359880473
780 102675330013158204848307385
781 107297445802244761980589006
782 112124605483426111066032986
783 117165772921881603351379708
784 122430298170644009306692138
785 127927933867783411841705195
786 133668852319817239667676615
787 139663663299509651692854802
788 145923432587649293955641304
789 152459701289309510101609441
790 159284505956627055745719596
791 166410399551135739210942103
792 173850473280337632578614481
793 181618379344287509858330759
794 189728354629735352882490394
795 198195245390565356345876476
796 207034532955171386836231851
797 216262360502711600354186879
798 225895560952228892613716599
799 235951686010045043480945537
800 246449036423033710798821457
801 257406693486927096539757154
802 268844551861173437122575678
803 280783353743551471295117176
804 293244724460288023023514164
805 306251209529264902668423714
806 319826313256632552259385073
807 333994538929151680224596725
808 348781430667521215566093639
809 364213617008132192268011606
810 380318856283845878207624704
811 397126083876768014021124855
812 414665461419388309193277981
813 432968428023036175172897585
814 452067753616257793237027496
815 471997594478527017871440649
816 492793551058633240083226693
817 514492728170140979719360671
818 537133797660544275984829714
819 560757063654055007638751144
820 585404530472513041234766703
821 611119973342508364651727427
822 637949012001699145805283755
823 665939187321221622776581000
824 695140041066352951549690088
825 725603198921835205140271545
826 757382456913933816129805144
827 790533871365913325410292327
828 825115852529708907475871019
829 861189262041573786907351279
830 898817514356041743305159319
831 938066682317969544115108106
832 979005607039482185030184039
833 1021706012254527895422560970
834 1066242623331345073021924564
835 1112693291129522975437510197
836 1161139120896511487795894924
837 1211664606405350625577600917
838 1264357769544186461842836667
839 1319310305575634417757369741
840 1376617734293517070082433660
841 1436379557312623412101831417
842 1498699421737324173920732801
843 1563685290463673418216413979
844 1631449619380590925202332330
845 1702109541745245538295663140
846 1775787060019559961686174365
847 1852609245465071659191783727
848 1932708445806084750516202631
849 2016222501282213491848886151
850 2103294969425086864127135166
851 2194075358906068948304223518
852 2288719372816561403217607675
853 2387389161755532196208203352
854 2490253587114748695827788898
855 2597488494966342670541298254
856 2709277000974376684454977605
857 2825809786767387448642092832
858 2947285408227223808882858253
859 3073910616166051367323684641
860 3205900689883137199870266034
861 3343479784110929423333075874
862 3486881289881193850777260131
863 3636348209861324583407324216
864 3792133548733813672630263163
865 3954500719212787456145299947
866 4123723964316129713787614238
867 4300088796534325512506690655
868 4483892454563649196620748031
869 4675444378295757832674428294
870 4875066702784260899796402395
871 5083094771935242082654831580
872 5299877672699392026355358874
873 5525778790571937284448370463
874 5761176387239572429801854850
875 6006464201244415867164098804
876 6262052072570548065008740911
877 6528366592091970278277678844
878 6805851776859067535007075623
879 7094969772236597071587734439
880 7396201581947382093010620661
881 7710047827114693146663193477
882 8037029535440592040188284343
883 8377688961699403369552018694
884 8732590440773142876648105708
885 9102321274500949437942268662
886 9487492653665858556342964996
887 9888740616491058206660250492
888 10306727045072960489540986077
889 10742140701231088472307777420
890 11195698303314166937689988496
891 11668145645558633284210407060
892 12160258761659688232745484713
893 12672845134276316398743203373
894 13206744952260465406586579310
895 13762832417466711120190271165
896 14342017103072717043815750088
897 14945245365412135130639979535
898 15573501811401191654738282184
899 16227810823717141141180991329
900 16909238145972407271880840021
901 17618892530211199224010249721
902 18357927449147522505216767567
903 19127542875652965596522867162
904 19928987132101758144529164102
905 20763558812277048717265798408
906 21632608778648974043711840390
907 22537542237939068678198851695
908 23479820898000262204919243529
909 24460965209153787813251783802
910 25482556693247705347686770468
911 26546240363822536425475287152
912 27653727240902221600790875218
913 28806796964058786231218541372
914 30007300507541847651377140317
915 31257163001404369345809452466
916 32558386662709599785479245717
917 33913053841055270723989838224
918 35323330182816256087713726121
919 36791467918669718765080845256
920 38319809279144361554534189344
921 39910790043110800376571663365
922 41566943224321061988025746180
923 43290902901294138689725090121
924 45085408196049913473022872135
925 46953307407397251409847930458
926 48897562304702906564556953639
927 50921252588287028107814084211
928 53027580522828530485737982457
929 55219875750399560622629093562
930 57501600290003644539863703660
931 59876353730746167048852199047
932 62347878626040387836208133609
933 64920066096525735346707595687
934 67596961649670299989651254549
935 70382771224323917789095796877
936 73281867468805581782254758505
937 76298796261425892696668491008
938 79438283482686421265428993454
939 82705242048739022933833980975
940 86104779216054890974621487772
941 89642204167620310927152035515
942 93323035891370308855363730001
943 97153011361966519563871996316
944 101138094037449354118923739991
945 105284482682719728379726802741
946 109598620532261079955332586805
947 114087204804969878109461268602
948 118757196584452358702877876417
949 123615831078637399424971791930
950 128670628273081561335637655396
951 133929403992871800607772672482
952 139400281388596754127103178105
953 145091702862427053919295398733
954 151012442450952717800647992466
955 157171618682038271010974911937
956 163578707923609154373939997579
957 170243558242941839252848768478
958 177176403795731621773724085961
959 184387879764920626570551144311
960 191889037870022340825143227415
961 199691362468440937251057953851
962 207806787271093521671974914001
963 216247712695462715411015917112
964 225027023880077074458511653241
965 234158109385297704090558437498
966 243654880606224162715421720800
967 253531791924479742693913141594
968 263803861626640344714844839379
969 274486693618089180723037379025
970 285596499962158158231260812071
971 297150124275511084671715698749
972 309165066011882402278605637999
973 321659505667461341534122934410
974 334652330942455768127042891829
975 348163163894634100757529971678
976 362212389121980164654613983341
977 376821183012954343990486880339
978 392011544104289724993910582603
979 407806324587711756255707661063
980 424229263008511350175989682102
981 441305018200469964056247513007
982 459059204503290415493811443356
983 477518428310372563479560471412
984 496710325996550330792547409186
985 516663603277217241890720090431
986 537408076052176031255910705582
987 558974712789493075960105690545
988 581395678506687373964462142560
989 604704380408673329603060995032
990 628935515244076400557995182902
991 654125118443785092439840320763
992 680310615107964379588384002522
993 707530872910166265573678524736
994 735826256989708352317608237323
995 765238686906080250191081451467
996 795811695731858988003445584839
997 827590491363394871511831741780
998 860622020131450249545339200631
999 894955032796959194776366854061
1000 930640153020211282063039602444