1	1
2	5
3	4553
4	46777
5	82505
6	4290773
7	4492205
8	4976429
9	21537833
10	21549349
11	51127261
12	56786089
13	60296573
14	80837773
15	87761789
16	94424465
17	138644873
18	168865001
19	221395541
20	255881453
21	297460453
22	305198249
23	360306365
24	562654205
25	635374253
26	673867253
27	808333573
28	1164757553
29	1210317349
30	1282877053
31	1413860633
32	1437285853
33	2127909449
34	2278781053
35	2308430093
36	2544589253
37	2788421485
38	3265278253
39	3341653873
40	3893666393
41	4627220965
42	4842254693
43	5207066329
44	5439236897
45	8148235153
46	10912884713
47	11123462717
48	11410611313
49	15849087985
50	15972360953
51	16390290913
52	19510788937
53	21195396953
54	21836776385
55	23553438457
56	24155035453
57	24852239653
58	29144200753
59	29309134753
60	29344202353
61	32474149945
62	33187332785
63	33778974605
64	33909580253
65	36467662745
66	37642594993
67	39383099941
68	41469806381
69	42717600785
70	43626858733
71	45528958933
72	46350828893
73	46414810081
74	50036341813
75	51279565921
76	52378931153
77	55882096273
78	57970119353
79	62277238565
80	63329417245
81	64122554765
82	66574942393
83	67027522201
84	74440572989
85	76724916845
86	83864574433
87	89593053553
88	94985968157
89	100547595865
90	107142367777
91	117111156893
92	117948884173
93	118705733513
94	120791571629
95	133413292301
96	164713757885
97	167344915013
98	182281276453
99	185952519353
100	192012537553
101	193200297293
102	194262384193
103	195006048253
104	218064811253
105	223257156389
106	234795389333
107	240674291861
108	241985326313
109	267263191133
110	292231411865
111	296709699289
112	310193698853
113	316733142613
114	332214597809
115	337375488089
116	339582319313
117	346460768657
118	347878024805
119	355878295237
120	378326622313
121	389736251033
122	454507246313
123	458496122633
124	474350247893
125	484056243245
126	519273923353
127	528092988517
128	530932628285
129	540889244353
130	545971651865
131	587267042113
132	700570620605
133	702952571753
134	714336962485
135	727577937505
136	728533863149
137	736551924313
138	758261027653
139	810273936205
140	827906878753
141	834727408973
142	843572120345
143	877464438989
144	911357986717
145	927178912705
146	975248267633
147	1012554230509
148	1061817386633
149	1111477324961
150	1178571759593
151	1193043083053
152	1240003369685
153	1248151337813
154	1274940134953
155	1305251291753
156	1314819900397
157	1338644471713
158	1356925042085
159	1397460487733
160	1552495655441
161	1628406476453
162	1825934803465
163	1869908894753
164	1902057460033
165	1954738188913
166	1957568764357
167	2095442643265
168	2175248231953
169	2182879405633
170	2260320059741
171	2299374175465
172	2310405641633
173	2328103507033
174	2355678185717
175	2364084001945
176	2546232501881
177	2611699897865
178	2626207059233
179	2670710585693
180	2698815757193
181	2702356765553
182	2736522564793
183	2805202678645
184	2843182896557
185	2888103791953
186	2892840316673
187	3156067895053
188	3192715085981
189	3240754044713
190	3256607326745
191	3329100056285
192	3380847420953
193	3390087542117
194	3492575508061
195	3518362268753
196	3578446003753
197	3703354366253
198	3885804800153
199	3891300699653
200	3962974382573
201	4322889757673
202	4338589062629
203	4401325678445
204	4490515543153
205	4559914666709
206	4585191435421
207	4634654510405
208	4785239052553
209	5190549837853
210	5309316680573
211	5378351455753
212	5496347520193
213	5509781052233
214	5540287263085
215	5567791588453
216	5645801543581
217	5728545517753
218	5732527688737
219	5800262548373
220	5883308000573
221	6207293958953
222	6304366520273
223	6437870789353
224	6454131879653
225	6486132498953
226	6734502137821
227	6998109226753
228	7053918385517
229	7103350259405
230	7326109319545
231	7620653989633
232	7630351870913
233	7788516754385
234	8002490018981
235	8131453536253
236	8356095329753
237	8446210336973
238	8506661641481
239	8751222449573
240	8860567485673
241	9044497265653
242	9071256992801
243	9324994752713
244	9420271510253
245	9433810675481
246	9452600371493
247	9494898202957
248	9578734408753
249	9635388156553
250	9891748500929
251	10039364505173
252	10042215235433
253	10340303962453
254	10344460139653
255	10350923789573
256	10500576638653
257	10564574470817
258	10674103994921
259	10841538985553
260	10857844779785
261	10857880675253
262	11064170867753
263	11483589986053
264	11652563320369
265	11767830185933
266	11778060524233
267	12003709464841
268	12401332293353
269	12495141608953
270	12754846408853
271	12792229581953
272	13238346313573
273	13243553666045
274	13262924536013
275	13275465083653
276	13278392095153
277	13299030726193
278	13399305288821
279	13780672598813
280	13802160456013
281	13970776547213
282	14000471362153
283	14526525250513
284	14957323878605
285	15640679659753
286	15807932490353
287	15821239571693
288	16288466515753
289	16324218002381
290	16684130926921
291	16771865027485
292	17082403948873
293	17102923349053
294	17524257271993
295	17761156230373
296	18011559295733
297	18416806524353
298	18960224482373
299	18960625964465
300	19129325057573
301	19429680386581
302	19486036559993
303	19909946424553
304	20782324668949
305	21172719865685
306	21782130998653
307	21792172942853
308	21886821682057
309	22409631660133
310	22432070553665
311	22536902786653
312	22857175989365
313	22903340399033
314	23049334224853
315	23492826916289
316	24291568201553
317	25150416559453
318	25743908233501
319	25878440598937
320	26307739984753
321	27346019937953
322	27368099637833
323	28975459780585
324	29124066759985
325	29594889641593
326	29978909329393
327	30150835503853
328	30628523418553
329	30675829361005
330	30813000108673
331	32380857104053
332	32720459642993
333	33385156034653
334	33801777117265
335	34263183835877
336	34626015694273
337	34683003816737
338	34797035863901
339	34938527067413
340	35266699156153
341	35377257649673
342	35674931089801
343	36410423526641
344	37446330563645
345	37606044219461
346	37623201616549
347	38033956752613
348	38185137500513
349	38352192146005
350	38437245002341
351	38648650952453
352	38659997567561
353	39476239689253
354	39536997850873
355	39561905116165
356	40129738702265
357	40187810449181
358	40217566182797
359	40620120083953
360	41080707309073
361	41196880416793
362	42059205073993
363	42077710747153
364	42689365436273
365	42975901976837
366	43040823672941
367	43480776727573
368	43669958397497
369	45719528590013
370	45952189407673
371	46546340875453
372	47305143403885
373	47556820321013
374	48540763068185
375	48629455938913
376	49284562047893
377	49492868740213
378	49529666301937
379	49540328268049
380	49780714739297
381	51438839989813
382	51455744177309
383	51617726082653
384	52148888778605
385	52179502407793
386	52315151822053
387	52389224865617
388	52720757967881
389	52793279608865
390	52873913842753
391	53251899820681
392	53264442863453
393	53587181297653
394	53663170747553
395	54847958108705
396	57114671407853
397	57243835121609
398	57336366283145
399	57364509857693
400	60916880070049
401	61479417155593
402	61661000379553
403	61874407503653
404	62043552085253
405	62073783475805
406	62160301859113
407	62375845584853
408	62413997095453
409	63335889528733
410	63498883051273
411	64088865397313
412	66138105679913
413	66468011930141
414	67673755580161
415	68654041269797
416	68727097977253
417	68735133673253
418	70052401770965
419	70216212725753
420	70369888496053
421	72198431015153
422	72465137778673
423	73498449177541
424	73789382379653
425	73997975806121
426	75957404854753
427	77408442989881
428	77479558037885
429	77884167658153
430	78285973052213
431	79161133728553
432	79527116819933
433	80096861754913
434	80557898969089
435	81308623538453
436	81431818352693
437	82014782599753
438	83376330668413
439	85226800537553
440	85430421590153
441	86271742209293
442	86730597751073
443	86758445421833
444	87163387462513
445	87904397572513
446	89277239656993
447	91906644179353
448	92618093675033
449	93291328483993
450	93402320485477
451	93762174396953
452	94225832175313
453	95173672873373
454	95231850283573
455	95993823741533
456	96578884080661
457	97486644096593
458	100147679623085
459	100646797137253
460	101930068329673
461	102327956580013
462	105418624892285
463	105554089344889
464	106589062112417
465	107379416285833
466	109502557285553
467	110550438424429
468	110698816786253
469	111233951722169
470	111959300561573
471	112865972056477
472	112939268482681
473	114159752174653
474	121661430640753
475	122125462863953
476	124414279655053
477	127196204744353
478	127748888500873
479	127998802299553
480	133246079439853
481	133940782988093
482	135831352935281
483	135879846375913
484	137741427265445
485	138356525394181
486	139166676946333
487	140534701576645
488	140797299479245
489	140939760193853
490	141095209577585
491	142558153764757
492	144402197652365
493	144704177375453
494	146985644199397
495	147267753729253
496	148334734185553
497	151405619161553
498	151540813589953
499	152297524521853
500	153206896234549
501	153760667720953
502	155103982295753
503	157371437888437
504	158080529406257
505	158093112860453
506	158295690619433
507	160016152391153
508	161874793288633
509	163903507915897
510	165617352333709
511	165972307769713
512	169403717936573
513	171822579510653
514	172317289388605
515	172676548302653
516	172852731188413
517	172940085562793
518	174506990482205
519	175637768522453
520	176964265023857
521	177405310645657
522	178679291282413
523	187264606117753
524	190007391296453
525	190232752629793
526	190824625816373
527	193098327945253
528	193414736688253
529	199021071919673
530	199562009336693
531	200198574672853
532	202858727093753
533	204504368795653
534	205805566496533
535	206136139400173
536	207244062237005
537	208880835694105
538	209440165985053
539	209447158285753
540	209698204068565
541	212500915881973
542	212553315324353
543	212820750892753
544	213426118112353
545	214893969818797
546	216829959948605
547	217859206858373
548	218336487120053
549	223055567724853
550	224027599593073
551	224836169522065
552	224885794266409
553	226168295317033
554	228215555556173
555	231967601382469
556	232195624380037
557	233985251342153
558	234236915018473
559	234558962974573
560	239310744346985
561	241775199504829
562	241990361575537
563	243958418531753
564	248886816932785
565	253946686984817
566	256523107635161
567	260152508157545
568	263455934140753
569	264489961660109
570	266126234491813
571	267918002151581
572	269824105656745
573	273059481342365
574	275187937089145
575	276688779514633
576	281603117381953
577	286528597906253
578	287388556383685
579	287431569835153
580	288734416890065
581	290068069741453
582	290312888496193
583	292585235147845
584	297700257204353
585	302043958906693
586	303055411138945
587	306073018228253
588	307100862740093
589	312129791661353
590	313192738528673
591	319232833908173
592	320680689824953
593	321866991325493
594	324304967629369
595	325495080866413
596	325784757114365
597	328125941553301
598	333004486632205
599	337254248441113
600	342883006800953
601	343808958220153
602	344741490338365
603	344866701826793
604	346908343431653
605	353141508943733
606	354742919235253
607	357018557010377
608	362101097419253
609	362961271342997
610	363855125980349
611	364558272635833
612	366088848821153
613	368322147989545
614	371137104784253
615	374998761328985
616	376410546427205
617	378352568400953
618	379163360291453
619	381185256273853
620	384071998362253
621	385705851805333
622	386123087946053
623	389585484930953
624	391861034236493
625	399715440911933
626	405997327999801
627	408466753163389
628	414508787637913
629	414821069970445
630	421078774938253
631	422132120692753
632	422689111356097
633	423048895496713
634	423546095075953
635	425321646832085
636	426397507311233
637	427573555017865
638	431403935551865
639	432880911495385
640	434871001672565
641	435463841702633
642	440413397058253
643	444956928700253
644	445632503839729
645	447559709050457
646	447679933886573
647	449322274909693
648	451337604620269
649	453909564099533
650	456157886289013
651	459492139606373
652	459552745228853
653	460903552224041
654	461611481503253
655	463925451105833
656	465305416330753
657	472251895942753
658	487121427253553
659	489191084897245
660	493945202036353
661	494713272621857
662	496628195279653
663	502308787791385
664	503316492503233
665	517366660282013
666	519095162201593
667	519289252482653
668	520169511431705
669	523671484912033
670	525456303387473
671	526317875493413
672	535499422071253
673	537075028252073
674	540432713651665
675	542261383829245
676	545268158126453
677	552352286665273
678	552936650961553
679	557871120785333
680	559448187914453
681	565557735244505
682	576813067204433
683	577057283315873
684	577229652472553
685	580803745317253
686	584862220450945
687	585398562202373
688	588052001960153
689	588523407413581
690	597221140736993
691	600450878621309
692	601392549829333
693	611573593304677
694	617263084953353
695	620222164606453
696	626702610515153
697	628431277380553
698	632347542904717
699	634663602157133
700	635728972961813
701	635894776746245
702	637788046906013
703	641414245520233
704	641522298723253
705	644385042104345
706	658966395585193
707	675211118231653
708	677242750634453
709	686264691354245
710	687055955788933
711	690133685370433
712	690246331460689
713	690984337684189
714	692353910421785
715	698161405590133
716	700358717058653
717	705303508619153
718	705771156558653
719	707067757005613
720	708807788695373
721	710535353002621
722	711852289802293
723	719363006712353
724	721320462809873
725	722350936856693
726	726282158812213
727	726733439994853
728	728507421631993
729	733118586020021
730	738362786536565
731	748907499781873
732	752766640688065
733	766680187827193
734	768610859801333
735	775241480111933
736	780262328741305
737	781201962471053
738	781797761242501
739	784227574445093
740	791737463106593
741	799205424367613
742	801802140718153
743	805462607155573
744	805885318373453
745	808439169667769
746	809352852748961
747	811516808964865
748	821981401188853
749	826227000353149
750	827900967414797
751	832447054478185
752	833985626428685
753	834811933205365
754	847168779135313
755	856051995779753
756	856507077682441
757	859372902292753
758	869226265858505
759	881713910194493
760	888287270624393
761	889900025748905
762	895424732455753
763	896893109050273
764	902344255968193
765	903604903624153
766	905366538960593
767	908193540738305
768	911462722330345
769	916581817407353
770	917626037315809
771	923087270901253
772	924938303031865
773	927756392982613
774	938953023387473
775	942691095495973
776	958139646583633
777	958527372651553
778	964751857833613
779	965432859218545
780	965737807020353
781	969146860235753