1 9
2 16
3 19
4 25
5 34
6 39
7 36
8 53
9 70
10 79
11 49
12 76
13 109
14 142
15 159
16 64
17 103
18 156
19 221
20 286
21 319
22 81
23 134
24 211
25 316
26 445
27 574
28 639
29 100
30 169
31 274
32 427
33 636
34 893
35 1150
36 1279
37 121
38 208
39 345
40 554
41 859
42 1276
43 1789
44 2302
45 2559
46 144
47 251
48 424
49 697
50 1114
51 1723
52 2556
53 3581
54 4606
55 5119
56 169
57 298
58 511
59 856
60 1401
61 2234
62 3451
63 5116
64 7165
65 9214
66 10239
67 196
68 349
69 606
70 1031
71 1720
72 2809
73 4474
74 6907
75 10236
76 14333
77 18430
78 20479
79 225
80 404
81 709
82 1222
83 2071
84 3448
85 5625
86 8954
87 13819
88 20476
89 28669
90 36862
91 40959
92 256
93 463
94 820
95 1429
96 2454
97 4151
98 6904
99 11257
100 17914
101 27643
102 40956
103 57341
104 73726
105 81919
106 289
107 526
108 939
109 1652
110 2869
111 4918
112 8311
113 13816
114 22521
115 35834
116 55291
117 81916
118 114685
119 147454
120 163839
121 324
122 593
123 1066
124 1891
125 3316
126 5749
127 9846
128 16631
129 27640
130 45049
131 71674
132 110587
133 163836
134 229373
135 294910
136 327679
137 361
138 664
139 1201
140 2146
141 3795
142 6644
143 11509
144 19702
145 33271
146 55288
147 90105
148 143354
149 221179
150 327676
151 458749
152 589822
153 655359
154 400
155 739
156 1344
157 2417
158 4306
159 7603
160 13300
161 23029
162 39414
163 66551
164 110584
165 180217
166 286714
167 442363
168 655356
169 917501
170 1179646
171 1310719
172 441
173 818
174 1495
175 2704
176 4849
177 8626
178 15219
179 26612
180 46069
181 78838
182 133111
183 221176
184 360441
185 573434
186 884731
187 1310716
188 1835005
189 2359294
190 2621439
191 484
192 901
193 1654
194 3007
195 5424
196 9713
197 17266
198 30451
199 53236
200 92149
201 157686
202 266231
203 442360
204 720889
205 1146874
206 1769467
207 2621436
208 3670013
209 4718590
210 5242879
211 529
212 988
213 1821
214 3326
215 6031
216 10864
217 19441
218 34546
219 60915
220 106484
221 184309
222 315382
223 532471
224 884728
225 1441785
226 2293754
227 3538939
228 5242876
229 7340029
230 9437182
231 10485759
232 576
233 1079
234 1996
235 3661
236 6670
237 12079
238 21744
239 38897
240 69106
241 121843
242 212980
243 368629
244 630774
245 1064951
246 1769464
247 2883577
248 4587514
249 7077883
250 10485756
251 14680061
252 18874366
253 20971519
254 625
255 1174
256 2179
257 4012
258 7341
259 13358
260 24175
261 43504
262 77809
263 138226
264 243699
265 425972
266 737269
267 1261558
268 2129911
269 3538936
270 5767161
271 9175034
272 14155771
273 20971516
274 29360125
275 37748734
276 41943039
277 676
278 1273
279 2370
280 4379
281 8044
282 14701
283 26734
284 48367
285 87024
286 155633
287 276466
288 487411
289 851956
290 1474549
291 2523126
292 4259831
293 7077880
294 11534329
295 18350074
296 28311547
297 41943036
298 58720253
299 75497470
300 83886079
301 729
302 1376
303 2569
304 4762
305 8779
306 16108
307 29421
308 53486
309 96751
310 174064
311 311281
312 552946
313 974835
314 1703924
315 2949109
316 5046262
317 8519671
318 14155768
319 23068665
320 36700154
321 56623099
322 83886076
323 117440509
324 150994942
325 167772159
326 784
327 1483
328 2776
329 5161
330 9546
331 17579
332 32236
333 58861
334 106990
335 193519
336 348144
337 622577
338 1105906
339 1949683
340 3407860
341 5898229
342 10092534
343 17039351
344 28311544
345 46137337
346 73400314
347 113246203
348 167772156
349 234881021
350 301989886
351 335544319
352 841
353 1594
354 2991
355 5576
356 10345
357 19114
358 35179
359 64492
360 117741
361 213998
362 387055
363 696304
364 1245169
365 2211826
366 3899379
367 6815732
368 11796469
369 20185078
370 34078711
371 56623096
372 92274681
373 146800634
374 226492411
375 335544316
376 469762045
377 603979774
378 671088639
379 900
380 1709
381 3214
382 6007
383 11176
384 20713
385 38250
386 70379
387 129004
388 235501
389 428014
390 774127
391 1392624
392 2490353
393 4423666
394 7798771
395 13631476
396 23592949
397 40370166
398 68157431
399 113246200
400 184549369
401 293601274
402 452984827
403 671088636
404 939524093
405 1207959550
406 1342177279
407 961
408 1828
409 3445
410 6454
411 12039
412 22376
413 41449
414 76522
415 140779
416 258028
417 471021
418 856046
419 1548271
420 2785264
421 4980721
422 8847346
423 15597555
424 27262964
425 47185909
426 80740342
427 136314871
428 226492408
429 369098745
430 587202554
431 905969659
432 1342177276
433 1879048189
434 2415919102
435 2684354559
436 1024
437 1951
438 3684
439 6917
440 12934
441 24103
442 44776
443 82921
444 153066
445 281579
446 516076
447 942061
448 1712110
449 3096559
450 5570544
451 9961457
452 17694706
453 31195123
454 54525940
455 94371829
456 161480694
457 272629751
458 452984824
459 738197497
460 1174405114
461 1811939323
462 2684354556
463 3758096381
464 4831838206
465 5368709119
466 1089
467 2078
468 3931
469 7396
470 13861
471 25894
472 48231
473 89576
474 165865
475 306154
476 563179
477 1032172
478 1884141
479 3424238
480 6193135
481 11141104
482 19922929
483 35389426
484 62390259
485 109051892
486 188743669
487 322961398
488 545259511
489 905969656
490 1476395001
491 2348810234
492 3623878651
493 5368709116
494 7516192765
495 9663676414
496 10737418239
497 1156
498 2209
499 4186
500 7891
501 14820
502 27749
503 51814
504 96487
505 179176
506 331753
507 612330
508 1126379
509 2064364
510 3768301
511 6848494
512 12386287
513 22282224
514 39845873
515 70778866
516 124780531
517 218103796
518 377487349
519 645922806
520 1090519031
521 1811939320
522 2952790009
523 4697620474
524 7247757307
525 10737418236
526 15032385533
527 19327352830
528 21474836479
529 1225
530 2344
531 4449
532 8402
533 15811
534 29668
535 55525
536 103654
537 192999
538 358376
539 663529
540 1224682
541 2252779
542 4128748
543 7536621
544 13697006
545 24772591
546 44564464
547 79691761
548 141557746
549 249561075
550 436207604
551 754974709
552 1291845622
553 2181038071
554 3623878648
555 5905580025
556 9395240954
557 14495514619
558 21474836476
559 30064771069
560 38654705662
561 42949672959
562 1296
563 2483
564 4720
565 8929
566 16834
567 31651
568 59364
569 111077
570 207334
571 386023
572 716776
573 1327081
574 2449386
575 4505579
576 8257516
577 15073261
578 27394030
579 49545199
580 89128944
581 159383537
582 283115506
583 499122163
584 872415220
585 1509949429
586 2583691254
587 4362076151
588 7247757304
589 11811160057
590 18790481914
591 28991029243
592 42949672956
593 60129542141
594 77309411326
595 85899345919
596 1369
597 2626
598 4999
599 9472
600 17889
601 33698
602 63331
603 118756
604 222181
605 414694
606 772071
607 1433576
608 2654185
609 4898794
610 9011179
611 16515052
612 30146541
613 54788078
614 99090415
615 178257904
616 318767089
617 566231026
618 998244339
619 1744830452
620 3019898869
621 5167382518
622 8724152311
623 14495514616
624 23622320121
625 37580963834
626 57982058491
627 85899345916
628 120259084285
629 154618822654
630 171798691839
631 1444
632 2773
633 5286
634 10031
635 18976
636 35809
637 67426
638 126691
639 237540
640 444389
641 829414
642 1544167
643 2867176
644 5308393
645 9797610
646 18022379
647 33030124
648 60293101
649 109576174
650 198180847
651 356515824
652 637534193
653 1132462066
654 1996488691
655 3489660916
656 6039797749
657 10334765046
658 17448304631
659 28991029240
660 47244640249
661 75161927674
662 115964116987
663 171798691836
664 240518168573
665 309237645310
666 343597383679
667 1521
668 2924
669 5581
670 10606
671 20095
672 37984
673 71649
674 134882
675 253411
676 475108
677 888805
678 1658854
679 3088359
680 5734376
681 10616809
682 19595242
683 36044779
684 66060268
685 120586221
686 219152366
687 396361711
688 713031664
689 1275068401
690 2264924146
691 3992977395
692 6979321844
693 12079595509
694 20669530102
695 34896609271
696 57982058488
697 94489280505
698 150323855354
699 231928233979
700 343597383676
701 481036337149
702 618475290622
703 687194767359
704 1600
705 3079
706 5884
707 11197
708 21246
709 40223
710 76000
711 143329
712 269794
713 506851
714 950244
715 1777637
716 3317734
717 6176743
718 11468776
719 21233641
720 39190506
721 72089579
722 132120556
723 241172461
724 438304750
725 792723439
726 1426063344
727 2550136817
728 4529848306
729 7985954803
730 13958643700
731 24159191029
732 41339060214
733 69793218551
734 115964116984
735 188978561017
736 300647710714
737 463856467963
738 687194767356
739 962072674301
740 1236950581246
741 1374389534719
742 1681
743 3238
744 6195
745 11804
746 22429
747 42526
748 80479
749 152032
750 286689
751 539618
752 1013731
753 1900516
754 3555301
755 6635494
756 12353511
757 22937576
758 42467305
759 78381034
760 144179179
761 264241132
762 482344941
763 876609518
764 1585446895
765 2852126704
766 5100273649
767 9059696626
768 15971909619
769 27917287412
770 48318382069
771 82678120438
772 139586437111
773 231928233976
774 377957122041
775 601295421434
776 927712935931
777 1374389534716
778 1924145348605
779 2473901162494
780 2748779069439
781 1764
782 3401
783 6514
784 12427
785 23644
786 44893
787 85086
788 160991
789 304096
790 573409
791 1079266
792 2027491
793 3801060
794 7110629
795 13271014
796 24707047
797 45875176
798 84934633
799 156762090
800 288358379
801 528482284
802 964689901
803 1753219054
804 3170893807
805 5704253424
806 10200547313
807 18119393266
808 31943819251
809 55834574836
810 96636764149
811 165356240886
812 279172874231
813 463856467960
814 755914244089
815 1202590842874
816 1855425871867
817 2748779069436
818 3848290697213
819 4947802324990
820 5497558138879
821 1849
822 3568
823 6841
824 13066
825 24891
826 47324
827 89821
828 170206
829 322015
830 608224
831 1146849
832 2158562
833 4055011
834 7602148
835 14221285
836 26542054
837 49414119
838 91750376
839 169869289
840 313524202
841 576716779
842 1056964588
843 1929379821
844 3506438126
845 6341787631
846 11408506864
847 20401094641
848 36238786546
849 63887638515
850 111669149684
851 193273528309
852 330712481782
853 558345748471
854 927712935928
855 1511828488185
856 2405181685754
857 3710851743739
858 5497558138876
859 7696581394429
860 9895604649982
861 10995116277759
862 1936
863 3739
864 7176
865 13721
866 26170
867 49819
868 94684
869 179677
870 340446
871 644063
872 1216480
873 2293729
874 4317154
875 8110051
876 15204324
877 28442597
878 53084134
879 98828263
880 183500776