1 1
2 1
3 2
4 2
5 3
6 6
7 5
8 8
9 9
10 13
11 12
12 23
13 18
14 27
15 33
16 39
17 38
18 63
19 54
20 80
21 86
22 101
23 104
24 161
25 145
26 183
27 208
28 254
29 256
30 361
31 340
32 435
33 472
34 550
35 600
36 776
37 760
38 918
39 1018
40 1221
41 1260
42 1576
43 1610
44 1929
45 2129
46 2408
47 2590
48 3172
49 3274
50 3833
51 4173
52 4783
53 5120
54 6054
55 6414
56 7414
57 8025
58 9064
59 9792
60 11487
61 12076
62 13734
63 15045
64 16925
65 18254
66 20830
67 22250
68 25164
69 27338
70 30643
71 32992
72 37540
73 40026
74 44806
75 48817
76 54222
77 58559
78 65654
79 70488
80 78750
81 85176
82 94124
83 101698
84 113591
85 121906
86 134794
87 146090
88 161136
89 173682
90 192667
91 206938
92 228097
93 246600
94 270558
95 292036
96 322088
97 345856
98 379640
99 410178
100 449008
101 483330
102 530365
103 570078
104 623840
105 672981
106 733380
107 789640
108 863835
109 927406
110 1011345
111 1089264
112 1185361
113 1274118
114 1388273
115 1490840
116 1620708
117 1743647
118 1891370
119 2032480
120 2209443
121 2368866
122 2568360
123 2760346
124 2988474
125 3207513
126 3475696
127 3725410
128 4031045
129 4326036
130 4673599
131 5010688
132 5418020
133 5802278
134 6263224
135 6716443
136 7241548
137 7755776
138 8366688
139 8953856
140 9649599
141 10332336
142 11119960
143 11900150
144 12814862
145 13700467
146 14734270
147 15764430
148 16939518
149 18108418
150 19463947
151 20792120
152 22327922
153 23861854
154 25600250
155 27343441
156 29341726
157 31316314
158 33575234
159 35849248
160 38410065
161 40983060
162 43909968
163 46828032
164 50137440
165 53481120
166 57216542
167 61000704
168 65270649
169 69545511
170 74360206
171 79245996
172 84680186
173 90198446
174 96379280
175 102616594
176 109584407
177 116678200
178 124528104
179 132535702
180 141453153
181 150473568
182 160502047
183 170751576
184 182041769
185 193584922
186 206358844
187 219358771
188 233724246
189 248442236
190 264583630
191 281138048
192 299377367
193 317984256
194 338450486
195 359484844
196 382460123
197 406072422
198 431967285
199 458482688
200 487525291
201 517406170
202 549945666
203 583474464
204 620089604
205 657671364
206 698657502
207 740945982
208 786842416
209 834195348
210 885730108
211 938748852
212 996383836
213 1055918574
214 1120345128
215 1186953886
216 1259186937
217 1333642410
218 1414310432
219 1497785820
220 1587886471
221 1681117536
222 1781932279
223 1886061684
224 1998553519
225 2115069974
226 2240504078
227 2370513986
228 2510705592
229 2655684608
230 2811893246
231 2973892482
232 3147915922
233 3328423936
234 3522584804
235 3723683096
236 3939803850
237 4164130434
238 4404603200
239 4654300706
240 4922281505
241 5200062976
242 5497967182
243 5807472928
244 6138608310
245 6482684069
246 6851123718
247 7233520591
248 7642754430
249 8068159108
250 8522500065
251 8994926602
252 9499885143
253 10024302138
254 10584472674
255 11167216467
256 11788521856
257 12434895064
258 13124519772
259 13841327382
260 14605674106
261 15401095316
262 16247893248
263 17129359744
264 18068260339
265 19044659506
266 20084111406
267 21166422500
268 22316976666
269 23515017984
270 24789188617
271 26114971540
272 27524324256
273 28992192640
274 30550514514
275 32173840778
276 33897802572
277 35692320960
278 37597280498
279 39582052340
280 41686540383
281 43879178240
282 46204775664
283 48626519094
284 51193997624
285 53869558803
286 56703100816
287 59656259287
288 62784608050
289 66043042791
290 69493470005
291 73089900832
292 76894614040
293 80860419136
294 85056684810
295 89428677316
296 94052992992
297 98873590814
298 103968079874
299 109279178170
300 114892929143
301 120742518657
302 126923322936
303 133367350508
304 140170947960
305 147264254846
306 154754152470
307 162560142890
308 170800016153
309 179391104398
310 188453366327
311 197902232212
312 207870145427
313 218259394656
314 229215999184
315 240640458084
316 252680939930
317 265235325352
318 278467562152
319 292260343296
320 306793782043
321 321947420944
322 337905485060
323 354544949774
324 372068253025
325 390334114382
326 409564936722
327 429616772444
328 450716769314
329 472716887682
330 495867416228
331 519999315040
332 545386704032
333 571856496318
334 599689688622
335 628709579966
336 659224112844
337 691031243770
338 724468741057
339 759330458436
340 795962686502
341 834153669020
342 874283651854
343 916112410600
344 960054815734
345 1005865101339
346 1053970176078
347 1104119260918
348 1156779267188
349 1211664556454
350 1269285658503
351 1329351214814
352 1392386733380
353 1458093818816
354 1527047196392
355 1598909755554
356 1674307110934
357 1752894843405
358 1835319274454
359 1921228932216
360 2011328931542
361 2105220504203
362 2203672623978
363 2306279893318
364 2413835740799
365 2525925654024
366 2643415163936
367 2765837686784
368 2894134063224
369 3027827784400
370 3167893769140
371 3313846702848
372 3466747354038
373 3626048321048
374 3792902845289
375 3966755295073
376 4148799581413
377 4338469004814
378 4537063522234
379 4743946406976
380 4960527988480
381 5186159831684
382 5422307064484
383 5668311927092
384 5925764389401
385 6193924828681
386 6474518100736
387 6766795897186
388 7072549828406
389 7391018303854
390 7724147552791
391 8071084483396
392 8433936639504
393 8811839150990
394 9206986046572
395 9618503354888
396 10048767411853
397 10496798204736
398 10965170067968
399 11452894337589
400 11962651642732
401 12493440408000
402 13048166559116
403 13625712413928
404 14229217910434
405 14857555755330
406 15514002154020
407 16197423663402
408 16911364411870
409 17654554915430
410 18430827569660
411 19238908977068
412 20082799157788
413 20961217865536
414 21878491230466
415 22833193375582
416 23829992370083
417 24867459627790
418 25950477752578
419 27077619952640
420 28254159166121
421 29478499862528
422 30756334758204
423 32086078678006
424 33473683888770
425 34917571130983
426 36424167769732
427 37991717167516
428 39627146748914
429 41328712999148
430 43103675154544
431 44950311372460
432 46876449876078
433 48880168540672
434 50969904337340
435 53143771802040
436 55410610182350
437 57768567808496
438 60227177179958
439 62784376939520
440 65450428630028
441 68223318414520
442 71113817300479
443 74119976256080
444 77253392086349
445 80511887102774
446 83907943656248
447 87439471457634
448 91119574334503
449 94946245905984
450 98933598778210
451 103079395728190
452 107398810488340
453 111889722627312
454 116568080768322
455 121431903934888
456 126498343133994
457 131765175508648
458 137250843785390
459 142953300844789
460 148891937411177
461 155064887475476
462 161493007991084
463 168174207315550
464 175130884434046
465 182361182872016
466 189888679018460
467 197711788129024
468 205855840888601
469 214319026994284
470 223128554423784
471 232282947537588
472 241810853542766
473 251711150921222
474 262014613534574
475 272719945706684
476 283860165343690
477 295434416093699
478 307477501195074
479 319989057373738
480 333006439898640
481 346529143317148
482 360597252143616
483 375210869453620
484 390412247224286
485 406202131883064
486 422625866744646
487 439684162112802
488 457425632288314
489 475851765421062
490 495013861770716
491 514914277284172
492 535608023795470
493 557097521619898
494 579441741792093
495 602644159208813
496 626767005830522
497 651814877596136
498 677854504225914
499 704890732521792
500 732995048332976
501 762173639538752
502 792502016774240
503 823987858076150
504 856712062797116
505 890682771068934
506 925986636872642
507 962633581093210
508 1000715148233412
509 1040243150979584
510 1081315666466151
511 1123945306248290
512 1168237060167710
513 1214205801835669
514 1261962521579746
515 1311524575721626
516 1363010785718998
517 1416439699474222
518 1471938504993814
519 1529528683564338
520 1589344720926053
521 1651411233432320
522 1715872191154960
523 1782753988462274
524 1852210628916222
525 1924272226123778
526 1999101711648424
527 2076733260289656
528 2157341190524809
529 2240962117496826
530 2327782505422600
531 2417843741289596
532 2511343135821281
533 2608327191312600
534 2709006971933696
535 2813432402489410
536 2921829118300740
537 3034253057039198
538 3150943111251648
539 3271961746733831
540 3397564382636335
541 3527818029248524
542 3662995727926338
543 3803172150071370
544 3948636395762052
545 4099471335617778
546 4255986020687524
547 4418269447841280
548 4586651830727946
549 4761231743361886
550 4942358998751735
551 5130142551389785
552 5324956190926428
553 5526916854827896
554 5736423867354254
555 5953606292636092
556 6178887179391986
557 6412408569364172
558 6654622450035534
559 6905681325223166
560 7166067870929919
561 7435949686313030
562 7715838345238528
563 8005917788147074
564 8306734323257328
565 8618485342548754
566 8941754157782070
567 9276757148032560
568 9624112590625294
569 9984057165275480
570 10357251067140435
571 10743948315198452
572 11144853567855389
573 11560244422336000
574 11990868000829663
575 12437027330336328
576 12899519848083858
577 13378670620050080
578 13875330683724565
579 14389854535948480
580 14923144572319762
581 15475586777331542
582 16048144207886796
583 16641230942967976
584 17255874378913944
585 17892525039686627
586 18552272591811656
587 19235606795358220
588 19943690151866734
589 20677047748898744
590 21436919620662033
591 22223876132469472
592 23039232552792316
593 23883607699335168
594 24758404522810002
595 25664286474025600
596 26602749546113480
597 27574513075525632
598 28581164166361034
599 29623482180174912
600 30703159503035576
601 31821031242764410
602 32978901817503855
603 34177675499664454
604 35419266599927664
605 36704653329850718
606 38035876646733264
607 39413984631175424
608 40841152686782822
609 42318513914999186
610 43848376640817363
611 45431965206816764
612 47071739945698467
613 48769012012411666
614 50526403400115324
615 52345330132360326
616 54228574374711710
617 56177664191435968
618 58195564516019974
619 60283911416633536
620 62445863793612028
621 64683186271640878
622 66999231201668230
623 69395901033267770
624 71876767273384547
625 74443865956499351
626 77101001646883054
627 79850368377810672
628 82696003645031172
629 85640270154868760
630 88687468750290716
631 91840127431009792
632 95102826533675124
633 98478287300947394
634 101971370885788082
635 105585005393432484
636 109324367608839432
637 113192589204513030
638 117195182559063502
639 121335515959756878
640 125619439640339832
641 130050574409982720
642 134635149455087728
643 139377036381734912
644 144282866474529341
645 149356800072442634
646 154605875245715374
647 160034561092715412
648 165650349694129863
649 171458017675778240
650 177465539609541815
651 183678044652291585
652 190103996254423852
653 196748899676004248
654 203621762832640728
655 210728468401986040
656 218078602063092222
657 225678475645638074
658 233538262801447382
659 241664733752111550
660 250068714141761484
661 258757435450198016
662 267742415982339318
663 277031409890489204
664 286636641202056782
665 296566421262117378
666 306833755324654498
667 317447518765816088
668 328421545837799632
669 339765346558851726
670 351493602986732300
671 363616502537736452
672 376149662141017821
673 389103956543205484
674 402495995455844290
675 416337424756329149
676 430645870712969646
677 445433800804233382
678 460719960625931994
679 476517655184144640
680 492846817529391160
681 509721687032333412
682 527163416483008606
683 545187241854615562
684 563815654178253205
685 583064907352830720
686 602958913234958340
687 623515058359199456
688 644758715752765864
689 666708477940873216
690 689391318950512031
691 712827068077888960
692 737044397504516348
693 762064506330267187
694 787917817550982664
695 814626990036905752
696 842224359497512426
697 870734084093792122
698 900190529772197062
699 930619511233064448
700 962057489799583777
701 994532043192721630
702 1028081918924930108
703 1062736511703449680
704 1098536993327302585
705 1135514758208426088
706 1173713486030332988
707 1213166700732579850
708 1253920811318383174
709 1296011538852931584
710 1339488188257701468
711 1384388893968027888
712 1430765959216989752
713 1478660085767005408
714 1528126835763731665
715 1579209567317461153
716 1631967297819762924
717 1686446293331074290
718 1742709155957539448
719 1800805246224619946
720 1860801053890246163
721 1922749144569963426
722 1986720131634632395
723 2052770083654559744
724 2120973894878447472
725 2191391358077794183
726 2264102005259379990
727 2339169495422851818
728 2416678276824595334
729 2496696221320443702
730 2579312889849576368
731 2664600634797305608
732 2752654544947323866
733 2843551628300021780
734 2937392834930482568
735 3034260238648285332
736 3134260888892529210
737 3237482242526876435
738 3344037937638566222
739 3454021034668672126
740 3567552153970205632
741 3684730438228845912
742 3805683784279905684
743 3930517799844061184
744 4059368227621344316
745 4192347410303934380
746 4329599407370202908
747 4471243862335057928
748 4617433506949244396
749 4768295738648442830
750 4923992632254435617
751 5084659675675275560
752 5250468842488907167
753 5421564372446227764
754 5598128573211705648
755 5780314981538278758
756 5968317021363010293
757 6162297935619707410
758 6362462928341564480
759 6568985729495756426
760 6782083847402025596
761 7001942144914244608
762 7228791355550402370
763 7462827980733881084
764 7704296761663706212
765 7953406751892540621
766 8210417339177634744
767 8475550903782522240
768 8749082555203567721
769 9031248611609428978
770 9322340837327834295
771 9622610567318565820
772 9932366987279281560
773 10251877366749901978
774 10581469577405491390
775 10921427572815344531
776 11272099011387245572
777 11633785793516928204
778 12006856294069879150
779 12391631457494697968
780 12788501852725204333
781 13197808371674264192
782 13619965087138518155
783 14055334329546345628
784 14504354787308717116
785 14967411528592902702
786 15444969595920492750
787 15937437895497941056
788 16445309369102240112
789 16969018506217313676
790 17509087490348664118
791 18065977945405957962
792 18640243328471859332
793 19232373720292545936
794 19842955686240531264
795 20472509823401443546
796 21121657408258871044
797 21790951389243426816
798 22481050144296679431
799 23192540574062505420
800 23926120321530326753
801 24682412652615107976
802 25462156402663317774
803 26266013389911604922
804 27094766435823489348
805 27949117829378798311
806 28829896944731129320
807 29737849386780272856
808 30673853379440433134
809 31638700427605669254
810 32633320890270932412
811 33658554486099838720
812 34715386733689163322
813 35804708900665043240
814 36927564416695936866
815 38084899172574632328
816 39277818351681194983
817 40507325232515113258
818 41774590335843227818
819 43080678256502372479
820 44426828125451160114
821 45814169485295430240
822 47244014593243450128
823 48717561261903748022
824 50236199094017520398
825 51801198778079269660
826 53414031173203566610
827 55076044155484162048
828 56788795124426375367
829 58553713102334907284
830 60372447021687695814
831 62246512474933122700
832 64177654570145580619
833 66167480560147252084
834 68217837933814166578
835 70330430345648915494
836 72507213542364272866
837 74749993938125070522
838 77060841071613277526
839 79441670148851154112
840 81894671761655361299
841 84421875547541692000
842 87025600095708121976
843 89707996958757256130
844 92471519279848041712
845 95318447642120192549
846 98251378268081506794
847 101272727505055319554
848 104385242825317005688
849 107591485109684025452
850 110894360877703980791
851 114296583965762795200
852 117801229915278345601
853 121411173513469673536
854 125129668963783132680
855 128959762318815395231
856 132904895670832492482
857 136968296262749272064
858 141153605782080153748
859 145464242180631569964
860 149904058076168226562
861 154476674217024492220
862 159186165099265487532
863 164036365999875151520
864 169031586985766994922
865 174175889143960398410
866 179473831473967508444
867 184929715079185187506
868 190548360829247162218
869 196334323654696830054
870 202292702356386361062
871 208428319095005938292
872 214746566301101418702
873 221252550010896575808
874 227951971603107176880
875 234850237293067732146
876 241953376193614966321
877 249267110556045123600
878 256797815714097993664
879 264551549500760696990
880 272535051547840402518
881 280754734449641432204
882 289217724157357624127
883 297930806826997905474
884 306901516430156562865
885 316137035578615342256
886 325645327634464382924
887 335433994275434973760
888 345511454007086531552
889 355885749777114986986
890 366565780762401752844
891 377560058048951585162
892 388877986668672045044
893 400528572423567454950
894 412521756366918780266
895 424867065291364279180
896 437575006221332293219
897 450655658395928277738
898 464120124535372020328
899 477979067614429832702
900 492244221315934500933
901 506926863341272813960
902 522039393528319316408
903 537593741197087471964
904 553603007321387349504
905 570079809587321134944
906 587037991395953699316
907 604490895403729929376
908 622453148699383071620
909 640938862076577906440
910 659963487537310636394
911 679541947228839136972
912 699690566318734051285
913 720425121425734094104
914 741762859312167210010
915 763720461657680000534
916 786316145283710264554
917 809567547639344219584
918 833493912067353225503
919 858113882624395098112
920 883447785912408520473
921 909515331766526898824
922 936337987079189238726
923 963936587035182369974
924 992333804765091910267
925 1021551660609025093695
926 1051614100473615761750
927 1082544399145156624754
928 1114367842278601234946
929 1147109028938113381600
930 1180794661646516428262
931 1215450734159258064916
932 1251105443757753791354
933 1287786259893621880158
934 1325522953306258207548
935 1364344551090654265131
936 1404282487485995488510
937 1445367429957483933184
938 1487632567506107882126
939 1531110302748212069864
940 1575835671762614697966
941 1621842908304944646196
942 1669169000754698417928
943 1717850111270754803872
944 1767925287279172228362
945 1819432730083528784617
946 1872413654509003686080
947 1926908413523388672000
948 1982960512149183218560
949 2040612569147196273818
950 2099910504692179819675
951 2160899332825299977904
952 2223627515835472347570
953 2288142594734128375808
954 2354495717323737847935
955 2422737085589649448194
956 2492920678902583633764
957 2565099511419402531136
958 2639330542922555689940
959 2715669753945426262434
960 2794177251945650708351
961 2874912140903608308254
962 2957937846763043565680
963 3043316773615349912852
964 3131115840110273765632
965 3221400930775507894784
966 3314242652173058018722
967 3409710553449380120290
968 3507879128587272567102
969 3608821797499731701056
970 3712617145604070005234
971 3819342674540204977856
972 3929081288721439057642
973 4041914787171749126162
974 4157930626409128652086
975 4277215143530641035928
976 4399860585734177569838
977 4525958074670926499072
978 4655604913623935550968
979 4788897261364722424354
980 4925937749329267857974
981 5066827854103185898270
982 5211675814339856988556
983 5360588712526733770910
984 5513680703742473645026
985 5671064771791483811122
986 5832861305807621955374
987 5999189518386574669358
988 6170176358752314679988
989 6345947604595520520360
990 6526637125617141458320
991 6712377610196059013120
992 6903310218939003934702
993 7099574932577765834330
994 7301320583582357881234
995 7508694837745480573952
996 7721854619035984561132
997 7940955682115491800174
998 8166163474557982421056
999 8397642284820549457582
1000 8635566528749208080817