0 1
1 0
2 0
3 0
4 0
5 1
6 1
7 1
8 1
9 1
10 1
11 2
12 2
13 3
14 3
15 4
16 4
17 5
18 6
19 7
20 8
21 10
22 11
23 13
24 15
25 17
26 20
27 23
28 26
29 30
30 35
31 39
32 45
33 51
34 58
35 66
36 75
37 84
38 96
39 108
40 122
41 137
42 155
43 173
44 195
45 219
46 245
47 274
48 307
49 342
50 383
51 427
52 475
53 529
54 589
55 654
56 727
57 807
58 894
59 991
60 1098
61 1214
62 1343
63 1485
64 1638
65 1809
66 1995
67 2198
68 2422
69 2667
70 2933
71 3226
72 3545
73 3893
74 4274
75 4691
76 5142
77 5637
78 6175
79 6760
80 7399
81 8095
82 8848
83 9671
84 10564
85 11533
86 12587
87 13732
88 14971
89 16319
90 17780
91 19361
92 21077
93 22936
94 24945
95 27125
96 29482
97 32029
98 34787
99 37768
100 40986
101 44466
102 48224
103 52278
104 56658
105 61384
106 66476
107 71972
108 77897
109 84277
110 91158
111 98567
112 106541
113 115130
114 124373
115 134313
116 145011
117 156513
118 168874
119 182165
120 196447
121 211782
122 228259
123 245949
124 264933
125 285313
126 307179
127 330626
128 355781
129 382749
130 411652
131 442633
132 475828
133 511378
134 549461
135 590237
136 633880
137 680599
138 730591
139 784064
140 841272
141 902445
142 967842
143 1037759
144 1112481
145 1192315
146 1277614
147 1368721
148 1466006
149 1569888
150 1680783
151 1799129
152 1925430
153 2060180
154 2203908
155 2357211
156 2520680
157 2694948
158 2880725
159 3078717
160 3289682
161 3514458
162 3753890
163 4008881
164 4280426
165 4569534
166 4877275
167 5204831
168 5553400
169 5924258
170 6318802
171 6738455
172 7184732
173 7659286
174 8163805
175 8700089
176 9270083
177 9875795
178 10519350
179 11203052
180 11929273
181 12700526
182 13519528
183 14389084
184 15312163
185 16291970
186 17331809
187 18435191
188 19605881
189 20847785
190 22165035
191 23562062
192 25043464
193 26614111
194 28279205
195 30044164
196 31914704
197 33896943
198 35997242
199 38222325
200 40579364
201 43075828
202 45719608
203 48519112
204 51483099
205 54620828
206 57942134
207 61457292
208 65177139
209 69113190
210 73277470
211 77682660
212 82342221
213 87270220
214 92481484
215 97991738
216 103817411
217 109975830
218 116485340
219 123365130
220 130635419
221 138317596
222 146434045
223 155008341
224 164065407
225 173631333
226 183733577
227 194401160
228 205664458
229 217555439
230 230107861
231 243357060
232 257340222
233 272096583
234 287667226
235 304095367
236 321426570
237 339708560
238 358991520
239 379328330
240 400774387
241 423387908
242 447230228
243 472365586
244 498861487
245 526789006
246 556222583
247 587240428
248 619924844
249 654362035
250 690642546
251 728861603
252 769118966
253 811519370
254 856172940
255 903195023
256 952706690
257 1004835194
258 1059713815
259 1117482411
260 1178287930
261 1242284252
262 1309632836
263 1380503243
264 1455073038
265 1533528470
266 1616065069
267 1702887579
268 1794210710
269 1890259790
270 1991270754
271 2097490933
272 2209179842
273 2326609156
274 2450063631
275 2579841941
276 2716256720
277 2859635588
278 3010322074
279 3168675721
280 3335073228
281 3509909452
282 3693597635
283 3886570617
284 4089282002
285 4302206434
286 4525840960
287 4760706342
288 5007347419
289 5266334630
290 5538265480
291 5823764992
292 6123487448
293 6438117981
294 6768373199
295 7115003086
296 7478792800
297 7860563461
298 8261174254
299 8681524453
300 9122554383
301 9585247750
302 10070633947
303 10579789183
304 11113839113
305 11673961401
306 12261387075
307 12877403494
308 13523357195
309 14200655529
310 14910769968
311 15655239279
312 16435671512
313 17253747646
314 18111225193
315 19009940511
316 19951812872
317 20938848555
318 21973143503
319 23056887922
320 24192370836
321 25381983201
322 26628223078
323 27933700717
324 29301142203
325 30733395234
326 32233434815
327 33804367533
328 35449437975
329 37172035171
330 38975697494
331 40864119859
332 42841160985
333 44910849016
334 47077389601
335 49345174049
336 51718785765
337 54203009367
338 56802839784
339 59523489693
340 62370399699
341 65349248556
342 68465961717
343 71726722715
344 75137984659
345 78706480008
346 82439233289
347 86343574085
348 90427148110
349 94697931535
350 99164245519
351 103834768846
352 108718554010
353 113825043502
354 119164084210
355 124745945444
356 130581337186
357 136681426538
358 143057857840
359 149722773234
360 156688831269
361 163969229475
362 171577727460
363 179528667985
364 187837002281
365 196518315956
366 205588852841
367 215065543435
368 224966033889
369 235308713060
370 246112744331
371 257398098133
372 269185582566
373 281496879015
374 294354578637
375 307782216952
376 321804313695
377 336446413811
378 351735126416
379 367698169495
380 384364415807
381 401763936826
382 419928052847
383 438889384367
384 458681901656
385 479340980831
386 500903461387
387 523407702118
388 546893643787
389 571402873645
390 596978688306
391 623666163895
392 651512228340
393 680565732039
394 710877526395
395 742500544708
396 775489881599
397 809902880929
398 845799226260
399 883241030147
400 922292932418
401 963022201379
402 1005498834141
403 1049795666440
404 1095988485889
405 1144156144539
406 1194380681618
407 1246747450255
408 1301345243654
409 1358266432323
410 1417607105707
411 1479467213616
412 1543950719637
413 1611165759341
414 1681224798826
415 1754244806035
416 1830347427512
417 1909659166045
418 1992311571905
419 2078441440342
420 2168191010427
421 2261708178519
422 2359146718924
423 2460666506277
424 2566433753904
425 2676621260090
426 2791408656820
427 2910982675832
428 3035537423392
429 3165274658458
430 3300404089440
431 3441143680766
432 3587719963839
433 3740368367912
434 3899333562139
435 4064869802877
436 4237241302622
437 4416722611507
438 4603599005061
439 4798166895510
440 5000734257062
441 5211621058699
442 5431159722652
443 5659695598277
444 5897587445073
445 6145207943404
446 6402944222497
447 6671198399293
448 6950388147221
449 7240947284393
450 7543326374413
451 7857993359660
452 8185434216453
453 8526153624571
454 8880675672378
455 9249544586121
456 9633325475942
457 10032605120728
458 10447992779719
459 10880121023533
460 11329646607382
461 11797251374101
462 12283643179621
463 12789556864150
464 13315755256814
465 13863030205727
466 14432203658020
467 15024128777161
468 15639691089103
469 16279809683090
470 16945438453843
471 17637567376505
472 18357223841451
473 19105474034821
474 19883424356459
475 20692222903060
476 21533061002207
477 22407174788824
478 23315846852709
479 24260407942771
480 25242238719035
481 26262771582367
482 27323492567365
483 28425943288782
484 29571722973245
485 30762490560884
486 31999966867255
487 33285936838771
488 34622251885437
489 36010832281555
490 37453669668671
491 38952829644248
492 40510454426823
493 42128765632810
494 43810067148659
495 45556748088462
496 47371285873990
497 49256249420539
498 51214302418130
499 53248206747161
500 55360826011071
501 57555129175671
502 59834194356040
503 62201212732726
504 64659492587337
505 67212463499744
506 69863680688522
507 72616829484726
508 75475729982682
509 78444341849535
510 81526769283261
511 84727266164905
512 88050241386663
513 91500264345005
514 95082070647193
515 98800568012110
516 102660842354769
517 106668164105266
518 110827994742217
519 115145993530782
520 119628024517798
521 124280163764057
522 129108706804132
523 134120176388113
524 139321330485729
525 144719170542927
526 150320950048008
527 156134183387878
528 162166654984073
529 168426428769064
530 174921857982680
531 181661595278960
532 188654603206837
533 195910165043948
534 203437895974865
535 211247754679636
536 219350055312162
537 227755479860401
538 236475090956792
539 245520345119255
540 254903106414700
541 264635660617112
542 274730729840844
543 285201487641209
544 296061574658540
545 307325114786206
546 319006731855591
547 331121566918225
548 343685296105271
549 356714149059011
550 370224928019904
551 384235027550215
552 398762454890082
553 413825851033200
554 429444512504423
555 445638413835885
556 462428230833413
557 479835364616719
558 497881966430488
559 516590963323843
560 535986084681862
561 556091889608242
562 576933795261783
563 598538106130891
564 620932044247707
565 644143780449349
566 668202466672058
567 693138269282181
568 718982403556374
569 745767169299402
570 773525987604871
571 802293438877925
572 832105302110161
573 862998595414099
574 895011617943456
575 928183993191055
576 962556713674800
577 998172187145244
578 1035074284308235
579 1073308388077149
580 1112921444495013
581 1153962015323125
582 1196480332314460
583 1240528353319459
584 1286159820224742
585 1333430318746464
586 1382397340234623
587 1433120345492907
588 1485660830639221
589 1540082395173473
590 1596450812260381
591 1654834101257816
592 1715302602667302
593 1777929055518175
594 1842788677222342
595 1909959246086073
596 1979521186495728
597 2051557656820822
598 2126154640231191
599 2203401038451989
600 2283388768505771
601 2366212862651045
602 2451971571547617
603 2540766470704610
604 2632702570434602
605 2727888429350523
606 2826436271469834
607 2928462107163775
608 3034085857995328
609 3143431485520632
610 3256627124305824
611 3373805219212292
612 3495102667035319
613 3620660962763534
614 3750626350522920
615 3885149979300724
616 4024388063734493
617 4168502050041238
618 4317658787193323
619 4472030703646247
620 4631795989704537
621 4797138785646179
622 4968249375931479
623 5145324389594848
624 5328567006955912
625 5518187172996911
626 5714401817519941
627 5917435082237210
628 6127518555163758
629 6344891512443767
630 6569801167780530
631 6802502929865525
632 7043260667956052
633 7292346985790030
634 7550043504262304
635 7816641153030594
636 8092440471261905
637 8377751917973742
638 8672896192159014
639 8978204562930422
640 9294019210169797
641 9620693575895776
642 9958592726611935
643 10308093727154513
644 10669586026280767
645 11043471854287535
646 11430166633217271
647 11830099399921852
648 12243713242303928
649 12671465749334919
650 13113829475150883
651 13571292417580593
652 14044358511749397
653 14533548139093737
654 15039398652179551
655 15562464916014590
656 16103319866228358
657 16662555084554335
658 17240781392354721
659 17838629462604833
660 18456750450815631
661 19095816645690715
662 19756522139981573
663 20439583522067148
664 21145740589116028
665 21875757082344179
666 22630421444948563
667 23410547603640643
668 24216975774346629
669 25050573292714925
670 25912235470424317
671 26802886477920778
672 27723480254287855
673 28675001445319342
674 29658466370489969
675 30674924019597576
676 31725457080229258
677 32811182996819829
678 33933255062151168
679 35092863542536343
680 36291236837534759
681 37529642675130763
682 38809389343717562
683 40131826961817636
684 41498348786564681
685 42910392562393222
686 44369441910962148
687 45877027763436728
688 47434729836688460
689 49044178154543505
690 50707054615311371
691 52425094607277645
692 54200088673404803
693 56033884226588923
694 57928387317292551
695 59885564454919044
696 61907444484405439
697 63996120520000480
698 66153751937725421
699 68382566428136634
700 70684862111513296
701 73063009717114459
702 75519454828277852
703 78056720195653271
704 80677408120376223
705 83384202909118717
706 86179873403496868
707 89067275585814878
708 92049355263261873
709 95129150833244582
710 98309796132023114
711 101594523368964184
712 104986666149313824
713 108489662587861199
714 112107058516024493
715 115842510785496190
716 119699790671044660
717 123682787375237067
718 127795511638476156
719 132042099457194111
720 136426815913221265
721 140954059118001321
722 145628364274763066
723 150454407861941005
724 155437011941820672
725 160581148597806534
726 165891944503906495
727 171374685630736797
728 177034822091758480
729 182877973133668624
730 188909932275603590
731 195136672601208866
732 201564352207855271
733 208199319818041460
734 215048120557412638
735 222117501904060014
736 229414419814559078
737 236946045031582792
738 244719769578172432
739 252743213444578900
740 261024231472949591
741 269570920445401200
742 278391626381882304
743 287494952053577982
744 296889764717895554
745 306585204081964852
746 316590690500927198
747 326915933417591786
748 337570940050967157
749 348566024340510216
750 359911816153255172
751 371619270761955592
752 383699678601697536
753 396164675312779986
754 409026252078675078
755 422296766267192152
756 435988952383333145
757 450115933343386226
758 464691232079104900
759 479728783481212098
760 495242946692569400
761 511248517760646994
762 527760742659348482
763 544795330691389824
764 562368468281725763
765 580496833172958902
766 599197609034865120
767 618488500499457812
768 638387748633481750
769 658914146861484742
770 680087057351894516
771 701926427879032440
772 724452809175308891
773 747687372787118278
774 771651929448496014
775 796368947987967164
776 821861574783291806
777 848153653779393408
778 875269747086183500
779 903235156172277016
780 932075943671208837
781 961818955818259042
782 992491845535277109
783 1024123096181551725
784 1056742045990345192
785 1090378913209993457
786 1125064821969179067
787 1160831828887630798
788 1197712950452788850
789 1235742191183736545
790 1274954572605419251
791 1315386163055468972
792 1357074108346768831
793 1400056663310691369
794 1444373224245259780
795 1490064362293349901
796 1537171857777942056
797 1585738735520762260
798 1635809301171579444
799 1687429178577416654
800 1740645348220277172
801 1795506186752984686
802 1852061507664827306
803 1910362603108056396
804 1970462286917368161
805 2032414938856686353
806 2096276550126955498
807 2162104770169809237
808 2229958954804276575
809 2299900215733117502
810 2371991471456612079
811 2446297499634049103
812 2522884990932623915
813 2601822604404774450
814 2683181024437539903
815 2767033019317024443
816 2853453501452469754
817 2942519589307129907
818 3034310671082682943
819 3128908470205446544
820 3226397112665492144
821 3326863196259350184
822 3430395861788644702
823 3537086866269971756
824 3647030658211000716
825 3760324455009539132
826 3877068322535444648
827 3997365256954999870
828 4121321268859254439
829 4249045469761162195
830 4380650161026142812
831 4516250925302731521
832 4655966720523489109
833 4799919976546226060
834 4948236694507788741
835 5101046548966354779
836 5258482992908165109
837 5420683365696978764
838 5587789004048441147
839 5759945356111650077
840 5937302098742731798
841 6120013258059373715
842 6308237333365470273
843 6502137424537752292
844 6701881362970652460
845 6907641846175990992
846 7119596576136989746
847 7337928401520761434
848 7562825463853889636
849 7794481347768869078
850 8033095235434080004
851 8278872065280602262
852 8532022695142566136
853 8792764069932929598
854 9061319393977384312
855 9337918308132733752
856 9622797071821597204
857 9916198750116296336
858 10218373406008693788
859 10529578298008606492
860 10850078083214620820
861 11180145026005352664
862 11520059212505406398
863 11870108770981715516
864 12230590098330493146
865 12601808092821606794
866 12984076393268876724
867 13377717624799689016
868 13783063651404304444
869 14200455835447213606
870 14630245304328144732
871 15072793224487764628
872 15528471082955383302
873 15997660976641624434
874 16480755909586936860
875 16978160098379412162
876 17490289285961463079
877 18017571064053333381
878 18560445204424352130
879 19119363999249410567
880 19694792610797085035
881 20287209430699169014
882 20897106449058443435
883 21524989633661031185
884 22171379319563456911
885 22836810609332130312
886 23521833784223112559
887 24227014726594263651
888 24952935353850041994
889 25700194064230040871
890 26469406194757080399
891 27261204491669479666
892 28076239593673656742
893 28915180528358481326
894 29778715222122295036
895 30667551023975789846
896 31582415243589814298
897 32524055703967393932
898 33493241309132337618
899 34490762627233338680
900 35517432489473469189
901 36574086605288932337
902 37661584194208178332
903 38780808634834313899
904 39932668131408651573
905 41118096398421238380
906 42338053363746941217
907 43593525890801588889
908 44885528520221484677
909 46215104231583328200
910 47583325225698577187
911 48991293728025997545
912 50440142813760925266
913 51931037255177906725
914 53465174391814085205
915 55043785024096596352
916 56668134331036628370
917 58339522812624555800
918 60059287257577660924
919 61828801737112694620
920 63649478625428410114
921 65522769647601625472
922 67450166955622538336
923 69433204233309124372
924 71473457830860294465
925 73572547929831177278
926 75732139739329343535
927 77953944724252147893
928 80239721866410696346
929 82591278959402851183
930 85010473938120666407
931 87499216243804753276
932 90059468225576539632
933 92693246579404115983
934 95402623825486377421
935 98189729825060309152
936 101056753337662889175
937 104005943619910133997
938 107039612066877765436
939 110160133897196647527
940 113369949883009368618
941 116671568125958270798
942 120067565880406086318
943 123560591425125903654
944 127153365984723251416
945 130848685702086284364
946 134649423663198145142
947 138558531975673933926
948 142579043902420435083
949 146714076051857555610
950 150966830626171251002
951 155340597729106159956
952 159838757734849875024
953 164464783719594259868
954 169222243957400608608
955 174114804482042248792
956 179146231716534563513
957 184320395172106937080
958 189641270218421269418
959 195112940926881198878
960 200739602988924071374
961 206525566711241430702
962 212475260089916649366
963 218593231965519844902
964 224884155261257828955
965 231352830306323279298
966 238004188246642768256
967 244843294545285016762
968 251875352574841069994
969 259105707304147750160
970 266539849081791901778
971 274183417518887474418
972 282042205473681664569
973 290122163140617250840
974 298429402246537321142
975 306970200356787607040
976 315751005294047674866
977 324778439672786154756
978 334059305552309412826
979 343600589211454609318
980 353409466048047244155
981 363493305606323131792
982 373859676735602174274
983 384516352883576093980
984 395471317527658169308
985 406732769747936749176
986 418309129945355201730
987 430209045708833306550
988 442441397835145607177
989 455015306505459676992
990 467940137622536544524
991 481225509312703323676
992 494881298596802568392
993 508917648234429625772
994 523344973745884892218
995 538173970616369908920
996 553415621687071024373
997 569081204737898366998
998 585182300266758041244
999 601730799470358889042
1000 618738912431688158066