0 0
1 0
2 6
3 40
4 125
5 323
6 647
7 1235
8 2074
9 3337
10 5057
11 7477
12 10436
13 14490
14 19436
15 25591
16 33015
17 42259
18 52849
19 65833
20 80528
21 97909
22 117905
23 141163
24 166651
25 196474
26 229796
27 267289
28 308712
29 355766
30 406488
31 464094
32 526402
33 595477
34 670963
35 753680
36 842052
37 940540
38 1046368
39 1161117
40 1283499
41 1417861
42 1559763
43 1714935
44 1879280
45 2055600
46 2244566
47 2447606
48 2659753
49 2889622
50 3131942
51 3390613
52 3663460
53 3955334
54 4260028
55 4585379
56 4925895
57 5288004
58 5669138
59 6072600
60 6489452
61 6935600
62 7401782
63 7890518
64 8401529
65 8940470
66 9500360
67 10092452
68 10707027
69 11351890
70 12021548
71 12726754
72 13451927
73 14218701
74 15014213
75 15841775
76 16701896
77 17600761
78 18528851
79 19501739
80 20502270
81 21547520
82 22631956
83 23760914
84 24917528
85 26128203
86 27380127
87 28677790
88 30014858
89 31407974
90 32833502
91 34320865
92 35852206
93 37438811
94 39075865
95 40768680
96 42500912
97 44306278
98 46159862
99 48072970
100 50037962
101 52076882
102 54163572
103 56326428
104 58540148
105 60821133
106 63172471
107 65598161
108 68070807
109 70635491
110 73257981
111 75961698
112 78726897
113 81585401
114 84503863
115 87513460
116 90593851
117 93758863
118 97006795
119 100343406
120 103734496
121 107244753
122 110835633
123 114518624
124 118284481
125 122152802
126 126091844
127 130154132
128 134294209
129 138544894
130 142884070
131 147343498
132 151874254
133 156537437
134 161300353
135 166165270
136 171135128
137 176237624
138 181428654
139 186758432
140 192171830
141 197727237
142 203398447
143 209198790
144 215082003
145 221128212
146 227293870
147 233586510
148 240002655
149 246570909
150 253233085
151 260070015
152 267017335
153 274115515
154 281344773
155 288734188
156 296231258
157 303918116
158 311738022
159 319712401
160 327807921
161 336092950
162 344501056
163 353105424
164 361844421
165 370745926
166 379818670
167 389073580
168 398433612
169 408023053
170 417755855
171 427675361
172 437761110
173 448052064
174 458484762
175 469122370
176 479918421
177 490928420
178 502120646
179 513522278
180 525037851
181 536826693
182 548779103
183 560949896
184 573297656
185 585877767
186 598629309
187 611625988
188 624806387
189 638202416
190 651804438
191 665661566
192 679665641
193 693963385
194 708462233
195 723177154
196 738106182
197 753313178
198 768689858
199 784365518
200 800216015
201 816353208
202 832725388
203 849358349
204 866174997
205 883303132
206 900669530
207 918290652
208 936139203
209 954295850
210 972631032
211 991322762
212 1010240437
213 1029450812
214 1048924984
215 1068689333
216 1088644861
217 1108969764
218 1129558808
219 1150442157
220 1171558937
221 1193033074
222 1214747016
223 1236818666
224 1259114204
225 1281738118
226 1304683348
227 1327966088
228 1351468150
229 1375372626
230 1399536952
231 1424032061
232 1448830069
233 1474011259
234 1499431537
235 1525253010
236 1551369693
237 1577849066
238 1604634164
239 1631814342
240 1659192956
241 1687062204
242 1715235482
243 1743770386
244 1772640107
245 1801893871
246 1831461525
247 1861458190
248 1891762474
249 1922479025
250 1953528941
251 1985018947
252 2016743934
253 2048983359
254 2081578865
255 2114546848
256 2147881630
257 2181687668
258 2215807578
259 2250396415
260 2285300101
261 2320671591
262 2356451047
263 2392683959
264 2429188323
265 2466236730
266 2503657628
267 2541542067
268 2579818092
269 2618591358
270 2657653836
271 2697299498
272 2737293583
273 2777767580
274 2818701252
275 2860099042
276 2901852770
277 2944194216
278 2986949764
279 3030170540
280 3073756998
281 3117961730
282 3162542116
283 3207698550
284 3253261835
285 3299317322
286 3345852924
287 3392937315
288 3440349955
289 3488437800
290 3536947072
291 3586012865
292 3635543658
293 3685664656
294 3736164220
295 3787297175
296 3838878961
297 3891018466
298 3943699438
299 3996953901
300 4050554344
301 4104881209
302 4159715407
303 4215114638
304 4270988081
305 4327506968
306 4384464046
307 4442128208
308 4500224266
309 4558984903
310 4618259885
311 4678210211
312 4738544191
313 4799659811
314 4861304349
315 4923483480
316 4986283931
317 5049775451
318 5113745525
319 5178432204
320 5243576053
321 5309462052
322 5375911754
323 5443067229
324 5510660732
325 5579044900
326 5648041884
327 5717697053
328 5787920181
329 5858885916
330 5930312150
331 6002603372
332 6075451383
333 6148998237
334 6223207891
335 6298125476
336 6373481588
337 6449780074
338 6526675506
339 6604294665
340 6682481669
341 6761514942
342 6841084574
343 6921512587
344 7002540615
345 7084313478
346 7166824596
347 7250126492
348 7333946636
349 7418698590
350 7504016704
351 7590147761
352 7676936467
353 7764639165
354 7852935763
355 7942106654
356 8031950793
357 8122578354
358 8213987782
359 8306243724
360 8398923268
361 8492722825
362 8587234185
363 8682538135
364 8778523591
365 8875453338
366 8973052424
367 9071620872
368 9170832649
369 9270944839
370 9371813817
371 9473616734
372 9576039880
373 9679527060
374 9783727334
375 9888777849
376 9994630377
377 10101466794
378 10208911992
379 10317478966
380 10426699070
381 10536936279
382 10648016685
383 10760060713
384 10872692557
385 10986414402
386 11101025000
387 11216534230
388 11332890639
389 11450288555
390 11568306129
391 11687506870
392 11807427027
393 11928424166
394 12050318390
395 12173198029
396 12296723886
397 12421521888
398 12547170498
399 12673750579
400 12801132650
401 12929744506
402 13059122912
403 13189648789
404 13321022042
405 13453368572
406 13586703762
407 13721157347
408 13856300239
409 13992771355
410 14130077283
411 14268493054
412 14407836741
413 14548321812
414 14689605138
415 14832132147
416 14975504871
417 15120078060
418 15265615646
419 15412352902
420 15559677580
421 15708527946
422 15858335110
423 16009216750
424 16161078962
425 16314148208
426 16468147042
427 16623423185
428 16779661620
429 16937042025
430 17095466707
431 17255187559
432 17415604155
433 17577560515
434 17740468689
435 17904532956
436 18069708225
437 18236176082
438 18403577264
439 18572365686
440 18741972750
441 18912921684
442 19085031528
443 19258479908
444 19432776818
445 19608536341
446 19785415607
447 19963527326
448 20142614671
449 20323212291
450 20504609687
451 20687604978
452 20871663205
453 21057050754
454 21243630034
455 21431452003
456 21620228131
457 21810660331
458 22002219701
459 22195020966
460 22388928464
461 22584408844
462 22780782446
463 22978820028
464 23177885795
465 23378333830
466 23580118374
467 23783337104
468 23987412349
469 24193213394
470 24400155336
471 24608554725
472 24818134581
473 25029262432
474 25241488894
475 25455257100
476 25670158864
477 25886596002
478 26104390304
479 26323693592
480 26543778396
481 26765813151
482 26989125819
483 27213808182
484 27439797176
485 27667392099
486 27896105463
487 28126590069
488 28358239755
489 28591480192
490 28825938276
491 29062153100
492 29299411660
493 29538499261
494 29778868611
495 30020645132
496 30263860777
497 30508801402
498 30754967896
499 31002926894
500 31252025540
501 31502877839
502 31755187503
503 32009161491
504 32264013557
505 32520966878
506 32779299212
507 33039248372
508 33300642031
509 33563820143
510 33828071937
511 34094317332
512 34361866026
513 34631125427
514 34901982337
515 35174517082
516 35448268028
517 35724024201
518 36001176387
519 36280074558
520 36560236912
521 36842485178
522 37125957132
523 37411470404
524 37698375081
525 37986883398
526 38277175132
527 38569263497
528 38862440071
529 39157885158
530 39454744396
531 39753412082
532 40053555206
533 40355738003
534 40659312341
535 40964874990
536 41271917530
537 41580877925
538 41891512495
539 42203964835
540 42517513973
541 42833555001
542 43151175571
543 43470616592
544 43791562036
545 44114594453
546 44438961047
547 44765641449
548 45093843840
549 45423953378
550 45755667662
551 46089539709
552 46424677513
553 46762176034
554 47101382794
555 47442378761
556 47785179864
557 48130118680
558 48476457094
559 48825089145
560 49175009633
561 49527233970
562 49881361828
563 50237575624
564 50595163832
565 50955109057
566 51316857945
567 51680449685
568 52045895985
569 52413627699
570 52782706625
571 53154332053
572 53527499357
573 53902912516
574 54280131434
575 54659509792
576 55040244872
577 55423716526
578 55808949230
579 56196288183
580 56585302181
581 56976746024
582 57369865162
583 57765386687
584 58162625257
585 58561922152
586 58963424054
587 59367194080
588 59772319141
589 60180196900
590 60589846326
591 61001790073
592 61415556270
593 61831842210
594 62249634508
595 62669956529
596 63092272976
597 63516900305
598 63943518419
599 64372576755
600 64802877943
601 65236250897
602 65671463803
603 66108976705
604 66548543162
605 66990491776
606 67434329170
607 67880819714
608 68329044664
609 68779708475
610 69232485959
611 69687822472
612 70144688963
613 70604559157
614 71066457505
615 71530555608
616 71996604054
617 72465540924
618 72936295894
619 73409810138
620 73885084586
621 74362952987
622 74843156477
623 75325842728
624 75810096194
625 76297405058
626 76786939338
627 77278811119
628 77772934302
629 78269743261
630 78768025451
631 79269632847
632 79773199183
633 80279431104
634 80787988540
635 81299099917
636 81812063293
637 82328000773
638 82846159587
639 83366871813
640 83889576835
641 84415426555
642 84943238689
643 85474028439
644 86006758085
645 86542199996
646 87080121866
647 87620885044
648 88163250087
649 88708991212
650 89256805872
651 89807374695
652 90360392220
653 90916348368
654 91474341202
655 92035316449
656 92598465764
657 93164466120
658 93732908346
659 94304339268
660 94877298258
661 95453950518
662 96032961042
663 96614591255
664 97198659987
665 97785613804
666 98374805356
667 98967270665
668 99562041642
669 100159716019
670 100759813157
671 101362991624
672 101967842458
673 102576492624
674 103187587262
675 103801223061
676 104417562215
677 105037135371
678 105658898133
679 106283896184
680 106910977060
681 107541415083
682 108174440413
683 108810642097
684 109448708144
685 110090400591
686 110734603293
687 111381862614
688 112031588157
689 112684657914
690 113339770440
691 113998602744
692 114659864691
693 115323973110
694 115991138230
695 116661363229
696 117333684049
697 118009788178
698 118688563126
699 119370357865
700 120054409996
701 120742277200
702 121432266946
703 122125993677
704 122822039796
705 123521376271
706 124223775079
707 124929373866
708 125637237818
709 126348937620
710 127063154814
711 127780616452
712 128500847914
713 129224620655
714 129950620165
715 130680298402
716 131412831463
717 132148699670
718 132887551520
719 133629808166
720 134373692421
721 135122067616
722 135873294102
723 136627801879
724 137385181506
725 138146006526
726 138909405746
727 139676728302
728 140446387260
729 141219743673
730 141996081681
731 142776092752
732 143558480290
733 144344967914
734 145134355192
735 145926740343
736 146722241907
737 147521612608
738 148323514192
739 149129483528
740 149937968072
741 150750164269
742 151565500663
743 152384635051
744 153206028951
745 154031660602
746 154860426422
747 155692558124
748 156527661196
749 157366707353
750 158208210811
751 159054103713
752 159902716424
753 160755158199
754 161610775759
755 162470121018
756 163331677344
757 164198016926
758 165067449090
759 165940317035
760 166816049975
761 167696202095
762 168579121541
763 169466127182
764 170356202969
765 171249723818
766 172146993320
767 173048071401
768 173951566588
769 174859782652
770 175770658726
771 176685741685
772 177604091112
773 178526560084
774 179451737584
775 180381186094
776 181313794762
777 182250254457
778 183190383631
779 184134453786
780 185080744792
781 186032088413
782 186986687707
783 187945047274
784 188906551405
785 189872519598
786 190841586732
787 191815115064
788 192791794893
789 193772514476
790 194756606046
791 195744945703
792 196735677105
793 197731580856
794 198730949726
795 199734003149
796 200740752432
797 201751882040
798 202765744594
799 203784446593
800 204805929959
801 205832011691
802 206861911869
803 207895978296
804 208932932486
805 209974493999
806 211019760353
807 212069183544
808 213122078118
809 214179592598
810 215239698822
811 216305079212
812 217373558426
813 218446575215
814 219523285841
815 220604349746
816 221688172562
817 222777323415
818 223870138269
819 224966742946
820 226067071394
821 227172368072
822 228280886258
823 229394283530
824 230511016206
825 231631893355
826 232756906573
827 233886624447
828 235019094520
829 236157031776
830 237298413134
831 238444329743
832 239593722696
833 240748024806
834 241905837296
835 243068499333
836 244234670229
837 245405438692
838 246580435304
839 247760069852
840 248941860552
841 250129925281
842 251321836571
843 252518142378
844 253718353001
845 254923229843
846 256131604877
847 257345099979
848 258562279334
849 259784324703
850 261010144899
851 262241083958
852 263475236722
853 264714940698
854 265958359876
855 267206080665
856 268458130161
857 269715363741
858 270975808319
859 272241868093
860 273511333071
861 274785759694
862 276064688768
863 277348525056
864 278635104574
865 279927704745
866 281224529289
867 282525931139
868 283831254771
869 285141972018
870 286455964060
871 287775766925
872 289099391067
873 290427973943
874 291760957653
875 293098726938
876 294440224272
877 295787588422
878 297139102916
879 298495395723
880 299855204033
881 301221095773
882 302590218817
883 303965437643
884 305344399305
885 306728396120
886 308117212184
887 309511212748
888 310908445052
889 312311756249
890 313719173401
891 315131523031
892 316548516464
893 317970937341
894 319397242315
895 320829118890
896 322264765926
897 323705984443
898 325152029057
899 326603334254
900 328057468461
901 329518474736
902 330983768462
903 332454057209
904 333928912971
905 335409346354
906 336893898544
907 338384377754
908 339879043063
909 341378951263
910 342883060725
911 344393354539
912 345906903821
913 347427065940
914 348951831108
915 350481482195
916 352016026208
917 353556216931
918 355100232877
919 356650681359
920 358204822151
921 359765075404
922 361330250542
923 362900946307
924 364474881365
925 366055626569
926 367641271407
927 369232105929
928 370827496613
929 372429131235
930 374034404985
931 375646175267
932 377262591840
933 378884659519
934 380511777751
935 382144250788
936 383780351482
937 385423737466
938 387071608248
939 388725186133
940 390383194407
941 392047725001
942 393716487931
943 395391585052
944 397071050993
945 398755793508
946 400446283190
947 402142869802
948 403843362964
949 405550626023
950 407262351591
951 408980168802
952 410702394490
953 412431445946
954 414164623824
955 415904362171
956 417648968452
957 419399333697
958 421155199779
959 422916960740
960 424681987598
961 426454930257
962 428232716859
963 430016280673
964 431805075472
965 433600062893
966 435399312063
967 437205720229
968 439016541750
969 440833635355
970 442655987643
971 444484913773
972 446317650606
973 448157733173
974 450003097143
975 451853831350
976 453710054939
977 455573107685
978 457440723659
979 459315126384
980 461193727457
981 463079234831
982 464970466663
983 466868067661
984 468769644981
985 470678615664
986 472592897882
987 474513113789
988 476438672139
989 478371167270
990 480307438828
991 482251765860
992 484200761780
993 486156488921
994 488117655547
995 490085384258
996 492057673718
997 494037543670
998 496022777534
999 498013962561
1000 500010148307