0 1
1 1
2 0
3 0
4 1
5 1
6 1
7 1
8 1
9 2
10 3
11 2
12 2
13 3
14 4
15 5
16 5
17 4
18 6
19 8
20 8
21 9
22 11
23 11
24 13
25 16
26 17
27 19
28 22
29 23
30 27
31 31
32 32
33 36
34 43
35 47
36 52
37 57
38 61
39 70
40 80
41 84
42 93
43 105
44 114
45 127
46 141
47 150
48 167
49 188
50 202
51 220
52 244
53 264
54 291
55 322
56 346
57 377
58 416
59 450
60 493
61 540
62 580
63 633
64 696
65 750
66 814
67 888
68 957
69 1042
70 1138
71 1222
72 1323
73 1441
74 1553
75 1682
76 1825
77 1961
78 2121
79 2301
80 2474
81 2670
82 2888
83 3102
84 3349
85 3621
86 3883
87 4180
88 4513
89 4843
90 5213
91 5618
92 6018
93 6467
94 6966
95 7465
96 8012
97 8611
98 9219
99 9894
100 10629
101 11366
102 12177
103 13067
104 13975
105 14966
106 16036
107 17128
108 18327
109 19631
110 20962
111 22404
112 23966
113 25574
114 27321
115 29207
116 31143
117 33237
118 35500
119 37840
120 40363
121 43072
122 45871
123 48892
124 52145
125 55515
126 59128
127 63000
128 67024
129 71354
130 75991
131 80794
132 85938
133 91457
134 97204
135 103345
136 109897
137 116722
138 124021
139 131822
140 139950
141 148606
142 157835
143 167479
144 177760
145 188705
146 200123
147 212276
148 225215
149 238742
150 253121
151 268397
152 284362
153 301331
154 319366
155 338224
156 358217
157 379436
158 401651
159 425216
160 450200
161 476334
162 504014
163 533361
164 564100
165 596636
166 631065
167 667119
168 705277
169 745665
170 787955
171 832645
172 879902
173 929422
174 981751
175 1037048
176 1094953
177 1156089
178 1220680
179 1288368
180 1359782
181 1435145
182 1514103
183 1597393
184 1685278
185 1777357
186 1874391
187 1976704
188 2083922
189 2196905
190 2315967
191 2440682
192 2572012
193 2710382
194 2855364
195 3007964
196 3168607
197 3336888
198 3513966
199 3700356
200 3895587
201 4100877
202 4316839
203 4543069
204 4780907
205 5030996
206 5292885
207 5568087
208 5857382
209 6160353
210 6478598
211 6812945
212 7163014
213 7530644
214 7916800
215 8321060
216 8745369
217 9190864
218 9657220
219 10146611
220 10660253
221 11197800
222 11761661
223 12353309
224 12972484
225 13621758
226 14302698
227 15015170
228 15762109
229 16545317
230 17364643
231 18223248
232 19123213
233 20064593
234 21050901
235 22084403
236 23165182
237 24297168
238 25483027
239 26723024
240 28021392
241 29381055
242 30802505
243 32290527
244 33848451
245 35476892
246 37181026
247 38964663
248 40828780
249 42779159
250 44819971
251 46952379
252 49182828
253 51516152
254 53953895
255 56503082
256 59169032
257 61953734
258 64865106
259 67909202
260 71088329
261 74411125
262 77884473
263 81511365
264 85301409
265 89262207
266 93397227
267 97717191
268 102230807
269 106942298
270 111863403
271 117003754
272 122368447
273 127970685
274 133821338
275 139926263
276 146299962
277 152954735
278 159897640
279 167144835
280 174709964
281 182601105
282 190836275
283 199431003
284 208394786
285 217747429
286 227506170
287 237682133
288 248297517
289 259371732
290 270917466
291 282959186
292 295518735
293 308610992
294 322263223
295 336499686
296 351337291
297 366806449
298 382934596
299 399741214
300 417259867
301 435521074
302 454547262
303 474375974
304 495041483
305 516569211
306 539000629
307 562374195
308 586719217
309 612081872
310 638504933
311 666021548
312 694683174
313 724537917
314 755623588
315 787997113
316 821712010
317 856811344
318 893358707
319 931414032
320 971025866
321 1012264584
322 1055197294
323 1099879317
324 1146388980
325 1194800926
326 1245177458
327 1297605747
328 1352169490
329 1408939203
330 1468011421
331 1529479235
332 1593422426
333 1659948629
334 1729161817
335 1801151595
336 1876037224
337 1953934820
338 2034945729
339 2119202572
340 2206834467
341 2297955085
342 2392711922
343 2491249309
344 2593695200
345 2700213005
346 2810963195
347 2926089705
348 3045774428
349 3170196247
350 3299516346
351 3433936250
352 3573655345
353 3718854911
354 3869758864
355 4026588670
356 4189547076
357 4358882827
358 4534842880
359 4717654463
360 4907593199
361 5104933354
362 5309929445
363 5522887820
364 5744113692
365 5973891204
366 6212559737
367 6460458849
368 6717906746
369 6985280000
370 7262955467
371 7551288088
372 7850695725
373 8161597648
374 8484390338
375 8819536549
376 9167501407
377 9528727513
378 9903728503
379 10293021000
380 10697097969
381 11116528112
382 11551885198
383 12003719245
384 12472660636
385 12959345440
386 13464385726
387 13988480109
388 14532334944
389 15096631900
390 15682144090
391 16289654176
392 16919921036
393 17573801503
394 18252163542
395 18955850493
396 19685810316
397 20443005271
398 21228373712
399 22042965145
400 22887845023
401 23764055273
402 24672757664
403 25615133232
404 26592339496
405 27605660946
406 28656404669
407 29745856083
408 30875436865
409 32046594291
410 33260754026
411 34519487344
412 35824396375
413 37177063480
414 38579226118
415 40032655986
416 41539106821
417 43100499461
418 44718794535
419 46395936102
420 48134045907
421 49935291024
422 51801825774
423 53735995299
424 55740195604
425 57816811560
426 59968432520
427 62197706898
428 64507276057
429 66899999653
430 69378802829
431 71946607719
432 74606571846
433 77361927326
434 80215907268
435 83171995612
436 86233760391
437 89404777580
438 92688892919
439 96090045653
440 99612187872
441 103259561151
442 107036513622
443 110947414076
444 114996941227
445 119189891464
446 123531090003
447 128025696521
448 132679003220
449 137496339386
450 142483391908
451 147645995716
452 152990035132
453 158521779428
454 164247662068
455 170174176047
456 176308228199
457 182656910158
458 189227387407
459 196027269316
460 203064368903
461 210346588133
462 217882308573
463 225680139016
464 233748793024
465 242097498244
466 250735734784
467 259673108352
468 268919779064
469 278486185920
470 288382912699
471 298621140198
472 309212360684
473 320168235711
474 331501068625
475 343223505521
476 355348388272
477 367889252505
478 380860014305
479 394274813593
480 408148535815
481 422496487030
482 437334232175
483 452678141151
484 468545047314
485 484952076752
486 501917223866
487 519458997417
488 537596240170
489 556348730233
490 575736810822
491 595781203668
492 616503642701
493 637926486450
494 660072519769
495 682965617257
496 706630342178
497 731091741480
498 756376040088
499 782510219921
500 809521804247
501 837439588679
502 866293205323
503 896112895525
504 926930273530
505 958777871032
506 991688902654
507 1025698069780
508 1060841084429
509 1097154420631
510 1134676156393
511 1173445480990
512 1213502438114
513 1254888807030
514 1297647586488
515 1341822724772
516 1387460046845
517 1434606720778
518 1483310973985
519 1533623061569
520 1585594709848
521 1639278823621
522 1694730504913
523 1752006472037
524 1811164750605
525 1872265739949
526 1935371612689
527 2000545996144
528 2067855088348
529 2137367029836
530 2209151569734
531 2283281239793
532 2359830705498
533 2438876415666
534 2520497829059
535 2604776738794
536 2691796911362
537 2781645376197
538 2874411722027
539 2970187716746
540 3069068657286
541 3171152643463
542 3276540186682
543 3385335622358
544 3497646351701
545 3613582433126
546 3733258067163
547 3856790814219
548 3984301167434
549 4115914104338
550 4251758273705
551 4391965556327
552 4536672696263
553 4686020455345
554 4840153151932
555 4999220368730
556 5163376081773
557 5332778186645
558 5507590285446
559 5687980779681
560 5874122376856
561 6066193968574
562 6264379696626
563 6468868438833
564 6679855771794
565 6897543002278
566 7122136640478
567 7353850462589
568 7592904505725
569 7839524517264
570 8093944114503
571 8356403751229
572 8627150153695
573 8906438581481
574 9194531753612
575 9491699263369
576 9798219954122
577 10114380816412
578 10440476380380
579 10776811199674
580 11123698710843
581 11481460613047
582 11850429477803
583 12230947569242
584 12623366198354
585 13028048456046
586 13445368003283
587 13875708413393
588 14319466033478
589 14777048730892
590 15248875214371
591 15735378041220
592 16237002333335
593 16754205075997
594 17287458263654
595 17837247576444
596 18404071667842
597 18988445470450
598 19590898831474
599 20211975775381
600 20852237967052
601 21512263318338
602 22192645240948
603 22893996273840
604 23616946645288
605 24362143507151
606 25130254746709
607 25921967519932
608 26737987466529
609 27579042699755
610 28445882300432
611 29339275526433
612 30260016005933
613 31208920191916
614 32186826549883
615 33194599953788
616 34233130114899
617 35303330766735
618 36406144272123
619 37542540010313
620 38713513548817
621 39920091486531
622 41163329818282
623 42444313094450
624 43764159492941
625 45124019150744
626 46525073327888
627 47968539739878
628 49455670855529
629 50987753049147
630 52566112193552
631 54192111942140
632 55867152891035
633 57592678445176
634 59370173066663
635 61201161436981
636 63087214626444
637 65029948332756
638 67031022044664
639 69092145509436
640 71215076950847
641 73401622255396
642 75653641774581
643 77973048525119
644 80361807379953
645 82821942208573
646 85355534080398
647 87964720488807
648 90651702845292
649 93418744667895
650 96268170828596
651 99202375439603
652 102223820055240
653 105335032947111
654 108538617378574
655 111837249811025
656 115233679231857
657 118730735864269
658 122331329382198
659 126038448274048
660 129855168993665
661 133784654212294
662 137830152251669
663 141995006698150
664 146282654673705
665 150696626331467
666 155240554979177
667 159918175405578
668 164733323445908
669 169689946615386
670 174792102482346
671 180043958337719
672 185449802395331
673 191014042221408
674 196741204490828
675 202635946767266
676 208703056023987
677 214947448529832
678 221374182239270
679 227988455389269
680 234795606509746
681 241801127482512
682 249010662259878
683 256430007013972
684 264065123868913
685 271922139738588
686 280007346657401
687 288327216257840
688 296888398741888
689 305697723380741
690 314762213757983
691 324089086921059
692 333685754104453
693 343559836780764
694 353719165979537
695 364171783235550
696 374925957521940
697 385990184796131
698 397373189194105
699 409083940861414
700 421131655729354
701 433525797011995
702 446276094023891
703 459392542212915
704 472885404952575
705 486765233379481
706 501042866743679
707 515729434567875
708 530836377561448
709 546375448284059
710 562358713681910
711 578798577174659
712 595707779707993
713 613099402703405
714 630986891345727
715 649384056039904
716 668305075847743
717 687764523091866
718 707777365256449
719 728358968914201
720 749525125697524
721 771292054726085
722 793676407116317
723 816695293399257
724 840366286482377
725 864707426767963
726 889737251140351
727 915474796564940
728 941939605869259
729 969151758348586
730 997131874033074
731 1025901120232749
732 1055481243908709
733 1085894576670385
734 1117164042104801
735 1149313189991272
736 1182366202138737
737 1216347900622712
738 1251283783953266
739 1287200033781217
740 1324123524089634
741 1362081859478718
742 1401103382876351
743 1441217185767030
744 1482453148670643
745 1524841949916678
746 1568415077045876
747 1613204869675125
748 1659244529429568
749 1706568132565081
750 1755210675332505
751 1805208085218467
752 1856597234953902
753 1909415990531857
754 1963703223814344
755 2019498828010754
756 2076843768563626
757 2135780097305478
758 2196350969528687
759 2258600697861416
760 2322574768071683
761 2388319857914261
762 2455883894249936
763 2525316070638230
764 2596666868048394
765 2669988115388704
766 2745333009094789
767 2822756135929617
768 2902313537135152
769 2984062730123161
770 3068062733497329
771 3154374135114222
772 3243059116124553
773 3334181478399700
774 3427806716685045
775 3524002045146947
776 3622836427459782
777 3724380653388676
778 3828707368048789
779 3935891104800692
780 4046008366504197
781 4159137657776799
782 4275359521002068
783 4394756622554482
784 4517413788231823
785 4643418042584456
786 4772858700494787
787 4905827406125831
788 5042418175836555
789 5182727495387931
790 5326854362648027
791 5474900334448690
792 5626969629867535
793 5783169176991848
794 5943608663953443
795 6108400648635431
796 6277660609890327
797 6451507003174934
798 6630061377099462
799 6813448429376864
800 7001796067371141
801 7195235532009957
802 7393901458934928
803 7597931944348519
804 7807468676690346
805 8022657003351138
806 8243646002310114
807 8470588622180721
808 8703641754927180
809 8942966313659052
810 9188727381543427
811 9441094291077324
812 9700240708620529
813 9966344792758469
814 10239589280553035
815 10520161579283049
816 10808253934965589
817 11104063526234202
818 11407792563844631
819 11719648469935254
820 12039843980069119
821 12368597251190396
822 12706132052446016
823 13052677876023745
824 13408470054110377
825 13773749961986283
826 14148765138429964
827 14533769412482724
828 14929023119631202
829 15334793232414290
830 15751353497683603
831 16178984666840018
832 16617974637544941
833 17068618602276667
834 17531219293455816
835 18006087137045990
836 18493540413363510
837 18993905518211526
838 19507517129274049
839 20034718380000060
840 20575861137754880
841 21131306184082007
842 21701423402777842
843 22286592076202276
844 22887201080345897
845 23503649088095856
846 24136344885032931
847 24785707580557332
848 25452166827488264
849 26136163158539813
850 26838148214644669
851 27558584982224025
852 28297948151872929
853 29056724365173952
854 29835412470838002
855 30634523907023723
856 31454582968140941
857 32296127081416788
858 33159707214443844
859 34045888163337391
860 34955248851173541
861 35888382762590911
862 36845898255044183
863 37828418880737109
864 38836583849975681
865 39871048367156190
866 40932483978058430
867 42021579064052683
868 43139039204656285
869 44285587551925205
870 45461965357522121
871 46668932363936551
872 47907267208137887
873 49177767983728091
874 50481252662799194
875 51818559530917850
876 53190547786876397
877 54598097997610644
878 56042112566818443
879 57523516374711116
880 59043257268329963
881 60602306566405593
882 62201659742001432
883 63842336950821518
884 65525383574806606
885 67251870950490708
886 69022896938224666
887 70839586507517476
888 72703092514211255
889 74614596313444814
890 76575308389687296
891 78586469186197864
892 80649349765104814
893 82765252485379139
894 84935511887963861
895 87161495406293236
896 89444604095844125
897 91786273578915099
898 94187974809239722
899 96651214856677154
900 99177537915595545
901 101768526127652889
902 104425800425818877
903 107151021610685379
904 109945891235434917
905 112812152513364645
906 115751591466913683
907 118766037879511841
908 121857366271174565
909 125027497125004839
910 128278397910622421
911 131612084132896730
912 135030620641411008
913 138536122730606874
914 142130757266707220
915 145816744085665335
916 149596357175705010
917 153471925888260437
918 157445836430424625
919 161520533135569799
920 165698519764190799
921 169982361097465547
922 174374684302477399
923 178878180329371818
924 183495605612692523
925 188229783537819319
926 193083605941492486
927 198060034928493023
928 203162104446489846
929 208392921897056329
930 213755670075404930
931 219253608861540948
932 224890076949867356
933 230668493920323758
934 236592362053860569
935 242665268188896879
936 248890885932994915
937 255272977611710691
938 261815396260872334
939 268522087988090671
940 275397094064261753
941 282444553061470786
942 289668703374780480
943 297073885466429145
944 304664544159378350
945 312445231330103058
946 320420608316456416
947 328595448378091582
948 336974639571841883
949 345563187334488609
950 354366217121624467
951 363388977478231229
952 372636842808910923
953 382115316207693691
954 391830032736765274
955 401786762397126098
956 411991413162955620
957 422450034482879347
958 433168820465056952
959 444154113130120759
960 455412406149877369
961 466950348262033434
962 478774746757277010
963 490892571471457394
964 503310958445654403
965 516037213663543996
966 529078817314449032
967 542443427716138573
968 556138885319875095
969 570173217262329658
970 584554641569178539
971 599291571446684578
972 614392620142314902
973 629866605448589139
974 645722554300751223
975 661969707966723346
976 678617526872269388
977 695675695526295189
978 713154128062323840
979 731062973406854490
980 749412620554747512
981 768213704486186638
982 787477111702275515
983 807213985874652880
984 827435734162880902
985 848154033142375388
986 869380834854341121
987 891128373550894483
988 913409172042301941
989 936236048174422477
990 959622122030110576
991 983580822724871513
992 1008125895341566136
993 1033271408618721210
994 1059031762224993735
995 1085421694182287707
996 1112456289073967673
997 1140150985831320834
998 1168521585678522626
999 1197584260895232930
1000 1227355563149845674