1 0
2 0
3 0
4 0
5 1
6 1
7 1
8 1
9 4
10 4
11 4
12 4
13 10
14 11
15 11
16 11
17 22
18 25
19 26
20 26
21 44
22 51
23 54
24 55
25 84
26 98
27 105
28 108
29 153
30 178
31 193
32 200
33 269
34 313
35 341
36 356
37 459
38 531
39 582
40 611
41 764
42 880
43 967
44 1021
45 1244
46 1424
47 1568
48 1662
49 1988
50 2264
51 2494
52 2653
53 3122
54 3536
55 3896
56 4155
57 4828
58 5444
59 5995
60 6408
61 7365
62 8265
63 9096
64 9738
65 11094
66 12400
67 13632
68 14615
69 16522
70 18393
71 20198
72 21674
73 24347
74 27011
75 29622
76 31812
77 35533
78 39289
79 43030
80 46231
81 51393
82 56658
83 61964
84 66597
85 73717
86 81039
87 88505
88 95132
89 104916
90 115045
91 125463
92 134863
93 148238
94 162160
95 176598
96 189804
97 208021
98 227062
99 246935
100 265354
101 290048
102 315946
103 343135
104 368623
105 401974
106 437040
107 474020
108 509066
109 553917
110 601165
111 651198
112 699063
113 759162
114 822562
115 889906
116 954914
117 1035125
118 1119829
119 1210051
120 1297829
121 1404515
122 1517248
123 1637572
124 1755506
125 1896879
126 2046330
127 2206122
128 2363768
129 2550489
130 2747912
131 2959257
132 3169044
133 3414810
134 3674672
135 3953139
136 4231056
137 4553518
138 4894435
139 5259991
140 5626676
141 6048407
142 6494187
143 6972403
144 7454259
145 8004170
146 8585266
147 9208766
148 9839638
149 10554521
150 11309698
151 12120023
152 12942989
153 13869700
154 14848265
155 15898154
156 16968091
157 18165991
158 19430418
159 20786691
160 22173107
161 23717392
162 25346748
163 27093823
164 28884774
165 30870293
166 32964309
167 35208644
168 37515144
169 40061470
170 42745774
171 45621277
172 48583244
173 51840559
174 55272948
175 58947726
176 62740797
177 66897579
178 71275942
179 75960572
180 80805069
181 86097098
182 91668992
183 97626743
184 103798093
185 110520014
186 117594629
187 125153954
188 132996157
189 141515157
190 150477781
191 160047732
192 169989145
193 180762265
194 192092248
195 204181251
196 216754709
197 230349421
198 244641908
199 259880792
200 275747347
201 292867361
202 310860061
203 330030127
204 350008939
205 371524952
206 394130580
207 418197850
208 443301624
209 470289548
210 498635542
211 528792383
212 560271570
213 594058207
214 629534785
215 667250595
216 706645931
217 748865314
218 793184098
219 840266727
220 889474247
221 942135037
222 997399878
223 1056070132
224 1117418616
225 1182986754
226 1251779733
227 1324761554
228 1401107675
229 1482605250
230 1568090497
231 1658719976
232 1753561766
233 1854687639
234 1960736925
235 2073093892
236 2190709370
237 2315983467
238 2447327481
239 2586394265
240 2732006769
241 2886945274
242 3049356163
243 3221208722
244 3401187905
245 3592512723
246 3793023506
247 4005061377
248 4227162911
249 4463055005
250 4710223506
251 4971446162
252 5245101849
253 5535503794
254 5839729393
255 6161067848
256 6497731415
257 6854712065
258 7228615677
259 7623330065
260 8036894119
261 8475083661
262 8933962763
263 9418118487
264 9925411029
265 10462523605
266 11024896940
267 11617934233
268 12239315320
269 12896771777
270 13585030272
271 14310444758
272 15070516336
273 15874190189
274 16715374293
275 17601529571
276 18529985808
277 19511090802
278 20537817773
279 21618914231
280 22751551918
281 23947702460
282 25199271311
283 26516500458
284 27896426126
285 29352897188
286 30876604114
287 32479522357
288 34158584687
289 35929813308
290 37782516198
291 39730678352
292 41771175087
293 43922541749
294 46172519107
295 48537418615
296 51014119378
297 53624066163
298 56353223626
299 59220595535
300 62223146524
301 65385686134
302 68692173682
303 72164724830
304 75800494516
305 79628187411
306 83629500093
307 87830143703
308 92227598460
309 96855073986
310 101691723046
311 106767406868
312 112080099808
313 117668225736
314 123508080565
315 129634314071
316 136045606941
317 142786413531
318 149829833288
319 157216036239
320 164944671167
321 173067170894
322 181553063253
323 190448880546
324 199755562826
325 209532612688
326 219745582834
327 230448332423
328 241643486781
329 253399884372
330 265678661474
331 278542113111
332 291995030815
333 306117046516
334 320864410038
335 336309122964
336 352458723867
337 369405327179
338 387099788752
339 405625276742
340 424992778953
341 445308837067
342 466518379599
343 488717413735
344 511921219137
345 536253015532
346 561651236939
347 588226651002
348 615999839935
349 645113292672
350 675498363970
351 707282782737
352 740493639434
353 775295688181
354 811612595939
355 849591580237
356 889267677822
357 930831355879
358 974197982956
359 1019537160896
360 1066893579514
361 1116487401375
362 1168225082108
363 1222301932257
364 1278774320019
365 1337896685087
366 1399565980995
367 1464007035912
368 1531290291087
369 1601709749612
370 1675152303253
371 1751876670750
372 1831970195486
373 1915772523207
374 2003159994757
375 2094430230148
376 2189690807881
377 2289334024013
378 2393225262957
379 2501706797687
380 2614910366081
381 2733288969019
382 2856696768858
383 2985527283931
384 3119941019916
385 3260460958172
386 3406929941386
387 3559800299668
388 3719266715299
389 3885932806204
390 4059630242708
391 4240878839814
392 4429913791951
393 4627431613594
394 4833253243409
395 5047975936430
396 5271882814166
397 5505777363928
398 5749470634001
399 6003648731698
400 6268651369868
401 6545405189868
402 6833712668586
403 7134361863542
404 7447759196049
405 7774973028249
406 8115799209247
407 8471142764610
408 8841488619617
409 9228068181805
410 9630673360471
411 10050343383738
412 10487655424460
413 10944028389587
414 11419253881316
415 11914525091822
416 12430527435308
417 12968895380512
418 13529424977043
419 14113486059107
420 14721890880792
421 15356521632584
422 16017184963293
423 16705453352314
424 17422287498658
425 18169854191135
426 18947978481953
427 19758465332577
428 20602448968322
429 21482423009922
430 22398240744205
431 23351973827425
432 24344959099090
433 25380065401301
434 26457186478744
435 27578699932989
436 28746178931886
437 29962922923601
438 31228881232544
439 32546782408591
440 33918474991328
441 35347752443544
442 36834638201307
443 38382263385134
444 39992797092151
445 41670599328301
446 43415790270180
447 45231962788882
448 47121658795039
449 49089887814248
450 51136894196962
451 53266800433449
452 55482581645218
453 57789991727600
454 60189432366874
455 62685633465952
456 65282073114057
457 67985358012219
458 70796087047721
459 73719686726648
460 76760218628836
461 79925266137903
462 83215673148204
463 86637664978352
464 90195979590583
465 93899318572781
466 97748827900712
467 101751648855963
468 105913302883675
469 110243771349763
470 114744570311696
471 119423891226371
472 124288162433250
473 129348829542564
474 134607859413408
475 140074647455410
476 145756671035245
477 151667050481616
478 157808299102627
479 164191192380545
480 170824420310995
481 177723018079181
482 184890158433493
483 192338198643980
484 200077229555968
485 208124475044766
486 216483900562973
487 225169676104860
488 234193509798234
489 243575126436579
490 253319440945757
491 263442700434220
492 273958479062101
493 284889358370277
494 296241386913191
495 308033191478948
496 320280498013915
497 333009150279157
498 346226546300209
499 359954038780430
500 374209833561898
501 389023498452301
502 404404033599721
503 420375913678926
504 436960200990454
505 454190713329596
506 472078348134787
507 490651155049324
508 509933484809458
509 529964003898354
510 550755851465407
511 572341170051764
512 594748094153260
513 618020820355365
514 642175130729278
515 667247852804704
516 693271472541895
517 720296491876123
518 748341802648249
519 777449593989404
520 807657353706904
521 839022770935261
522 871568389684972
523 905342533763416
524 940388437606346
525 976771980276491
526 1014519987485834
527 1053687800681749
528 1094325253446093
529 1136507554738031
530 1180266541647769
531 1225665581535403
532 1272762082560860
533 1321641879110653
534 1372342664589434
535 1424936983216721
536 1479490933342050
537 1536102446808616
538 1594816050548935
539 1655714779168823
540 1718874696615209
541 1784407504198518
542 1852365691565859
543 1922844282232106
544 1995930763255032
545 2071752504185950
546 2150371260733360
547 2231895754494110
548 2316426560589877
549 2404108872402722
550 2495015214806683
551 2589269956214998
552 2686988660980243
553 2788336792944712
554 2893399377876082
555 3002318652309614
556 3115227339872149
557 3232313950970662
558 3353678005805347
559 3479482140133240
560 3609878712854201
561 3745082430203172
562 3885209599615904
563 4030446139405057
564 4180966867736618
565 4337016258190316
566 4498730040459991
567 4666320698825544
568 4839988730409426
569 5020012425633724
570 5206549962165994
571 5399844128222422
572 5600124769323634
573 5807708582845309
574 6022779666311054
575 6245615365831436
576 6476479055788780
577 6715731042253761
578 6963585323275575
579 7220358642637205
580 7486352664464262
581 7761977196735631
582 8047480698974920
583 8343224816987849
584 8649554924556530
585 8966937006658020
586 9295659206230361
587 9636134329444050
588 9988757627636996
589 10354058821414146
590 10732371712048426
591 11124167379210772
592 11529897968396156
593 11950165493009993
594 12385356244374185
595 12836007657927089
596 13302636752523293
597 13785927519386508
598 14286326546527770
599 14804446805431723
600 15340879258956487
601 15896400835152339
602 16471527333588471
603 17066957686081417
604 17683367107208182
605 18321637859161651
606 18982365127596496
607 19666345637493601
608 20374350564566769
609 21107381526305269
610 21866124699474978
611 22651488029815553
612 23464351951232119
613 24305853290092206
614 25176782443616189
615 26078173810427816
616 27011032177386748
617 27976647501087497
618 28975929471418349
619 30010056213737793
620 31080173997451971
621 32187746163008042
622 33333818855696929
623 34519733510309790
624 35746797310904865
625 37016669865906185
626 38330553308424850
627 39689974575961021
628 41096423803833060
629 42551782718190095
630 44057431657985060
631 45615108206977085
632 47226510433559901
633 48893771374508981
634 50618474834225899
635 52402597519951637
636 54248073744265709
637 56157320814781470
638 58132154704982133
639 60174823487901989
640 62287529793787467
641 64473012406127798
642 66733352068364785
643 69071104713276236
644 71488777612569656
645 73989473011768543
646 76575573434265355
647 79249983965443812
648 82015557642353943
649 84875807543225638
650 87833459966709118
651 90891815859249569
652 94054120566296159
653 97324351431435883
654 100705626159301147
655 104201694374813812
656 107816246391171106
657 111553784073653078
658 115417870530477285
659 119412763772163234
660 123542658639787300
661 127812649455289849
662 132226805919524211
663 136789961902804456
664 141506884117851961
665 146383335917571103
666 151423962903178601
667 156634251033323579
668 162019615012720506
669 167586573516735259
670 173340426517758172
671 179287398154615160
672 185433637137647127
673 191786514683898613
674 198352073944681407
675 205137374441079715
676 212149396051255534
677 219396472038521518
678 226885489198873832
679 234624452147981550
680 242621281653487858
681 250885396338781393
682 259424640252392789
683 268248086900335672
684 277364721805871826
685 286785187783916355
686 296518414554436566
687 306574684158358386
688 316964186665689484
689 327698945348505584
690 338789120701986151
691 350246360777870780
692 362082217908165398
693 374310271669679110
694 386942077227228066
695 399990826174275571
696 413469610988532816
697 427393765389210680
698 441776424258874391
699 456632522814189800
700 471976894249290908
701 487826848951162231
702 504197310375539010
703 521105182792136053
704 538567266195109746
705 556603097875325629
706 575229625500705685
707 594465976310254923
708 614331171863961075
709 634847257688445663
710 656033471426516381
711 677911449205365267
712 700502721152936785
713 723832157250745925
714 747921584747032680
715 772795470520329269
716 798478176488930393
717 824997752439291640
718 852378952922641196
719 880649437790843616
720 909836764660265118
721 939972562354156948
722 971084893196067629
723 1003205017537674052
724 1036364098288931560
725 1070597791738806232
726 1105937896497377151
727 1142419731783588212
728 1180078526687858455
729 1218954468538439903
730 1259083574696048527
731 1300505738654431287
732 1343260774137279222
733 1387393964881686270
734 1432946090027410039
735 1479962196726831963
736 1528487266380484205
737 1578572313738919620
738 1630263490716785763
739 1683611649247421608
740 1738667593904523917
741 1795488782607419509
742 1854127427296648252
743 1914640916228368422
744 1977086613895796617
745 2041529220389200813
746 2108027780452515494
747 2176647040335615652
748 2247451752288324516
749 2320514754808018234
750 2395902794119123482
751 2473688897118923493
752 2553946133747374256
753 2636756485985494827
754 2722195377713384173
755 2810345152245565692
756 2901288241546782097
757 2995116897961623377
758 3091916319668782989
759 3191779328842681244
760 3294798891963082085
761 3401078794899444091
762 3510715241734169404
763 3623812837764335209
764 3740476400000779126
765 3860822663443745293
766 3984960220845959652
767 4113006923626328219
768 4245080916041008821
769 4381313468315640647
770 4521827113896396204
771 4666754590951036499
772 4816229027573801311
773 4970398005934966865
774 5129399741666319836
775 5293383699027406729
776 5462499847840446734
777 5636914072033002359
778 5816782222950732371
779 6002272552542577012
780 6193553955457031004
781 6390812845348064297
782 6594224900034559527
783 6803979469270609329
784 7020266707526395572
785 7243296052262266922
786 7473265463877056745
787 7710387977865532944
788 7954877625192553320
789 8206969658484359982
790 8466887073548570028
791 8734869490054503678
792 9011157747035718906
793 9296016035672617191
794 9589695471728651041
795 9892465504421241227
796 10204597064382506801
797 10526386775492650544
798 10858117328768613683
799 11200091635912099623
800 11552614395958764025
801 11916018573550260285
802 12290622304522765124
803 12676766028840482844
804 13074792330085187969
805 13485074883718755166
806 13907971602743618384
807 14343865004459238246
808 14793140163813453058
809 15256216352702242464
810 15733496110485218612
811 16225409120374389324
812 16732388103387960996
813 17254903388666593315
814 17793407568202267000
815 18348383181805797538
816 18920316362885847420
817 19509734600242237605
818 20117146608959755625
819 20743094147960160620
820 21388123211961151093
821 22052825267360037435
822 22737771941713586788
823 23443571325006758567
824 24170836483825791274
825 24920230477898094697
826 25692395438757902982
827 26488013735239422144
828 27307773565993888580
829 28152418089146160231
830 29022668426469573637
831 29919290105405834123
832 30843055464448414302
833 31794797256360931574
834 32775325077260983730
835 33785497531894768835
836 34826181162946386901
837 35898308918501374030
838 37002789465679521662
839 38140585563148557383
840 39312669199960409512
841 40520085350606949831
842 41763853590024860478
843 43045053197665232674
844 44364774163828766920
845 45724186690937919111
846 47124434480644303211
847 48566727137415163343
848 50052286670375063185
849 51582423237507080460
850 53158419425972318218
851 54781630570414439772
852 56453426345813260907
853 58175273292444916972
854 59948609357121215473
855 61774952792525468548
856 63655838401352215600
857 65592907424229999538
858 67587771552115218779
859 69642131128287807236
860 71757705565856935537
861 73936331228730102083
862 76179814063561593580
863 78490057885877713531
864 80868988451647232946
865 83318660013030369191
866 85841095651752365345
867 88438426495579327745
868 91112808879815586780
869 93866540315272600077
870 96701886533378596279
871 99621232549266553375
872 102626992300507738177
873 105721734824806645767
874 108907996950186702845
875 112188447196727204931
876 115565787227262831312
877 119042889097067358562
878 122622592439686690914
879 126307882281314468799
880 130101781581279687416
881 134007500485777192819
882 138028216770914992553
883 142167268732367507435
884 146428038031879575852
885 150814111962315452970
886 155329045813803923045
887 159976572097170847995
888 164760472846057357572
889 169684755981593106618
890 174753398164657572873
891 179970571715271240174
892 185340505447848335923
893 190867676311089870450
894 196556531178821816489
895 202411732939622510963
896 208438008864799187138
897 214640358793103453384
898 221023754193782218774
899 227593405021935209776
900 234354594534547539399
901 241312905390856210532
902 248473894193569446564
903 255843380836488886910
904 263427268592878833247
905 271231789611286817188
906 279263153003692416099
907 287527858553604800285
908 296032500802659961440
909 304784035538996266201
910 313789399353710395725
911 323055849730775626858
912 332590751751489360217
913 342401867298736235819
914 352496943844800729201
915 362884083109985186875
916 373571508889760059490
917 384567880834071206776
918 395881850059510384541
919 407522458742406133659
920 419498887449632447976
921 431820795498233659284
922 444497840802321756014
923 457540112959757605005
924 470957858333837533458
925 484761849155676026490
926 498962864820091044329
927 513572161233907162582
928 528601171751445182405
929 544061907351122727989
930 559966396384015732159
931 576327193177564865298
932 593157052772123570486
933 610469364684977269978
934 628277547889209808928
935 646595601910482382113
936 665437753144023329942
937 684818924914651759968
938 704754084220897989812
939 725258838826016928558
940 746349052753796071180
941 768041355563192545369
942 790352437132184255704
943 813299694528795050972
944 836900814089004922658
945 861174323050329896942
946 886138828370320251156
947 911813717470811894506
948 938218704090978383575
949 965374425666742036746
950 993301621878842015847
951 1022021893695549092488
952 1051557209967415303388
953 1081930554200015792821
954 1113165038204599960260
955 1145284724223086550417
956 1178314088987124984294
957 1212278723811637953349
958 1247204378375703992193
959 1283117851100835384784
960 1320046407134319410648
961 1358018535991756223507
962 1397062920125304156172
963 1437209399144316807909
964 1478488337900196016330
965 1520931446229094637356
966 1564570666567222445617
967 1609439218054263476781
968 1655570910592719414808
969 1703001031588770861931
970 1751765146448054725216
971 1801900229089540265757
972 1853443917524991432283
973 1906435472868370951133
974 1960914486088338260235
975 2016922101986197331117
976 2074500211489034250509
977 2133692488597837056427
978 2194542996282711820601
979 2257097511546188619705
980 2321402649244996913482
981 2387506983076227861839
982 2455459542975615060265
983 2525311249500102979932
984 2597113963586253474466
985 2670921698134399090014
986 2746788998706752598476
987 2824772496124246422651
988 2904929876132177681096
989 2987321188636643271761
990 3072007102895085418907
991 3159050587935722080513
992 3248515795631122808442
993 3340469475171688802923
994 3434979093293622868470
995 3532114652898885079020
996 3631947482532629374014
997 3734551764247679189218
998 3840002508720805940198
999 3948377523281372402162
1000 4059756100246552575178