0 0
1 0
2 1
3 0
4 2
5 0
6 3
7 1
8 6
9 4
10 10
11 11
12 20
13 23
14 32
15 44
16 57
17 77
18 90
19 129
20 150
21 208
22 236
23 334
24 381
25 522
26 595
27 803
28 936
29 1234
30 1435
31 1861
32 2193
33 2770
34 3291
35 4105
36 4884
37 6001
38 7172
39 8678
40 10418
41 12487
42 14969
43 17791
44 21330
45 25164
46 30181
47 35398
48 42337
49 49463
50 59057
51 68692
52 81806
53 94973
54 112774
55 130548
56 154523
57 178608
58 210772
59 243207
60 285946
61 329669
62 386411
63 444821
64 519600
65 597665
66 696049
67 799703
68 928275
69 1065751
70 1233628
71 1414722
72 1632867
73 1870993
74 2153971
75 2465425
76 2831085
77 3237633
78 3709421
79 4237316
80 4843995
81 5527974
82 6306971
83 7189322
84 8186788
85 9322274
86 10597532
87 12053538
88 13679490
89 15541717
90 17611681
91 19985982
92 22615226
93 25634920
94 28968887
95 32798301
96 37016974
97 41862507
98 47191023
99 53306385
100 60023255
101 67724391
102 76176448
103 85852498
104 96468102
105 108599010
106 121908024
107 137086784
108 153740618
109 172695128
110 193499095
111 217122751
112 243064704
113 272453894
114 304744982
115 341243901
116 381372014
117 426618278
118 476399029
119 532400475
120 594053484
121 663252966
122 739485130
123 824859439
124 918970080
125 1024138016
126 1140130848
127 1269498124
128 1412249500
129 1571140598
130 1746551418
131 1941445740
132 2156671073
133 2395388286
134 2659081110
135 2951089805
136 3273712178
137 3630433253
138 4024588767
139 4459821939
140 4940736968
141 5471065015
142 6057036501
143 6702472333
144 7415526439
145 8200079760
146 9066659085
147 10019198668
148 11071057908
149 12226183093
150 13501334817
151 14900559803
152 16444586130
153 18137530939
154 20004894187
155 22050992454
156 24306820161
157 26776996222
158 29498994944
159 32477975639
160 35758876328
161 39347617137
162 43297828914
163 47616698075
164 52367751354
165 57559877931
166 63268102861
167 69503823161
168 76355070665
169 83836618087
170 92051449023
171 101018972835
172 110859099508
173 121597291916
174 133372767681
175 146219090995
176 160297214210
177 175651022456
178 192466227141
179 210800083032
180 230866118735
181 252738389458
182 276661986977
183 302732256164
184 331229722330
185 362276132178
186 396192158622
187 433132376059
188 473462608956
189 517377647475
190 565294437720
191 617457118873
192 674340206255
193 736247707285
194 803719368150
195 877131811814
196 957098460909
197 1044083218437
198 1138783256375
199 1241767214154
200 1353827238217
201 1475656990338
202 1608156741825
203 1752168997672
204 1908717357480
205 2078820570597
206 2263643216627
207 2464412520685
208 2682454427590
209 2919241650360
210 3176285439298
211 3455346814600
212 3758150325922
213 4086794789006
214 4443250455432
215 4830010852433
216 5249330325012
217 5704162540857
218 6197090469242
219 6731602909767
220 7310664104046
221 7938384279989
222 8618170059144
223 9354851338314
224 10152349642742
225 11016327640520
226 11951305555319
227 12963907123033
228 14059351016057
229 15245369489399
230 16527994716903
231 17916234592733
232 19417071370406
233 21040980322249
234 22796051324244
235 24694443880056
236 26745542312508
237 28963439080427
238 31359028009515
239 33948615400872
240 36744858637222
241 39766600385149
242 43028553792079
243 46552461172268
244 50355436482476
245 54462538337432
246 58893676718528
247 63677697304467
248 68837771070202
249 74407069194439
250 80412557405631
251 86892340012744
252 93877801649620
253 101412676941759
254 109533484872423
255 118290375577884
256 127725838450535
257 137897339409438
258 148854292511393
259 160662497175006
260 173379404311645
261 187080309741027
262 201831972843688
263 217720500972489
264 234823434341094
265 253239200119992
266 273057801036485
267 294391685001136
268 317345265328703
269 342046960065012
270 368617808070881
271 397204406667064
272 427946978755194
273 461012822777120
274 496564261625727
275 534792153716711
276 575884271060232
277 620058306616419
278 667531293092204
279 718551462343621
280 773369487964048
281 832268379428183
282 895537419479526
283 963499206943634
284 1036487330074835
285 1114869467372834
286 1199029982671442
287 1289387868030759
288 1386385648698633
289 1490500758251396
290 1602242265833869
291 1722154124598844
292 1850821518709686
293 1988864147822243
294 2136954145367337
295 2295797441913366
296 2466165466777760
297 2648862328340842
298 2844772741841456
299 3054812564274945
300 3279995691735654
301 3521365212327266
302 3780082199936114
303 4057334532439977
304 4354450910624553
305 4672784014514479
306 5013853280176592
307 5379198919003693
308 5770557322683469
309 6189682086935878
310 6638556208099860
311 7119176016269393
312 7633804681728215
313 8184714661160191
314 8774487238239125
315 9405708857852119
316 10081321864741695
317 10804269728472086
318 11577904328623600
319 12405574977287015
320 13291097912277247
321 14238283690166901
322 15251474798062578
323 16335005840377892
324 17493815453175094
325 18732833549498872
326 20057673786667063
327 21473942080472589
328 22988016163345879
329 24606269425291234
330 26335944078062578
331 28184284551775933
332 30159510821066655
333 32269855605158869
334 34524644360933904
335 36933230755542280
336 39506189695383200
337 42254145900260089
338 45189085971420368
339 48323075358534293
340 51669695183620386
341 55242643440186530
342 59057301695591830
343 63129217199005106
344 67475803882728123
345 72114703001939340
346 77065622009554120
347 82348572478227388
348 87985849326625621
349 94000146282059366
350 100416676606257466
351 107261167950420402
352 114562124195566776
353 122348703577079901
354 130653119465225483
355 139508407846661336
356 148950962641057341
357 159018201403555756
358 169751228438994791
359 181192410421380824
360 193388157628160063
361 206386424825479074
362 220239597907954194
363 235001939024707100
364 250732562112236596
365 267492845911178970
366 285349478057725572
367 304371864166029481
368 324635215374701333
369 346217987526321156
370 369204982311929949
371 393684856193217589
372 419753199399338739
373 447510161369364812
374 477063466207613678
375 508526208182360077
376 542019755022279557
377 577671775767557537
378 615618976555404520
379 656005431049355667
380 698985084912414082
381 744720469490515580
382 793384903113048854
383 845161678199518885
384 900245877691575458
385 958844137743443045
386 1021175988610008369
387 1087474306094046813
388 1157986074559107454
389 1232973654537503763
390 1312714855432435417
391 1397505158881828735
392 1487656975904301773
393 1583502981850694768
394 1685394421246021789
395 1793705724226020517
396 1908831708062027526
397 2031193662916272828
398 2161235287015561075
399 2299430445051897435
400 2446277658079104277
401 2602309758194044977
402 2768086741585971447
403 2944207559515979985
404 3131301126459287580
405 3330040509628944136
406 3541131870814987691
407 3765331334560409028
408 4003431625282445446
409 4256281917485147099
410 4524771917316229094
411 4809855016753798763
412 5112529551155315033
413 5433865604449841636
414 5774983162895936677
415 6137082936391452023
416 6521421112501389754
417 6929344584729629080
418 7362262001167400681
419 7821683808538540798
420 8309189275474207417
421 8826471786417015345
422 9375301513673933873
423 9957576411612692267
424 10575280200264183937
425 11230539534768135161
426 11925576962405083603
427 12662774755632464007
428 13444622498265944935
429 14273788092663475526
430 15153059636763666041
431 16085424125268243510
432 17074003280139112051
433 18122140483997202493
434 19233330242077321286
435 20411313889442983470
436 21660002373047941544
437 22983581286924997160
438 24386426690718748825
439 25873220022456922964
440 27448856693195546342
441 29118571431666080243
442 30887839438479134783
443 32762512701612869530
444 34748713533054135027
445 36852982389142663251
446 39082163675381050044
447 41443565576966913820
448 43944838079003867392
449 46594145292782276108
450 49400035725812750209
451 52371627546104483387
452 55518471221784481079
453 58850748129535216690
454 62379125802268477891
455 66114970222559080286
456 70070194033900592978
457 74257482805651727944
458 78690136715458375629
459 83382310983678016623
460 88348851692177662967
461 93605550504644116218
462 99168975481609825282
463 105056740090523070296
464 111287330075894017775
465 117880386653198607619
466 124856530742299030903
467 132237660090525058347
468 140046772429711902996
469 148308276136515206505
470 157047814175819075689
471 166292587722299805920
472 176071183073525389556
473 186413907475958179937
474 197352621561041907815
475 208921086402705328985
476 221154804414569337183
477 234091376444793845815
478 247770354528324551766
479 262233607556845405866
480 277525189747690373760
481 293691713170213754229
482 310782236326822963248
483 328848641504765976659
484 347945548435595375654
485 368130694127109067955
486 389464877200961207518
487 412012337511505992448
488 435840737425441846370
489 461021538172017844130
490 487630025085642444455
491 515745677223975814314
492 545452244375064002028
493 576838106085223759984
494 609996409095941396430
495 645025411471662768899
496 682028690059013411500
497 721115464947365099661
498 762400887540539525732
499 806006340111567714164
500 852059816125953316691
501 900696189158266817146
502 952057698268803614632
503 1006294180027118780740
504 1063563672947450272234
505 1124032605864552362489
506 1187876536728444721881
507 1255280290042578974276
508 1326438846710380248719
509 1401557422708513521169
510 1480852528139374472556
511 1564551978808648769020
512 1652896144177457934178
513 1746137882988806881605
514 1844544001476070633047
515 1948395103683883432006
516 2057987283013981727164
517 2173631877432904394174
518 2295657419248169494218
519 2424409284968923908822
520 2560251930153452986474
521 2703568423283160795334
522 2854762994520057983728
523 3014260442683392721605
524 3182509028861565550397
525 3359979745313392831492
526 3547169587099463487491
527 3744600671600083276263
528 3952823923638213677701
529 4172418034278127830875
530 4403993597275303368704
531 4648191895954144111180
532 4905689531364168579998
533 5177197026248433138824
534 5463463987830483867918
535 5765277518417936815574
536 6083467958436314985008
537 6418907093817219411817
538 6772514527656188999750
539 7145255675494271675569
540 7538148816854754009640
541 7952262870695000695224
542 8388725180947000160516
543 8848719065996724709746
544 9333492395454105955548
545 9844354909301688317041
546 10382687646134862763966
547 10949940030043628847767
548 11547640213769894552055
549 12177391934029586279019
550 12840885836224709513679
551 13539896102275536702764
552 14276292826878373411695
553 15052038425688443411385
554 15869201136349969559329
555 16729951219482149099628
556 17636575661240180586437
557 18591474184605537829937
558 19597175233556887382514
559 20656331818362840489788
560 21771738865026887471224
561 22946328924978234770141
562 24183190976889074125266
563 25485566039171039705088
564 26856867514948474573362
565 28300676754522087628722
566 29820765037706764830906
567 31421089143708726282608
568 33105815068865163301352
569 34879313672504759938164
570 36746186231595972817164
571 38711260244222617000453
572 40779616926522278186199
573 42956587269450680658473
574 45247781586961817580206
575 47659085938001634445040
576 50196693838888882186796
577 52867103180038860453334
578 55677150219112668405283
579 58634007142116761291261
580 61745218458116987698672
581 65018699375998156343246
582 68462774725308501598556
583 72086178344711589206363
584 75898094657998725896107
585 79908159296774892412148
586 84126503464742295507110
587 88563756047248512443402
588 93231090901851596088167
589 98140230739603499040533
590 103303497484388911497184
591 108733818247194893443503
592 114444778902295528280340
593 120450632514653307839717
594 126766356286215110747732
595 133407662840300407810711
596 140391060697807406566970
597 147733868869119308679870
598 155454281026277637375825
599 163571383905145937231099
600 172105225347550950840496
601 181076837072117245632310
602 190508306768219474120105
603 200422805855941098570032
604 210844665823597663217067
605 221799411663390026012967
606 233313842654347195929255
607 245416072233579601355995
608 258135613439217196574519
609 271503426055308889092975
610 285552006942496159820873
611 300315445381015917742385
612 315829518533389885317254
613 332131756001862447123066
614 349261540684904415161545
615 367260183666780093662569
616 386171030751243099019915
617 406039548908714736446237
618 426913438793837743258958
619 448842734094130624899604
620 471879920366542466484774
621 496080048757353160087067
622 521500861523718651300142
623 548202921732621726564006
624 576249745870812464495325
625 605707951277102642619467
626 636647396285115320059024
627 669141347303554634374756
628 703266626985048077614021
629 739103803039301572233198
630 776737344975333743586891
631 816255836918015230254887
632 857752143534956411030084
633 901323649324153020226055
634 947072434407322428239924
635 995105542971106299601733
636 1045535169691625559998366
637 1098478960239430621243435
638 1154060209192017197684567
639 1212408195760422826623054
640 1273658394153236119093406
641 1337952847945711539281686
642 1405440393977581497043759
643 1476277079070561597071707
644 1550626398679517815685588
645 1628659759967103518023367
646 1710556736579909885687534
647 1796505582417043976533655
648 1886703504077765040208909
649 1981357230008940465972410
650 2080683302364807766110267
651 2184908706595085910117338
652 2294271184678766141385183
653 2409019930615055952342783
654 2529415927238935036558312
655 2655732713509361555715135
656 2788256747393411485123357
657 2927288251306029447505757
658 3073141603858656310173196
659 3226146270301133140558973
660 3386647226280344214887463
661 3555005980662477896661999
662 3731601034834493372712621
663 3916829005854284608710711
664 4111105125263146036692093
665 4314864471117519389965577
666 4528562510762727187462262
667 4752676450952878325100596
668 4987705829576446266843011
669 5234173993766989936777105
670 5492628746167941709157267
671 5763643961686626536320470
672 6047820294552520865558614
673 6345786945166572241863177
674 6658202434943291657103525
675 6985756535568716305533566
676 7329171119435866440729926
677 7689202264544572187289220
678 8066641189243202241781655
679 8462316546993810791622761
680 8877095455135761171283850
681 9311885994798757748118961
682 9767638344507793583457134
683 10245347501667078741655460
684 10746054533047946970711107
685 11270849535487581540591231
686 11820873016645437498999095
687 12397319113875817798890098
688 13001437120122292128479480
689 13634534981333329882694965
690 14297980983994128967413071
691 14993207552973571037338075
692 15721713118988714104625685
693 16485066240402621512250896
694 17284907670886678713717517
695 18122954830447031342809190
696 19001004095715762727104540
697 19920935647374563309401103
698 20884716007878784790564427
699 21894403294485912277037719
700 22952150031820771171956477
701 24060208841912334983843995
702 25220935561858272847344801
703 26436795404643443641421752
704 27710366415283683971702122
705 29044346138755188431005910
706 30441555451410591600467548
707 31904945775108000577758150
708 33437603324424596566480125
709 35042756909055697487234536
710 36723782641426610857665583
711 38484212372653038058218462
712 40327738909603095396759818
713 42258225133194457367436240
714 44279709778813526398735890
715 46396417289493059396535357
716 48612764218889361630901990
717 50933369875964811161988382
718 53363063415494950952195750
719 55906895335295894355301550
720 58570145325516511705268597
721 61358334684240888784145019
722 64277235003662411224673958
723 67332881575076983225897770
724 70531582997479406401953854
725 73879935648592959522938284
726 77384834309524629983532970
727 81053487784579588085652350
728 84893430644408072714638545
729 88912540083983971442328667
730 93119048896240600315788850
731 97521563664782075824951552
732 102129079090384169840415857
733 106950997622830889950226768
734 111997145273929673316837821
735 117277792801351266166051785
736 122803673154036525250201711
737 128586004330155413873558525
738 134636508614051704762889696
739 140967437240468729203612069
740 147591591596554751830289400
741 154522349835427627019621132
742 161773690232361727088409050
743 169360219902628096784836725
744 177297200517866873016620838
745 185600579296076090341994238
746 194287017302474031530107723
747 203373922893560448685262877
748 212879482846578208954761272
749 222822698454891207434191317
750 233223419751604935874264170
751 244102384470162567196329298
752 255481255650875983846575563
753 267382663698804114953261762
754 279830247687064332056437520
755 292848700763801678052370749
756 306463815493287208589377177
757 320702532885334612670977544
758 335592992144559625317485883
759 351164583619023025031593085
760 367448003359752497686821311
761 384475310310945786936849832
762 402279986116169657466188283
763 420896996900255712243714339
764 440362858795634646039504651
765 460715704696379025764390633
766 481995356018196767225772654
767 504243394838050226212342367
768 527503242444561146763106230
769 551820237312622116921764633
770 577241721047691085502249456
771 603817122683936687719601481
772 631598052676320955596641437
773 660638394053499490902359978
774 690994405166062917987426332
775 722724818271837639037240200
776 755890951807404118427549267
777 790556817034063826397922630
778 826789240663229854506532828
779 864657980246365751200730357
780 904235858053275754469695193
781 945598885949348862055605623
782 988826411499681920453796355
783 1034001253142208751318096867
784 1081209859570279192017316353
785 1130542456081372095329397396
786 1182093218376786510428814161
787 1235960431042957889250917730
788 1292246676999650317923171301
789 1351059009155130830267888237
790 1412509156834383204058083835
791 1476713711740935208683092219
792 1543794352804515551076256655
793 1613878047682056035730063959
794 1687097297580684401978980394
795 1763590355638752930213367148
796 1843501493405599178726831523
797 1926981237561399633869579404
798 2014186659870606623247830607
799 2105281633827554488852702560
800 2200437150046472669319253508
801 2299831594559196951427429801
802 2403651091762237732614229976
803 2512089806244337478502323937
804 2625350315580860409830844630
805 2743643937733647861823545648
806 2867191136166218084332453177
807 2996221875037136872184114256
808 3130976059306984774433272723
809 3271703920140839070892006140
810 3418666492891028624098125118
811 3572136035335271356478546743
812 3732396546648841824485998288
813 3899744221334150397421646299
814 4074488012543733394847522640
815 4256950124805726523299469264
816 4447466625326098518109445621
817 4646387978884633596419435384
818 4854079711032945703143236265
819 5070922988828509837131454608
820 5297315340155544976614793841
821 5533671284282697091733140145
822 5780423111868950695971097573
823 6038021569675368267014302765
824 6306936706179343530760639698
825 6587658615144990737705067532
826 6880698352158791796071496518
827 7186588742168691856949511188
828 7505885372674276496877334270
829 7839167470784511062459829193
830 8187038979248888577437113350
831 8550129509060198095512857202
832 8929095505001793343560261908
833 9324621280338389721956448321
834 9737420279081947337591017025
835 10168236199872924336427420878
836 10617844362735812922498738798
837 11087052929859563197573455145
838 11576704385227389482938558695
839 12087676860661338446610285039
840 12620885737372533931496479772
841 13177285086345848109465454155
842 13757869401570686943315009702
843 14363675164611010837966605060
844 14995782720046659450558983762
845 15655317974907005120341992255
846 16343454427683672044748840278
847 17061415014207216147556155148
848 17810474302488117060364914642
849 18591960497591219935462955743
850 19407257815528949857308538406
851 20257808660742898488025412812
852 21145116193316194069858752256
853 22070746693812747117196969969
854 23036332339201380363653784648
855 24043573771036730513303526886
856 25094243096701943208417157005
857 26190186678249289156630051348
858 27333328376878693734479455846
859 28525672581197758048083143698
860 29769307714266980552102148063
861 31066409521597433705187063661
862 32419244861619283169021958631
863 33830175275419042765022779639
864 35301661083133885663499648738
865 36836265259250022993357691870
866 38436657859201761607029248097
867 40105620226017623490879681706
868 41846049773319606699134554788
869 43660964551226620339349701138
870 45553508414017922917922209848
871 47526955975495490885559818568
872 49584718191807247713312918216
873 51730347738945319965715418190
874 53967545043633352192221820778
875 56300164118309309277228675301
876 58732219075579859390902568910
877 61267890458920845139826030375
878 63911532279006484548608626836
879 66667678881473066334384914012
880 69541052546456823874807151847
881 72536570938125630546751964542
882 75659355312025378169014381759
883 78914738594708248242658607688
884 82308274247011130615170419960
885 85845745026019009156319038733
886 89533172556201852291917194216
887 93376826830168508420257035745
888 97383236543691451917881200437
889 101559199396255159971963542590
890 105911793250425910960055444495
891 110448387298103041890847829555
892 115176654109468071869154441955
893 120104581736136046189597319653
894 125240486720073270731434874203
895 130593027210547212005656112464
896 136171217008963577618800791846
897 141984439782659771189092501362
898 148042464227613062155864970650
899 154355459468747040259111775637
900 160934011428936479164271754577
901 167789139512636282389710960247
902 174932314276593640703512601785
903 182375475501302605866698709054
904 190131051266369035496380807324
905 198211977522584510517662735521
906 206631718683018675926989088007
907 215404288817437772996015073056
908 224544273878967489643703439246
909 234066854652203855667619175037
910 243987830744748721615349145883
911 254323645430725294690480015543
912 265091411546690580743099188442
913 276308938383431740619490787803
914 287994759636764329897866139687
915 300168162512508384223825046162
916 312849217894549239248208791577
917 326058811840839781119046468576
918 339818678143900444808989283648
919 354151432409635134919093600909
920 369080607199249808197866342153
921 384630688897680303733083725504
922 400827155640793538615180300459
923 417696517196385562557017094099
924 435266355896578690939928543115
925 453565369771744888554344622197
926 472623416725317206329749166796
927 492471561179719647046563726938
928 513142121749467964415290774814
929 534668721678343084120278763548
930 557086340286770139447331307575
931 580431367501165137158371808302
932 604741659373263342420168270936
933 630056597025914360804156648400
934 656417146565403078821504785178
935 683865922793090335491712437550
936 712447253856960983072108200518
937 742207250105539227551581059337
938 773193873852049231165635533569
939 805457013776119441029261682177
940 839048560203201029288104892043
941 874022485490867770667910913844
942 910434925257668799589732538889
943 948344265224495219960810234532
944 987811228861019359191502824166
945 1028898971188813749759577684887
946 1071673173350136070930454276390
947 1116202143918441640903579585811
948 1162556920933712517799505776690
949 1210811381307905059636115159435
950 1261042350913508791407272464976
951 1313329722716537394581646519794
952 1367756575550769817595181628309
953 1424409301659361164730761616460
954 1483377734836514396606774046954
955 1544755288110912190907904874415
956 1608639091989660605873828387736
957 1675130143072795321634664607267
958 1744333453191515651066626560670
959 1816358209803293367900793920217
960 1891317936877986945854735191976
961 1969330667987890255242534120101
962 2050519119861613706892321903891
963 2135010879153094313166702135197
964 2222938589654510416086668558357
965 2314440153803193276325546527318
966 2409658934621687336212996507606
967 2508743973102049218160126525758
968 2611850206023889278024413965991
969 2719138700442131344208629347532
970 2830776888622913233456851758197
971 2946938820953962721013405137370
972 3067805419334072326545873839495
973 3193564749925300832123742734335
974 3324412296434877621135507760418
975 3460551254235987708846071484813
976 3602192825091953300958583126734
977 3749556534287953316396015225799
978 3902870548466759038795873432247
979 4062372017537978841124919298993
980 4228307417423125111313283599412
981 4400932918642495181952544400162
982 4580514755905590399434166421527
983 4767329625419239455737194467833
984 4961665083408109314825870827372
985 5163819974341876534428041208071
986 5374104860630537988565904158481
987 5592842484134140229782539601626
988 5820368229449657735890156847009
989 6057030621244839950702438953521
990 6303191823738468236566431290431
991 6559228176591196749548532283962
992 6825530733379996322984649573855
993 7102505838984416998915472806593
994 7390575710070003711432083666799
995 7690179057129256782865220358588
996 8001771710218877796166834412550
997 8325827289051963889771920805410
998 8662837877481293312136914788190
999 9013314745294182989351502555650
1000 9377789075199936998007950166880