1 0
2 0
3 0
4 1
5 1
6 1
7 2
8 2
9 4
10 5
11 5
12 7
13 8
14 11
15 14
16 15
17 19
18 22
19 27
20 33
21 37
22 44
23 50
24 59
25 71
26 79
27 93
28 106
29 120
30 142
31 159
32 181
33 207
34 232
35 267
36 301
37 339
38 383
39 428
40 486
41 544
42 609
43 683
44 758
45 853
46 951
47 1056
48 1180
49 1304
50 1453
51 1616
52 1785
53 1980
54 2185
55 2417
56 2674
57 2947
58 3253
59 3574
60 3939
61 4338
62 4760
63 5236
64 5737
65 6290
66 6908
67 7556
68 8277
69 9049
70 9888
71 10815
72 11804
73 12886
74 14048
75 15308
76 16693
77 18166
78 19782
79 21511
80 23376
81 25425
82 27605
83 29973
84 32530
85 35262
86 38252
87 41450
88 44901
89 48617
90 52604
91 56927
92 61557
93 66548
94 71914
95 77646
96 83869
97 90514
98 97657
99 105343
100 113542
101 122389
102 131874
103 142019
104 152924
105 164561
106 177076
107 190465
108 204802
109 220158
110 236541
111 254125
112 272922
113 292994
114 314508
115 337406
116 361939
117 388155
118 416109
119 445998
120 477849
121 511855
122 548174
123 586872
124 628187
125 672146
126 719072
127 769080
128 822325
129 879111
130 939491
131 1003801
132 1072347
133 1145194
134 1222806
135 1305287
136 1393026
137 1486390
138 1585618
139 1691135
140 1803219
141 1922316
142 2048929
143 2183317
144 2326168
145 2477710
146 2638599
147 2809478
148 2990717
149 3183093
150 3387151
151 3603475
152 3833055
153 4076374
154 4334403
155 4607813
156 4897551
157 5204628
158 5529893
159 5874511
160 6239428
161 6625710
162 7034920
163 7467906
164 7926318
165 8411384
166 8924485
167 9467454
168 10041764
169 10649137
170 11291447
171 11970374
172 12688288
173 13446975
174 14248942
175 15096260
176 15991356
177 16937107
178 17935957
179 18990853
180 20104908
181 21280768
182 22522385
183 23832834
184 25215911
185 26675405
186 28215182
187 29839667
188 31553270
189 33360607
190 35266668
191 37276117
192 39395045
193 41628543
194 43982876
195 46464231
196 49078731
197 51833654
198 54736201
199 57793573
200 61014159
201 64405541
202 67977024
203 71737414
204 75696505
205 79864139
206 84250588
207 88867181
208 93725399
209 98837102
210 104215542
211 109872871
212 115823950
213 122082976
214 128665179
215 135586700
216 142863898
217 150514288
218 158556642
219 167009666
220 175893998
221 185229680
222 195039657
223 205346381
224 216174263
225 227548658
226 239495289
227 252042008
228 265218272
229 279053312
230 293579899
231 308829789
232 324838217
233 341641196
234 359276705
235 377784116
236 397204504
237 417580982
238 438959218
239 461385616
240 484910810
241 509584479
242 535461626
243 562598316
244 591053173
245 620887983
246 652166606
247 684955345
248 719325582
249 755349251
250 793103945
251 832667888
252 874125352
253 917562705
254 963071165
255 1010745706
256 1060684648
257 1112990777
258 1167773476
259 1225143315
260 1285219890
261 1348123819
262 1413983472
263 1482932332
264 1555109934
265 1630661151
266 1709737723
267 1792496566
268 1879104002
269 1969730379
270 2064557376
271 2163769293
272 2267562355
273 2376139721
274 2489713283
275 2608504420
276 2732743862
277 2862669579
278 2998534746
279 3140598163
280 3289134064
281 3444423874
282 3606764030
283 3776461532
284 3953838148
285 4139228133
286 4332979761
287 4535453920
288 4747031666
289 4968103380
290 5199082906
291 5440394837
292 5692484342
293 5955814784
294 6230869601
295 6518150313
296 6818181697
297 7131505524
298 7458691876
299 7800328442
300 8157033956
301 8529444617
302 8918227943
303 9324076708
304 9747712794
305 10189887179
306 10651383247
307 11133009451
308 11635616913
309 12160082328
310 12707325628
311 13278297297
312 13873990042
313 14495433626
314 15143703094
315 15819913886
316 16525228579
317 17260850135
318 18028039591
319 18828097112
320 19662386781
321 20532317310
322 21439357039
323 22385032009
324 23370931381
325 24398702928
326 25470066392
327 26586798763
328 27750758711
329 28963867845
330 30228135180
331 31545636999
332 32918538135
333 34349084769
334 35839613783
335 37392551147
336 39010423913
337 40695843233
338 42451539594
339 44280334492
340 46185172184
341 48169101610
342 50235294715
343 52387041046
344 54627764868
345 56961016134
346 59390489662
347 61920008300
348 64553559916
349 67295266571
350 70149428072
351 73120495047
352 76213092761
353 79432021200
354 82782269566
355 86269007810
356 89897618267
357 93673666192
358 97602948978
359 101691466082
360 105945463431
361 110371406851
362 114976016008
363 119766257509
364 124749367384
365 129932846961
366 135324495885
367 140932378668
368 146764892618
369 152830724345
370 159138906734
371 165698797704
372 172520110769
373 179612912190
374 186987657830
375 194655178055
376 202626725987
377 210913943726
378 219528936249
379 228484225778
380 237792828115
381 247468221601
382 257524387501
383 267975816912
384 278837547751
385 290125150643
386 301854801480
387 314043228902
388 326707810355
389 339866530077
390 353538059123
391 367741729355
392 382497591186
393 397826412432
394 413749732707
395 430289855899
396 447469932377
397 465313901348
398 483846619375
399 503093802633
400 523082128468
401 543839223077
402 565393718298
403 587775259227
404 611014587223
405 635143517053
406 660195051163
407 686203323339
408 713203742187
409 741232936190
410 770328887605
411 800530913638
412 831879743467
413 864417543741
414 898188012227
415 933236357819
416 969609462412
417 1007355801043
418 1046525625435
419 1087170922755
420 1129345560419
421 1173105284761
422 1218507831974
423 1265612946737
424 1314482515185
425 1365180557050
426 1417773417036
427 1472329684070
428 1528920431471
429 1587619164978
430 1648502006654
431 1711647726193
432 1777137863184
433 1845056764980
434 1915491779630
435 1988533230608
436 2064274673805
437 2142812829059
438 2224247854399
439 2308683314668
440 2396226423110
441 2486988079836
442 2581083041482
443 2678629993620
444 2779751783545
445 2884575407232
446 2993232358857
447 3105858544391
448 3222594629702
449 3343586051083
450 3468983288620
451 3598941950933
452 3733623018615
453 3873192919426
454 4017823849639
455 4167693791055
456 4322986933138
457 4483893608648
458 4650610744238
459 4823341885565
460 5002297549401
461 5187695382079
462 5379760454115
463 5578725380594
464 5784830769756
465 5998325235060
466 6219465949322
467 6448518630888
468 6685758071632
469 6931468231202
470 7185942703632
471 7449484920954
472 7722408562849
473 8005037751238
474 8297707609738
475 8600764323019
476 8914565870777
477 9239482034938
478 9575895071679
479 9924199917277
480 10284804745473
481 10658131282151
482 11044615383653
483 11444707271156
484 11858872285343
485 12287591032235
486 12731360282074
487 13190693071478
488 13666119573620
489 14158187393221
490 14667462299098
491 15194528702196
492 15739990391632
493 16304470884040
494 16888614447649
495 17493086304345
496 18118573794810
497 18765786638200
498 19435457984477
499 20128344896478
500 20845229331458
501 21586918761145
502 22354247183023
503 23148075645993
504 23969293546256
505 24818818985370
506 25697600292085
507 26606616427472
508 27546878339309
509 28519429717956
510 29525348225677
511 30565746376573
512 31641772933220
513 32754613589384
514 33905492689334
515 35095673831329
516 36326461756435
517 37599203041201
518 38915287865404
519 40276151045930
520 41683273674458
521 43138184364344
522 44642461063189
523 46197732037256
524 47805678160298
525 49468033766980
526 51186589092550
527 52963191389506
528 54799747134555
529 56698223524225
530 58660650679478
531 60689123276128
532 62785802995951
533 64952919951535
534 67192775604359
535 69507744068602
536 71900275283372
537 74372896601156
538 76928215665683
539 79568922551121
540 82297792604984
541 85117688688658
542 88031564496065
543 91042466463786
544 94153537602617
545 97368019456596
546 100689256097504
547 104120696466101
548 107665898160554
549 111328530306486
550 115112377357007
551 119021342174909
552 123059450359737
553 127230852939610
554 131539831414778
555 135990800484237
556 140588313217122
557 145337064444123
558 150241895606236
559 155307798716804
560 160539921462235
561 165943571260917
562 171524221034429
563 177287512999166
564 183239265130688
565 189385475073963
566 195732326875245
567 202286195630978
568 209053653866586
569 216041476981868
570 223256649913695
571 230706372633275
572 238398067841655
573 246339386091099
574 254538214228176
575 263002680949874
576 271741165395733
577 280762303625302
578 290074997053312
579 299688419684187
580 309612026986095
581 319855563342563
582 330429072080848
583 341342902550910
584 352607721174445
585 364234519036953
586 376234623060183
587 388619704955040
588 401401792176105
589 414593277685522
590 428206931782941
591 442255911958292
592 456753776128901
593 471714492400393
594 487152453293832
595 503082486249673
596 519519868210887
597 536480337647291
598 553980109008741
599 572035885874024
600 590664876448764
601 609884806795596
602 629713938297917
603 650171080794174
604 671275611119364
605 693047487549235
606 715507268605345
607 738676129336126
608 762575880423647
609 787228985555952
610 812658581938726
611 838888498058083
612 865943276397498
613 893848191293229
614 922629273133481
615 952313327789277
616 982927961147259
617 1014501601055615
618 1047063522282839
619 1080643869672148
620 1115273685273051
621 1150984931836710
622 1187810522587669
623 1225784345422520
624 1264941294182326
625 1305317294928387
626 1346949338015072
627 1389875507195915
628 1434135012499914
629 1479768221048670
630 1526816692542889
631 1575323210586943
632 1625331821686112
633 1676887867554219
634 1730038025831728
635 1784830345462941
636 1841314288298226
637 1899540767857861
638 1959562192641422
639 2021432506680445
640 2085207236194322
641 2150943531311145
642 2218700216705310
643 2288537834908840
644 2360518699370882
645 2434706941468356
646 2511168564829288
647 2589971496811851
648 2671185645095223
649 2754882951293201
650 2841137452228974
651 2930025334975345
652 3021625002892050
653 3116017133513691
654 3213284747262474
655 3313513270041240
656 3416790604216422
657 3523207196325727
658 3632856111321138
659 3745833103358782
660 3862236695681314
661 3982168253489807
662 4105732070020241
663 4233035443170833
664 4364188764876264
665 4499305604179961
666 4638502799486178
667 4781900547792901
668 4929622502010565
669 5081795863763891
670 5238551487794003
671 5400023978290263
672 5566351800467105
673 5737677382120951
674 5914147229899358
675 6095912038650015
676 6283126811718542
677 6475950978311279
678 6674548520338732
679 6879088094337634
680 7089743167756292
681 7306692145476701
682 7530118514792076
683 7760210979640900
684 7997163611232657
685 8241175992052543
686 8492453372687605
687 8751206825250270
688 9017653408973470
689 9292016330174229
690 9574525119281147
691 9865415797202215
692 10164931063589473
693 10473320473121216
694 10790840631076558
695 11117755382509814
696 11454336015887637
697 11800861463807051
698 12157618518918103
699 12524902042781473
700 12903015196054268
701 13292269656865792
702 13692985864394158
703 14105493250338992
704 14530130492765611
705 14967245763280298
706 15417196991808010
707 15880352128752187
708 16357089425392248
709 16847797706757743
710 17352876670583075
711 17872737172620945
712 18407801542134526
713 18958503885133314
714 19525290412845352
715 20108619764586020
716 20708963351742067
717 21326805698784647
718 21962644807525167
719 22616992513114152
720 23290374870973814
721 23983332529527801
722 24696421138545130
723 25430211744600441
724 26185291216478313
725 26962262666077224
726 27761745893930053
727 28584377832779106
728 29430813020144991
729 30301724061133282
730 31197802129330927
731 32119757452860633
732 33068319841506614
733 34044239202071235
734 35048286088902287
735 36081252250556382
736 37143951206932774
737 38237218825408975
738 39361913932075603
739 40518918913249693
740 41709140363157279
741 42933509715566391
742 44192983924437259
743 45488546134185684
744 46821206390428566
745 48192002349508171
746 49602000025279837
747 51052294535213717
748 52544010890738394
749 54078304777873635
750 55656363392597447
751 57279406261049978
752 58948686117657129
753 60665489774009288
754 62431139036441714
755 64246991625388860
756 66114442139331474
757 68034923020512445
758 70009905575536532
759 72040900985690181
760 74129461384046054
761 76277180918703642
762 78485696883346113
763 80756690842469840
764 83091889814812619
765 85493067461339477
766 87962045328931810
767 90500694098620527
768 93110934900445821
769 95794740620078055
770 98554137286048408
771 101391205444310608
772 104308081613397939
773 107306959739114079
774 110390092717786638
775 113559793930025707
776 116818438843360188
777 120168466621932115
778 123612381819336131
779 127152756065946459
780 130792229852030032
781 134533514302947921
782 138379393050262337
783 142332724107662271
784 146396441830589185
785 150573558893454453
786 154867168350637497
787 159280445710625581
788 163816651112739736
789 168479131501247709
790 173271322915923810
791 178196752780990680
792 183259042306924050
793 188461908906936621
794 193809168715159777
795 199304739130105075
796 204952641463030337
797 210757003606934301
798 216722062830207931
799 222852168575177246
800 229151785397224990
801 235625495909700077
802 242278003865013229
803 249114137262668648
804 256138851579611705
805 263357233038832093
806 270774502008243837
807 278396016428613554
808 286227275395944409
809 294273922758642474
810 302541750882623113
811 311036704435826454
812 319764884336514243
813 328732551742787182
814 337946132193133621
815 347412219801158075
816 357137581610132711
817 367129161991331621
818 377394087232268712
819 387939670151713030
820 398773414919025116
821 409903021910463980
822 421336392761074850
823 433081635479913279
824 445147069751048730
825 457541232307343735
826 470272882504091005
827 483351007955093081
828 496784830399814780
829 510583811617683160
830 524757659589954566
831 539316334719978225
832 554270056291735610
833 569629309019293092
834 585404849823063750
835 601607714706744924
836 618249225882603683
837 635340998981760858
838 652894950549651880
839 670923305615062899
840 689438605557147427
841 708453716063381218
842 727981835377303483
843 748036502670339811
844 768631606695565969
845 789781394576955929
846 811500480904523007
847 833803856948628538
848 856706900224491929
849 880225384163145006
850 904375488146249951
851 929173807673275426
852 954637364879526271
853 980783619225338596
854 1007630478534598881
855 1035196310210933235
856 1063499952835461062
857 1092560727927270301
858 1122398452131028576
859 1153033449559412960
860 1184486564578893703
861 1216779174779019170
862 1249933204372894469
863 1283971137827685776
864 1318916033925466824
865 1354791540060956822
866 1391621907013031400
867 1429432003932966061
868 1468247333859134067
869 1508094049448523887
870 1548998969246301555
871 1590989594210303681
872 1634094124764887558
873 1678341478156836259
874 1723761306347707078
875 1770384014217493379
876 1818240778352921800
877 1867363566128337559
878 1917785155433504764
879 1969539154695769593
880 2022660023562403227
881 2077183093928127823
882 2133144591610526072
883 2190581658424993554
884 2249532374926516498
885 2310035783554628180
886 2372131912505917554
887 2435861799995624037
888 2501267519310771394
889 2568392204264246845
890 2637280075458054811
891 2707976467003731744
892 2780527854044047246
893 2854981880796306430
894 2931387389420942271
895 3009794449417091936
896 3090254387920680148
897 3172819820512253381
898 3257544683000836091
899 3344484263744081502
900 3433695236957812273
901 3525235696632332801
902 3619165191438820215
903 3715544760308106850
904 3814436969038564313
905 3915905947586839928
906 4020017428473394982
907 4126838785859949506
908 4236439075828346751
909 4348889077365030641
910 4464261334564992261
911 4582630199630612618
912 4704071877091032178
913 4828664468892234335
914 4956488020767401954
915 5087624569484066707
916 5222158191476149304
917 5360175052353247610
918 5501763457884896121
919 5647013905914475629
920 5796019139775280944
921 5948874202735366479
922 6105676493957405053
923 6266525825577594940
924 6431524481372079098
925 6600777276554711774
926 6774391619291493545
927 6952477573349357425
928 7135147922565973550
929 7322518236531759671
930 7514706938119334450
931 7711835372346174634
932 7914027877115995351
933 8121411855387441801
934 8334117849320511865
935 8552279615874401892
936 8776034204527202251
937 9005522036466089410
938 9240886986023534550
939 9482276463678646606
940 9729841501343194149
941 9983736839362283383
942 10244121015840382096
943 10511156457792626224
944 10785009574755427736
945 11065850854247768863
946 11353854959865250893
947 11649200831268140119
948 11952071786935031943
949 12262655628937992411
950 12581144750541725454
951 12907736245991826765
952 13242632023193587610
953 13586038918713899897
954 13938168815833759932
955 14299238764966143822
956 14669471107335710717
957 15049093601082015971
958 15438339550781609801
959 15837447939564105006
960 16246663564714773323
961 16666237176073658181
962 17096425618024203344
963 17537491974423998421
964 17989705717330508616
965 18453342858737599917
966 18928686106345408039
967 19416025022433598635
968 19915656186958372431
969 20427883363957058418
970 20953017672272634026
971 21491377759833629074
972 22043289982384376798
973 22609088585946396112
974 23189115893993868901
975 23783722498444738870
976 24393267455651887924
977 25018118486350192728
978 25658652180815779752
979 26315254208241931531
980 26988319531464679769
981 27678252626187098241
982 28385467705735264193
983 29110388950530452866
984 29853450743406281455
985 30615097909765805600
986 31395785963930603044
987 32195981360509016773
988 33016161752213299567
989 33856816253029047476
990 34718445708002753363
991 35601562968722456252
992 36506693175667251347
993 37434374046497765886
994 38385156171606197812
995 39359603315786619530
996 40358292727562724271
997 41381815454883093225
998 42430776668791319132
999 43505795993860863214
1000 44607507846835014936