0 1
1 0
2 0
3 2
4 2
5 4
6 4
7 6
8 6
9 8
10 12
11 14
12 18
13 24
14 32
15 38
16 50
17 60
18 76
19 90
20 110
21 136
22 164
23 194
24 234
25 280
26 336
27 402
28 474
29 564
30 668
31 790
32 926
33 1096
34 1276
35 1494
36 1754
37 2040
38 2368
39 2758
40 3186
41 3692
42 4268
43 4922
44 5670
45 6528
46 7492
47 8594
48 9858
49 11272
50 12888
51 14722
52 16786
53 19108
54 21756
55 24734
56 28086
57 31864
58 36108
59 40870
60 46250
61 52248
62 58992
63 66550
64 75018
65 84468
66 95052
67 106858
68 120046
69 134752
70 151148
71 169410
72 189754
73 212376
74 237512
75 265482
76 296506
77 330932
78 369180
79 411534
80 458454
81 510440
82 567948
83 631574
84 701922
85 779664
86 865472
87 960278
88 1064818
89 1180132
90 1307268
91 1447306
92 1601494
93 1771296
94 1958044
95 2163466
96 2389282
97 2637400
98 2909896
99 3209146
100 3537482
101 3897636
102 4292652
103 4725534
104 5199822
105 5719488
106 6288204
107 6910678
108 7591786
109 8336528
110 9150728
111 10040598
112 11012586
113 12074100
114 13233092
115 14497698
116 15877358
117 17382160
118 19022604
119 20810442
120 22758546
121 24880088
122 27190232
123 29704938
124 32441138
125 35417740
126 38655052
127 42174238
128 45999286
129 50155616
130 54670116
131 59572534
132 64895058
133 70671360
134 76938872
135 83737710
136 91110386
137 99103380
138 107767172
139 117154498
140 127324030
141 138338144
142 150263244
143 163171882
144 177142170
145 192256688
146 208605736
147 226286266
148 245401162
149 266062556
150 288390724
151 312513310
152 338569342
153 366707712
154 397086804
155 429878478
156 465266826
157 503447968
158 544633928
159 589052206
160 636944834
161 688573476
162 744218164
163 804177602
164 868773702
165 938351496
166 1013278188
167 1093949626
168 1180789666
169 1274249616
170 1374815376
171 1483007274
172 1599378274
173 1724524556
174 1859082532
175 2003731174
176 2159198614
177 2326264400
178 2505758052
179 2698570350
180 2905652682
181 3128019040
182 3366755576
183 3623023694
184 3898059370
185 4193187116
186 4509820868
187 4849466706
188 5213736222
189 5604349896
190 6023138916
191 6472063018
192 6953211754
193 7468810288
194 8021236608
195 8613027218
196 9246881178
197 9925681292
198 10652501476
199 11430612342
200 12263504854
201 13154899392
202 14108753348
203 15129289662
204 16221005378
205 17388684312
206 18637427016
207 19972664542
208 21400171330
209 22926101820
210 24557007484
211 26299850018
212 28162047830
213 30151492360
214 32276570468
215 34546211826
216 36969914082
217 39557765840
218 42320506832
219 45269553186
220 48417030938
221 51775838924
222 55359687284
223 59183131878
224 63261652766
225 67611693896
226 72250712804
227 77197264062
228 82471054314
229 88092995256
230 94085308016
231 100471581150
232 107276842458
233 114527672780
234 122252284092
235 130480596938
236 139244379678
237 148577334936
238 158515201972
239 169095908674
240 180359683554
241 192349169008
242 205109607856
243 218688967922
244 233138085010
245 248510872660
246 264864477028
247 282259441478
248 300759956534
249 320434035512
250 341353722844
251 363595368798
252 387239855202
253 412372827224
254 439085023424
255 467472538198
256 497637097442
257 529686444364
258 563734646428
259 599902425898
260 638317604686
261 679115469160
262 722439160564
263 768440193746
264 817278883930
265 869124813832
266 924157428256
267 982566546098
268 1044552904666
269 1110328856132
270 1180118965484
271 1254160655238
272 1332705011406
273 1416017492920
274 1504378683196
275 1598085233206
276 1697450684618
277 1802806371624
278 1914502494576
279 2032909106422
280 2158417153986
281 2291439739532
282 2432413266860
283 2581798672266
284 2740082876758
285 2907780146288
286 3085433513556
287 3273616485890
288 3472934614594
289 3684027184936
290 3907569171976
291 4144273096946
292 4394890989378
293 4660216672372
294 4941087910892
295 5238388729278
296 5553052029014
297 5886062142632
298 6238457489372
299 6611333657206
300 7005846342170
301 7423214476392
302 7864723779792
303 8331730203510
304 8825663566202
305 9348031675780
306 9900424326300
307 10484517557530
308 11102078402878
309 11754969569312
310 12445154369356
311 13174702233074
312 13945794150026
313 14760728407880
314 15621926961976
315 16531941772570
316 17493461461466
317 18509318703220
318 19582497560364
319 20716141235038
320 21913560603110
321 23178242737496
322 24513859905340
323 25924279425046
324 27413573565762
325 28986029973184
326 30646163060912
327 32398725496326
328 34248720276418
329 36201413888724
330 38262349618692
331 40437361526090
332 42732589669830
333 45154495485840
334 47709877989036
335 50405891322330
336 53250062571986
337 56250310504184
338 59414965808328
339 62752791698058
340 66273005590010
341 69985302417652
342 73899878487036
343 78027456466798
344 82379312332046
345 86967302853408
346 91803894508860
347 96902194485254
348 102275982468282
349 107939743942016
350 113908705971480
351 120198873797238
352 126827069334090
353 133810972293060
354 141169162443540
355 148921163938162
356 157087492682174
357 165689705012832
358 174750448801484
359 184293517900522
360 194343908277730
361 204927876785160
362 216073003865608
363 227808258077402
364 240164063828066
365 253172373374348
366 266866741121132
367 281282401509934
368 296456351773446
369 312427437350096
370 329236441477748
371 346926180176934
372 365541600522066
373 385129883503616
374 405740553167496
375 427425589423678
376 450239546284994
377 474239677040228
378 499486063843636
379 526041753432162
380 553972900738398
381 583348917576656
382 614242628453116
383 646730435166106
384 680892487436746
385 716812861573184
386 754579749149576
387 794285652658234
388 836027590351354
389 879907312373932
390 926031525037780
391 974512125519150
392 1025466449420814
393 1079017527643168
394 1135294355263796
395 1194432174889022
396 1256572770788122
397 1321864776777168
398 1390464000381368
399 1462533759554174
400 1538245234971170
401 1617777840809284
402 1701319609972068
403 1789067597128850
404 1881228302533398
405 1978018112664248
406 2079663760940316
407 2186402812203066
408 2298484166286498
409 2416168584695904
410 2539729243963232
411 2669452311092346
412 2805637545213170
413 2948598929513020
414 3098665328406244
415 3256181174688870
416 3421507190730214
417 3595021138882560
418 3777118605723348
419 3968213825072734
420 4168740534213658
421 4379152868843648
422 4599926301682104
423 4831558619299678
424 5074570942714106
425 5329508797677948
426 5596943228329876
427 5877471961008962
428 6171720623810622
429 6480344016141000
430 6804027434891156
431 7143488063956762
432 7499476420574874
433 7872777866266912
434 8264214189071056
435 8674645251009266
436 9104970708438554
437 9556131813504828
438 10029113289525588
439 10524945289508486
440 11044705445947654
441 11589521005251536
442 12160571056173572
443 12759088861737630
444 13386364287163218
445 14043746334839784
446 14732645795802072
447 15454538010981934
448 16210965753291026
449 17003542241848380
450 17833954280670620
451 18703965534639538
452 19615419954439334
453 20570245343367160
454 21570457079279636
455 22618162005210050
456 23715562480754018
457 24864960609612432
458 26068762657276064
459 27329483651532594
460 28649752182207274
461 30032315415723164
462 31480044317247396
463 32995939098165990
464 34583134906222718
465 36244907751084696
466 37984680684795796
467 39806030256360686
468 41712693233025754
469 43708573610032136
470 45797749929633232
471 47984482902406110
472 50273223354777610
473 52668620525418556
474 55175530704209452
475 57799026239800154
476 60544404940750446
477 63417199864638072
478 66423189523633748
479 69568408533904498
480 72859158704291154
481 76302020595076928
482 79903865577723136
483 83671868391104034
484 87613520228868850
485 91736642391365364
486 96049400499265428
487 100560319306466326
488 105278298149682406
489 110212627032530536
490 115373003386405484
491 120769549548196094
492 126412830955687938
493 132313875105668648
494 138484191320470032
495 144935791324285670
496 151681210680317842
497 158733531138072124
498 166106403895389020
499 173814073830344202
500 181871404758846142
501 190293905723727032
502 199097758377982052
503 208299845521727170
504 217917780803924746
505 227969939655837416
506 238475491524177120
507 249454433416848194
508 260927624837041738
509 272916824178993012
510 285444726604503644
511 298535003481589814
512 312212343469070542
513 326502495268465080
514 341432312135720044
515 357029798243093542
516 373324156920436730
517 390345840876019448
518 408126604499030496
519 426699558277243062
520 446099225443244770
521 466361600959636284
522 487524212886837084
523 509626186256170842
524 532708309573104710
525 556813104000940160
526 581984895362131700
527 608269889094944450
528 635716248225915410
529 664374174509164792
530 694295992886855960
531 725536239340042178
532 758151752300105938
533 792201767788843956
534 827748018371809420
535 864854836110792110
536 903589259704128678
537 944021145912312312
538 986223285475951948
539 1030271523734596870
540 1076244886061093786
541 1124225708339656488
542 1174299772720975264
543 1226556448785307590
544 1281088840368626378
545 1337993938309279860
546 1397372779267784172
547 1459330610902029530
548 1523977063684516190
549 1591426329536650480
550 1661797347594355580
551 1735213997422270690
552 1811805299879316122
553 1891705625982706488
554 1975054914124109048
555 2061998895870087546
556 2152689330731737354
557 2247284250297723044
558 2345948211994563740
559 2448852562903254190
560 2556175714069017302
561 2668103425606193784
562 2784829103074722300
563 2906554105613363046
564 3033488066173931858
565 3165849224386246544
566 3303864772591716160
567 3447771215439548598
568 3597814743631001218
569 3754251622412684724
570 3917348595263511860
571 4087383303428119034
572 4264644721963116246
573 4449433612801804192
574 4642062995560906492
575 4842858636832556986
576 5052159558531191250
577 5270318566103195208
578 5497702797420657944
579 5734694293009168410
580 5981690588502044810
581 6239105330238818116
582 6507368914738083996
583 6786929153040590350
584 7078251960938421406
585 7381822075919282480
586 7698143801926966956
587 8027741783073890486
588 8371161807233655210
589 8728971640743313344
590 9101761895472785848
591 9490146929311373478
592 9894765781434733402
593 10316283143752098996
594 10755390369713590404
595 11212806521995497698
596 11689279460615053374
597 12185586972808579552
598 12702537946350630492
599 13240973588048197690
600 13801768688900217938
601 14385832937794066200
602 14994112285660251896
603 15627590361763604058
604 16287289944206640258
605 16974274486784338492
606 17689649704068522844
607 18434565217035203934
608 19210216261603632758
609 20017845462202326336
610 20858744672923314196
611 21734256888905164134
612 22645778230308727522
613 23594760001735927632
614 24582710830020662424
615 25611198883045578958
616 26681854172744031186
617 27796370945549362692
618 28956510163253510452
619 30164102077792683090
620 31421048903576338414
621 32729327590680048480
622 34090992702804161772
623 35508179404018740202
624 36983106558004959082
625 38518079944129747232
626 40115495594813973240
627 41777843258348328170
628 43507709991964112138
629 45307783890120208028
630 47180857952640414500
631 49129834098043698158
632 51157727327573657486
633 53267670045102828208
634 55462916538842279492
635 57746847630971795086
636 60122975500964691914
637 62594948689194716928
638 65166557287607512184
639 67841738323906141022
640 70624581346555598578
641 73519334218138795316
642 76530409124256490068
643 79662388806075222850
644 82920033024887224038
645 86308285266696446456
646 89832279695826152604
647 93497348366829130250
648 97309028703629784274
649 101273071255879733232
650 105395447742824815920
651 109682359394628959274
652 114140245602231552146
653 118775792887156606844
654 123595944202355940916
655 128607908576365465366
656 133819171113446188886
657 139237503362042767568
658 144870974065178685732
659 150727960306841135486
660 156817159068082535706
661 163147599207934254704
662 169728653884726231976
663 176570053433071031630
664 183681898713260099626
665 191074674950353260364
666 198759266079935859508
667 206746969619106822562
668 215049512081856790862
669 223679064957704650456
670 232648261274172733988
671 241970212764329637162
672 251658527660383532810
673 261727329136115671520
674 272191274421701820656
675 283065574614215708322
676 294366015209082715370
677 306108977378565974188
678 318311460023166442948
679 330991102623923669910
680 344166208924524709510
681 357855771471947800176
682 372079497046658912340
683 386857833014364438510
684 402211994631230487874
685 418163993336902588152
686 434736666070792192840
687 451953705647028258542
688 469839692226107230258
689 488420125922506550284
690 507721460587549692908
691 527771138809616994850
692 548597628175201756566
693 570230458834363123176
694 592700262417203488500
695 616038812349504550594
696 640279065615836972562
697 665455206021739684864
698 691602689008262051216
699 718758288072420202850
700 746960142850684103866
701 776247808924459376060
702 806662309406941689636
703 838246188374517469014
704 871043566207988009134
705 905100196909385691944
706 940463527464299781156
707 977182759321916134366
708 1015308912065643334298
709 1054894889351657912168
710 1095995547195254072640
711 1138667764685693737998
712 1182970517215110221626
713 1228964952309795189612
714 1276714468153253574972
715 1326284794895608130554
716 1377744078847057748366
717 1431162969654327469160
718 1486614710564697549348
719 1544175231885633352194
720 1603923247749531305954
721 1665940356299191554992
722 1730311143413452610368
723 1797123290094153799746
724 1866467683642235053474
725 1938438532754970398468
726 2013133486678400490084
727 2090653758556205937606
728 2171104253120897910742
729 2254593698875617863400
730 2341234784922617498220
731 2431144302599601332878
732 2524443292087937859122
733 2621257194165148839064
734 2721716007279769965184
735 2825954450129899063478
736 2934112129935890341010
737 3046333716603919605052
738 3162769122980845521516
739 3283573691410724889978
740 3408908386810252703150
741 3538939996484631646984
742 3673841336916177940756
743 3813791467765571083138
744 3958975913330520584138
745 4109586891718332915928
746 4265823551997258813776
747 4427892219597047199026
748 4596006650241827414650
749 4770388292707744873988
750 4951266560704032745148
751 5138879114190029270390
752 5333472150450897218782
753 5535300705261890427304
754 5744628964486051352636
755 5961730586461523164470
756 6186889035542658350314
757 6420397927175493409592
758 6662561384900571231168
759 6913694409685168412582
760 7174123262004758922994
761 7444185857107282676876
762 7724232173903959517228
763 8014624677949760898666
764 8315738758991772752774
765 8627963183575140687904
766 8951700563217337054532
767 9287367838678215161234
768 9635396780866086481314
769 9996234508943075629288
770 10370344026211343133224
771 10758204774376153049890
772 11160313206806779714354
773 11577183381436488850564
774 12009347573958888021596
775 12457356912005245883934
776 12921782031009611719606
777 13403213752486599275560
778 13902263785476351984588
779 14419565451935804095974
780 14955774436875368669226
781 15511569564072611852120
782 16087653598221469336400
783 16684754074397947110006
784 17303624155758551194874
785 17945043520417478539220
786 18609819278473450083180
787 19298786920195680301802
788 20012811296411130669038
789 20752787632162992909920
790 21519642574752334435532
791 22314335277310892120466
792 23137858519083808301946
793 23991239863647001778584
794 24875542856323451706280
795 25791868262096987489322
796 26741355345372171350938
797 27725183192972523427508
798 28744572081807294466188
799 29800784892691708422222
800 30895128571853478104342
801 32028955641700630429736
802 33203665762485312547980
803 34420707346550975136694
804 35681579226897087800738
805 36987832381860728831776
806 38341071717772262604192
807 39742957911494246045110
808 41195209314823747452754
809 42699603922802026097668
810 44257981408032880085892
811 45872245223188673730986
812 47544364773953049057350
813 49276377664712868056032
814 51070392019396745311004
815 52928588879934517922026
816 54853224684882180754434
817 56846633830849599999544
818 58911231319452730416520
819 61049515492589831283946
820 63264070858942366849674
821 65557571014694158220356
822 67932781661548168910188
823 70392563725230931977374
824 72939876577776599152462
825 75577781366977413056416
826 78309444456508216465372
827 81138140980344683893366
828 84067258515199516426730
829 87100300874832985841200
830 90240892030217148978728
831 93492780159648516066070
832 96859841833048303070602
833 100346086334824394761380
834 103955660129796469350212
835 107692851476843517101218
836 111562095195081118944718
837 115567977587516301581584
838 119715241527300124890860
839 124008791711860839265930
840 128453700090355151596514
841 133055211470063552808440
842 137818749307534161284728
843 142749921690449938526954
844 147854527516400112217042
845 153138562874932456157580
846 158608227639450742157292
847 164269932275746842776942
848 170130304874171720875798
849 176196198412656198073184
850 182474698258038473383172
851 188973129913390913637334
852 195699067019266123493650
853 202660339617051178619008
854 209865042682877350047528
855 217321544940782813921006
856 225038497964119814596434
857 233024845574481112048084
858 241289833547695669493316
859 249843019636764893854562
860 258694283921921412509726
861 267853839498294829963760
862 277332243512020264138924
863 287140408555965871768330
864 297289614436588214123162
865 307791520323808184253968
866 318658177296173485885416
867 329902041293939056438362
868 341535986493116504457178
869 353573319113952614624028
870 366027791677698495771716
871 378913617725989525555838
872 392245487017604572591038
873 406038581217813732786656
874 420308590096025278446996
875 435071728247933481768510
876 450344752358853118553642
877 466144979025474381282304
878 482490303153809872860872
879 499399216951636692754286
880 516890829534335617122018
881 534984887163618380362692
882 553701794139217450725764
883 573062634364267005298210
884 593089193605749189527206
885 613803982472019526727720
886 635230260130140668252492
887 657392058786460162065402
888 680314208954569870904738
889 704022365535566240986240
890 728543034736304282028752
891 753903601852107742063786
892 780132359941252298041634
893 807258539419385160448012
894 835312338602888733063492
895 864324955231129128055206
896 894328618998457302052934
897 925356625127755772137520
898 957443369018343709108868
899 990624382002067464832750
900 1024936368242417858385354
901 1060417242812629476223904
902 1097106170989827510445016
903 1135043608803398603460254
904 1174271344876979629776874
905 1214832543604672676517164
906 1256771789703311960605668
907 1300135134183938136214322
908 1344970141786964134036094
909 1391325939926850010856904
910 1439253269193557086940052
911 1488804535459504709934186
912 1540033863642213563027882
913 1592997153174405860520496
914 1647752135234922473043392
915 1704358431795415812177586
916 1762877616539510422590042
917 1823373277712861359682332
918 1885911082964290900826756
919 1950558846240076746577046
920 2017386596795365648223670
921 2086466650388601994356640
922 2157873682726928182474628
923 2231684805232591206348510
924 2307979643202486693910834
925 2386840416435228647430232
926 2468352022402404634067976
927 2552602122042970126346110
928 2639681228262200314219426
929 2729682797219100345918492
930 2822703322488684605598780
931 2918842432188226350673874
932 3018202989159292562553686
933 3120891194300123436554728
934 3227016693145853947431524
935 3336692685797039704767602
936 3450036040299951088195234
937 3567167409585306710879792
938 3688211352075356721283680
939 3813296456072508548648706
940 3942555468046188539852826
941 4076125424938171745387564
942 4214147790610200526042772
943 4356768596561533373626534
944 4504138587047931269670910
945 4656413368737510991249464
946 4813753565043064847269028
947 4976324975274668634199038
948 5144298738760686009965322
949 5317851504089828313369592
950 5497165603631539887097936
951 5682429233496662819752030
952 5873836639105301020708842
953 6071588306533838245945260
954 6275891159818182412837276
955 6486958764395726739421194
956 6705011536874015264128254
957 6930276961319690982626392
958 7162989812267215940076628
959 7403392384652853819590994
960 7651734730885511786444354
961 7908274905272486900759216
962 8173279216024713036099472
963 8447022485072772665126162
964 8729788315931972135882002
965 9021869369861928480912724
966 9323567650573397219736916
967 9635194797742743167729926
968 9957072389602258004511574
969 10289532254882478455919864
970 10632916794391026354341404
971 10987579312521005080328702
972 11353884358990665298494210
973 11732208081125177646994984
974 12122938587000638314127072
975 12526476319779905782608694
976 12943234443579816527805282
977 13373639241219460471254060
978 13818130524209533938536860
979 14277162055353636439117578
980 14751201984343429998425822
981 15240733296740859667369768
982 15746254276752460720226356
983 16268278984212832626398002
984 16807337746206666478594970
985 17363977663771605345464424
986 17938763134137362498256544
987 18532276388969948287926370
988 19145118049103908702590202
989 19777907696259813535191332
990 20431284462258875413728556
991 21105907636261897196686662
992 21802457290575373813046254
993 22521634925583545103221528
994 23264164134381887458480332
995 24030791287704570125310230
996 24822286239755816800916458
997 25639443055573302135782984
998 26483080760570283956428752
999 27354044112922160973473014
1000 28253204399482963070051906