1 0
2 1
3 1
4 1
5 2
6 3
7 4
8 6
9 7
10 10
11 13
12 18
13 23
14 31
15 39
16 50
17 64
18 82
19 102
20 130
21 162
22 203
23 252
24 313
25 384
26 475
27 580
28 710
29 864
30 1053
31 1273
32 1544
33 1859
34 2240
35 2688
36 3224
37 3851
38 4602
39 5476
40 6514
41 7727
42 9160
43 10826
44 12791
45 15072
46 17747
47 20853
48 24481
49 28679
50 33577
51 39231
52 45801
53 53383
54 62166
55 72276
56 83968
57 97402
58 112892
59 130670
60 151121
61 174545
62 201448
63 232208
64 267451
65 307704
66 353733
67 406209
68 466124
69 534326
70 612049
71 700414
72 800944
73 915064
74 1044711
75 1191680
76 1358374
77 1547118
78 1760879
79 2002580
80 2275966
81 2584695
82 2933407
83 3326752
84 3770455
85 4270339
86 4833554
87 5467344
88 6180543
89 6982256
90 7883364
91 8895174
92 10031188
93 11305410
94 12734454
95 14335755
96 16129711
97 18137864
98 20385369
99 22898752
100 25708866
101 28848492
102 32355377
103 36269796
104 40638055
105 45509535
106 50940796
107 56992464
108 63733504
109 71238050
110 79590305
111 88880726
112 99211786
113 110693949
114 123451711
115 137619536
116 153348758
117 170802779
118 190165085
119 211634235
120 235432387
121 261800237
122 291006752
123 323343244
124 359134674
125 398733537
126 442531914
127 490955434
128 544477023
129 603609921
130 668923572
131 741036515
132 820633566
133 908458918
134 1005335686
135 1112158100
136 1229914031
137 1359677293
138 1502632133
139 1660066084
140 1833397904
141 2024169618
142 2234078666
143 2464970481
144 2718873762
145 2997994222
146 3304754714
147 3641788684
148 4011986314
149 4418489310
150 4864741863
151 5354487640
152 5891827945
153 6481219297
154 7127540204
155 7836091556
156 8612670868
157 9463576730
158 10395693492
159 11416498109
160 12534157442
161 13757540298
162 15096326253
163 16561024776
164 18163099581
165 19914993264
166 21830270004
167 23923649596
168 26211167910
169 28710222957
170 31439758386
171 34420320315
172 37674268122
173 41225847304
174 45101427438
175 49329595158
176 53941426541
177 58970599644
178 64453707272
179 70430396355
180 76943722496
181 84040322110
182 91770818566
183 100190028019
184 109357425938
185 119337396894
186 130199764688
187 142020095153
188 154880303858
189 168869015081
190 184082259776
191 200623905335
192 218606450772
193 238151540797
194 259390877564
195 282466826383
196 307533462810
197 334757291014
198 364318438446
199 396411507219
200 431246944338
201 469052039596
202 510072498804
203 554573618844
204 602842084907
205 655187353301
206 711943712349
207 773471896717
208 840161452897
209 912432629467
210 990739081193
211 1075570081101
212 1167453620972
213 1266958984526
214 1374700304179
215 1491339560717
216 1617590650671
217 1754222881076
218 1902065630902
219 2062012404072
220 2235026174023
221 2422144090543
222 2624483591860
223 2843247867938
224 3079732861838
225 3335333588730
226 3611552157287
227 3910005085110
228 4232432470465
229 4580706456515
230 4956841730501
231 5363005290193
232 5801528463962
233 6274918185954
234 6785870734289
235 7337284741474
236 7932276909500
237 8574196989453
238 9266645757549
239 10013492267106
240 10818894383377
241 11687318642339
242 12623563721271
243 13632783257999
244 14720512674768
245 15892695402210
246 17155713500544
247 18516417781708
248 19982162778177
249 21560841292168
250 23260924323201
251 25091500694353
252 27062322598648
253 29183851027002
254 31467307733525
255 33924727251950
256 36569016173320
257 39414012699618
258 42474554207239
259 45766545398912
260 49307035317096
261 53114295255726
262 57207906524848
263 61608849504302
264 66339603589666
265 71424248936374
266 76888580274410
267 82760223049865
268 89068763000838
269 95845878703478
270 103125488998577
271 110943904194869
272 119339993790373
273 128355358828023
274 138034522653238
275 148425127330550
276 159578150479586
277 171548129019287
278 184393405611048
279 198176383362043
280 212963805839643
281 228827046935755
282 245842428862363
283 264091551899924
284 283661655459244
285 304645992977514
286 327144241758558
287 351262929072304
288 377115897145685
289 404824787271891
290 434519567259518
291 466339081152158
292 500431647348365
293 536955682633744
294 576080380144045
295 617986417491750
296 662866725049855
297 710927289108679
298 762388022251695
299 817483674014585
300 876464816518133
301 939598876644669
302 1007171251909515
303 1079486479838021
304 1156869500906132
305 1239666982944253
306 1328248749978673
307 1423009281688572
308 1524369329519850
309 1632777613613107
310 1748712650186597
311 1872684671347182
312 2005237690606096
313 2146951674107405
314 2298444874681316
315 2460376286440706
316 2633448281500520
317 2818409384072441
318 3016057248056791
319 3227241791184676
320 3452868556637042
321 3693902252635540
322 3951370546497869
323 4226368060915654
324 4520060654639935
325 4833689932916584
326 5168578075894121
327 5526132927554948
328 5907853440343301
329 6315335415069293
330 6750277638418414
331 7214488355072882
332 7709892184385415
333 8238537415643327
334 8802603800581832
335 9404410774059887
336 10046426230581326
337 10731275784945887
338 11461752654338061
339 12240828087120178
340 13071662486610268
341 13957617151968166
342 14902266795897148
343 15909412758775867
344 16983097091145894
345 18127617421293716
346 19347542793720209
347 20647730392314979
348 22033343348545151
349 23509869546362467
350 25083141639706742
351 26759358191895410
352 28545106170378957
353 30447384703801865
354 32473630353371859
355 34631743804188608
356 36930118248444862
357 39377669364675595
358 41983867187402007
359 44758769770124460
360 47713058959734682
361 50858078185463707
362 54205872606006380
363 57769231518116715
364 61561733399033038
365 65597793486732008
366 69892714300878829
367 74462739011025298
368 79325108087879052
369 84498119147064236
370 90001190458116136
371 95854928031940890
372 102081196798871559
373 108703195796816835
374 115745537924280383
375 123234334184808815
376 131197283025299211
377 139663764703317313
378 148664941336900344
379 158233862583892044
380 168405577659663258
381 179217253653636593
382 190708300915229060
383 202920505485392260
384 215898169410750396
385 229688258936717923
386 244340561488761597
387 259907851460880086
388 276446065800793891
389 294014489437190345
390 312675951625150979
391 332497033287383859
392 353548286521727164
393 375904466388726541
394 399644776254604117
395 424853126844881546
396 451618410397377101
397 480034790119415369
398 510202006461653412
399 542225700468862459
400 576217755857350170
401 612296660142467854
402 650587886614758744
403 691224297562298687
404 734346570700372974
405 780103649288870921
406 828653218078795370
407 880162205661960149
408 934807315561177426
409 992775586743580663
410 1054264986108613379
411 1119485033754529036
412 1188657463812198441
413 1262016921786563287
414 1339811701452913112
415 1422304522404988772
416 1509773351584922161
417 1602512270066660208
418 1700832388735862766
419 1805062814333964582
420 1915551669850797933
421 2032667170956774067
422 2156798762833086126
423 2288358319339585024
424 2427781409292402461
425 2575528632069306874
426 2732087027766694112
427 2897971564441418253
428 3073726708156774151
429 3259928078716406003
430 3457184197352881610
431 3666138329646233358
432 3887470430537932437
433 4121899195156899350
434 4370184222979906774
435 4633128299533271610
436 4911579803883597566
437 5206435246670944146
438 5518641947726360915
439 5849200858640784903
440 6199169540198991002
441 6569665300726607036
442 6961868506226049552
443 7377026069107174247
444 7816455127442720134
445 8281546922402512984
446 8773770886954143291
447 9294678954424542107
448 9845910101287208489
449 10429195133814380341
450 11046361734359042245
451 11699339778072482015
452 12390166937360196533
453 13120994586173980474
454 13894094023138735895
455 14711863027045537437
456 15576832765569591670
457 16491675072341482467
458 17459210115273854553
459 18482414473039383084
460 19564429644854400446
461 20708571012422749890
462 21918337281665693063
463 23197420425269881631
464 24549716156394641239
465 25979334956978647884
466 27490613693978713656
467 29088127849646575198
468 30776704402459894529
469 32561435387771842535
470 34447692178403245660
471 36441140517510988057
472 38547756347929530763
473 40773842473934853295
474 43126046103989107197
475 45611377314421995717
476 48237228487399181869
477 51011394767558125743
478 53942095595936499759
479 57037997370462186723
480 60308237297421184568
481 63762448488582724067
482 67410786374760365529
483 71263956496458505175
484 75333243749383764499
485 79630543152061610293
486 84168392221023715565
487 88960005028092297762
488 94019308033670088711
489 99360977778596481832
490 105000480537765043542
491 110954114026925738148
492 117239051276062137803
493 123873386770554019108
494 130876184984713141151
495 138267531419688100389
496 146068586282637288044
497 154301640931054727126
498 162990177232662121030
499 172158929977868222650
500 181833952510049020822
501 192042685725095231209
502 202814030621790506592
503 214178424570379046977
504 226167921498787090401
505 238816276181396755705
506 252159032849489574847
507 266233618327563804092
508 281079439936233785386
509 296737988387167383308
510 313252945934462695830
511 330670300031327174144
512 349038462782465327623
513 368408396466786905739
514 388833745449400305574
515 410370974785830177701
516 433079515868756053138
517 457021919451387629926
518 482264016432153826613
519 508875086769097876724
520 536928036946397471441
521 566499586399088637017
522 597670463359809615957
523 630525610575092461830
524 665154401400430188910
525 701650866767193097505
526 740113933580454978368
527 780647675090851222673
528 823361573854174324774
529 868370797876838409131
530 915796490620843932707
531 965766075526789729657
532 1018413575794298666380
533 1073879950144755797606
534 1132313445377787590474
535 1193869966519265847826
536 1258713465451266485723
537 1327016348901773740146
538 1398959906771187586618
539 1474734761761247085274
540 1554541341378365050909
541 1638590373373400118466
542 1727103405793907782964
543 1820313352816679580927
544 1918465067650658777775
545 2021815943794099072221
546 2130636546061003218065
547 2245211272788048910241
548 2365839050773930022726
549 2492834064501970198926
550 2626526521347929442186
551 2767263454476999083065
552 2915409565296183942062
553 3071348107334005770687
554 3235481813593646377228
555 3408233869435551105935
556 3590048933232676485656
557 3781394207056174422340
558 3982760559850460981781
559 4194663705576623160350
560 4417645439019339104845
561 4652274931978581984028
562 4899150092799926185944
563 5158898992230200024736
564 5432181358835394848513
565 5719690147258418472578
566 6022153182863436226472
567 6340334886362912470892
568 6675038082313204283154
569 7027105895423628830382
570 7397423738935894182490
571 7786921399400778770657
572 8196575222514897151680
573 8627410404762574227826
574 9080503395969807032490
575 9556984417973028024706
576 10058040104995445399044
577 10584916271434643910416
578 11138920813185541159680
579 11721426748750565026801
580 12333875406842243842259
581 12977779767329858562659
582 13654727962870728799732
583 14366386948733991114945
584 15114506348852120824454
585 15900922486325811384625
586 16727562607176948864377
587 17596449306360288708222
588 18509705165658723208922
589 19469557613331223002454
590 20478344016045654151177
591 21538517013904168228569
592 22652650110084967422002
593 23823443526934265620076
594 25053730341115739055001
595 26346482910773000279979
596 27704819608496180953979
597 29132011874274094743671
598 30631491603516368467454
599 32206858885666714472399
600 33861890109904402460019
601 35600546454919012710287
602 37426982780798439821996
603 39345556941614535941448
604 41360839538431410295862
605 43477624133067811129766
606 45700937944178552183934
607 48036053047894664027297
608 50488498106596121194425
609 53064070650140779151436
610 55768849935316556620113
611 58609210410116077761882
612 61591835810994789988665
613 64723733922196380977432
614 68012252027919413613649
615 71465093089121360050152
616 75090332678585574717612
617 78896436709008043165911
618 82892279990841095398150
619 87087165657882308405951
620 91490845500740834785870
621 96113541249695669322511
622 100965966850782040967591
623 106059351780468117168565
624 111405465446798549975896
625 117016642726565008546987
626 122905810690787066516548
627 129086516572642993754136
628 135572957034939984083914
629 142380008796258330432738
630 149523260678099987945769
631 157019047137623739100551
632 164884483354011799100021
633 173137501938990660735895
634 181796891345781121339756
635 190882336053477641934369
636 200414458607923385852994
637 210414863603143009686175
638 220906183691802071091976
639 231912127716453271245605
640 243457531058106273266151
641 255568408302272083393108
642 268272008327810598069531
643 281596871927877106058695
644 295572892077876180022464
645 310231376969683969047058
646 325605115937484769730929
647 341728448405340954974885
648 358637335993212497309464
649 376369437923374889931217
650 394964189876337091379694
651 414462886451094918192620
652 434908767392311258600817
653 456347107753294962744724
654 478825312172060518788342
655 502393013444627666988078
656 527102175588840069814487
657 553007201599509690130913
658 580165046105583755020040
659 608635333148267748180635
660 638480479309763694754970
661 669765822431292724761196
662 702559756170703060798657
663 736933870659816822698804
664 772963099534284752580174
665 810725873619488018240844
666 850304281569708882163222
667 891784237769562225280588
668 935255657821519735231887
669 980812641956218015303083
670 1028553666718337306906519
671 1078581785294882885623207
672 1131004836870158560498228
673 1185935665407058590126058
674 1243492348273238759496624
675 1303798435147470048367619
676 1366983197662015217290695
677 1433181890255141108225772
678 1502536022730154325442161
679 1575193645037285477001834
680 1651309644818906735191935
681 1731046058280316442498465
682 1814572394974528476526944
683 1902065977113223303662773
684 1993712294044438658354299
685 2089705372563440306574352
686 2190248163754038285491453
687 2295552947085807174674453
688 2405841752526101075791744
689 2521346801456480917105009
690 2642310967219430748964392
691 2768988256154721583538816
692 2901644310024105229001801
693 3040556930759496826767303
694 3186016628512452105526692
695 3338327194022475547708060
696 3497806296367945934602460
697 3664786107206712201477427
698 3839613952663568426688155
699 4022652994068925179729203
700 4214282938807384675575985
701 4414900782586208785227116
702 4624921584492648933594183
703 4844779276264921821442281
704 5074927507265569398124821
705 5315840526706679501436638
706 5568014104745790208471029
707 5831966494137384352981733
708 6108239434200071020957522
709 6397399198931438452935496
710 6700037691184085646351348
711 7016773584894528321846920
712 7348253517445060557440098
713 7695153334323680403993817
714 8058179388343009596674335
715 8438069895771587060064143
716 8835596351834794375286732
717 9251565008143175457786156
718 9686818414718520683710137
719 10142237029397328634848464
720 10618740897513323670958611
721 11117291404879431835543555
722 11638893107221926882776710
723 12184595639348467296862522
724 12755495707475151904339607
725 13352739168277885404856091
726 13977523198388771804054075
727 14631098558210515376510856
728 15314771954090253326551398
729 16029908503059624367333432
730 16777934304530421042400130
731 17560339123514776661447934
732 18378679190136649246900716
733 19234580120396388161906574
734 20129739963364512789835320
735 21065932380192571140813770
736 22045009960561191279195038
737 23068907682415293564506102
738 24139646521088058038929241
739 25259337214164731187978283
740 26430184188709964446853974
741 27654489657753143394143894
742 28934657893221489146357652
743 30273199682804532980201115
744 31672736978553474867266959
745 33136007745337732602980710
746 34665871017627509658651009
747 36265312173417062199820178
748 37937448434478670031006944
749 39685534602512474346974304
750 41512969041163840187883637
751 43423299914286800432479799
752 45420231691272363432550968
753 47507631930701738473412067
754 49689538354061257707139495
755 51970166221734264756588344
756 54353916024001455669212802
757 56845381500299948814356807
758 59449358000550300218013837
759 62170851202923099879667503
760 65015086203021945711437631
761 67987516990069237398559445
762 71093836326336392381852066
763 74339986046720850782810727
764 77732167796081476564103373
765 81276854222660051784371943
766 84980800646684294717534082
767 88851057224023792731422878
768 92894981625601234595633140
769 97120252254102072717762242
770 101534882020425148537622593
771 106147232703227655881203857
772 110966029915891193859426450
773 116000378706222335591148106
774 121259779815254499724606992
775 126754146622586621300414726
776 132493822806833954049088755
777 138489600750923779196715871
778 144752740723202119581988374
779 151294990866570970107706794
780 158128608029209939835352764
781 165266379471793401493692538
782 172721645487557865774594181
783 180508322973043729957872182
784 188640929988897241644801349
785 197134611351709300725036324
786 206005165299557018076827782
787 215269071275635932398088571
788 224943518876197979312082605
789 235046438010874125036208696
790 245596530325436782453894328
791 256613301939074262900152832
792 268117097550386732053797436
793 280129135968495991174407923
794 292671547127972578090567557
795 305767410648645636949617397
796 319440796003860116112077127
797 333716804363301357310316411
798 348621612179209271168797707
799 364182516587568945018984802
800 380427982698785960149074412
801 397387692855345325942937192
802 415092597937111237368197033
803 433574970798159636929492935
804 452868461922449682765498726
805 473008157389138749654359179
806 494030639242035980380903329
807 515974048361472833394132087
808 538878149940857798168237726
809 562784401674273603599490385
810 587736024765786104479765677
811 613778077875557536606582163
812 640957534122515495776674092
813 669323361268111416177793498
814 698926605210736486021419082
815 729820476925532925689892115
816 762060442989778077309218721
817 795704319839607218544543905
818 830812371909718103133770423
819 867447413813740504066247451
820 905674916729303423907693721
821 945563119158360666093916176
822 987183142240194596375500776
823 1030609109801572476739415770
824 1075918273335939010973946115
825 1123191142111151616597634279
826 1172511618613267849779063671
827 1223967139542130673136126137
828 1277648822583140750067389756
829 1333651619188503190558307299
830 1392074473610570832489683995
831 1453020488439518739091835449
832 1516597096907664945718376913
833 1582916242233135898942709920
834 1652094564286459842918502766
835 1724253593874886490076875776
836 1799519954950983916026316645
837 1878025575064175960767324903
838 1959907904386572066303843230
839 2045310143657521764728081770
840 2134381481405024267494152009
841 2227277340816248005624801559
842 2324159636644202035862351258
843 2425197042552851815792953189
844 2530565269318933124663980593
845 2640447354325183111990422104
846 2755033962796934914945661143
847 2874523701251797384572410470
848 2999123443650734184750780189
849 3129048670758044155008232014
850 3264523823237809549869663370
851 3405782669035089478914709898
852 3553068685611787546557393763
853 3706635457629475576366871767
854 3866747090694817739538518141
855 4033678641807362726833066564
856 4207716567174678137723131759
857 4389159188085833142975771603
858 4578317175561429693375545302
859 4775514054526471749485864518
860 4981086728281698510903487458
861 5195386024079314321739051441
862 5418777260640693192369516997
863 5651640838486332535997457900
864 5894372853982463964996811499
865 6147385738044001302849770300
866 6411108920470320138541586244
867 6685989520928411117833583793
868 6972493067637651968050453941
869 7271104244851481870778203111
870 7582327670274076799539803083
871 7906688703594385454782496427
872 8244734287366053263063336057
873 8597033821509494644238224514
874 8964180072762153407030241627
875 9346790120454463927636301665
876 9745506340042695956806755421
877 10160997425885367541945138557
878 10593959454807771196158684188
879 11045116992058999695777753700
880 11515224241328231721496738403
881 12005066240551552803648211989
882 12515460105307821292793076955
883 13047256321671638115846052936
884 13601340090463947350094309318
885 14178632724915764572343553897
886 14780093103838634140109192216
887 15406719182476223806141067999
888 16059549563295637540472438363
889 16739665129064119981367761651
890 17448190740647531736064665969
891 18186297002060834470109688602
892 18955202095398564067585272696
893 19756173688374415319006689502
894 20590530917304372461990614707
895 21459646448476807965138738745
896 22364948620966432901286164850
897 23307923674066412687317381294
898 24290118062635195191537313700
899 25313140863781115654985139983
900 26378666278439517382410670498
901 27488436231533424815488791120
902 28644263074550640734471857079
903 29848032394516962528158119816
904 31101705933497981641805636758
905 32407324622920080369709462123
906 33767011737165774832401970340
907 35182976171068891395628474376
908 36657515846112257793775065516
909 38193021250314043092343132742
910 39791979116979694785640691426
911 41456976247693984129813034171
912 43190703485133137871782048967
913 44995959841489777278077137025
914 46875656788524615306812777024
915 48832822715487935459572261884
916 50870607561392061604760279486
917 52992287628362666629381959915
918 55201270583053191324383431853
919 57501100653372177531464386803
920 59895464028049358504374649715
921 62388194466852203327679438275
922 64983279129561746784060420231
923 67684864632124244743434940139
924 70497263338715015739990453274
925 73424959898782040553745989823
926 76472618038481106947139548028
927 79645087616270770498792762552
928 82947411952805848224660251249
929 86384835445651819771826601002
930 89962811479741159054029652229
931 93687010644905494408665782317
932 97563329272246463931070641133
933 101597898301552419226433092792
934 105797092492429695005119010028
935 110167539992295216695587054819
936 114716132274873821556503244288
937 119450034463358022907683034292
938 124376696052922213744225624917
939 129503862047836677881895355486
940 134839584529001524895151711202
941 140392234668315973883316633985
942 146170515206916666823599554236
943 152183473414959072528983185235
944 158440514551281054872575151292
945 164951415841976496371454749766
946 171726340997622126536224730762
947 178775855289641572594437945286
948 186110941207059899727998346078
949 193743014715698706495046398112
950 201683942142689102868990535953
951 209946057710036791966478290167
952 218542181741863067024599558804
953 227485639570866994638780319971
954 236790281170510607842004003197
955 246470501540419756701349821811
956 256541261873521751932980219117
957 267018111534506276445206148593
958 277917210880301800425037064032
959 289255354954405118275401531335
960 301049998088090387668708410445
961 313319279442755409536216736994
962 326082049528940798382699845817
963 339357897738881393081370182262
964 353167180930822914109862704949
965 367531053104759747593662164558
966 382471496210726215793680203581
967 398011352132303071791686534743
968 414174355889587853405449203261
969 430985170107521477759463163531
970 448469420797168921287661353016
971 466653734499318382147696901460
972 485565776841596092780371133164
973 505234292562192360092286524459
974 525689147055263866136885948597
975 546961369495117239437582065055
976 569083197598395105981312286875
977 592088124085677789188320853360
978 616010944906187559806912760876
979 640887809291637451585123530616
980 666756271707709495028580968453
981 693655345774177472926909045732
982 721625560227313653539349976494
983 750709017000937195249294409613
984 780949451505281094211552005479
985 812392295185774551425188494105
986 845084740446865911715324386954
987 879075808029147876213411910641
988 914416416931299369044882493342
989 951159456971727377374832656408
990 989359864088285576330631335138
991 1029074698478064867386902582875
992 1070363225683002858862958759351
993 1113287000730945227762095399821
994 1157909955445821073062338986414
995 1204298489044767402422279650040
996 1252521562144364557948136583765
997 1302650794302625473880685025371
998 1354760565228027493033630357347
999 1408928119791687051653316760357
1000 1465233676983765783079119209223