0 0
1 1
2 0
3 1
4 2
5 2
6 3
7 4
8 6
9 7
10 10
11 12
12 16
13 20
14 25
15 31
16 39
17 47
18 58
19 71
20 85
21 103
22 124
23 148
24 176
25 210
26 248
27 293
28 345
29 405
30 474
31 555
32 645
33 751
34 872
35 1009
36 1166
37 1346
38 1549
39 1781
40 2044
41 2341
42 2678
43 3060
44 3488
45 3973
46 4520
47 5132
48 5822
49 6597
50 7464
51 8436
52 9525
53 10740
54 12099
55 13616
56 15305
57 17188
58 19286
59 21615
60 24206
61 27084
62 30274
63 33813
64 37736
65 42074
66 46878
67 52189
68 58054
69 64532
70 71682
71 79562
72 88249
73 97819
74 108348
75 119934
76 132675
77 146669
78 162043
79 178919
80 197428
81 217727
82 239975
83 264339
84 291018
85 320215
86 352143
87 387053
88 425204
89 466867
90 512357
91 562003
92 616148
93 675190
94 739540
95 809636
96 885974
97 969072
98 1059482
99 1157824
100 1264748
101 1380947
102 1507193
103 1644303
104 1793140
105 1954669
106 2129905
107 2319929
108 2525938
109 2749195
110 2991045
111 3252973
112 3536544
113 3843433
114 4175469
115 4534597
116 4922886
117 5342597
118 5796130
119 6286042
120 6815119
121 7386317
122 8002788
123 8667958
124 9385461
125 10159175
126 10993300
127 11892299
128 12860930
129 13904336
130 15027982
131 16237697
132 17539764
133 18940868
134 20448128
135 22069213
136 23812278
137 25686006
138 27699740
139 29863407
140 32187584
141 34683626
142 37363602
143 40240369
144 43327706
145 46640262
146 50193633
147 54004516
148 58090663
149 62470956
150 67165601
151 72196066
152 77585185
153 83357364
154 89538527
155 96156242
156 103239942
157 110820885
158 118932302
159 127609634
160 136890518
161 146814943
162 157425530
163 168767524
164 180888980
165 193841077
166 207678130
167 222457800
168 238241464
169 255094225
170 273085184
171 292287834
172 312780114
173 334644715
174 357969524
175 382847720
176 409378124
177 437665700
178 467821705
179 499964075
180 534218020
181 570716200
182 609599195
183 651016175
184 695125124
185 742093408
186 792098517
187 845328373
188 901981985
189 962270287
190 1026416550
191 1094657117
192 1167242387
193 1244437309
194 1326522246
195 1413794099
196 1506566917
197 1605172903
198 1709963704
199 1821311147
200 1939608425
201 2065271563
202 2198740316
203 2340479559
204 2490980943
205 2650764011
206 2820377788
207 3000402695
208 3191451889
209 3394173095
210 3609250828
211 3837407970
212 4079407912
213 4336057108
214 4608206934
215 4896756204
216 5202654070
217 5526902260
218 5870557980
219 6234737240
220 6620617522
221 7029441124
222 7462518994
223 7921233877
224 8407044175
225 8921488379
226 9466188742
227 10042855773
228 10653293321
229 11299402881
230 11983188808
231 12706764147
232 13472355687
233 14282309993
234 15139100086
235 16045331385
236 17003748645
237 18017243659
238 19088862182
239 20221811939
240 21419471485
241 22685398269
242 24023337872
243 25437234203
244 26931238845
245 28509721759
246 30177282952
247 31938763359
248 33799257182
249 35764125266
250 37839007761
251 40029838297
252 42342859368
253 44784637000
254 47362077045
255 50082442879
256 52953372332
257 55982896474
258 59179459899
259 62551940291
260 66109670050
261 69862459525
262 73820619632
263 77994986700
264 82396949090
265 87038473315
266 91932132548
267 97091137148
268 102529364752
269 108261392991
270 114302534476
271 120668871426
272 127377293206
273 134445536403
274 141892224620
275 149736911560
276 158000126858
277 166703421837
278 175869418884
279 185521863842
280 195685678616
281 206387017663
282 217653327940
283 229513409258
284 241997478918
285 255137240273
286 268965951884
287 283518501492
288 298831484343
289 314943282394
290 331894148935
291 349726297982
292 368483994997
293 388213653572
294 408963937447
295 430785864340
296 453732916323
297 477861156250
298 503229346457
299 529899074726
300 557934887103
301 587404423472
302 618378561298
303 650931566999
304 685141250742
305 721089130370
306 758860603834
307 798545125847
308 840236394714
309 884032548658
310 930036367324
311 978355484551
312 1029102611864
313 1082395768140
314 1138358521802
315 1197120245155
316 1258816375936
317 1323588692932
318 1391585605232
319 1462962449915
320 1537881805608
321 1616513821186
322 1699036554546
323 1785636329017
324 1876508106802
325 1971855874264
326 2071893046832
327 2176842893143
328 2286938972916
329 2402425596772
330 2523558307746
331 2650604378620
332 2783843333929
333 2923567496283
334 3070082550984
335 3223708138340
336 3384778473217
337 3553642985773
338 3730666993182
339 3916232401934
340 4110738434611
341 4314602391259
342 4528260445212
343 4752168466994
344 4986802886931
345 5232661596583
346 5490264882239
347 5760156401869
348 6042904205678
349 6339101793267
350 6649369219641
351 6974354250033
352 7314733556674
353 7671213970245
354 8044533786127
355 8435464118605
356 8844810316200
357 9273413438683
358 9722151788629
359 10191942511433
360 10683743264736
361 11198553949697
362 11737418519139
363 12301426863549
364 12891716767308
365 13509475951175
366 14155944202017
367 14832415582369
368 15540240736550
369 16280829294701
370 17055652367387
371 17866245148263
372 18714209626726
373 19601217403051
374 20529012624565
375 21499415045325
376 22514323201576
377 23575717722908
378 24685664781906
379 25846319674586
380 27059930552950
381 28328842312708
382 29655500628778
383 31042456161126
384 32492368934470
385 34008012884916
386 35592280597100
387 37248188236376
388 38978880669148
389 40787636796396
390 42677875105954
391 44653159436522
392 46717204980510
393 48873884531835
394 51127234972065
395 53481464024005
396 55940957279398
397 58510285495005
398 61194212187781
399 63997701536993
400 66925926588198
401 69984277791647
402 73178371884419
403 76514061111697
404 79997442822008
405 83634869447275
406 87432958863583
407 91398605170225
408 95538989899200
409 99861593652005
410 104374208204167
411 109084949091027
412 114002268673042
413 119134969723801
414 124492219556051
415 130083564685619
416 135918946079146
417 142008715003421
418 148363649477469
419 154994971376745
420 161914364209808
421 169133991569989
422 176666516315485
423 184525120500721
424 192723526063368
425 201276016324911
426 210197458330012
427 219503326031832
428 229209724385347
429 239333414377175
430 249891839002002
431 260903150251984
432 272386237151801
433 284360754852055
434 296847154852800
435 309866716394126
436 323441579029453
437 337594776459587
438 352350271668628
439 367732993381304
440 383768873926307
441 400484888551405
442 417909096214556
443 436070681942353
444 455000000807130
445 474728623552100
446 495289383963046
447 516716428044507
448 539045265035092
449 562312820368720
450 586557490646974
451 611819200662905
452 638139462592618
453 665561437427322
454 694129998692972
455 723891798584313
456 754895336593898
457 787191030691546
458 820831291191732
459 855870597398879
460 892365577095140
461 930375089019592
462 969960308439944
463 1011184815890635
464 1054114689239574
465 1098818599196586
466 1145367908347736
467 1193836773892917
468 1244302254212268
469 1296844419357830
470 1351546465664050
471 1408494834616511
472 1467779336089378
473 1529493276162340
474 1593733589672326
475 1660600977625891
476 1730200049701816
477 1802639472017234
478 1878032120299731
479 1956495238716086
480 2038150604550789
481 2123124698894920
482 2211548883619881
483 2303559584850314
484 2399298483117563
485 2498912710494144
486 2602555054946793
487 2710384172113112
488 2822564804830097
489 2939268010678370
490 3060671397773329
491 3186959369161682
492 3318323376116963
493 3454962180593440
494 3597082127230733
495 3744897425235490
496 3898630440430402
497 4058511997900959
498 4224781695601430
499 4397688229245428
500 4577489728953044
501 4764454108054517
502 4958859424415542
503 5160994254800746
504 5371158082718900
505 5589661700158363
506 5816827623778278
507 6052990526047760
508 6298497681788756
509 6553709430742779
510 6818999656707046
511 7094756283747874
512 7381381790172130
513 7679293740860339
514 7988925338527688
515 8310725994660074
516 8645161920792672
517 8992716740762369
518 9353892124753482
519 9729208445875154
520 10119205459973778
521 10524443009578717
522 10945501752798936
523 11382983917952282
524 11837514084913236
525 12309739994083865
526 12800333383855810
527 13309990857646362
528 13839434781508178
529 14389414213276481
530 14960705864443344
531 15554115095862678
532 16170476948356770
533 16810657209529710
534 17475553518007149
535 18166096506290733
536 18883250983659556
537 19628017160466444
538 20401431915145833
539 21204570105506203
540 22038545925795734
541 22904514310999308
542 23803672390095157
543 24737260989913725
544 25706566191213694
545 26712920938873648
546 27757706708011175
547 28842355227817873
548 29968350265194602
549 31137229470185956
550 32350586285193153
551 33610071920253559
552 34917397396592533
553 36274335660635781
554 37682723770995168
555 39144465160860799
556 40661531978217191
557 42235967506644211
558 43869888669384204
559 45565488619346675
560 47325039418083133
561 49150894806686115
562 51045493071564016
563 53011360008421337
564 55051111987699219
565 57167459124735739
566 59363208558301080
567 61641267841094323
568 64004648445798251
569 66456469390705857
570 68999960988869418
571 71638468724738499
572 74375457262695277
573 77214514591836377
574 80159356311375708
575 83213830061508997
576 86381920104526509
577 89667752060997889
578 93075597806342612
579 96609880533054075
580 100275179983894239
581 104076237861890901
582 108017963422934970
583 112105439256834965
584 116343927263230547
585 120738874828743149
586 125295921211813730
587 130020904142255261
588 134919866642533975
589 139999064077881097
590 145264971442948686
591 150724290892720588
592 156383959525496924
593 162251157426416068
594 168333315979990946
595 174638126460264200
596 181173548907867818
597 187947821303305530
598 194969469045922984
599 202247314748753364
600 209790488359478754
601 217608437617915580
602 225710938861201576
603 234108108187933542
604 242810412992700170
605 251828683883271182
606 261174126992797416
607 270858336699603330
608 280893308768018414
609 291291453923815204
610 302065611878081070
611 313229065814268005
612 324795557353318565
613 336779302012058413
614 349195005171022432
615 362057878568069221
616 375383657334467897
617 389188617591183023
618 403489594623306224
619 418304001650955945
620 433649849216076985
621 449545765204833263
622 466011015525709904
623 483065525464621819
624 500729901738633831
625 519025455270373345
626 537974224706473496
627 557599000703745985
628 577923351007313869
629 598971646346276637
630 620769087172898482
631 643341731271901673
632 666716522267883647
633 690921319059354259
634 715984926208550444
635 741937125317722233
636 768808707423126861
637 796631506438708255
638 825438433683079036
639 855263513524041621
640 886141920175709763
641 918110015685043701
642 951205389145318036
643 985466897174954639
644 1020934705702030147
645 1057650333095565557
646 1095656694685716372
647 1134998148716996335
648 1175720543779563383
649 1217871267764718601
650 1261499298392929184
651 1306655255363690049
652 1353391454177784330
653 1401761961684817488
654 1451822653410025659
655 1503631272715737507
656 1557247491855349946
657 1612732974978940728
658 1670151443151161331
659 1729568741444718691
660 1791052908174164920
661 1854674246336389258
662 1920505397327073697
663 1988621417003942153
664 2059099854169481728
665 2132020831548898184
666 2207467129340808633
667 2285524271420216271
668 2366280614276624792
669 2449827438772085010
670 2536259044806216149
671 2625672848978805131
672 2718169485342737778
673 2813852909342487959
674 2912830505037225596
675 3015213195709987744
676 3121115557967072022
677 3230655939435946271
678 3343956580172601186
679 3461143737892258600
680 3582347817141803598
681 3707703502535215245
682 3837349896176554818
683 3971430659399868926
684 4110094158958576002
685 4253493617800510687
686 4401787270569971366
687 4555138523981662372
688 4713716122215375202
689 4877694317485832213
690 5047253045946025328
691 5222578109086713900
692 5403861360800769968
693 5591300900285360327
694 5785101270959703798
695 5985473665582646136
696 6192636137759023740
697 6406813820028994753
698 6628239148741535360
699 6857152095918499366
700 7093800408321343950
701 7338439853940200829
702 7591334476130691522
703 7852756855630125700
704 8122988380692908300
705 8402319525591263069
706 8691050137734203700
707 8989489733666536334
708 9297957804216565826
709 9616784129068644055
710 9946309101046268470
711 10286884060398989854
712 10638871639394556900
713 11002646117528066869
714 11378593787668170794
715 11767113333469310696
716 12168616218390145861
717 12583527086667400724
718 13012284176604118403
719 13455339746543397818
720 13913160513908631453
721 14386228107701907882
722 14875039534865331513
723 15380107660920886190
724 15901961705316096745
725 16441147751916905552
726 16998229275101073345
727 17573787681918111270
728 18168422870797073409
729 18782753807296545354
730 19417419117405022805
731 20073077698916452980
732 20750409351419934627
733 21450115425457686608
734 22172919491423342683
735 22919568028788173314
736 23690831136259314223
737 24487503263493517916
738 25310403965006916594
739 26160378676939254497
740 27038299517352094290
741 27945066110759027898
742 28881606437605517302
743 29848877709438774811
744 30847867270528315774
745 31879593526719173010
746 32945106902324430212
747 34045490825885804945
748 35181862745654274262
749 36355375175669454496
750 37567216773340525216
751 38818613449456821547
752 40110829511585164068
753 41445168841837245878
754 42822976110017988778
755 44245638023197133595
756 45714584612774940976
757 47231290560142927050
758 48797276562074515066
759 50414110737011667209
760 52083410073446270880
761 53806841921631832428
762 55586125529895011800
763 57423033626852124991
764 59319394050875585024
765 61277091428192266572
766 63298068901034501934
767 65384329907307586563
768 67537940013277973116
769 69761028800828459250
770 72055791810873445886
771 74424492544571209321
772 76869464524015957060
773 79393113414143100852
774 81997919207628926988
775 84686438474615679399
776 87461306679147951518
777 90325240564258245772
778 93281040607693734516
779 96331593550335715135
780 99479874999419783110
781 102728952108723629680
782 106081986337953794192
783 109542236293624179346
784 113113060653783135905
785 116797921179015717789
786 120600385812214553802
787 124524131869682332090
788 128572949326204496833
789 132750744196803431739
790 137061542017960967928
791 141509491431177949132
792 146098867871818588281
793 150834077366269422993
794 155719660440531395354
795 160760296143449435606
796 165960806187873059591
797 171326159213137600639
798 176861475172348971052
799 182572029848051635290
800 188463259499963587295
801 194540765648563440807
802 200810319998419831562
803 207277869505266091554
804 213949541590933196697
805 220831649510368070003
806 227930697875086447791
807 235253388337529018135
808 242806625440913351036
809 250597522639306411699
810 258633408492772193549
811 266921833042583355875
812 275470574371629012400
813 284287645355291646879
814 293381300608211905139
815 302760043632515160277
816 312432634173226583520
817 322408095786759605427
818 332695723628530650181
819 343305092465918875855
820 354246064922961200458
821 365528799963354798449
822 377163761618519199787
823 389161727967656161737
824 401533800376942446240
825 414291413005185837625
826 427446342583476461833
827 441010718476578725473
828 454997033034020899270
829 469418152239058086905
830 484287326663915197597
831 499618202739946110477
832 515424834351582328614
833 531721694763194346029
834 548523688888237863415
835 565846165910313995519
836 583704932266043138138
837 602116264999922013707
838 621096925501611937459
839 640664173636399159743
840 660835782279860639006
841 681630052268070397851
842 703065827774998537561
843 725162512129071973201
844 747940084081192938568
845 771419114536854292305
846 795620783765334130971
847 820566899099306453969
848 846279913138575765692
849 872782942472015636899
850 900099786932174948169
851 928254949397417118359
852 957273656156860760764
853 987181877853805754290
854 1018006351023763212666
855 1049774600243644488094
856 1082514960909114320294
857 1116256602657583318536
858 1151029553454787838556
859 1186864724363392524436
860 1223793935012559304156
861 1261849939787938658644
862 1301066454762066445370
863 1341478185385699602658
864 1383120854961178429360
865 1426031233919474092724
866 1470247169923174929434
867 1515807618818265237886
868 1562752676458168210898
869 1611123611424168054578
870 1660962898666975919550
871 1712314254094872999064
872 1765222670134559927832
873 1819734452291544610732
874 1875897256737624213316
875 1933760128953769397202
876 1993373543457479585998
877 2054789444644460941119
878 2118061288775292160641
879 2183244087138566271435
880 2250394450422843514172
881 2319570634330629816771
882 2390832586468485771337
883 2464241994548287104175
884 2539862335935608267132
885 2617758928582163939901
886 2697998983380233980317
887 2780651657978024927513
888 2865788112095962861440
889 2953481564384983820635
890 3043807350868998586363
891 3136842985014835145211
892 3232668219474120626816
893 3331365109542764742307
894 3433018078384924829765
895 3537713984069585103281
896 3645542188469179667932
897 3756594628071005811673
898 3870965886753528037377
899 3988753270581074682087
900 4110056884671852630180
901 4234979712195669091525
902 4363627695559263491269
903 4496109819838691335567
904 4632538198519783586080
905 4773028161609340741521
906 4917698346181383917223
907 5066670789424494449715
908 5220071024258040387804
909 5378028177586885443349
910 5540675071266022846061
911 5708148325848484888091
912 5880588467191820875712
913 6058140036000431550743
914 6240951700383109050233
915 6429176371507229522253
916 6622971322433201030596
917 6822498310214995064143
918 7027923701354856404339
919 7239418600702614408009
920 7457158983892422037508
921 7681325833412197033935
922 7912105278403554304935
923 8149688738292613368775
924 8394273070354708663420
925 8646060721318746182027
926 8905259883119751155662
927 9172084652911006740366
928 9446755197450116018357
929 9729497921976343535937
930 10020545643699675629552
931 10320137770025204794988
932 10628520481639707315093
933 10945946920590611969759
934 11272677383490975574408
935 11608979519987603806736
936 11955128536633049137253
937 12311407406305907179817
938 12678107083327634376058
939 13055526724427988683508
940 13443973915715177157517
941 13843764905810896485089
942 14255224845314638910454
943 14678688032765933679008
944 15114498167277620227201
945 15563008608017767251489
946 16024582640722489442550
947 16499593751426688843104
948 16988425907604622924993
949 17491473846917205491681
950 18009143373768097779068
951 18541851663875907183019
952 19090027577075209801110
953 19654111978564669404534
954 20234558068826200246456
955 20831831722444945138407
956 21446411836065833115392
957 22078790685728602604044
958 22729474293829458125442
959 23398982805963991609673
960 24087850877912602265664
961 24796628073036424498066
962 25525879270358742798246
963 26276185083613993750727
964 27048142291553762308748
965 27842364279806694264646
966 28659481494596926303986
967 29500141908633514404715
968 30365011499491443334090
969 31254774740813080642448
970 32170135106667434242572
971 33111815589413306936139
972 34080559231421369241650
973 35077129671019331147240
974 36102311703033808444382
975 37156911854312104251469
976 38241758974617000024424
977 39357704843297798262938
978 40505624792151234367040
979 41686418344896517894385
980 42901009873699700263268
981 44150349273193748847518
982 45435412652452178099210
983 46757203045385874206769
984 48116751140044802046146
985 49515116027318644927296
986 50953385969543127317672
987 52432679189531758628917
988 53954144680566056831676
989 55518963037890993754438
990 57128347312276398713150
991 58783543886219409715215
992 60485833373377802777314
993 62236531541839108119124
994 64036990261845884973116
995 65888598478613406592803
996 67792783210892250983018
997 69751010575944950537350
998 71764786841622958479498
999 73835659506247688111573
1000 75965218407017323765754