0 1
1 1
2 2
3 3
4 5
5 7
6 10
7 15
8 21
9 29
10 40
11 54
12 72
13 96
14 127
15 166
16 216
17 279
18 358
19 457
20 580
21 735
22 924
23 1159
24 1446
25 1799
26 2228
27 2752
28 3388
29 4158
30 5087
31 6207
32 7551
33 9165
34 11093
35 13401
36 16144
37 19412
38 23286
39 27882
40 33310
41 39727
42 47289
43 56191
44 66647
45 78923
46 93299
47 110126
48 129779
49 152725
50 179449
51 210565
52 246722
53 288714
54 337396
55 393799
56 459050
57 534474
58 621540
59 721971
60 837666
61 970848
62 1123974
63 1299910
64 1501803
65 1733337
66 1998564
67 2302178
68 2649377
69 3046147
70 3499137
71 4015933
72 4605010
73 5276013
74 6039682
75 6908229
76 7895258
77 9016208
78 10288234
79 11730791
80 13365518
81 15216861
82 17312024
83 19681672
84 22359951
85 25385217
86 28800212
87 32652876
88 36996571
89 41891082
90 47402914
91 53606494
92 60584497
93 68429388
94 77243840
95 87142457
96 98252478
97 110715754
98 124689699
99 140349497
100 157889535
101 177525924
102 199498231
103 224072564
104 251543733
105 282238917
106 316520231
107 354789266
108 397490245
109 445115279
110 498208420
111 557371835
112 623270879
113 696641218
114 778295310
115 869130777
116 970138200
117 1082411226
118 1207155976
119 1345703109
120 1499519066
121 1670220679
122 1859588680
123 2069584901
124 2302368841
125 2560317965
126 2846047759
127 3162435581
128 3512645163
129 3900154797
130 4328786538
131 4802739890
132 5326626753
133 5905511440
134 6544952132
135 7251048820
136 8030492676
137 8890622625
138 9839484503
139 10885897961
140 12039527062
141 13310959069
142 14711788947
143 16254712409
144 17953626004
145 19823737526
146 21881684558
147 24145665079
148 26635577517
149 29373175615
150 32382233963
151 35688730429
152 39321042351
153 43310161495
154 47689925903
155 52497272702
156 57772512503
157 63559626809
158 69906591103
159 76865725390
160 84494074502
161 92853820548
162 102012729718
163 112044637959
164 123029975965
165 135056339055
166 148219104460
167 162622099856
168 178378328131
169 195610750585
170 214453137967
171 235050987970
172 257562521949
173 282159760081
174 309029688148
175 338375516009
176 370418041914
177 405397125528
178 443573282563
179 485229405606
180 530672628103
181 580236333632
182 634282332467
183 693203205433
184 757424844907
185 827409187947
186 903657177953
187 986711951346
188 1077162287843
189 1175646322579
190 1282855562073
191 1399539207159
192 1526508825292
193 1664643378416
194 1814894657300
195 1978293126296
196 2155954238994
197 2349085227452
198 2558992439170
199 2787089219478
200 3034904426342
201 3304091578667
202 3596438732503
203 3913879091184
204 4258502452750
205 4632567510091
206 5038515112889
207 5478982514419
208 5956818729456
209 6475101027014
210 7037152703883
211 7646562165227
212 8307203484382
213 9023258466244
214 9799240411841
215 10640019619787
216 11550850840949
217 12537402735816
218 13605789573488
219 14762605242777
220 16014959833521
221 17370518878527
222 18837545550352
223 20424945915510
224 22142317581452
225 24000001854902
226 26009139798905
227 28181732319311
228 30530704720827
229 33069975895252
230 35814532628668
231 38780509227623
232 41985273005278
233 45447515877918
234 49187352665136
235 53226426396028
236 57588021293849
237 62297183785816
238 67380852300204
239 72867996251780
240 78789765085799
241 85179647834947
242 92073644174000
243 99510447511940
244 107531641217242
245 116181908615027
246 125509257979550
247 135565263283004
248 146405322056667
249 158088931257424
250 170679982671537
251 184247078879393
252 198863871512320
253 214609422977906
254 231568593619518
255 249832455648397
256 269498736068404
257 290672290148929
258 313465607928019
259 337999355550478
260 364402954221819
261 392815198878257
262 423384919675731
263 456271688723119
264 491646575561022
265 529692954154607
266 570607365351024
267 614600437964908
268 661897872961844
269 712741494335449
270 767390371719864
271 826122018865656
272 889233673633335
273 957043664238656
274 1029892868097357
275 1108146268707317
276 1192194617676151
277 1282456208115060
278 1379378767411246
279 1483441476449285
280 1595157124313147
281 1715074406507560
282 1843780376895008
283 1981903062460106
284 2130114252390518
285 2289132471856015
286 2459726153386792
287 2642717017669394
288 2838983678256511
289 3049465483653085
290 3275166613041731
291 3517160440947578
292 3776594189154635
293 4054693883200023
294 4352769634064155
295 4672221264676142
296 5014544304467684
297 5381336374151525
298 5774303986873400
299 6195269790867976
300 6646180282988054
301 7129114021569989
302 7646290371629608
303 8200078814630940
304 8793008859859450
305 9427780593871518
306 10107275909667375
307 10834570456755032
308 11612946358936577
309 12445905746277749
310 13337185153940221
311 14290770840249823
312 15310915083213415
313 16402153514599160
314 17569323558048690
315 18817584037914333
316 20152436033438210
317 21579745053515683
318 23105764615751040
319 24737161314612767
320 26481041472696552
321 28344979470558583
322 30337047860674399
323 32465849372953524
324 34740550930344907
325 37170919795338316
326 39767361980397294
327 42540963058250747
328 45503531521224928
329 48667644842500109
330 52046698406567776
331 55654957480819479
332 59507612415740663
333 63620837266938131
334 68011852049218679
335 72698988839691060
336 77701761965563890
337 83040942520214741
338 88738637471728658
339 94818373637190783
340 101305186818786569
341 108225716408399655
342 115608305792255633
343 123483108899676790
344 131882203267192616
345 140839710003931182
346 150391921073823996
347 160577434327292803
348 171437296747618311
349 183015156396768100
350 195357423581371452
351 208513441781865993
352 222535668927539913
353 237479869625481961
354 253405318995364014
355 270375018790851415
356 288455926536657921
357 307719198443315430
358 328240446914733769
359 350100013501416666
360 373383258210334806
361 398180866125577146
362 424589172358017077
363 452710506390902236
364 482653556959208418
365 514533758655497948
366 548473701533565266
367 584603565042812532
368 623061577713309663
369 663994504081054377
370 707558160438871446
371 753917961076983721
372 803249496783114942
373 855739147460719972
374 911584730840514348
375 970996189360552219
376 1034196317418985212
377 1101421531315825749
378 1172922684342796219
379 1248965929606055943
380 1329833633324812517
381 1415825341489340201
382 1507258802937308776
383 1604471052064758720
384 1707819554581876076
385 1817683419900249530
386 1934464683952557934
387 2058589666443490198
388 2190510406767344642
389 2330706183049363380
390 2479685119029789331
391 2637985883756964870
392 2806179489346057459
393 2984871192335937884
394 3174702504498479467
395 3376353319261944724
396 3590544160266789473
397 3818038558915104490
398 4059645568169491875
399 4316222420239802243
400 4588677336232765905
401 4877972496266384632
402 5185127179033731358
403 5511221080276728174
404 5857397820165016854
405 6224868650104548272
406 6614916370092746164
407 7028899468326061790
408 7468256495421954230
409 7934510686271775892
410 8429274843268139671
411 8954256495378061325
412 9511263348337750939
413 10102209042054260154
414 10729119232189536045
415 11394138013802294323
416 12099534705907902726
417 12847711016816640491
418 13641208611200727143
419 14482717100950648038
420 15375082483088242574
421 16321316049235904916
422 17324603792477607683
423 18388316338813541453
424 19516019431889713652
425 20711485001199291113
426 21978702845589082492
427 23321892965585743330
428 24745518579866565655
429 26254299863064349412
430 27853228444097463861
431 29547582706283742192
432 31342943932710892482
433 33245213342626542584
434 35260630067060378611
435 37395790114427639256
436 39657666379572692253
437 42053629752519775922
438 44591471386194819541
439 47279426185491705396
440 50126197583368964322
441 53140983673105579552
442 56333504769505907055
443 59714032475654568387
444 63293420335867716663
445 67083136159704484088
446 71095296106373262375
447 75342700623531898541
448 79838872339421846437
449 84598096012434140121
450 89635460647664922496
451 94966903895719652238
452 100609258855057555132
453 106580303405470324070
454 112898812206951092905
455 119584611505175950676
456 126658636892176653234
457 134142994178481717972
458 142061023541124141831
459 150437367120420028699
460 159298040247388049907
461 168670506493073712968
462 178583756740939935637
463 189068392493858283140
464 200156713638160045083
465 211882810898656779562
466 224282663230596845988
467 237394240407163937599
468 251257611074425299980
469 265915056559587747104
470 281411190733092470703
471 297793086240474250674
472 315110407436092572784
473 333415550367827323618
474 352763790179677215006
475 373213436317932793482
476 394825995946274175372
477 417666345995802332966
478 441802914297708915754
479 467307870269065744343
480 494257325646132387187
481 522731545784688840606
482 552815172073258742609
483 584597456032764946894
484 618172505705203712402
485 653639544964425475446
486 691103186414107978438
487 730673718571617161384
488 772467408071699971588
489 816606817660977519647
490 863221140793032440782
491 912446553674663459659
492 964426585656638856920
493 1019312508907186284465
494 1077263748353539494233
495 1138448312926307225445
496 1203043249193262368705
497 1271235118523584585284
498 1343220498980642755721
499 1419206513201323207927
500 1499411383582697611466
501 1584065016162770361978
502 1673409614651137077489
503 1767700326137947978215
504 1867205920085588716706
505 1972209502287320850982
506 2083009265560751945163
507 2199919279031814351699
508 2323270317956916140675
509 2453410736127502187064
510 2590707383002419058134
511 2735546567819677736543
512 2888335073050432974864
513 3049501219674765870374
514 3219495986881131806229
515 3398794188919702686997
516 3587895711974240618598
517 3787326814058230796288
518 3997641491088726199201
519 4219422912446408902671
520 4453284929492709796191
521 4699873660685195576461
522 4959869157110799753753
523 5233987152443645280547
524 5522980901530152977394
525 5827643112009733635362
526 6148807973594587866201
527 6487353289857956267815
528 6844202717616527858815
529 7220328119240698656856
530 7616752033485920090998
531 8034550270710654751157
532 8474854638631422193907
533 8938855805064325650925
534 9427806304415277143750
535 9943023695009230638029
536 10485893874692095319785
537 11057874562499079864445
538 11660498954560035405334
539 12295379562807494796535
540 12964212245466577596014
541 13668780438739461332315
542 14410959599550743876634
543 15192721869695618117962
544 16016140972230391472173
545 16883397351466543130413
546 17796783568475301745296
547 18758709964581831584391
548 19771710605926664210196
549 20838449522799349045410
550 21961727258105612166247
551 23144487740017122400871
552 24389825494572511796178
553 25700993214752308835438
554 27081409703339205382903
555 28534668207701549026716
556 30064545165502463689099
557 31675009381242769560030
558 33370231654493284512249
559 35154594881664616219794
560 37032704654200676318678
561 39009400377169595885931
562 41089766933363084914880
563 43279146919206558394517
564 45583153480028273801070
565 48007683773540582517450
566 50558933091751043624693
567 53243409672950224630468
568 56067950236917495455445
569 59039736278051032516140
570 62166311152764695279356
571 65455597999207864800113
572 68915918529155998265904
573 72556012733795429842449
574 76385059547087298338615
575 80412698512448719295065
576 84649052500636142038878
577 89104751528963017585194
578 93790957734333427773889
579 98719391555032467823013
580 103902359178785187499317
581 109352781317286640868047
582 115084223370218608511353
583 121110927044712334750737
584 127447843499294009289660
585 134110668084569913658658
586 141115876756274334125171
587 148480764239825430984259
588 156223484029215862933122
589 164363090306916761126068
590 172919581875499724795676
591 181913948195893333959577
592 191368217631592887776624
593 201305508002747007994155
594 211750079558857605908004
595 222727390483863810129623
596 234264155052641597338059
597 246388404563453440781971
598 259129551176632743864920
599 272518454795801714716022
600 286587493134205830239453
601 301370635115319916114416
602 316903517763748146786119
603 333223526749621017712763
604 350369880757195515845695
605 368383719856209764397087
606 387308198062740354520590
607 407188580284880343785817
608 428072343857509621715098
609 450009284879789636294308
610 473051629578793649407926
611 497254150932906185072734
612 522674290799304746220143
613 549372287800999636485670
614 577411311240568842944632
615 606857601319912947453557
616 637780615958086571104460
617 670253184512568680921841
618 704351668723232623472047
619 740156131212801153123156
620 777750511892742403102626
621 817222812639415453199395
622 858665290621831406133997
623 902174660679696321839855
624 947852307168470774397711
625 995804505707058941967112
626 1046142655283455283740885
627 1098983521194274159689661
628 1154449489315597180885929
629 1212668832225043423125553
630 1273775987718431907832141
631 1337911850288916602869585
632 1405224076162067972217096
633 1475867402507108623455793
634 1550003981472423891648318
635 1627803729722622583160921
636 1709444694184862552258037
637 1795113434743946594374317
638 1885005424658884530288288
639 1979325469508279017006779
640 2078288145508078386237139
641 2182118258083027242840474
642 2291051321612592524700899
643 2405334061313333070472160
644 2525224938262677931896071
645 2650994698613973270573626
646 2782926948099519283627226
647 2921318752967245034976533
648 3066481268547736623479221
649 3218740396701648481959274
650 3378437473453172287359614
651 3545929988173327276809972
652 3721592335737461019920832
653 3905816603144634544751069
654 4099013392152609931436622
655 4301612679551095880087431
656 4514064716767846327204694
657 4736840970577293632116038
658 4970435106759750341528363
659 5215364018640988491386778
660 5472168902527333056576264
661 5741416382140455591982003
662 6023699684248967652983271
663 6319639867790874024714511
664 6629887108882108507099341
665 6955122044211937750424724
666 7296057175436150901428226
667 7653438337293868579096039
668 8028046232293688745411807
669 8420698034939970953516707
670 8832249068600545678951593
671 9263594558253272496554745
672 9715671462490879426335474
673 10189460388311666775699597
674 10685987592378191758732926
675 11206327072587258071718323
676 11751602753962678554518138
677 12322990773057675942951775
678 12921721865236720958397968
679 13549083859397421466728788
680 14206424284892080847241569
681 14895153095616109092996581
682 15616745516446933555134959
683 16372745017442819240583493
684 17164766421446437919136239
685 17994499150983555504650528
686 18863710620603237410897995
687 19774249781072971869004956
688 20728050822120515903251820
689 21727137040704586202245597
690 22773624882099220128854171
691 23869728161392270532198022
692 25017762473327585847161646
693 26220149798763559285065143
694 27479423316378466451512187
695 28798232428625993446017208
696 30179348011333194579052509
697 31625667896738507211734829
698 33140222600190050606126749
699 34726181301165000119218411
700 36386858089730074491167166
701 38125718490041918082026753
702 39946386272985180629565605
703 41852650570566276803112096
704 43848473305222992735372423
705 45937996947775251306240521
706 48125552618331371185613861
707 50415668545078089236845690
708 52813078896522459454798209
709 55322733003420611546126916
710 57949804987323331328087690
711 60699703813392722363121119
712 63578083785898998683804446
713 66590855505593050055287713
714 69744197308970089168194559
715 73044567210293849229823214
716 76498715368140834342782834
717 80113697099151564049570589
718 83896886462642098791234675
719 87855990440736039842637489
720 91999063739726293948574458
721 96334524239468969731968047
722 100871169118750595779910179
723 105618191685756355772366616
724 110585198944003138552806031
725 115782229925388995555444142
726 121219774823352159835719483
727 126908794960530375857544867
728 132860743626767166920191526
729 139087587824828277912490674
730 145601830962771313470687965
731 152416536533557195187205378
732 159545352824206129106850876
733 167002538698586171423684446
734 174802990499782069657142526
735 182962270119928936928039866
736 191496634287412590449542909
737 200423065123439402373718932
738 209759302022166631805182459
739 219523874910863054025529663
740 229736138948942915826716479
741 240416310727187741441318398
742 251585506031044232942961318
743 263265779234566686923707506
744 275480164394363253367043509
745 288252718115811570763490397
746 301608564266835444466965408
747 315573940617685241557708788
748 330176247488445557313267721
749 345444098489409815100360004
750 361407373443018207364666069
751 378097273579758552730683328
752 395546379104285092495415444
753 413788709232024229165205711
754 432859784800715060705033568
755 452796693565683041926043050
756 473638158292174069775296235
757 495424607762791042302780176
758 518198250822982904800703677
759 542003153592645259554986081
760 566885319977209808354722566
761 592892775617135743275653251
762 620075655420478387665720388
763 648486294829208126145582996
764 678179324976195344242753884
765 709211771896274676705270511
766 741643159961564497635451759
767 775535619718256027459899845
768 810954000309411666161142674
769 847965986675935804856273764
770 886642221735815295613866185
771 927056433749983519901339093
772 969285569091754429478192030
773 1013409930645714593050803527
774 1059513322071266048021618894
775 1107683198175695267654399976
776 1158010821651718812838306583
777 1210591426444940054620481293
778 1265524388027559942923633099
779 1322913400866035233172519165
780 1382866663382187387217436515
781 1445497070719552977414456406
782 1510922415639550775036834791
783 1579265597885341707639981674
784 1650654842365095979637857060
785 1725223926520778364934544582
786 1803112417263540098535257228
787 1884465917872387126735980290
788 1969436325269003594767203670
789 2058182098098471414821309033
790 2150868536063167350987736777
791 2247668070975365331888174257
792 2348760570013051504476064480
793 2454333651683202074216433033
794 2564583015017309310512014887
795 2679712782545300750860994676
796 2799935857616213085595082101
797 2925474296657089465684569605
798 3056559696985602110884966684
799 3193433600816897817599273203
800 3336347916131160129320972027
801 3485565355095418155722273942
802 3641359890761249174581914393
803 3804017232789262974246453877
804 3973835322981664504442700395
805 4151124851435813927837857776
806 4336209794164587214176651493
807 4529427973063535761757763060
808 4731131639140401549888472439
809 4941688079959518714082064508
810 5161480252292078641731048637
811 5390907441003211632390400475
812 5630385945248403685962598656
813 5880349793094984553999388017
814 6141251485729357371232188133
815 6413562772457358367363522068
816 6697775457753706992666570795
817 6994402241667004958082271494
818 7303977594939242327705269626
819 7627058670253348294876313116
820 7964226251079064670656253155
821 8316085739646405945939306177
822 8683268185637288473285085989
823 9066431357249654002532539376
824 9466260856354673774947985240
825 9883471279536496915551632530
826 10318807426875602635482208235
827 10773045560411235727566682172
828 11246994714295758646335965262
829 11741498058734155342428935253
830 12257434319885490187512996632
831 12795719257989982922571598500
832 13357307206075635045720144734
833 13943192671692167164488406622
834 14554412004217537977291417350
835 15192045130383656792002865076
836 15857217360773220955771792529
837 16551101270149061459251873149
838 17274918654591123946791449473
839 18029942568534414591495867000
840 18817499444924072860257472313
841 19638971301831375175524013756
842 20495798039007110333129704003
843 21389479827986592219594892247
844 22321579599503787743285264625
845 23293725632120845858122451357
846 24307614246133932471680176806
847 25365012606976929886872752001
848 26467761642511480267011784272
849 27617779078765281750255747528
850 28817062598860733266721431829
851 30067693130063229780154878175
852 31371838264072902906772222587
853 32731755815885662663372388528
854 34149797526759314584579236873
855 35628412917038604213241308972
856 37170153294819590509559586949
857 38777675926669095853183180896
858 40453748376859459612419195421
859 42201253021832784520697124156
860 44023191746872672827082273833
861 45922690832235479052059279109
862 47903006036277748551363406406
863 49967527883412171566340209653
864 52119787165031481375118185728
865 54363460661858699261956064194
866 56702377096513430905033740530
867 59140523325428018614763028454
868 61682050779604738945730034380
869 64331282164076411714030085222
870 67092718426318279007709233262
871 69971046004259366245393405892
872 72971144364957316483214424747
873 76098093845432480481771461605
874 79357183807605456450501679479
875 82753921119747936138354775127
876 86294038977340282375347852128
877 89983506076731416673789941589
878 93828536155518038311618732238
879 97835597914101659580277698141
880 102011425333444183480754162374
881 106363028404626556869274325849
882 110897704286421219469001783878
883 115623048907718483864221156613
884 120546969032300501172712039468
885 125677694804135002435444581227
886 131023792792065501126345246749
887 136594179553506077566673619640
888 142398135737508257336290010450
889 148445320748355897292717614105
890 154745787991662497456283575485
891 161310000725795098921530947122
892 168148848542331082793898915802
893 175273664500169972856765004462
894 182696242938873029873248359222
895 190428857997790320254904074283
896 198484282868559406491464224870
897 206875809809623252443662588341
898 215617270952518826263033718157
899 224723059930833734983908389502
900 234208154363917610990116458520
901 244088139228669523631719281189
902 254379231154004101064582533149
903 265098303673929072825313525708
904 276262913476547401904255315102
905 287891327687729953060297900149
906 300002552229691697813188996897
907 312616361296247814668860481116
908 325753327988127808618016639750
909 339434856153388127818461548012
910 353683213479688958411550132597
911 368521565886991275232277790696
912 383974013271088247065458191565
913 400065626650313260355604561550
914 416822486769767747277114309912
915 434271724219488391755008860037
916 452441561125127948290580861630
917 471361354471959754827244273676
918 491061641125336070227023712483
919 511574184613137748294368557141
920 532932023738250716939000756141
921 555169523091696625663688238537
922 578322425539734342379393528657
923 602427906761039335007456330938
924 627524631912963109550210638924
925 653652814508878676927507767944
926 680854277591734509956760121734
927 709172517292172801022750238362
928 738652768862922363747560073375
929 769342075284656720167667654454
930 801289358542118423470531483797
931 834545493673056300045061871320
932 869163385696408043347025116079
933 905198049530191628052782070169
934 942706693013750696300581827829
935 981748803153336954218462924808
936 1022386235714512463874362085758
937 1064683308289522490568881302482
938 1108706896972631451876903168783
939 1154526536781436922009809081911
940 1202214525967386214304721119701
941 1251846034364123678843306789461
942 1303499215927901643678152399289
943 1357255325630101288274950378089
944 1413198840867939325601038131538
945 1471417587565690121725343245239
946 1532002871145239022963866117821
947 1595049612551509712695639620074
948 1660656489525285213318324897164
949 1728926083323177833440751921299
950 1799965031092007416940816949235
951 1873884184112629502451363479256
952 1950798772136325627324868690029
953 2030828574045237555038108541963
954 2114098095077006595639262505903
955 2200736750862779745851338399066
956 2290879058537077827545949416226
957 2384664835187699302055385485378
958 2482239403923869572453991365331
959 2583753807851252399178358600616
960 2689365032253231058244219471133
961 2799236235289056064093587182599
962 2913536987531058162393893796762
963 3032443520675154894792828840297
964 3156138985771351910378536412305
965 3284813721333872468921942133287
966 3418665531703956949197541455165
967 3557899976052275941209143130957
968 3702730668422313583986271418907
969 3853379589231020772994274107333
970 4010077408658529930687568533072
971 4173063822374784126321581232290
972 4342587900067584076094487748581
973 4518908447253818319187107486632
974 4702294380873536781089737513564
975 4893025119185078925433493520870
976 5091390986498698501643900531548
977 5297693633306062108037656735622
978 5512246472383663876861265024388
979 5735375131469619926045692270424
980 5967417923135511130429440758698
981 6208726332497959534716409291956
982 6459665523438481662306715190008
983 6720614864024891412396530936742
984 6991968471853157607686900652741
985 7274135780055189099779651965298
986 7567542124745557360632034125425
987 7872629354708707585744550773676
988 8189856464157790649004589661066
989 8519700249426907204458646073045
990 8862655990490330581042253308284
991 9219238158235206991547116373565
992 9589981148448361530992604755795
993 9975440043513209499028180669812
994 10376191402849429299615455445035
995 10792834083166041680298691369399
996 11225990089637908139553701338333
997 11676305459156458410641584648403
998 12144451176847734232523639318206
999 12631124127094647161259635251727
1000 13137048080345746853818834160385