1 0
2 0
3 5
4 29
5 93
6 235
7 493
8 936
9 1622
10 2642
11 4057
12 6055
13 8608
14 12001
15 16297
16 21619
17 28127
18 36170
19 45624
20 57041
21 70350
22 85892
23 103748
24 124748
25 148174
26 175083
27 205683
28 239800
29 277908
30 321224
31 368301
32 421093
33 479209
34 543193
35 613374
36 690422
37 773636
38 864970
39 964201
40 1071741
41 1186934
42 1313362
43 1447192
44 1592913
45 1749028
46 1915007
47 2093648
48 2285571
49 2488292
50 2705252
51 2936280
52 3181978
53 3440904
54 3719010
55 4010455
56 4319752
57 4646724
58 4991615
59 5355319
60 5741016
61 6141857
62 6568042
63 7015501
64 7483705
65 7975422
66 8492908
67 9031460
68 9597639
69 10191100
70 10811430
71 11455996
72 12135103
73 12836355
74 13573177
75 14342591
76 15140323
77 15970888
78 16837795
79 17736500
80 18675413
81 19646277
82 20656669
83 21703570
84 22797256
85 23921211
86 25090291
87 26306241
88 27560829
89 28859284
90 30211642
91 31597916
92 33038819
93 34528313
94 36067412
95 37655121
96 39300349
97 40990983
98 42740442
99 44547022
100 46407166
101 48321225
102 50305068
103 52337702
104 54439628
105 56601707
106 58821395
107 61112866
108 63476023
109 65891313
110 68389400
111 70950124
112 73587402
113 76284176
114 79075336
115 81928885
116 84858494
117 87874251
118 90960614
119 94133977
120 97395097
121 100719558
122 104143968
123 107654432
124 111252831
125 114938613
126 118722955
127 122579456
128 126544457
129 130607473
130 134764452
131 139009483
132 143377791
133 147820715
134 152381316
135 157054184
136 161816316
137 166685225
138 171680753
139 176774610
140 181991806
141 187309939
142 192755409
143 198310272
144 203996675
145 209781844
146 215705153
147 221763229
148 227929798
149 234224058
150 240670793
151 247213392
152 253919307
153 260750164
154 267717446
155 274816966
156 282075142
157 289452729
158 296981134
159 304673794
160 312505013
161 320469564
162 328609917
163 336873828
164 345324601
165 353926599
166 362671947
167 371589403
168 380687790
169 389912645
170 399336328
171 408917394
172 418666889
173 428584525
174 438713237
175 448989830
176 459437087
177 470083630
178 480910863
179 491919462
180 503148172
181 514502311
182 526097285
183 537871451
184 549854891
185 562019553
186 574404322
187 586976689
188 599755522
189 612756534
190 625947586
191 639348730
192 653007826
193 666815962
194 680891098
195 695196822
196 709688177
197 724410848
198 739397907
199 754569235
200 770004116
201 785659087
202 801564020
203 817690902
204 834090789
205 850699694
206 867577411
207 884717434
208 902084629
209 919706321
210 937622459
211 955724800
212 974149710
213 992827237
214 1011773344
215 1030982221
216 1050489485
217 1070217406
218 1090246189
219 1110584028
220 1131197310
221 1152035874
222 1173239360
223 1194683114
224 1216463709
225 1238516363
226 1260837484
227 1283497869
228 1306471570
229 1329711827
230 1353295912
231 1377184575
232 1401370321
233 1425862944
234 1450746394
235 1475868641
236 1501359336
237 1527188050
238 1553330814
239 1579789557
240 1606657097
241 1633750379
242 1661262356
243 1689116787
244 1717312221
245 1745859481
246 1774771387
247 1804014285
248 1833612146
249 1863600103
250 1893964393
251 1924661759
252 1955805999
253 1987196283
254 2019046399
255 2051306251
256 2083883154
257 2116855880
258 2150281865
259 2184042079
260 2218230632
261 2252792885
262 2287771111
263 2323124318
264 2358969757
265 2395126158
266 2431742988
267 2468784554
268 2506245275
269 2544128699
270 2582482267
271 2621154224
272 2660366221
273 2699978407
274 2740016433
275 2780519115
276 2821479484
277 2862832414
278 2904693433
279 2947044585
280 2989809520
281 3032959138
282 3076726314
283 3120865760
284 3165515360
285 3210669509
286 3256248029
287 3302321537
288 3348917809
289 3395925269
290 3443516370
291 3491566488
292 3540137197
293 3589151927
294 3638797493
295 3688827756
296 3739435035
297 3790579113
298 3842157612
299 3894338387
300 3947093237
301 4000235210
302 4054003712
303 4108326436
304 4163199966
305 4218554712
306 4274537985
307 4330993915
308 4388068092
309 4445679951
310 4503893527
311 4562599757
312 4621997348
313 4681817630
314 4742329805
315 4803449304
316 4865028716
317 4927280312
318 4990188951
319 5053592172
320 5117654702
321 5182293365
322 5247587809
323 5313414073
324 5379984371
325 5447029318
326 5514740457
327 5583177239
328 5652192838
329 5721818818
330 5792174612
331 5863012277
332 5934628800
333 6006858858
334 6079750547
335 6153328648
336 6227597651
337 6302395194
338 6377954083
339 6454245283
340 6531184776
341 6608735262
342 6687114068
343 6766028495
344 6845745498
345 6926166507
346 7007234165
347 7089005060
348 7171607387
349 7254793511
350 7338820160
351 7423483798
352 7508881455
353 7594964262
354 7681949679
355 7769575230
356 7857962148
357 7947147450
358 8036964403
359 8127645568
360 8219184846
361 8311193805
362 8404210496
363 8497988824
364 8592526600
365 8687757501
366 8783916330
367 8880796433
368 8978481926
369 9076999510
370 9176317034
371 9276377782
372 9377400434
373 9479077676
374 9581714438
375 9685147518
376 9789363680
377 9894446703
378 10000449320
379 10107119069
380 10214800510
381 10323276807
382 10432649512
383 10542819005
384 10654028044
385 10765932198
386 10878728229
387 10992550395
388 11107136883
389 11222622117
390 11339162192
391 11456334742
392 11574580611
393 11693687851
394 11813790523
395 11934801434
396 12056765539
397 12179465161
398 12303265558
399 12428075646
400 12553702773
401 12680199148
402 12807890671
403 12936321781
404 13065864662
405 13196399361
406 13327760639
407 13460151961
408 13593629800
409 13727916276
410 13863303317
411 13999709212
412 14137145824
413 14275460820
414 14414975708
415 14555331560
416 14696807771
417 14839269329
418 14982794626
419 15127293312
420 15273049834
421 15419453179
422 15567238564
423 15716040330
424 15865821642
425 16016702553
426 16168715252
427 16321736499
428 16475802708
429 16631097511
430 16787390885
431 16944704815
432 17103385237
433 17262823447
434 17423638255
435 17585518319
436 17748434660
437 17912529465
438 18077822484
439 18244187459
440 18411821038
441 18580448431
442 18750236789
443 18921161701
444 19093507895
445 19266748991
446 19441230781
447 19617034424
448 19793940521
449 19971908805
450 20151361638
451 20331633572
452 20513343067
453 20696297129
454 20880491323
455 21065866725
456 21252475445
457 21440170499
458 21629276450
459 21819684293
460 22011239313
461 22203966879
462 22398233122
463 22593375059
464 22790094635
465 22988074928
466 23187176714
467 23387718297
468 23589617220
469 23792554749
470 23997014128
471 24202767575
472 24409860656
473 24618043891
474 24827898099
475 25038889133
476 25251265174
477 25464992993
478 25680036742
479 25896479643
480 26114455488
481 26333384615
482 26553980751
483 26776002540
484 26999298594
485 27223944599
486 27450188891
487 27677576314
488 27906512933
489 28136947817
490 28368770844
491 28601800996
492 28836657794
493 29072599850
494 29310152143
495 29549199269
496 29789481943
497 30031357693
498 30274826638
499 30519648657
500 30766057074
501 31013759962
502 31263126987
503 31513908904
504 31766440835
505 32020001955
506 32275389714
507 32532348977
508 32790663480
509 33050581671
510 33312301261
511 33575125958
512 33839728371
513 34105880930
514 34373549997
515 34642827474
516 34913836420
517 35186200617
518 35460185564
519 35735872046
520 36013203716
521 36291879958
522 36572550851
523 36854418508
524 37138279709
525 37423763310
526 37710585204
527 37999206078
528 38289651999
529 38581374381
530 38875124048
531 39170469163
532 39467475845
533 39765945325
534 40066476086
535 40368502777
536 40672171218
537 40977724979
538 41284912601
539 41593887622
540 41904634153
541 42216635141
542 42530884169
543 42846793338
544 43164515240
545 43483766461
546 43805090603
547 44127821028
548 44452594307
549 44779237094
550 45107519027
551 45437474492
552 45769619762
553 46103073060
554 46438633207
555 46776199877
556 47115311702
557 47456307816
558 47799420569
559 48144059193
560 48490791940
561 48839104682
562 49189457428
563 49541602103
564 49895947487
565 50251874080
566 50609797655
567 50969797512
568 51331373715
569 51695040370
570 52060917185
571 52428150081
572 52797762125
573 53169146771
574 53542621014
575 53917935504
576 54295396468
577 54674466280
578 55055674285
579 55439079728
580 55824436131
581 56211495551
582 56601000051
583 56992197133
584 57385641774
585 57781078657
586 58178279375
587 58577752900
588 58979471076
589 59382745238
590 59788461824
591 60196227667
592 60606035579
593 61017766459
594 61432064887
595 61847899493
596 62265991944
597 62686458199
598 63108917502
599 63533304482
600 63960295855
601 64388753719
602 64819940166
603 65253112468
604 65688443293
605 66125909189
606 66565659006
607 67007494795
608 67451561488
609 67897916192
610 68346338175
611 68796890409
612 69250096979
613 69704808963
614 70162401012
615 70622278920
616 71084107156
617 71548008295
618 72014630212
619 72483303157
620 72954404974
621 73427642012
622 73903164767
623 74381014214
624 74861447919
625 75343727512
626 75828562166
627 76315928775
628 76805364996
629 77297278542
630 77791834750
631 78287862012
632 78787056503
633 79288403736
634 79792217991
635 80298378792
636 80807133431
637 81317947397
638 81831179566
639 82347142733
640 82865439999
641 83385817086
642 83909335964
643 84434800962
644 84962916159
645 85493479970
646 86026418784
647 86561923914
648 87100119867
649 87640331067
650 88183496102
651 88729014522
652 89277047418
653 89827456198
654 90380992666
655 90936494614
656 91494758151
657 92055672407
658 92619012122
659 93184939728
660 93753913828
661 94324576945
662 94898382760
663 95474909342
664 96053920162
665 96635552641
666 97219842472
667 97806575469
668 98396176400
669 98988539742
670 99583546223
671 100180970294
672 100781537951
673 101384001177
674 101989900120
675 102598523879
676 103209290772
677 103822981525
678 104439843130
679 105059064186
680 105681167450
681 106305871211
682 106933559988
683 107563549226
684 108197106388
685 108832698569
686 109471489554
687 110113143823
688 110757438216
689 111404430003
690 112054703056
691 112707180043
692 113363111328
693 114021764034
694 114682898833
695 115347283778
696 116014665297
697 116684410261
698 117357287134
699 118033384675
700 118712317163
701 119393600751
702 120078647674
703 120765803438
704 121456392433
705 122149927738
706 122846224587
707 123545679301
708 124248278118
709 124953456418
710 125662016045
711 126373378574
712 127087838452
713 127805025399
714 128525893317
715 129249081946
716 129975437449
717 130705289170
718 131437894795
719 132173766206
720 132913093866
721 133654289306
722 134399379493
723 135147628901
724 135899064923
725 136653265931
726 137411025287
727 138171527343
728 138935470016
729 139702370542
730 140472561164
731 141245794278
732 142022553479
733 142801993427
734 143585138973
735 144371578558
736 145160640446
737 145953171897
738 146749260531
739 147548071480
740 148350645739
741 149156259910
742 149965181280
743 150776930534
744 151592928740
745 152411469991
746 153233526726
747 154059296444
748 154887889843
749 155719840043
750 156555651587
751 157393993511
752 158236380759
753 159081835291
754 159930880546
755 160783197724
756 161639242542
757 162497732294
758 163360396457
759 164226703722
760 165096004060
761 165968378572
762 166845234680
763 167724802843
764 168608215628
765 169495175506
766 170385097254
767 171278833201
768 172176396880
769 173076871432
770 173981336650
771 174888909138
772 175800494476
773 176715293028
774 177634154231
775 178556036151
776 179481636040
777 180411141976
778 181343831087
779 182280377025
780 183220976175
781 184163942567
782 185111539730
783 186062686780
784 187017380718
785 187975501270
786 188937890388
787 189903442087
788 190872690381
789 191846070557
790 192823127345
791 193803489667
792 194788222845
793 195775569998
794 196767570498
795 197763433739
796 198762630040
797 199765683168
798 200772940145
799 201783278920
800 202797973275
801 203816202597
802 204838352500
803 205864320979
804 206894679373
805 207928231102
806 208965606096
807 210007352381
808 211052687564
809 212101684025
810 213155477245
811 214211921011
812 215273299092
813 216338051028
814 217407178512
815 218479944831
816 219557040330
817 220637417816
818 221722254827
819 222811466767
820 223903891648
821 225000416626
822 226101834081
823 227206329567
824 228315467376
825 229428647153
826 230545280692
827 231666224352
828 232791887851
829 233920732040
830 235054318747
831 236191866191
832 237333720295
833 238478964105
834 239629223107
835 240783221916
836 241941557769
837 243103939007
838 244270296311
839 245441115628
840 246616706135
841 247794832844
842 248978300541
843 250166215778
844 251358211079
845 252554406641
846 253755045440
847 254959476568
848 256168265865
849 257381757914
850 258599560954
851 259820829653
852 261047543882
853 262277567238
854 263512835981
855 264752296522
856 265995474311
857 267243444722
858 268496155283
859 269752464657
860 271013929507
861 272279503194
862 273549468176
863 274823753293
864 276103266692
865 277385797274
866 278673745963
867 279966521753
868 281263285414
869 282564247129
870 283870578620
871 285180362039
872 286495319256
873 287814832691
874 289138874567
875 290467290059
876 291800454032
877 293137896329
878 294480050340
879 295827266285
880 297179012871
881 298534547103
882 299895976808
883 301260583400
884 302630951659
885 304005763289
886 305384741496
887 306768897098
888 308158177866
889 309551328461
890 310949751830
891 312352776786
892 313760319622
893 315172267584
894 316590104782
895 318012020189
896 319438813989
897 320870288584
898 322306496953
899 323747865470
900 325194402069
901 326644233861
902 328100254842
903 329560880389
904 331026183622
905 332496331167
906 333971995237
907 335451853272
908 336936905575
909 338427188153
910 339922110084
911 341421319178
912 342926883750
913 344435925423
914 345950589010
915 347470795387
916 348995371521
917 350525051567
918 352060176284
919 353599420972
920 355144721951
921 356694333757
922 358249518168
923 359809326243
924 361375127085
925 362944511152
926 364519902389
927 366100845838
928 367686157177
929 369276800828
930 370873332206
931 372473794733
932 374079942693
933 375691587741
934 377308514865
935 378930366586
936 380557671448
937 382189232680
938 383826920718
939 385469998095
940 387118376475
941 388771040353
942 390430360918
943 392093901112
944 393763419861
945 395438318352
946 397117405145
947 398802674167
948 400493926664
949 402189512412
950 403891116146
951 405597892632
952 407310276211
953 409027152509
954 410751019533
955 412479108930
956 414212816507
957 415952622798
958 417697276141
959 419447635930
960 421204011367
961 422964288401
962 424731576038
963 426503747236
964 428281723089
965 430065265813
966 431854833045
967 433648894902
968 435449116771
969 437254998823
970 439066313738
971 440883149630
972 442706641987
973 444534144887
974 446368203788
975 448208441882
976 450053333188
977 451903873668
978 453761109753
979 455623397055
980 457491897838
981 459365368992
982 461245032501
983 463130348052
984 465022265053
985 466918708103
986 468821451988
987 470730456403
988 472644514833
989 474564545023
990 476491427369
991 478422011703
992 480360342328
993 482304063999
994 484253968237
995 486209000963
996 488170847264
997 490137881381
998 492110990744
999 494090836200
1000 496076032096