0 1
1 8
2 36
3 120
4 330
5 792
6 1716
7 3432
8 6434
9 11432
10 19412
11 31704
12 50058
13 76728
14 114564
15 167112
16 238722
17 334664
18 461252
19 625976
20 837642
21 1106520
22 1444500
23 1865256
24 2384418
25 3019752
26 3791348
27 4721816
28 5836490
29 7163640
30 8734692
31 10584456
32 12751362
33 15277704
34 18209892
35 21598712
36 25499594
37 29972888
38 35084148
39 40904424
40 47510562
41 54985512
42 63418644
43 72906072
44 83550986
45 95463992
46 108763460
47 123575880
48 140036226
49 158288328
50 178485252
51 200789688
52 225374346
53 252422360
54 282127700
55 314695592
56 350342946
57 389298792
58 431804724
59 478115352
60 528498762
61 583236984
62 642626468
63 706978568
64 776620034
65 851893512
66 933158052
67 1020789624
68 1115181642
69 1216745496
70 1325911092
71 1443127400
72 1568863010
73 1703606696
74 1847867988
75 2002177752
76 2167088778
77 2343176376
78 2531038980
79 2731298760
80 2944602242
81 3171620936
82 3413051972
83 3669618744
84 3942071562
85 4231188312
86 4537775124
87 4862667048
88 5206728738
89 5570855144
90 5955972212
91 6363037592
92 6793041354
93 7247006712
94 7725990756
95 8231085192
96 8763417090
97 9324149640
98 9914482916
99 10535654648
100 11188941002
101 11875657368
102 12597159156
103 13354842600
104 14150145570
105 14984548392
106 15859574676
107 16776792152
108 17737813514
109 18744297272
110 19797948612
111 20900520264
112 22053813378
113 23259678408
114 24520016004
115 25836777912
116 27211967882
117 28647642584
118 30145912532
119 31708943016
120 33338955042
121 35038226280
122 36809092020
123 38653946136
124 40575242058
125 42575493752
126 44657276708
127 46823228936
128 49076051970
129 51418511880
130 53853440292
131 56383735416
132 59012363082
133 61742357784
134 64576823732
135 67518935912
136 70571941154
137 73739159208
138 77023983828
139 80429883864
140 83960404362
141 87619167672
142 91409874564
143 95336305352
144 99402321026
145 103611864392
146 107968961220
147 112477721400
148 117142340106
149 121967098968
150 126956367252
151 132114603048
152 137446354466
153 142956260840
154 148649053940
155 154529559192
156 160602696906
157 166873483512
158 173347032804
159 180028557192
160 186923368962
161 194036881544
162 201374610788
163 208942176248
164 216745302474
165 224789820312
166 233081668212
167 241626893544
168 250431653922
169 259502218536
170 268844969492
171 278466403160
172 288373131530
173 298571883576
174 309069506628
175 319872967752
176 330989355138
177 342425879496
178 354189875460
179 366288803000
180 378730248842
181 391521927896
182 404671684692
183 418187494824
184 432077466402
185 446349841512
186 461012997684
187 476075449368
188 491545849418
189 507432990584
190 523745807012
191 540493375752
192 557684918274
193 575329801992
194 593437541796
195 612017801592
196 631080395850
197 650635291160
198 670692607796
199 691262621288
200 712355764002
201 733982626728
202 756153960276
203 778880677080
204 802173852810
205 826044727992
206 850504709636
207 875565372872
208 901238462594
209 927535895112
210 954469759812
211 982052320824
212 1010296018698
213 1039213472088
214 1068817479444
215 1099121020712
216 1130137259042
217 1161879542504
218 1194361405812
219 1227596572056
220 1261598954442
221 1296382658040
222 1331961981540
223 1368351419016
224 1405565661698
225 1443619599752
226 1482528324068
227 1522307128056
228 1562971509450
229 1604537172120
230 1647020027892
231 1690436198376
232 1734802016802
233 1780134029864
234 1826448999572
235 1873763905112
236 1922095944714
237 1971462537528
238 2021881325508
239 2073370175304
240 2125947180162
241 2179630661832
242 2234439172484
243 2290391496632
244 2347506653066
245 2405803896792
246 2465302720980
247 2526022858920
248 2587984285986
249 2651207221608
250 2715712131252
251 2781519728408
252 2848650976586
253 2917127091320
254 2986969542180
255 3058200054792
256 3130840612866
257 3204913460232
258 3280441102884
259 3357446311032
260 3435952121162
261 3515981838104
262 3597559037108
263 3680707565928
264 3765451546914
265 3851815379112
266 3939823740372
267 4029501589464
268 4120874168202
269 4213967003576
270 4308805909892
271 4405416990920
272 4503826642050
273 4604061552456
274 4706148707268
275 4810115389752
276 4915989183498
277 5023797974616
278 5133569953940
279 5245333619240
280 5359117777442
281 5474951546856
282 5592864359412
283 5712885962904
284 5835046423242
285 5959376126712
286 6085905782244
287 6214666423688
288 6345689412098
289 6479006438024
290 6614649523812
291 6752651025912
292 6893043637194
293 7035860389272
294 7181134654836
295 7328900149992
296 7479190936610
297 7632041424680
298 7787486374676
299 7945560899928
300 8106300469002
301 8269740908088
302 8435918403396
303 8604869503560
304 8776631122050
305 8951240539592
306 9128735406596
307 9309153745592
308 9492533953674
309 9678914804952
310 9868335453012
311 10060835433384
312 10256454666018
313 10455233457768
314 10657212504884
315 10862432895512
316 11070936112202
317 11282764034424
318 11497958941092
319 11716563513096
320 11938620835842
321 12164174401800
322 12393268113060
323 12625946283896
324 12862253643338
325 13102235337752
326 13345936933428
327 13593404419176
328 13844684208930
329 14099823144360
330 14358868497492
331 14621867973336
332 14888869712522
333 15159922293944
334 15435074737412
335 15714376506312
336 15997877510274
337 16285628107848
338 16577679109188
339 16874081778744
340 17174887837962
341 17480149467992
342 17789919312404
343 18104250479912
344 18423196547106
345 18746811561192
346 19075150042740
347 19408266988440
348 19746217873866
349 20089058656248
350 20436845777252
351 20789636165768
352 21147487240706
353 21510456913800
354 21878603592420
355 22251986182392
356 22630664090826
357 23014697228952
358 23404146014964
359 23799071376872
360 24199534755362
361 24605598106664
362 25017323905428
363 25434775147608
364 25858015353354
365 26287108569912
366 26722119374532
367 27163112877384
368 27610154724482
369 28063311100616
370 28522648732292
371 28988234890680
372 29460137394570
373 29938424613336
374 30423165469908
375 30914429443752
376 31412286573858
377 31916807461736
378 32428063274420
379 32946125747480
380 33471067188042
381 34002960477816
382 34541879076132
383 35087897022984
384 35641088942082
385 36201530043912
386 36769296128804
387 37344463590008
388 37927109416778
389 38517311197464
390 39115147122612
391 39720695988072
392 40334037198114
393 40955250768552
394 41584417329876
395 42221618130392
396 42866935039370
397 43520450550200
398 44182247783556
399 44852410490568
400 45531023056002
401 46218170501448
402 46913938488516
403 47618413322040
404 48331681953290
405 49053831983192
406 49784951665556
407 50525129910312
408 51274456286754
409 52033021026792
410 52800915028212
411 53578229857944
412 54365057755338
413 55161491635448
414 55967625092324
415 56783552402312
416 57609368527362
417 58445169118344
418 59291050518372
419 60147109766136
420 61013444599242
421 61890153457560
422 62777335486580
423 63675090540776
424 64583519186978
425 65502722707752
426 66432803104788
427 67373863102296
428 68326006150410
429 69289336428600
430 70263958849092
431 71249979060296
432 72247503450242
433 73256639150024
434 74277494037252
435 75310176739512
436 76354796637834
437 77411463870168
438 78480289334868
439 79561384694184
440 80654862377762
441 81760835586152
442 82879418294324
443 84010725255192
444 85154872003146
445 86311974857592
446 87482150926500
447 88665518109960
448 89862195103746
449 91072301402888
450 92295957305252
451 93533283915128
452 94784403146826
453 96049437728280
454 97328511204660
455 98621747941992
456 99929273130786
457 101251212789672
458 102587693769044
459 103938843754712
460 105304791271562
461 106685665687224
462 108081597215748
463 109492716921288
464 110919156721794
465 112361049392712
466 113818528570692
467 115291728757304
468 116780785322762
469 118285834509656
470 119807013436692
471 121344460102440
472 122898313389090
473 124468713066216
474 126055799794548
475 127659715129752
476 129280601526218
477 130918602340856
478 132573861836900
479 134246525187720
480 135936738480642
481 137644648720776
482 139370403834852
483 141114152675064
484 142876045022922
485 144656231593112
486 146454864037364
487 148272094948328
488 150108077863458
489 151962967268904
490 153836918603412
491 155730088262232
492 157642633601034
493 159574712939832
494 161526485566916
495 163498111742792
496 165489752704130
497 167501570667720
498 169533728834436
499 171586391393208
500 173659723525002
501 175753891406808
502 177869062215636
503 180005404132520
504 182163086346530
505 184342279058792
506 186543153486516
507 188765881867032
508 191010637461834
509 193277594560632
510 195566928485412
511 197878815594504
512 200213433286658
513 202570960005128
514 204951575241764
515 207355459541112
516 209782794504522
517 212233762794264
518 214708548137652
519 217207335331176
520 219730310244642
521 222277659825320
522 224849572102100
523 227446236189656
524 230067842292618
525 232714581709752
526 235386646838148
527 238084231177416
528 240807529333890
529 243556737024840
530 246332051082692
531 249133669459256
532 251961791229962
533 254816616598104
534 257698346899092
535 260607184604712
536 263543333327394
537 266506997824488
538 269498384002548
539 272517698921624
540 275565150799562
541 278640949016312
542 281745304118244
543 284878427822472
544 288040533021186
545 291231833785992
546 294452545372260
547 297702884223480
548 300983067975626
549 304293315461528
550 307633846715252
551 311004882976488
552 314406646694946
553 317839361534760
554 321303252378900
555 324798545333592
556 328325467732746
557 331884248142392
558 335475116365124
559 339098303444552
560 342754041669762
561 346442564579784
562 350164106968068
563 353918904886968
564 357707195652234
565 361529217847512
566 365385211328852
567 369275417229224
568 373200077963042
569 377159437230696
570 381153740023092
571 385183232626200
572 389248162625610
573 393348778911096
574 397485331681188
575 401658072447752
576 405867254040578
577 410113130611976
578 414395957641380
579 418715991939960
580 423073491655242
581 427468716275736
582 431901926635572
583 436373384919144
584 440883354665762
585 445432100774312
586 450019889507924
587 454646988498648
588 459313666752138
589 464020194652344
590 468766843966212
591 473553887848392
592 478381600845954
593 483250258903112
594 488160139365956
595 493111520987192
596 498104683930890
597 503139909777240
598 508217481527316
599 513337683607848
600 518500801876002
601 523707123624168
602 528956937584756
603 534250533935000
604 539588204301770
605 544970241766392
606 550396940869476
607 555868597615752
608 561385509478914
609 566947975406472
610 572556295824612
611 578210772643064
612 583911709259978
613 589659410566808
614 595454182953204
615 601296334311912
616 607186174043682
617 613124013062184
618 619110163798932
619 625144940208216
620 631228657772042
621 637361633505080
622 643544185959620
623 649776635230536
624 656059302960258
625 662392512343752
626 668776588133508
627 675211856644536
628 681698645759370
629 688237284933080
630 694828105198292
631 701471439170216
632 708167621051682
633 714916986638184
634 721719873322932
635 728576620101912
636 735487567578954
637 742453057970808
638 749473435112228
639 756549044461064
640 763680233103362
641 770867349758472
642 778110744784164
643 785410770181752
644 792767779601226
645 800182128346392
646 807654173380020
647 815184273329000
648 822772788489506
649 830420080832168
650 838126514007252
651 845892453349848
652 853718265885066
653 861604320333240
654 869550987115140
655 877558638357192
656 885627647896706
657 893758391287112
658 901951245803204
659 910206590446392
660 918524805949962
661 926906274784344
662 935351381162388
663 943860511044648
664 952434052144674
665 961072393934312
666 969775927649012
667 978545046293144
668 987380144645322
669 996281619263736
670 1005249868491492
671 1014285292461960
672 1023388293104130
673 1032559274147976
674 1041798641129828
675 1051106801397752
676 1060484164116938
677 1069931140275096
678 1079448142687860
679 1089035586004200
680 1098693886711842
681 1108423463142696
682 1118224735478292
683 1128098125755224
684 1138044057870602
685 1148062957587512
686 1158155252540484
687 1168321372240968
688 1178561748082818
689 1188876813347784
690 1199267003211012
691 1209732754746552
692 1220274506932874
693 1230892700658392
694 1241587778726996
695 1252360185863592
696 1263210368719650
697 1274138775878760
698 1285145857862196
699 1296232067134488
700 1307397858109002
701 1318643687153528
702 1329970012595876
703 1341377294729480
704 1352865995819010
705 1364436580105992
706 1376089513814436
707 1387825265156472
708 1399644304337994
709 1411547103564312
710 1423534137045812
711 1435605881003624
712 1447762813675298
713 1460005415320488
714 1472334168226644
715 1484749556714712
716 1497252067144842
717 1509842187922104
718 1522520409502212
719 1535287224397256
720 1548143127181442
721 1561088614496840
722 1574124185059140
723 1587250339663416
724 1600467581189898
725 1613776414609752
726 1627177346990868
727 1640670887503656
728 1654257547426850
729 1667937840153320
730 1681712281195892
731 1695581388193176
732 1709545680915402
733 1723605681270264
734 1737761913308772
735 1752014903231112
736 1766365179392514
737 1780813272309128
738 1795359714663908
739 1810005041312504
740 1824749789289162
741 1839594497812632
742 1854539708292084
743 1869585964333032
744 1884733811743266
745 1899983798538792
746 1915336474949780
747 1930792393426520
748 1946352108645386
749 1962016177514808
750 1977785159181252
751 1993659615035208
752 2009640108717186
753 2025727206123720
754 2041921475413380
755 2058223487012792
756 2074633813622666
757 2091153030223832
758 2107781714083284
759 2124520444760232
760 2141369804112162
761 2158330376300904
762 2175402747798708
763 2192587507394328
764 2209885246199114
765 2227296557653112
766 2244822037531172
767 2262462283949064
768 2280217897369602
769 2298089480608776
770 2316077638841892
771 2334182979609720
772 2352406112824650
773 2370747650776856
774 2389208208140468
775 2407788401979752
776 2426488851755298
777 2445310179330216
778 2464253008976340
779 2483317967380440
780 2502505683650442
781 2521816789321656
782 2541251918363012
783 2560811707183304
784 2580496794637442
785 2600307822032712
786 2620245433135044
787 2640310274175288
788 2660502993855498
789 2680824243355224
790 2701274676337812
791 2721854948956712
792 2742565719861794
793 2763407650205672
794 2784381403650036
795 2805487646371992
796 2826727047070410
797 2848100276972280
798 2869608009839076
799 2891250921973128
800 2913029692224002
801 2934945001994888
802 2956997535248996
803 2979187978515960
804 3001517020898250
805 3023985354077592
806 3046593672321396
807 3069342672489192
808 3092233054039074
809 3115265519034152
810 3138440772149012
811 3161759520676184
812 3185222474532618
813 3208830346266168
814 3232583851062084
815 3256483706749512
816 3280530633808002
817 3304725355374024
818 3329068597247492
819 3353561087898296
820 3378203558472842
821 3402996742800600
822 3427941377400660
823 3453038201488296
824 3478287956981538
825 3503691388507752
826 3529249243410228
827 3554962271754776
828 3580831226336330
829 3606856862685560
830 3633039939075492
831 3659381216528136
832 3685881458821122
833 3712541432494344
834 3739361906856612
835 3766343653992312
836 3793487448768074
837 3820794068839448
838 3848264294657588
839 3875898909475944
840 3903698699356962
841 3931664453178792
842 3959796962642004
843 3988097022276312
844 4016565429447306
845 4045202984363192
846 4074010490081540
847 4102988752516040
848 4132138580443266
849 4161460785509448
850 4190956182237252
851 4220625588032568
852 4250469823191306
853 4280489710906200
854 4310686077273620
855 4341059751300392
856 4371611564910626
857 4402342352952552
858 4433252953205364
859 4464344206386072
860 4495616956156362
861 4527072049129464
862 4558710334877028
863 4590532665936008
864 4622539897815554
865 4654732889003912
866 4687112500975332
867 4719679598196984
868 4752435048135882
869 4785379721265816
870 4818514491074292
871 4851840234069480
872 4885357829787170
873 4919068160797736
874 4952972112713108
875 4987070574193752
876 5021364436955658
877 5055854595777336
878 5090541948506820
879 5125427396068680
880 5160511842471042
881 5195796194812616
882 5231281363289732
883 5266968261203384
884 5302857804966282
885 5338950914109912
886 5375248511291604
887 5411751522301608
888 5448460876070178
889 5485377504674664
890 5522502343346612
891 5559836330478872
892 5597380407632714
893 5635135519544952
894 5673102614135076
895 5711282642512392
896 5749676558983170
897 5788285321057800
898 5827109889457956
899 5866151228123768
900 5905410304221002
901 5944888088148248
902 5984585553544116
903 6024503677294440
904 6064643439539490
905 6105005823681192
906 6145591816390356
907 6186402407613912
908 6227438590582154
909 6268701361815992
910 6310191721134212
911 6351910671660744
912 6393859219831938
913 6436038375403848
914 6478449151459524
915 6521092564416312
916 6563969634033162
917 6607081383417944
918 6650428839034772
919 6694013030711336
920 6737834991646242
921 6781895758416360
922 6826196370984180
923 6870737872705176
924 6915521310335178
925 6960547734037752
926 7005818197391588
927 7051333757397896
928 7097095474487810
929 7143104412529800
930 7189361638837092
931 7235868224175096
932 7282625242768842
933 7329633772310424
934 7376894893966452
935 7424409692385512
936 7472179255705634
937 7520204675561768
938 7568487047093268
939 7617027468951384
940 7665827043306762
941 7714886875856952
942 7764208075833924
943 7813791756011592
944 7863639032713346
945 7913751025819592
946 7964128858775300
947 8014773658597560
948 8065686555883146
949 8116868684816088
950 8168321183175252
951 8220045192341928
952 8272041857307426
953 8324312326680680
954 8376857752695860
955 8429679291219992
956 8482778101760586
957 8536155347473272
958 8589812195169444
959 8643749815323912
960 8697969382082562
961 8752472073270024
962 8807259070397348
963 8862331558669688
964 8917690726993994
965 8973337767986712
966 9029273877981492
967 9085500257036904
968 9142018108944162
969 9198828641234856
970 9255933065188692
971 9313332595841240
972 9371028451991690
973 9429021856210616
974 9487314034847748
975 9545906218039752
976 9604799639718018
977 9663995537616456
978 9723495153279300
979 9783299732068920
980 9843410523173642
981 9903828779615576
982 9964555758258452
983 10025592719815464
984 10086940928857122
985 10148601653819112
986 10210576167010164
987 10272865744619928
988 10335471666726858
989 10398395217306104
990 10461637684237412
991 10525200359313032
992 10589084538245634
993 10653291520676232
994 10717822610182116
995 10782679114284792
996 10847862344457930
997 10913373616135320
998 10979214248718836
999 11045385565586408
1000 11111888894100002