0 1
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 1
9 2
10 2
11 3
12 3
13 4
14 4
15 6
16 6
17 8
18 9
19 11
20 12
21 15
22 17
23 20
24 23
25 27
26 31
27 36
28 41
29 47
30 55
31 62
32 71
33 81
34 93
35 105
36 120
37 135
38 154
39 174
40 197
41 221
42 251
43 281
44 317
45 356
46 400
47 447
48 502
49 561
50 628
51 701
52 782
53 871
54 972
55 1081
56 1202
57 1336
58 1483
59 1645
60 1825
61 2021
62 2237
63 2476
64 2736
65 3023
66 3338
67 3683
68 4060
69 4476
70 4928
71 5424
72 5967
73 6560
74 7207
75 7917
76 8687
77 9530
78 10449
79 11451
80 12541
81 13732
82 15023
83 16431
84 17963
85 19628
86 21435
87 23403
88 25535
89 27852
90 30367
91 33093
92 36048
93 39255
94 42725
95 46486
96 50559
97 54965
98 59732
99 64893
100 70468
101 76495
102 83011
103 90046
104 97644
105 105850
106 114700
107 124250
108 134555
109 145661
110 157634
111 170539
112 184438
113 199407
114 215531
115 232880
116 251552
117 271643
118 293247
119 316478
120 341458
121 368295
122 397133
123 428114
124 461380
125 497095
126 535438
127 576575
128 620714
129 668062
130 718831
131 773259
132 831609
133 894127
134 961113
135 1032870
136 1109708
137 1191977
138 1280052
139 1374301
140 1475152
141 1583044
142 1698433
143 1821823
144 1953753
145 2094760
146 2245456
147 2406480
148 2578487
149 2762203
150 2958397
151 3167850
152 3391436
153 3630068
154 3884691
155 4156340
156 4446110
157 4755128
158 5084633
159 5435928
160 5810362
161 6209406
162 6634615
163 7087598
164 7570108
165 8083992
166 8631165
167 9213712
168 9833826
169 10493792
170 11196077
171 11943286
172 12738132
173 13583544
174 14482607
175 15438544
176 16454815
177 17535081
178 18683155
179 19903141
180 21199356
181 22576321
182 24038878
183 25592136
184 27241436
185 28992496
186 30851337
187 32824275
188 34918044
189 37139755
190 39496844
191 41997253
192 44649345
193 47461896
194 50444240
195 53606226
196 56958168
197 60511054
198 64276447
199 68266489
200 72494068
201 76972771
202 81716850
203 86741437
204 92062463
205 97696656
206 103661742
207 109976404
208 116660238
209 123734018
210 131219604
211 139139952
212 147519360
213 156383410
214 165758954
215 175674398
216 186159632
217 197246050
218 208966824
219 221356868
220 234452830
221 248293426
222 262919385
223 278373471
224 294700826
225 311948929
226 330167622
227 349409501
228 369729865
229 391186772
230 413841438
231 437758220
232 463004680
233 489652022
234 517775087
235 547452427
236 578766792
237 611805143
238 646658746
239 683423697
240 722200957
241 763096468
242 806221748
243 851693916
244 899635874
245 950176914
246 1003452811
247 1059606014
248 1118786331
249 1181151041
250 1246865129
251 1316102031
252 1389043810
253 1465881405
254 1546815486
255 1632056626
256 1721825656
257 1816354564
258 1915886755
259 2020677434
260 2130994620
261 2247119446
262 2369346651
263 2497985654
264 2633360968
265 2775812722
266 2925697905
267 3083390822
268 3249283748
269 3423788260
270 3607335823
271 3800378512
272 4003390552
273 4216868946
274 4441334385
275 4677332874
276 4925436562
277 5186244744
278 5460385705
279 5748517662
280 6051329948
281 6369545040
282 6703919709
283 7055246338
284 7424355230
285 7812115886
286 8219438595
287 8647276959
288 9096629421
289 9568541064
290 10064106440
291 10584471334
292 11130834867
293 11704452611
294 12306638679
295 12938768078
296 13602280248
297 14298681442
298 15029547453
299 15796527539
300 16601347183
301 17445811211
302 18331808201
303 19261313636
304 20236393496
305 21259209151
306 22332021022
307 23457192677
308 24637196308
309 25874616930
310 27172157043
311 28532642773
312 29959028707
313 31454403175
314 33021995161
315 34665179790
316 36387484384
317 38192596201
318 40084368696
319 42066828433
320 44144183708
321 46320831756
322 48601366581
323 50990588639
324 53493513039
325 56115378435
326 58861657893
327 61738068250
328 64750580178
329 67905430405
330 71209132309
331 74668487392
332 78290598960
333 82082884187
334 86053087095
335 90209293908
336 94559946750
337 99113858383
338 103880229385
339 108868663742
340 114089185464
341 119552257923
342 125268801501
343 131250212408
344 137508384358
345 144055728564
346 150905195006
347 158070296800
348 165565132769
349 173404411543
350 181603478808
351 190178342931
352 199145702120
353 208522975037
354 218328329729
355 228580714290
356 239299891196
357 250506470040
358 262221942050
359 274468718678
360 287270168455
361 300650656013
362 314635585300
363 329251441219
364 344525833550
365 360487545431
366 377166580301
367 394594211420
368 412803036170
369 431827029016
370 451701597172
371 472463641568
372 494151616455
373 516805592075
374 540467322968
375 565180315085
376 590989896261
377 617943292826
378 646089705053
379 675480386447
380 706168729502
381 738210350637
382 771663179263
383 806587553862
384 843046317463
385 881104917657
386 920831514234
387 962297086485
388 1005575545443
389 1050743854476
390 1097882149693
391 1147073866013
392 1198405872127
393 1251968605684
394 1307856214701
395 1366166708603
396 1427002109939
397 1490468612968
398 1556676752655
399 1625741574855
400 1697782814017
401 1772925082308
402 1851298060401
403 1933036696587
404 2018281418307
405 2107178345918
406 2199879515759
407 2296543116695
408 2397333729543
409 2502422576862
410 2611987787325
411 2726214663871
412 2845295963291
413 2969432191664
414 3098831904533
415 3233712019651
416 3374298147149
417 3520824925386
418 3673536370731
419 3832686246377
420 3998538437939
421 4171367344564
422 4351458290829
423 4539107946619
424 4734624764331
425 4938329438609
426 5150555375744
427 5371649182109
428 5601971177296
429 5841895918548
430 6091812746260
431 6352126356598
432 6623257387231
433 6905643026370
434 7199737651579
435 7506013483643
436 7824961266461
437 8157090979419
438 8502932567200
439 8863036698387
440 9237975559684
441 9628343670206
442 10034758727713
443 10457862493787
444 10898321702135
445 11356829002103
446 11834103945149
447 12330893997570
448 12847975592294
449 13386155227797
450 13946270596910
451 14529191758953
452 15135822363674
453 15767100908964
454 16424002046791
455 17107537945781
456 17818759692395
457 18558758745299
458 19328668452097
459 20129665609654
460 20962972083324
461 21829856494829
462 22731635959340
463 23669677887683
464 24645401864196
465 25660281579828
466 26715846837641
467 27813685641311
468 28955446345917
469 30142839888817
470 31377642111863
471 32661696153666
472 33996914930554
473 35385283717911
474 36828862810302
475 38329790279565
476 39890284843658
477 41512648823645
478 43199271209168
479 44952630845831
480 46775299721242
481 48669946371191
482 50639339420074
483 52686351231553
484 54813961692280
485 57025262143251
486 59323459434620
487 61711880127553
488 64193974858682
489 66773322842439
490 69453636535926
491 72238766483019
492 75132706312260
493 78139597914365
494 81263736817330
495 84509577732710
496 87881740300813
497 91385015053349
498 95024369566789
499 98804954835623
500 102732111885061
501 106811378596210
502 111048496774170
503 115449419479887
504 120020318598408
505 124767592675415
506 129697875044562
507 134818042217452
508 140135222570019
509 145656805349279
510 151390449971783
511 157344095649631
512 163525971369345
513 169944606194540
514 176608839930454
515 183527834177015
516 190711083741432
517 198168428450271
518 205910065389410
519 213946561542892
520 222288866872567
521 230948327869323
522 239936701546349
523 249266169918895
524 258949355003527
525 268999334306984
526 279429656852140
527 290254359775991
528 301487985469802
529 313145599311991
530 325242808030688
531 337795778666838
532 350821258190910
533 364336593813012
534 378359753957545
535 392909349958596
536 408004658518999
537 423665644904349
538 439912986931657
539 456768099798891
540 474253161726862
541 492391140477513
542 511205820797636
543 530721832760464
544 550964681073240
545 571960775403318
546 593737461696435
547 616323054559434
548 639746870763811
549 664039263845217
550 689231659875495
551 715356594468440
552 742447750995353
553 770540000092211
554 799669440524327
555 829873441386100
556 861190685723495
557 893661215649919
558 927326478934911
559 962229377159728
560 998414315515275
561 1035927254224961
562 1074815761692271
563 1115129069454734
564 1156918128929569
565 1200235670057591
566 1245136261933841
567 1291676375413072
568 1339914447804081
569 1389910949748751
570 1441728454276929
571 1495431708160106
572 1551087705666535
573 1608765764713501
574 1668537605548327
575 1730477432068980
576 1794662015784961
577 1861170782559343
578 1930085902251691
579 2001492381268204
580 2075478158169813
581 2152134202468369
582 2231554616622695
583 2313836741396608
584 2399081264719755
585 2487392334069589
586 2578877672549083
587 2673648698812366
588 2771820650863963
589 2873512713919937
590 2978848152495004
591 3087954446750723
592 3200963433306523
593 3318011450691648
594 3439239489482723
595 3564793347343889
596 3694823789163030
597 3829486712338997
598 3968943317453533
599 4113360284538062
600 4262909955001499
601 4417770519471867
602 4578126211778808
603 4744167509156599
604 4916091338940373
605 5094101292001568
606 5278407843017451
607 5469228577868385
608 5666788428429930
609 5871319914871155
610 6083063395775658
611 6302267326376067
612 6529188525030647
613 6764092448284166
614 7007253474828744
615 7258955198513016
616 7519490730769812
617 7789163012804772
618 8068285137716243
619 8357180682946971
620 8656184053439030
621 8965640835687417
622 9285908163124802
623 9617355093241095
624 9960362996660449
625 10315325958643090
626 10682651193451420
627 11062759471832058
628 11456085562119670
629 11863078685440678
630 12284202985300471
631 12719938012102735
632 13170779223119810
633 13637238498233797
634 14119844672042834
635 14619144082896119
636 15135701139217957
637 15670098903763772
638 16222939696421318
639 16794845715961016
640 17386459681431702
641 17998445493869518
642 18631488918770949
643 19286298290084935
644 19963605236450564
645 20664165430183311
646 21388759359829206
647 22138193127076365
648 22913299268584695
649 23714937603622454
650 24543996108368154
651 25401391817502445
652 26288071754053325
653 27205013888428656
654 28153228127330434
655 29133757333595183
656 30147678377977755
657 31196103223648072
658 32280180044534272
659 33401094378619423
660 34560070317043989
661 35758371730245050
662 36997303532336294
663 38278212984671981
664 39602491039931659
665 40971573728034894
666 42386943584930136
667 43850131125707791
668 45362716363462657
669 46926330375059104
670 48542656915372880
671 50213434081561421
672 51940456028634484
673 53725574738034267
674 55570701840914286
675 57477810497518354
676 59448937334517113
677 61486184442139171
678 63591721432641137
679 65767787562133919
680 68016693917764017
681 70340825671950592
682 72742644405868730
683 75224690504353979
684 77789585624099440
685 80440035237523985
686 83178831254679710
687 86008854725254364
688 88933078623253141
689 91954570716936727
690 95076496526273519
691 98302122370714373
692 101634818510093263
693 105078062381132428
694 108635441932603922
695 112310659062196689
696 116107533157810242
697 120030004746589403
698 124082139255017972
699 128268130883055678
700 132592306595918735
701 137059130237114939
702 141673206766003273
703 146439286623789905
704 151362270231889519
705 156447212626233176
706 161699328231774720
707 167123995781468149
708 172726763383638096
709 178513353742363299
710 184489669535519982
711 190661798954779062
712 197036021412575697
713 203618813421105781
714 210416854648047607
715 217437034154460374
716 224686456820358484
717 232172449963098266
718 239902570154500649
719 247884610242690301
720 256126606584265925
721 264636846493238388
722 273423875913239222
723 282496507319135116
724 291863827855041937
725 301535207715807855
726 311520308778669561
727 321829093492677802
728 332471834033579152
729 343459121731475158
730 354801876779510085
731 366511358231945663
732 378599174299613751
733 391077292951710084
734 403958052833016228
735 417254174505268880
736 430978772022414349
737 445145364849624252
738 459767890135585070
739 474860715348638914
740 490438651287508669
741 506516965476983992
742 523111395960054736
743 540238165498156882
744 557913996190845145
745 576156124527366052
746 594982316882809502
747 614410885471169768
748 634460704768862711
749 655151228422475068
750 676502506654182370
751 698535204179547378
752 721270618652664693
753 744730699653290202
754 768938068231930250
755 793916037029147744
756 819688630985030681
757 846280608656166212
758 873717484157779978
759 902025549748404250
760 931231899075902545
761 961364451104033220
762 992451974738453382
763 1024524114172601922
764 1057611414974295163
765 1091745350933605896
766 1126958351694213602
767 1163283831190847636
768 1200756216915207513
769 1239410980034443644
770 1279284666386759636
771 1320414928378490252
772 1362840557808790641
773 1406601519648603020
774 1451738986800390530
775 1498295375866999604
776 1546314383958600697
777 1595841026566511686
778 1646921676534679514
779 1699604104160244180
780 1753937518454500643
781 1809972609597652450
782 1867761592621460609
783 1927358252353828741
784 1988817989661554029
785 2052197869028252499
786 2117556667504456176
787 2184954925069182523
788 2254454996443134042
789 2326121104393730002
790 2400019394574598318
791 2476217991943099770
792 2554787058799557681
793 2635798854494427914
794 2719327796850679031
795 2805450525348818873
796 2894245966124710887
797 2985795398831453629
798 3080182525416839224
799 3177493540870766555
800 3277817205998219228
801 3381244922273746946
802 3487870808836406750
803 3597791781685473050
804 3711107635137645333
805 3827921125609671039
806 3948338057791782804
807 4072467373277865633
808 4200421241721644736
809 4332315154589803855
810 4468268021583567577
811 4608402269803858340
812 4752843945736900490
813 4901722820137891952
814 5055172495894151982
815 5213330518951073546
816 5376338492385093669
817 5544342193711904357
818 5717491695520222846
819 5895941489522470987
820 6079850614117961898
821 6269382785566480091
822 6464706532871327645
823 6665995336475418300
824 6873427770876492860
825 7087187651268889316
826 7307464184324089350
827 7534452123224971626
828 7768351927070255155
829 8009369924770701327
830 8257718483561587460
831 8513616182257731391
832 8777287989382743548
833 9048965446307388255
834 9328886855533931553
835 9617297474269086300
836 9914449713431654218
837 10220603342243204824
838 10536025698556229888
839 10860991905078004856
840 11195785091650896907
841 11540696623756352479
842 11896026337413911420
843 12262082780649402369
844 12639183461713384258
845 13027655104235364707
846 13427833909502460019
847 13840065826058513726
848 14264706826824542096
849 14702123193944860070
850 15152691811571069750
851 15616800466801363696
852 16094848158996455772
853 16587245417701798676
854 17094414629411464316
855 17616790373413336014
856 18154819766964163340
857 18708962820049225934
858 19279692799986078100
859 19867496606141340244
860 20472875155036218024
861 21096343776121649000
862 21738432618514100186
863 22399687068990322008
864 23080668181545113966
865 23781953118826959458
866 24504135605774283122
867 25247826395781404532
868 26013653749734797590
869 26802263928268820400
870 27614321697597021456
871 28450510849287453644
872 29311534734359687746
873 30198116812088838040
874 31111001213915081592
875 32050953322867176790
876 33018760368916846381
877 34015232040694957815
878 35041201114011288990
879 36097524097628822729
880 37185081896758548114
881 38304780494752502395
882 39457551653482795565
883 40644353632910441752
884 41866171930360541946
885 43124020040031299326
886 44418940233281555994
887 45752004360255294836
888 47124314673413498905
889 48537004673562171183
890 49991239978980192958
891 51488219218263743317
892 53029174947523698736
893 54615374592588522197
894 56248121416879375435
895 57928755515645269512
896 59658654837263471040
897 61439236232325875258
898 63271956531254632654
899 65158313651209128526
900 67099847733063283487
901 69098142309256326269
902 71154825503340515950
903 73271571262067652579
904 75450100620882120762
905 77692183003710170717
906 79999637557955119549
907 82374334525635902788
908 84818196651630136250
909 87333200630004566580
910 89921378589445518404
911 92584819618827586434
912 95325671333982409943
913 98146141486761234925
914 101048499617512662392
915 104035078752122593897
916 107108277144797553636
917 110270560067802462525
918 113524461649391746129
919 116872586761209290972
920 120317612956465038484
921 123862292460226181272
922 127509454213200199260
923 131262005970421818992
924 135122936456288704579
925 139095317577432802750
926 143182306694951881871
927 147387148957561272265
928 151713179697270990811
929 156163826889234028461
930 160742613677450009942
931 165453160968056901169
932 170299190091987235978
933 175284525538806967166
934 180413097763607043828
935 185688946068865062428
936 191116221563239428807
937 196699190199314249980
938 202442235892364142857
939 208349863722256956679
940 214426703220672257793
941 220677511745868404795
942 227107177947283851754
943 233720725322322551181
944 240523315867732620034
945 247520253828044555162
946 254716989543604231460
947 262119123400799837580
948 269732409887143686499
949 277562761753943839974
950 285616254289369396144
951 293899129704780093882
952 302417801637270310107
953 311178859771451815478
954 320189074583571859610
955 329455402211148408748
956 338984989451384438537
957 348785178891701196948
958 358863514175821878026
959 369227745408923447670
960 379885834705458634887
961 390845961883348367782
962 402116530308337918784
963 413706172892401043780
964 425623758250181900329
965 437878397017564710000
966 450479448336559417622
967 463436526510804861664
968 476759507836098898949
969 490458537610471029458
970 504544037328434670034
971 519026712064172491180
972 533917558048522734563
973 549227870444765001000
974 564969251328329222920
975 581153617875675081458
976 597793210767729339435
977 614900602813403405596
978 632488707798846733968
979 650570789568242216358
980 669160471342094919021
981 688271745279109286548
982 707918982287911587100
983 728116942095030703298
984 748880783575705413463
985 770226075354259880968
986 792168806680957376004
987 814725398592409400530
988 837912715362803776485
989 861748076253396426168
990 886249267567891746254
991 911434555021536630226
992 937322696431948175569
993 963932954739889302764
994 991285111368421436742
995 1019399479929073232596
996 1048296920283873592765
997 1077998852972327992770
998 1108527274012642933462
999 1139904770086728797962
1000 1172154534118759182439