1 1
2 1
3 2
4 4
5 5
6 8
7 11
8 16
9 23
10 32
11 43
12 59
13 78
14 104
15 137
16 181
17 233
18 303
19 388
20 497
21 630
22 799
23 1003
24 1262
25 1574
26 1961
27 2430
28 3008
29 3701
30 4551
31 5569
32 6805
33 8284
34 10070
35 12195
36 14753
37 17786
38 21413
39 25709
40 30824
41 36856
42 44014
43 52435
44 62384
45 74062
46 87811
47 103901
48 122792
49 144846
50 170649
51 200712
52 235788
53 276548
54 323989
55 379000
56 442855
57 516752
58 602328
59 701150
60 815346
61 946960
62 1098708
63 1273291
64 1474179
65 1704854
66 1969787
67 2273480
68 2621611
69 3020019
70 3475919
71 3996791
72 4591839
73 5270625
74 6044789
75 6926584
76 7930717
77 9072745
78 10371285
79 11846070
80 13520510
81 15419632
82 17572848
83 20011717
84 22773205
85 25897018
86 29429408
87 33420329
88 37927566
89 43013669
90 48750809
91 55217185
92 62502619
93 70704767
94 79935266
95 90315664
96 101984593
97 115093066
98 129812767
99 146331123
100 164860426
101 185632634
102 208910002
103 234979154
104 264163310
105 296816174
106 333335540
107 374156925
108 419769340
109 470708190
110 527573441
111 591022477
112 661790370
113 740682679
114 828598954
115 926524915
116 1035559490
117 1156907297
118 1291909058
119 1442034430
120 1608917173
121 1794347814
122 2000314160
123 2228994997
124 2482805826
125 2764393815
126 3076690778
127 3422908861
128 3806601577
129 4231661949
130 4702391828
131 5223502989
132 5800197323
133 6438170594
134 7143705009
135 7923677976
136 8785667649
137 9737967723
138 10789709698
139 11950883811
140 13232480231
141 14646519590
142 16206214654
143 17926012276
144 19821780683
145 21910863787
146 24212297885
147 26746883294
148 29537433183
149 32608865890
150 35988493450
151 39706136942
152 43794460476
153 48289117027
154 53229133076
155 58657090541
156 64619572891
157 71167388039
158 78356085310
159 86246230446
160 94904002024
161 104401528129
162 114817578384
163 126237971154
164 138756375714
165 152474806991
166 167504552575
167 183966770506
168 201993564841
169 221728702158
170 243328858744
171 266964481733
172 292821231491
173 321101012591
174 352023647312
175 385828102672
176 422774430749
177 463145231551
178 507247898383
179 555416356765
180 608013668440
181 665434089671
182 728106089757
183 796494789508
184 871105454492
185 952486377443
186 1041232927685
187 1137990947115
188 1243461441713
189 1358404584544
190 1483645144317
191 1620077195317
192 1768670405591
193 1930475564672
194 2106631864281
195 2298373386590
196 2507037524781
197 2734072587516
198 2981047545252
199 3249660924906
200 3541752085050
201 3859311619051
202 4204494387279
203 4579631669129
204 4987246232588
205 5430066505959
206 5911043995691
207 6433369809773
208 7000494773240
209 7616148672908
210 8284363494162
211 9009495804666
212 9796253584287
213 10649722251752
214 11575395621716
215 12579206138570
216 13667560597810
217 14847375226838
218 16126116885769
219 17511843757073
220 19013252835344
221 20639727083306
222 22401390168251
223 24309161057677
224 26374817079912
225 28611057107427
226 31031574165232
227 33651128497460
228 36485631156897
229 39552228427740
230 42869398015419
231 46457046548519
232 50336620206985
233 54531217252375
234 59065715235986
235 63966900773445
236 69263615754012
237 74986906936418
238 81170193911268
239 87849441436479
240 95063352339356
241 102853565910699
242 111264879355988
243 120345476086889
244 130147179821677
245 140725717125736
246 152141008891010
247 164457472072318
248 177744353903495
249 192076078528457
250 207532630041480
251 224199950474206
252 242170378653931
253 261543106889110
254 282424683573140
255 304929536996730
256 329180550697462
257 355309663955739
258 383458530202117
259 413779205049763
260 446434899443750
261 481600767652883
262 519464768422320
263 560228567005313
264 604108519470504
265 651336704753998
266 702162049287757
267 756851507316949
268 815691345315522
269 878988491241147
270 947072000932540
271 1020294599743737
272 1099034356053960
273 1183696441988192
274 1274715042520212
275 1372555365520625
276 1477715818857585
277 1590730304037982
278 1712170697980536
279 1842649469213032
280 1982822505842873
281 2133392098401956
282 2295110161183335
283 2468781631647611
284 2655268138470311
285 2855491874171483
286 3070439770228215
287 3301167906998749
288 3548806264343737
289 3814563741315204
290 4099733559641368
291 4405698975319926
292 4733939422405307
293 5086037009316861
294 5463683501951470
295 5868687709587338
296 6302983419145976
297 6768637789401905
298 7267860362691345
299 7803012601450440
300 8376618120205469
301 8991373515758832
302 9650159980639324
303 10356055597984083
304 11112348518323333
305 11922550912113451
306 12790413915301332
307 13719943457168622
308 14715417206309813
309 15781402519534188
310 16922775649413767
311 18144742091229763
312 19452858346746795
313 20853054981379932
314 22351661276149174
315 23955431347125620
316 25671572059495483
317 27507772605770523
318 29472236103409863
319 31573713078256154
320 33821537220111035
321 36225663274364451
322 38796707489456827
323 41545990482662374
324 44485582980597940
325 47628354295912057
326 50988024036980168
327 54579216912111596
328 58417521168771249
329 62519550531004557
330 66903010223431925
331 71586766947593733
332 76590923451839704
333 81936897564906296
334 87647506391620928
335 93747055547675438
336 100261434194711446
337 107218215761168085
338 114646765179458294
339 122578352536181342
340 131046274041263564
341 140085980227607864
342 149735212369863896
343 160034147051646886
344 171025549961147086
345 182754938866389443
346 195270756949566090
347 208624556478902171
348 222871194106837255
349 238069037804781658
350 254280186843995410
351 271570704870862666
352 290010867617950127
353 309675425344775563
354 330643881694738146
355 353000789114840615
356 376836062684897500
357 402245312564682842
358 429330197080996773
359 458198796735875560
360 488966011350956439
361 521753980712573852
362 556692531145877721
363 593919648479090244
364 633581980059913002
365 675835366397349676
366 720845405348532490
367 768788049551503129
368 819850240308209297
369 874230578765273809
370 932140037909229226
371 993802716392458892
372 1059456638051091291
373 1129354598322308250
374 1203765061803193117
375 1282973112376675239
376 1367281460565281870
377 1457011509787439478
378 1552504486638913181
379 1654122637155580906
380 1762250494690802554
381 1877296221682997212
382 1999693031508536071
383 2129900693058500076
384 2268407124854667784
385 2415730081752045778
386 2572418941729181195
387 2739056596275572108
388 2916261452632738935
389 3104689551920969930
390 3305036812242453444
391 3518041401380045327
392 3744486249104867627
393 3985201704373557573
394 4241068348445019398
395 4513019969943310109
396 4802046714019598062
397 5109198412475989119
398 5435588108246221185
399 5782395782035431866
400 6150872295883691756
401 6542343562511474467
402 6958214956725120525
403 7399975978922166894
404 7869205188648282086
405 8367575419570246681
406 8896859295663226359
407 9458935061461987092
408 10055792748214749568
409 10689540690448737117
410 11362412417042577003
411 12076773933170906666
412 12835131419706648903
413 13640139368523385681
414 14494609183035274658
415 15401518264734246772
416 16364019618104953843
417 17385451997265004349
418 18469350630070070893
419 19619458545921671738
420 20839738546729227326
421 22134385850484589894
422 23507841451004628720
423 24964806226890836715
424 26510255847792395689
425 28149456515025744225
426 29887981589643538077
427 31731729149462157681
428 33686940533674753158
429 35760219921520853662
430 37958555009749476768
431 40289338840871883176
432 42760392853691335554
433 45379991214248251365
434 48156886506128333831
435 51100336845103015046
436 54220134505286021079
437 57526636129372135069
438 61030794619239936452
439 64744192787921350607
440 68679078879271895231
441 72848404045716795204
442 77265861901503450229
443 81945930252246471420
444 86903915130450751686
445 92155997249350334620
446 97719281018284975290
447 103611846244771561247
448 109852802681432997465
449 116462347557167037659
450 123461826267213881595
451 130873796377274922214
452 138722095134557117145
453 147031910658379735111
454 155829857023319305070
455 165144053426912730161
456 175004207677082339364
457 185441704212773206162
458 196489696917459214579
459 208183206962791962481
460 220559225969070791635
461 233656824746151450085
462 247517267931289301408
463 262184134816692104656
464 277703446716181995366
465 294123801196014642660
466 311496513555546718893
467 329875765918516301415
468 349318764360660703948
469 369885904473939632625
470 391640945837249167757
471 414651195837585111807
472 438987703360234584830
473 464725462840269776263
474 491943629247618154928
475 520725744551383603958
476 551159976294902671057
477 583339368886228902840
478 617362108300795307473
479 653331800866166051282
480 691357766897571941023
481 731555349926175508113
482 774046242368063283926
483 818958828455469583119
484 866428545365613933556
485 916598263456511800719
486 969618686641431630948
487 1025648773908334186486
488 1084856183122065713935
489 1147417738222676437833
490 1213519921074505189681
491 1283359389197522078791
492 1357143520764301815329
493 1435090988224423787065
494 1517432362081459297609
495 1604410746328072880798
496 1696282447220522603422
497 1793317677056603336881
498 1895801294810222780533
499 2004033585461419238975
500 2118331080064274974205
501 2239027418584192096667
502 2366474257755307782689
503 2501042226201866266243
504 2643121929303613571644
505 2793125006283016377037
506 2951485242246712495165
507 3118659737916786040249
508 3295130140061920868285
509 3481403935648004153802
510 3678015813023701422470
511 3885529093473312924338
512 4104537236788475619755
513 4335665424535388936323
514 4579572225038726014201
515 4836951344138048616275
516 5108533466144357882995
517 5395088189469914031114
518 5697426061805930981387
519 6016400719780554911391
520 6352911138463144914207
521 6707903996152644740329
522 7082376160356284716596
523 7477377300952381662316
524 7894012637037286547240
525 8333445824061812817696
526 8796901988409785043170
527 9285670916696648883913
528 9801110407657900695957
529 10344649794644856702449
530 10917793647385456483703
531 11522125661840732073995
532 12159312747680225945928
533 12831109323100811537406
534 13539361827462995642001
535 14286013462451495221133
536 15073109173278435008080
537 15902800881715436980453
538 16777352983619673848416
539 17699148123926207398836
540 18670693263030786215312
541 19694626048838308452132
542 20773721509783448382529
543 21910899084529690557428
544 23109230005170620368645
545 24371945051211283895933
546 25702442692818846167622
547 27104297642345937464600
548 28581269834443545079150
549 30137313855661263861974
550 31776588845857121500974
551 33503468894394286045687
552 35322553955646993295492
553 37238681309075238816435
554 39256937590804074495372
555 41382671424471466903196
556 43621506680927721554682
557 45979356397298258335036
558 48462437387895852645626
559 51077285580508514555605
560 53830772113732528945162
561 56730120232183193334468
562 59782923018743017194510
563 62997162004306036147438
564 66381226698004201355057
565 69943935082350636971059
566 73694555120479694295127
567 77642827324277967531429
568 81798988435182613698099
569 86173796271220025357198
570 90778555797098077129898
571 95625146476162932221789
572 100726050966552495804357
573 106094385226097834430665
574 111743930094350757204635
575 117689164422578938537595
576 123945299826729708198429
577 130528317141095268836142
578 137455004654934349037935
579 144742998217332252421259
580 152410823300498143741981
581 160477939115050237532589
582 168964784876186095120155
583 177892828323344138411332
584 187284616601776974755721
585 197163829618558395775504
586 207555335991869882170254
587 218485251716944842237699
588 229981001678927538204936
589 242071384147909419263256
590 254786638398888519055465
591 268158515604922954746403
592 282220353159890398609781
593 297007152593361120990731
594 312555661248949430505934
595 328904457904229702278208
596 346094042519940671755451
597 364166930313609156413373
598 383167750363211464510573
599 403143348954650633797601
600 424142897898239906093603
601 446218008048367350213452
602 469422848272936421659876
603 493814270129065330337539
604 519451938515045128053558
605 546398468579434521334098
606 574719569182881162123418
607 604484193220221448029867
608 635764695126423705686052
609 668636995903088978228044
610 703180756019653152485608
611 739479556557883108244885
612 777621088987231621072130
613 817697353974486883576743
614 859804869651804308236146
615 904044889784635436875352
616 950523632303549415735682
617 999352518683071961308878
618 1050648424675138523508512
619 1104533942925749438504194
620 1161137658030054671655039
621 1220594434604122300598050
622 1283045718980644917591288
623 1348639855161089997973111
624 1417532415688369725087479
625 1489886548131789680581384
626 1565873337910402543000181
627 1645672188211234372903853
628 1729471217796262698692622
629 1817467677525270634236757
630 1909868386462427240583710
631 2006890188470860817261873
632 2108760430243825530981115
633 2215717461760941722000087
634 2328011160206250486742779
635 2445903478428485009284706
636 2569669019076494724542127
637 2699595635590548833616839
638 2835985061287430160770498
639 2979153567829527006003135
640 3129432654430376136418868
641 3287169769206324625314766
642 3452729064151730853438866
643 3626492185277705380610239
644 3808859099528137520434646
645 4000248960155187493029890
646 4201101012316689011313369
647 4411875540732726312852060
648 4633054861326007875081080
649 4865144358852441429752483
650 5108673572623390059927401
651 5364197332510464085530960
652 5632296947527173047742724
653 5913581449379414854398205
654 6208688893489379653765308
655 6518287720104121797965799
656 6843078178222585477847652
657 7183793815191379345001371
658 7541203034952929133487017
659 7916110728056863554214315
660 8309359976690569122918727
661 8721833838123751862880321
662 9154457210119698372460935
663 9608198782017550697357872
664 10084073075361653904003121
665 10583142578119512276212095
666 11106519976716736635466263
667 11655370490297931370221467
668 12230914311825735747748496
669 12834429160827230927903077
670 13467252952818039698472899
671 14130786590649332597618781
672 14826496883263472743732545
673 15555919597578393390821113
674 16320662649482411504124876
675 17122409440176740393627517
676 17962922344387496205908641
677 18844046357247623777675012
678 19767712906958610781435864
679 20735943840645595089293946
680 21750855591155985639762367
681 22814663532882768681748036
682 23929686535059603056736448
683 25098351721335577049891092
684 26323199444835392705271121
685 27606888488303837565030969
686 28952201499366021961528942
687 30362050671363111758730205
688 31839483680693627643981676
689 33387689892056868158619686
690 35010006843506331851800791
691 36709927023729074173084515
692 38491104954522761631891615
693 40357364591995446345825492
694 42312707060617250958122758
695 44361318734855552168431209
696 46507579683781914811459703
697 48756072494694837258181103
698 51111591492516039855030917
699 53579152372431885311489797
700 56164002264027089935452674
701 58871630245934824055758394
702 61707778330870075186386511
703 64678452941758630549710039
704 67789936900589771821845004
705 71048801952540727472095716
706 74461921848915866365652545
707 78036486013444468021840865
708 81780013817561813154172661
709 85700369491387062853017349
710 89805777698285612230698586
711 94104839802087766565732750
712 98606550857311070765999099
713 103320317354021427742856473
714 108255975750353514843509470
715 113423811827111351594895999
716 118834580900374487407453789
717 124499528929557808672295129
718 130430414560006956423050115
719 136639532140866524184725041
720 143139735760732557923447982
721 149944464345400045799991207
722 157067767863942703239662407
723 164524334691317804563019045
724 172329520177780594976286268
725 180499376477517867579333290
726 189050683691181214393597240
727 198000982379309556810079636
728 207368607506095771525026003
729 217172723875461019233541713
730 227433363124076285667525387
731 238171462338696089203553591
732 249408904368073674673475161
733 261168559902687483952367310
734 273474331398660773053727350
735 286351198925471647813202657
736 299825268020471431303398535
737 313923819636721174007632993
738 328675362274367899094286411
739 344109686389573924569479792
740 360257921179039976773797401
741 377152593842279707257590165
742 394827691428172662772570829
743 413318725376792200768813747
744 432662798872245008766871321
745 452898677127110539181345586
746 474066860724210597954951746
747 496209662146705310324887453
748 519371285633088965774387694
749 543597910499374339189265571
750 568937778076803076003888172
751 595441282419621581928077577
752 623161064944021915878842932
753 652152113166076548420910720
754 682471863713609562867265735
755 714180309794247862426869029
756 747340113309609406899538149
757 782016721813505849894942566
758 818278490520400024941228821
759 856196809578950099608467432
760 895846236834538868772435449
761 937304636314004956481339475
762 980653322675621297827736821
763 1025977211877471983140859026
764 1073364978328032250014623987
765 1122909218793714970435145049
766 1174706623349694092393695068
767 1228858153672197700446620674
768 1285469228982977762770965245
769 1344649919969546053832746923
770 1406515151018327342200689133
771 1471184911111846393008395165
772 1538784473755760541947177444
773 1609444626316687670549497506
774 1683301909167701664768337658
775 1760498865054774988528407654
776 1841184299114698332358861245
777 1925513549992789064672013765
778 2013648772527387845149372119
779 2105759232487411995741935211
780 2202021613869477242329425202
781 2302620339281978580408029132
782 2407747903965447067819326681
783 2517605224021120750216884191
784 2632401999443414974822400721
785 2752357092576484087549413968
786 2877698922640783674945936721
787 3008665877002089227873546227
788 3145506739883275541115031504
789 3288481139247914983127578404
790 3437860012614906621909190272
791 3593926092594489731443260955
792 3756974412968642638367633597
793 3927312836172592289559649947
794 4105262603069504249823192293
795 4291158905946941015877856789
796 4485351485701937398950482616
797 4688205254221081492018552831
798 4900100943003404418315590115
799 5121435779116689532050999248
800 5352624189622636544307837567
801 5594098535652657100872782345
802 5846309877364590095712312454
803 6109728771060786813975792603
804 6384846099800513695689595659
805 6672173938893913237052744426
806 6972246457721570070832901167
807 7285620859382487867554868356
808 7612878359734746714354235841
809 7954625207456696817972267180
810 8311493746823042357490152285
811 8684143524958973659244686555
812 9073262445407444282086094173
813 9479567969919133799370200366
814 9903808370452454735202175073
815 10346764033451501429701249949
816 10809248818554009242752173958
817 11292111473968518407117619802
818 11796237110850971774927974278
819 12322548739105218691912622579
820 12872008867130348362668521961
821 13445621168139708753011940773
822 14044432215782930038218591948
823 14669533291912511964637787293
824 15322062269451652088022875635
825 16003205573439206800996632742
826 16714200223452142921255686308
827 17456335960734746818386861983
828 18230957463498420610244047918
829 19039466653995274942900012926
830 19883325101114194617493676008
831 20764056522398741893087575864
832 21683249389543504398274774209
833 22642559641588395595755073002
834 23643713510200372970182543659
835 24688510461608127607101881913
836 25778826259938984888210854841
837 26916616156897583761584047080
838 28103918212924410305782632850
839 29342856755177962687411803980
840 30635645977898834288856646591
841 31984593690936300273147482894
842 33392105222449775651784962157
843 34860687482037727933068441381
844 36392953190797054682184692677
845 37991625285075490640138878220
846 39659541500950159422235130956
847 41399659146745812557738168128
848 43215060071198566409445413543
849 45108955835173902734517188986
850 47084693095163402627678816305
851 49145759207111949531469853089
852 51295788059468130092837425060
853 53538566144704060660747151038
854 55878038878919146776000740964
855 58318317179524087261633025148
856 60863684311399153405886825508
857 63518603012333116732877094928
858 66287722908978677399322797794
859 69175888235005534207845886802
860 72188145863595976079265055819
861 75329753666908703957016833764
862 78606189215637286040486817452
863 82023158832308814139676401687
864 85586607012508881684261946596
865 89302726228779516912034151310
866 93177967132520245032145073173
867 97219049169827559901650713783
868 101432971627837984399888919654
869 105827025128793095980626270424
870 110408803589724782371278155756
871 115186216666364047322293299625
872 120167502700610476607009354218
873 125361242191660445025292794802
874 130776371811684051072301169373
875 136422198987762023134598471186
876 142308417072648401213683400502
877 148445121127811049889901907439
878 154842824343124160738136536149
879 161512475118543218937313790140
880 168465474834087817834561624437
881 175713696335489546839166217731
882 183269503163935562288156504206
883 191145769559451697396984125885
884 199355901268626930886088425127
885 207913857188582016278884049489
886 216834171880334188679963817041
887 226131978986005400721174110362
888 235823035585668881224988046311
889 245923747531026236173137233444
890 256451195794560497838969895368
891 267423163874317745424957963321
892 278858166296037151095737258635
893 290775478255974818494913823327
894 303195166449456881986572351968
895 316138121131950297535919178561
896 329626089461262227888165953560
897 343681710171369189036437309541
898 358328549630342191634723879499
899 373591139336872280164269377917
900 389495014912019537401703694932
901 406066756645006106271740464357
902 423334031654157884479551144646
903 441325637726468625843892678183
904 460071548901722464791056454042
905 479602962869664764776774950185
906 499952350251365361491993189115
907 521153505838671176675770589632
908 543241601868505984485272851784
909 566253243411742331097645702013
910 590226525959453916844739062381
911 615201095292554734646979312614
912 641218209724154137678562026046
913 668320804807403456844544488726
914 696553560605190597736162840541
915 725962971621752993475244023015
916 756597419500137775911032123189
917 788507248593439947707850087553
918 821744844521906739069454925718
919 856364715832308245954940679947
920 892423578880453603407213598093
921 929980446062377534013944973649
922 969096717524547585647702491611
923 1009836276488447096653968446393
924 1052265588330087129336620244501
925 1096453803560391855179686747705
926 1142472864858001204432597450375
927 1190397618311841793711047664344
928 1240305929036848133051739934557
929 1292278801332470924836679818568
930 1346400503560104737845328675804
931 1402758697922303787627912705486
932 1461444575333649794910950821341
933 1522552995580390557018387800463
934 1586182632973500808399092089632
935 1652436127707629143434605548418
936 1721420243146506187112353473244
937 1793246029263801191036168046563
938 1868028992477147936224188136679
939 1945889272122118031603820691669
940 2026951823822322787435760811245
941 2111346610021576079544665655859
942 2199208797954173707612814997322
943 2290678965339842473038311907662
944 2385903314100809671906880709143
945 2485033892409744273895678689545
946 2588228825389051348866875058647
947 2695652554794165297313382033106
948 2807476088026113341440781368654
949 2923877256831713220484080655138
950 3045040986063358003071982323553
951 3171159572884431820043809837696
952 3302432976821024830591877851742
953 3439069121075780133317563986219
954 3581284205535443235452623808838
955 3729303031920003278144325213608
956 3883359341538250135882730146798
957 4043696166132130938090938778736
958 4210566192310511322790602843270
959 4384232140091840085966227919775
960 4564967156094820967025556795968
961 4753055221936522554862949682569
962 4948791578418449299603452397888
963 5152483166102965107371525871320
964 5364449082905151185145705028801
965 5585021059348704831259346145236
966 5814543952158893726048424445313
967 6053376256890885638178443376054
968 6301890640318027283591243871041
969 6560474493331864691676396615379
970 6829530505133934964920015152413
971 7109477259528633908556118195717
972 7400749854156833138468361903255
973 7703800543541404057966242230879
974 8019099406848465594604640766153
975 8347135041302030048518132690027
976 8688415282224841710337465533541
977 9043467950714610614580665180893
978 9412841630002607859017814580870
979 9797106471580736405090939349119
980 10196855032223795470564071876425
981 10612703143075747314439758719675
982 11045290812012450308262215013522
983 11495283160538574412585193043439
984 11963371396523347370034507622211
985 12450273824128427999771554327903
986 12956736892331655019364113332598
987 13483536283502715190906856491587
988 14031478043541006972108191398675
989 14601399755142188342595966702492
990 15194171755818189720530593289889
991 15810698402355892011218010632602
992 16451919383462321848773007317671
993 17118811082409152490090616946294
994 17812387991556632391598332169576
995 18533704180706850439674712582396
996 19283854821308607142819457010256
997 20063977768611156110676222769358
998 20875255203941837583792111548208
999 21718915339363212413227127871893
1000 22596234187048856690613030518768