0 1
1 1
2 1
3 2
4 3
5 4
6 6
7 8
8 11
9 15
10 20
11 26
12 34
13 44
14 56
15 72
16 91
17 114
18 144
19 179
20 222
21 275
22 338
23 414
24 507
25 617
26 748
27 906
28 1093
29 1314
30 1578
31 1888
32 2253
33 2685
34 3190
35 3782
36 4477
37 5286
38 6230
39 7331
40 8609
41 10091
42 11812
43 13801
44 16099
45 18755
46 21813
47 25332
48 29383
49 34031
50 39362
51 45474
52 52465
53 60457
54 69589
55 80003
56 91871
57 105389
58 120762
59 138231
60 158073
61 180575
62 206078
63 234967
64 267648
65 304595
66 346341
67 393455
68 446595
69 506495
70 573949
71 649859
72 735238
73 831180
74 938925
75 1059857
76 1195478
77 1347481
78 1517753
79 1708343
80 1921556
81 2159946
82 2426301
83 2723739
84 3055712
85 3425990
86 3838773
87 4298707
88 4810870
89 5380898
90 6015021
91 6720042
92 7503504
93 8373722
94 9339785
95 10411742
96 11600655
97 12918616
98 14378971
99 15996384
100 17786889
101 19768138
102 21959516
103 24382202
104 27059479
105 30016881
106 33282292
107 36886322
108 40862505
109 45247435
110 50081236
111 55407802
112 61275025
113 67735333
114 74846030
115 82669595
116 91274343
117 100734869
118 111132457
119 122555875
120 135101968
121 148876180
122 163993560
123 180579497
124 198770430
125 218715071
126 240575353
127 264527365
128 290762854
129 319490428
130 350936791
131 385348559
132 422993838
133 464163778
134 509174837
135 558370766
136 612124615
137 670841524
138 734961240
139 804960666
140 881357327
141 964712513
142 1055634568
143 1154783128
144 1262873106
145 1380678837
146 1509039322
147 1648863235
148 1801134158
149 1966917033
150 2147364472
151 2343723297
152 2557342560
153 2789681382
154 3042317193
155 3316955603
156 3615440194
157 3939762834
158 4292075851
159 4674704206
160 5090158399
161 5541149427
162 6030603973
163 6561680420
164 7137787315
165 7762602181
166 8440091428
167 9174533080
168 9970540076
169 10833084930
170 11767527720
171 12779644839
172 13875659584
173 15062276477
174 16346716797
175 17736756337
176 19240767541
177 20867763296
178 22627443497
179 24530246690
180 26587403997
181 28810996379
182 31214017987
183 33810442336
184 36615292742
185 39644719815
186 42916082664
187 46448035339
188 50260621582
189 54375374280
190 58815421443
191 63605601853
192 68772586839
193 74345009873
194 80353607721
195 86831369202
196 93813693570
197 101338562543
198 109446721846
199 118181874455
200 127590890098
201 137724026430
202 148635164670
203 160382064291
204 173026632329
205 186635210158
206 201278882951
207 217033807118
208 233981558960
209 252209510213
210 271811225768
211 292886886943
212 315543746924
213 339896613114
214 366068360577
215 394190483619
216 424403680271
217 456858474325
218 491715882743
219 529148123046
220 569339366146
221 612486542975
222 658800199908
223 708505408677
224 761842740527
225 819069299319
226 880459820323
227 946307845435
228 1016926969674
229 1092652166573
230 1173841204674
231 1260876149839
232 1354164962555
233 1454143203372
234 1561275841963
235 1676059179950
236 1799022902489
237 1930732254469
238 2071790353024
239 2222840653115
240 2384569562963
241 2557709222375
242 2743040463416
243 2941395950466
244 3153663515312
245 3380789708811
246 3623783567542
247 3883720613373
248 4161747110397
249 4459084578967
250 4777034587847
251 5116983851804
252 5480409636752
253 5868885496070
254 6284087369868
255 6727800051109
256 7201924046314
257 7708482866913
258 8249630758013
259 8827660896605
260 9445014100759
261 10104288059469
262 10808247121067
263 11559832686934
264 12362174225023
265 13218600946718
266 14132654200976
267 15108100605147
268 16148945963202
269 17259450033179
270 18444142169684
271 19707837899947
272 21055656505317
273 22493039640471
274 24025771059365
275 25659997530072
276 27402250979911
277 29259471951066
278 31239034461548
279 33348772323160
280 35597007010381
281 37992577189026
282 40544869969640
283 43263853994116
284 46160114482280
285 49244890317588
286 52530113298964
287 56028449705117
288 59753344268129
289 63719066704316
290 67940760972223
291 72434497374563
292 77217327677782
293 82307343444833
294 87723737723478
295 93486870291899
296 99618336688880
297 106141041199526
298 113079274032058
299 120458792948977
300 128306909558148
301 136652580537726
302 145526504101449
303 154961221948711
304 164991227020077
305 175653077413026
306 186985516749874
307 199029601371466
308 211828834768586
309 225429309597882
310 239879857718490
311 255232208726623
312 271541157400727
313 288864740564129
314 307264423920702
315 326805299350794
316 347556293258856
317 369590386617412
318 392984847283151
319 417821475273809
320 444186861755022
321 472172662415142
322 501875886031363
323 533399199095433
324 566851247298723
325 602346994810758
326 640008082360046
327 679963205057022
328 722348511046426
329 767308022159863
330 814994077672715
331 865567802429165
332 919199600695794
333 976069677036588
334 1036368585680750
335 1100297809960809
336 1168070373336042
337 1239911483711175
338 1316059212880900
339 1396765212872187
340 1482295471172217
341 1572931106964054
342 1668969210442598
343 1770723727517766
344 1878526392367752
345 1992727710260634
346 2113697993323857
347 2241828452116345
348 2377532345824261
349 2521246194189803
350 2673431054482716
351 2834573866800617
352 3005188871307337
353 3185819101241830
354 3377037955526094
355 3579450855155835
356 3793696987814182
357 4020451145162120
358 4260425657655440
359 4514372432029188
360 4783085096628393
361 5067401260202623
362 5368204890117235
363 5686428815995170
364 6023057365297509
365 6379129137729048
366 6755739925451704
367 7154045786639194
368 7575266280338551
369 8020687870738823
370 8491667509565422
371 8989636405808524
372 9516103992179123
373 10072662098374185
374 10660989341796728
375 11282855746612539
376 11940127602800542
377 12634772577496067
378 13368865091227541
379 14144591972517402
380 14964258405053516
381 15830294182010760
382 16745260283086302
383 17711855790646632
384 18732925161851500
385 19811465874723154
386 20950636467086618
387 22153764987874707
388 23424357881536893
389 24766109327384012
390 26182911056390904
391 27678862669381179
392 29258282481772498
393 30925718920884386
394 32685962503401027
395 34544058422009672
396 36505319771224124
397 38575341444198533
398 40760014733970886
399 43065542673750318
400 45498456152896898
401 48065630847106627
402 50774305002711280
403 53632098117299516
404 56647030561004019
405 59827544184440987
406 63182523961895193
407 66721320720785337
408 70453775010376278
409 74390242165658624
410 78541618625109694
411 82919369563310148
412 87535557902747240
413 92402874772321025
414 97534671482720589
415 102944993092639749
416 108648613643447077
417 114661073143013685
418 120998716383720730
419 127678733683832479
420 134719203645018876
421 142139138023710662
422 149958528818734564
423 158198397681847481
424 166880847763362520
425 176029118110494979
426 185667640740899652
427 195822100520200414
428 206519497978523094
429 217788215206648673
430 229658084979600424
431 242160463262564647
432 255328305260533831
433 269196245181231841
434 283800679888980435
435 299179856634650720
436 315373965056137773
437 332425233653038008
438 350378030947842216
439 369278971556522078
440 389177027401938007
441 410123644313434442
442 432172864268009228
443 455381453540470308
444 479809037041439024
445 505518239135717690
446 532574831247264117
447 561047886570168465
448 591009942220560186
449 622537169180022157
450 655709550396198070
451 690611067423932711
452 727329896008135480
453 765958611026882615
454 806594401233356440
455 849339294255555826
456 894300392332582521
457 941590119289134725
458 991326479273014643
459 1043633327803217377
460 1098640655702122221
461 1156484886511700696
462 1217309188019721096
463 1281263798551417627
464 1348506368712163423
465 1419202319296493346
466 1493525216112345031
467 1571657162503618765
468 1653789210388235024
469 1740121790666959855
470 1830865163897237481
471 1926239892165195101
472 2026477333132276004
473 2131820157277286906
474 2242522889399104817
475 2358852475494456763
476 2481088876175623847
477 2609525687843649504
478 2744470792888482643
479 2886247040244844506
480 3035192957690470096
481 3191663497336792391
482 3356030815827362584
483 3528685090825242225
484 3710035375442624039
485 3900510492340060758
486 4100559969297821708
487 4310655018143648206
488 4531289559005407599
489 4762981291942709943
490 5006272818104342425
491 5261732812654047325
492 5529957251804575191
493 5811570696405220650
494 6107227634636712367
495 6417613886478134151
496 6743448072729998134
497 7085483151500950737
498 7444508025191605973
499 7821349221144472748
500 8216872649268960673
501 8631985440093680879
502 9067637866851893790
503 9524825355364810046
504 10004590585650216256
505 10508025689358058325
506 11036274547314820320
507 11590535191643395498
508 12172062317122551439
509 12782169906654440479
510 13422233975918491221
511 14093695442513697312
512 14798063125123003361
513 15536916878471665963
514 16311910870104893432
515 17124777005272631348
516 17977328506479580656
517 18871463654545559233
518 19809169698318818004
519 20792526940491361464
520 21823713007290337818
521 22905007310156534923
522 24038795707868428984
523 25227575377938145976
524 26473959906487303885
525 27780684606204386589
526 29150612072401707389
527 30586737987622022303
528 32092197185690844651
529 33670269986581665277
530 35324388813950217736
531 37058145107698985181
532 38875296544466133322
533 40779774579486236849
534 42775692323841963141
535 44867352771728619251
536 47059257392979211008
537 49356115106744767404
538 51762851652906166987
539 54284619378501304365
540 56926807457183551899
541 59695052560497764577
542 62595250000560053655
543 65633565364555553367
544 68816446662338903955
545 72150637009326294418
546 75643187867804100380
547 79301472870762601207
548 83133202253384837446
549 87146437918378840565
550 91349609162452263571
551 95751529092382396909
552 100361411760330265972
553 105188890049301782387
554 110244034340962109181
555 115537371999360075711
556 121079907705535457918
557 126883144679453220583
558 132959106827234127954
559 139320361853249226818
560 145980045378306348446
561 152951886106878769134
562 160250232088129387072
563 167890078117357610266
564 175887094326439683178
565 184257656013867277559
566 193018874767103076196
567 202188630932164979527
568 211785607487644568095
569 221829325382749526377
570 232340180401433333799
571 243339481617261967508
572 254849491506355473687
573 266893467788531671331
574 279495707069694736307
575 292681590361541498359
576 306477630557803013697
577 320911521949524494696
578 336012191865301409762
579 351809854525933883755
580 368336067206663163744
581 385623788804001108340
582 403707440908157304451
583 422622971486237785159
584 442407921285722714914
585 463101493072229080914
586 484744623820259549988
587 507380059980518400502
588 531052435952441715249
589 555808355895874857561
590 581696479021323908950
591 608767608503911715821
592 637074784172118661070
593 666673379128571479243
594 697621200466563770086
595 729978594252686588827
596 763808554952905145184
597 799176839486642398913
598 836152086100961906994
599 874805938264769421124
600 915213173791080671104
601 957451839403873711939
602 1001603390974847408031
603 1047752839664549288538
604 1095988904211861288126
605 1146404169625730372117
606 1199095252543310372941
607 1254162973529389595144
608 1311712536603106172786
609 1371853716289508832370
610 1434701052505556001520
611 1500374053602652113823
612 1568997407900807311734
613 1640701204063030303262
614 1715621160672616029578
615 1793898865390582570653
616 1875682024085704101893
617 1961124720345371915753
618 2050387685791908262462
619 2143638581646020896292
620 2241052291996814397492
621 2342811229256184606279
622 2449105652294582363572
623 2560133997775038355440
624 2676103225223012125150
625 2797229176391137499840
626 2923736949500282041239
627 3055861288961542510434
628 3193846991207939448409
629 3337949327289652290604
630 3488434482912678286373
631 3645580016627887360795
632 3809675336905584192321
633 3981022198859908193521
634 4159935221417791849706
635 4346742425758764105020
636 4541785795884662704430
637 4745421862212404526769
638 4958022309118365721922
639 5179974607399683200554
640 5411682672656010352273
641 5653567550634956484677
642 5906068130625656292577
643 6169641888027765482387
644 6444765657267680056999
645 6731936436279980518381
646 7031672223820130510998
647 7344512890924335934606
648 7671021087884253069358
649 8011783188158054870796
650 8367410270695253162202
651 8738539142210696312290
652 9125833401003460386222
653 9529984543978963223025
654 9951713118597629592745
655 10391769921540976594818
656 10850937245956116319776
657 11330030179212471130727
658 11829897953180134166574
659 12351425349117837129459
660 12895534159340003553533
661 13463184707917051429868
662 14055377432751027767880
663 14673154531459915654299
664 15317601673598750754304
665 15989849781844093509094
666 16691076884870545416458
667 17422510044754089283183
668 18185427361847161604692
669 18981160060184665046827
670 19811094656598836381985
671 20676675216844101783891
672 21579405702160928818378
673 22520852409840479854722
674 23502646511489703018198
675 24526486692839534291215
676 25594141899087408744188
677 26707454189919426158806
678 27868341708517477526056
679 29078801769022720616545
680 30340914067099151546411
681 31656844018419869084307
682 33028846230084304633413
683 34459268110167372501939
684 35950553620801422493678
685 37505247180399416398011
686 39125997720843106671611
687 40815562905683438326531
688 42576813515632324975901
689 44412738007865600781507
690 46326447255906622736503
691 48321179477119131587858
692 50400305355106840768927
693 52567333364596147437913
694 54825915306667829921933
695 57179852062503913177444
696 59633099574127424804128
697 62189775060936056862629
698 64854163481166135221713
699 67630724247771199013120
700 70524098208560487721071
701 73539114900817109168147
702 76680800091004088237166
703 79954383610569509778373
704 83365307499280006952100
705 86919234467945432655543
706 90622056692847385894521
707 94479904954650839811977
708 98499158135062018983509
709 102686453084997668888595
710 107048694878551505477387
711 111593067467583580300210
712 116327044752318391894808
713 121258402083918441507202
714 126395228215602299085262
715 131745937719501043135695
716 137319283887094867720300
717 143124372131743523094908
718 149170673912521096192777
719 155468041199288231653559
720 162026721499684147729238
721 168857373469497840133825
722 175971083128683575347680
723 183379380706121159903982
724 191094258137087774275075
725 199128187238306370126016
726 207494138586366869375330
727 216205601126282039023615
728 225276602537941057073358
729 234721730389261680147477
730 244556154105918078497241
731 254795647788637060831152
732 265456613910211958854043
733 276556107925582539131761
734 288111863829572347015282
735 300142320698163408519366
736 312666650250524051509411
737 325704785470390309237837
738 339277450326836655139518
739 353406190635959706172667
740 368113406106540756164923
741 383422383614351470223950
742 399357331751424013039633
743 415943416698324231879800
744 433206799469246392153478
745 451174674581592825829230
746 469875310203613858542871
747 489338089835664888296316
748 509593555582691207952321
749 530673453077679500691124
750 552610778118020512146952
751 575439825079013206532046
752 599196237171109427400029
753 623917058609952615842822
754 649640788770807792404292
755 676407438401615768935098
756 704258587971635653299631
757 733237448235469788708339
758 763388923095197653958115
759 794759674846383526391441
760 827398191896870900914332
761 861354859050538463919087
762 896682030451571819626885
763 933434105288306601892720
764 971667606359326190802046
765 1011441261608255404615591
766 1052816088737585161235704
767 1095855483015896773071859
768 1140625308397033151598924
769 1187193992074093172128679
770 1235632622595609869029901
771 1286015051675918426773065
772 1338417999836532087825693
773 1392921166020328762243711
774 1449607341325514316820129
775 1508562527011676853157530
776 1569876056935786027267380
777 1633640724581729292131194
778 1699952914852920158953830
779 1768912740803669137480849
780 1840624185491383327459657
781 1915195249138263754110321
782 1992738101798008201393696
783 2073369241730109693236075
784 2157209659691675809544535
785 2244385009364290278452711
786 2335025784141304838391010
787 2429267500509096047781477
788 2527250888264258051643243
789 2629122087817438349540856
790 2735032854843570210020135
791 2845140772547623094456947
792 2959609471824692424975386
793 3078608859603294252224421
794 3202315355671130547868528
795 3330912138293359293448431
796 3464589398944553510132832
797 3603544606487077838188703
798 3747982781140563879937834
799 3898116778599540896041417
800 4054167584669090958724310
801 4216364620801662423151354
802 4384946060931908736685514
803 4560159160020637079298611
804 4742260594733669833769400
805 4931516816696659262166604
806 5128204418782669641006261
807 5332610514905669975780639
808 5545033133809983976271574
809 5765781627363241742368787
810 5995177093878490044349305
811 6233552817009866932635135
812 6481254720785653283280531
813 6738641841362601402614543
814 7006086816106232992700462
815 7283976390623319526544910
816 7572711944395032418422363
817 7872710035682304811900352
818 8184402966398807800212635
819 8508239367671639102431465
820 8844684806835380910996450
821 9194222416631635065540342
822 9557353547413518473080266
823 9934598443182932089591726
824 10326496942317735169724653
825 10733609203876296675190286
826 11156516460398293363853285
827 11595821798153114950681670
828 12052150965820858184222976
829 12526153212625683068609653
830 13018502156977305349140182
831 13529896686713651030783406
832 14061061892076244538788053
833 14612750032589785893700564
834 15185741539058639541562946
835 15780846051935656169817915
836 16398903497362927283421823
837 17040785202229780858889900
838 17707395049640617904190302
839 18399670676234117632494630
840 19118584712845958805863098
841 19865146070059574945448316
842 20640401270243640532668060
843 21445435827731035429186002
844 22281375678852019862179173
845 23149388663594337613827855
846 24050686060725018292917183
847 24986524178272841718100092
848 25958206001336830461719517
849 26967082899254825298194927
850 28014556394237250940243703
851 29102079993644675474573529
852 30231161088163788888560636
853 31403362918215060322199660
854 32620306611006667886285851
855 33883673290733420162952826
856 35195206264506400021227531
857 36556713286689055934400762
858 37970068904408544095069489
859 39437216887107391218837033
860 40960172743100109826798563
861 42541026326202365884697938
862 44181944535606788631642749
863 45885174112289642109385708
864 47653044535346469609326092
865 49487971021772603499032037
866 51392457633326233688509600
867 53369100494237683227811675
868 55420591123658789730697479
869 57549719886880979897910709
870 59759379569489900094143889
871 62052569078768483594169457
872 64432397276809252903419281
873 66902086949950637444994061
874 69464978919311303554244618
875 72124536297361119510276030
876 74884348895637594010664655
877 77748137788892620098027849
878 80719760041136320318007189
879 83803213599232922045451837
880 87002642359898101612573312
881 90322341416148334015421548
882 93766762489460691106226391
883 97340519554116473484097963
884 101048394660424273321226183
885 104895343963747789011163385
886 108886503966501199125251844
887 113027197980520410066891722
888 117322942817472285530912736
889 121779455715226323183939295
890 126402661508384448429742784
891 131198700051444940285398697
892 136173933903366295041684709
893 141334956282596381874796451
894 146688599301941874260659248
895 152241942492972987473675863
896 158002321629989359680417927
897 163977337863914838247100213
898 170174867176842343274937152
899 176603070168315255960603301
900 183270402184809312230978134
901 190185623804269178845291835
902 197357811687957167015076948
903 204796369812288329221603243
904 212511041093756935848834033
905 220511919420504498845744195
906 228809462104539575054919194
907 237414502769095034600056888
908 246338264686099825472954823
909 255592374579250027194568386
910 265188876908688706073391707
911 275140248653846318707115402
912 285459414611553734525841635
913 296159763227118958594254447
914 307255162976656945075633122
915 318759979319580133024428079
916 330689092240796165428500905
917 343057914402819343632346750
918 355882409928684419213055157
919 369179113837256055521442875
920 382965152153255442940721226
921 397258262715077891946841555
922 412076816704252549764716266
923 427439840921198505488365169
924 443367040832761308049332277
925 459878824417871193958849250
926 476996326838550004491066333
927 494741435964408792109109610
928 513136818779723432912701767
929 532205948703152162376945062
930 551973133851167855223042318
931 572463546277320131748799024
932 593703252220519077300652010
933 615719243396644629785636240
934 638539469368934681768410133
935 662192871033791851632421482
936 686709415259874934866199619
937 712120130719607526305442754
938 738457144953544518444398667
939 765753722709388484337906077
940 794044305598843746894097119
941 823364553116937660874253030
942 853751385069927778473332417
943 885243025459451673212591600
944 917879047872164844135678018
945 951700422425752949036135089
946 986749564323899312930360054
947 1023070384074538966965222771
948 1060708339427538191104327004
949 1099710489089805519342863897
950 1140125548277768331480389241
951 1182003946169140475653550994
952 1225397885317962881975332340
953 1270361403099022940947697401
954 1316950435249951700383697143
955 1365222881581562923231072979
956 1415238673929337054021588769
957 1467059846421368546667834955
958 1520750608140589273046158404
959 1576377418261656395260432620
960 1634009063745552761752643280
961 1693716739677694282089943754
962 1755574132338174631227338556
963 1819657505095705905119453740
964 1886045787219837464178491610
965 1954820665709157216104226565
966 2026066680236403160367121086
967 2099871321314741401976888910
968 2176325131792903398259682818
969 2255521811790423393191207955
970 2337558327187880396679489595
971 2422535021790831365333148025
972 2510555733290027239089953548
973 2601727913144535110970066975
974 2696162750518552099148029125
975 2793975300406993624863665705
976 2895284616089375085392493305
977 3000213886056085786646955649
978 3108890575555882044932760406
979 3221446572918307310269382862
980 3338018340809785874914027977
981 3458747072587338235855821125
982 3583778853919235666960789530
983 3713264829847454369121266660
984 3847361377472511219044687135
985 3986230284447169320651076858
986 4130038933471598140309401591
987 4278960492988866027192977496
988 4433174114286138626029036513
989 4592865135213661512838081433
990 4758225290740525959908624232
991 4929452930573359911781900338
992 5106753244071459083602319514
993 5290338492699482853899412602
994 5480428250266693825296254667
995 5677249651209826305134174599
996 5881037647185035493912157647
997 6092035272243014097445158356
998 6310493916870274882236232890
999 6536673611188795123286163989
1000 6770843317615710978184972695