1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 61
16 438
17 499
18 937
19 1436
20 2373
21 389
22 2762
23 3151
24 5913
25 964
26 6877
27 7841
28 14718
29 22559
30 37277
31 59836
32 97113
33 156949
34 25462
35 182411
36 27873
37 21284
38 49157
39 7441
40 56598
41 6439
42 6337
43 12776
44 19113
45 31889
46 512
47 3241
48 3753
49 6994
50 1747
51 8741
52 1488
53 1229
54 2717
55 3946
56 6663
57 169
58 6832
59 71
60 693
61 764
62 1457
63 2221
64 3678
65 5899
66 9577
67 15476
68 2553
69 1829
70 4382
71 6211
72 1593
73 784
74 2377
75 3161
76 5538
77 8699
78 14237
79 22936
80 37173
81 619
82 37792
83 38411
84 7623
85 4634
86 12257
87 16891
88 29148
89 4639
90 33787
91 38426
92 72213
93 11639
94 83852
95 95491
96 179343
97 274834
98 454177
99 72911
100 52788
101 125699
102 178487
103 34186
104 212673
105 246859
106 459532
107 76391
108 535923
109 612314
110 1148237
111 176551
112 1324788
113 151339
114 1476127
115 1627466
116 313593
117 194159
118 57752
119 251911
120 39663
121 291574
122 331237
123 622811
124 95448
125 718259
126 81377
127 799636
128 88113
129 887749
130 975862
131 1863611
132 2839473
133 47384
134 2886857
135 2934241
136 582198
137 3516439
138 498637
139 41576
140 54213
141 95789
142 152
143 95941
144 9693
145 15634
146 25327
147 4961
148 3288
149 8249
150 11537
151 19786
152 31323
153 5119
154 36442
155 41561
156 783
157 42344
158 43127
159 85471
160 128598
161 21469
162 1567
163 2336
164 393
165 2729
166 3122
167 5851
168 8973
169 14824
170 23797
171 38621
172 62418
173 1139
174 63557
175 64696
176 128253
177 192949
178 32122
179 22571
180 54693
181 77264
182 131957
183 29221
184 161178
185 19399
186 18577
187 37976
188 56553
189 94529
190 15182
191 19711
192 34893
193 5464
194 4357
195 9821
196 14178
197 23999
198 38177
199 62176
200 1353
201 63529
202 64882
203 128411
204 193293
205 32174
206 225467
207 257641
208 48318
209 35959
210 84277
211 12236
212 96513
213 18749
214 115262
215 13411
216 128673
217 14284
218 142957
219 157241
220 3198
221 16439
222 19637
223 3676
224 23313
225 26989
226 532
227 27521
228 2853
229 3374
230 6227
231 961
232 7188
233 8149
234 15337
235 23486
236 38823
237 6239
238 4562
239 181
240 4743
241 4924
242 9667
243 14591
244 24258
245 38849
246 6317
247 45166
248 51483
249 96649
250 148132
251 244781
252 392913
253 637694
254 1367
255 63961
256 65328
257 129289
258 194617
259 32396
260 22713
261 5519
262 28232
263 33751
264 61983
265 95734
266 157717
267 253451
268 411168
269 664619
270 175787
271 8446
272 184233
273 192679
274 376912
275 569591
276 94653
277 664244
278 758897
279 1423141
280 218238
281 1641379
282 1859617
283 35996
284 1895613
285 193169
286 288782
287 481951
288 77733
289 559684
290 637417
291 119711
292 757128
293 876839
294 1633967
295 25186
296 1659153
297 1684339
298 3343492
299 527831
300 3871323
301 4399154
302 827477
303 5226631
304 65418
305 529249
306 594667
307 1123916
308 1718583
309 2842499
310 456182
311 3298681
312 3754863
313 753544
314 45847
315 799391
316 845238
317 1644629
318 2489867
319 4134496
320 6624363
321 1758859
322 8383222
323 114281
324 849753
325 96434
326 946187
327 142621
328 18888
329 16159
330 3547
331 1976
332 5523
333 7499
334 1322
335 8821
336 1143
337 9964
338 1117
339 1181
340 2298
341 3479
342 5777
343 9256
344 1533
345 1789
346 3322
347 5111
348 8433
349 13544
350 21977
351 35521
352 57498
353 9319
354 66817
355 76136
356 142953
357 21989
358 164942
359 186931
360 351873
361 53884
362 45757
363 99641
364 145398
365 24539
366 169937
367 194476
368 364413
369 558889
370 92332
371 651221
372 743553
373 1394774
374 2138327
375 353311
376 2491638
377 2844949
378 5336587
379 8181536
380 13518123
381 21699659
382 35217782
383 56917441
384 92135223
385 14952664
386 1787887
387 1674551
388 3462438
389 5136989
390 8599427
391 13736416
392 22335843
393 3672259
394 26812
395 369971
396 396783
397 766754
398 1163537
399 193291
400 1356828
401 155119
402 1511947
403 166766
404 1678713
405 1845479
406 3524192
407 5369671
408 8893863
409 14263534
410 23157397
411 3742931
412 269328
413 412259
414 681587
415 193846
416 875433
417 169279
418 144712
419 313991
420 45873
421 359864
422 45737
423 4561
424 5298
425 9859
426 15157
427 2516
428 17673
429 2189
430 19862
431 2251
432 22113
433 24364
434 46477
435 7841
436 54318
437 62159
438 116477
439 178636
440 295113
441 473749
442 768862
443 1242611
444 211473
445 145484
446 356957
447 52441
448 49398
449 11839
450 61237
451 7376
452 68613
453 75989
454 14462
455 9451
456 23913
457 33364
458 57277
459 9641
460 66918
461 76559
462 143477
463 2236
464 145713
465 147949
466 293662
467 441611
468 735273
469 1176884
470 1912157
471 38941
472 195198
473 234139
474 429337
475 663476
476 192813
477 856289
478 14912
479 87121
480 1233
481 88354
482 89587
483 177941
484 267528
485 445469
486 712997
487 1158466
488 1871463
489 329929
490 221392
491 551321
492 772713
493 132434
494 95147
495 227581
496 322728
497 5539
498 328267
499 33386
500 361653
501 39539
502 41192
503 8731
504 49923
505 58654
506 18577
507 77231
508 9588
509 86819
510 9647
511 96466
512 16113
513 112579
514 128692
515 241271
516 369963
517 611234
518 981197
519 1592431
520 2573628
521 416659
522 299287
523 715946
524 115233
525 831179
526 946412
527 1777591
528 27243
529 184834
530 21277
531 26111
532 47388
533 73499
534 12887
535 86386
536 99273
537 185659
538 284932
539 47591
540 332523
541 38114
542 37637
543 75751
544 113388
545 189139
546 32527
547 221666
548 254193
549 475859
550 7352
551 483211
552 49563
553 532774
554 582337
555 1115111
556 1697448
557 2812559
558 4517
559 281776
560 286293
561 56869
562 343162
563 431
564 343593
565 34424
566 37817
567 72241
568 1158
569 73399
570 74557
571 147956
572 222513
573 37469
574 259982
575 297451
576 557433
577 854884
578 1412317
579 226721
580 163938
581 39659
582 23597
583 63256
584 86853
585 1519
586 88372
587 89891
588 178263
589 268154
590 446417
591 714571
592 116988
593 831559
594 948547
595 17816
596 966363
597 984179
598 195542
599 1179721
600 1375263
601 2554984
602 393247
603 2948231
604 3341478
605 628979
606 397457
607 126436
608 523893
609 65329
610 589222
611 654551
612 1243773
613 1898324
614 314297
615 2212621
616 2526918
617 4739539
618 7266457
619 125996
620 7392453
621 7518449
622 149192
623 7667641
624 7816833
625 15484474
626 233137
627 15717611
628 1595748
629 17313359
630 189917
631 1753276
632 1943193
633 3696469
634 5639662
635 9336131
636 14975793
637 24311924
638 39287717
639 63599641
640 12887358
641 76486999
642 89374357
643 165861356
644 255235713
645 4219769
646 259455482
647 263675251
648 52313733
649 315988984
650 36832717
651 35282171
652 72114888
653 1739759
654 73854647
655 7559446
656 8141493
657 157939
658 8299432
659 8457371
660 1675683
661 113354
662 178937
663 292291
664 471228
665 763519
666 1234747
667 1998266
668 323313
669 2321579
670 2644892
671 4966471
672 7611363
673 12577834
674 2189197
675 1476731
676 3665928
677 5142659
678 888587
679 631246
680 1519833
681 215179
682 173512
683 388691
684 56223
685 444914
686 51137
687 49651
688 1788
689 51439
690 53227
691 14666
692 67893
693 82559
694 15452
695 9811
696 25263
697 3574
698 28837
699 32411
700 61248
701 93659
702 15497
703 19156
704 34653
705 5389
706 442
707 5831
708 6273
709 1214
710 7487
711 871
712 8358
713 9229
714 17587
715 26816
716 4443
717 31259
718 3572
719 34831
720 3843
721 38674
722 42517
723 81191
724 12378
725 93569
726 15947
727 19516
728 35463
729 54979
730 9442
731 64421
732 73863
733 138284
734 212147
735 35431
736 247578
737 2839
738 25417
739 28256
740 53673
741 81929
742 13562
743 95491
744 1953
745 97444
746 99397
747 196841
748 296238
749 49379
750 345617
751 394996
752 74613
753 46969
754 121582
755 168551
756 29133
757 197684
758 226817
759 42451
760 269268
761 311719
762 58987
763 3776
764 62763
765 66539
766 12932
767 79471
768 9243
769 88714
770 97957
771 186671
772 284628
773 471299
774 755927
775 1227226
776 1983153
777 321379
778 234532
779 555911
780 79443
781 635354
782 714797
783 135151
784 849948
785 98599
786 948547
787 147146
788 195693
789 342839
790 538532
791 881371
792 141993
793 123364
794 265357
795 388721
796 65478
797 454199
798 519677
799 973876
800 1493553
801 2467429
802 396982
803 2864411
804 3261393
805 612584
806 3873977
807 4486561
808 836538
809 532399
810 1368937
811 191336
812 156273
813 34769
814 19142
815 53911
816 7353
817 61264
818 68617
819 129881
820 198498
821 328379
822 526877
823 855256
824 1382133
825 2237389
826 3619522
827 5856911
828 9476433
829 15333344
830 2489777
831 17823121
832 2312898
833 213619
834 2526517
835 274136
836 28653
837 32789
838 61442
839 94231
840 155673
841 24994
842 18667
843 43661
844 62328
845 15989
846 78317
847 9436
848 87753
849 97189
850 184942
851 282131
852 46773
853 32894
854 79667
855 112561
856 192228
857 34789
858 22717
859 5756
860 28473
861 34229
862 6272
863 451
864 6723
865 7174
866 13897
867 2171
868 1668
869 3839
870 557
871 4396
872 4953
873 9349
874 1432
875 1781
876 3213
877 4994
878 827
879 5821
880 6648
881 12469
882 19117
883 31586
884 573
885 32159
886 32732
887 64891
888 97623
889 162514
890 26137
891 188651
892 214788
893 43439
894 258227
895 31666
896 289893
897 321559
898 611452
899 93311
900 74763
901 16874
902 91637
903 18511
904 11148
905 29659
906 487
907 3146
908 3633
909 6779
910 1412
911 8191
912 963
913 9154
914 1117
915 1271
916 2388
917 3659
918 647
919 436
920 183
921 619
922 82
923 71
924 153
925 224
926 377
927 61