1	1
2	9
3	35
4	91
5	242
6	442
7	833
8	1273
9	2024
10	3306
11	4464
12	6586
13	8897
14	11137
15	14288
16	18762
17	24190
18	28670
19	35778
20	42813
21	49275
22	59329
23	69056
24	81702
25	98067
26	112110
27	124836
28	140919
29	155325
30	173568
31	210312
32	233835
33	262903
34	285923
35	327949
36	355001
37	393285
38	434395
39	472610
40	519000
41	568504
42	607436
43	676522
44	720662
45	774013
46	821273
47	914052
48	1014427
49	1083698
50	1145458
51	1219289
52	1307091
53	1375869
54	1494705
55	1595713
56	1701347
57	1811715
58	1898355
59	2016283
60	2123798
61	2218720
62	2381504
63	2587396
64	2717207
65	2832337
66	2968388
67	3206728
68	3377414
69	3596308
70	3738488
71	3905239
72	4099421
73	4323994
74	4532696
75	4748112
76	4944147
77	5171755
78	5434136
79	5648887
80	5927228
81	6245614
82	6452246
83	6789112
84	7007672
85	7296180
86	7558023
87	7860643
88	8207720
89	8491159
90	8741903
91	9034582
92	9493301
93	9887074
94	10208381
95	10621714
96	10958861
97	11347137
98	11882968
99	12201590
100	12909342
101	13350082
102	13901606
103	14366634
104	14841796
105	15219434
106	15710556
107	16324470
108	16841200
109	17368604
110	17787196
111	18331400
112	18886530
113	19389225
114	19834617
115	20613508
116	21347864
117	21827278
118	22380377
119	23012373
120	23656123
121	24164177
122	25051752
123	25657623
124	26349457
125	27132806
126	28013362
127	28832903
128	29752939
129	30609608
130	31397322
131	32198230
132	32923073
133	33838558
134	34679684
135	35440531
136	36401384
137	37186711
138	38474069
139	39594163
140	40839938
141	41597812
142	42780668
143	43561390
144	44455385
145	45249307
146	46494863
147	47992339
148	48950126
149	49801384
150	50776331
151	52363039
152	53376266
153	54276244
154	55307111
155	57367750
156	58448849
157	59803006
158	61312142
159	62714347
160	63865670
161	65166858
162	66485092
163	68390108
164	69613903
165	70995659
166	72395001
167	73962294
168	75401116
169	77320679
170	78651346
171	80152502
172	81351238
173	83205824
174	84433288
175	86000108
176	87922984
177	89194166
178	91163242
179	92463992
180	94125450
181	96882136
182	98426747
183	99800737
184	101367188
185	103134912
186	104922490
187	106922591
188	108754689
189	110607001
190	114074459
191	115600933
192	117950297
193	120128206
194	122542922
195	124570902
196	126620248
197	128906933
198	131659020
199	133571835
200	135722425
201	137895029
202	139633561
203	141840605
204	144769092
205	147506958
206	151235110
207	153106532
208	155228887
209	157612475
210	159522415
211	161942123
212	164131558
213	166080380
214	168295855
215	171572882
216	173576758
217	176122094
218	182463826
219	185132810
220	187826400
221	190822437
222	195254233
223	198628139
224	202616701
225	205219724
226	207547960
227	210179543
228	213125973
229	216398850
230	219099549
231	221511303
232	224550313
233	228552212
234	232291888
235	234803390
236	237644905
237	240180167
238	243051442
239	246270710
240	250516245
241	254816176
242	258492509
243	262890168
244	266307178
245	269403569
246	272870211
247	276719664
248	279890931
249	283803144
250	287024811
251	292102479
252	295394106
253	299078770
254	302038262
255	305387677
256	309139955
257	312147865
258	315945503
259	320558977
260	327204476
261	331149864
262	334721931
263	337907409
264	345612406
265	349305389
266	352601965
267	357589451
268	363051834
269	366440748
270	371562132
271	376301481
272	380645095
273	385020155
274	389426769
275	396553543
276	401066237
277	405155788
278	408807968
279	414782907
280	420356643
281	426454390
282	431671067
283	438839812
284	445616450
285	450533238
286	454995393
287	458988015
288	463487610
289	467510232
290	473557188
291	480167887
292	485314337
293	490495113
294	498821713
295	503072915
296	511020004
297	515348846
298	525031084
299	530538236
300	536623129
301	542209601
302	547281844
303	551823950
304	556936153
305	563196638
306	568939224
307	575858538
308	580541538
309	587550084
310	595784706
311	602932380
312	608960494
313	616810481
314	621740089
315	627285416
316	632248384
317	639670250
318	647770905
319	652847271
320	662306352
321	667467558
322	673907224
323	679748231
324	684973519
325	692794493
326	700030018
327	710589332
328	723242697
329	729422328
330	736296082
331	743881751
332	754226920
333	759912122
334	766296277
335	774087386
336	784710715
337	790549097
338	797104732
339	805104041
340	812445315
341	819827755
342	826529510
343	836165097
344	842227773
345	855662745
346	863327239
347	869543381
348	877273395
349	884291034
350	892096216
351	903000092
352	910928202
353	918125505
354	924573021
355	932601097
356	939884252
357	947988840
358	958529215
359	966749243
360	975012777
361	986568273
362	994141188
363	1002565264
364	1013513735
365	1022887276
366	1031483354
367	1039282321
368	1056423689
369	1070353575
370	1080992631
371	1090845804
372	1099026111
373	1108108927
374	1115483423
375	1124637639
376	1140936705
377	1152943180
378	1160554196
379	1174501357
380	1184940962
381	1193616505
382	1205998256
383	1219398784
384	1231051868
385	1239046138
386	1247996309
387	1258869010
388	1268855168
389	1278889512
390	1288010763
391	1296197493
392	1305372504
393	1315557376
394	1326773789
395	1336078396
396	1344421724
397	1354779816
398	1367196252
399	1375653858
400	1388190414
401	1399788051
402	1409398350
403	1424202570
404	1437047514
405	1451019085
406	1459846505
407	1470799653
408	1480743048
409	1489654350
410	1506081759
411	1521567471
412	1531758714
413	1543072366
414	1555531259
415	1566958791
416	1577332242
417	1595518768
418	1608275525
419	1622224399
420	1634002901
421	1645833657
422	1658857062
423	1673096616
424	1688575999
425	1705319111
426	1716366994
427	1728620126
428	1740926592
429	1750923198
430	1776376677
431	1786564323
432	1801568619
433	1815457536
434	1826995395
435	1844658615
436	1856329794
437	1870497471
438	1887210574
439	1900307066
440	1917204009
441	1929193416
442	1942480582
443	1964692133
444	1980724069
445	1991731691
446	2011758100
447	2038395350
448	2050996705
449	2062331327
450	2080240398
451	2094311554
452	2107116221
453	2125280184
454	2139549406
455	2155219499
456	2168267686
457	2184066539
458	2209480381
459	2221418399
460	2234751466
461	2246741564
462	2265694131
463	2295925854
464	2308211046
465	2323332850
466	2338514180
467	2353755144
468	2367627531
469	2382974767
470	2395498643
471	2415284070
472	2429369745
473	2449342492
474	2462093828
475	2480766094
476	2493611678
477	2516898463
478	2529879287
479	2553396592
480	2569531658
481	2596340137
482	2620308770
483	2638323631
484	2653347962
485	2666870152
486	2681963723
487	2695541353
488	2724784847
489	2743257988
490	2764972187
491	2782056027
492	2802388431
493	2816427849
494	2832095196
495	2849418772
496	2863564208
497	2880986904
498	2901743688
499	2916038178
500	2938600897
501	2959635623
502	2974122895
503	2995315229
504	3019971571
505	3038038019
506	3054476926
507	3072659054
508	3092613475
509	3110940683
510	3129333357
511	3156436350
512	3180242365
513	3195462251
514	3212455174
515	3238284086
516	3257204880
517	3274419039
518	3295238796
519	3317935602
520	3338948487
521	3358247863
522	3377614433
523	3411591817
524	3431213387
525	3447236701
526	3470644937
527	3497862877
528	3515961248
529	3535968552
530	3567270316
531	3583749014
532	3607795918
533	3635745842
534	3654348685
535	3671088311
536	3695519635
537	3723916655
538	3742813114
539	3765637031
540	3798295539
541	3817472346
542	3838660000
543	3855974642
544	3875292397
545	3896644685
546	3914077045
547	3941548976
548	3961118419
549	3996887378
550	4034921368
551	4063043507
552	4081094527
553	4101220598
554	4123453812
555	4145759260
556	4163986760
557	4186404768
558	4225625478
559	4244119272
560	4266852382
561	4300236743
562	4323197493
563	4352627632
564	4371504092
565	4394701860
566	4424443195
567	4458662228
568	4477867468
569	4499278859
570	4522929501
571	4555446465
572	4577106420
573	4596601662
574	4633905322
575	4678128575
576	4706975791
577	4731452915
578	4751492647
579	4780618073
580	4800776077
581	4830087623
582	4850364235
583	4879862429
584	4904873091
585	4925328249
586	4955107425
587	4975682031
588	5005649175
589	5031044179
590	5058875288
591	5112852432
592	5143456476
593	5164650954
594	5195445870
595	5223968931
596	5250185509
597	5281320203
598	5322300363
599	5348893339
600	5382904010
601	5417073405
602	5439082521
603	5480900119
604	5508067541
605	5532824452
606	5560134242
607	5587524258
608	5630098678
609	5652704360
610	5685478144
611	5723475356
612	5751448434
613	5776940361
614	5799915069
615	5825497356
616	5877029329
617	5900303195
618	5936643210
619	5965296658
620	6007162667
621	6038707576
622	6067718210
623	6096811590
624	6141965182
625	6184696127
626	6208879351
627	6235781150
628	6265438704
629	6289761246
630	6319549000
631	6349420580
632	6384850744
633	6414927716
634	6453357099
635	6491955358
636	6539047658
637	6564119860
638	6594808034
639	6622778041
640	6670494269
641	6704355466
642	6760985735
643	6789545710
644	6815312102
645	6843967837
646	6875551295
647	6901461505
648	6941847656
649	6970810759
650	7014375281
651	7081490217
652	7119760473
653	7152300949
654	7193772380
655	7238377348
656	7271318798
657	7310302984
658	7352421791
659	7379733469
660	7410081536
661	7443505524
662	7480045065
663	7513666933
664	7553470877
665	7581198331
666	7612021910
667	7658286550
668	7692415520
669	7726634364
670	7757836911
671	7792215787
672	7820432183
673	7861224049
674	7889580893
675	7940063158
676	7984454117
677	8022673498
678	8076948530
679	8109118489
680	8144556611
681	8189738454
682	8218965846
683	8254699450
684	8290524980
685	8326442544
686	8398406223
687	8434734427
688	8484312173
689	8517609148
690	8557587977
691	8601011383
692	8641259780
693	8688315087
694	8745612547
695	8779658090
696	8810393926
697	8844544109
698	8912691666
699	8960793829
700	8998842071
701	9030135049
702	9085509746
703	9123906954
704	9162399616
705	9214858220
706	9260583844
707	9313447376
708	9349037107
709	9430326263
710	9469845009
711	9509460721
712	9549173507
713	9592537072
714	9632465978
715	9668917057
716	9701847041
717	9752794284
718	9793113526
719	9829911917
720	9863145997
721	9903693725
722	9973550935
723	10014469943
724	10048140823
725	10085528894
726	10148849910
727	10182817236
728	10220534919
729	10273232170
730	10307430950
731	10349163798
732	10387234593
733	10466870679
734	10509102241
735	10551433937
736	10590059812
737	10636387001
738	10686676537
739	10779369722
740	10841795155
741	10877455685
742	10920897063
743	10960555278
744	10996385190
745	11036156445
746	11072076837
747	11123751483
748	11183479089
749	11227634041
750	11267927180
751	11316239857
752	11368676393
753	11413287309
754	11486070648
755	11527026663
756	11564018655
757	11609133919
758	11703024005
759	11744555908
760	11794315433
761	11848304659
762	11894263241
763	11940326349
764	11990619690
765	12036915478
766	12095762933
767	12138178084
768	12184835666
769	12223230484
770	12270051866
771	12312771217
772	12359780087
773	12398432701
774	12454091237
775	12492908323
776	12561624284
777	12609233016
778	12686977155
779	12730662570
780	12791673577
781	12857223917
782	12953386636
783	13002207380
784	13081666159
785	13126497206
786	13202099214
787	13256038563
788	13305713077
789	13351074548
790	13400942502
791	13468703598
792	13518886672
793	13569179060
794	13628545936
795	13670116574
796	13729751410
797	13794088421
798	13849582714
799	13909767560
800	13951912636
801	14012367290
802	14068425727
803	14133817442
804	14194825846
805	14288342339
806	14331375115
807	14379087458
808	14436183823
809	14488762019
810	14536772446
811	14594241779
812	14675383683
813	14737994337
814	14791333363
815	14844785123
816	14888840227
817	14942467547
818	15005767591
819	15074048714
820	15118531186
821	15182322212
822	15236641902
823	15291075298
824	15345622508
825	15405151945
826	15459952475
827	15524654569
828	15579734411
829	15625090429
830	15680348351
831	15735720879
832	15791208121
833	15856750487
834	15917501572
835	16018372385
836	16074627543
837	16171170603
838	16217794647
839	16304836333
840	16356804944
841	16418997805
842	16486432481
843	16605054837
844	16668027738
845	16756784620
846	16809924959
847	16857992233
848	16926757997
849	16985364765
850	17033707605
851	17092498333
852	17146190048
853	17236574802
854	17301096807
855	17376291466
856	17467535354
857	17553854011
858	17614007237
859	17663659783
860	17739970310
861	17800510134
862	17871870870
863	17921977320
864	17993632416
865	18043926354
866	18105068416
867	18177166022
868	18260326912
869	18316548863
870	18427430028
871	18478612530
872	18568230099
873	18619683441
874	18693225777
875	18744869127
876	18818710311
877	18920520150
878	18978206625
879	19030394787
880	19088217822
881	19157338011
882	19249107540
883	19313031040
884	19377078074
885	19429923736
886	19511191919
887	19604088016
888	19674499709
889	19733641756
890	19798598270
891	19932624174
892	19986644310
893	20063799096
894	20118013944
895	20183872756
896	20244041927
897	20310123747
898	20376331153
899	20448521198
900	20515008084
901	20575735971
902	20660143714
903	20727064886
904	20800039459
905	20885064950
906	20946522913
907	21037912037
908	21123614076
909	21203572962
910	21325827007
911	21394357775
912	21481137390
913	21550009678
914	21606872618
915	21724609282
916	21800135783
917	21906392985
918	21988533069
919	22058607661
920	22153431539
921	22217711146
922	22275893474
923	22346515566
924	22429693002
925	22506860127
926	22577959273
927	22642932632
928	22714263618
929	22861147642
930	22958288408
931	23043106762
932	23102828066
933	23194311669
934	23279700465
935	23339817051
936	23444691612
937	23505101838
938	23616893362
939	23748378647
940	23861055891
941	23935363615
942	24042187160
943	24155858862
944	24230895112
945	24293023166
946	24407485134
947	24476492901
948	24552156535
949	24614792777
950	24703858213
951	24786537530
952	24876023134
953	24952451906
954	25029016092
955	25112387097
956	25182566220
957	25259537308
958	25323211088
959	25413856894
960	25477742186
961	25575482589
962	25646387136
963	25724174884
964	25802099126
965	25866514684
966	25965164963
967	26036676682
968	26142621140
969	26262652830
970	26334804873
971	26413962793
972	26541764804
973	26614468051
974	26701183784
975	26781108276
976	26854180167
977	26941357068
978	27014675199
979	27123271731
980	27203981749
981	27277762676
982	27387054202
983	27489571757
984	27563909968
985	27631211138
986	27798598284
987	27873589371
988	28020442984
989	28103126156
990	28185950142
991	28290586753
992	28395505640
993	28507962580
994	28591665530
995	28668223345
996	28737573077
997	28814288452
998	28942437536
999	29026913280
1000	29133628807