1 1
2 1
3 2
4 2
5 3
6 5
7 6
8 8
9 11
10 15
11 18
12 24
13 29
14 37
15 47
16 57
17 69
18 86
19 103
20 125
21 154
22 183
23 220
24 264
25 316
26 375
27 450
28 533
29 631
30 747
31 882
32 1035
33 1222
34 1428
35 1674
36 1959
37 2282
38 2653
39 3088
40 3578
41 4142
42 4790
43 5525
44 6363
45 7330
46 8410
47 9644
48 11050
49 12633
50 14424
51 16459
52 18743
53 21320
54 24232
55 27504
56 31173
57 35312
58 39935
59 45127
60 50952
61 57459
62 64726
63 72878
64 81945
65 92079
66 103383
67 115960
68 129956
69 145561
70 162870
71 182121
72 203498
73 227215
74 253489
75 282670
76 314923
77 350664
78 390208
79 433917
80 482199
81 535592
82 594452
83 659439
84 731099
85 810080
86 897043
87 992881
88 1098255
89 1214217
90 1341719
91 1481829
92 1635662
93 1804681
94 1990037
95 2193433
96 2416428
97 2660818
98 2928486
99 3221713
100 3542520
101 3893589
102 4277532
103 4697244
104 5155814
105 5656903
106 6203835
107 6800893
108 7452319
109 8162772
110 8937255
111 9781492
112 10701003
113 11702512
114 12792794
115 13979296
116 15269948
117 16673789
118 18199689
119 19858127
120 21659884
121 23616623
122 25740940
123 28046829
124 30548398
125 33261922
126 36204253
127 39393637
128 42849699
129 46594080
130 50648902
131 55039178
132 59791090
133 64932900
134 70494876
135 76510260
136 83013292
137 90042252
138 97637438
139 105842095
140 114702701
141 124269771
142 134595940
143 145739367
144 157761401
145 170727912
146 184709452
147 199782491
148 216027085
149 233530931
150 252386917
151 272694349
152 294559772
153 318098059
154 343429925
155 370686913
156 400008363
157 431543290
158 465451189
159 501903531
160 541081181
161 583179936
162 628407676
163 676986287
164 729153042
165 785162400
166 845283187
167 909805384
168 979037039
169 1053306353
170 1132964239
171 1218385919
172 1309968548
173 1408139044
174 1513350912
175 1626087090
176 1746863046
177 1876229229
178 2014768794
179 2163106582
180 2321906668
181 2491875200
182 2673765508
183 2868380620
184 3076571598
185 3299248451
186 3537377816
187 3791987109
188 4064171034
189 4355094935
190 4665994329
191 4998187325
192 5353074163
193 5732141438
194 6136971825
195 6569248160
196 7030754390
197 7523390842
198 8049175177
199 8610247932
200 9208885989
201 9847507460
202 10528675708
203 11255117307
204 12029725450
205 12855567763
206 13735903906
207 14674192950
208 15674100399
209 16739520130
210 17874582110
211 19083661799
212 20371405159
213 21742737785
214 23202877147
215 24757360075
216 26412055070
217 28173176173
218 30047315592
219 32041456897
220 34162994479
221 36419766989
222 38820078241
223 41372715376
224 44086992635
225 46972770253
226 50040482936
227 53301183163
228 56766571595
229 60449022602
230 64361643045
231 68518298087
232 72933653500
233 77623230597
234 82603450490
235 87891670439
236 93506260623
237 99466642350
238 105793346948
239 112508086921
240 119633819726
241 127194797720
242 135216670674
243 143726539134
244 152753036590
245 162326423348
246 172478674388
247 183243550982
248 194656734705
249 206755902756
250 219580842584
251 233173573459
252 247578470224
253 262842361556
254 279014706640
255 296147702286
256 314296437362
257 333519056107
258 353876925589
259 375434773245
260 398260919455
261 422427425879
262 448010307052
263 475089745431
264 503750319546
265 534081195169
266 566176429192
267 600135177693
268 636061979904
269 674067044765
270 714266559443
271 756782951762
272 801745290448
273 849289571619
274 899559099316
275 952704869048
276 1008885980093
277 1068269997781
278 1131033476860
279 1197362354858
280 1267452462674
281 1341510032698
282 1419752253721
283 1502407763392
284 1589717333764
285 1681934411044
286 1779325792822
287 1882172307990
288 1990769554060
289 2105428567142
290 2226476720658
291 2354258456890
292 2489136189575
293 2631491206349
294 2781724648716
295 2940258419962
296 3107536358742
297 3284025232695
298 3470215930729
299 3666624663513
300 3873794263041
301 4092295403265
302 4322728138119
303 4565723237561
304 4821943763968
305 5092086665561
306 5376884492078
307 5677107035623
308 5993563338143
309 6327103484638
310 6678620682991
311 7049053371194
312 7439387483187
313 7850658640047
314 8283954771190
315 8740418513172
316 9221249942524
317 9727709365038
318 10261120294645
319 10822872371054
320 11414424783436
321 12037309459653
322 12693134660267
323 13383588652627
324 14110443624975
325 14875559560318
326 15680888695788
327 16528479759935
328 17420482678838
329 18359153413454
330 19346859090918
331 20386083126603
332 21479431037428
333 22629636040599
334 23839565213072
335 25112225845797
336 26450772154162
337 27858512037777
338 29338914641442
339 30895617736766
340 32532435769781
341 34253368184159
342 36062608190479
343 37964551652108
344 39963806913468
345 42065204505885
346 44273807637079
347 46594923080767
348 49034112606781
349 51597204634201
350 54290306996094
351 57119819655805
352 60092448369805
353 63215218894496
354 66495491862838
355 69940978031780
356 73559754829545
357 77360282988678
358 81351424298085
359 85542460106518
360 89943110656944
361 94563554975238
362 99414452310992
363 104506963823585
364 109852775618858
365 115464122802651
366 121353814556532
367 127535260036023
368 134022496099410
369 140830215525932
370 147973796862775
371 155469335623625
372 163333676771787
373 171584448352826
374 180240097318557
375 189319926161875
376 198844131517376
377 208833844566016
378 219311173030250
379 230299244764843
380 241822253980900
381 253905508694796
382 266575480586845
383 279859857215665
384 293787596232944
385 308388981769163
386 323695683980485
387 339740820398563
388 356559020211515
389 374186491626877
390 392661091756908
391 412022399393691
392 432311791637353
393 453572523039657
394 475849808363097
395 499190909339765
396 523645224597564
397 549264383435818
398 576102344273862
399 604215496570137
400 633662767207551
401 664505732029310
402 696808731397818
403 730638990784552
404 766066747090396
405 803165379656467
406 842011546800550
407 882685328986353
408 925270377074407
409 969854067130645
410 1016527662287001
411 1065386480834618
412 1116530071216804
413 1170062395483492
414 1226092019204874
415 1284732309875744
416 1346101644007606
417 1410323622458099
418 1477527294354338
419 1547847391807469
420 1621424572842259
421 1698405675229386
422 1778943981111309
423 1863199492358395
424 1951339216695382
425 2043537467541856
426 2139976174278126
427 2240845206499173
428 2346342711657991
429 2456675466632647
430 2572059242814384
431 2692719188536785
432 2818890224803841
433 2950817458818828
434 3088756614220782
435 3232974479257888
436 3383749371937087
437 3541371627106452
438 3706144100423988
439 3878382694960581
440 4058416908671646
441 4246590404837825
442 4443261603895589
443 4648804302876379
444 4863608316338680
445 5088080145966433
446 5322643676260155
447 5567740899556999
448 5823832667961822
449 6091399480006960
450 6370942294642689
451 6662983381400839
452 6968067203281149
453 7286761336875886
454 7619657426415633
455 7967372181410447
456 8330548408976376
457 8709856091769415
458 9105993506912460
459 9519688392095771
460 9951699154436914
461 10402816133928229
462 10873862910943688
463 11365697671021221
464 11879214621101589
465 12415345465331700
466 12975060934716526
467 13559372385101816
468 14169333450955829
469 14806041771022586
470 15470640778548002
471 16164321566489017
472 16888324820588759
473 17643942837762118
474 18432521615149649
475 19255463029163765
476 20114227095533909
477 21010334323598896
478 21945368155991273
479 22920977514763572
480 23938879436871743
481 25000861822122897
482 26108786282781406
483 27264591111288521
484 28470294355417707
485 29727997026067322
486 31039886417838066
487 32408239570034454
488 33835426855093618
489 35323915714836832
490 36876274531760001
491 38495176665359871
492 40183404630715847
493 41943854452054623
494 43779540176024485
495 45693598569646881
496 47689293987776829
497 49770023445806251
498 51939321871403079
499 54200867574113852
500 56558487914974267
501 59016165206410127
502 61578042824822237
503 64248431578012638
504 67031816297720171
505 69932862703057017
506 72956424514154255
507 76107550852683891
508 79391493908785280
509 82813716924243854
510 86379902458248911
511 90095960989580858
512 93968039831628055
513 98002532404160025
514 102206087838522623
515 106585620974895461
516 111148322713708926
517 115901670784539473
518 120853440905609343
519 126011718386488346
520 131384910147581765
521 136981757225175274
522 142811347719828201
523 148883130262163595
524 155206927965969668
525 161792952931245426
526 168651821267519746
527 175794568718164946
528 183232666838739514
529 190978039816068697
530 199043081894622203
531 207440675484436921
532 216184209917876292
533 225287600949459509
534 234765310947207561
535 244632369876702246
536 254904397041055566
537 265597623664809481
538 276728916285807613
539 288315801065219045
540 300376488959434307
541 312929901871761849
542 325995699744134315
543 339594308692561244
544 353746950147662351
545 368475671128746967
546 383803375590551965
547 399753856980134224
548 416351831961208336
549 433622975428271805
550 451593956769436544
551 470292477527575759
552 489747310394853362
553 509988339700463162
554 531046603346803723
555 552954336337961912
556 575745015857635210
557 599453408070834508
558 624115616580702528
559 649769132726431744
560 676452887676213525
561 704207306484082665
562 733074364067289078
563 763097643306833388
564 794322395200019083
565 826795601281200614
566 860566038264490228
567 895684345106762770
568 932203092448104551
569 970176854665576473
570 1009662284467870146
571 1050718190281968055
572 1093405616387457562
573 1137787926030761527
574 1183930887479276407
575 1231902763289659580
576 1281774402718432508
577 1333619337566892827
578 1387513881419758989
579 1443537232549888045
580 1501771580454247938
581 1562302216339989704
582 1625217647492220353
583 1690609715862589770
584 1758573720845331781
585 1829208546559719309
586 1902616793612634662
587 1978904915712325554
588 2058183361071412141
589 2140566718993521002
590 2226173871621236052
591 2315128151218772876
592 2407557502976301168
593 2503594653767412325
594 2603377286809115407
595 2707048222682994205
596 2814755606711240375
597 2926653103125204907
598 3042900096031665889
599 3163661897679378704
600 3289109963992163908
601 3419422117902079578
602 3554782780499342220
603 3695383210511398961
604 3841421752142236991
605 3993104091857308615
606 4150643524104431897
607 4314261226592275670
608 4484186545173701384
609 4660657288934778251
610 4843920035555095607
611 5034230447621673617
612 5231853599920620706
613 5437064318430662656
614 5650147531107323648
615 5871398631162242841
616 6101123852948888291
617 6339640661251088101
618 6587278154043391272
619 6844377479568250061
620 7111292267872925813
621 7388389077632656691
622 7676047858431291673
623 7974662429429256454
624 8284640974547807860
625 8606406555156305632
626 8940397640475406610
627 9287068656667143062
628 9646890554859688360
629 10020351399194269900
630 10407956975100963199
631 10810231418956712936
632 11227717869428832441
633 11660979141644738792
634 12110598424534227930
635 12577180002617135404
636 13061350002543061859
637 13563757165733457678
638 14085073647543286152
639 14625995844284584671
640 15187245248582568715
641 15769569334555709310
642 16373742473254535586
643 17000566879940982560
644 17650873593770202250
645 18325523491455289876
646 19025408335541947553
647 19751451859043328246
648 20504610887030893502
649 21285876497037546137
650 22096275219015902081
651 22936870276714302000
652 23808762871293756812
653 24713093509241404948
654 25651043375379498645
655 26623835753150430979
656 27632737493146288932
657 28679060532080833878
658 29764163463270381295
659 30889453161041564232
660 32056386460118383076
661 33266471892552929083
662 34521271483449051345
663 35822402608074110085
664 37171539911727611854
665 38570417295213989363
666 40020829967286579074
667 41524636567083148684
668 43083761358148343719
669 44700196497111237109
670 46376004378759525134
671 48113320060866823248
672 49914353770530302614
673 51781393495579047947
674 53716807663075958908
675 55723047908543492214
676 57802651938113105246
677 59958246487560535917
678 62192550380463882275
679 64508377689687499120
680 66908641004738805862
681 69396354809297217274
682 71974638971677923459
683 74646722352911452416
684 77415946535266492835
685 80285769676182331945
686 83259770490799800657
687 86341652368187367927
688 89535247624712297836
689 92844521900094001238
690 96273578699689616493
691 99826664088886170162
692 103508171543572764630
693 107322646962738432288
694 111274793847485018721
695 115369478653010802653
696 119611736317997188921
697 124006775978354522866
698 128559986870255063481
699 133276944429631142831
700 138163416593449098375
701 143225370310527364770
702 148468978267407137084
703 153900625837518441465
704 159526918259731397572
705 165354688054820506579
706 171391002686392601047
707 177643172475492793938
708 184118758775703406959
709 190825582418513284499
710 197771732436456025168
711 204965575074154762187
712 212415763095328694758
713 220131245396697326564
714 228121276937184152717
715 236395428994025190714
716 244963599754986926664
717 253836025258752887021
718 263023290693353324212
719 272536342065627902665
720 282386498252043794219
721 292585463444653531751
722 303145340003460980544
723 314078641729545898675
724 325398307571021372967
725 337117715777262131387
726 349250698514047921540
727 361811556956005309783
728 374815076870106106500
729 388276544707308484140
730 402211764217068448406
731 416637073603078583362
732 431569363235682019508
733 447026093940442258909
734 463025315879630234909
735 479585688046978175424
736 496726498393624524117
737 514467684607089064740
738 532829855562103661561
739 551834313466474210337
740 571503076722350018486
741 591858903527143713116
742 612925316235873990437
743 634726626510920799543
744 657287961282085708051
745 680635289544537932246
746 704795450019368480462
747 729796179705642344862
748 755666143350343778483
749 782434963867155321176
750 810133253731851897422
751 838792647387142124924
752 868445834686900862247
753 899126595414223836889
754 930869834905251314777
755 963711620815603269617
756 997689221063077256845
757 1032841142985703282360
758 1069207173751362174190
759 1106828422060008710927
760 1145747361177103594876
761 1186007873342131864552
762 1227655295592901078387
763 1270736467052175469873
764 1315299777720360402902
765 1361395218823159434837
766 1409074434760783406033
767 1458390776710975417382
768 1509399357934980791196
769 1562157110841912511609
770 1616722845864215133011
771 1673157312202543517004
772 1731523260496183787112
773 1791885507481270308745
774 1854311002696028163697
775 1918868897299087087971
776 1985630615064322160885
777 2054669925621734504729
778 2126063020011914719818
779 2199888588628245628090
780 2276227901618151967084
781 2355164891822062253115
782 2436786240326391709037
783 2521181464713395498444
784 2608443010089077489875
785 2698666342977483936714
786 2791950048167121713147
787 2888395928603193672593
788 2988109108417307503460
789 3091198139193391818910
790 3197775109567290720369
791 3307955758265237992539
792 3421859590684182926981
793 3539609999125544284933
794 3661334386792365598718
795 3787164295667513691082
796 3917235538389819869311
797 4051688334253444862433
798 4190667449453994001888
799 4334322341714241175372
800 4482807309421274235500
801 4636281645415203529980
802 4794909795569494955229
803 4958861522312092291779
804 5128312073235360122893
805 5303442354953017385695
806 5484439112361895793123
807 5671495113475430727326
808 5864809339996533406226
809 6064587183807412706567
810 6271040649553566016619
811 6484388563510202139386
812 6704856788919916644129
813 6932678448000348217086
814 7168094150822307970578
815 7411352231269709955102
816 7662708990293265152290
817 7922428946681968704587
818 8190785095578066622736
819 8468059174972052871135
820 8754541940417256830725
821 9050533448215460284569
822 9356343347326836458691
823 9672291180270725889923
824 9998706693286776355508
825 10335930156037926932452
826 10684312691141240940241
827 11044216613825666044231
828 11416015782019141523915
829 11800095957182019200995
830 12196855176208421349980
831 12606704134730365166088
832 13030066582165841103870
833 13467379728866472025609
834 13919094665725539697721
835 14385676796623224867939
836 14867606284092553340967
837 15365378508604199843669
838 15879504541876854182917
839 16410511634635879207383
840 16958943719250341367471
841 17525361927696298923432
842 18110345125303275784099
843 18714490460757189020127
844 19338413932844184604268
845 19982750974437694465892
846 20648157054241015354529
847 21335308296817538205234
848 22044902121452660571842
849 22777657900409725400126
850 23534317637156646906473
851 24315646665159880762272
852 25122434367855542834133
853 25955494920429652962388
854 26815668054054805768882
855 27703819843251182111240
856 28620843517057852606481
857 29567660294722825107852
858 30545220246637194034790
859 31554503181263666233083
860 32596519558829122782737
861 33672311432574193553753
862 34782953418375268831690
863 35929553693579802022838
864 37113255025917140639677
865 38335235833375244279478
866 39596711275957845859713
867 40898934380263121792209
868 42243197197852585160686
869 43630831998407801191578
870 45063212498699206219509
871 46541755128423195024013
872 48067920333993533630142
873 49643213921403423940389
874 51269188439308336586182
875 52947444603512679754192
876 54679632764076319288687
877 56467454416293279363568
878 58312663756831553055221
879 60217069286357679850527
880 62182535460010756528685
881 64210984387128302372855
882 66304397581666744769649
883 68464817764800814786171
884 70694350721230653074192
885 72995167210765425720642
886 75369504936801742892043
887 77819670573358613642040
888 80348041852379714941031
889 82957069713061437259088
890 85649280515018969794560
891 88427278317148940151310
892 91293747224106575439209
893 94251453802365512155068
894 97303249567887668036088
895 100452073547485541542615
896 103700954916024014209368
897 107053015711662405196416
898 110511473631408639188741
899 114079644909315522620656
900 117760947279720422820391
901 121558903027993193821741
902 125477142131334697620266
903 129519405492230741522325
904 133689548267251025777119
905 137991543293950270366623
906 142429484618714078460026
907 147007591128465820127267
908 151730210289243298896650
909 156601821994726892248119
910 161627042527901598812916
911 166810628639114193360496
912 172157481743888589522797
913 177672652243948266907211
914 183361343975004634152395
915 189228918784955528882379
916 195280901246257459407759
917 201522983506327238989920
918 207961030279949869219779
919 214601083987769541888688
920 221449370045071133500441
921 228512302305159615176619
922 235796488661786005209234
923 243308736815176261716892
924 251056060206363310273884
925 259045684124639275566840
926 267285051993099431954907
927 275781831837366905169112
928 284543922942753789917244
929 293579462705240769605418
930 302896833681827505719206
931 312504670845942896273958
932 322411869053786707239516
933 332627590727612298345145
934 343161273762156473907399
935 354022639660570992337540
936 365221701906411260974726
937 376768774578398193331500
938 388674481214884219797997
939 400949763935117211017806
940 413605892824626969294599
941 426654475592233594869155
942 440107467506413992958337
943 453977181618951154470863
944 468276299284043906956337
945 483017880981246667470734
946 498215377450879934570231
947 513882641150757861851226
948 530033938043358149759829
949 546683959722780878592929
950 563847835891140313625918
951 581541147194259957130948
952 599779938426859296388481
953 618580732117662892451775
954 637960542505190263332680
955 657936889915245397432672
956 678527815551473820106741
957 699751896710622091211349
958 721628262434507465732024
959 744176609610990915116576
960 767417219536631508146237
961 791370974954006583338532
962 816059377577091442854809
963 841504566118407355412692
964 867729334832083192819089
965 894757152587312581215062
966 922612182487139653726524
967 951319302047867276660461
968 980904123954861020418883
969 1011393017410894041237646
970 1042813130093688683918839
971 1075192410739707480165331
972 1108559632371774772263537
973 1142944416188535057123110
974 1178377256134315180691126
975 1214889544168396473613302
976 1252513596253299802009336
977 1291282679082154513802720
978 1331231037565840857912500
979 1372393923101095862937804
980 1414807622641428699474408
981 1458509488593209607602546
982 1503537969559993697749842
983 1549932641958692766282014
984 1597734242531931701360987
985 1646984701781515418223313
986 1697727178348698854486492
987 1750006094367563836010015
988 1803867171818620545023773
989 1859357469910401909459348
990 1916525423517664652018555
991 1975420882705504800263507
992 2036095153369590681795910
993 2098601039023437456708750
994 2162992883764596900432947
995 2229326616452402939561257
996 2297659796130900796910572
997 2368051658731404817384225
998 2440563165090174864167073
999 2515257050317551366099761
1000 2592197874555996569164368