0 0
1 1
2 346
3 6219
4 36628
5 124405
6 316206
7 672511
8 1267624
9 2189673
10 3540610
11 5436211
12 8006076
13 11393629
14 15756118
15 21264615
16 28104016
17 36473041
18 46584234
19 58663963
20 72952420
21 89703621
22 109185406
23 131679439
24 157481208
25 186900025
26 220259026
27 257895171
28 300159244
29 347415853
30 400043430
31 458434231
32 522994336
33 594143649
34 672315898
35 757958635
36 851533236
37 953514901
38 1064392654
39 1184669343
40 1314861640
41 1455500041
42 1607128866
43 1770306259
44 1945604188
45 2133608445
46 2334918646
47 2550148231
48 2779924464
49 3024888433
50 3285695050
51 3563013051
52 3857524996
53 4169927269
54 4500930078
55 4851257455
56 5221647256
57 5612851161
58 6025634674
59 6460777123
60 6919071660
61 7401325261
62 7908358726
63 8441006679
64 9000117568
65 9586553665
66 10201191066
67 10844919691
68 11518643284
69 12223279413
70 12959759470
71 13729028671
72 14532046056
73 15369784489
74 16243230658
75 17153385075
76 18101262076
77 19087889821
78 20114310294
79 21181579303
80 22290766480
81 23442955281
82 24639242986
83 25880740699
84 27168573348
85 28503879685
86 29887812286
87 31321537551
88 32806235704
89 34343100793
90 35933340690
91 37578177091
92 39278845516
93 41036595309
94 42852689638
95 44728405495
96 46665033696
97 48663878881
98 50726259514
99 52853507883
100 55046970100
101 57308006101
102 59637989646
103 62038308319
104 64510363528
105 67055570505
106 69675358306
107 72371169811
108 75144461724
109 77996704573
110 80929382710
111 83943994311
112 87042051376
113 90225079729
114 93494619018
115 96852222715
116 100299458116
117 103837906341
118 107469162334
119 111194834863
120 115016546520
121 118935933721
122 122954646706
123 127074349539
124 131296720108
125 135623450125
126 140056245126
127 144596824471
128 149246921344
129 154008282753
130 158882669530
131 163871856331
132 168977631636
133 174201797749
134 179546170798
135 185012580735
136 190602871336
137 196318900201
138 202162538754
139 208135672243
140 214240199740
141 220478034141
142 226851102166
143 233361344359
144 240010715088
145 246801182545
146 253734728746
147 260813349531
148 268039054564
149 275413867333
150 282939825150
151 290618979151
152 298453394296
153 306445149369
154 314596336978
155 322909063555
156 331385449356
157 340027628461
158 348837748774
159 357817972023
160 366970473760
161 376297443361
162 385801084026
163 395483612779
164 405347260468
165 415394271765
166 425626905166
167 436047432991
168 446658141384
169 457461330313
170 468459313570
171 479654418771
172 491048987356
173 502645374589
174 514445949558
175 526453095175
176 538669208176
177 551096699121
178 563737992394
179 576595526203
180 589671752580
181 602969137381
182 616490160286
183 630237314799
184 644213108248
185 658420061785
186 672860710386
187 687537602851
188 702453301804
189 717610383693
190 733011438790
191 748659071191
192 764555898816
193 780704553409
194 797107680538
195 813767939595
196 830688003796
197 847870560181
198 865318309614
199 883033966783
200 901020260200
201 919279932201
202 937815738946
203 956630450419
204 975726850428
205 995107736605
206 1014775920406
207 1034734227111
208 1054985495824
209 1075532579473
210 1096378344810
211 1117525672411
212 1138977456676
213 1160736605829
214 1182806041918
215 1205188700815
216 1227887532216
217 1250905499641
218 1274245580434
219 1297910765763
220 1321904060620
221 1346228483821
222 1370887068006
223 1395882859639
224 1421218919008
225 1446898320225
226 1472924151226
227 1499299513771
228 1526027523444
229 1553111309653
230 1580554015630
231 1608358798431
232 1636528828936
233 1665067291849
234 1693977385698
235 1723262322835
236 1752925329436
237 1782969645501
238 1813398524854
239 1844215235143
240 1875423057840
241 1907025288241
242 1939025235466
243 1971426222459
244 2004231585988
245 2037444676645
246 2071068858846
247 2105107510831
248 2139564024664
249 2174441806233
250 2209744275250
251 2245474865251
252 2281637023596
253 2318234211469
254 2355269903878
255 2392747589655
256 2430670771456
257 2469042965761
258 2507867702874
259 2547148526923
260 2586888995860
261 2627092681461
262 2667763169326
263 2708904058879
264 2750518963368
265 2792611509865
266 2835185339266
267 2878244106291
268 2921791479484
269 2965831141213
270 3010366787670
271 3055402128871
272 3100940888656
273 3146986804689
274 3193543628458
275 3240615125275
276 3288205074276
277 3336317268421
278 3384955514494
279 3434123633103
280 3483825458680
281 3534064839481
282 3584845637586
283 3636171728899
284 3688047003148
285 3740475363885
286 3793460728486
287 3847007028151
288 3901118207904
289 3955798226593
290 4011051056890
291 4066880685291
292 4123291112116
293 4180286351509
294 4237870431438
295 4296047393695
296 4354821293896
297 4414196201481
298 4474176199714
299 4534765385683
300 4595967870300
301 4657787778301
302 4720229248246
303 4783296432519
304 4846993497328
305 4911324622705
306 4976294002506
307 5041905844411
308 5108164369924
309 5175073814373
310 5242638426910
311 5310862470511
312 5379750221976
313 5449305971929
314 5519534024818
315 5590438698915
316 5662024326316
317 5734295252941
318 5807255838534
319 5880910456663
320 5955263494720
321 6030319353921
322 6106082449306
323 6182557209739
324 6259748077908
325 6337659510325
326 6416295977326
327 6495661963071
328 6575761965544
329 6656600496553
330 6738182081730
331 6820511260531
332 6903592586236
333 6987430625949
334 7072029960598
335 7157395184935
336 7243530907536
337 7330441750801
338 7418132350954
339 7506607358043
340 7595871435940
341 7685929262341
342 7776785528766
343 7868444940559
344 7960912216888
345 8054192090745
346 8148289308946
347 8243208632131
348 8338954834764
349 8435532705133
350 8532947045350
351 8631202671351
352 8730304412896
353 8830257113569
354 8931065630778
355 9032734835755
356 9135269613556
357 9238674863061
358 9342955496974
359 9448116441823
360 9554162637960
361 9661099039561
362 9768930614626
363 9877662344979
364 9987299226268
365 10097846267965
366 10209308493366
367 10321690939591
368 10434998657584
369 10549236712113
370 10664410181770
371 10780524158971
372 10897583749956
373 11015594074789
374 11134560267358
375 11254487475375
376 11375380860376
377 11497245597721
378 11620086876594
379 11743909900003
380 11868719884780
381 11994522061581
382 12121321674886
383 12249123982999
384 12377934258048
385 12507757785985
386 12638599866586
387 12770465813451
388 12903360954004
389 13037290629493
390 13172260194990
391 13308275019391
392 13445340485416
393 13583461989609
394 13722644942338
395 13862894767795
396 14004216903996
397 14146616802781
398 14290099929814
399 14434671764583
400 14580337800400
401 14727103544401
402 14874974517546
403 15023956254619
404 15174054304228
405 15325274228805
406 15477621604606
407 15631102021711
408 15785721084024
409 15941484409273
410 16098397629010
411 16256466388611
412 16415696347276
413 16576093178029
414 16737662567718
415 16900410217015
416 17064341840416
417 17229463166241
418 17395779936634
419 17563297907563
420 17732022848820
421 17901960544021
422 18073116790606
423 18245497399839
424 18419108196808
425 18593955020425
426 18770043723426
427 18947380172371
428 19125970247644
429 19305819843453
430 19486934867830
431 19669321242631
432 19852984903536
433 20037931800049
434 20224167895498
435 20411699167035
436 20600531605636
437 20790671216101
438 20982124017054
439 21174896040943
440 21368993334040
441 21564421956441
442 21761187982066
443 21959297498659
444 22158756607788
445 22359571424845
446 22561748079046
447 22765292713431
448 22970211484864
449 23176510564033
450 23384196135450
451 23593274397451
452 23803751562196
453 24015633855669
454 24228927517678
455 24443638801855
456 24659773975656
457 24877339320361
458 25096341131074
459 25316785716723
460 25538679400060
461 25762028517661
462 25986839419926
463 26213118471079
464 26440872049168
465 26670106546065
466 26900828367466
467 27133043932891
468 27366759675684
469 27601982043013
470 27838717495870
471 28076972509071
472 28316753571256
473 28558067184889
474 28800919866258
475 29045318145475
476 29291268566476
477 29538777687021
478 29787852078694
479 30038498326903
480 30290723030880
481 30544532803681
482 30799934272186
483 31056934077099
484 31315538872948
485 31575755328085
486 31837590124686
487 32101049958751
488 32366141540104
489 32632871592393
490 32901246853090
491 33171274073491
492 33442960018716
493 33716311467709
494 33991335213238
495 34268038061895
496 34546426834096
497 34826508364081
498 35108289499914
499 35391777103483
500 35676978050500
501 35963899230501
502 36252547546846
503 36542929916719
504 36835053271128
505 37128924554905
506 37424550726706
507 37721938759011
508 38021095638124
509 38322028364173
510 38624743951110
511 38929249426711
512 39235551832576
513 39543658224129
514 39853575670618
515 40165311255115
516 40478872074516
517 40794265239541
518 41111497874734
519 41430577118463
520 41751510122920
521 42074304054121
522 42398966091906
523 42725503429939
524 43053923275708
525 43384232850525
526 43716439389526
527 44050550141671
528 44386572369744
529 44724513350353
530 45064380373930
531 45406180744731
532 45749921780836
533 46095610814149
534 46443255190398
535 46792862269135
536 47144439423736
537 47497994041401
538 47853533523154
539 48211065283843
540 48570596752140
541 48932135370541
542 49295688595366
543 49661263896759
544 50028868758688
545 50398510678945
546 50770197169146
547 51143935754731
548 51519733974964
549 51897599382933
550 52277539545550
551 52659562043551
552 53043674471496
553 53429884437769
554 53818199564578
555 54208627487955
556 54601175857756
557 54995852337661
558 55392664605174
559 55791620351623
560 56192727282160
561 56595993115761
562 57001425585226
563 57409032437179
564 57818821432068
565 58230800344165
566 58644976961566
567 59061359086191
568 59479954533784
569 59900771133913
570 60323816729970
571 60749099179171
572 61176626352556
573 61606406134989
574 62038446425158
575 62472755135575
576 62909340192576
577 63348209536321
578 63789371120794
579 64232832913803
580 64678602896980
581 65126689065781
582 65577099429486
583 66029842011199
584 66484924847848
585 66942355990185
586 67402143502786
587 67864295464051
588 68328819966204
589 68795725115293
590 69265019031190
591 69736709847591
592 70210805712016
593 70687314785809
594 71166245244138
595 71647605275995
596 72131403084196
597 72617646885381
598 73106344910014
599 73597505402383
600 74091136620600
601 74587246836601
602 75085844336146
603 75586937418819
604 76090534398028
605 76596643601005
606 77105273368806
607 77616432056311
608 78130128032224
609 78646369679073
610 79165165393210
611 79686523584811
612 80210452677876
613 80736961110229
614 81266057333518
615 81797749813215
616 82332047028616
617 82868957472841
618 83408489652834
619 83950652089363
620 84495453317020
621 85042901884221
622 85593006353206
623 86145775300039
624 86701217314608
625 87259341000625
626 87820154975626
627 88383667870971
628 88949888331844
629 89518825017253
630 90090486600030
631 90664881766831
632 91242019218136
633 91821907668249
634 92404555845298
635 92989972491235
636 93578166361836
637 94169146226701
638 94762920869254
639 95359499086743
640 95958889690240
641 96561101504641
642 97166143368666
643 97774024134859
644 98384752669588
645 98998337853045
646 99614788579246
647 100234113756031
648 100856322305064
649 101481423161833
650 102109425275650
651 102740337609651
652 103374169140796
653 104010928859869
654 104650625771478
655 105293268894055
656 105938867259856
657 106587429914961
658 107238965919274
659 107893484346523
660 108550994284260
661 109211504833861
662 109875025110526
663 110541564243279
664 111211131374968
665 111883735662265
666 112559386275666
667 113238092399491
668 113919863231884
669 114604707984813
670 115292635884070
671 115983656169271
672 116677778093856
673 117375010925089
674 118075363944058
675 118778846445675
676 119485467738676
677 120195237145621
678 120908164002894
679 121624257660703
680 122343527483080
681 123065982847881
682 123791633146786
683 124520487785299
684 125252556182748
685 125987847772285
686 126726372000886
687 127468138329351
688 128213156232304
689 128961435198193
690 129712984729290
691 130467814341691
692 131225933565316
693 131987351943909
694 132752079035038
695 133520124410095
696 134291497654296
697 135066208366681
698 135844266160114
699 136625680661283
700 137410461510700
701 138198618362701
702 138990160885446
703 139785098760919
704 140583441684928
705 141385199367105
706 142190381530906
707 142998997913611
708 143811058266324
709 144626572353973
710 145445549955310
711 146268000862911
712 147093934883176
713 147923361836329
714 148756291556418
715 149592733891315
716 150432698702716
717 151276195866141
718 152123235270934
719 152973826820263
720 153827980431120
721 154685706034321
722 155547013574506
723 156411913010139
724 157280414313508
725 158152527470725
726 159028262481726
727 159907629360271
728 160790638133944
729 161677298844153
730 162567621546130
731 163461616308931
732 164359293215436
733 165260662362349
734 166165733860198
735 167074517833335
736 167987024419936
737 168903263772001
738 169823246055354
739 170746981449643
740 171674480148340
741 172605752358741
742 173540808301966
743 174479658212959
744 175422312340488
745 176368780947145
746 177319074309346
747 178273202717331
748 179231176475164
749 180193005900733
750 181158701325750
751 182128273095751
752 183101731570096
753 184079087121969
754 185060350138378
755 186045531020155
756 187034640181956
757 188027688052261
758 189024685073374
759 190025641701423
760 191030568406360
761 192039475671961
762 193052373995826
763 194069273889379
764 195090185877868
765 196115120500365
766 197144088309766
767 198177099872791
768 199214165769984
769 200255296595713
770 201300502958170
771 202349795479371
772 203403184795156
773 204460681555189
774 205522296422958
775 206588040075775
776 207657923204776
777 208731956514921
778 209810150724994
779 210892516567603
780 211979064789180
781 213069806149981
782 214164751424086
783 215263911399399
784 216367296877648
785 217474918674385
786 218586787618986
787 219702914554651
788 220823310338404
789 221947985841093
790 223076951947390
791 224210219555791
792 225347799578616
793 226489702942009
794 227635940585938
795 228786523464195
796 229941462544396
797 231100768807981
798 232264453250214
799 233432526880183
800 234605000720800
801 235781885808801
802 236963193194746
803 238148933943019
804 239339119131828
805 240533759853205
806 241732867213006
807 242936452330911
808 244144526340424
809 245357100388873
810 246574185637410
811 247795793261011
812 249021934448476
813 250252620402429
814 251487862339318
815 252727671489415
816 253972059096816
817 255221036419441
818 256474614729034
819 257732805311163
820 258995619465220
821 260263068504421
822 261535163755806
823 262811916560239
824 264093338272408
825 265379440260825
826 266670233907826
827 267965730609571
828 269265941776044
829 270570878831053
830 271880553212230
831 273194976371031
832 274514159772736
833 275838114896449
834 277166853235098
835 278500386295435
836 279838725598036
837 281181882677301
838 282529869081454
839 283882696372543
840 285240376126440
841 286602919932841
842 287970339395266
843 289342646131059
844 290719851771388
845 292101967961245
846 293489006359446
847 294880978638631
848 296277896485264
849 297679771599633
850 299086615695850
851 300498440501851
852 301915257759396
853 303337079224069
854 304763916665278
855 306195781866255
856 307632686624056
857 309074642749561
858 310521662067474
859 311973756416323
860 313430937648460
861 314893217630061
862 316360608241126
863 317833121375479
864 319310768940768
865 320793562858465
866 322281515063866
867 323774637506091
868 325272942148084
869 326776440966613
870 328285145952270
871 329799069109471
872 331318222456456
873 332842618025289
874 334372267861858
875 335907184025875
876 337447378590876
877 338992863644221
878 340543651287094
879 342099753634503
880 343661182815280
881 345227950972081
882 346800070261386
883 348377552853499
884 349960410932548
885 351548656696485
886 353142302357086
887 354741360139951
888 356345842284504
889 357955761043993
890 359571128685490
891 361191957489891
892 362818259751916
893 364450047780109
894 366087333896838
895 367730130438295
896 369378449754496
897 371032304209281
898 372691706180314
899 374356668059083
900 376027202250900
901 377703321174901
902 379385037264046
903 381072362965119
904 382765310738728
905 384463893059305
906 386168122415106
907 387878011308211
908 389593572254524
909 391314817783773
910 393041760439510
911 394774412779111
912 396512787373776
913 398256896808529
914 400006753682218
915 401762370607515
916 403523760210916
917 405290935132741
918 407063908027134
919 408842691562063
920 410627298419320
921 412417741294521
922 414214032897106
923 416016185950339
924 417824213191308
925 419638127370925
926 421457941253926
927 423283667618871
928 425115319258144
929 426952908977953
930 428796449598330
931 430645953953131
932 432501434890036
933 434362905270549
934 436230377969998
935 438103865877535
936 439983381896136
937 441868938942601
938 443760549947554
939 445658227855443
940 447561985624540
941 449471836226941
942 451387792648566
943 453309867889159
944 455238074962288
945 457172426895345
946 459112936729546
947 461059617519931
948 463012482335364
949 464971544258533
950 466936816385950
951 468908311827951
952 470886043708696
953 472870025166169
954 474860269352178
955 476856789432355
956 478859598586156
957 480868710006861
958 482884136901574
959 484905892491223
960 486933990010560
961 488968442708161
962 491009263846426
963 493056466701579
964 495110064563668
965 497170070736565
966 499236498537966
967 501309361299391
968 503388672366184
969 505474445097513
970 507566692866370
971 509665429059571
972 511770667077756
973 513882420335389
974 516000702260758
975 518125526295975
976 520256905896976
977 522394854533521
978 524539385689194
979 526690512861403
980 528848249561380
981 531012609314181
982 533183605658686
983 535361252147599
984 537545562347448
985 539736549838585
986 541934228215186
987 544138611085251
988 546349712070604
989 548567544806893
990 550792122943590
991 553023460143991
992 555261570085216
993 557506466458209
994 559758162967738
995 562016673332395
996 564282011284596
997 566554190570581
998 568833224950414
999 571119128197983
1000 573411914101000