1 0
2 0
3 0
4 1
5 1
6 1
7 2
8 4
9 4
10 5
11 7
12 10
13 12
14 14
15 18
16 24
17 28
18 33
19 41
20 50
21 59
22 70
23 84
24 100
25 117
26 137
27 161
28 188
29 219
30 254
31 295
32 341
33 393
34 453
35 520
36 595
37 682
38 780
39 889
40 1011
41 1150
42 1307
43 1481
44 1673
45 1893
46 2140
47 2411
48 2713
49 3053
50 3433
51 3851
52 4313
53 4833
54 5411
55 6045
56 6746
57 7529
58 8396
59 9346
60 10394
61 11559
62 12844
63 14252
64 15802
65 17515
66 19401
67 21465
68 23730
69 26227
70 28967
71 31962
72 35245
73 38848
74 42793
75 47102
76 51812
77 56969
78 62605
79 68749
80 75455
81 82779
82 90764
83 99459
84 108933
85 119255
86 130489
87 142707
88 155994
89 170442
90 186142
91 203190
92 221701
93 241797
94 263595
95 287233
96 312866
97 340640
98 370725
99 403310
100 438585
101 476755
102 518047
103 562704
104 610985
105 663160
106 719521
107 780401
108 846141
109 917082
110 993624
111 1076207
112 1165263
113 1261254
114 1364705
115 1476180
116 1596257
117 1725542
118 1864708
119 2014503
120 2175685
121 2349026
122 2535421
123 2735843
124 2951255
125 3182688
126 3431301
127 3698331
128 3985051
129 4292799
130 4623052
131 4977427
132 5357570
133 5765192
134 6202222
135 6670734
136 7172827
137 7710742
138 8286952
139 8904087
140 9564878
141 10272208
142 11029217
143 11839295
144 12705944
145 13632836
146 14624014
147 15683797
148 16816630
149 18027251
150 19320810
151 20702759
152 22178809
153 23755010
154 25437860
155 27234322
156 29151661
157 31197528
158 33380215
159 35708527
160 38191639
161 40839318
162 43662041
163 46670884
164 49877516
165 53294295
166 56934392
167 60811825
168 64941326
169 69338445
170 74019827
171 79003103
172 84306774
173 89950490
174 95955163
175 102342867
176 109136927
177 116362032
178 124044335
179 132211575
180 140893003
181 150119491
182 159923861
183 170340800
184 181406830
185 193160674
186 205643313
187 218897971
188 232970362
189 247908802
190 263764313
191 280590856
192 298445393
193 317388035
194 337482380
195 358795543
196 381398287
197 405365463
198 430776071
199 457713344
200 486265264
201 516524720
202 548589563
203 582563100
204 618554361
205 656678292
206 697056178
207 739815840
208 785092041
209 833027080
210 883770831
211 937481077
212 994324417
213 1054476492
214 1118122094
215 1185456003
216 1256683607
217 1332021237
218 1411696707
219 1495949853
220 1585033361
221 1679213587
222 1778770717
223 1883999474
224 1995210606
225 2112731326
226 2236905535
227 2368095259
228 2506681811
229 2653066361
230 2807670842
231 2970938995
232 3143337841
233 3325358982
234 3517518992
235 3720360817
236 3934456107
237 4160406049
238 4398842030
239 4650427923
240 4915862099
241 5195878554
242 5491248430
243 5802781972
244 6131330976
245 6477790891
246 6843101887
247 7228251280
248 7634277169
249 8062270103
250 8513374551
251 8988792609
252 9489787323
253 10017684832
254 10573877134
255 11159825460
256 11777064271
257 12427204827
258 13111937510
259 13833035988
260 14592362842
261 15391872727
262 16233615517
263 17119742184
264 18052510196
265 19034287602
266 20067557917
267 21154925887
268 22299123962
269 23503018319
270 24769613636
271 26102060017
272 27503661725
273 28977883132
274 30528354735
275 32158882599
276 33873457119
277 35676260413
278 37571675034
279 39564293540
280 41658928985
281 43860625205
282 46174665772
283 48606585546
284 51162184350
285 53847537654
286 56669007731
287 59633258741
288 62747270994
289 66018354091
290 69454161965
291 73062708803
292 76852386071
293 80831979881
294 85010687182
295 89398134815
296 94004401156
297 98840034911
298 103916074846
299 109244074051
300 114836123245
301 120704873493
302 126863561839
303 133326037594
304 140106790028
305 147220977529
306 154684455772
307 162513809103
308 170726385153
309 179340327001
310 188374607259
311 197849067142
312 207784454555
313 218202462795
314 229125773340
315 240578099174
316 252584229962
317 265170080363
318 278362738044
319 292190515066
320 306683003527
321 321871129807
322 337787211979
323 354465022914
324 371939852534
325 390248572547
326 409429707151
327 429523503981
328 450572007804
329 472619139934
330 495710778351
331 519894841646
332 545221378696
333 571742658756
334 599513266652
335 628590204606
336 659032993768
337 690903781156
338 724267455126
339 759191761031
340 795747421204
341 834008264284
342 874051357100
343 915957141148
344 959809577049
345 1005696292470
346 1053708737862
347 1103942350456
348 1156496719313
349 1211475759902
350 1268987901087
351 1329146272698
352 1392068899999
353 1457878912853
354 1526704760173
355 1598680430717
356 1673945685408
357 1752646297576
358 1834934305307
359 1920968274626
360 2010913566418
361 2104942618943
362 2203235248180
363 2305978950382
364 2413369215712
365 2525609864073
366 2642913390722
367 2765501321437
368 2893604584797
369 3027463899051
370 3167330177432
371 3313464948874
372 3466140787226
373 3625641764743
374 3792263931327
375 3966315799690
376 4148118848320
377 4338008057287
378 4536332460898
379 4743455715663
380 4959756694227
381 5185630103608
382 5421487131470
383 5667756115610
384 5924883229873
385 6193333206979
386 6473590098727
387 6766158049245
388 7071562096956
389 7390349024257
390 7723088235252
391 8070372658846
392 8432819691344
393 8811072177906
394 9205799436314
395 9617698316975
396 10047494292515
397 10495942602355
398 10963829452099
399 11451973238665
400 11961225821225
401 12492473861275
402 13046640208099
403 13624685326443
404 14227608784513
405 14856450802373
406 15512293864307
407 16196264388495
408 16909534447387
409 17653323569330
410 18428900621211
411 19237585738261
412 20080752326310
413 20959829164182
414 21876302578177
415 22831718686356
416 23827685734835
417 24865876526568
418 25948030947099
419 27075958580766
420 28251541411127
421 29476736641176
422 30753579633770
423 32084186934554
424 33470759408004
425 34915585519106
426 36421044728392
427 37989611000252
428 39623856451775
429 41326455141850
430 43100187007322
431 44947941941547
432 46872724008962
433 48877655836683
434 50965983185243
435 53141079657917
436 55406451585532
437 57765743123801
438 60222741527360
439 62781382604902
440 65445756388182
441 68220113013097
442 71108868823717
443 74116612698594
444 77248112592745
445 80508322341961
446 83902388734725
447 87435658810481
448 91113687427935
449 94942245144895
450 98927326371886
451 103075157810777
452 107392207217961
453 111885192487777
454 116561091073154
455 121427149750705
456 126490894722672
457 131760142108490
458 137243008837339
459 142947923901392
460 148883640022248
461 155059245776262
462 161484178140699
463 168168235483517
464 175121591043315
465 182354806892443
466 189878848409827
467 197705099282163
468 205845377025924
469 214311949089093
470 223117549553746
471 232275396404108
472 241799209422362
473 251703228763232
474 262002234171725
475 272711564883347
476 283847140262509
477 295425481168804
478 307463732091833
479 319979684090531
480 332991798529924
481 346519231681800
482 360581860225466
483 375200307622227
484 390395971438685
485 406191051676774
486 422608580080953
487 439672450485997
488 457407450272402
489 475839292916279
490 494994651695649
491 514901194612480
492 535587620526459
493 557083696577166
494 579420296951739
495 602629442988487
496 626744344707221
497 651799443834333
498 677830458305781
499 704874428343013
500 732969764185852
501 762156295467936
502 792475322325913
503 823969668335743
504 856683735277342
505 890663559819762
506 925956872214468
507 962613157011483
508 1000683715912266
509 1040221732842009
510 1081282341245643
511 1123922693746655
512 1168202034275494
513 1214181772656992
514 1261925561789049
515 1311499377551707
516 1362971601459890
517 1416413106175060
518 1471897344005919
519 1529500438449812
520 1589301278920713
521 1651381618769836
522 1715826176637073
523 1782722741330693
524 1852162280376033
525 1924239052234983
526 1999050722384448
527 2076698483456447
528 2157287179474409
529 2240925434336150
530 2327725784734791
531 2417804817620599
532 2511283312397065
533 2608286387994680
534 2708943654910192
535 2813389372489641
536 2921762611644335
537 3034207423028127
538 3150873010943051
539 3271913913259766
540 3397490187426486
541 3527767602770699
542 3662917839368953
543 3803118693663098
544 3948554291083387
545 4099415305881715
546 4255899188337025
547 4418210399718274
548 4586560655268093
549 4761169175283522
550 4942262944669517
551 5130076981367080
552 5324854613792240
553 5526847767573404
554 5736317261979846
555 5953533116325283
556 6178774866706610
557 6412331893373093
558 6654503758995787
559 6905600558368893
560 7165943279914966
561 7435864179152323
562 7715707164651895
563 8005828197041313
564 8306595701293128
565 8618390992711106
566 8941608717169539
567 9276657306040644
568 9623959446315024
569 9983952566350007
570 10357089337673789
571 10743838193574136
572 11144683865005485
573 11560127934106233
574 11990689406061608
575 12436905300086968
576 12899331259922644
577 13378542184443143
578 13875132879164270
579 14389718729293761
580 14922936395044701
581 15475444529855323
582 16047924522169076
583 16641081261777063
584 17255643931491563
585 17892366824652255
586 18552030189491558
587 19235441101431110
588 19943434363937780
589 20676873438820052
590 21436651407067752
591 22223691961180900
592 23038950430016373
593 23883414837106022
594 24758106993425095
595 25664083625989187
596 26602437543392488
597 27574298839108221
598 28580836133983294
599 29623257859413470
600 30702813582181794
601 31820795372247616
602 32978539215038671
603 34177426469616221
604 35418885374190232
605 36704392600393356
606 38035474857755572
607 39413710550282581
608 40840731486748447
609 42318224645999452
610 43847933999272238
611 45431662391587872
612 47071273483729767
613 48768693756683086
614 50525914580717056
615 52344994351086629
616 54228060692473343
617 56177312734234244
618 58195023458564812
619 60283542124208238
620 62445296768041930
621 64682796786538810
622 66998635599905890
623 69395493401771683
624 71876139996695102
625 74443437728224357
626 77100344500574046
627 79849916896756017
628 82695313396207600
629 85639797694935309
630 88686742131226133
631 91839631220583085
632 95102065303246525
633 98477764307319425
634 101970571631423576
635 105584458150895356
636 109323526350903323
637 113192014590432923
638 117194301501454910
639 121334910527335786
640 125618514604851000
641 130049940994176306
642 134634176261257556
643 139376371417653157
644 144281847222681989
645 149356099652368402
646 154604805540690804
647 160033828398745902
648 165649224416806401
649 171457248654947201
650 177464361428319474
651 183677234892864577
652 190102759837701467
653 196748052690495451
654 203620462742119980
655 210727579597732533
656 218077240861185856
657 225677540059375071
658 233536834814252823
659 241663755270379861
660 250067212785273418
661 258756408890678529
662 267740844533322477
663 277030329603407888
664 286634992759726657
665 296565291560440962
666 306832022908553982
667 317446333822040913
668 328419732538521495
669 339764099964074527
670 351491701477056635
671 363615199097972323
672 376147664035905169
673 389102589623094101
674 402493904649707535
675 416335987110559075
676 430643678376385839
677 445432297802599695
678 460717657788367073
679 476516079299998302
680 492844407872704774
681 509720030104571796
682 527160890658010043
683 545185509784207693
684 563813001385691721
685 583063091633450386
686 602956138155577282
687 623513149814112969
688 644755807087966464
689 666706483080259228
690 689388265168359874
691 712824977316224286
692 737041203068977286
693 762062309249575984
694 787914470378990756
695 814624693841722308
696 842220845818248136
697 870731678007678613
698 900186855164476403
699 930616983472865901
700 962053639784202213
701 994529401743260854
702 1028077878829332730
703 1062733744339650666
704 1098532768343327577
705 1135511851634069433
706 1173709060711752147
707 1213163663823515809
708 1253916168095088994
709 1296008357785177153
710 1339483333696429546
711 1384385553776390197
712 1430760874944042597
713 1478656596178568074
714 1528121502906897410
715 1579205912728667897
716 1631961722518303662
717 1686442456944284387
718 1742703318447798103
719 1800801238723808890
720 1860794931748035020
721 1922744948396008426
722 1986713732701245632
723 2052765679799655343
724 2120967195610233865
725 2191386758303547815
726 2264094981609562280
727 2339164680018931959
728 2416670935933583031
729 2496691168823138991
730 2579305206446297482
731 2664595358197490304
732 2752646490640188463
733 2843546105291607027
734 2937384418724704505
735 3034254445053806772
736 3134252080874031866
737 3237476192726736273
738 3344028707163475840
739 3454014703484234106
740 3567542509228191470
741 3684723798496570446
742 3805673693190232024
743 3930510867246494575
744 4059357653961441520
745 4192340156488313750
746 4329588361604164721
747 4471236256837914430
748 4617421951057969775
749 4768287798620430257
750 4923980527179557700
751 5084651369266392808
752 5250456197744993087
753 5421555665257788151
754 5598115347775508473
755 5780305892369760503
756 5968303169329149154
757 6162288428745405571
758 6362448461698239821
759 6568975766169379285
760 6782068717822812410
761 7001931745792202249
762 7228775513617740174
763 7462817105480191847
764 7704280217884890944
765 7953395356951530345
766 8210400041470707339
767 8475539011891962988
768 8749064445412278184
769 9031236177341154604
770 9322321928921702107
771 9622597541790036814
772 9932347219263824970
773 10251863774656245985
774 10581448886813964765
775 10921413363084924051
776 11272077409928632775
777 11633770911386216401
778 12006833715634218814
779 12391615929851562567
780 12788478223635178251
781 13197792141209105836
782 13619940422676683392
783 14055317334569972645
784 14504329009961652710
785 14967393798412091148
786 15444942626028154730
787 15937419365919898943
788 16445281219350609922
789 16968999107882337997
790 17509058076828052120
791 18065957710329239902
792 18640212558386414298
793 19232352576182107727
794 19842923576042948588
795 20472487692394304670
796 21121623860075377620
797 21790928306392893880
798 22481015057297669225
799 23192516458081088917
800 23926083709001169734
801 24682387416257402360
802 25462118158745722416
803 26265987071035819843
804 27094726443025033948
805 27949090336738986210
806 28829855220759260166
807 29737820622768644904
808 30673809800723210281
809 31638670433174528091
810 32633275329274804380
811 33658523159014766755
812 34715339204261158406
813 35804676131174188296
814 36927514784601806439
815 38084865005062914564
816 39277766468948242941
817 40507289552588594974
818 41774536220854770540
819 43080640940968312924
820 44426771622226711928
821 45814130582365898073
822 47243955541297056606
823 48717520642977711751
824 50236137506199898203
825 51801156305097198917
826 53413966880194968809
827 55075999880849330435
828 56788727939943335150
829 58553666881736452747
830 60372376963784404705
831 62246464153867598237
832 64177581442898503407
833 66167430194804540000
834 68217761534403923824
835 70330377774322758058
836 72507133882032367169
837 74749938988112342997
838 77060757936875578715
839 79441612880521077006
840 81894584918011503196
841 84421815779909355908
842 87025509560435154516
843 89707934498041128975
844 92471424805836067315
845 95318382553232770939
846 98251279600219788683
847 101272659585700629851
848 104385139971384923721
849 107591414142752739180
850 110894253568655391426
851 114296510021156825952
852 117801117857262183241
853 121411096364229354897
854 125129552170200827100
855 128959681721935338328
856 132904773831474497747
857 136968212293628311466
858 141153478576206729578
859 145464154584980289872
860 149903925505408415393
861 154476582723224708249
862 159186026826026090570
863 164036270688068725456
864 169031442640531500016
865 174175789729573640501
866 179473681064570912108
867 184929611258973695283
868 190548203966303833497
869 196334215513873605741
870 202292538636871167515
871 208428206315532222479
872 214746395718192337249
873 221252432253084235687
874 227951793731822801565
875 234850114647597417601
876 241953190571169864214
877 249266982667864136137
878 256797622338814806387
879 264551415989822016466
880 272534849931258893835
881 280754595412567582605
882 289217513794965460026
883 297930661866084756640
884 306901297300369281836
885 316136884269147933382
886 325645099204411312492
887 335433836720422860612
888 345511215697402624628
889 355885585531639974886
890 366565532556502322118
891 377559886638919037753
892 388877727956049856353
893 400528393956969831924
894 412521486514321529136
895 424866879271022081149
896 437574725187248077609
897 450655464293052577893
898 464119831652113323326
899 477978865542254433051
900 492243915858528559534
901 506926652744805195170
902 522039075459962800308
903 537593521484936177824
904 553602675877044035478
905 570079580878188282735
906 587037645783680288619
907 604490657078633759680
908 622452788849046210078
909 640938613474870210339
910 659963112612571752252
911 679541688474867689741
912 699690175415530271542
913 720424851827359971787
914 741762452361635523021
915 763720180477560050293
916 786315721330454037544
917 809567255007671603761
918 833493470121441209679
919 858113577768080098439
920 883447325863277421637
921 909515013863384916043
922 936337507882919197403
923 963936256218743624445
924 992333305291663041369
925 1021551316016451131654
926 1051613580611612881364
927 1082544039860470474671
928 1114367300835471098129
929 1147108655097920541936
930 1180794097385653359467
931 1215450344801484058948
932 1251104856515614697393
933 1287785853995505451084
934 1325522341777072577226
935 1364344128791435205027
936 1404281850261791160312
937 1445366990185386759357
938 1487631904415929196525
939 1531109844362178034915
940 1575834981318867559165
941 1621842431446524328389
942 1669168281417161770886
943 1717849614743281984923
944 1767924538808060442791
945 1819432212615038022899
946 1872412875276126724997
947 1926907875257217498468
948 1982959700401163084642
949 2040612008748425324578
950 2099909660176195503063
951 2160898748877321264798
952 2223626636700929821017
953 2288141987377193668908
954 2354494801649251047018
955 2422736453335895115466
956 2492919726349245299762
957 2565098852692220904320
958 2639329551461285038924
959 2715669068880576565963
960 2794176219394201199019
961 2874911427844145946214
962 2957936772761981596975
963 3043316030803226776176
964 3131114722353992004649
965 3221400158340271723636
966 3314241488271017195272
967 3409709749546930091365
968 3507877918067722470106
969 3608820960171407336285
970 3712615885940053697284
971 3819341803907314001863
972 3929079977203911909756
973 4041913881178207510897
974 4157929262529900150393
975 4277214199995884001558
976 4399859166628268953700
977 4525957093705587284859
978 4655603436319237647950
979 4788896240678298737347
980 4925936213176927317773
981 5066826791269657438160
982 5211674216201083265533
983 5360587607637581723729
984 5513679040249914737524
985 5671063622296795440680
986 5832859576260769537303
987 5999188321589047067572
988 6170174559593254637758
989 6345946360563431443613
990 6526635253152978837021
991 6712376316092719362253
992 6903308272293673122728
993 7099573585399640645959
994 7301318558852241285417
995 7508693437532630064933
996 7721852512045705341624
997 7940954225714284953293
998 8166161284352427052807
999 8397640768888795070492
1000 8635564250912751310564