1 0
2 1
3 1
4 2
5 2
6 4
7 5
8 8
9 10
10 16
11 20
12 29
13 37
14 52
15 66
16 90
17 113
18 151
19 190
20 248
21 310
22 400
23 497
24 632
25 782
26 985
27 1212
28 1512
29 1851
30 2291
31 2793
32 3431
33 4163
34 5084
35 6142
36 7456
37 8972
38 10836
39 12989
40 15613
41 18646
42 22316
43 26561
44 31659
45 37556
46 44601
47 52743
48 62416
49 73593
50 86809
51 102064
52 120025
53 140736
54 165028
55 193011
56 225710
57 263333
58 307161
59 357521
60 416006
61 483129
62 560864
63 649960
64 752877
65 870677
66 1006426
67 1161604
68 1340012
69 1543687
70 1777365
71 2043780
72 2348821
73 2696156
74 3093095
75 3544485
76 4059416
77 4644241
78 5310255
79 6065739
80 6924691
81 7897846
82 9002580
83 10252687
84 11669704
85 13271328
86 15084211
87 17130918
88 19444436
89 22053415
90 24998640
91 28316370
92 32056941
93 36266093
94 41005947
95 46333953
96 52326672
97 59056128
98 66616548
99 75097925
100 84616150
101 95283359
102 107241923
103 120631254
104 135625995
105 152399071
106 171164557
107 192136373
108 215576593
109 241749411
110 270975242
111 303579637
112 339953965
113 380498578
114 425690950
115 476022556
116 532075157
117 594451027
118 663858302
119 741033636
120 826837956
121 922170954
122 1028078054
123 1145656219
124 1276173587
125 1420965540
126 1581568632
127 1759606135
128 1956937635
129 2175533518
130 2417642016
131 2685651311
132 2982276475
133 3310408366
134 3673322195
135 4074512536
136 4517926253
137 5007782198
138 5548831584
139 6146161389
140 6805484958
141 7532928545
142 8335355650
143 9220135073
144 10195503546
145 11270314440
146 12454442414
147 13758512241
148 15194350744
149 16774694260
150 18513693839
151 20426600638
152 22530330140
153 24843125486
154 27385187785
155 30178316087
156 33246612592
157 36616099292
158 40315506042
159 44375864634
160 48831390225
161 53719052545
162 59079562675
163 64956922535
164 71399529150
165 78459704991
166 86194934299
167 94667375548
168 103945247454
169 114102327226
170 125219503502
171 137384265759
172 150692445800
173 165247702967
174 181163478912
175 198562486204
176 217578902413
177 238357872709
178 261057974047
179 285850741772
180 312923440362
181 342478628789
182 374737275534
183 409938381443
184 448342484721
185 490231360871
186 535911970005
187 585716259725
188 640005611405
189 699170778533
190 763636898176
191 833863599420
192 910350657428
193 993638316401
194 1084313669342
195 1183011249309
196 1290420233355
197 1407285361444
198 1534415077278
199 1672682847961
200 1823036366105
201 1986499358230
202 2164181992422
203 2357283273065
204 2567102821165
205 2795043974057
206 3042627122079
207 3311493653526
208 3603421062158
209 3920327895383
210 4264290877936
211 4637551051529
212 5042533188856
213 5481853346425
214 5958340884921
215 6475047685202
216 7035273138840
217 7642575323118
218 8300799367402
219 9014090932118
220 9786928420126
221 10624139151255
222 11530935954694
223 12512936497419
224 13576204860949
225 14727274556605
226 15973195779023
227 17321562713039
228 18780567257515
229 20359031328722
230 22066467946444
231 23913119348587
232 25910026464628
233 28069073768483
234 30403068308605
235 32925792372436
236 35652093394379
237 38597945669677
238 41780552651027
239 45218419119376
240 48931467594861
241 52941122589176
242 57270443078809
243 61944220705169
244 66989130538333
245 72433845348672
246 78309207198319
247 84648360225397
248 91486945934852
249 98863257294121
250 106818460997215
251 115396776053836
252 124645726756016
253 134616349409697
254 145363480221008
255 156945994342394
256 169427133485129
257 182874782022904
258 197361839793595
259 212966540683460
260 229772876802972
261 247870965742260
262 267357533153993
263 288336335710235
264 310918710084228
265 335224059632175
266 361380478813866
267 389525312739187
268 419805867301272
269 452380051961602
270 487417187250223
271 525098742603510
272 565619254418607
273 609187172382474
274 656025903041194
275 706374779857052
276 760490249255397
277 818646981735067
278 881139219569289
279 948282048644352
280 1020412929553802
281 1097893152456114
282 1181109576176798
283 1270476291387940
284 1366436595540219
285 1469464893062171
286 1580068937617744
287 1698792001804765
288 1826215422374719
289 1962961076249695
290 2109694268949485
291 2267126558628187
292 2436019033230519
293 2617185529704191
294 2811496351331932
295 3019881935500995
296 3243337069283114
297 3482925066150782
298 3739782545412617
299 4015124186097030
300 4310248144331735
301 4626541461530177
302 4965486203273301
303 5328665608955017
304 5717771046486883
305 6134609001773796
306 6581108955643450
307 7059331324242740
308 7571476378118214
309 8119893258923029
310 8707090075877362
311 9335744140174361
312 10008713391247362
313 10729048008373348
314 11500003338401991
315 12325053064390141
316 13207903828187452
317 14152510158701948
318 15163091007121797
319 16244146663115651
320 17400477447769442
321 18637202874879430
322 19959782777454351
323 21374039003548443
324 22886179286708273
325 24502821802193240
326 26231022130362475
327 28078301039949787
328 30052674936877675
329 32162687286937682
330 34417442991249831
331 36826643912100015
332 39400627670790814
333 42150407798002223
334 45087717511058478
335 48225055074623020
336 51575733183063381
337 55153930189710199
338 58974745796756772
339 63054258892410676
340 67409590336951526
341 72058968237796864
342 77021798716793472
343 82318739554982446
344 87971779934030813
345 94004323496376370
346 100441278174591857
347 107309149839882065
348 114636143468412820
349 122452268693810773
350 130789453710561880
351 139681664205717336
352 149165031568693103
353 159277986855633016
354 170061405064075112
355 181558755982974841
356 193816266501929437
357 206883090422879924
358 220811491009889043
359 235657032087527265
360 251478783301180396
361 268339535105609947
362 286306029500356999
363 305449201822952043
364 325844440053296911
365 347571856673023437
366 370716580000299865
367 395369059764581907
368 421625394343310622
369 449587674134015894
370 479364349022239074
371 511070614115498789
372 544828822282542624
373 580768917352403386
374 619028897134443136
375 659755299786483915
376 703103723360440008
377 749239371713072893
378 798337637330191203
379 850584713900420592
380 906178249959977690
381 965328036082153098
382 1028256737764320020
383 1095200666112868479
384 1166410599374062737
385 1242152647027396400
386 1322709170452985614
387 1408379751496978306
388 1499482223983711007
389 1596353759097684853
390 1699352020801864770
391 1808856381807204423
392 1925269217464240208
393 2049017267678726593
394 2180553085519877265
395 2320356562206788935
396 2468936548541534560
397 2626832562056501613
398 2794616601454368874
399 2972895057192452118
400 3162310741418594367
401 3363545025698964905
402 3577320111503785370
403 3804401421487713028
404 4045600138430032111
405 4301775879480791364
406 4573839534628998805
407 4862756256665494627
408 5169548633773745196
409 5495300031669753174
410 5841158138820994573
411 6208338701343941504
412 6598129483701389567
413 7011894441513529154
414 7451078145408300311
415 7917210441983121567
416 8411911393838459790
417 8936896484567997687
418 9493982133951103748
419 10085091509109124038
420 10712260680430481316
421 11377645107978274030
422 12083526511041755885
423 12832320106588180216
424 13626582273455769130
425 14469018628191675328
426 15362492573908704705
427 16310034308333182605
428 17314850357334785351
429 18380333620521385288
430 19510074000524712510
431 20707869603133059005
432 21977738585689560888
433 23323931641671395577
434 24750945205158909903
435 26263535364084318335
436 27866732572801796923
437 29565857154086910586
438 31366535688534084953
439 33274718282955543138
440 35296696823824161172
441 37439124209176423689
442 39709034673797093666
443 42113865203272523819
444 44661478161286358382
445 47360185128319403266
446 50218772086522051179
447 53246525951955124790
448 56453262600281822770
449 59849356390656452911
450 63445771346214791750
451 67254094000041376472
452 71286568078440378940
453 75556131035169785520
454 80076452623088539474
455 84861975522393894682
456 89927958227838358047
457 95290520220441972408
458 100966689643466790885
459 106974453515430930110
460 113332810718878162162
461 120061827805972476935
462 127182697880305609612
463 134717802605429814419
464 142690777622058656546
465 151126581435179847087
466 160051568077636769428
467 169493563623590070029
468 179481946885287503033
469 190047734380319897611
470 201223669932131414435
471 213044319006514289722
472 225546168178897201877
473 238767729852694651726
474 252749652658529016458
475 267534837674336562975
476 283168560934411337881
477 299698602389599787838
478 317175381828488409051
479 335652101946726064978
480 355184899120000125304
481 375833002095763134994
482 397658899209161246875
483 420728514369579673903
484 445111392477847571669
485 470880894555562555002
486 498114403306277186755
487 526893539429181544859
488 557304389470316520926
489 589437745575705932027
490 623389358002858694117
491 659260200803850999792
492 697156751614571573050
493 737191286017769058224
494 779482187499968819328
495 824154273530537513590
496 871339138876499829930
497 921175516748888083872
498 973809658996595347843
499 1029395736018599697176
500 1088096257722564963285
501 1150082516284160195228
502 1215535052157728174181
503 1284644144185379730847
504 1357610325389379232553
505 1434644925397854279201
506 1515970641235644460006
507 1601822137544568870284
508 1692446678125803856421
509 1788104789995349063877
510 1889070962021415977430
511 1995634379475147217445
512 2108099696756362286402
513 2226787849781318011225
514 2352036910505353502960
515 2484202985239681487827
516 2623661159466440213046
517 2770806491001933879934
518 2926055054465399389878
519 3089845039114165090006
520 3262637903279835837368
521 3444919587699626163784
522 3637201791281150838642
523 3840023311852620267520
524 4053951455769310437411
525 4279583519213134698092
526 4517548345420380827490
527 4768507960989083934055
528 5033159295899948453464
529 5312235990749672570529
530 5606510296267383347695
531 5916795068996439139970
532 6243945868690651790984
533 6588863161730186941949
534 6952494636630048267349
535 7335837636412932897259
536 7739941714493038387800
537 8165911319356988623191
538 8614908615316677008037
539 9088156445187144157315
540 9586941442852234247688
541 10112617302195842515986
542 10666608211114819309586
543 11250412457779475207451
544 11865606218682631897742
545 12513847536400942542792
546 13196880497512645108082
547 13916539619429707920819
548 14674754457577479835276
549 15473554442597974138261
550 16315073960092664254845
551 17201557683591187210221
552 18135366174447279278050
553 19118981760459645860075
554 20155014708216878863814
555 21246209702186282092097
556 22395452646966417293408
557 23605777807066952421208
558 24880375302190809844943
559 26222598973859207708065
560 27635974643056882602957
561 29124208776361246426379
562 30691197582095958536940
563 32341036555756007872574
564 34078030498283984754324
565 35906704028403518436778
566 37831812614821230761958
567 39858354151654428208784
568 41991581105338021975229
569 44237013258729870925770
570 46600451083340332673813
571 49087989767998000853332
572 51706033937801331528663
573 54461313094513716925128
574 57360897815450699974699
575 60412216745139257498220
576 63623074420297550086219
577 67001669965840454287106
578 70556616706287648422219
579 74296962734036669341681
580 78232212483065282718656
581 82372349353645706688557
582 86727859441215163471299
583 91309756419502652632346
584 96129607636065483970326
585 101199561475287452352028
586 106532376052469891973529
587 112141449299494917036082
588 118040850511681791603207
589 124245353422263158954416
590 130770470880651056890508
591 137632491207435568010865
592 144848516309445882213488
593 152436501634954540406115
594 160415298060181677999076
595 168804695794997737313630
596 177625470407537082721000
597 186899431064181789240714
598 196649471093979190555417
599 206899620983325400923391
600 217675103920198163575855
601 229002394004031667131562
602 240909277251684690681991
603 253424915526824874489771
604 266579913535383561990795
605 280406389026693541560050
606 294938046356297019367088
607 310210253563482851100127
608 326260123134106243067899
609 343126596616460516696779
610 360850533276665514506814
611 379474802977432949592235
612 399044383484052797909293
613 419606462399058669164670
614 441210543948397532330378
615 463908560839804564190105
616 487754991436937125672474
617 512806982491007302968677
618 539124477696101694898536
619 566770352332926580196422
620 595810554291880676373224
621 626314251765331338721889
622 658353987926977049814515
623 692005842915643724379123
624 727349603470850543161147
625 764468940567510879673455
626 803451595429252417205137
627 844389574300517873819582
628 887379352392017517121852
629 932522087415520559163978
630 979923843160847259593572
631 1029695823570178794275403
632 1081954617804329189733130
633 1136822456798829611977156
634 1194427481850057437014188
635 1254904025775922313547734
636 1318392907241077114455255
637 1385041738842110913273942
638 1455005249596946472606064
639 1528445622489513098689343
640 1605532847773095680763453
641 1686445092744133077862572
642 1771369088754409127460813
643 1860500536239657243811286
644 1954044528602907498298713
645 2052215995802887756600106
646 2155240168562557730441651
647 2263353064126961916680941
648 2376801994569161652466564
649 2495846098659479051064264
650 2620756898388042485020315
651 2751818881249725985263201
652 2889330109480920434384965
653 3033602857459597799856667
654 3184964278566502763090003
655 3343757102830568648294100
656 3510340366774529838099362
657 3685090176905553914495426
658 3868400508395607218602712
659 4060684040529089811511635
660 4262373030602736307736896
661 4473920227999991634336049
662 4695799830277701282536615
663 4928508483145017415245470
664 5172566326338871474810223
665 5428518087447777097123025
666 5696934225869697000052873
667 5978412129143021176660971
668 6273577364033953219381164
669 6583084984823416367768699
670 6907620901391940912521508
671 7247903309767966876854621
672 7604684187972334672794279
673 7978750860066583292492655
674 8370927631492963904374015
675 8782077498877581534954826
676 9213103937662354632430077
677 9664952771024500351037182
678 10138614123751643890160599
679 10635124464844114878958234
680 11155568742841714328727107
681 11701082617987165623774441
682 12272854795581829794207424
683 12872129465016771712525869
684 13500208849224701210035109
685 14158455869439607508786797
686 14848296930433954412736035
687 15571224831559707174845247
688 16328801809224790058723204
689 17122662716609525949088990
690 17954518346757020946699951
691 18826158905362526710229727
692 19739457639942260837191170
693 20696374632273061911292693
694 21698960761377851861459991
695 22749361844564462300548659
696 23849822964439412250062786
697 25002692990074522611210746
698 26210429300951192075148206
699 27475602722589376993615487
700 28800902683250842418103620
701 30189142601416789879539725
702 31643265514260974333147280
703 33166349957680893422281326
704 34761616109012255792042594
705 36432432203927179785717060
706 38182321239624205783290791
707 40014967976830314258194669
708 41934226253791452214502866
709 43944126625880403790553542
710 46048884345159801497494410
711 48252907694734285262788295
712 50560806693491724240760864
713 52977402187377475447172767
714 55507735344173158008302025
715 58157077569347644255467770
716 60930940861442101638121653
717 63835088626103993911558154
718 66875546968851154044155253
719 70058616487362061237586099
720 73390884585132619407087525
721 76879238329122231766081397
722 80530877875140464242617081
723 84353330485581572874857753
724 88354465165333895253696995
725 92542507942627096595138500
726 96926057822898671250970506
727 101514103444784180025401951
728 106316040468760867890912596
729 111341689730092161485478986
730 116601316189261192310920700
731 122105648714302462837519095
732 127865900731106343903253140
733 133893791779104230080154757
734 140201570011542889312188673
735 146802035681011667815860536
736 153708565652833106920034910
737 160935138990515291014468389
738 168496363659569277404011926
739 176407504397726911089252427
740 184684511801870419745076307
741 193344052683873853814041992
742 202403541750017567604570186
743 211881174660695907633925630
744 221795962529799561823547050
745 232167767925398019655514911
746 243017342436225385867782360
747 254366365870917775402606905
748 266237487160062493722933573
749 278654367033782480744510806
750 291641722550944774278755090
751 305225373558982059563888277
752 319432291166955621416988846
753 334290648317645677016358800
754 349829872548390639201836915
755 366080701033833880689204868
756 383075238007992627776702417
757 400847014666803831752957239
758 419431051656904535008045175
759 438863924260473490012135163
760 459183830390938310034760808
761 480430661518778658401752606
762 502646076652038885173349227
763 525873579500977016616460179
764 550158598962098286585268812
765 575548573062054951632032045
766 602093036508189465718719048
767 629843711998187195057772139
768 658854605448112789933009883
769 689182105304287409515682100
770 720885086111826199264530602
771 754025016519374061539012919
772 788666071907539257156720745
773 824875251835823585246755322
774 862722502511457336756637273
775 902280844491475696422277607
776 943626505838683244008132200
777 986839060960763649685286324
778 1032001575371858971057649812
779 1079200756625292376433262527
780 1128527111676994146896423866
781 1180075110949340867815741705
782 1233943359376888774794645286
783 1290234774726499621066939729
784 1349056773497085149040393990
785 1410521464716153134692849305
786 1474745851964099733658903061
787 1541852043970167239586312161
788 1611967474138865755916722862
789 1685225129379733514094036061
790 1761763788629397872053656235
791 1841728271470168310812182922
792 1925269697266785463516503426
793 2012545755259511142279757939
794 2103720986070547761528308056
795 2198967075098734712886734939
796 2298463158297797109106489154
797 2402396140852894891466543967
798 2510961029292195375886771676
799 2624361277591302806539384785
800 2742809147852133365579270728
801 2866526086160707034443096536
802 2995743114254005523873182447
803 3130701237650846261415731925
804 3271651870929477727256898460
805 3418857280861477088681193790
806 3572591048141530694746914090
807 3733138548481798221217911552
808 3900797453871985260052458844
809 4075878254837797239255661362
810 4258704804565490337503808388
811 4449614885794408992222605768
812 4648960801417270951112899149
813 4857109989764974418889650337
814 5074445665593628197149672976
815 5301367487831589899371459786
816 5538292255188523013383705493
817 5785654630771887697258497283
818 6043907896904068905377662354
819 6313524741380338713964117041
820 6594998076459485958378893765
821 6888841891929819394715899058
822 7195592143649041349226451797
823 7515807679011555533543598553
824 7850071200857049151561981277
825 8198990271393788468402832910
826 8563198357775186443280519481
827 8943355921032697994415593150
828 9340151550138446296778694695
829 9754303143040772965858698738
830 10186559136591896947738953736
831 10637699787362374673765851572
832 11108538505419138541106703326
833 11599923243225576269540370773
834 12112737941910774330966523058
835 12647904037243407637973185275
836 13206382027741516006002444773
837 13789173107444975251914898250
838 14397320865980889208205146211
839 15031913058655481638070586170
840 15694083449417751979187285200
841 16385013729651919315626553903
842 17105935515876284315740117365
843 17858132429546978449201954040
844 18642942262295300491873644125
845 19461759230057983058514364692
846 20316036319700347953181321854
847 21207287731873535854431146036
848 22137091423998816527291292573
849 23107091757424638493951397296
850 24119002252965985500055581660
851 25174608459200593776095715796
852 26275770938073532080602199025
853 27424428372539945976102494714
854 28622600801166781235900298970
855 29872392984806968861002167150
856 31175997910665738676215333083
857 32535700439286901798700622702
858 33953881100209489208178765965
859 35433020042270038972801446267
860 36975701144766017861780518855
861 38584616295938822096005170732
862 40262569845494024660947295511
863 42012483238138973765711468209
864 43837399835397589524492169699
865 45740489933245656295108230276
866 47725055983411775986894981246
867 49794538026495265348750612249
868 51952519345378003110827261245
869 54202732347737800210892356482
870 56549064686822307278421356410
871 58995565629999410845245249221
872 61546452684979235524105543392
873 64206118493988245395946543733
874 66979138006584989785657480428
875 69870275942223081868526029050
876 72884494554108264331119307928
877 76026961706345527347594704821
878 79303059276848230400183285964
879 82718391898965943827138763547
880 86278796055301131921625891170
881 89990349537708001698370213912
882 93859381288020573385341309156
883 97892481634621667732376275773
884 102096512940561692318764350730
885 106478620679545414041204857990
886 111046244956748916027527818266
887 115807132492086385272396343388
888 120769349084240838947935232064
889 125941292574482232140687671573
890 131331706330045205888407419457
891 136949693267603986395677650558
892 142804730438189318931860098564
893 148906684195717827992813143566
894 155265825972174647112602889961
895 161892848683380596389328909468
896 168798883790213584227554656159
897 175995519041114298262612289035
898 183494816922717833662350417491
899 191309333846488659930765021359
900 199452140100326732087685874827
901 207936840595229492504233306945
902 216777596438269801155552535674
903 225989147364354226256328129418
904 235586835060492831290374086887
905 245586627417610185343204061592
906 256005143746292461230858854104
907 266859680994265528704374966390
908 278168241004870074309855533803
909 289949558857309080032590923875
910 302223132331028229051470028105
911 315009252538216762992077236392
912 328329035770124403095575862384
913 342204456604643593166154197584
914 356658382324446662590285111339
915 371714608696857560054084016710
916 387397897168620511892076337672
917 403734013530764870356760850287
918 420749768110901356565795734354
919 438473057552479914783735391765
920 456932908242840263192740301117
921 476159521454251428449155821804
922 496184320264614922255701369227
923 517039998327054611531178692256
924 538760570560285726505201457873
925 561381425834401015587597535976
926 584939381729587005984478601759
927 609472741448241096381760883829
928 635021352964056342627117622190
929 661626670494826928877707482912
930 689331818389061435327715706812
931 718181657519922884138092885125
932 748222854283604706643641918883
933 779503952302948062455752164291
934 812075446940971556454220205991
935 845989862732965181976582851237
936 881301833849962251212020351556
937 918068187710689931737879063981
938 956348031863579681046869065489
939 996202844265034999401543635263
940 1037696567084977431863133956145
941 1080895704175662077477097681300
942 1125869422344946107001489685584
943 1172689656580545105299911876909
944 1221431219377400856365008062125
945 1272171914326045278112412396250
946 1324992654125860472140359971668
947 1379977583193336648931110320432
948 1437214205041903525522823045089
949 1496793514616586528181506509934
950 1558810135773706057762595635280
951 1623362464103023456790431377003
952 1690552815297234404129805536148
953 1760487579281443848700666076840
954 1833277380323323666107694871693
955 1909037243352976817456052905899
956 1987886766730211623716388821460
957 2069950301705885835470684805039
958 2155357138833318717890981357707
959 2244241701595406448756246293607
960 2336743747523122717244801858771
961 2433008577091455559906146902916
962 2533187250689639102003003938112
963 2637436813973694926780915237098
964 2745920531920923374894539658203
965 2858808131917986922455670422595
966 2976276056226732419151647081191
967 3098507724184809838592937106397
968 3225693804511594489967048435217
969 3358032498103807430810629474061
970 3495729831719693225164232556755
971 3638999962965551799845091399647
972 3788065497013976291477983073933
973 3943157815499214466575034483217
974 4104517418051798361058842767460
975 4272394276951864575302865470265
976 4447048205398573802143251956433
977 4628749239911618246836197601280
978 4817778037400144366426924010692
979 5014426287454397541588084311629
980 5218997140436187099507955835990
981 5431805651965752308215752079443
982 5653179244424962571740792903632
983 5883458186119881799298949808463
984 6122996088769755989132217215853
985 6372160424014314043224848431797
986 6631333059657101468251150927444
987 6900910816389260269059601626914
988 7181306045765931733941703701194
989 7472947230236152966218002189763
990 7776279606056958068397836065164
991 8091765809953237435885886484806
992 8419886550416978656059338614377
993 8761141304572662132767573920603
994 9116049041570049084353194338913
995 9485148973501226502442605372510
996 9869001334875809155483171895491
997 10268188191726485611314504174264
998 10683314281456891036071681173407
999 11115007884584932289804712473511
1000 11563921729577449985956018909705