0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 21
9 30
10 41
11 55
12 75
13 99
14 131
15 172
16 223
17 288
18 372
19 474
20 603
21 764
22 962
23 1206
24 1509
25 1876
26 2326
27 2878
28 3543
29 4351
30 5330
31 6506
32 7921
33 9623
34 11655
35 14085
36 16987
37 20434
38 24529
39 29392
40 35138
41 41930
42 49947
43 59381
44 70474
45 83512
46 98779
47 116662
48 137572
49 161979
50 190433
51 223588
52 262123
53 306902
54 358865
55 419077
56 488775
57 569402
58 662501
59 769952
60 893820
61 1036455
62 1200542
63 1389185
64 1605745
65 1854226
66 2139035
67 2465191
68 2838360
69 3265046
70 3752368
71 4308627
72 4943015
73 5665924
74 6489060
75 7425729
76 8490595
77 9700511
78 11074165
79 12632623
80 14399489
81 16401448
82 18667970
83 21232604
84 24132555
85 27409602
86 31110391
87 35287392
88 39998630
89 45309631
90 51293052
91 58030148
92 65611447
93 74138264
94 83722703
95 94490546
96 106581163
97 120149923
98 135369444
99 152432219
100 171551061
101 192963651
102 216932990
103 243751387
104 273742855
105 307267503
106 344723092
107 386552056
108 433243277
109 485338596
110 543437378
111 608203768
112 680370477
113 760749705
114 850237569
115 949824802
116 1060605054
117 1183787083
118 1320702460
119 1472823077
120 1641770192
121 1829332247
122 2037479620
123 2268384985
124 2524438260
125 2808274467
126 3122791414
127 3471178982
128 3856945215
129 4283950047
130 4756432957
131 5279057682
132 5856944927
133 6495720641
134 7201561133
135 7981249055
136 8842222651
137 9792648096
138 10841477627
139 11998529188
140 13274563277
141 14681375537
142 16231882603
143 17940238845
144 19821937788
145 21893942504
146 24174815565
147 26684871005
148 29446321267
149 32483465793
150 35822864213
151 39493549511
152 43527244716
153 47958611636
154 52825498144
155 58169242775
156 64034965586
157 70471915172
158 77533826467
159 85279325791
160 93772341851
161 103082595958
162 113286084867
163 124465642212
164 136711524967
165 150122068599
166 164804363102
167 180875039286
168 198461061134
169 217700630247
170 238744138086
171 261755220904
172 286911860048
173 314407638923
174 344453030262
175 377276845376
176 413127768970
177 452276048002
178 495015267495
179 541664350599
180 592569632472
181 648107169567
182 708685196721
183 774746814922
184 846772835558
185 925284947968
186 1010849034693
187 1104078831958
188 1205639835853
189 1316253557932
190 1436702046435
191 1567832880676
192 1710564431577
193 1865891633540
194 2034892155886
195 2218733103677
196 2418678158132
197 2636095411964
198 2872465662831
199 3129391466042
200 3408606827828
201 3711987699988
202 4041563186926
203 4399527778790
204 4788254345800
205 5210308264407
206 5668462555021
207 6165714235175
208 6705301804746
209 7290724255964
210 7925761313097
211 8614495366307
212 9361334983976
213 10171040266636
214 11048749978097
215 12000010944560
216 13030809409234
217 14147604921104
218 15357366668034
219 16667612592741
220 18086451269838
221 19622627161598
222 21285568937626
223 23085441587204
224 25033202284056
225 27140660450354
226 29420542068612
227 31886559031959
228 34553483236180
229 37437226346935
230 40554925285928
231 43925034037914
232 47567421943604
233 51503479498340
234 55756231425968
235 60350458226332
236 65312826392135
237 70672028106676
238 76458930781389
239 82706737761667
240 89451160103234
241 96730600980149
242 104586353156192
243 113062810639350
244 122207695170137
245 132072299303777
246 142711746217552
247 154185268307687
248 166556505370506
249 179893823933187
250 194270658827183
251 209765879361998
252 226464180618309
253 244456502612413
254 263840478692045
255 284720915357418
256 307210305276651
257 331429376681410
258 357507680282153
259 385584217416727
260 415808111630975
261 448339326807871
262 483349434600034
263 521022435531601
264 561555635856984
265 605160585248096
266 652064078749784
267 702509227452575
268 756756602088440
269 815085455578900
270 877795028070872
271 945205941436318
272 1017661688510424
273 1095530223429016
274 1179205659401319
275 1269110082294930
276 1365695485739755
277 1469445837418303
278 1580879284486664
279 1700550507261536
280 1829053230576332
281 1967022904541414
282 2115139563600104
283 2274130877378746
284 2444775405137324
285 2627906066951394
286 2824413845460065
287 3035251734675371
288 3261438949426002
289 3504065414348988
290 3764296549821001
291 4043378373688071
292 4342642939005340
293 4663514131042322
294 5007513843932485
295 5376268563560322
296 5771516382090515
297 6195114471224671
298 6649047043500641
299 7135433834519738
300 7656539136276796
301 8214781419102199
302 8812743579059889
303 9453183849658433
304 10139047420174310
305 10873478807121397
306 11659835023138174
307 12501699596232422
308 13402897492556186
309 14367510998330944
310 15399896621694588
311 16504703080339958
312 17686890439362567
313 18951750474093597
314 20304928334266916
315 21752445589003034
316 23300724739536803
317 24956615292938439
318 26727421489891977
319 28620931792180922
320 30645450239020344
321 32809829785582005
322 35123507747599675
323 37596543483951783
324 40239658450943157
325 43064278777424339
326 46082580516229166
327 49307537733137559
328 52752973609383928
329 56433614744054460
330 60365148847557311
331 64564286036519753
332 69048823950818460
333 73837716921513047
334 78951149438968988
335 84410614184109280
336 90238994894910105
337 96460654364496316
338 103101527883136292
339 110189222447991234
340 117753122092669817
341 125824499706995250
342 134436635732830105
343 143624944152807053
344 153427106212649371
345 163883212334336162
346 175035912716030640
347 186930577139611062
348 199615464531006051
349 213141902858712224
350 227564479990596891
351 242941246153069691
352 259333928689355212
353 276808159847928454
354 295433718368956655
355 315284785689363538
356 336440217636827438
357 358983832517728176
358 383004716575561669
359 408597547843909752
360 435862939472212558
361 464907803672518318
362 495845737505744543
363 528797431775967786
364 563891104398283367
365 601262959671869362
366 641057674968214130
367 683428916437882399
368 728539885437842216
369 776563897453233288
370 827684995418718894
371 882098599436819871
372 940012195002121764
373 1001646061966061626
374 1067234046614203567
375 1137024379330788168
376 1211280540502761069
377 1290282177444242171
378 1374326075279616138
379 1463727184893576491
380 1558819711246372863
381 1659958265498947022
382 1767519084632372928
383 1881901322425550547
384 2003528415875040744
385 2132849531371901835
386 2270341095212044155
387 2416508413224176924
388 2571887384622964990
389 2737046315445258881
390 2912587837232705677
391 3099150936938638967
392 3297413104396123059
393 3508092603976916217
394 3731950877507569187
395 3969795085856924738
396 4222480797031499350
397 4490914829044102070
398 4776058256312325467
399 5078929588754696769
400 5400608133340985753
401 5742237548336083850
402 6105029601057998575
403 6490268140555695292
404 6899313297283020544
405 7333605922419769903
406 7794672280284534966
407 8284129007952623520
408 8803688356989086676
409 9355163733005724447
410 9940475549663803441
411 10561657414544697032
412 11220862665379928960
413 11920371276055517894
414 12662597152894743692
415 13450095842813211309
416 14285572676180873296
417 15171891368335646775
418 16112083105133752225
419 17109356139193639966
420 18167105924975519897
421 19288925822324121644
422 20478618399785649161
423 21740207370543732118
424 23077950195758540187
425 24496351391840482284
426 26000176580209852623
427 27594467320117213956
428 29284556767379193235
429 31076086203996752853
430 32975022486232646476
431 34987676461119159896
432 37120722404108932751
433 39381218533333848607
434 41776628659020590583
435 44314845029510803129
436 47004212438843829559
437 49853553664132686873
438 52872196304678253120
439 56070001098504880664
440 59457391796165149731
441 63045386675629374094
442 66845631786792974821
443 70870436018597730901
444 75132808086785385703
445 79646495545372407423
446 84426025930551070405
447 89486750151136898407
448 94844888246018484090
449 100517577635137199029
450 106522923997304522351
451 112880054915030615797
452 119609176434102485823
453 126731632693019394493
454 134269968785896782287
455 142247997030690832734
456 150690866823734515895
457 159625138270858254343
458 169078859795543836685
459 179081649934564526955
460 189664783542967008694
461 200861282641412526158
462 212706012151192535830
463 225235780774763470509
464 238489447293314455224
465 252508032566430983012
466 267334837534194304053
467 283015567537142026974
468 299598463286040744752
469 317134438830305202756
470 335677226892238196035
471 355283531952573365109
472 376013191493251338219
473 397929345823707438866
474 421098616939123036630
475 445591296881806842444
476 471481546101446863777
477 498847602334659089908
478 527772000551601972648
479 558341804544818284221
480 590648850765176170808
481 624790005040290692305
482 660867432843693471813
483 698988883816234292803
484 739267991277723616647
485 781824587503631572564
486 826785035581412523772
487 874282578701937581312
488 924457707785472358669
489 977458548386243960690
490 1033441267868381119512
491 1092570503895377282689
492 1155019815328345761746
493 1220972156683114231235
494 1290620377354880236755
495 1364167746878940628442
496 1441828507560976177625
497 1523828455876468016305
498 1610405554109704879432
499 1701810573776068529266
500 1798307772449508390929
501 1900175605697117087052
502 2007707475909222631680
503 2121212519901756805785
504 2241016437262119380566
505 2367462361507499895291
506 2500911776228775361918
507 2641745478499955982706
508 2790364591948200693613
509 2947191631997310500750
510 3112671625923322717105
511 3287273290491095188386
512 3471490270079282316652
513 3665842438343586987590
514 3870877266621011741895
515 4087171262434889964554
516 4315331481627570736704
517 4555997117820988070078
518 4809841173089315850284
519 5077572213917593271154
520 5359936216723012304419
521 5657718507424478317083
522 5971745799767858876351
523 6302888337344703054105
524 6652062144486258331403
525 7020231391466736234820
526 7408410879718576619691
527 7817668653039946898107
528 8249128741068766100057
529 8703974041603234580169
530 9183449348672184900487
531 9688864533593180217912
532 10221597886612133023014
533 10783099627086233252061
534 11374895590561318042254
535 11998591101499894224602
536 12655875040843883166658
537 13348524118039586079359
538 14078407357622900707900
539 14847490810950200697726
540 15657842504175156697024
541 16511637634107822445224
542 17411164024157790354389
543 18358827853150009055275
544 19357159670423310091183
545 20408820711266245268497
546 21516609527424854657499
547 22683468948125383362092
548 23912493387801429155532
549 25206936517490411288718
550 26570219317684073730887
551 28005938531268986141900
552 29517875536090045361754
553 31110005657604915310546
554 32786507943081526156619
555 34551775419814011857486
556 36410425860912715381627
557 38367313083346612878414
558 40427538804098393663185
559 42596465081524746462420
560 44879727370310460960628
561 47283248219753477726354
562 49813251646539774448950
563 52476278214645802065969
564 55279200856561495882283
565 58229241471649096794562
566 61333988339157760991500
567 64601414385188797077359
568 68039896344775428086747
569 71658234862186352250370
570 75465675574606665224347
571 79471931226482500351452
572 83687204864055409772225
573 88122214161945503116687
574 92788216936096631300057
575 97697037899952793384122
576 102861096723418784067786
577 108293437456958722405949
578 114007759386125127245247
579 120018449384873995540518
580 126340615839240386097980
581 132990124216302855975434
582 139983634356884471697624
583 147338639574111224345139
584 155073507643801005717909
585 163207523776672234889179
586 171760935666578582580141
587 180755000713371816783901
588 190212035523604512966854
589 200155467797096023317437
590 210609890712428789039457
591 221601119929701410423908
592 233156253334383967322774
593 245303733651875079277084
594 258073414068391198040456
595 271496627000114323610924
596 285606256159120386891338
597 300436812071490069593958
598 316024511210218393119276
599 332407358913062788266268
600 349625236263350989253987
601 367719991119998032097865
602 386735533491598225109665
603 406717935458446308507498
604 427715535855762538430460
605 449779049941221928348819
606 472961684280176560007406
607 497319257092700827375219
608 522910324317833127723722
609 549796311662117641229843
610 578041652911837409074878
611 607713934801147381339400
612 638884048741732191195029
613 671626349733619162127157
614 706018822791432722830942
615 742143257235667365743963
616 780085429214566171630492
617 819935292838893708590859
618 861787180329367234222382
619 905740011594752821521548
620 951897513677715527555212
621 1000368450525423306578578
622 1051266863562741901486879
623 1104712323567597206055752
624 1160830194370819371497623
625 1219751908926518367287402
626 1281615258323860688786032
627 1346564694337014383039634
628 1414751646137121811832729
629 1486334851818424919391085
630 1561480705420221691608414
631 1640363620157181254075292
632 1723166408602793566508764
633 1810080680604377906206450
634 1901307259743261917757842
635 1997056619190454198944651
636 2097549337846506462874710
637 2203016577694312635667853
638 2313700583335448943702744
639 2429855204724331258580697
640 2551746444160120547401185
641 2679653028643937629747572
642 2813867008758720741662677
643 2954694385281004052190559
644 3102455764788166855433177
645 3257487045581326140689198
646 3420140135303219755273363
647 3590783701692160249309502
648 3769803957977631201259853
649 3957605484490397893179509
650 4154612088130301300959128
651 4361267701408242699872604
652 4578037322855486757899372
653 4805408000673339676276508
654 5043889861579738520260046
655 5294017186896393648882689
656 5556349538011089154674897
657 5831472933444637503907843
658 6120001079851095437872006
659 6422576659383230997436557
660 6739872675963181355812853
661 7072593863110867663176900
662 7421478156100320196627250
663 7787298231336721853618149
664 8170863115975053876899320
665 8573019870934813117292260
666 8994655350604725099600550
667 9436698042676856816543625
668 9900119991701387426052291
669 10385938810111678863339364
670 10895219780634632243245108
671 11429078054173756925102417
672 11988680947432357896391606
673 12575250344731978643883153
674 13190065208677153433664296
675 13834464204521843154573812
676 14509848443306178625712835
677 15217684349054516509699315
678 15959506655557866870453360
679 16736921538505771074764910
680 17551609888985230215095475
681 18405330734627608734179165
682 19299924814959210442077200
683 20237318317797732403319925
684 21219526783835712873856360
685 22248659186863797357798189
686 23326922197411817981157714
687 24456624637924725141133503
688 25640182137944120128441043
689 26880121998134913528265027
690 28179088272381300243253330
691 29539847077577324433109899
692 30965292141155635917579528
693 32458450596834163542234415
694 34022489039515329291288874
695 35660719850746647015420871
696 37376607806646111549468269
697 39173776980711384283111247
698 41056017954469454698522231
699 43027295349483935652463400
700 45091755694821643646196960
701 47253735644689362562155596
702 49517770561586956675791897
703 51888603480985201610942481
704 54371194474227133594110002
705 56970730427071343771446140
706 59692635252045966162224545
707 62542580553564110827564392
708 65526496765566753453918636
709 68650584782308805152028550
710 71921328103789870654862360
711 75345505518254326223071962
712 78930204345147674994698757
713 82682834262918971825393827
714 86611141747104415386597965
715 90723225145216538552246663
716 95027550416098817668740579
717 99532967562588620064373269
718 104248727787564538193757461
719 109184501404739032416287513
720 114350396536896373779228061
721 119756978635671159096576965
722 125415290858416708355342856
723 131336875339227595438331084
724 137533795392759301558364267
725 144018658691132756011048113
726 150804641455925405130355978
727 157905513709036029588440253
728 165335665628071008471397414
729 173110135053837882068360318
730 181244636199551508081143495
731 189755589613461748732294824
732 198660153448803304058152695
733 207976256097251367629847484
734 217722630244445240978866298
735 227918848408619480502489908
736 238585360025963083957735383
737 249743530149015420061179767
738 261415679827207868558890981
739 273625128241576765838718364
740 286396236668711291561907458
741 299754454352163983252618748
742 313726366362847283062603587
743 328339743533371761751178954
744 343623594554856452717024337
745 359608220328464563537018151
746 376325270667795063717057456
747 393807803452298168491659597
748 412090346336087632299177844
749 431208961120901275753356795
750 451201310906520852913513724
751 472106730136710246446228546
752 493966297663675044775001467
753 516822912959194342348749182
754 540721375605935988933107266
755 565708468208047498797394268
756 591833042865925899708803007
757 619146111366119910111802866
758 647700939243617030720927181
759 677553143880326036928311470
760 708760796810393092837307161
761 741384530410097507057823299
762 775487649157472921554790419
763 811136245654502863460965076
764 848399321612758740453724057
765 887348914011695763597184769
766 928060226647511901735313837
767 970611767299519858570955721
768 1015085490750397169420941907
769 1061566947906479316494532744
770 1110145441274461167351331385
771 1160914187061488610025974588
772 1213970484176672511512421238
773 1269415890423557676413639692
774 1327356406185049106995923141
775 1387902665914754928955515077
776 1451170137761669859502044428
777 1517279331668614801295245456
778 1586356016298889034667717020
779 1658531445160202660198934640
780 1733942592310161995621605895
781 1812732398043402817934497376
782 1895050024976930829184173531
783 1981051124967360533817978397
784 2070898117311570438994400479
785 2164760478700840903975487868
786 2262815045417840682701675132
787 2365246328285908654493296657
788 2472246840900970061404269277
789 2584017441698163430323664661
790 2700767690427869877030308288
791 2822716219639364583824964012
792 2950091121794788090478816675
793 3083130352661599826436248820
794 3222082151658167806771482415
795 3367205479854706632820297628
796 3518770476360444321391030182
797 3677058933857719930564085347
798 3842364794074735122703843805
799 4014994664020950640697932477
800 4195268353842683132362787213
801 4383519437191369356333978414
802 4580095835033278032319547744
803 4785360423867218643763445109
804 4999691669356079922920708884
805 5223484286418887721254248474
806 5457149926872565234021599122
807 5701117895756771804333544579
808 5955835897521158114583994902
809 6221770813302173840871580674
810 6499409510566272260286717838
811 6789259686448049392095514895
812 7091850746165611779372686448
813 7407734717951367211123015360
814 7737487205994562216177967669
815 8081708382952335171568422654
816 8441024023648906477536778192
817 8816086581647881239883451465
818 9207576310450594080933786264
819 9616202431144081034732046692
820 10042704348395727331886924302
821 10487852916768020680083347777
822 10952451759406252861621021596
823 11437338641234575994825367524
824 11943386898881657554269432224
825 12471506929646417139325932575
826 13022647741907102514004405425
827 13597798569473408971257307139
828 14197990552481609263989403321
829 14824298487536889272139881548
830 15477842649915432545919175703
831 16159790690751424296406906090
832 16871359612251220702469707422
833 17613817824098623871699752776
834 18388487284341697590381901680
835 19196745728183039956039904363
836 20040028988232090651661097089
837 20919833409920093046514714902
838 21837718365925965269280552922
839 22795308873614774903009308938
840 23794298319649985745540486682
841 24836451296106385183634439142
842 25923606552582850708539122379
843 27057680068993124792257669122
844 28240668253898802422317207196
845 29474651273442064680722365100
846 30761796516136598513729094786
847 32104362198983919230634019148
848 33504701120599263052107122751
849 34965264567256656458997226035
850 36488606377997026857261101246
851 38077387175186632995039894476
852 39734378767166018322372623115
853 41462468729892491592185240294
854 43264665174752197573871068689
855 45144101710001550190584613463
856 47104042603592572707674925728
857 49147888155442947716081379349
858 51279180287529766801112580245
859 53501608360516543237125222044
860 55819015225966487112375762304
861 58235403523551833070545662713
862 60754942233039670970325395610
863 63381973491219788256422061274
864 66121019684340043287680795377
865 68976790827030322921296059265
866 71954192239127790244657650895
867 75058332532264514591508383947
868 78294531918544338298606261803
869 81668330854119634337257396035
870 85185499030981137013623743646
871 88852044730795998473879600467
872 92674224555171379444966652549
873 96658553547283991801526636533
874 100811815720400874702234883170
875 105141075009424131145695944446
876 109653686662223239950778594996
877 114357309088173780810191534391
878 119259916182001893731003762061
879 124369810141740497850343401584
880 129695634800337217777183228268
881 135246389491216139159039707685
882 141031443468887014003234331252
883 147060550906517472455423358381
884 153343866493237326474415401427
885 159891961654830368298135567688
886 166715841422389418383359364021
887 173826961974466049388647027910
888 181237248879238744213762144118
889 188959116064253623452991215665
890 197005485542361740358128512726
891 205389807923587780504421906251
892 214126083743818370285140104440
893 223228885642395695663993595496
894 232713381421945428454909806144
895 242595358025058778911066827273
896 252891246463788633236275823328
897 263618147739311049976532088105
898 274793859790547811446459862013
899 286436905512045251383911302284
900 298566561882961284237909688321
901 311202890250628595181925120519
902 324366767813839544212242461904
903 338079920352739804406850392119
904 352364956254025496411506129664
905 367245401882015082872184176400
906 382745738348115130712302932543
907 398891439733220911291082284845
908 415709012819691463730157330109
909 433226038391717071054930132553
910 451471214165158079965710424021
911 470474399410280723295714457326
912 490266661333251290631026701040
913 510880323284777963866105932228
914 532349014866913340465219053810
915 554707724011753683404835446352
916 577992851108596975986469202949
917 602242265259054763362143404693
918 627495362742656520536361205146
919 653793127778644032735646513805
920 681178195672931294334479537074
921 709694918442607169375649985491
922 739389433013888121356361447859
923 770309732093091484527180735473
924 802505737814000968008480225351
925 836029378268940491453806034973
926 870934667034965368424028772307
927 907277785810826797096160962525
928 945117170284772311200878398314
929 984513599357817211859322710363
930 1025530287851866192228314561578
931 1068232982836986753400685026194
932 1112690063717243195564375189893
933 1158972646219798797954901878301
934 1207154690437491375341574779760
935 1257313113080791068733910157052
936 1309527904100966620610767262021
937 1363882247852425403812169933421
938 1420462648968561308202242114115
939 1479359063132051729264763117259
940 1540665032927399151763096961785
941 1604477828970623294784451123871
942 1670898596518385936634266829828
943 1740032507766482166801224664853
944 1811988920055569068803569775492
945 1886881540210236243694532479789
946 1964828595246063048624974418266
947 2045953009688166244315883616866
948 2130382589753930633497043703640
949 2218250214662146367863776645214
950 2309694035340662478906386376639
951 2404857680814919881218020921326
952 2503890472570362116194269557634
953 2606947647192752439969763695397
954 2714190587601866016688440422163
955 2825787063205890986762846841373
956 2941911479316177608288401069167
957 3062745136174736653134217323768
958 3188476497960123500268531713757
959 3319301472151070225090078640578
960 3455423699641462385181494569009
961 3597054856015018749455692034896
962 3744414964403340173157481601652
963 3897732720366868148942240672852
964 4057245829254754951510886564856
965 4223201356516717163208211360689
966 4395856091457644922460581159895
967 4575476924944093479519471258877
968 4762341241590815397831618718201
969 4956737326975225690570144226694
970 5158964790448153907668342734131
971 5369335004130453176179373196918
972 5588171558707033891181985621164
973 5815810736652697590223361736391
974 6052602003547793966230177995199
975 6298908518166241490835416475608
976 6555107662043871337843072912468
977 6821591589261407944527756267139
978 7098767797203721534834832045015
979 7387059719085313381164777733124
980 7686907339061359873141224114043
981 7998767830774084276674202758978
982 8323116220215784438336795126274
983 8660446073822561038901298332911
984 9011270212746706195929617901572
985 9376121454290869631403716021160
986 9755553381523564162804516773509
987 10150141142133350465807652746501
988 10560482277618201074820926006158
989 10987197583947135324701323768059
990 11430932004873292066522672306386
991 11892355559121219035806346378786
992 12372164302716362124677234851783
993 12871081327771591908623427368725
994 13389857799094168043719242310756
995 13929274030026876127596230753400
996 14490140598989240044546717571951
997 15073299508238781705964163587808
998 15679625386428337789089228954481
999 16310026736593520350983787226243
1000 16965447231264598340990362164213