0 1
1 1
2 2
3 2
4 4
5 5
6 7
7 10
8 14
9 16
10 24
11 31
12 37
13 51
14 67
15 76
16 103
17 129
18 158
19 199
20 242
21 293
22 370
23 450
24 538
25 652
26 799
27 953
28 1147
29 1376
30 1635
31 1956
32 2322
33 2757
34 3271
35 3845
36 4539
37 5336
38 6282
39 7366
40 8589
41 10046
42 11735
43 13647
44 15858
45 18442
46 21354
47 24716
48 28630
49 32985
50 38030
51 43900
52 50400
53 57918
54 66594
55 76197
56 87232
57 99968
58 114082
59 130239
60 148694
61 169236
62 192616
63 219322
64 248928
65 282552
66 320787
67 363251
68 411283
69 465743
70 526089
71 594296
72 671228
73 756692
74 852750
75 961043
76 1081097
77 1215842
78 1367016
79 1534915
80 1722765
81 1933084
82 2166243
83 2426816
84 2717700
85 3040327
86 3399557
87 3800247
88 4243902
89 4737499
90 5286233
91 5893920
92 6568467
93 7317384
94 8145437
95 9063773
96 10080910
97 11205304
98 12448973
99 13825611
100 15345593
101 17024758
102 18879107
103 20925797
104 23183575
105 25674284
106 28418464
107 31443350
108 34774723
109 38443397
110 42480298
111 46921815
112 51807399
113 57177945
114 63077953
115 69564163
116 76683938
117 84498936
118 93077873
119 102488729
120 112806077
121 124122164
122 136519389
123 150099035
124 164979030
125 181267108
126 199085169
127 218595365
128 239928392
129 263248675
130 288754202
131 316620657
132 347053043
133 380309129
134 416607928
135 456220191
136 499464411
137 546629620
138 598047921
139 654141405
140 715266961
141 781853874
142 854424564
143 933447672
144 1019463191
145 1113137146
146 1215048783
147 1325902251
148 1446520241
149 1577658766
150 1720186424
151 1875154125
152 2043509573
153 2226360131
154 2425009834
155 2640679610
156 2874744029
157 3128853381
158 3404525388
159 3703524205
160 4027885490
161 4379542089
162 4760685292
163 5173877299
164 5621541968
165 6106443804
166 6631735057
167 7200503596
168 7816176459
169 8482708914
170 9203937146
171 9984173970
172 10828302141
173 11741153409
174 12728082198
175 13795171749
176 14948426418
177 16194552912
178 17541029097
179 18995414210
180 20565997163
181 22262055976
182 24092966193
183 26069060266
184 28201764246
185 30502778122
186 32984849053
187 35662124957
188 38549077534
189 41661549852
190 45016902574
191 48633126998
192 52529746429
193 56728179998
194 61250637705
195 66121266792
196 71366327021
197 77013325624
198 83091940046
199 89634496051
200 96674845737
201 104249575175
202 112398262615
203 121162660530
204 130587662915
205 140721846175
206 151616456813
207 163326672373
208 175911857308
209 189435042073
210 203963758554
211 219570672683
212 236332963384
213 254333395081
214 273660659736
215 294409311919
216 316680438089
217 340582390231
218 366230660136
219 393748776784
220 423268712725
221 454931626048
222 488888060769
223 525298829084
224 564335933910
225 606182915711
226 651035337127
227 699102739346
228 750608336428
229 805789980626
230 864902450890
231 928217140027
232 996022713881
233 1068628896112
234 1146365060033
235 1229581478737
236 1318653864066
237 1413981860884
238 1515989872625
239 1625133359925
240 1741896360661
241 1866792947725
242 2000374479930
243 2143226822721
244 2295971606733
245 2459275958553
246 2633848134748
247 2820439335836
248 3019855465048
249 3232952160150
250 3460636292203
251 3703880661638
252 3963717462362
253 4241240839080
254 4537623632150
255 4854110119789
256 5192018755516
257 5552762520178
258 5937839898459
259 6348838115988
260 6787457501323
261 7255501343755
262 7754878792700
263 8287634154403
264 8855934742069
265 9462075388931
266 10108511808211
267 10797846597057
268 11532835234785
269 12316424914213
270 13151738633108
271 14042082061669
272 14990988725789
273 16002202934047
274 17079686975298
275 18227673811039
276 19450648347159
277 20753356177609
278 22140864198872
279 23618539144441
280 25192059877376
281 26867486511506
282 28651236444155
283 30550099207726
284 32571315929169
285 34722554314948
286 37011926114053
287 39448076158642
288 42040158282791
289 44797855133514
290 47731480664037
291 50851953433539
292 54170822042564
293 57700381604814
294 61453645892626
295 65444377712704
296 69687222471117
297 74197678776850
298 78992137107159
299 84088026725595
300 89503792221739
301 95258937387219
302 101374191436059
303 107871486394570
304 114774012423882
305 122106404638632
306 129894724996703
307 138166524462028
308 146951058924324
309 156279272229293
310 166183875952022
311 176699585709269
312 187863116623320
313 199713276617473
314 212291232778446
315 225640514406745
316 239807130305673
317 254839861341192
318 270790283302433
319 287712897615658
320 305665469827525
321 324709063642480
322 344908201233107
323 366331235838629
324 389050415047518
325 413142068234480
326 438687028262664
327 465770712048232
328 494483357978796
329 524920485347739
330 557183021645648
331 591377570099951
332 627616935147083
333 666020285738083
334 706713479049463
335 749829639546708
336 795509387265185
337 843901206596500
338 895162109876738
339 949457910030491
340 1006963680727211
341 1067864481520129
342 1132355718852646
343 1200643673092855
344 1272946327635005
345 1349493810027254
346 1430529028009488
347 1516308575704874
348 1607103310123265
349 1703199074346972
350 1804897742426251
351 1912517898544092
352 2026395714004270
353 2146886101637145
354 2274363566232930
355 2409223212171137
356 2551882071305061
357 2702780104144236
358 2862381416259783
359 3031175715681374
360 3209679568176995
361 3398437785192558
362 3598025100439769
363 3809047643540224
364 4032144600517846
365 4267990080639857
366 4517294915251065
367 4780808552117343
368 5059321222947338
369 5353666034563406
370 5664721239384203
371 5993412638400452
372 6340716117258841
373 6707660251151941
374 7095329080867013
375 7504865067315012
376 7937472184993039
377 8394419021453623
378 8877042332757737
379 9386750573228963
380 9925027510278088
381 10493436335776141
382 11093623844013550
383 11727324490870224
384 12396365292995267
385 13102670623579525
386 13848266928734423
387 14635288379941771
388 15465982543792463
389 16342715687758032
390 17267979496116754
391 18244397552704371
392 19274731521481989
393 20361888892270399
394 21508930601464749
395 22719078034547569
396 23995722155658133
397 25342432231142773
398 26762964005765431
399 28261270190592298
400 29841510714140590
401 31508061996630849
402 33265529264940823
403 35118758297412578
404 37072846234768114
405 39133155736001416
406 41305328720478601
407 43595298672921728
408 46009307205901579
409 48553919786241677
410 51236040117078288
411 54062929122078256
412 57042223300339851
413 60181951150668347
414 63490555297967491
415 66976913527865602
416 70650357937944303
417 74520700278085113
418 78598256470096669
419 82893868506466177
420 87418933911512676
421 92185433806903113
422 97205958461344794
423 102493741011182768
424 108062690068582433
425 113927419009696497
426 120103285072063031
427 126606426689528426
428 133453797616223615
429 140663211618506383
430 148253385827622957
431 156243979882161453
432 164655647608758860
433 173510086646447423
434 182830084031032468
435 192639575263037544
436 202963701764275993
437 213828863211228668
438 225262785746127095
439 237294587737374439
440 249954840628961695
441 263275646819195647
442 277290715741308286
443 292035433768064072
444 307546953929410688
445 323864282963686430
446 341028362540696798
447 359082171674783334
448 378070827212429697
449 398041677141508561
450 419044418469142725
451 441131212181771642
452 464356791453238121
453 488778596104609963
454 514456905214753107
455 541454961457429128
456 569839125556574269
457 599679027932546536
458 631047712773396532
459 664021814198018251
460 698681730847746097
461 735111791358805180
462 773400456600564088
463 813640519273987697
464 855929295292323258
465 900368854298442135
466 947066249319125039
467 996133736561318114
468 1047689039582493452
469 1101855611737394102
470 1158762890143330867
471 1218546596773459919
472 1281349039940454213
473 1347319405710544235
474 1416614102837341318
475 1489397107169240858
476 1565840297775140750
477 1646123849913838317
478 1730436630366094756
479 1818976583051282013
480 1911951178532514059
481 2009577865443822727
482 2112084514884190414
483 2219709932387361585
484 2332704375441641725
485 2451330062789891021
486 2575861759893469137
487 2706587369731316899
488 2843808518630957150
489 2987841222906207782
490 3139016565640148675
491 3297681367825495202
492 3464198949844764114
493 3638949903529075365
494 3822332863588335736
495 4014765374400390664
496 4216684773446809194
497 4428549074296370229
498 4650837956203490038
499 4884053771761831236
500 5128722560049912556
501 5385395172779652979
502 5654648426672024137
503 5937086262216347743
504 6233341028351213725
505 6544074795856960541
506 6869980685960621544
507 7211784332026007587
508 7570245379713901740
509 7946159005435703444
510 8340357582888502728
511 8753712392468255983
512 9187135359829321560
513 9641580951047198721
514 10118048124323686448
515 10617582315274224399
516 11141277596200177763
517 11690278898687320595
518 12265784284471813456
519 12869047400727836239
520 13501380014771996227
521 14164154605308395096
522 14858807158775446621
523 15586840054429721556
524 16349825025001562913
525 17149406334600273804
526 17987304067529753678
527 18865317504279654140
528 19785328737843139163
529 20749306415402372774
530 21759309591882544783
531 22817491839077852618
532 23926105507124934881
533 25087506114586300419
534 26304157023118157355
535 27578634282991908011
536 28913631639167353673
537 30311965840697610907
538 31776582155851780354
539 33310560071914331951
540 34917119330445632022
541 36599626195324291408
542 38361599947149054563
543 40206719735278576588
544 42138831707042551184
545 44161956395355044634
546 46280296505040315007
547 48498245011487942902
548 50820393569221543013
549 53251541348878949545
550 55796704242408119165
551 58461124422678993591
552 61250280378880843413
553 64169897366907672219
554 67225958282878469361
555 70424715047446284039
556 73772700476333623253
557 77276740632935264061
558 80943967750145336510
559 84781833701128009949
560 88798124035913730775
561 93000972634580860995
562 97398877000040232526
563 102000714192922823004
564 106815757454833657786
565 111853693551636607960
566 117124640869237121762
567 122639168256553918704
568 128408314700252934756
569 134443609854655262034
570 140757095406672320240
571 147361347379066844012
572 154269499425471969462
573 161495267035821154202
574 169052972825423833533
575 176957572945250592743
576 185224684512894552934
577 193870614264314000910
578 202912388500178943586
579 212367784152316553825
580 222255361248289736318
581 232594496842074829610
582 243405420203348203766
583 254709249579364837788
584 266528030642204914378
585 278884776320399430820
586 291803508432551060633
587 305309301223612835051
588 319428326456225911305
589 334187900531869253091
590 349616533788775685676
591 365743981521615108522
592 382601297314579768957
593 400220888828675548257
594 418636575532506425407
595 437883649032087622242
596 457998936201245923305
597 479020864470473971708
598 500989530072052817601
599 523946769442054866330
600 547936233054445391348
601 573003462581240963362
602 599195971644326074722
603 626563329275788080221
604 655157247153985260617
605 685031670879080026894
606 716242874313623342026
607 748849558164998048134
608 782912953147093220750
609 818496926571541096165
610 855668093741416304261
611 894495934496495429469
612 935052913636296295097
613 977414606735075997374
614 1021659831792255168718
615 1067870785225166748065
616 1116133183960161290073
617 1166536414079372095848
618 1219173684382535048414
619 1274142186797491797734
620 1331543264191047430337
621 1391482583704786850289
622 1454070317823174272868
623 1519421333746828734145
624 1587655389024730378702
625 1658897335858868291131
626 1733277334780781310900
627 1810931075369645135579
628 1892000006743394240590
629 1976631578567028367131
630 2064979490034252118416
631 2157203949815216946588
632 2253471947845731796019
633 2353957536096962788043
634 2458842121697775688138
635 2568314773327724749908
636 2682572537786005573319
637 2801820770410406796662
638 2926273480419535942842
639 3056153687733789057319
640 3191693795367384519429
641 3333135978546953869950
642 3480732586831295292052
643 3634746563680594166614
644 3795451884818827323652
645 3963134011259384039452
646 4138090361944897246083
647 4320630807433658113578
648 4511078180183130629595
649 4709768806814879034224
650 4917053063993228185900
651 5133295953042516239562
652 5358877699241490547021
653 5594194377548246694321
654 5839658559536441821675
655 6095699987965280357910
656 6362766280990272482812
657 6641323660314826509862
658 6931857710340884158177
659 7234874170492100844473
660 7550899754606234983966
661 7880483005044094964166
662 8224195183963897688790
663 8582631195144108070273
664 8956410544731906438508
665 9346178343555185352389
666 9752606343969213598674
667 10176394020275722884149
668 10618269695673899140976
669 11078991708182826388210
670 11559349625375319198034
671 12060165511150043906614
672 12582295236519364067818
673 13126629845015087451358
674 13694096976327825812093
675 14285662339584536419806
676 14902331247794832008971
677 15545150217389605949877
678 16215208623776171924787
679 16913640425332762209101
680 17641625960191746374345
681 18400393806179728224719
682 19191222717353886235232
683 20015443641876572840888
684 20874441811120888320558
685 21769658914432396611639
686 22702595364819104227316
687 23674812644899115271436
688 24687935748670569019983
689 25743655724869643181638
690 26843732310751625358001
691 27989996673023564225867
692 29184354262286992116334
693 30428787769293560505954
694 31725360201023104763336
695 33076218083533995017243
696 34483594779457160592111
697 35949813939424746261540
698 37477293095085105126284
699 39068547381133918694288
700 40726193407050024212759
701 42452953286935484650977
702 44251658814490428315329
703 46125255805284804566348
704 48076808615568988435422
705 50109504824278455267556
706 52226660101972027297707
707 54431723276853172427781
708 56728281584239269669846
709 59120066124877431508933
710 61610957543220374319244
711 64204991911862791137805
712 66906366849258297988818
713 69719447882925775507733
714 72648775044213914104935
715 75699069723615129879215
716 78875241800021213594920
717 82182397029998557172274
718 85625844727977113694967
719 89211105752128223466649
720 92943920782073273860833
721 96830258921432955835416
722 100876326641361866517795
723 105088577051565742928223
724 109473719533932333910450
725 114038729756548423524771
726 118790860054981907191658
727 123737650218356494902149
728 128886938699649298509485
729 134246874237824344921236
730 139825927931641844458934
731 145632905786638048047339
732 151676961723651322078711
733 157967611091409833141044
734 164514744706652866331579
735 171328643411459511149560
736 178419993192901768217069
737 185799900890933664230414
738 193479910485468845527819
739 201472020010851689627590
740 209788699126013201363747
741 218442907333217659790295
742 227448112896455794691630
743 236818312490829443445450
744 246568051577802776340270
745 256712445560808751049318
746 267267201755425218348100
747 278248642171872753375430
748 289673727167535984661350
749 301560080007371311379225
750 313926012332754335679527
751 326790550600476144266245
752 340173463533230894752355
753 354095290586065372476764
754 368577371494072113089818
755 383641876947208709341340
756 399311840400639053225905
757 415611191090366424674174
758 432564788304247143288580
759 450198456922155797446060
760 468539024299147898307906
761 487614358547148794520311
762 507453408234189809484339
763 528086243580333388107769
764 549544099210948205569126
765 571859418493356282119532
766 595065899540594218061501
767 619198542949708165512733
768 644293701307609657468722
769 670389130554224476612441
770 697524043276598915841928
771 725739163976209031427722
772 755076786404547151677982
773 785580833048780951947393
774 817296916818764141949034
775 850272405037652249425335
776 884556485825565637553607
777 920200236939270297792992
778 957256697176303890753115
779 995780940443032754633571
780 1035830152561341475575699
781 1077463710930615542080586
782 1120743267153830896352410
783 1165732832717493443950479
784 1212498867849348825890085
785 1261110373674833375169506
786 1311638987776804871345569
787 1364159083292455816492769
788 1418747871679901512892382
789 1475485509277643647116928
790 1534455207799449323651805
791 1595743348912116655278068
792 1659439603038127360754836
793 1725637052537443239951550
794 1794432319429895332815922
795 1865925697823827610187730
796 1940221291215591803415973
797 2017427154839478962008429
798 2097655443257229048109672
799 2181022563365940990444470
800 2267649333021368921444498
801 2357661145494732902031929
802 2451188139954384797214653
803 2548365378191768758590680
804 2649333027839014265384822
805 2754236552286595765711985
806 2863226907541621608371217
807 2976460746310292699372821
808 3094100629528386841246892
809 3216315245607338914777204
810 3343279637715706692224845
811 3475175439340786756590291
812 3612191118424192840697120
813 3754522230435379938968535
814 3902371680646572704496707
815 4055949995936492716770823
816 4215475606531441899974680
817 4381175137972578438837113
818 4553283713668949921844895
819 4732045268499130451475486
820 4917712873773854810255421
821 5110549073959612945930072
822 5310826235680821610563941
823 5518826909344534022808091
824 5734844203827185758218649
825 5959182174807133446836062
826 6192156227115768193428397
827 6434093531596736786192637
828 6685333457124209697900462
829 6946228018191198906704448
830 7217142338606298039441913
831 7498455132030311620774327
832 7790559199800216338778781
833 8093861946639527334710635
834 8408785915068021144493688
835 8735769339006379207333019
836 9075266717234687588638411
837 9427749407615252896358678
838 9793706242620710073137964
839 10173644166900750142985498
840 10568088897897725084879599
841 10977585610110658533641595
842 11402699643814778388513721
843 11844017239365407265576692
844 12302146297742549199985010
845 12777717168234142981344857
846 13271383464507158816949347
847 13783822909796490416683016
848 14315738212200600543036796
849 14867857971475353027507390
850 15440937618127605092160588
851 16035760385908497182008850
852 16653138319244376987637332
853 17293913316497641767004163
854 17958958210268574391841399
855 18649177886448997839805587
856 19365510443009451240692957
857 20108928389866351316164281
858 20880439891716850342323396
859 21681090054935939835055125
860 22511962260019862477112799
861 23374179541670223552941043
862 24268906017725816420458103
863 25197348368592249056208290
864 26160757369477152507662939
865 27160429476778178067793002
866 28197708470441580156575260
867 29273987154849233340014282
868 30390709119722549415743143
869 31549370563062313141664550
870 32751522178940253489395056
871 33998771111804640547733811
872 35292782979525864790847285
873 36635283968297430391648565
874 38028063001230444168416342
875 39472973983114963162621528
876 40971938124773726625102449
877 42526946349061949756569584
878 44140061781239875771882557
879 45813422327503539355626056
880 47549243343948753049633068
881 49349820398994524517874187
882 51217532133425228199854787
883 53154843220594707085574608
884 55164307430128577076667291
885 57248570799716219669531337
886 59410374917810040232936560
887 61652560320935438760607292
888 63978070010653205057170576
889 66389953093322035921508665
890 68891368546745268668533715
891 71485589119261336838698045
892 74176005364769273956884809
893 76966129818219588422873797
894 79859601317669935281060947
895 82860189476807944920102641
896 85971799312936087524917303
897 89198476037138945807811046
898 92544410010962086439577798
899 96013941875140929345292220
900 99611567857751215137798164
901 103341945266614959308783019
902 107209898172069245659403802
903 111220423288214771829695208
904 115378696058007445440447035
905 119690076948962639619607231
906 124160117968368912405311268
907 128794569404000103201618924
908 133599386797791014517909598
909 138580738162264129120189589
910 143745011446353932189329766
911 149098822258898781493130906
912 154649021860527081914372144
913 160402705431353774221550512
914 166367220623604308354322264
915 172550176410963616913641514
916 178959452242877958565789675
917 185603207513905942133521092
918 192489891361043757661046505
919 199628252798199206861619473
920 207027351198947527893718763
921 214696567141773028757912513
922 222645613627975280073532075
923 230884547684564122486646848
924 239423782367700848006964835
925 248274099178029021045651251
926 257446660901479210443515305
927 266953024892641370474081716
928 276805156813286958031614897
929 287015444841068873533731486
930 297596714367120654211624976
931 308562243196564607349864270
932 319925777268495086589316113
933 331701546915997956481452319
934 343904283681737817909964341
935 356549237707436738923456492
936 369652195719757883846230571
937 383229499629876629115606590
938 397298065766933967368459173
939 411875404770090099155906156
940 426979642158335202743700242
941 442629539600379486084030940
942 458844516911687798200787924
943 475644674799960246565687418
944 493050818383655295316664256
945 511084481513265619206630102
946 529767951918942877110657143
947 549124297211652545380512604
948 569177391770389555425602112
949 589951944541668519725274959
950 611473527781236968272972780
951 633768606773711010475528100
952 656864570559162678764667022
953 680789763699738406513724596
954 705573519125393242666356302
955 731246192090971716279471616
956 757839195281071811240639758
957 785385035105579169035250865
958 813917349221545073889308625
959 843470945321636459276072757
960 874081841236118041292628477
961 905787306387937714408018045
962 938625904645220853834764183
963 972637538622695979351012977
964 1007863495475826025345038380
965 1044346494236545470650852225
966 1082130734747013735258073531
967 1121261948239912172936073871
968 1161787449619130436274592456
969 1203756191502722100609445978
970 1247218820081788301013817509
971 1292227732854690582795622551
972 1338837138304352921509332577
973 1387103117578092450393696121
974 1437083688235369786899782470
975 1488838870137789172391316762
976 1542430753547033842364291634
977 1597923569502850749458118780
978 1655383762562480529589101289
979 1714880065974241091118240594
980 1776483579364640324790264639
981 1840267849028291858691252188
982 1906308950900946350160361571
983 1974685576303141461505595768
984 2045479120552234631606445090
985 2118773774531662347096275446
986 2194656619313709988424344933
987 2273217723943019782155490724
988 2354550246478921931650838943
989 2438750538402688325322793664
990 2525918252507147831544940971
991 2616156454377087581664340008
992 2709571737577168064392394837
993 2806274342676151171892372053
994 2906378280227078814503331937
995 3010001457831990351085554260
996 3117265811432245826526708337
997 3228297440956625824226671179
998 3343226750468642531037800137
999 3462188592967764789978473878
1000 3585322419990333557099742470