0 0
1 1
2 2
3 2
4 4
5 5
6 7
7 11
8 16
9 21
10 29
11 43
12 54
13 78
14 102
15 131
16 175
17 233
18 295
19 389
20 490
21 623
22 794
23 1009
24 1255
25 1579
26 1967
27 2443
28 3016
29 3737
30 4569
31 5627
32 6861
33 8371
34 10171
35 12350
36 14901
37 18025
38 21682
39 26068
40 31225
41 37415
42 44617
43 53258
44 63313
45 75235
46 89173
47 105645
48 124748
49 147327
50 173497
51 204207
52 239823
53 281513
54 329661
55 385916
56 450820
57 526308
58 613382
59 714400
60 830528
61 965087
62 1119606
63 1297962
64 1502616
65 1738372
66 2008270
67 2318701
68 2673581
69 3080693
70 3545626
71 4078033
72 4684883
73 5378769
74 6168699
75 7069937
76 8094818
77 9262291
78 10587776
79 12095579
80 13805296
81 15746816
82 17945983
83 20439693
84 23260327
85 26454663
86 30063674
87 34144687
88 38750504
89 43952105
90 49815303
91 56429077
92 63876010
93 72265337
94 81701925
95 92320298
96 104250816
97 117660929
98 132712907
99 149612027
100 168561856
101 189814819
102 213622594
103 240297015
104 270149714
105 303562193
106 340922037
107 382696337
108 429361993
109 481493362
110 539677434
111 604614942
112 677030241
113 757778695
114 847747791
115 947983501
116 1059572976
117 1183788743
118 1321963901
119 1475646223
120 1646461841
121 1836295782
122 2047130446
123 2281251643
124 2541077396
125 2829378797
126 3149093490
127 3503582024
128 3896410361
129 4331641614
130 4813604349
131 5347207782
132 5937690178
133 6590983128
134 7313420468
135 8112150815
136 8994830111
137 9970068256
138 11047096288
139 12236280598
140 13548741383
141 14996935299
142 16594251265
143 18355644883
144 20297204776
145 22436878965
146 24793982339
147 27390017058
148 30248155867
149 33394138880
150 36855720624
151 40663695478
152 44851275623
153 49455249089
154 54515330533
155 60075431327
156 66182973697
157 72890337814
158 80254098134
159 88336657153
160 97205457390
161 106934781352
162 117604926454
163 129304253393
164 142128281838
165 156182001258
166 171578952700
167 188443782262
168 206911300514
169 227129385607
170 249257967439
171 273472305644
172 299961986081
173 328934556866
174 360614530782
175 395247514527
176 433099167024
177 474459861453
178 519643707009
179 568993738759
180 622881006906
181 681710470994
182 745920102136
183 815987545036
184 892429382637
185 975808573979
186 1066733898411
187 1165868400034
188 1273928969664
189 1391695897313
190 1520012781588
191 1659797229702
192 1812041143617
193 1977822872982
194 2158307852508
195 2354762360896
196 2568554776560
197 2801171029030
198 3054216561372
199 3329433887029
200 3628705275960
201 3954072653964
202 4307741370546
203 4692102604549
204 5109738388636
205 5563447075296
206 6056249698719
207 6591418862647
208 7172486948104
209 7803278711924
210 8487921621599
211 9230882928910
212 10036982337862
213 10911434098326
214 11859862719514
215 12888350557860
216 14003457056382
217 15212272882827
218 16522443081598
219 17942228589364
220 19480534321763
221 21146978833211
222 22951928094567
223 24906574773821
224 27022978410545
225 29314155550859
226 31794127779011
227 34478023911376
228 37382137093495
229 40524041138514
230 43922657848974
231 47598389348605
232 51573197756767
233 55870755375438
234 60516538582011
235 65537998825361
236 70964672639211
237 76828376194985
238 83163334508483
239 90006402404442
240 97397215791596
241 105378443255309
242 113995962386708
243 123299146079564
244 133341068416875
245 144178829979435
246 155873797647476
247 168491974960011
248 182104280486672
249 196786969269541
250 212621956301931
251 229697295525200
252 248107555006801
253 267954362165018
254 289346837755099
255 312402216198773
256 337246347951096
257 364014404574706
258 392851459329457
259 423913289486178
260 457367045915971
261 493392165684298
262 532181144570061
263 573940574223937
264 618892032299479
265 667273262163780
266 719339196779509
267 775363300060637
268 835638744831902
269 900479936885302
270 970223868694242
271 1045231852110012
272 1125891071877153
273 1212616554831471
274 1305852952763550
275 1406076778992748
276 1513798452532268
277 1629564839410144
278 1753961593641987
279 1887616043859719
280 2031199874016115
281 2185432400424414
282 2351083638966865
283 2528978026355778
284 2719997926083312
285 2925087852735013
286 3145258478838452
287 3381591427851582
288 3635243850189918
289 3907453862290299
290 4199545768123395
291 4512936229467757
292 4849140222798328
293 5209778035893009
294 5596582059277342
295 6011404720311039
296 6456226220295422
297 6933163528854116
298 7444479196267294
299 7992591545591711
300 8580084703834912
301 9209720151178425
302 9884448131928548
303 10607420737542545
304 11382004883783269
305 12211797125450265
306 13100638406859759
307 14052630836344938
308 15072154442410837
309 16163886161546381
310 17332818867422356
311 18584282856144708
312 19923967446342517
313 21357945287583916
314 22892696865443905
315 24535137995878602
316 26292647617952393
317 28173098880848920
318 30184890651034573
319 32336982656178529
320 34638931185614545
321 37100928808965069
322 39733844816002170
323 42549270090433339
324 45559562899029696
325 48777899580826670
326 52218326369536965
327 55895816635266733
328 59826329517741094
329 64026874546755111
330 68515577954900399
331 73311755613739797
332 78435988000282455
333 83910202495501982
334 89757758108600327
335 96003538310733454
336 102674046751208583
337 109797511953125584
338 117403995404848146
339 125525509600030172
340 134196140068295391
341 143452178420326834
342 153332260066039576
343 163877514139102390
344 175131718861610442
345 187141470442642969
346 199956358299190361
347 213629155274207854
348 228216015184165734
349 243776686998807587
350 260374737481720964
351 278077792284326508
352 296957786794440852
353 317091237448955857
354 338559524271904704
355 361449196122118700
356 385852288817588763
357 411866668470087316
358 439596389576102964
359 469152081082940474
360 500651349340815781
361 534219212115959981
362 569988551878784844
363 608100603589322248
364 648705464467053523
365 691962642061303723
366 738041627367067346
367 787122510483966837
368 839396624751875793
369 895067238153047761
370 954350277069705132
371 1017475102540734873
372 1084685323245750823
373 1156239666821943273
374 1232412892804664297
375 1313496770394323902
376 1399801103367743192
377 1491654827013710115
378 1589407158422443998
379 1693428826820174550
380 1804113364206100727
381 1921878484960197272
382 2047167533570011554
383 2180451031226895229
384 2322228299317257189
385 2473029192807779166
386 2633415920337658413
387 2803984986469630668
388 2985369231664590936
389 3178240008020343981
390 3383309465082462950
391 3601332986565058850
392 3833111750938348039
393 4079495459770140573
394 4341385205395632474
395 4619736525029202275
396 4915562611510774599
397 5229937731287552534
398 5564000818347070940
399 5918959298502688421
400 6296093111248467224
401 6696758987615255969
402 7122394949761770900
403 7574525095091311167
404 8054764629054852830
405 8564825214179444413
406 9106520597904084605
407 9681772591810580160
408 10292617363292972454
409 10941212117715118518
410 11629842130484719813
411 12360928213043533481
412 13137034570608409872
413 13960877142003597421
414 14835332377902178964
415 15763446554681869211
416 16748445578645487351
417 17793745385288501965
418 18902962886860886914
419 20079927580892621113
420 21328693771558208951
421 22653553525202192773
422 24059050310522046446
423 25549993454156492088
424 27131473360925541573
425 28808877639560325516
426 30587908082130004504
427 32474598648943451897
428 34475334406156286991
429 36596871579779759571
430 38846358672568825675
431 41231358820272687490
432 43759873333296796893
433 46440366614132949358
434 49281792396346061772
435 52293621510593705531
436 55485871123567049125
437 58869135671581815158
438 62454619435294774043
439 66254170994922895056
440 70280319513350885327
441 74546313105743204791
442 79066159244511536892
443 83854667478975854516
444 88927494420749109346
445 94301191296702100973
446 99993254023266493534
447 106022176128489600789
448 112407504479155897238
449 119169898165886512278
450 126331190508118195310
451 133914454560691701073
452 141944072089406555158
453 150445806428710657695
454 159446879195548470534
455 168976051306518031224
456 179063708280493810236
457 189741950310850613739
458 201044687098898252017
459 213007737973026518097
460 225668937296362320035
461 239068245731136642198
462 253247867375821547745
463 268252373390830880649
464 284128832144049239551
465 300926946543946492571
466 318699198609213176947
467 337501001999012452277
468 357390862573340810611
469 378430547768997690987
470 400685264884023641372
471 424223849123174152701
472 449118961524115014202
473 475447297689714641603
474 503289807476946965961
475 532731926647187257673
476 563863820663238588323
477 596780641724630568325
478 631582799266161331469
479 668376245105525047579
480 707272773510140918060
481 748390337471931508159
482 791853381510923198007
483 837793192408890267148
484 886348268251309508396
485 937664707301224910272
486 991896617148234726175
487 1049206545789816453517
488 1109765935160950175426
489 1173755598915338340189
490 1241366225056033455963
491 1312798905377870042744
492 1388265692411656693280
493 1467990186006310778591
494 1552208150341797186167
495 1641168163699106968025
496 1735132301895460700174
497 1834376857918125930619
498 1939193098794328567932
499 2049888062457017721507
500 2166785395787997913999
501 2290226236845802854482
502 2420570142620717948794
503 2558196065594412042826
504 2703503380626368903173
505 2856912965739815942844
506 3018868338529196573038
507 3189836852084890879952
508 3370310952379880798096
509 3560809501366593107072
510 3761879167976716490672
511 3974095891657691958363
512 4198066420913970572265
513 4434429931908520015432
514 4683859729898675275144
515 4947065039022376758467
516 5224792883549072995498
517 5517830066615030411095
518 5827005249934202493104
519 6153191141055616126996
520 6497306792076520699273
521 6860320016984394210470
522 7243249932000916286496
523 7647169626759646919354
524 8073208971203698600260
525 8522557566755960406623
526 8996467847216507543918
527 9496258338727418290936
528 10023317084889105621724
529 10579105247230061108800
530 11165160887809639670475
531 11783102945098827833737
532 12434635410687777475679
533 13121551718995791723495
534 13845739358383134097110
535 14609184716968019355601
536 15413978172486935974758
537 16262319440735800584051
538 17156523192966901029144
539 18099024958128279075042
540 19092387321465554245836
541 20139306436848886736109
542 21242618865607551901939
543 22405308760850165226715
544 23630515411445699589734
545 24921541166409400599454
546 26281859755404966146393
547 27715125028039236730716
548 29225180129352945271593
549 30816067136298084278042
550 32492037174470169458884
551 34257561042197690444972
552 36117340363311765170908
553 38076319298227260009822
554 40139696836919780933425
555 42312939706196924702439
556 44601795917337790098844
557 47012308989524660471011
558 49550832877881465813156
559 52224047644852481929682
560 55038975906749710322402
561 58003000097823127721507
562 61123880586997320909364
563 64409774693587396327435
564 67869256640783759951895
565 71511338497548463695967
566 75345492151719322226426
567 79381672369700692410127
568 83630340989940646044076
569 88102492310751325619653
570 92809679724511487390162
571 97764043664470504613799
572 102978340921506932689614
573 108465975403253771896665
574 114241030398779721839712
575 120318302428008254210213
576 126713336745472682728857
577 133442464584991054264831
578 140522842221892172643746
579 147972491947470323190170
580 155810345040018766520297
581 164056286835965982256038
582 172731203993934987962903
583 181857034064920589782896
584 191456817470694464331210
585 201554752014205350294304
586 212176250034272799784402
587 223347998339895490964295
588 235098021047645760846864
589 247455745470099251536415
590 260452071191018170287972
591 274119442489039055796355
592 288491924259007348147432
593 303605281607789928670126
594 319497063288420024216050
595 336206689165884309180829
596 353775541894523451928810
597 372247063018362455597267
598 391666853691997580260487
599 412082780253026400134794
600 433545084862986556156014
601 456106501469278925001461
602 479822377326214869955374
603 504750800351139037438479
604 530952732576950291062943
605 558492150002611359707509
606 587436189128349009421031
607 617855300505138463991552
608 649823409612947649881602
609 683418085427918998038441
610 718720717023357252731970
611 755816698598095666043651
612 794795623310363909080158
613 835751486347194506020872
614 878782897643865972730591
615 923993304723233983767388
616 971491226109234007201539
617 1021390495827869496432089
618 1073810519493479150458096
619 1128876542541042852335747
620 1186719931149889762652116
621 1247478466471358515660757
622 1311296652757778189710932
623 1378326040061841541139785
624 1448725562160586166279815
625 1522661890434739287131851
626 1600309804419765193235290
627 1681852579826685235827882
628 1767482394816893787967548
629 1857400755402484279406712
630 1951818940830479344763471
631 2050958469902609607000053
632 2155051589170054785950923
633 2264341784042210925333245
634 2379084313837391351761642
635 2499546771909879586395994
636 2626009671977887882224942
637 2758767061890845593248922
638 2898127166066097047038767
639 3044413057946867257909169
640 3197963363826787025700060
641 3359132999516532349517765
642 3528293941323641457295736
643 3705836032955945567731162
644 3892167829956948293863480
645 4087717483430655395410144
646 4292933664813999195360200
647 4508286533614685202153799
648 4734268750036078271394269
649 4971396534581727907509379
650 5220210776739499131717271
651 5481278195028412969631233
652 5755192550702723706405990
653 6042575917603959478280608
654 6344080010667674496821685
655 6660387575801904237157653
656 6992213843875515525807983
657 7340308051780002937694805
658 7705455033555306550792328
659 8088476884811840730857687
660 8490234703714494243620334
661 8911630412053465022914024
662 9353608659967687425794416
663 9817158818164547236670954
664 10303317061528657455686980
665 10813168548310671783927113
666 11347849699145334239334862
667 11908550580467984482569027
668 12496517396967136751170495
669 13113055098054279486208101
670 13759530103411757291002504
671 14437373153048436811109417
672 15148082287385156441340565
673 15893225963288062502768108
674 16674446312074182361061299
675 17493462545939076685095275
676 18352074519378113035476398
677 19252166452630054869902540
678 20195710824310477363103847
679 21184772440893792602706129
680 22221512690860397909377634
681 23308193991853527703441463
682 24447184439369006937145423
683 25640962666068829728233697
684 26892122921011169555586207
685 28203380378699911962558845
686 29577576688083901660001206
687 31017685772292710747787797
688 32526819890150832808873877
689 34108235971218564882937115
690 35765342236393775072601727
691 37501705116868763544896063
692 39321056484556268405914400
693 41227301207916580263978160
694 43224525047474840617731598
695 45317002906197972775956330
696 47509207450298764810424071
697 49805818116982393518144557
698 52211730526093701245709587
699 54732066313644062391295487
700 57372183405689014224870225
701 60137686752126862928071062
702 63034439540534913153805675
703 66068574911343746606717978
704 69246508196255688518953322
705 72574949703088881331563357
706 76060918070899023919046205
707 79711754220604887271547097
708 83535135927085467080797664
709 87539093040197324808699754
710 91732023382980222003699667
711 96122709356915017143672957
712 100720335285002448326078774
713 105534505525151644334312505
714 110575263387364937734330496
715 115853110890060062492376622
716 121379029391970259959733781
717 127164501138062389677550081
718 133221531759123696361844735
719 139562673766824118747553438
720 146201051087392958788946041
721 153150384679374174104850600
722 160425019282388978037510172
723 168039951346342688839440511
724 176010858192121771096585606
725 184354128457532733140938000
726 193086893884001308877835285
727 202227062502469385962708449
728 211793353278865940221428534
729 221805332282677756912640108
730 232283450444272068398828606
731 243249082970021751782108783
732 254724570486614530527415286
733 266733261989595148727626231
734 279299559673743032421535323
735 292448965726846170629295104
736 306208131171228118643570494
737 320604906841657310970470275
738 335668396591328295056473609
739 351429012822216126590820204
740 367918534439453255793532861
741 385170167334356580788110455
742 403218607504393520598935380
743 422100106923750538578347374
744 441852542282169449846391705
745 462515486715519571722360935
746 484130284655946316586328506
747 506740129935702247606570467
748 530390147283542258245115217
749 555127477359329914112216944
750 581001365477716000495997952
751 608063254179055939338670749
752 636366879811423267168818940
753 665968373295465825000688385
754 696926365250059752154575306
755 729302095665236702130527046
756 763159528315630983962258746
757 798565470116895362683460329
758 835589695634916993384507778
759 874305076967603696187141425
760 914787719227057676446034702
761 957117101860688564833430104
762 1001376226058585877675916836
763 1047651768506065936808674320
764 1096034241749859686633569579
765 1146618161458932314582486381
766 1199502220871327166720640628
767 1254789472731955284329672600
768 1312587519037576318131925241
769 1373008708919830647785134941
770 1436170345009508389988759951
771 1502194898641027729524668233
772 1571210234269507398753584324
773 1643349843489871911516364356
774 1718753089062019312536241374
775 1797565459364503953938186209
776 1879938833715056453726493897
777 1966031759016164907614741445
778 2056009738201197523570142081
779 2150045530978046831728523432
780 2248319467386035112017748458
781 2351019774705047175996452333
782 2458342918276245934569096060
783 2570493956818817999008945240
784 2687686912849352470410699691
785 2810145158837562983137222423
786 2938101819756133692287029415
787 3071800192711753665235087371
788 3211494184370549549837897924
789 3357448766922761799054981139
790 3509940453359903098110428208
791 3669257792871813256940179035
792 3835701887201853533767632168
793 4009586928835402814323057663
794 4191240761930284589197655174
795 4381005466937636932645526355
796 4579237969898060980779770778
797 4786310677440967775509848820
798 5002612138554460253078727461
799 5228547734239628841428042836
800 5464540396205905522860293032
801 5711031355814396907640823166
802 5968480924522509331490346109
803 6237369307137487163344513754
804 6518197449236803116314425695
805 6811487920172002208144473393
806 7117785833127166770516482348
807 7437659803766535305895928113
808 7771702949064970955323402659
809 8120533927983418514154131647
810 8484798025715626390937396587
811 8865168283306335815463915868
812 9262346674510658945459655907
813 9677065331844213296491503357
814 10110087823848921264703454328
815 10562210485685620607531096378
816 11034263805246270620098266197
817 11527113867071675877610605435
818 12041663856449099170732782203
819 12578855626164721427502074755
820 13139671328481721477553083592
821 13725135115023375751048292659
822 14336314907344357199299126085
823 14974324241090719731172493855
824 15640324186761444101745299857
825 16335525350211097085311998699
826 17061189956154853662865724464
827 17818634018073919778318369718
828 18609229598051152826716973609
829 19434407160214378237527981945
830 20295658021607534852779123020
831 21194536904469260895368303380
832 22132664594052918923743543591
833 23111730706294247190027167036
834 24133496569799910908367380544
835 25199798226816130978686406581
836 26312549558017375155255082507
837 27473745536155799658702546851
838 28685465613807760679089816764
839 29949877250670385615426879735
840 31269239586072839212369587112
841 32645907262600817299709904717
842 34082334406961743347494641834
843 35581078774470626047295009733
844 37144806063784160231247715601
845 38776294408783185803169404989
846 40478439054771418520525921488
847 42254257226452526230377136528
848 44106893195437208801268382066
849 46039623555349428273412009758
850 48055862712914042650674796501
851 50159168603750746622639133698
852 52353248641937724765198627814
853 54641965912778209791663413783
854 57029345618569055348034209767
855 59519581787569486230501831206
856 62117044256763697688944174150
857 64826285939441589194376432897
858 67652050389049366141856380932
859 70599279671226388813712100194
860 73673122556406565430042887189
861 76878943045863927566169434876
862 80222329244581140379784826177
863 83709102594860606209902275095
864 87345327485137070666325365417
865 91137321249034201985036183763
866 95091664570290169138699182855
867 99215212309806791203957087651
868 103515104771706103115626798329
869 107998779425957301530902447041
870 112673983105816703853662864252
871 117548784699055906337671298137
872 122631588352687356470635672637
873 127931147211686702425401223594
874 133456577713003941593841839695
875 139217374457007612513870839480
876 145223425679362164018468576087
877 151485029347257756841763147802
878 158012909904835827708888739151
879 164818235693644961650612212853
880 171912637074959215547844113147
881 179308225281859939137285192380
882 187017612030059008164647631991
883 195053929917593997094749265685
884 203430853644688148965342215743
885 212162622086310805678828040336
886 221264061251228420422361142957
887 230750608162676251499069495799
888 240638335697134602266550406897
889 250943978419138133768091893288
890 261684959451507577913926187540
891 272879418421950611736163938180
892 284546240528554811541383921257
893 296705086768374511986558015804
894 309376425375013868969691827050
895 322581564512918171154955649793
896 336342686277919877253982065416
897 350682882055536521707010870994
898 365626189290496401690890654117
899 381197629723070389529792046361
900 397423249149922494863347290979
901 414330158769457668244986444416
902 431946578173947150991368593049
903 450301880053153536857900252597
904 469426636676659995627254290505
905 489352668224739472089312982700
906 510113093040276352970173379767
907 531742379877088493694806970866
908 554276402222883550948122145933
909 577752494778138636659504249017
910 602209512175303855881715680964
911 627687890026021847466455231667
912 654229708387409826650746439323
913 681878757741996759567727599556
914 710680607589524166701608462109
915 740682677752639211892081167304
916 771934312502406152582092525270
917 804486857613677336389596080104
918 838393740464565483173956020466
919 873710553298691549234747370021
920 910495139773409371495751092605
921 948807684921982488308542590705
922 988710808662566745566666833318
923 1030269662991994149485229568458
924 1073552033007609796380632620129
925 1118628441905951184454463208444
926 1165572260112722605156210956145
927 1214459818704480477630679433150
928 1265370527288546944355350625410
929 1318386996514090227654489577640
930 1373595165393883135216275691166
931 1431084433623165047707787953315
932 1490947799089112920141957881379
933 1553282000771870887918436481313
934 1618187667245714144563447352446
935 1685769470996937076380619213703
936 1756136288783269051036829671846
937 1829401368268248980171782826156
938 1905682501172835084179512327785
939 1985102203195813784575582740692
940 2067787900964096746973019651560
941 2153872126283992197403548316768
942 2243492717974792994344761156617
943 2336793031576784184314974061701
944 2433922157236815703746987875301
945 2535035146086166813557570656067
946 2640293245437317801072677033752
947 2749864143138707898400761088429
948 2863922221439357195124035589333
949 2982648820728642636868770999555
950 3106232513530295529841831985547
951 3234869389144120526847445358143
952 3368763349343765620298736274966
953 3508126415554402100635331243647
954 3653179047950134409182756833914
955 3804150476927668443239080412034
956 3961279047429944337811446901164
957 4124812576611415990655508536346
958 4295008725355144943440654174698
959 4472135384171215047780760260642
960 4656471074025865724323948617327
961 4848305362671544995224119691653
962 5047939297069486298992031100801
963 5255685852518790543220659218483
964 5471870399129022338716816839329
965 5696831186297398479869823174785
966 5930919845876420457106087143469
967 6174501914743689856870783087591
968 6427957377512296002129155732274
969 6691681230148005782964047292925
970 6966084065288153069457770463990
971 7251592680087064780156034440135
972 7548650707443695561523178565771
973 7857719271499338062963662660594
974 8179277668326439681098230200784
975 8513824072764174771842449399219
976 8861876272392087671627811464135
977 9223972429670343151000978802862
978 9600671873313475908775988202360
979 9992555920004548423492706575544
980 10400228727597869956199612674351
981 10824318181001451069075362067778
982 11265476811974714497429841814033
983 11724382754123231266941033692787
984 12201740734419930634500662647728
985 12698283102631945877798692951559
986 13214770900083517922784508585251
987 13751994969238814009806625593512
988 14310777105643623970034757242240
989 14891971253822328752670503547638
990 15496464748785771120090557751470
991 16125179604867382518445527291241
992 16779073853668590574599074891963
993 17459142932960864465005610097796
994 18166421128460188532920289057681
995 18901983070461035775011110839782
996 19666945287390460020055413016278
997 20462467818419519786376362242033
998 21289755887348285034209345006647
999 22150061640062976082656417501015
1000 23044685947948717589008022972098