0 1
1 1
2 3
3 2
4 7
5 6
6 12
7 10
8 21
9 22
10 36
11 36
12 59
13 63
14 93
15 98
16 142
17 156
18 218
19 238
20 327
21 358
22 482
23 528
24 696
25 769
26 996
27 1106
28 1411
29 1572
30 1978
31 2206
32 2745
33 3068
34 3776
35 4224
36 5161
37 5778
38 6999
39 7832
40 9429
41 10554
42 12612
43 14112
44 16776
45 18782
46 22190
47 24828
48 29195
49 32666
50 38220
51 42730
52 49794
53 55656
54 64598
55 72146
56 83439
57 93134
58 107346
59 119724
60 137555
61 153317
62 175626
63 195612
64 223447
65 248700
66 283330
67 315112
68 358104
69 397974
70 451200
71 501048
72 566837
73 628980
74 710061
75 787274
76 887035
77 982740
78 1105150
79 1223430
80 1373394
81 1519264
82 1702538
83 1881912
84 2105527
85 2325647
86 2597898
87 2867314
88 3198242
89 3527364
90 3928866
91 4329962
92 4816272
93 5304156
94 5892154
95 6484356
96 7194132
97 7911666
98 8767056
99 9634794
100 10664065
101 11711580
102 12948138
103 14210432
104 15693855
105 17212408
106 18989328
107 20813136
108 22938726
109 25125672
110 27664662
111 30282892
112 33311708
113 36441642
114 40049772
115 43785826
116 48078693
117 52532046
118 57632878
119 62933628
120 68987130
121 75288146
122 82463313
123 89943170
124 98437883
125 107305908
126 117350996
127 127851264
128 139716177
129 152133998
130 166132612
131 180800280
132 197298176
133 214603172
134 234025560
135 254418506
136 277259664
137 301264632
138 328098364
139 356323898
140 387816177
141 420968654
142 457891186
143 496789512
144 540036567
145 585629531
146 636235332
147 689620850
148 748781983
149 811230204
150 880328324
151 953306520
152 1033937649
153 1119140604
154 1213144856
155 1312526892
156 1422026253
157 1537841234
158 1665279018
159 1800122122
160 1948311349
161 2105170884
162 2277346268
163 2459658102
164 2659537722
165 2871251920
166 3103105556
167 3348757908
168 3617486303
169 3902283570
170 4213507266
171 4543420392
172 4903581593
173 5285454528
174 5701931608
175 6143602638
176 6624841863
177 7135283166
178 7690945558
179 8280419688
180 8921550716
181 9601789421
182 10341006585
183 11125411612
184 11977122834
185 12880995876
186 13861639702
187 14902438886
188 16030763946
189 17228398412
190 18525770584
191 19902927252
192 21393685637
193 22976206192
194 24688056642
195 26505354298
196 28469821432
197 30555360924
198 32808290786
199 35200119166
200 37782251784
201 40523607606
202 43481217934
203 46621207752
204 50006831355
205 53601200778
206 57474447858
207 61586441096
208 66014915156
209 70716249108
210 75776577444
211 81148532154
212 86927529015
213 93062178218
214 99658146072
215 106659735816
216 114183934961
217 122170435850
218 130748724162
219 139853569984
220 149628256971
221 160002302214
222 171134214000
223 182947921576
224 195618733980
225 209064638598
226 223479473822
227 238774929684
228 255165285596
229 272555562186
230 291182575344
231 310944305610
232 332102422079
233 354547483800
234 378568552024
235 404048388600
236 431306251590
237 460216729032
238 491132350600
239 523919167224
240 558966371563
241 596131125068
242 635843004012
243 677949952332
244 722926029385
245 770609657700
246 821523881602
247 875497340024
248 933107018451
249 994171550272
250 1059327305922
251 1128382758072
252 1202039651946
253 1280096206564
254 1363326119469
255 1451517364946
256 1545522828597
257 1645120342212
258 1751249920122
259 1863679498384
260 1983444955785
261 2110304714038
262 2245400099432
263 2388480596604
264 2540803524298
265 2702110198937
266 2873785496118
267 3055563591852
268 3248969641434
269 3453731975916
270 3671529980744
271 3902087777458
272 4147254322893
273 4406751532620
274 4682614756658
275 4974566153460
276 5284845952983
277 5613179497320
278 5962032170460
279 6331136018170
280 6723203848283
281 7137978573336
282 7578444854108
283 8044361385624
284 8539011504279
285 9062175432870
286 9617464605982
287 10204687493568
288 10827815923409
289 11486694395962
290 12185690550810
291 12924693957320
292 13708506935870
293 14537074523568
294 15415676335402
295 16344324875032
296 17328823812432
297 18369266847550
298 19472032957890
299 20637312790044
300 21872116867080
301 23176750729866
302 24558918074058
303 26019059819082
304 27565640441792
305 29199259504872
306 30929216340196
307 32756295593206
308 34690712691807
309 36733467309966
310 38895779971434
311 41178899290368
312 43595148462310
313 46146063347013
314 48845176699326
315 51694354870324
316 54708457325824
317 57889729628364
318 61254486281834
319 64805406924842
320 68560401710118
321 72522646009430
322 76711799627474
323 81131602953144
324 85803634145328
325 90732276301176
326 95941210667130
327 101435550186770
328 107241281518527
329 113364344975964
330 119833254123906
331 126654885827358
332 133860523101945
333 141458101346064
334 149481938490550
335 157941164786628
336 166873423730242
337 176289192496714
338 186229758194061
339 196707114577954
340 207766540517654
341 219421735354548
342 231722350607096
343 244684001737968
344 258361129751268
345 272771500491852
346 287974800401006
347 303991206286608
348 320886148875889
349 338682505534524
350 357451996844388
351 377220522445154
352 398066689518061
353 420019777087920
354 443165931465978
355 467538207322674
356 493231003663020
357 520281590153504
358 548793398611312
359 578808400696512
360 610439913919882
361 643735151310056
362 678818248296894
363 715742256560070
364 754643148396870
365 795580474999326
366 838703159005816
367 884077982226346
368 931868034439398
369 982148136242888
370 1035096873923774
371 1090798000095480
372 1149447049983004
373 1211137694738572
374 1276084004957076
375 1344390659686472
376 1416291997787125
377 1491904908362796
378 1571485890883162
379 1655165370834738
380 1743224074847517
381 1835807427337414
382 1933222638298858
383 2035631743374576
384 2143370899206673
385 2256620529212034
386 2375748425448078
387 2500955356042386
388 2632643683287955
389 2771036674724088
390 2916574465668320
391 3069505194836192
392 3230310265591149
393 3399265297397772
394 3576896774941208
395 3763510668918552
396 3959682705535353
397 4165752362846028
398 4382349146527890
399 4609849511397714
400 4848941692229831
401 5100042932742492
402 5363905594546900
403 5640991898107264
404 5932124217902634
405 6237814349790902
406 6558961098487644
407 6896130883937268
408 7250305937364700
409 7622112843403704
410 8012624885780652
411 8422534892929482
412 8853015513004129
413 9304832485806468
414 9779266881802402
415 10277164663463602
416 10799925193752897
417 11348482672392758
418 11924365508275564
419 12528604921759260
420 13162870082521369
421 13828298854574599
422 14526713928544404
423 15259370352439582
424 16028258235378386
425 16834761351131172
426 17681052361363448
427 18568656400945022
428 19499945163044061
429 20476598972220726
430 21501206493976222
431 22575618373706568
432 23702659779587603
433 24884368229581660
434 26123826652265841
435 27423277540047336
436 28786084717356468
437 30214715442718476
438 31712839611905048
439 33283170884381742
440 34929712619883297
441 36655448521974798
442 38464745215082682
443 40360882279652616
444 42348622022160779
445 44431568117727800
446 46614913813437450
447 48902617695924144
448 51300342297915430
449 53812434764490240
450 56445068609598214
451 59203016266283736
452 62093007564106203
453 65120280309209884
454 68292169930446834
455 71614423345488408
456 75095035153945203
457 78740309098974936
458 82558957175206212
459 86557891991611192
460 90746606212152519
461 95132678058240300
462 99726449616438404
463 104536226586916754
464 109573275177071583
465 114846695999321366
466 120368760528624680
467 126149437777253400
468 132202092629523865
469 138537642565914130
470 145170641607679548
471 152113042925840314
472 159380693632891025
473 166986677586101544
474 174948247862694010
475 183279722449456564
476 191999882932423623
477 201124394046901558
478 210673698913749500
479 220664931603785208
480 231120341161152452
481 242058664402914521
482 253504112997521286
483 265477171672992996
484 278004184766783200
485 291107542841779944
486 304815907405116016
487 319153746629204072
488 334152239354227104
489 349838118167622518
490 366245296370481750
491 383402974081678620
492 401348034566887325
493 420112366288041940
494 439736077877935500
495 460253986148881600
496 481709702052047131
497 504141231575784228
498 527595988270675146
499 552115450703252742
500 577751160562134012
501 604548376871292752
502 632563122335107732
503 661844770850484024
504 692454208606178562
505 724445287548657914
506 757884171841858116
507 792829585829855842
508 829353420794098934
509 867519701598758940
510 907406533274851374
511 949083705923012198
512 992636065514710590
513 1038139671741245498
514 1085686682575883678
515 1135359974588603400
516 1187259636267090779
517 1241475954839818186
518 1298117619135026484
519 1357282971161938676
520 1419090025404609914
521 1483645877274566988
522 1551078652218739622
523 1621504956667985008
524 1695063877197683598
525 1771882352724478590
526 1852111351223644510
527 1935889034660651364
528 2023379248457265201
529 2114732342951943192
530 2210126118947486034
531 2309724161361354890
532 2413719392801140234
533 2522289766457831136
534 2635644588774586592
535 2753977409535548262
536 2877515284340297772
537 3006468690211879708
538 3141083908801163754
539 3281589785659191984
540 3428253425895651666
541 3581323604494045376
542 3741089977579538889
543 3907822939776283600
544 4081836566326193224
545 4263424701453493086
546 4452927859367144544
547 4650665314881525602
548 4857006204856971957
549 5072297378878798174
550 5296938956998872268
551 5531307684069814860
552 5775837214774148142
553 6030936700190758320
554 6297076087098323454
555 6574699649487865394
556 6864316606037127844
557 7166409292513194696
558 7481529419199746154
559 7810200562425825066
560 8153020402628554968
561 8510557194528280456
562 8883458346494719770
563 9272340509128836768
564 9677904877718852992
565 10100820518109705074
566 10541846796361011360
567 11001709538742648136
568 11481231016295912731
569 11981198512508365212
570 12502502315412824572
571 13045996241914557416
572 13612644116403052578
573 14203371774745259148
574 14819222536222484980
575 15461200182804283296
576 16130433960625012953
577 16828012001223158378
578 17555156419841549712
579 18313046614787824172
580 19103005062651496201
581 19926309899712474588
582 20784392048833874934
583 21678636452841716424
584 22610591204453117013
585 23581756765658105840
586 24593807810709653366
587 25648369727677271808
588 26747253925345198917
589 27892220873148821112
590 29085229665943907718
591 30328186816395081418
592 31623210917091373356
593 32972366354987019288
594 34377943958401677550
595 35842178756224284920
596 37367547548065024371
597 38956469781463705790
598 40611623037021191816
599 42335626044699611568
600 44131373132287009372
601 46001698346864818634
602 47949729974630567388
603 49978534675617093756
604 52091493245866418999
605 54291923612329958088
606 56583479074848596750
607 58969748943703549130
608 61454680568982259626
609 64042156335287898254
610 66736440860076377742
611 69541732988408860488
612 72462639619916185877
613 75503701270979401215
614 78669894072359963934
615 81966127386639029122
616 85397775605444768198
617 88970146226136444852
618 92689043169241116264
619 96560203630036641290
620 100589894733497238198
621 104784317383347159244
622 109150238173817083354
623 113694358360694439912
624 118423983056751973113
625 123346353346016629378
626 128469354903187262550
627 133800811163552434008
628 139349233626337734349
629 145123073878095256212
630 151131517966080981732
631 157383694952264781508
632 163889517875843498307
633 170658846387918048768
634 177702376962497280346
635 185030757028079393400
636 192655527234346754417
637 200588184355978292792
638 208841178578110293648
639 217426922299379565594
640 226358845563525207589
641 235650347732494224216
642 245315914364760401676
643 255370008564958115208
644 265828252792034753250
645 276706256518857755070
646 288020866645724156534
647 299788927921309691688
648 312028605839812695333
649 324758076082986594770
650 337996923992885009028
651 351764759093094947330
652 366082695454199247796
653 380971887140162567016
654 396455094020895639426
655 412555133766551481392
656 429296537911537703067
657 446703915784651647420
658 464803705892274502992
659 483622446925281225852
660 503188629806598144266
661 523530870655994576746
662 544679869139499101415
663 566666477999940828438
664 589523773653606608638
665 613285016607007264428
666 637985840570497188956
667 663662097779567571432
668 690352173236736427284
669 718094708637899918464
670 746931048713591459810
671 776902837126860583536
672 808054602263888483097
673 840431218118621640660
674 874080637281762963708
675 909051209458191045728
676 945394569823519074465
677 983162807432217449208
678 1022411517553394521730
679 1063196811819646352256
680 1105578543619567596864
681 1149617151408638096374
682 1195377066726487965914
683 1242923381640635647536
684 1292325449472919829532
685 1343653366873498582039
686 1396981777884532667070
687 1452386160644479926498
688 1509946845989397051566
689 1569745098264980698428
690 1631867360268317078634
691 1696401117096171027034
692 1763439379864112870715
693 1833076320942874550716
694 1905412009559258702320
695 1980547806166705842900
696 2058591363734850640078
697 2139651768364269877384
698 2223844820810906560770
699 2311287909786927066232
700 2402105589044271621835
701 2496424169101982618916
702 2594377606031951455776
703 2696101796616496682968
704 2801740795840954034415
705 2911440799711867179254
706 3025356709367695892246
707 3143645784976093946916
708 3266474575327911743866
709 3394012225379699486276
710 3526437791199858772458
711 3663933182827911123042
712 3806690885497575886887
713 3954906518545344824508
714 4108786984946182796068
715 4268542626018541746958
716 4434395822477020322247
717 4606572723646821805406
718 4785312324467106786970
719 4970857746842835570456
720 5163465818325698129409
721 5363397882092770669128
722 5570929904392173835980
723 5786342788443585797582
724 6009933039166449225630
725 6242002555044376975680
726 6482869880158529501710
727 6732859446743673424946
728 6992313446131896802731
729 7261580493349526973424
730 7541028150240761290238
731 7831030982008940772132
732 8131983767539932400581
733 8444288916275087117764
734 8768370402594848425086
735 9104660509820977534892
736 9453614527456290807417
737 9815696787446794776996
738 10191396165108640820722
739 10581211371033284622040
740 10985667298672582632357
741 11405299533438028682798
742 11840671592164847139642
743 12292358609036053012728
744 12760965514511851748972
745 13247109855696433634586
746 13751440964805942025452
747 14274621869486474078074
748 14817349503508339347619
749 15380335660333061040300
750 15964328301470181756448
751 16570091504274668807576
752 17198427926291762380869
753 17850157695839075640176
754 18526142093702163441494
755 19227261332512871044416
756 19954439520350717722005
757 20708621272265259512228
758 21490798023694032490530
759 22301983414686504128020
760 23143241024576214604517
761 24015658466541394571994
762 24920376618675924085824
763 25858562363461076562466
764 26831439394275792758391
765 27840259531148830150488
766 28886335185843381453756
767 29971009181902867803432
768 31095688965747824279804
769 32261814855514644622668
770 33470896090124644654620
771 34724477427736435022208
772 36024177129498877810975
773 37371651824586773905464
774 38768636530342832960860
775 40216907696835631391430
776 41718325370342581020825
777 43274794326150324467870
778 44888308487843944276676
779 46560910052655086508144
780 48294736284815423395578
781 50091976533137831036376
782 51954921522778605778734
783 53885918159903214459556
784 55887421452596464336609
785 57961946992406979926028
786 60112125641863057346774
787 62340653577399556043794
788 64650349887995505475782
789 67044104058453062695720
790 69524936631088292488952
791 72095944002543844866264
792 74760362308254270570592
793 77521509399920812622692
794 80382852120656136399819
795 83347945323919833178120
796 86420502715843857418553
797 89604332769808773216228
798 92903413321481458130808
799 96321824226292594244002
800 99863825902203573357435
801 103533788570111973873054
802 107336274949328186666262
803 111275965913374480954248
804 115357747553617076058935
805 119586633075021494354970
806 123967854454378048207938
807 128506780392317348885642
808 133209012804112286124892
809 138080300635627228576572
810 143126641436805474065082
811 148354190840208574869274
812 153769369480033447891152
813 159378767922477560462888
814 165189259206505090906266
815 171207899005432923512172
816 177442044079711937748439
817 183899247438849767082432
818 190587383011225190113536
819 197514535564728556262162
820 204689131914119102516888
821 212119825347553382249748
822 219815633708264235770498
823 227785818062442164426464
824 236040028009098919627035
825 244588174312545674111420
826 253440581812244626348050
827 262607855730370176205512
828 272101042572290688591769
829 281931489806382280831354
830 292111015165565001345162
831 302651759382640811096504
832 313566364324080243613165
833 324867818449652630392800
834 336569644231470492873794
835 348685735991546890245610
836 361230557082006343865151
837 374218969738415456343488
838 387666442521115816436132
839 401588871805703903993544
840 416002800010689328732034
841 430925228329320615402323
842 446373846295281529313952
843 462366835342142989351612
844 478923110286643037126316
845 496062113283361910827956
846 513804067834353662982116
847 532169762687161774654694
848 551180819010250814714541
849 570859463762171807535078
850 591228810704453484862648
851 612312622748558271137124
852 634135607511709956812187
853 656723168126218376827920
854 680101714079223839028858
855 704298399945977403268130
856 729341452291755207241684
857 755259895766725215806484
858 782083896887414866309292
859 809844476905837908859704
860 838573873328978056755954
861 868305238948852277722174
862 899073022001598495359884
863 930912650718075584074752
864 963860933069415361480925
865 997955726169563331970352
866 1033236356601681265813008
867 1069743273974675044393786
868 1107518492874724915700113
869 1146605229847283735562924
870 1187048368070385494146000
871 1228894077001784868086494
872 1272190300925672900315871
873 1316986360471520394537692
874 1363333466243542677158074
875 1411284301383358439480856
876 1460893561552127779926357
877 1512217517673295031771034
878 1565314583600918880014664
879 1620244858141483342366392
880 1677070721808693882955772
881 1735856357184562468695204
882 1796668376231016742461300
883 1859575318010141065131288
884 1924648308096500386810407
885 1991960532634493857111740
886 2061587931472504336496032
887 2133608647491739756972584
888 2208103755164363469580452
889 2285156684042902589009706
890 2364853984529584319131674
891 2447284724368322277361260
892 2532541293501778251916131
893 2620718772359035646942352
894 2711915777770634839811920
895 2806233801794246658068622
896 2903778100756311517860162
897 3004657003305271118305272
898 3108982844751708256311758
899 3216871242983917980532368
900 3328442080386837473558884
901 3443818746197871828188506
902 3563129168398676706820986
903 3686505021030132140815066
904 3814082808570460318978615
905 3946003036666993630393404
906 4082411351639457027725586
907 4223457673022634792593518
908 4369297390965213919978623
909 4520090458911545254978720
910 4676002651804541054328732
911 4837204617166378767319188
912 5003873197158894603509945
913 5176190436252217144186318
914 5354344970348240650446342
915 5538530989152727417764792
916 5728949695727134929531695
917 5925808221603612896290320
918 6129321160298073025253134
919 6339709433128653767721744
920 6557201900398852143055575
921 6782034175798356929828272
922 7014450319149722539511060
923 7254701597185902973411056
924 7503048261947770154984441
925 7759758255645135677799429
926 8025109078995856162959948
927 8299386437786529747330652
928 8582886205657465201198761
929 8875913009885503845373812
930 9178782293343259640932580
931 9491818836929566313414758
932 9815358925666647360472326
933 10149748805103441301528844
934 10495346956761287163530916
935 10852522485731759720619432
936 11221657510940635997676576
937 11603145481054796676112578
938 11997393685306282856736609
939 12404821494712212482603690
940 12825862999486281506038460
941 13260965172461426477984592
942 13710590639415843343005206
943 14175215761470224775061864
944 14655333544969965679253088
945 15151451639507140412205966
946 15664095394330778616671272
947 16193805768518252647240308
948 16741142541232115158512458
949 17306682130436168960086200
950 17891020964681176571122218
951 18494773206627518483024610
952 19118574294423968796239039
953 19763078566161447394940424
954 20428962979309906006891410
955 21116924632086187600883328
956 21827684669834825802424545
957 22561985699147382763566990
958 23320595890514625041377388
959 24104306280884871111765072
960 24913935082378607690553600
961 25750324868819292275164516
962 26614347100788110233131696
963 27506899191502309771664808
964 28428909258998618010667322
965 29381333066571501271905300
966 30365159013409964758119082
967 31381404944641108059568054
968 32431123392307891819288242
969 33515398249891979171513036
970 34635350276110894855474394
971 35792133628618403944903248
972 36986941643719707844401927
973 38221003223767514609893196
974 39495588906544980114034506
975 40812007100691187585638538
976 42171610459184987606675907
977 43575791956944854851696752
978 45025991583564226739153516
979 46523692257037687692275128
980 48070426851651547824765129
981 49667773941591074821168700
982 51317365180680677006401070
983 53020880869425537476252472
984 54780057704125739414085265
985 56596684160700246181048616
986 58472608631570600541322530
987 60409734619405853884106682
988 62410029281086147116349044
989 64475518424294052674910972
990 66608295478828575475685144
991 68810516288751594026502856
992 71084408532330880129797267
993 73432266302230089294798780
994 75856459996417683512493140
995 78359430678665440381695048
996 80943700463871184696421807
997 83611866650904296501544082
998 86366612626956556759686312
999 89210701764543912755879338
1000 92146988870724290802345961