0 1
1 1
2 1
3 3
4 4
5 6
6 8
7 12
8 18
9 24
10 32
11 45
12 59
13 79
14 104
15 137
16 177
17 229
18 295
19 377
20 477
21 605
22 761
23 956
24 1193
25 1484
26 1840
27 2276
28 2800
29 3441
30 4210
31 5141
32 6261
33 7603
34 9206
35 11132
36 13419
37 16144
38 19380
39 23223
40 27763
41 33134
42 39467
43 46931
44 55703
45 66008
46 78085
47 92239
48 108776
49 128091
50 150617
51 176860
52 207372
53 242842
54 283991
55 331698
56 386934
57 450826
58 524634
59 609843
60 708065
61 821215
62 951419
63 1101113
64 1273021
65 1470310
66 1696482
67 1955566
68 2252070
69 2591132
70 2978521
71 3420809
72 3925306
73 4500361
74 5155329
75 5900759
76 6748477
77 7711887
78 8805930
79 10047490
80 11455468
81 13051091
82 14858142
83 16903357
84 19216538
85 21831198
86 24784780
87 28119153
88 31881094
89 36122980
90 40903166
91 46286885
92 52346878
93 59164255
94 66829440
95 75443225
96 85117703
97 95977803
98 108162496
99 121826234
100 137140780
101 154297067
102 173507028
103 195006017
104 219055279
105 245944508
106 275995057
107 309563095
108 347043170
109 388872377
110 435534748
111 487565695
112 545557824
113 610166422
114 682115924
115 762206858
116 851323808
117 950443289
118 1060643748
119 1183115048
120 1319169959
121 1470256102
122 1637969861
123 1824069899
124 2030494483
125 2259377967
126 2513070636
127 2794158994
128 3105489748
129 3450193374
130 3831713356
131 4253834326
132 4720716225
133 5236928859
134 5807492485
135 6437918037
136 7134256421
137 7903146734
138 8751873639
139 9688425630
140 10721563515
141 11860888704
142 13116925265
143 14501201245
144 16026344771
145 17706182004
146 19555850816
147 21591915563
148 23832503045
149 26297438915
150 29008406643
151 31989110368
152 35265462943
153 38865777365
154 42820989835
155 47164886186
156 51934363244
157 57169698393
158 62914857181
159 69217809542
160 76130894023
161 83711190989
162 92020948670
163 101128024999
164 111106388513
165 122036636819
166 134006586521
167 147111883301
168 161456692110
169 177154417034
170 194328510313
171 213113315226
172 233655017128
173 256112633137
174 280659122479
175 307482550194
176 336787386530
177 368795868308
178 403749521163
179 441910753348
180 483564632020
181 529020752234
182 578615310498
183 632713286797
184 691710868935
185 756038002406
186 826161213634
187 902586591473
188 985863078285
189 1076585945390
190 1175400630617
191 1283006790252
192 1400162763190
193 1527690297762
194 1666479744357
195 1817495555204
196 1981782328115
197 2160471206449
198 2354786896953
199 2566055118284
200 2795710751569
201 3045306492202
202 3316522316244
203 3611175528213
204 3931231737826
205 4278816530500
206 4656228191907
207 5065951240107
208 5510671178760
209 5993290184498
210 6516944185914
211 7085021047172
212 7701180336520
213 8369374376128
214 9093871118834
215 9879278507228
216 10730570918570
217 11653117348998
218 12652711971200
219 13735606706310
220 14908546530325
221 16178807103573
222 17554235519568
223 19043293766481
224 20655105742928
225 22399507407010
226 24287101007285
227 26329312924029
228 28538456170906
229 30927797089689
230 33511627352844
231 36305340800875
232 39325516369541
233 42590006575873
234 46118032950591
235 49930287904832
236 54049044512073
237 58498273692380
238 63303770458098
239 68493288659130
240 74096686065810
241 80146079254035
242 86676010262612
243 93723624508486
244 101328862165663
245 109534662447418
246 118387183232651
247 127936035536997
248 138234535455721
249 149339973120961
250 161313901609789
251 174222445326446
252 188136631114619
253 203132741713920
254 219292695078508
255 236704449268278
256 255462436839778
257 275668028460595
258 297430030101011
259 320865213687585
260 346098885946089
261 373265495473796
262 402509283315039
263 433984977166412
264 467858535066249
265 504307938941986
266 543524044390323
267 585711487338948
268 631089654701852
269 679893719856700
270 732375750845413
271 788805892525387
272 849473631310637
273 914689144153866
274 984784741403348
275 1060116405544413
276 1141065436537596
277 1228040206362328
278 1321478034513685
279 1421847187739580
280 1529649017123468
281 1645420236392330
282 1769735356036296
283 1903209278043668
284 2046500067295937
285 2200311905447903
286 2365398245190550
287 2542565171707017
288 2732674991258236
289 2936650055074340
290 3155476840540103
291 3390210299402944
292 3641978497544913
293 3911987557569093
294 4201526931554897
295 4511975017282222
296 4844805148162299
297 5201591972465179
298 5584018255596379
299 5993882123367290
300 6433104783912505
301 6903738749180875
302 7407976597707701
303 7948160302988059
304 8526791174020780
305 9146540435860047
306 9810260502146355
307 10520996971837319
308 11282001407802416
309 12096744934423968
310 12968932718610544
311 13902519376602366
312 14901725378481565
313 15971054499088238
314 17115312395241767
315 18339626365132073
316 19649466379134366
317 21050667445562658
318 22549453411045556
319 24152462268179465
320 25866773081343573
321 27699934613607184
322 29659995778612361
323 31755538011507465
324 33995709697320978
325 36390262763916738
326 38949591593598196
327 41684774375260184
328 44607617069220450
329 47730700122656225
330 51067428127955644
331 54632082580582286
332 58439877950697026
333 62507021246115250
334 66850775305957624
335 71489526025575521
336 76442853780154722
337 81731609274062951
338 87377994113980704
339 93405646362689731
340 99839731406464547
341 106707038425647176
342 114036082840336263
343 121857215058282563
344 130202735939648564
345 139107019347806990
346 148606642249311175
347 158740522778620465
348 169550066784850720
349 181079323328953619
350 193375149708110105
351 206487386535039809
352 220469043516292510
353 235376496522649251
354 251269696670808266
355 268212392083754454
356 286272363131737543
357 305521671904411199
358 326036926809340667
359 347899563139454108
360 371196140608739040
361 396018658802693140
362 422464891657726517
363 450638742032414495
364 480650617613972468
365 512617829351665785
366 546665013804611647
367 582924580740886518
368 621537187534627288
369 662652241860312104
370 706428434409579742
371 753034303309655615
372 802648832167917235
373 855462083623756933
374 911675870552608259
375 971504467029102333
376 1035175361440966123
377 1102930054110906800
378 1175024902093024305
379 1251732013781721881
380 1333340196304005799
381 1420155958646325912
382 1512504573827153573
383 1610731203413872351
384 1715202088074096828
385 1826305807848772709
386 1944454616256842147
387 2070085852352370564
388 2203663435312492275
389 2345679446157844679
390 2496655801705324054
391 2657146025892169958
392 2827737124148883910
393 3009051566558467338
394 3201749386123695713
395 3406530398543825394
396 3624136550538905548
397 3855354403863814540
398 4101017762844003503
399 4362010453399623366
400 4639269262274239191
401 4933787045349146659
402 5246616014742319381
403 5578871214592092712
404 5931734196313488596
405 6306456904360576266
406 6704365784494465743
407 7126866126847027162
408 7575446657125887009
409 8051684389649577611
410 8557249757049485468
411 9093912031882106195
412 9663545056645940221
413 10268133299169684157
414 10909778251706343469
415 11590705192616257290
416 12313270331011934317
417 13079968355375664280
418 13893440408786945414
419 14756482514128865049
420 15672054474422457563
421 16643289274277904856
422 17673503010393214583
423 18766205379996612919
424 19925110758250554438
425 21154149896733949647
426 22457482277443765565
427 23839509158007398222
428 25304887346336441661
429 26858543744377481763
430 28505690703393376264
431 30251842234820246877
432 32102831123791040985
433 34064826994239300554
434 36144355377827937101
435 38348317841012310306
436 40684013228194398040
437 43159160081249009129
438 45781920299705052324
439 48560924108481262765
440 51505296404457382382
441 54624684556110295722
442 57929287735246699030
443 61429887863171292361
444 65137882258901079495
445 69065318080745728399
446 73224928658350875304
447 77630171816465347553
448 82295270298028790549
449 87235254398833147491
450 92466006932970005697
451 98004310653483281576
452 103867898260277678446
453 110075505133160380293
454 116646924936267559300
455 123603068246628239022
456 130966024368818706209
457 138759126504911978787
458 147007020459022903768
459 155735737063842403086
460 164972768527638562095
461 174747148909212260480
462 185089538940477069681
463 196032315426362342479
464 207609665465111902139
465 219857685743219082971
466 232814487173926887668
467 246520305160634204922
468 261017615782694481297
469 276351258214884630720
470 292568563709553268397
471 309719491485786478613
472 327856771889408190254
473 347036057204642137946
474 367316080519676979216
475 388758823067247308206
476 411429690484866600258
477 435397698460289143636
478 460735668253624623467
479 487520432610735046956
480 515833052610959590053
481 545759046017923161540
482 577388627733403952752
483 610816962982725187535
484 646144433894441762590
485 683476920168625894901
486 722926094565771287516
487 764609733983230107058
488 808652046927536041040
489 855184018229585543804
490 904343771895186061933
491 956276953026178755605
492 1011137129797401938383
493 1069086216521960818221
494 1130294918892270890057
495 1194943202536520983230
496 1263220786090639320059
497 1335327660043480808880
498 1411474632679385372340
499 1491883904505905727769
500 1576789672627489543284
501 1666438766596193091005
502 1761091317350696100363
503 1861021460932461622709
504 1966518078756015613049
505 2077885576295913677380
506 2195444702149779361735
507 2319533409531239549354
508 2450507762352942395829
509 2588742888163983027646
510 2734633980322928192176
511 2888597351902442969799
512 3051071543949886033576
513 3222518490854815136361
514 3403424745715335484450
515 3594302768734692931366
516 3795692281834395102496
517 4008161692823790453952
518 4232309592636121780824
519 4468766329310330256133
520 4718195662584663632631
521 4981296503154513069568
522 5258804740852029973837
523 5551495166210248181146
524 5860183490099650106104
525 6185728466350976871812
526 6529034122525337310595
527 6891052104241202927465
528 7272784138739344877658
529 7675284623640197479372
530 8099663347146110377055
531 8547088346241749910514
532 9018788909772962560795
533 9516058733615199447197
534 10040259235501576719891
535 10592823037444346272890
536 11175257624077471173430
537 11789149185647856115844
538 12436166654815016735533
539 13118065946858433832005
540 13836694413366113609057
541 14593995519960783393786
542 15392013759140444143105
543 16232899809840604491169
544 17118915955896243870253
545 18052441776164387951619
546 19035980119694213146428
547 20072163379971700390662
548 21163760082952420443067
549 22313681804298963835339
550 23524990431992401958739
551 24800905791258882898146
552 26144813649578026518078
553 27560274120386880200547
554 29051030484998289657690
555 30621018453182285867521
556 32274375883851275465161
557 34015452988310029784350
558 35848823039619078115546
559 37779293612739405399661
560 39811918381318348254742
561 41952009498204459086634
562 44205150588085367978481
563 46577210381989356364681
564 49074357024822749957948
565 51703073088591999866438
566 54470171325527566207843
567 57382811196945946561431
568 60448516215404185134661
569 63675192139476261767842
570 67071146062362672350845
571 70645106437490117541146
572 74406244086319347424109
573 78364194235711505508488
574 82529079634460482817923
575 86911534800935232843276
576 91522731456247654234842
577 96374405199921402472534
578 101478883487743094480619
579 106849114974281467559835
580 112498700285522504561296
581 118441924290139732181476
582 124693789941161710935589
583 131270053763161990337419
584 138187263063645968667706
585 145462794950991765433092
586 153114897245186233879069
587 161162731371628953942008
588 169626417332527128745892
589 178527080854817531178170
590 187886902818201616702616
591 197729171071710199676438
592 208078334752300982424315
593 218960061224278099666611
594 230401295763887189780706
595 242430324119223152319015
596 255076838081673506732935
597 268372004211447835593504
598 282348535866399047171537
599 297040768690263738082776
600 312484739723726266275877
601 328718270309281412276205
602 345781052968826968952653
603 363714742441196436057142
604 382563051075539956022967
605 402371848785513979330309
606 423189267778747761039928
607 445065812285951632639317
608 468054473524423231687808
609 492210850141526738797864
610 517593274395075843640673
611 544262944339376228217461
612 572284062298091702448163
613 601723979918021310950992
614 632653350111431565658044
615 665146286208709611603243
616 699280528657913042819681
617 735137619623221178662515
618 772803085850469743328043
619 812366630184806345408693
620 853922332143172467976833
621 897568857962729246525364
622 943409680565639042534522
623 991553309900723424506567
624 1042113534143586819565829
625 1095209672258754434736525
626 1150966838450375835461513
627 1209516219052023241489340
628 1270995362431225202937959
629 1335548482510554378729214
630 1403326776534498995426103
631 1474488757739924451101509
632 1549200603617848486506042
633 1627636520485445344945618
634 1709979125119842817140502
635 1796419844239318117045740
636 1887159332653124142478927
637 1982407910938325729353590
638 2082386023540895050232716
639 2187324718238848206614265
640 2297466147947609127759743
641 2413064095892007508951088
642 2534384525215572604468162
643 2661706154146022849143897
644 2795321057886301148104699
645 2935535298453120506996302
646 3082669583740003583246635
647 3237059957139181322982577
648 3399058519116711225953345
649 3569034182197748693992373
650 3747373460884319281009120
651 3934481298096166024507636
652 4130781929796560924176367
653 4336719789539351327872326
654 4552760454751251405077130
655 4779391636644471959062585
656 5017124215739514838700448
657 5266493325066336731797619
658 5528059483204432726400158
659 5802409779418709111837612
660 6090159113248646394820762
661 6391951491013214744729647
662 6708461381803652591592378
663 7040395135650585490658724
664 7388492466671422823911255
665 7753528004128569877337212
666 8136312914459129596238975
667 8537696597472502470560972
668 8958568460054044463243095
669 9399859770860790275276178
670 9862545599649635364966215
671 10347646845039393579199847
672 10856232354676276628669259
673 11389421141947696135218649
674 11948384703572364954513844
675 12534349442585615167619552
676 13148599201438180165539156
677 13792477910134577421179158
678 14467392354554233197440801
679 15174815070324807986532624
680 15916287367853402426275389
681 16693422494367676988880531
682 17507908939076030474418111
683 18361513887824116414785712
684 19256086833904797700040590
685 20193563351970448809922302
686 21175969042301019063173516
687 22205423652998811639782606
688 23284145388012262586659676
689 24414455409236509612214806
690 25598782541299021699531416
691 26839668188014453441975346
692 28139771469885044607578723
693 29501874592431795948564959
694 30928888455568223436806843
695 32423858514673274356895051
696 33989970904483947473591787
697 35630558837411907788064232
698 37349109288392957283424617
699 39149269978904298547722679
700 41034856673333209915036967
701 43009860801452797302238755
702 45078457421357076840533080
703 47245013537829613203226661
704 49514096791768550973781146
705 51890484536967060159973938
706 54379173321253318071987832
707 56985388789729196231431822
708 59714596028613254052246325
709 62572510368992593089876016
710 65565108670621141104612511
711 68698641106770262007818330
712 71979643472042879104042766
713 75414950036005928787820017
714 79011706966479702919121838
715 82777386347347998281696444
716 86719800816821873451839937
717 90847118853203872666980394
718 95167880736360852774911602
719 99691015214323859347661101
720 104425856905695032308346495
721 109382164469856267507108652
722 114570139578344672768088362
723 120000446722187910915628446
724 125684233891480845825523348
725 131633154165035881129985818
726 137859388249555722764971584
727 144375668009461604947717696
728 151195301030265218498952995
729 158332196260201509019460092
730 165800890776745313804799952
731 173616577726620578712431050
732 181795135489980023239647636
733 190353158121588979760585086
734 199307987124093365264720685
735 208677744610792030770479239
736 218481367917771996589633996
737 228738645727805329934117877
738 239470255771052880260079008
739 250697804170377118835194335
740 262443866501938486429195043
741 274732030644741683124913440
742 287586941495915142648832118
743 301034347631753683505683953
744 315101149997936309858209424
745 329815452715853956170107238
746 345206616095651336036572371
747 361305311950409063457820366
748 378143581309873013901779668
749 395754894636284105644008351
750 414174214649179943930572277
751 433438061870537268814683921
752 453584583006308042274193818
753 474653622285280102961516981
754 496686795881273331003850649
755 519727569549972666758506689
756 543821339617208452828569104
757 569015517461231596925985366
758 595359617637504984799696715
759 622905349800753360856650993
760 651706714585491252286535345
761 681820103612993231477389105
762 713304403799693379271381918
763 746221106149312918079966638
764 780634419218627956067898419
765 816611387454715786962862783
766 854222014609770452744462453
767 893539392448170018388765378
768 934639834969422436429806725
769 977603018379928846469007031
770 1022512127056196928203906724
771 1069454005752228585585704611
772 1118519318314311190843683865
773 1169802713177377266077292800
774 1223402995928480470200473352
775 1279423309234784920521301948
776 1337971320445798192648883119
777 1399159417192416183027058530
778 1463104911318709805940608072
779 1529930251496291271060644527
780 1599763244885572430512047445
781 1672737288223293226477503390
782 1748991608731377282310221735
783 1828671515258489930374522498
784 1911928660082655946309387701
785 1998921311820967822810813014
786 2089814639910807024038033780
787 2184781011146140423871605802
788 2284000298772370635123795462
789 2387660204663944724086036791
790 2495956595130491755750412306
791 2609093850919700896232034817
792 2727285232008501774098417608
793 2850753257798405459970876870
794 2979730103356143812282674524
795 3114458012367048094943311692
796 3255189727495973638663908053
797 3402188938879050221112846167
798 3555730751499159849784583100
799 3716102172228862612980109313
800 3883602617356552667951545809
801 4058544441444981950761783340
802 4241253488405987910397968392
803 4432069665711359302463801812
804 4631347542697323855725819244
805 4839456973959203693495056335
806 5056783748873416037728300776
807 5283730268326262978995576738
808 5520716249772916830226735506
809 5768179461795736990032686991
810 6026576489378617149215123202
811 6296383531163533826208794896
812 6578097230006920793464568892
813 6872235538207010692096315863
814 7179338618828942971730594712
815 7499969784612324429185016931
816 7834716476006129230049732646
817 8184191279938434519722345125
818 8549032990993596469203774521
819 8929907716737182486809970824
820 9327510028999386510185332523
821 9742564163000876479555245149
822 10175825266281162261366306332
823 10628080699468747832253941080
824 11100151391014657873660759024
825 11592893248096534824000101336
826 12107198625989511414608813783
827 12643997858292614625753969833
828 13204260850495683192391396603
829 13788998739471831967742412380
830 14399265621584516570737056693
831 15036160352206402202537857187
832 15700828419559676690530927679
833 16394463895904343710683376531
834 17118311469222555448555309664
835 17873668558673382246337701551
836 18661887517223751039381950685
837 19484377924997816779688786423
838 20342608977028956883101378457
839 21238111969246115923065831475
840 22172482886679587080824585120
841 23147385098030733071590129371
842 24164552160915849808926835143
843 25225790742266613995448835849
844 26332983658548576482630166107
845 27488093040645239303833038689
846 28693163628448650442724352171
847 29950326200398460439733294622
848 31261801143420294405583163583
849 32629902168931418422426509586
850 34057040180807328665090248445
851 35545727301437405859752100588
852 37098581062241489117867576697
853 38718328765272499048931844430
854 40407812022793438657704504727
855 42169991481990617515770980977
856 44007951742269166438931074402
857 45924906472872262545346118840
858 47924203738872384759722750267
859 50009331543901826504264151177
860 52183923598321054735324318278
861 54451765321867816884840075944
862 56816800090187644007778169979
863 59283135735018111746809626341
864 61855051308185422785550731909
865 64537004119973138339597001479
866 67333637062839774850827143671
867 70249786231895112426082337938
868 73290488853995040458461985137
869 76460991537782257597199918365
870 79766758857485801776330759124
871 83213482283796926519110742006
872 86807089475662967041514472341
873 90553753947385323627521843734
874 94459905125973289893932148128
875 98532238814292998581881684436
876 102777728076161065877883302894
877 107203634560166478901840666379
878 111817520279662771803193285065
879 116627259867056533832987649230
880 121641053321228737945823133933
881 126867439267663304048884515308
882 132315308751623740550099465621
883 137993919585514753117766908755
884 143912911272392473203717188513
885 150082320528445637225382583707
886 156512597428161828040196559931
887 163214622196819060735646159196
888 170199722675904834010034788563
889 177479692488063661512337196136
890 185066809929211422127400054040
891 192973857616532114389076176236
892 201214142922191251560718521061
893 209801519223761793452000372913
894 218750408003564776265561647295
895 228075821830379397074802750699
896 237793388258277955015660307724
897 247919374678691601799014231648
898 258470714163215161593348510805
899 269465032336115339802030161829
900 280920675317018445399477941389
901 292856738775823448082958471117
902 305293098143515925629172342044
903 318250440024250536247963593268
904 331750294855826385375786414300
905 345815070867503528009093245766
906 360468089386002342562107092774
907 375733621542493299050539042132
908 391636926435425398870740656595
909 408204290806160155156137629369
910 425463070286577291040536979785
911 443441732280101443574155206996
912 462169900539969171886315692920
913 481678401511015796727664351729
914 501999312503815378504632162146
915 523166011772658038663964304544
916 545213230571600431490696014179
917 568177107265681313927534728404
918 592095243577358698483026722806
919 617006763051302129876182798329
920 642952371823867350537060559967
921 669974421786895443287410623418
922 698116976238918926163380099587
923 727425878120427985740057149240
924 757948820933555873527773616559
925 789735422450388572288623390732
926 822837301318095329998133913214
927 857308156673219058159000165024
928 893203850881764452155751264804
929 930582495526182924306625693943
930 969504540764983017435934342637
931 1010032868195499238820390770409
932 1052232887355337642847118044585
933 1096172636003189819502242537400
934 1141922884325075119095356538340
935 1189557243217641293287598786149
936 1239152276805933681128892700390
937 1290787619359040493614090177235
938 1344546096773244630595057220508
939 1400513852798769262357083168379
940 1458780480192903701966324943434
941 1519439156989246974674698544946
942 1582586788080018176411795472322
943 1648324152315864970210766241863
944 1716756055335364305856615343355
945 1787991488344463153553795517065
946 1862143793074462365611907690393
947 1939330833155814987456909385469
948 2019675172154002873907054329839
949 2103304258523084428759335884737
950 2190350617742183971569190263149
951 2280952051910232639960268110784
952 2375251847084685070740749407054
953 2473398988660739323532234230041
954 2575548385098793811254331442140
955 2681861100319499367756904363283
956 2792504595097822263799921028775
957 2907652977800041068816464602309
958 3027487264820573129203112783601
959 3152195651088982370453487765849
960 3281973791031476727011200300460
961 3417025090385679308506795904533
962 3557561009282471324606754211993
963 3703801377024276725903888810639
964 3855974719005308774597219931145
965 4014318596236048712836645429797
966 4179079957951598149068044827473
967 4350515507801562680213809192150
968 4528892084137808021068696421205
969 4714487054935806152563673982433
970 4907588727905382866197564189675
971 5108496776367516009721563258924
972 5317522681495442721107122432617
973 5534990191540742347476101675840
974 5761235798688298563154306392358
975 5996609234208139876864897701659
976 6241473982597143364779607951175
977 6496207815429494761446686421868
978 6761203345661662384068722679754
979 7036868603165497822959547196659
980 7323627632291958754687983633275
981 7621921112297896250599042579499
982 7932207001499399044843411384856
983 8254961206047380764066128530540
984 8590678274254474408920598935079
985 8939872117436904729735419377170
986 9303076758270887882931742805277
987 9680847107700305360102431841896
988 10073759771470963218765177672557
989 10482413887406727963412137353709
990 10907431994584278075105068100624
991 11349460935606178642956811420798
992 11809172793216530586272050063017
993 12287265862549622932469599990857
994 12784465660349885303638027422835
995 13301525972551059688236214039149
996 13839229941653948787583832282230
997 14398391195395418716315893893721
998 14979855018256604246392073659397
999 15584499567415555884607982892336
1000 16213237134808952428769604092827