0 1
1 0
2 1
3 0
4 2
5 0
6 3
7 1
8 4
9 2
10 7
11 3
12 10
13 7
14 14
15 11
16 22
17 17
18 32
19 28
20 45
21 43
22 67
23 63
24 95
25 96
26 134
27 139
28 192
29 199
30 269
31 287
32 373
33 406
34 521
35 566
36 718
37 792
38 983
39 1092
40 1346
41 1496
42 1827
43 2045
44 2465
45 2772
46 3323
47 3733
48 4449
49 5016
50 5929
51 6696
52 7882
53 8897
54 10426
55 11784
56 13735
57 15534
58 18047
59 20391
60 23613
61 26692
62 30788
63 34797
64 40034
65 45207
66 51877
67 58564
68 67013
69 75614
70 86341
71 97328
72 110905
73 124953
74 142063
75 159945
76 181529
77 204185
78 231340
79 260025
80 294077
81 330286
82 372977
83 418506
84 471908
85 529106
86 595725
87 667380
88 750432
89 839938
90 943262
91 1054922
92 1183173
93 1322156
94 1481186
95 1653741
96 1850580
97 2064533
98 2307678
99 2572417
100 2872419
101 3199318
102 3568844
103 3971929
104 4426283
105 4922426
106 5480402
107 6089941
108 6774110
109 7521951
110 8359496
111 9275519
112 10299565
113 11419749
114 12670011
115 14038031
116 15562239
117 17230455
118 19086373
119 21117596
120 23374370
121 25844468
122 28584930
123 31584593
124 34908488
125 38546263
126 42572702
127 46978965
128 51850260
129 57180574
130 63067281
131 69507238
132 76612560
133 84384198
134 92950223
135 102317732
136 112633479
137 123911249
138 136320176
139 149882833
140 164793039
141 181085325
142 198982251
143 218531876
144 239991026
145 263424789
146 289128140
147 317188184
148 347944410
149 381509156
150 418274570
151 458384064
152 502289053
153 550171861
154 602552845
155 659659348
156 722093023
157 790135720
158 864481158
159 945478050
160 1033927249
161 1130255083
162 1235388072
163 1349845595
164 1474697364
165 1610575199
166 1758715126
167 1919879715
168 2095499651
169 2286492903
170 2494512647
171 2720662717
172 2966854573
173 3234408225
174 3525536380
175 3841814445
176 4185800555
177 4559373005
178 4965490351
179 5406383029
180 5885475697
181 6405412662
182 6970153699
183 7582831004
184 8248024129
185 8969431859
186 9752353408
187 10601150751
188 11521950414
189 12519892091
190 13602059152
191 14774493395
192 16045387270
193 17421834752
194 18913303490
195 20528116321
196 22277214229
197 24170343259
198 26220148836
199 28438031996
200 30838598177
201 33435174454
202 36244627632
203 39282512243
204 42568307015
205 46120149670
206 49960521197
207 54110556591
208 58596196742
209 63442037432
210 68678009080
211 74332711527
212 80440658598
213 87035083775
214 94155775802
215 101841310239
216 110137549324
217 119089235717
218 128749203748
219 139169316260
220 150410421780
221 162532579242
222 175605850631
223 189699738272
224 204894871955
225 221271633689
226 238922784741
227 257941212101
228 278433604772
229 300507231127
230 324284739443
231 349889935147
232 377463764564
233 407149012698
234 439107603949
235 473504113766
236 510524480587
237 550358291822
238 593218984380
239 639324811157
240 688920693916
241 742257743408
242 799616883928
243 861286879944
244 927589832107
245 998857598864
246 1075459365174
247 1157776311307
248 1246231405103
249 1341262259822
250 1443353280142
251 1553006579513
252 1670776727020
253 1797239551462
254 1933029680087
255 2078807162473
256 2235297969424
257 2403258285320
258 2583518272852
259 2776943835592
260 2984483890796
261 3207129523888
262 3445964988108
263 3702124079647
264 3976845241593
265 4271424932852
266 4587277144899
267 4925883678719
268 5288858358227
269 5677894020997
270 6094831898238
271 6541605066155
272 7020313385353
273 7533163320490
274 8082548808271
275 8670987234102
276 9301206814217
277 9976078449176
278 10698710123950
279 11472374547754
280 12300611052792
281 13187148793850
282 14136016880183
283 15151462837422
284 16238071618334
285 17400679246504
286 18644501334089
287 19975041679304
288 21398231216118
289 22920331257407
290 24548083710390
291 26288608915345
292 28149567947977
293 30139054838663
294 32265772133170
295 34538917198010
296 36968372117703
297 39564584089529
298 42338770736592
299 45302794421322
300 48469384465439
301 51852005127927
302 55465096134096
303 59323934420878
304 63444894394062
305 67845303354888
306 72543723395280
307 77559800345163
308 82914569135437
309 88630296523512
310 94730811799365
311 101241343358500
312 108188877208707
313 115601987392683
314 123511224693841
315 131948941417284
316 140949712776729
317 150550156350486
318 160789389333071
319 171708842944667
320 183352758702791
321 195767998668627
322 209004584036515
323 223115501930919
324 238157290454882
325 254189842746607
326 271277042655751
327 289486567511294
328 308890578817189
329 329565525039787
330 351592892742228
331 375059010766000
332 400055867328633
333 426680917879428
334 455037974024882
335 485237017263753
336 517395166861183
337 551636501822782
338 588093115067147
339 626904947129886
340 668220934482816
341 712198858476695
342 759006597208518
343 808821993519952
344 861834220212961
345 918243672327711
346 978263456234405
347 1042119311596463
348 1110051236796308
349 1182313446497897
350 1259176146515084
351 1340925534677336
352 1427865739284233
353 1520318871386641
354 1618627143393921
355 1723152981702936
356 1834281343024268
357 1952419898560897
358 2078001567089861
359 2211484782655337
360 2353356266500104
361 2504131391476316
362 2664357216416223
363 2834612963396563
364 3015513340193991
365 3207709147787473
366 3411890920442814
367 3628789682689774
368 3859180938757621
369 4103885602047103
370 4363774368508648
371 4639768843599167
372 4932846339186180
373 5244041225662139
374 5574450195086473
375 5925233871078683
376 6297622584881024
377 6692918278602691
378 7112500847333437
379 7557830375175131
380 8030454100963333
381 8532009032995879
382 9064229601398639
383 9628950701819677
384 10228116105833570
385 10863781989330311
386 11538126178571230
387 12253452227546817
388 13012199584816699
389 13816948290380615
390 14670430159340842
391 15575534176523718
392 16535318801650078
393 17553018151228739
394 18632055540215368
395 19776050549645817
396 20988833934040784
397 22274455683949619
398 23637201440327873
399 25081601676152794
400 26612449773036553
401 28234812458649364
402 29954049719603167
403 31775826646273063
404 33706135372441585
405 35751308499021385
406 37918043270054241
407 40213416764411033
408 42644912542481816
409 45220437815372718
410 47948352819166322
411 50837490197689982
412 53897187387137178
413 57137308472808972
414 60568279899592686
415 64201115091148093
416 68047453832480549
417 72119589975433559
418 76430514874686278
419 80993948536949763
420 85824387535012183
421 90937139996356008
422 96348378461669518
423 102075179155876538
424 108135580304928141
425 114548626178162655
426 121334431434607630
427 128514230477780981
428 136110448459366357
429 144146756550659443
430 152648150295393301
431 161641011464731267
432 171153194527207166
433 181214095824956161
434 191854749005285938
435 203107902340128581
436 215008124049757582
437 227591888672619991
438 240897693312912580
439 254966154063765284
440 269840134313581534
441 285564852338048345
442 302188022915680267
443 319759977319549631
444 338333819626895193
445 357965560470713796
446 378714289567117827
447 400642324737109446
448 423815402330293794
449 448302843182974549
450 474177762795429060
451 501517256066492458
452 530402629267923473
453 560919605595901253
454 593158581193436803
455 627214853769094159
456 663188905155622908
457 701186655479895930
458 741319774995570083
459 783705966555161378
460 828469309731786602
461 875740574626197320
462 925657601607658502
463 978365649802003621
464 1034017816115488066
465 1092775422105302059
466 1154808476320277800
467 1220296103633154819
468 1289427055350061574
469 1362400185502748190
470 1439425013624329282
471 1520722252972498236
472 1606524431362118602
473 1697076476795704983
474 1792636402297915701
475 1893475954988922406
476 1999881371459602992
477 2112154096951652124
478 2230611618468456813
479 2355588261400219003
480 2487436108300310686
481 2626525881039021564
482 2773247953965170922
483 2928013330506103196
484 3091254760306222544
485 3263427820089202234
486 3445012145338180663
487 3636512626227798621
488 3838460765460196539
489 4051416001180270158
490 4275967203738552477
491 4512734138697716848
492 4762369116580779546
493 5025558610393909840
494 5303025073810367852
495 5595528729099262262
496 5903869570728665015
497 6228889341175722506
498 6571473738633973340
499 6932554599926799447
500 7313112332847628556
501 7714178327336062534
502 8136837635008324886
503 8582231631857121872
504 9051560969776466573
505 9546088516358837059
506 10067142605657035001
507 10616120283212074109
508 11194490885975697751
509 11803799623483398992
510 12445671519824868714
511 13121815364934045788
512 13834028054715583029
513 14584198949801996488
514 15374314653482667956
515 16206463818952582750
516 17082842408595422053
517 18005758994784833155
518 18977640548321617418
519 20001038282301394165
520 21078634022169963509
521 22213246647018836386
522 23407839098862820411
523 24665525481046567047
524 25989578769944927286
525 27383438636025978711
526 28850719927314829097
527 30395221285045176704
528 32020934474985213981
529 33732053876616082412
530 35532986745781421414
531 37428363664039914048
532 39423049824173174759
533 41522156534761939021
534 43731053628962588360
535 46055382128568801952
536 48501067886141487639
537 51074335522942334641
538 53781723425103733035
539 56630099080860522266
540 59626675563090290518
541 62779028403366377967
542 66095113705895035203
543 69583286709194813669
544 73252321690362595799
545 77111432379670571621
546 81170293829351737881
547 85439064862270231989
548 89928412096057923236
549 94649534624417303332
550 99614190405657923210
551 104834723394175240766
552 110324092522408935910
553 116095901520820851053
554 122164430744082894676
555 128544669940654685831
556 135252353197846152993
557 142303994946943218517
558 149716928327906245504
559 157509344743176934437
560 165700335971260793469
561 174309937612124729762
562 183359175310067239676
563 192870112466099208671
564 202865900964615837895
565 213370833563674402760
566 224410399557188498210
567 236011342292898227395
568 248201720242480918481
569 261010970139422555250
570 274469973973942283533
571 288611128289333738863
572 303468417667139876180
573 319077490771246746542
574 335475740941784709996
575 352702389631572113913
576 370798574785218301972
577 389807442372949799388
578 409774243294642885735
579 430746433782138374828
580 452773781637019313631
581 475908476344577781751
582 500205245529660447508
583 525721475704145526056
584 552517339907512294548
585 580655930095676036788
586 610203397022830556647
587 641229095373250383915
588 673805737039150089080
589 708009550199418827398
590 743920447255293288481
591 781622199171777522213
592 821202619449762371104
593 862753755167750047124
594 906372088496617153991
595 952158746012248296371
596 1000219719398183373369
597 1050666094744933470990
598 1103614294237444991649
599 1159186327315094086495
600 1217510055306444188016
601 1278719466496506238982
602 1342954965851667273318
603 1410363676229122044011
604 1481099755531587729044
605 1555324726499015906324
606 1633207823847317073501
607 1714926355306215675690
608 1800666081530021227238
609 1890621611289525174805
610 1984996817197748152982
611 2084005268229628439352
612 2187870684583603802240
613 2296827410992617780089
614 2411120914345118452081
615 2531008301566820493705
616 2656758863954600410378
617 2788654643752513571610
618 2926991029511631527281
619 3072077375858703948888
620 3224237654586525158666
621 3383811132522167944479
622 3551153083479003338902
623 3726635529576254143297
624 3910648019648506323362
625 4103598439852836752902
626 4305913864637558977287
627 4518041443000965774412
628 4740449328671981967025
629 4973627648959063972961
630 5218089521395445885767
631 5474372112742278936134
632 5743037750004172691707
633 6024675077831817789987
634 6319900272524416039506
635 6629358306818273731847
636 6953724276266655651567
637 7293704781207656826806
638 7650039375754087050013
639 8023502077612166586576
640 8414902950830443777668
641 8825089755096292360014
642 9254949674390178627639
643 9705411118426547831662
644 10177445610444557347512
645 10672069754591167815297
646 11190347297259617780952
647 11733391275442842729557
648 12302366267314884330239
649 12898490737921020793090
650 13523039496093450203476
651 14177346255300208179427
652 14862806315504844611333
653 15580879358578936989506
654 16333092375366790308035
655 17121042716787404761883
656 17946401288160365904628
657 18810915878994560513120
658 19716414648583101390854
659 20664809759510254689073
660 21658101180645075650255
661 22698380651609241179009
662 23787835831605049729535
663 24928754624490501343025
664 26123529704383585306902
665 27374663233602854696024
666 28684771798713809605758
667 30056591556431572747449
668 31492983616734601947481
669 32996939654910415689312
670 34571587781577343126215
671 36220198662404855727613
672 37946191918377605957931
673 39753142798361895699307
674 41644789156740802830564
675 43625038727952481497248
676 45697976732746758275793
677 47867873808115238440514
678 50139194297896349240767
679 52516604896180940633677
680 55004983682853659724692
681 57609429543622411273582
682 60335272016362189781082
683 63188081556415497908346
684 66173680265335867435173
685 69298153076076310969189
686 72567859441951099984499
687 75989445522810569582513
688 79569856918793169089213
689 83316351945619630817660
690 87236515505037948411937
691 91338273545005207429294
692 95629908166683579357276
693 100120073373564761433164
694 104817811523508377433075
695 109732570479855683673473
696 114874221526370108464175
697 120253078043143387439386
698 125879915012461910309731
699 131765989352894110147192
700 137923061155133049038333
701 144363415819136972176442
702 151099887170960597645879
703 158145881560276904745024
704 165515403022183847028691
705 173223079505946200107804
706 181284190259835999608561
707 189714694376585330515077
708 198531260594579440274427
709 207751298361400439432647
710 217392990261239425329791
711 227475325815140387551566
712 238018136762439469922422
713 249042133834997921442822
714 260568945139928913004042
715 272621156165359219560385
716 285222351532790629338203
717 298397158513882736134286
718 312171292443653062019835
719 326571604051567266295081
720 341626128851556445776186
721 357364138616489250538095
722 373816195087833283301858
723 391014205950531082819198
724 408991483234227109898428
725 427782804175852775477243
726 447424474715866676047732
727 467954395668666084310835
728 489412131751444359752628
729 511838983518096046025636
730 535278062395298900298344
731 559774368874090138523655
732 585374874067865535390779
733 612128604697519381164971
734 640086731729470518123389
735 669302662735441360968376
736 699832138215644571531035
737 731733331963209063165866
738 765066955728586838950877
739 799896368271623967889384
740 836287689078391836111738
741 874309916841280562891959
742 914035052999168055037037
743 955538230448038265064598
744 998897847740047679088443
745 1044195708894429081828417
746 1091517169160998369582131
747 1140951286873914450158230
748 1192590981760924924686697
749 1246533199861363513253633
750 1302879085444430782050957
751 1361734160098110632092363
752 1423208509408526097153556
753 1487416977418772928969700
754 1554479369317428776241435
755 1624520662566200755254844
756 1697671226949590309394863
757 1774067053778347878948992
758 1853849994764740666845868
759 1937168010825764400287695
760 2024175431370116933664127
761 2115033224351647384390899
762 2209909277685748940976741
763 2308978692340402985732025
764 2412424087742069250922526
765 2520435919839741175102244
766 2633212812514398121740431
767 2750961902711624995355947
768 2873899200035235003891781
769 3002249961217193963484735
770 3136249080256128765717576
771 3276141494680583417036846
772 3422182608787888018257320
773 3574638734359286983578692
774 3733787549765231243249890
775 3899918578009880881652016
776 4073333684696563401851221
777 4254347596515880255650655
778 4443288441311215196854449
779 4640498310380583421807743
780 4846333844148151955255488
781 5061166841926594888636319
782 5285384896988189711610186
783 5519392057733435514802525
784 5763609516266132941065989
785 6018476325237162500556084
786 6284450144363892906609016
787 6562008017567227581193680
788 6851647182238708462624509
789 7153885911666293781031687
790 7469264392244786097688059
791 7798345636593534234609591
792 8141716434329636867075143
793 8499988341721277734012356
794 8873798712101037321371221
795 9263811768374472031223942
796 9670719719645505889209081
797 10095243923413947430077648
798 10538136095519239801331701
799 11000179569415894971879629
800 11482190607118983905982392
801 11985019763546211559986101
802 12509553306771809725032796
803 13056714696071680702200373
804 13627466120465456254691671
805 14222810099800585228495056
806 14843791151289161838277177
807 15491497523722097475810874
808 16167063002492131348876399
809 16871668787844693483190359
810 17606545449725848130148791
811 18372974961856855673726052
812 19172292818660567990374692
813 20005890237897128491947618
814 20875216452909830502702706
815 21781781097585340930520413
816 22727156688225946798809966
817 23712981205705065517544335
818 24740960782423272680220323
819 25812872497725041932295615
820 26930567286637582958594508
821 28095972965904591294874564
822 29311097382546850836508348
823 30578031689260660977826584
824 31898953752285034843037687
825 33276131696414367047755183
826 34711927593217148300211413
827 36208801297532904358432997
828 37769314438770543378157227
829 39396134572507865671011532
830 41092039499413529617688499
831 42859921757453438890891991
832 44702793294939167698631703
833 46623790330879965674447761
834 48626178410773422980702533
835 50713357664836211055786700
836 52888868277431731620903600
837 55156396175279430318305573
838 57519778943872024157503180
839 59983011980315618210573003
840 62550254892739686453543109
841 65225838155172652339052193
842 68014270028805996773197545
843 70920243759277887293348354
844 73948645061734639770864721
845 77104559904095020078294724
846 80393282601175046755828635
847 83820324230955643443612134
848 87391421386618992693831407
849 91112545276561544813024637
850 94989911187051796174172524
851 99029988320739968708948146
852 103239510026809680706032318
853 107625484437057194501596307
854 112195205524896082217032948
855 116956264602736777099043709
856 121916562276038884602567301
857 127084320870741647787931659
858 132468097353769768203383733
859 138076796764675055750549971
860 143919686179617265513107316
861 150006409227206488717075894
862 156347001179031530767373370
863 162951904635973592040265007
864 169831985834874390177574292
865 176998551598358892994900352
866 184463366954259499657437860
867 192238673449276135010023921
868 200337208185339835948385364
869 208772223605292286844351909
870 217557508058523486739057010
871 226707407175312706461434818
872 236236846082855010342062643
873 246161352494017773102970167
874 256497080704327525352021221
875 267260836530710153101507001
876 278470103230194241091284268
877 290143068434772196348149162
878 302298652143544224170495497
879 314956535811219163789247880
880 328137192577233851379084561
881 341861918677667993745446219
882 356152866087590791471957964
883 371033076439359891692313317
884 386526516268139353800536930
885 402658113633759738396763233
886 419453796174092530903137209
887 436940530642943150899204108
888 455146363991836031485055821
889 474100466052876899503524344
890 493833173886584948221788822
891 514376037856383382343102090
892 535761869498501984044472348
893 558024791253830417852496785
894 581200288135704235899250473
895 605325261405385645908371321
896 630438084334844168203929939
897 656578660134223890486822337
898 683788482129649971866522829
899 712110696274817338255042517
900 741590166088517823678856201
901 772273540108069031234050026
902 804209321957794902783496527
903 837447943129540652811028707
904 872041838581892464288425639
905 908045525262640569093157406
906 945515683669242460644948739
907 984511242559957703292064163
908 1025093466939105529450001597
909 1067326049437869706021673926
910 1111275205223449627139135250
911 1157009770567401798725822510
912 1204601305216020348076441076
913 1254124198703736971486675520
914 1305655780763192689135450442
915 1359276435983868240463527017
916 1415069722884539235166665310
917 1473122497563177035960399076
918 1533525042102045332616471879
919 1596371197904237004852983058
920 1661758504152819660102335802
921 1729788341582413875501974772
922 1800566081768794713566836553
923 1874201242140946977614728510
924 1950807646936664989482221122
925 2030503594321837183799167618
926 2113412029911164236456330417
927 2199660726927346265546474854
928 2289382473254388958745674699
929 2382715265640232846368251307
930 2479802511323591668222814901
931 2580793237359740597356456110
932 2685842307940809756590775624
933 2795110650006329566591297172
934 2908765487461791812682610718
935 3026980584323556736330249028
936 3149936497131730749568317418
937 3277820836973623492739604818
938 3410828541485043327894189733
939 3549162157198138251873292105
940 3693032132630579911362494317
941 3842657122512850122448279625
942 3998264303578010081280226199
943 4160089702340862275516811338
944 4328378535322661648288771222
945 4503385562180689368753838885
946 4685375452232976756239547357
947 4874623164872314549387602178
948 5071414344396493151498467738
949 5276045729786327107469462101
950 5488825579997779536874014326
951 5710074115339944733677612961
952 5940123975547484998416610201
953 6179320695162476212763717539
954 6428023196879661418988107112
955 6686604303516473750399230918
956 6955451269310581959060418559
957 7234966331256172346494563835
958 7525567281234069426646211495
959 7827688059700459252265457847
960 8141779371745523882084610992
961 8468309326344268879757985735
962 8807764099671196335927870291
963 9160648623362880794768895876
964 9527487298664883391655763056
965 9908824737413405138928922803
966 10305226530857658898537901602
967 10717280047344605412603541103
968 11145595259946684332650021911
969 11590805605130687724321865229
970 12053568873628536048779347494
971 12534568134690246264877779677
972 13034512694965855873202240493
973 13554139093284784531190080920
974 14094212132671701148875025002
975 14655525950962059087145148503
976 15238905131455427605533093656
977 15845205855071422795594230496
978 16475317095552671065254427154
979 17130161859288712857424955386
980 17810698471419352660882304080
981 18517921909908471598025238427
982 19252865189369210378649711602
983 20016600796457230539111019680
984 20810242178744292932011703226
985 21634945289023756158135785132
986 22491910187101137991974807113
987 23382382701166104784919977094
988 24307656150950198072699799244
989 25269073134922004853263324323
990 26268027383886247287364271095
991 27305965683405181185693407548
992 28384389867582736591212540782
993 29504858886808630628362266571
994 30668990952189481234280285139
995 31878465759456025118712839123
996 33135026795273608479519910118
997 34440483728950895785868615869
998 35796714892688620757002369046
999 37205669853584138509363526064
1000 38669372080763814035338241680