0 1
1 1
2 0
3 1
4 2
5 1
6 1
7 3
8 2
9 2
10 5
11 4
12 3
13 7
14 7
15 5
16 10
17 11
18 8
19 14
20 17
21 13
22 20
23 25
24 19
25 27
26 36
27 29
28 37
29 50
30 43
31 51
32 69
33 61
34 69
35 94
36 86
37 93
38 126
39 120
40 125
41 167
42 164
43 167
44 220
45 222
46 222
47 287
48 297
49 294
50 373
51 393
52 386
53 481
54 516
55 505
56 617
57 672
58 657
59 788
60 868
61 850
62 1002
63 1114
64 1094
65 1269
66 1422
67 1402
68 1601
69 1803
70 1787
71 2013
72 2275
73 2267
74 2522
75 2858
76 2864
77 3150
78 3573
79 3602
80 3923
81 4449
82 4511
83 4870
84 5520
85 5629
86 6029
87 6822
88 6996
89 7444
90 8404
91 8664
92 9166
93 10321
94 10693
95 11258
96 12637
97 13153
98 13792
99 15429
100 16128
101 16855
102 18790
103 19717
104 20549
105 22824
106 24035
107 24995
108 27657
109 29217
110 30334
111 33439
112 35424
113 36732
114 40340
115 42840
116 44384
117 48563
118 51682
119 53517
120 58347
121 62206
122 64397
123 69964
124 74705
125 77336
126 83738
127 89522
128 92692
129 100045
130 107059
131 110887
132 119318
133 127777
134 132409
135 142063
136 152213
137 157823
138 168869
139 180990
140 187785
141 200413
142 214826
143 223053
144 237481
145 254551
146 264502
147 280985
148 301126
149 313144
150 331970
151 355654
152 370145
153 391645
154 419407
155 436847
156 461408
157 493851
158 514792
159 542857
160 580668
161 605757
162 637834
163 681787
164 711776
165 748460
166 799429
167 835185
168 877156
169 936131
170 978662
171 1026704
172 1094800
173 1145266
174 1200292
175 1278767
176 1338501
177 1401559
178 1491832
179 1562369
180 1634666
181 1738337
182 1821436
183 1904371
184 2023242
185 2120913
186 2216093
187 2352195
188 2466736
189 2576010
190 2731633
191 2865665
192 2991166
193 3168886
194 3325391
195 3469568
196 3672290
197 3854660
198 4020319
199 4251314
200 4463404
201 4653775
202 4916723
203 5162896
204 5381677
205 5680728
206 5965930
207 6217348
208 6557172
209 6887000
210 7175901
211 7561755
212 7942526
213 8274441
214 8712248
215 9151098
216 9532333
217 10028760
218 10533735
219 10971492
220 11534043
221 12114201
222 12616676
223 13253801
224 13919343
225 14495854
226 15217065
227 15979462
228 16640608
229 17456608
230 18328747
231 19086558
232 20009393
233 21005743
234 21873854
235 22917082
236 24053883
237 25047752
238 26226618
239 27522073
240 28659194
241 29990850
242 31465359
243 32765501
244 34269236
245 35945649
246 37431157
247 39128652
248 41032533
249 42728623
250 44644252
251 46804202
252 48739293
253 50900444
254 53348445
255 55554565
256 57992000
257 60763781
258 63276975
259 66025245
260 69160720
261 72021510
262 75119400
263 78663132
264 81917066
265 85408101
266 89409813
267 93108023
268 97041031
269 101556194
270 105756029
271 110185769
272 115276240
273 120041998
274 125029848
275 130764568
276 136168269
277 141783006
278 148238791
279 154361032
280 160679695
281 167942112
282 174873053
283 181981883
284 190146199
285 197986616
286 205982130
287 215154384
288 224016820
289 233006986
290 243305180
291 253315277
292 263420802
293 274976181
294 286274101
295 297629896
296 310588410
297 323330386
298 336087155
299 350611064
300 364971187
301 379297195
302 395566811
303 411738934
304 427821974
305 446037632
306 464237474
307 482287034
308 502671248
309 523138765
310 543388418
311 566188251
312 589190201
313 611900255
314 637389963
315 663222720
316 688683148
317 717167091
318 746159805
319 774693460
320 806509293
321 839027326
322 870993507
323 906515724
324 942964409
325 978762797
326 1018406650
327 1059235493
328 1099310458
329 1143536240
330 1189243505
331 1234088894
332 1283406688
333 1334544397
334 1384708789
335 1439683719
336 1496863244
337 1552955715
338 1614213670
339 1678111819
340 1740808329
341 1809042326
342 1880407996
343 1950458386
344 2026435568
345 2106097149
346 2184332832
347 2268902123
348 2357775568
349 2445118009
350 2539218587
351 2638316240
352 2735786259
353 2840456865
354 2950897246
355 3059625229
356 3176014372
357 3299032852
358 3420269975
359 3549647185
360 3686607669
361 3821738231
362 3965506421
363 4117914245
364 4268469167
365 4428178181
366 4597694220
367 4765365878
368 4942727387
369 5131183462
370 5317841969
371 5514745857
372 5724161721
373 5931872720
374 6150405000
375 6383006918
376 6614051139
377 6856513648
378 7114754674
379 7371649347
380 7640581373
381 7927163684
382 8212685952
383 8510887871
384 8828787176
385 9145999784
386 9476559025
387 9829051203
388 10181330589
389 10547650103
390 10938340501
391 11329407525
392 11735236889
393 12168092312
394 12602045899
395 13051515446
396 13530899096
397 14012253018
398 14509911197
399 15040621005
400 15574344085
401 16125198305
402 16712508796
403 17304068858
404 17913630208
405 18563338201
406 19218750128
407 19893082313
408 20611556982
409 21337435159
410 22083207951
411 22877445510
412 23681061144
413 24505608837
414 25383292174
415 26272635899
416 27184021243
417 28153585187
418 29137435336
419 30144519307
420 31215221886
421 32303219066
422 33415737097
423 34597737198
424 35800465658
425 37029110946
426 38333553251
427 39662629578
428 41019143908
429 42458251544
430 43926421464
431 45423694405
432 47010869889
433 48632113787
434 50284290953
435 52034226481
436 53823874403
437 55646475439
438 57575273108
439 59550130120
440 61560177433
441 63685480203
442 65863962989
443 68080122113
444 70421256712
445 72823542337
446 75266274854
447 77844407492
448 80492595433
449 83184325637
450 86022631536
451 88940920153
452 91906216653
453 95030064865
454 98244943444
455 101510716879
456 104947871578
457 108488329376
458 112084047702
459 115864887190
460 119762640963
461 123720563914
462 127878319193
463 132168060620
464 136523494755
465 141094509212
466 145814174107
467 150605750346
468 155629762115
469 160820823194
470 166090798827
471 171611248182
472 177319033297
473 183113620295
474 189177983993
475 195452022142
476 201821744199
477 208481898851
478 215376296220
479 222376376958
480 229688994308
481 237262842836
482 244953627583
483 252980604162
484 261298425443
485 269745839594
486 278554763460
487 287686990916
488 296963037932
489 306627695993
490 316651198457
491 326834500658
492 337435429790
493 348434079986
494 359610465809
495 371235551231
496 383300842985
497 395563984623
498 408309109802
499 421540827817
500 434992933237
501 448962685543
502 463469632239
503 478222196145
504 493530632519
505 509431416694
506 525606035455
507 542377513509
508 559801405694
509 577530661195
510 595900741041
511 614988601255
512 634417019472
513 654533441700
514 675438725489
515 696723816052
516 718747562647
517 741637411668
518 764950794680
519 789057239489
520 814113663730
521 839642291179
522 866022446872
523 893443605892
524 921391085406
525 950252955344
526 980254546529
527 1010842575470
528 1042412618789
529 1075229381362
530 1108699300400
531 1143224019193
532 1179111363379
533 1215725839224
534 1253473498132
535 1292709269452
536 1332754116933
537 1374016605740
538 1416902995383
539 1460689150146
540 1505784000485
541 1552649613617
542 1600515267663
543 1649787836678
544 1700989931098
545 1753302843917
546 1807128678232
547 1863055587156
548 1920215586520
549 1979002980404
550 2040076734178
551 2102518421944
552 2166711185698
553 2233390347973
554 2301586026791
555 2371666482079
556 2444449217762
557 2518912056305
558 2595404275814
559 2674831669154
560 2756119125004
561 2839592436458
562 2926252078833
563 3014969598880
564 3106042374174
565 3200572243105
566 3297377263561
567 3396721014923
568 3499813667203
569 3605419936887
570 3713763744869
571 3826170848395
572 3941353100265
573 4059488399485
574 4182025630431
575 4307624628787
576 4436410378901
577 4569962712908
578 4706890705732
579 4847258978294
580 4992786406282
581 5142033013967
582 5294995027574
583 5453538729300
584 5616177303747
585 5782829941758
586 5955518952944
587 6132713443752
588 6314246292535
589 6502304703522
590 6695317070189
591 6893020018360
592 7097774745606
593 7307972957902
594 7523244399104
595 7746133573986
596 7975000246250
597 8209355932654
598 8451937954757
599 8701079662356
600 8956162259094
601 9220125565445
602 9491282895860
603 9768872289304
604 10056045894538
605 10351104289744
606 10653128708175
607 10965493574431
608 11286495024511
609 11615043033311
610 11954744333555
611 12303899986683
612 12661233423920
613 13030593766883
614 13410297525740
615 13798865450526
616 14200399140331
617 14613242319411
618 15035696049968
619 15472124459149
620 15920911583600
621 16380120906911
622 16854389047441
623 17342154880069
624 17841225522354
625 18356519905128
626 18886547794006
627 19428840247420
628 19988608127528
629 20564449773730
630 21153599580611
631 21761569693242
632 22387066445967
633 23027006050818
634 23687210949473
635 24366516742844
636 25061499030093
637 25778299147602
638 26515905202102
639 27270528844789
640 28048638406521
641 28849399827648
642 29668636583141
643 30513151510443
644 31382315925632
645 32271540024005
646 33187967976725
647 34131206362421
648 35096226142091
649 36090518859674
650 37113958722068
651 38161050680572
652 39239638792239
653 40349899875671
654 41485845314953
655 42655675802455
656 43859908512949
657 45092032970075
658 46360609479539
659 47666536224674
660 49002751894606
661 50378178107883
662 51794137767711
663 53242989139025
664 54734015430270
665 56269011190044
666 57839724129013
667 59455797748687
668 61119548541042
669 62822083078047
670 64573402123277
671 66376397944386
672 68221505034580
673 70119076483594
674 72072637866979
675 74071920414880
676 76127622523555
677 78243964476195
678 80409942936266
679 82636592315009
680 84928893041012
681 87275075928568
682 89686499641023
683 92168974401432
684 94709934069775
685 97321047119449
686 100009027602570
687 102760481669622
688 105587370265266
689 108497389866826
690 111476288701660
691 114536299720920
692 117686185162198
693 120910805868413
694 124222642968688
695 127631612711882
696 131121660078134
697 134705486934553
698 138394256885363
699 142170971806040
700 146048522990867
701 150039420013549
702 154125695915803
703 158320395969655
704 162637479777235
705 167057987630523
706 171595078913877
707 176264272934330
708 181045595458625
709 185952275413439
710 191001507275272
711 196172283005165
712 201477851500883
713 206937203827089
714 212528281736779
715 218264299221211
716 224166171467512
717 230210776910994
718 236411234136849
719 242790516261436
720 249324429032240
721 256025929184520
722 262920187992323
723 269981933364883
724 277223887470101
725 284673566531715
726 292304620206892
727 300129456766855
728 308178090874566
729 316423098812454
730 324876488670995
731 333570933862419
732 342477948056033
733 351609045575247
734 360999725824238
735 370620457140720
736 380482158838433
737 390623330589084
738 401013419879304
739 411662641758745
740 422612677560572
741 433831986323373
742 445329961209538
743 457151653796233
744 469264575771847
745 481677172059858
746 494438060306716
747 507513855464988
748 520911918781986
749 534684637076239
750 548797789568123
751 563257508952128
752 578120161613594
753 593350763361584
754 608954063670153
755 624990626171686
756 641424787886181
757 658259750265087
758 675560499122385
759 693290790654589
760 711452103020008
761 730114076346109
762 749239998418752
763 768829438039101
764 788956928894022
765 809585418386129
766 830712368792186
767 852417453604145
768 874663424715550
769 897445429316447
770 920848533803387
771 944835457583214
772 969398812527051
773 994629317710830
774 1020489842597601
775 1046970231587533
776 1074167122670057
777 1102043738872100
778 1130586912829272
779 1159899473883833
780 1189945224620212
781 1220707729280333
782 1252296286910023
783 1284675529730456
784 1317825484468088
785 1351862203796602
786 1386751425417816
787 1422469356811875
788 1459139093394878
789 1496727781721617
790 1535207515611191
791 1574708727096924
792 1615200304336942
793 1656649920367160
794 1699195641991942
795 1742808463037911
796 1787451315961376
797 1833270204236138
798 1880238624766338
799 1928314437049389
800 1977651886283301
801 2028227405325149
802 2079993435911678
803 2133112772529231
804 2187565254546887
805 2243297548953023
806 2300481308888143
807 2359100290792776
808 2419095018048306
809 2480646312848376
810 2543742401682610
811 2608317284001565
812 2674561261649034
813 2742467629079264
814 2811963470528270
815 2883248877382324
816 2956322857539984
817 3031105178386954
818 3107806029068944
819 3186430826707213
820 3266891610574234
821 3349408973072685
822 3433995489466344
823 3520555050876596
824 3609318954623050
825 3700307739129448
826 3793416719537224
827 3888888194712625
828 3986751530425260
829 4086893031348836
830 4189566288224060
831 4294810420705790
832 4402502283145429
833 4512907040832699
834 4626074559505055
835 4741871799428864
836 4860575774033443
837 4982248156418536
838 5106745566737842
839 5234357129553074
840 5365157459232199
841 5498992389365907
842 5636163406445611
843 5776759276307878
844 5920614601156804
845 6068043466335801
846 6219150079437477
847 6373757370359073
848 6532192244578509
849 6694575725735236
850 6860718636923971
851 7030960907550087
852 7205441839637848
853 7383959724184134
854 7566867698893889
855 7754324898733155
856 7946116669558926
857 8142609520311196
858 8343984069971750
859 8550012321819387
860 8761074295430000
861 8977373845819810
862 9198669255514472
863 9425354168416466
864 9657657533097513
865 9895323556413410
866 10138759592319305
867 10388221650650296
868 10643439535287075
869 10904834365669746
870 11172691295606479
871 11446725431034943
872 11727371679620867
873 12014946541801927
874 12309150168069995
875 12610431241900409
876 12919139938034451
877 13234961237036323
878 13558357548091833
879 13889715178138083
880 14228703772352140
881 14575799375269183
882 14931427019460525
883 15295240904758514
884 15667730577797569
885 16049362531219550
886 16439775472043858
887 16839472270197506
888 17248963759405194
889 17667873176410947
890 18096716487376640
891 18536051900399997
892 18985487282573806
893 19445551418271147
894 19916853081352034
895 20398984956648820
896 20892488315032655
897 21398025851556070
898 21915175352251748
899 22444490186371651
900 22986690495692541
901 23541339556944262
902 24109002390542615
903 24690460286795042
904 25285262519330060
905 25893985250750954
906 26517474804264027
907 27155267084700759
908 27807948823514533
909 28476435450138989
910 29160250275188116
911 29859989958738751
912 30576643305243325
913 31309721958944040
914 32059831798992967
915 32828039475724183
916 33613846061960712
917 34417865874750949
918 35241248089956101
919 36083484485779916
920 36945196962194306
921 37827622115821898
922 38730243904583069
923 39653690880617593
924 40599292179035328
925 41566525626019187
926 42556025417558608
927 43569218574463710
928 44605578711649437
929 45665744581534015
930 46751246674409459
931 47861556565123823
932 48997316394735423
933 50160165950536845
934 51349577209186362
935 52566194451280631
936 53811772839620872
937 55085787486368797
938 56388883480657947
939 57722937697624988
940 59087431432842288
941 60483009170896143
942 61911676101811786
943 63372923090395878
944 64867392521797166
945 66397224776693429
946 67961924037938271
947 69562129015330745
948 71200122436730789
949 72875425941352479
950 74588672908061012
951 76342295856821372
952 78135838439025525
953 79969926969331407
954 81847151500826349
955 83767082699968966
956 85730338008924522
957 87739673058782904
958 89794691012237158
959 91895998559105300
960 94046525265064559
961 96245912781395872
962 98494755098435928
963 100796164392656254
964 103149827342150907
965 105556323228575944
966 108018955843016160
967 110537464011024371
968 113112410240536580
969 115747299276753356
970 118441929834230431
971 121196845533638751
972 124015761757639569
973 126898545512729272
974 129845719378802977
975 132861219411417418
976 135944990015945185
977 139097530547877694
978 142323008131541416
979 145621454426906810
980 148993343362594149
981 152443083896476321
982 155970805594696878
983 159576954750520051
984 163266193297627576
985 167038760205214460
986 170895071931178779
987 174840054913482036
988 178874069918466635
989 182997501393435084
990 187215552204190160
991 191528718260019251
992 195937349865438890
993 200446938641800634
994 205058129996003430
995 209771238020989149
996 214592055834768368
997 219521393765329150
998 224559527711288695
999 229712565451317789
1000 234981498789615126