0 1
1 1
2 1
3 3
4 3
5 4
6 8
7 9
8 11
9 19
10 22
11 27
12 42
13 49
14 60
15 87
16 102
17 124
18 172
19 202
20 244
21 326
22 383
23 460
24 598
25 702
26 838
27 1066
28 1249
29 1483
30 1854
31 2167
32 2560
33 3154
34 3677
35 4324
36 5264
37 6120
38 7165
39 8633
40 10009
41 11671
42 13939
43 16116
44 18720
45 22188
46 25583
47 29611
48 34862
49 40089
50 46246
51 54124
52 62078
53 71387
54 83108
55 95083
56 109017
57 126314
58 144165
59 164831
60 190166
61 216536
62 246922
63 283765
64 322391
65 366714
66 419930
67 476065
68 540233
69 616604
70 697587
71 789834
72 898770
73 1014795
74 1146532
75 1301014
76 1466167
77 1653130
78 1870989
79 2104637
80 2368412
81 2674025
82 3002665
83 3372733
84 3799282
85 4259003
86 4775443
87 5367903
88 6007643
89 6724713
90 7543809
91 8429655
92 9420507
93 10547896
94 11768737
95 13131620
96 14676718
97 16351661
98 18218025
99 20326910
100 22614965
101 25160067
102 28027098
103 31139804
104 34596491
105 38479407
106 42697237
107 47373851
108 52613357
109 58306973
110 64610523
111 71655591
112 79313313
113 87779399
114 97219932
115 107483149
116 118814485
117 131423308
118 145131997
119 160247925
120 177034692
121 195285818
122 215385737
123 237665936
124 261888175
125 288532665
126 318015797
127 350064940
128 385279239
129 424181166
130 466461658
131 512867411
132 564053305
133 619672750
134 680655331
135 747821069
136 820786222
137 900706889
138 988608840
139 1084073745
140 1188538005
141 1303283512
142 1427863020
143 1564059509
144 1713473431
145 1875638578
146 2052766136
147 2246852408
148 2457428090
149 2687233019
150 2938754949
151 3211545246
152 3508995899
153 3834204293
154 4186776748
155 4570909177
156 4990454491
157 5445122100
158 5940098189
159 6480171201
160 7065219850
161 7701649239
162 8395405221
163 9146625404
164 9963214176
165 10852548023
166 11815143212
167 12860746925
168 13998502425
169 15229462980
170 16565639123
171 18018354128
172 19589405756
173 21293582438
174 23144894923
175 25146155305
176 27315558949
177 29670426749
178 32214933720
179 34971450612
180 37961371793
181 41190682810
182 44686867876
183 48476329711
184 52567436303
185 56993929585
186 61788364575
187 66962218886
188 72556886862
189 78612474401
190 85144489472
191 92203677540
192 99839403591
193 108072367285
194 116964732580
195 126577208142
196 136937144955
197 148120639598
198 160202286023
199 173217915031
200 187260610950
201 202421949003
202 218748523611
203 236354116506
204 255351052113
205 275799532809
206 297838538672
207 321605725036
208 347178435421
209 374726305152
210 404417886615
211 436352042563
212 470735674286
213 507774987475
214 547595776605
215 590450211296
216 636590344161
217 686175577896
218 739513030024
219 796910528166
220 858569302089
221 924863116498
222 996167593293
223 1072735886750
224 1155022538324
225 1243485502744
226 1338442241048
227 1440445123171
228 1550052007323
229 1667659818336
230 1793939317062
231 1929569482464
232 2075045225140
233 2231180473982
234 2398800927867
235 2578522079987
236 2771330860407
237 2978230548075
238 3199984744032
239 3437789273230
240 3692862166262
241 3966148609912
242 4259096477027
243 4573183287033
244 4909576471448
245 5270027792773
246 5656328057841
247 6069916254453
248 6512910268249
249 6987478836840
250 7495392229210
251 8039209107125
252 8621553751092
253 9244599954216
254 9911436639521
255 10625236739196
256 11388664845481
257 12205447328211
258 13079417383243
259 14013835708010
260 15013194412945
261 16082120646059
262 17224598122109
263 18446038140251
264 19752021808701
265 21147408635253
266 22638712510363
267 24232659865873
268 25935169707661
269 27754077565769
270 29697483886068
271 31772587828745
272 33988808000429
273 36355891954944
274 38882583767523
275 41580196930684
276 44460451983838
277 47533955271187
278 50814286799020
279 54315528671133
280 58050529514205
281 62035578464516
282 66287582197812
283 70822086223513
284 75658615610857
285 80817452904280
286 86317383803767
287 92181795887175
288 98435003522536
289 105099681320352
290 112203824108894
291 119776558012123
292 127845220430390
293 136443298042838
294 145605655425682
295 155365215132716
296 165762005720612
297 176837730537233
298 188631995669770
299 201192617121466
300 214569442592478
301 228810068573674
302 243971575077592
303 260113502244585
304 277292990605718
305 295578133446208
306 315039997760824
307 335747113605910
308 357780658539906
309 381225398673490
310 406163443986391
311 432691506667258
312 460910622591082
313 490919079387341
314 522832021252846
315 556769793957058
316 592849941200923
317 631209463002913
318 671991608077844
319 715336821498540
320 761408002504226
321 810375546597829
322 862407113576379
323 917696274083917
324 976445579777017
325 1038855005275565
326 1105154421538159
327 1175584445681359
328 1250383393157824
329 1329824070689793
330 1414192127494805
331 1503771334841703
332 1598885252533309
333 1699872770057278
334 1807071509405408
335 1920864987721933
336 2041654999895939
337 2169842916943930
338 2305883044294543
339 2450251456168978
340 2603424935683586
341 2765941314285385
342 2938364322486003
343 3121259888886259
344 3315264342578264
345 3521044793920283
346 3739272477642979
347 3970699807778262
348 4216115745657387
349 4476315836825228
350 4752189228569993
351 5044668419610330
352 5354695601391983
353 5683320883048314
354 6031645747673555
355 6400785265354506
356 6791978921026524
357 7206527025113023
358 7645748317966939
359 8111104964425578
360 8604131081165083
361 9126385199679798
362 9679591179411986
363 10265557919588658
364 10886126090008478
365 11543326924680624
366 12239292081272427
367 12976193985321860
368 13756424700877664
369 14582494784996208
370 15456966521038958
371 16382655324652613
372 17362516312930559
373 18399569625644600
374 19497127117139069
375 20658665218645969
376 21887741462048068
377 23188249534335694
378 24564276855858596
379 26020011328901822
380 27560028195103317
381 29189130580755959
382 30912245391440603
383 32734745818482377
384 34662272913289884
385 36700619438830923
386 38856092323556279
387 41135313118559621
388 43545088496066899
389 46092817453539256
390 48786268278407038
391 51633434252211124
392 54642990969655686
393 57824047183934790
394 61185984131907575
395 64738968959206132
396 68493676542704840
397 72461110696305787
398 76653180391037586
399 81082389347838419
400 85761637214326436
401 90704866046163874
402 95926714130707458
403 101442295041671843
404 107267922713794534
405 113420725593557168
406 119918401280044397
407 126780029489022770
408 134025642228191880
409 141675951517934229
410 149753260614303900
411 158280985470304419
412 167283352798758941
413 176786421118605249
414 186817548287513689
415 197405056919967548
416 208579378151244177
417 220372459507106225
418 232817394422613318
419 245949703098289877
420 259806674406308033
421 274426955968869855
422 289851988128060065
423 306125272971379164
424 323291921122171158
425 341400256677115157
426 360501005763493337
427 380646795867679718
428 401893951632776221
429 424301594631808887
430 447931090713500330
431 472848058820133345
432 499121372871019275
433 526822552237666891
434 556028008264028506
435 586817938299033658
436 619275654026160805
437 653490093173062848
438 689554594806601029
439 727566159835409064
440 767628258514936602
441 809849475119103172
442 854342694509866111
443 901228239511861463
444 950632371997390965
445 1002686398975983450
446 1057530177768819212
447 1115310459384218855
448 1176179907125094490
449 1240301011780290746
450 1307844261922156088
451 1378987067563808112
452 1453918132350266249
453 1532835434074391825
454 1615945045443200511
455 1703466015549347420
456 1795628142473422108
457 1892670682744424715
458 1994847800260873083
459 2102426111323306627
460 2215683273905156039
461 2334914068738101880
462 2460427695496489118
463 2592546232539434579
464 2731611422150000509
465 2877981694871704987
466 3032030489950954558
467 3194153824805153812
468 3364767022690304128
469 3544302883677075014
470 3733220127409225296
471 3931999797361410718
472 4141143271837355247
473 4361181679067001428
474 4592671949297718425
475 4836194655027043858
476 5092364508586092556
477 5361826031199949558
478 5645251211481780391
479 5943351207984888984
480 6256871602176158095
481 6586589864148523748
482 6933328396332175639
483 7297949335058325178
484 7681351812523363882
485 8084486493083914961
486 8508349885760238549
487 8953981391743602851
488 9422479501630197214
489 9914995578841490913
490 10432730682448538849
491 10976953612515131018
492 11548994122018635617
493 12150239505520540901
494 12782154700699833498
495 13446274883970219301
496 14144201816613014651
497 14877626233821353382
498 15648319776862865161
499 16458131089776654081
500 17309010753077501818
501 18203002503049690177
502 19142239074072962252
503 20128969962842608804
504 21165551883251964732
505 22254444351944517971
506 23398240600812344975
507 24599657213994487136
508 25861529457460068733
509 27186845693011864203
510 28578736142270431834
511 30040467965099400614
512 31575483567761241515
513 33187388437462416067
514 34879945979379410398
515 36657120155433141208
516 38523062332145062572
517 40482105892075726424
518 42538813688395769024
519 44697963848573071466
520 46964544183384512216
521 49343804996613935840
522 51841243787604779453
523 54462599489869068280
524 57213911235446969671
525 60101501900792502364
526 63131972217633478390
527 66312266158463044798
528 69649653272782893627
529 73151722725553095078
530 76826456044710292945
531 80682208198712369024
532 84727701632990087520
533 88972107203141910770
534 93425023950285041727
535 98096473223762431618
536 102996988715688614144
537 108137594898138566134
538 113529801341410259143
539 119185702867934021024
540 125117956625198790206
541 131339776733621462117
542 137865045691647223636
543 144708290070958110651
544 151884675657027026670
545 159410131363823514764
546 167301323553775691150
547 175575651868041472261
548 184251387050035941341
549 193347643912406022421
550 202884378093678998441
551 212882539346450662147
552 223364043197952466516
553 234351768915887519498
554 245869729991352648741
555 257943044569201283131
556 270597934959518152740
557 283861917239186681134
558 297763770564063685693
559 312333538624779007934
560 327602740506522908786
561 343604339038068045349
562 360372744662664632091
563 377944049935584557585
564 396355997116418302983
565 415647985009197893949
566 435861329744251398949
567 457039231881303160871
568 479226786869218825114
569 502471275055866370981
570 526822128641885262931
571 552330946521454044362
572 579051816794543388909
573 607041283996539949235
574 636358369209280559107
575 667064928718131132331
576 699225622042948076262
577 732907938355679067982
578 768182595334356793393
579 805123508638429457894
580 843807825838189634219
581 884316369973767170712
582 926733611255253201114
583 971147709903138094728
584 1017651009427998078115
585 1066340011496026746893
586 1117315429301998348259
587 1170682736150445719074
588 1226552144613559410546
589 1285038672312858181722
590 1346262752011802197025
591 1410350216409342859858
592 1477432378497908463688
593 1547646710077886236190
594 1621136833780746680363
595 1698052620504149535088
596 1778550944038696674047
597 1862795682204442041684
598 1950957834244556274980
599 2043216360123266224182
600 2139758192994288294773
601 2240778379868960694543
602 2346481015111448935885
603 2457079266843548655632
604 2572795544698733073611
605 2693862538117778355094
606 2820523259738659093344
607 2953031244612728886179
608 3091651705103455057474
609 3236661594820916338517
610 3388349844319549596272
611 3547018645738666942515
612 3712983541427575112548
613 3886573701876374674692
614 4068133354724951748677
615 4258021902897396491412
616 4456614251349952566608
617 4664302396732602213153
618 4881495580622053973981
619 5108620672617320508567
620 5346123938784209292489
621 5594471236457997678128
622 5854148462292151668039
623 6125663519672569699944
624 6409546562569212228377
625 6706350518363928945590
626 7016653276712222431849
627 7341057991074536398733
628 7680193687533911332792
629 8034717700135130377375
630 8405316040040263700698
631 8792704103117169555494
632 9197629379629011869900
633 9620871902456628576356
634 10063245068018642067420
635 10525598651351764061014
636 11008819346548978750710
637 11513831717588110865492
638 12041601553372127052224
639 12593136515474469782656
640 13169487237735583575485
641 13771751059763885608863
642 14401072799288796181710
643 15058646021967923207593
644 15745717196229525553273
645 16463586610044701397794
646 17213609835309857126662
647 17997202351791593898499
648 18815840630981350535151
649 19671063822721320662118
650 20564478901449873015224
651 21497761943038819361419
652 22472660065064249112042
653 23490997154608475171345
654 24554675367651627831578
655 25665677358606006860890
656 26826072655680005864151
657 28038019416557701564275
658 29303766987576944010186
659 30625663000180703687327
660 32006155421333419594988
661 33447795488097217163772
662 34953245607074579630296
663 36525281743348861208352
664 38166796782276070415289
665 39880809323157628710966
666 41670466456533732592159
667 43539047611845651746313
668 45489974346977674651584
669 47526813570564698823932
670 49653281941887900927787
671 51873256769512241752627
672 54190779742993413341820
673 56610061960055543220228
674 59135496060460088757483
675 61771660540223852296566
676 64523325490911516323001
677 67395466109253990316142
678 70393267676843980878709
679 73522132107393501175199
680 76787692988642402083366
681 80195821321621501867019
682 83752632984126796586846
683 87464505479308661599361
684 91338084541142330820847
685 95380292636325410729694
686 99598347613822851744979
687 103999770297337122161325
688 108592394163532986333320
689 113384386108964087029121
690 118384255166288186855333
691 123600863514374678045055
692 129043449603712885878730
693 134721638151092636869139
694 140645452656992378018756
695 146825341158053564663948
696 153272187675191393824561
697 159997326435959475083576
698 167012570553287670101905
699 174330225124779463988962
700 181963103382798830703044
701 189924558632765333770478
702 198228499227043620473139
703 206889406893630281262110
704 215922372305274522209485
705 225343112180218759030161
706 235167990071947549663122
707 245414055982693715388844
708 256099065875735121696215
709 267241505244117144613790
710 278860633229201088163176
711 290976504865694873932264
712 303609997787036241464754
713 316782861362085845417024
714 330517742035053681745164
715 344838213569847379242994
716 359768831776410536868333
717 375335163353744140593123
718 391563820125557881234026
719 408482519992776866605495
720 426120119739553302556413
721 444506653768650553070222
722 463673401989035273516691
723 483652927102805193729986
724 504479118411601772970588
725 526187267428800502065703
726 548814110230400431233197
727 572397876974200730477222
728 596978376115822604207012
729 622597042479657658314311
730 649296993211447614757970
731 677123121577243176790832
732 706122151492431512552506
733 736342700716720565788359
734 767835385326303875267093
735 800652881530831203438061
736 834849997018727301636650
737 870483787316554669926876
738 907613625826725575834023
739 946301284341814793540140
740 986611062642803089114717
741 1028609867805658181843232
742 1072367305027208237084003
743 1117955821967172425789987
744 1165450798500917317014856
745 1214930649138076304337120
746 1266476983783768498240506
747 1320174709259486910548580
748 1376112144750686861591979
749 1434381200852291973495830
750 1495077494341598110031558
751 1558300478264413791459322
752 1624153641340997198601643
753 1692744637656078222189542
754 1764185433186934642082245
755 1838592527880679023467279
756 1916087102129252784562635
757 1996795181759422053809146
758 2080847885353483413824370
759 2168381589603865894601612
760 2259538115027055396968584
761 2354465001390250470622178
762 2453315694293801146306232
763 2556249754141442294313027
764 2663433162858465640508003
765 2775038534333723696099290
766 2891245349480521196651680
767 3012240297791096785376775
768 3138217514586770992442745
769 3269378845341027236704573
770 3405934226014533245973435
771 3548101950416047478384495
772 3696108967335639119279413
773 3850191304048583534396244
774 4010594367485126416194148
775 4177573278141918299967728
776 4351393341636837092346479
777 4532330387827387138690845
778 4720671145937230533162582
779 4916713769592811640920758
780 5120768218523314376126089
781 5333156679862187357971984
782 5554214152706459197512808
783 5784288877581656698643036
784 6023742809461586706157970
785 6272952268569190647404973
786 6532308423404158967958189
787 6802217821674775251609022
788 7083103114812554734306548
789 7375403601045722278563365
790 7679575821162227412555619
791 7996094365047550994463052
792 8325452482051797372405009
793 8668162749311475786442713
794 9024757969549952622087602
795 9395791856838588681329112
796 9781839786105907679098362
797 10183499792473430056069003
798 10601393341462000012857182
799 11036166169320912866315063
800 11488489395319609911623919
801 11959060386510122182879826
802 12448603699627136878231855
803 12957872319030807926569346
804 13487648627317347288766496
805 14038745460786676422553560
806 14612007487147318843516914
807 15208312294583197838621300
808 15828571574172647176543706
809 16473732653038408112303080
810 17144779715944742945453210
811 17842735129595931838357942
812 18568661148659869028846000
813 19323661285602430073104599
814 20108881793512645064000045
815 20925513564366189693876805
816 21774793664622141192949733
817 22658006995135188538763323
818 23576488403176392449057250
819 24531624403341654869351989
820 25524855035240114699157074
821 26557676213177108725131692
822 27631641654176737208217995
823 28748364956503851196661422
824 29909522213563877702575880
825 31116854173349157249471668
826 32372168563486099571701115
827 33677342998846890796292390
828 35034327399518934791980539
829 36445146590998149866435648
830 37911903538270050640688100
831 39436782052504824805345236
832 41022049698274850306851453
833 42670061390482106761212167
834 44383262423432723650200020
835 46164191720577613324643472
836 48015485834678207931809756
837 49939882336752024656249470
838 51940223447859717617050426
839 54019460487354465547840731
840 56180657663456651984164321
841 58426996131082818966523843
842 60761778937962907943733116
843 63188435263344561532929129
844 65710524950828346397027849
845 68331744007613763687131062
846 71055929343104018789042599
847 73887063831231657272925569
848 76829282424166656783082699
849 79886877448448452913997630
850 83064304257416797908435447
851 86366188027447307108227383
852 89797329675742930859679972
853 93362712170292819988495872
854 97067508084163191715040695
855 100917086206305996887579156
856 104917018584027376574127239
857 109073088919132889420239226
858 113391299951135097628856045
859 117877881315604186610955995
860 122539298875132984156722061
861 127382262963234188418117185
862 132413737151258925701554950
863 137640948617304250891296776
864 143071397348980607699942785
865 148712865921919121448082479
866 154573431020998143123247093
867 160661473711138305245626188
868 166985690341886366241067987
869 173555105347804722394842795
870 180379082708632404790062870
871 187467338107154169831276760
872 194829953149406916421389881
873 202477388149059903899785680
874 210420495679887278403438806
875 218670536371740719846818971
876 227239193168994528466228587
877 236138586434586889740798902
878 245381291494646524510424295
879 254980354537476741163809371
880 264949309443480195744725804
881 275302197270083027229811804
882 286053583976171896432109517
883 297218579171450869815369500
884 308812857754071904439675382
885 320852679665884168279459390
886 333354910776091196050205521
887 346337046906984151626432770
888 359817235848027620071358656
889 373814300612312716121518123
890 388347766111233964597509806
891 403437883680557052275524660
892 419105656974344797894436635
893 435372871577578861708886707
894 452262122325194258883709327
895 469796842127161431866851401
896 488001334839216386258748547
897 506900805686693105069878786
898 526521393346576182692384911
899 546890206430983155100686792
900 568035357361798541061628964
901 589985998071098678070748788
902 612772360490176494023214011
903 636425794258832286531321523
904 660978806444981129510996990
905 686465106474207747427680513
906 712919648099488622871214297
907 740378673584426249937864831
908 768879763554994537120315481
909 798461883701884216174645940
910 829165433920112881219779426
911 861032303616237725521651788
912 894105923666905983935850354
913 928431321061056924676187065
914 964055180252955294120340070
915 1001025900957414361860483668
916 1039393658899978590410790484
917 1079210473869237721788513642
918 1120530273992149863823847416
919 1163408963263070367763274281
920 1207904497018571473112480910
921 1254076953405964516462873936
922 1301988608434482382644294182
923 1351704019672946040587237448
924 1403290105701671981770425924
925 1456816229509251421117955123
926 1512354291298637036138973372
927 1569978816797900326649758140
928 1629767049914684550346905016
929 1691799055630474963280821754
930 1756157818139997041318123169
931 1822929343773438657184953917
932 1892202775062743780162074328
933 1964070499783760549178746167
934 2038628265264709211513510755
935 2115975304823326164768420232
936 2196214458901221797517714341
937 2279452301996892263071565611
938 2365799282799566015948523943
939 2455369858732762950694654588
940 2548282636882598618183144843
941 2644660529294492101344057361
942 2744630902383895605271230855
943 2848325733377029201307122949
944 2955881782391566638739582368
945 3067440758328322837000029316
946 3183149492503329382839322102
947 3303160129304732579032708772
948 3427630310351422293861076810
949 3556723367174104159950839736
950 3690608532429583924014016924
951 3829461144302588521027083987
952 3973462860290963130896003161
953 4122801891167108369319749645
954 4277673227809449365727049541
955 4438278878365015645917101743
956 4604828127378058943339031236
957 4777537787469824227084084248
958 4956632462392684976096101231
959 5142344834000119345408528160
960 5334915941449892912609292761
961 5534595472929964135255829578
962 5741642083424479461657630447
963 5956323704398684932232711812
964 6178917867270566502695419188
965 6409712055237031183781909706
966 6649004046711569830623833680
967 6897102273939895447729136242
968 7154326212491969388935532731
969 7421006762068664518455057843
970 7697486644017639278935056117
971 7984120832473605185315159320
972 8281276976531317031584830139
973 8589335840813014418396174398
974 8908691782654896580368288637
975 9239753220064358915186454139
976 9582943119926336489186444484
977 9938699526092301981780964700
978 10307476078003808780361064962
979 10689742551606153378759005734
980 11085985443701684835847084018
981 11496708546633842590126423036
982 11922433547507306045185988998
983 12363700674724777030544601934
984 12821069334690699365573328152
985 13295118775522533846419921210
986 13786448802304703938337044086
987 14295680482394427449467589720
988 14823456880454498747695407588
989 15370443849635552098997834155
990 15937330812753834867185316877
991 16524831576188006708404451340
992 17133685204947630642693380947
993 17764656887750774034236073525
994 18418538838112567516577793331
995 19096151262080869972753992916
996 19798343316077449174877610381
997 20525994104371772253305685682
998 21280013749171791200138603165
999 22061344451013993199990549290
1000 22870961592770246563291141367