1 0
2 0
3 18
4 434
5 2814
6 11127
7 33365
8 83568
9 184254
10 369254
11 686952
12 1203930
13 2009018
14 3217749
15 4977219
16 7471352
17 10926570
18 15617868
19 21875294
20 30090834
21 40725702
22 54318035
23 71490993
24 92961264
25 119547974
26 152182002
27 191915700
28 239933018
29 297560034
30 366275889
31 447724127
32 543724440
33 656284818
34 787614104
35 940134954
36 1116497202
37 1319591630
38 1552564143
39 1818830349
40 2122090544
41 2466345102
42 2855910270
43 3295434368
44 3789914394
45 4344713034
46 4965576077
47 5658650235
48 6430501368
49 7288133114
50 8239005924
51 9291056502
52 10452717650
53 11732938518
54 13141205259
55 14687562089
56 16382632752
57 18237642390
58 20264439818
59 22475520204
60 24884048154
61 27503881202
62 30349593705
63 33436501143
64 36780684824
65 40399016994
66 44309186352
67 48529723970
68 53080029618
69 57980398494
70 63252048359
71 68917147077
72 74998840560
73 81521281118
74 88509656214
75 95990217624
76 103990311002
77 112538405850
78 121664125893
79 131398279859
80 141772892664
81 152821237002
82 164577865340
83 177078642318
84 190360777554
85 204462858854
86 219424885827
87 235288303905
88 252096038768
89 269892531174
90 288723772194
91 308637338852
92 329682430170
93 351909903618
94 375372311969
95 400123940559
96 426220844952
97 453720889010
98 482683783368
99 513171124314
100 545246433074
101 578975195502
102 614424902175
103 651665088893
104 690767377584
105 731805517614
106 774855427502
107 819995237040
108 867305329818
109 916868386154
110 968769426429
111 1023095854827
112 1079937503480
113 1139386677018
114 1201538197524
115 1266489449894
116 1334340427602
117 1405193778870
118 1479154853243
119 1556331748569
120 1636835358384
121 1720779419702
122 1808280561210
123 1899458351868
124 1994435349914
125 2093337152274
126 2196292444377
127 2303433050375
128 2414893983768
129 2530813498434
130 2651333140064
131 2776597798002
132 2906755757490
133 3041958752318
134 3182362017879
135 3328124344629
136 3479408131952
137 3636379442430
138 3799208056518
139 3968067527624
140 4143135237594
141 4324592452602
142 4512624379445
143 4707420222243
144 4909173239544
145 5118080801834
146 5334344449452
147 5558169950910
148 5789767361618
149 6029351083014
150 6277139922099
151 6533357151377
152 6798230569200
153 7071992560518
154 7354880158034
155 7647135103764
156 7949003911002
157 8260737926690
158 8582593394193
159 8914831516479
160 9257718519704
161 9611525717202
162 9976529573880
163 10353011771018
164 10741259271474
165 11141564385294
166 11554224835727
167 11979543825645
168 12417830104368
169 12869398034894
170 13334567661534
171 13813664777952
172 14307020995610
173 14814973812618
174 15337866682989
175 15876049086299
176 16429876597752
177 16999710958650
178 17585920147268
179 18188878450134
180 18808966533714
181 19446571516502
182 20102087041515
183 20775913349193
184 21468457350704
185 22180132701654
186 22911359876202
187 23662566241580
188 24434186133018
189 25226660929074
190 26040439127369
191 26875976420727
192 27733735773720
193 28614187499618
194 29517809337744
195 30445086531234
196 31396511905202
197 32372585945310
198 33373816876743
199 34400720743589
200 35453821488624
201 36533651033502
202 37640749359350
203 38775664587768
204 39938953062234
205 41131179429914
206 42352916723877
207 43604746445715
208 44887258648568
209 46201052020554
210 47546733968604
211 48924920702702
212 50336237320530
213 51781317892518
214 53260805547299
215 54775352557569
216 56325620426352
217 57912279973670
218 59536011423618
219 61197504491844
220 62897458473434
221 64636582331202
222 66415594784385
223 68235224397743
224 70096209671064
225 71999299129074
226 73945251411752
227 75934835365050
228 77968830132018
229 80048025244334
230 82173220714239
231 84345227126877
232 86564865733040
233 88832968542318
234 91150378416654
235 93517949164304
236 95936545634202
237 98407043810730
238 100930330908893
239 103507305469899
240 106138877457144
241 108825968352602
242 111569511253620
243 114370450970118
244 117229744122194
245 120148359238134
246 123127276852827
247 126167489606585
248 129270002344368
249 132435832215414
250 135666008773274
251 138961574076252
252 142323582788250
253 145753102280018
254 149251212730809
255 152819007230439
256 156457591881752
257 160168085903490
258 163951621733568
259 167809345132754
260 171742415288754
261 175752004920702
262 179839300384055
263 184005501775893
264 188251823040624
265 192579492076094
266 196989750840102
267 201483855457320
268 206063076326618
269 210728698228794
270 215482020434709
271 220324356813827
272 225257035943160
273 230281401216618
274 235398810954764
275 240610638514974
276 245918272402002
277 251323116378950
278 256826589578643
279 262430126615409
280 268135177697264
281 273943208738502
282 279855701472690
283 285874153566068
284 292000078731354
285 298235006841954
286 304580484046577
287 311038072884255
288 317609352399768
289 324295918259474
290 331099382867544
291 338021375482602
292 345063542334770
293 352227546743118
294 359515069233519
295 366927807656909
296 374467477307952
297 382135811044110
298 389934559405118
299 397865490732864
300 405930391291674
301 414131065389002
302 422469335496525
303 430947042371643
304 439566045179384
305 448328221614714
306 457235468025252
307 466289699534390
308 475492850164818
309 484846872962454
310 494353740120779
311 504015443105577
312 513833992780080
313 523811419530518
314 533949773392074
315 544251124175244
316 554717561592602
317 565351195385970
318 576154155453993
319 587128591980119
320 598276675560984
321 609600597335202
322 621102569112560
323 632784823503618
324 644649614049714
325 656699215353374
326 668935923209127
327 681362054734725
328 693979948502768
329 706791964672734
330 719800485123414
331 733007913585752
332 746416675776090
333 760029219529818
334 773848014935429
335 787875554468979
336 802114353128952
337 816566948571530
338 831235901246268
339 846123794532174
340 861233234874194
341 876566851920102
342 892127298657795
343 907917251552993
344 923939410687344
345 940196499896934
346 956691266911202
347 973426483492260
348 990404945574618
349 1007629473405314
350 1025102911684449
351 1042828129706127
352 1060808021499800
353 1079045505972018
354 1097543527048584
355 1116305053817114
356 1135333080670002
357 1154630627447790
358 1174200739582943
359 1194046488244029
360 1214170970480304
361 1234577309366702
362 1255268654149230
363 1276248180390768
364 1297519090117274
365 1319084611964394
366 1340948001324477
367 1363112540493995
368 1385581538821368
369 1408358332855194
370 1431446286492884
371 1454848791129702
372 1478569265808210
373 1502611157368118
374 1526977940596539
375 1551673118378649
376 1576700221848752
377 1602062810541750
378 1627764472545018
379 1653808824650684
380 1680199512508314
381 1706940210778002
382 1734034623283865
383 1761486483167943
384 1789299553044504
385 1817477625154754
386 1846024521521952
387 1874944094106930
388 1904240224964018
389 1933916826397374
390 1963977841117719
391 1994427242399477
392 2025269034238320
393 2056507251509118
394 2088145960124294
395 2120189257192584
396 2152641271178202
397 2185506162060410
398 2218788121493493
399 2252491372967139
400 2286620171967224
401 2321178806137002
402 2356171595438700
403 2391602892315518
404 2427477081854034
405 2463798581947014
406 2500571843456627
407 2537801350378065
408 2575491620003568
409 2613647203086854
410 2652272684007954
411 2691372680938452
412 2730951846007130
413 2771014865466018
414 2811566459856849
415 2852611384177919
416 2894154428051352
417 2936200415890770
418 2978754207069368
419 3021820696088394
420 3065404812746034
421 3109511522306702
422 3154145825670735
423 3199312759544493
424 3245017396610864
425 3291264845700174
426 3338060251961502
427 3385408797034400
428 3433315699221018
429 3481786213658634
430 3530825632492589
431 3580439285049627
432 3630632538011640
433 3681410795589818
434 3732779499699204
435 3784744130133654
436 3837310204741202
437 3890483279599830
438 3944268949193643
439 3998672846589449
440 4053700643613744
441 4109358051030102
442 4165650818716970
443 4222584735845868
444 4280165631059994
445 4338399372653234
446 4397291868749577
447 4456849067482935
448 4517076957177368
449 4577981566527714
450 4639568964780624
451 4701845261916002
452 4764816608828850
453 4828489197511518
454 4892869261236359
455 4957963074738789
456 5023776954400752
457 5090317258434590
458 5157590387067318
459 5225602782725304
460 5294360930219354
461 5363871356930202
462 5434140632994405
463 5505175371490643
464 5576982228626424
465 5649567903925194
466 5722939140413852
467 5797102724810670
468 5872065487713618
469 5947834303789094
470 6024416091961059
471 6101817815600577
472 6180046482715760
473 6259109146142118
474 6339012903733314
475 6419764898552324
476 6501372319063002
477 6583842399322050
478 6667182419171393
479 6751399704430959
480 6836501627091864
481 6922495605510002
482 7009389104600040
483 7097189636029818
484 7185904758415154
485 7275542077515054
486 7366109246427327
487 7457613965784605
488 7550063983950768
489 7643467097217774
490 7737831150002894
491 7833164035046352
492 7929473693609370
493 8026768115672618
494 8125055340135069
495 8224343455013259
496 8324640597640952
497 8425954954869210
498 8528294763266868
499 8631668309321414
500 8736083929640274
501 8841550011152502
502 8948074991310875
503 9055667358294393
504 9164335651211184
505 9274088460301814
506 9384934427143002
507 9496882244851740
508 9609940658289818
509 9724118464268754
510 9839424511755129
511 9955867702076327
512 10073456989126680
513 10192201379574018
514 10312109933066624
515 10433191762440594
516 10555456033927602
517 10678911967363070
518 10803568836394743
519 10929435968691669
520 11056522746153584
521 11184838605120702
522 11314393036583910
523 11445195586395368
524 11577255855479514
525 11710583500044474
526 11845188231793877
527 11981079818139075
528 12118268082411768
529 12256762904077034
530 12396574218946764
531 12537712019393502
532 12680186354564690
533 12824007330597318
534 12969185110832979
535 13115729916033329
536 13263652024595952
537 13412961772770630
538 13563669554876018
539 13715785823516724
540 13869321089800794
541 14024285923557602
542 14180690953556145
543 14338546867723743
544 14497864413365144
545 14658654397382034
546 14820927686492952
547 14984695207453610
548 15149967947277618
549 15316756953457614
550 15485073334186799
551 15654928258580877
552 15826332956900400
553 15999298720773518
554 16173836903419134
555 16349958919870464
556 16527676247199002
557 16707000424738890
558 16887943054311693
559 17070515800451579
560 17254730390630904
561 17440598615486202
562 17628132329044580
563 17817343448950518
564 18008243956693074
565 18200845897833494
566 18395161382233227
567 18591202584282345
568 18788981743128368
569 18988511162905494
570 19189803212964234
571 19392870328101452
572 19597725008790810
573 19804379821413618
574 20012847398490089
575 20223140438910999
576 20435271708169752
577 20649254038594850
578 20865100329582768
579 21082823547831234
580 21302436727572914
581 21523952970809502
582 21747385447546215
583 21972747396026693
584 22200052122968304
585 22429313003797854
586 22660543482887702
587 22893757073792280
588 23128967359485018
589 23366187992595674
590 23605432695648069
591 23846715261298227
592 24090049552572920
593 24335449503108618
594 24582929117390844
595 24832502470993934
596 25084183710821202
597 25337987055345510
598 25593926794850243
599 25852017291670689
600 26112272980435824
601 26374708368310502
602 26639338035238050
603 26906176634183268
604 27175238891375834
605 27446539606554114
606 27720093653209377
607 27995915978830415
608 28274021605148568
609 28554425628383154
610 28837143219487304
611 29122189624394202
612 29409580164263730
613 29699330235729518
614 29991455311146399
615 30285970938838269
616 30582892743346352
617 30882236425677870
618 31184017763555118
619 31488252611664944
620 31794956901908634
621 32104146643652202
622 32415837923977085
623 32730046907931243
624 33046789838780664
625 33366083038261274
626 33687942906831252
627 34012385923923750
628 34339428648200018
629 34669087717802934
630 35001379850610939
631 35336321844492377
632 35673930577560240
633 36014223008427318
634 36357216176461754
635 36702927202043004
636 37051373286818202
637 37402571713958930
638 37756539848418393
639 38113295137188999
640 38472855109560344
641 38835237377377602
642 39200459635300320
643 39568539661061618
644 39939495315727794
645 40313344543958334
646 40690105374266327
647 41069795919279285
648 41452434376000368
649 41838039026070014
650 42226628236027974
651 42618220457575752
652 43012834227839450
653 43410488169633018
654 43811200991721909
655 44214991489087139
656 44621878543189752
657 45031881122235690
658 45445018281441068
659 45861309163297854
660 46280772997839954
661 46703429102909702
662 47129296884424755
663 47558395836645393
664 47990745542442224
665 48426365673564294
666 48865275990907602
667 49307496344784020
668 49753046675190618
669 50201947012079394
670 50654217475627409
671 51109878276507327
672 51568949716158360
673 52031452187057618
674 52497406172991864
675 52966832249329674
676 53439751083294002
677 53916183434235150
678 54396150153904143
679 54879672186726509
680 55366770570076464
681 55857466434551502
682 56351781004247390
683 56849735597033568
684 57351351624828954
685 57856650593878154
686 58365654105028077
687 58878383854004955
688 59394861631691768
689 59915109324406074
690 60439148914178244
691 60967002479030102
692 61498692193253970
693 62034240327692118
694 62573669250016619
695 63117001425009609
696 63664259414843952
697 64215465879364310
698 64770643576368618
699 65329815361889964
700 65893004190478874
701 66460233115486002
702 67031525289345225
703 67606903963857143
704 68186392490472984
705 68770014320578914
706 69357793005780752
707 69949752198189090
708 70545915650704818
709 71146307217305054
710 71750950853329479
711 72359870615767077
712 72973090663543280
713 73590635257807518
714 74212528762221174
715 74838795643245944
716 75469460470432602
717 76104547916710170
718 76744082758675493
719 77388089876883219
720 78036594256136184
721 78689620985776202
722 79347195259975260
723 80009342378027118
724 80676087744639314
725 81347456870225574
726 82023475371198627
727 82704168970263425
728 83389563496710768
729 84079684886711334
730 84774559183610114
731 85474212538221252
732 86178671209123290
733 86887961562954818
734 87602110074710529
735 88321143328037679
736 89045088015532952
737 89773970939039730
738 90507819009945768
739 91246659249481274
740 91990518789017394
741 92739424870365102
742 93493404846074495
743 94252486179734493
744 95016696446272944
745 95786063332257134
746 96560614636194702
747 97340378268834960
748 98125382253470618
749 98915654726239914
750 99711223936429149
751 100512118246775627
752 101318366133771000
753 102129996187965018
754 102947037114269684
755 103769517732263814
756 104597466976498002
757 105430913896799990
758 106269887658580443
759 107114417543139129
760 107964532947971504
761 108820263387075702
762 109681638491259930
763 110548688008450268
764 111421441803998874
765 112299929860992594
766 113184182280561977
767 114074229282190695
768 114970101204025368
769 115871828503185794
770 116779441756075584
771 117692971658693202
772 118612449026943410
773 119537904796949118
774 120469370025363639
775 121406875889683349
776 122350453688560752
777 123300134842117950
778 124255950892260518
779 125217933502991784
780 126186114460727514
781 127160525674611002
782 128141199176828565
783 129128167122925443
784 130121461792122104
785 131121115587630954
786 132127161036973452
787 133139630792297630
788 134158557630696018
789 135183974454523974
790 136215914291718419
791 137254410296116977
792 138299495747777520
793 139351204053298118
794 140409568746137394
795 141474623486935284
796 142546402063834202
797 143624938392800610
798 144710266517946993
799 145802420611854239
800 146901434975894424
801 148007344040554002
802 149120182365757400
803 150239984641191018
804 151366785686627634
805 152500620452251214
806 153641524018982127
807 154789531598802765
808 155944678535083568
809 157107000302909454
810 158276532509406654
811 159453310894069952
812 160637371329090330
813 161828749819683018
814 163027482504415949
815 164233605655538619
816 165447155679311352
817 166668169116334970
818 167896682641880868
819 169132733066221494
820 170376357334961234
821 171627592529367702
822 172886475866703435
823 174153044700557993
824 175427336521180464
825 176709388955812374
826 177999239769021002
827 179296926863033100
828 180602488278069018
829 181915962192677234
830 183237386924069289
831 184566800928455127
832 185904242801378840
833 187249751278054818
834 188603365233704304
835 189965123683892354
836 191335065784865202
837 192713230833888030
838 194099658269583143
839 195494387672268549
840 196897458764296944
841 198308911410395102
842 199728785618003670
843 201157121537617368
844 202593959463125594
845 204039339832153434
846 205493303226403077
847 206955890371995635
848 208427142139813368
849 209907099545842314
850 211395803751515324
851 212893296064055502
852 214399617936820050
853 215914810969644518
854 217438916909187459
855 218971977649275489
856 220514035231248752
857 222065131844306790
858 223625309825854818
859 225194611661850404
860 226773079987150554
861 228360757585859202
862 229957687391675105
863 231563912488240143
864 233179476109488024
865 234804421639993394
866 236438792615321352
867 238082632722377370
868 239735985799757618
869 241398895838099694
870 243071406980433759
871 244753563522534077
872 246445409913270960
873 248146990754963118
874 249858350803730414
875 251579534969847024
876 253310588318095002
877 255051556068118250
878 256802483594776893
879 258563416428502059
880 260334400255651064
881 262115480918863002
882 263906704417414740
883 265708116907577318
884 267519764702972754
885 269341694274931254
886 271173952252848827
887 273016585424545305
888 274869640736622768
889 276733165294824374
890 278607206364393594
891 280491811370433852
892 282387027898268570
893 284292903693801618
894 286209486663878169
895 288136824876645959
896 290074966561916952
897 292023960111529410
898 293983854079710368
899 295954697183438514
900 297936538302807474
901 299929426481389502
902 301933410926599575
903 303948541010059893
904 305974866267964784
905 308012436401446014
906 310061301276938502
907 312121510926546440
908 314193115548409818
909 316276165507071354
910 318370711333843829
911 320476803727177827
912 322594493553029880
913 324723831845231018
914 326864869805855724
915 329017658805591294
916 331182250384107602
917 333358696250427270
918 335547048283296243
919 337747358531554769
920 339959679214508784
921 342184062722301702
922 344420561616286610
923 346669228629398868
924 348930116666529114
925 351203278804896674
926 353488768294423377
927 355786638558107775
928 358096943192399768
929 360419735967575634
930 362755070828113464
931 365103001893069002
932 367463583456451890
933 369836869987602318
934 372222916131568079
935 374621776709482029
936 377033506718939952
937 379458161334378830
938 381895795907455518
939 384346465967425824
940 386810227221523994
941 389287135555342602
942 391777247033212845
943 394280617898585243
944 396797304574410744
945 399327363663522234
946 401870851949016452
947 404427826394636310
948 406998344145153618
949 409582462526752214
950 412180239047411499
951 414791731397290377
952 417416997449111600
953 420056095258546518
954 422709083064600234
955 425376019289997164
956 428056962541567002
957 430751971610631090
958 433461105473389193
959 436184423291306679
960 438921984411502104
961 441673848367135202
962 444440074877795280
963 447220723849890018
964 450015855377034674
965 452825529740441694
966 455649807409310727
967 458488749041219045
968 461342415482512368
969 464210867768696094
970 467094167124826934
971 469992374965904952
972 472905552897266010
973 475833762714974618
974 478777066406217189
975 481735526149695699
976 484709204316021752
977 487698163468111050
978 490702466361578268
979 493722175945132334
980 496757355360972114
981 499808067945182502
982 502874377228130915
983 505956346934864193
984 509054040985505904
985 512167523495654054
986 515296858776779202
987 518442111336622980
988 521603345879597018
989 524780627307182274
990 527974020718328769
991 531183591409855727
992 534409404876852120
993 537651526813077618
994 540910023111363944
995 544184959864016634
996 547476403363217202
997 550784420101425710
998 554109076771783743
999 557450440268517789
1000 560808577687343024