1 0
2 1
3 1
4 3
5 2
6 7
7 5
8 12
9 13
10 22
11 22
12 43
13 43
14 67
15 81
16 117
17 133
18 195
19 223
20 312
21 373
22 492
23 584
24 782
25 925
26 1190
27 1433
28 1820
29 2170
30 2748
31 3268
32 4075
33 4872
34 5997
35 7150
36 8781
37 10420
38 12669
39 15055
40 18198
41 21535
42 25925
43 30602
44 36624
45 43201
46 51428
47 60478
48 71802
49 84215
50 99537
51 116572
52 137282
53 160361
54 188326
55 219502
56 256953
57 298953
58 348914
59 405058
60 471679
61 546431
62 634585
63 733929
64 850311
65 981486
66 1134748
67 1307384
68 1508262
69 1734869
70 1997354
71 2293426
72 2635633
73 3021274
74 3465544
75 3966603
76 4541896
77 5190371
78 5933484
79 6770437
80 7727231
81 8804743
82 10033354
83 11416207
84 12990370
85 14760517
86 16771490
87 19032118
88 21595193
89 24474249
90 27733716
91 31391865
92 35526555
93 40164415
94 45397768
95 51263574
96 57873988
97 65276785
98 73607684
99 82931299
100 93409339
101 105126633
102 118279487
103 132975909
104 149453007
105 167851020
106 188453454
107 211440123
108 237154419
109 265821474
110 297856062
111 333544191
112 373382834
113 417731670
114 467191521
115 522209102
116 583508778
117 651648981
118 727498539
119 811751548
120 905456278
121 1009466814
122 1125045665
123 1253249308
124 1395591479
125 1553372432
126 1728414814
127 1922308935
128 2137245854
129 2375174800
130 2638721387
131 2930267304
132 3252966967
133 3609716094
134 4004299255
135 4440242470
136 4922074644
137 5454076888
138 6041678376
139 6690059017
140 7405718901
141 8194927825
142 9065452554
143 10024867197
144 11082460032
145 12247354032
146 13530645332
147 14943324216
148 16498624123
149 18209759964
150 20092521528
151 22162763988
152 24439307793
153 26941170545
154 29690753364
155 32710833525
156 36028075871
157 39669709069
158 43667444249
159 48053818427
160 52866496966
161 58144307113
162 63931980052
163 70275779505
164 77228780212
165 84846074777
166 93190569366
167 102327794696
168 112332286027
169 123281883820
170 135264828724
171 148373528183
172 162712344094
173 178390859362
174 195532450724
175 214266918603
176 234740001709
177 257105345409
178 281534948933
179 308210508919
180 337334915661
181 369122811719
182 403813344384
183 441659909288
184 482944151722
185 527964947984
186 577053815588
187 630562943494
188 688882266318
189 752426513963
190 821653972102
191 897052614562
192 979160754185
193 1068552044194
194 1165858354571
195 1271753616545
196 1386978965894
197 1512325521872
198 1648662081271
199 1796916586139
200 1958106792710
201 2133320415583
202 2323748872926
203 2530666231002
204 2755466390648
205 2999640574172
206 3264818514818
207 3552744494998
208 3865322703559
209 4204592006186
210 4572775983486
211 4972256159708
212 5405627444110
213 5875669880498
214 6385409778932
215 6938090251501
216 7537238713946
217 8186635954265
218 8890390975912
219 9652908736014
220 10478972775808
221 11373712027181
222 12342692182557
223 13391881364809
224 14527751508617
225 15757243178948
226 17087877676254
227 18527721597471
228 20085510957902
229 21770615410319
230 23593176121945
231 25564070150126
232 27695063140560
233 29998774765742
234 32488848060196
235 35179916052928
236 38087790069374
237 41229428419389
238 44623145300658
239 48288582895442
240 52246943392773
241 56520965006307
242 61135180328777
243 66115897673975
244 71491488169709
245 77292374484315
246 83551350214427
247 90303577118003
248 97586941194034
249 105442060669361
250 113912682378505
251 123045703583134
252 132891613632872
253 143504531730592
254 154942699997780
255 167268540704223
256 180549206006892
257 194856659272751
258 210268288572354
259 226867015711760
260 244741981988591
261 263988690370518
262 284709771278297
263 307015164798413
264 331022976483227
265 356859705556114
266 384661202682637
267 414572952437714
268 446751144330358
269 481363019771414
270 518588070597847
271 558618459974088
272 601660365179808
273 647934484933060
274 697677542881413
275 751142896475143
276 808602221365389
277 870346236485013
278 936686593048239
279 1007956734473819
280 1084514013758973
281 1166740710519854
282 1255046405560409
283 1349869177360446
284 1451678267253864
285 1560975483041837
286 1678298189167095
287 1804220950072741
288 1939358886345129
289 2084369591429864
290 2239956901115336
291 2406873124346292
292 2585923275507317
293 2777967666964447
294 2983926662536362
295 3204783681780476
296 3441590541668030
297 3695470932317549
298 3967626417992685
299 4259340453469194
300 4571985127373069
301 4907025792988333
302 5266028648970627
303 5650666071546165
304 6062725134400743
305 6504113742487184
306 6976870209192674
307 7483170299803315
308 8025338000488655
309 8605853597511002
310 9227365783634737
311 9892700917598193
312 10604876635582557
313 11367112448190099
314 12182845047545310
315 13055740423768999
316 13989711075202147
317 14988929852158732
318 16057849308145973
319 17201217498341103
320 18424099741316965
321 19731896633905407
322 21130368518696494
323 22625656012916833
324 24224307518466516
325 25933302592329032
326 27760082880092314
327 29712578702610302
328 31799243831925630
329 34029085719225142
330 36411704589511229
331 38957327780204768
332 41676853692059264
333 44581890773252397
334 47684806919831106
335 50998773710349117
336 54537821928106843
337 58316891716391832
338 62351894980103604
339 66659772222301042
340 71258562663272220
341 76167468617220065
342 81406934276231326
343 86998718580004131
344 92965983730436723
345 99333377633149901
346 106127133324214683
347 113375162198914445
348 121107165683042281
349 129354740599531489
350 138151504581432498
351 147533215101413613
352 157537910288123737
353 168206043334119846
354 179580640586303134
355 191707453240408929
356 204635134804422663
357 218415412229574682
358 233103285079168262
359 248757218510885437
360 265439366771965279
361 283215790720595305
362 302156708585230961
363 322336741047620064
364 343835192532621717
365 366736327243463707
366 391129684647445982
367 417110390238499457
368 444779509322556198
369 474244396745816598
370 505619093544993811
371 539024720389859283
372 574589922213879599
373 612451310659147680
374 652753962409737769
375 695651916567313857
376 741308733053750816
377 789898051552094203
378 841604217104470114
379 896622908006605363
380 955161836564589801
381 1017441454214971381
382 1083695736301468370
383 1154172973668616061
384 1229136651365052509
385 1308866337007928850
386 1393658664474930150
387 1483828330554498742
388 1579709195933907985
389 1681655402996838736
390 1790042607853835448
391 1905269233604374344
392 2027757848746249196
393 2157956571895511328
394 2296340613635150767
395 2443413850540218285
396 2599710549502378445
397 2765797130921410076
398 2942274096728776977
399 3129778004909553574
400 3328983624826653552
401 3540606147785843449
402 3765403595973970123
403 4004179296557777868
404 4257784573549161927
405 4527121516087939244
406 4813145985822468034
407 5116870713523118655
408 5439368658280125882
409 5781776470417472561
410 6145298242920219100
411 6531209382945229131
412 6940860800387776828
413 7375683235075083081
414 7837191932461522685
415 8326991478838518977
416 8846781019768374625
417 9398359661560295500
418 9983632294217210812
419 10604615623975709781
420 11263444669475204518
421 11962379497347014063
422 12703812467990535035
423 13490275754272194502
424 14324449421721566506
425 15209169819338400676
426 16147438588477163936
427 17142432024582482609
428 18197511119491635321
429 19316232003924072545
430 20502357139434256758
431 21759866963657591941
432 23092972361014897052
433 24506127646113094238
434 26004044456539293962
435 27591706224787007101
436 29274383652143113616
437 31057650836072783711
438 32947402501692044183
439 34949871969777343534
440 37071650341656709941
441 39319706513346921341
442 41701408530992702240
443 44224545879123111065
444 46897353247496003373
445 49728535346235059771
446 52727293351170221355
447 55903352526194117554
448 59266991643084701486
449 62829073721905287115
450 66601078753439414953
451 70595137902045765264
452 74824069894357534248
453 79301419066339794661
454 84041495821045339148
455 89059418942878708837
456 94371160570672877649
457 99993593247626940387
458 105944539903994920480
459 112242826161630212900
460 118908335873497859239
461 125962069257503197314
462 133426204598744586688
463 141324162848732833096
464 149680676161127652001
465 158521859660561518625
466 167875287554038693586
467 177770072848774544825
468 188236951860585799718
469 199308372743020130823
470 211018589301436208216
471 223403759287467448170
472 236502048523755900984
473 250353740019075229102
474 265001349515237187301
475 280489746589790468943
476 296866282854184972752
477 314180926334426066062
478 332486403679103857893
479 351838349244581298470
480 372295462814721895370
481 393919674967228608544
482 416776321964867235354
483 440934329145421106211
484 466466404818194402215
485 493449243602925100330
486 521963741357588375846
487 552095220593021720667
488 583933668669966696136
489 617573987638611839121
490 653116258176172993522
491 690666016445741670642
492 730334546503332813997
493 772239187040386084927
494 816503655273096177359
495 863258386730845002183
496 912640893953148056583
497 964796142814524177659
498 1019876949699160954713
499 1078044398214016540651
500 1139468278891040987096
501 1204327550538744628370
502 1272810826939721291552
503 1345116887529678894332
504 1421455216018724576657
505 1502046565569651513529
506 1587123554778664827697
507 1676931293056807017482
508 1771728039963821061963
509 1871785897082272701866
510 1977391537313032241731
511 2088846970175885765913
512 2206470348351651965796
513 2330596814052637352574
514 2461579390840442152874
515 2599789919490289281231
516 2745620043932797168591
517 2899482245894635815800
518 3061810934713663176260
519 3233063590983269798070
520 3413721970980937484924
521 3604293370582784961468
522 3805311956135756054138
523 4017340161051094497260
524 4240970156148962569757
525 4476825392596157605430
526 4725562226069176418779
527 4987871621082790487982
528 5264480944766258974794
529 5556155849147112892846
530 5863702251927336370484
531 6187968414955506487303
532 6529847131138770786576
533 6890278019170127033123
534 7270249937634598528374
535 7670803518072402940829
536 8093033829449728504308
537 8538093173851813912968
538 9007194026807969653131
539 9501612122339438459244
540 10022689697176394561895
541 10571838894554329665556
542 11150545343158727286062
543 11760371911995243345136
544 12402962657969063315287
545 13080046967372487531403
546 13793443909378702399560
547 14545066803222477250175
548 15336928018589972994454
549 16171144011446082097659
550 17049940616363873549617
551 17975658598207538528291
552 18950759485903549491943
553 19977831691856645419011
554 21059596941556366554811
555 22198917017726534928715
556 23398800845526108034638
557 24662411924052156097671
558 25993076132780280449156
559 27394289919203663985589
560 28869728898613729176412
561 30423256873417362495248
562 32058935305436310180752
563 33781033249856281815863
564 35594037786985230252103
565 37502664961912680773197
566 39511871271175678958745
567 41626865708114380094481
568 43853122409219800040606
569 46196393914934735050933
570 48662725090679311544544
571 51258467723544439858981
572 53990295844192247161517
573 56865221791613406559267
574 59890613074371049661741
575 63074210048438078898629
576 66424144469698645125323
577 69948958943951156147464
578 73657627337309083462340
579 77559576172867796515549
580 81664707081775366608243
581 85983420337940250883347
582 90526639550207291497054
583 95305837544964597506632
584 100333063519201360500217
585 105620971501109093211030
586 111182850204971435999649
587 117032654322008550577481
588 123185037341229049373193
589 129655385947013965452543
590 136459856095431520239970
591 143615410821597134208763
592 151139859888715054131976
593 159051901337293556346164
594 167371165054559416648119
595 176118258429383299726566
596 185314814222953481585772
597 194983540728032565482718
598 205148274358138615598133
599 215834034747784289977291
600 227067082517189242834948
601 238874979791746118658333
602 251286653642789568120638
603 264332462550023282217007
604 278044266066439613652886
605 292455497797183330735295
606 307601241888730489681119
607 323518313152046741090266
608 340245341032999637938679
609 357822857567123030449249
610 376293389550396329839836
611 395701555077912942816220
612 416094164702103146138381
613 437520327378627871794380
614 460031561473373915257111
615 483681911016511837828563
616 508528067500727110661081
617 534629497429190185067914
618 562048575936138267796000
619 590850726707159724731197
620 621104568550088657540617
621 652882068867224631409629
622 686258704410288935105368
623 721313629594757946254190
624 758129852788173900768402
625 796794420877510801139918
626 837398612566313770717125
627 880038140737869608110638
628 924813364374427762493885
629 971829510402914039459307
630 1021196905999918554819564
631 1073031221763862327529527
632 1127453726333660563127113
633 1184591552902826726697453
634 1244577978258973646605361
635 1307552714842610542847661
636 1373662216510290801426392
637 1443059998545233506079861
638 1515906972660433584450186
639 1592371797591265690490742
640 1672631246087840147062167
641 1756870588963091094957002
642 1845283997077843782237997
643 1938074961983367862036808
644 2035456736179911463054598
645 2137652793782304019138212
646 2244897312635172946933488
647 2357435678746057666279517
648 2475525014170412660658730
649 2599434729301186274757843
650 2729447100796468564494839
651 2865857876190154947126558
652 3008976906527374401387197
653 3159128808170466385935502
654 3316653655235027454867628
655 3481907703911992547310592
656 3655264150263404757856525
657 3837113922868199991024073
658 4027866512045051726067363
659 4227950837160070517018221
660 4437816153898033067790455
661 4657933003148498212634876
662 4888794203550432844439880
663 5130915889503440605767607
664 5384838596868636101587169
665 5651128398338355325280405
666 5930378090892892933128315
667 6223208437510189011016365
668 6530269465758914705690623
669 6852241825644632542664262
670 7189838209570329258566072
671 7543804837003297905242747
672 7914923006960715979724443
673 8304010721148380378057477
674 8711924381137963940263147
675 9139560562681703772021982
676 9587857870846768486922497
677 10057798879356586562684926
678 10550412158144192592621268
679 11066774392819268564910751
680 11608012600404934857521940
681 12175306445388673309099875
682 12769890660825050001649476
683 13393057578908142867049582
684 14046159776166209572490921
685 14730612838103535516480853
686 15447898248893008770540480
687 16199566411387840748351992
688 16987239803546239046064387
689 17812616277020583457569367
690 18677472504537794747237630
691 19583667582348685282511285
692 20533146794952176127324997
693 21527945548945268796229789
694 22570193483834131624254017
695 23662118767281252618218429
696 24806052583308086636340691
697 26004433821607596436833705
698 27259813977229482111875553
699 28574862269532133890681473
700 29952370990471836600091465
701 31395261091928327009664159
702 32906588023014837853704080
703 34489547827947877728999201
704 36147483516378358943331000
705 37883891717712691431546331
706 39702429632361273389916080
707 41606922292480279557683364
708 43601370146269357834702011
709 45689956979519550252534686
710 47877058189696237243806625
711 50167249427478806661919457
712 52565315622369289141965435
713 55076260408626553708944190
714 57705315969579950496092650
715 60457953318030605288754240
716 63339893032359837646076524
717 66357116467631234136546527
718 69515877463005878200941980
719 72822714566473189841565665
720 76284463800062746449767798
721 79908271988404797886107959
722 83701610675808946653368398
723 87672290656756044609985083
724 91828477147148478686161781
725 96178705623417165906619136
726 100731898359192233479761265
727 105497381689029860915932048
728 110484904031465918721778305
729 115704654703490145455359707
730 121167283561494020101721225
731 126883921503612067566164905
732 132866201871529575519880588
733 139126282789746221073734052
734 145676870483645722409689289
735 152531243617695171737346981
736 159703278698680232386605760
737 167207476588920813672440729
738 175058990178231825468216872
739 183273653263505581352439952
740 191868010688866637631318941
741 200859349799544812413023141
742 210265733266958571861871922
743 220106033342789376948800490
744 230399967604465523257238790
745 241168136254867328742390488
746 252432061044015737882000429
747 264214225881017168163770913
748 276538119209822221728492314
749 289428278222997879610552735
750 302910334993356086890479127
751 317011064604069970446441842
752 331758435363936494781474215
753 347181661195395499894310048
754 363311256289354592990381213
755 380179092122001410106472820
756 397818456935665954970935941
757 416264117787128444521963791
758 435552385274122964112654667
759 455721181052342169831704128
760 476810108263111239742776757
761 498860524993700036123656923
762 521915620900650421692458436
763 546020497128568015428761817
764 571222249665820479905760233
765 597570056280956381358238339
766 625115267193279090415426441
767 653911499633712412945475409
768 684014736462388637913075063
769 715483429012455588838244824
770 748378604340616370133800401
771 782763977068381392010693780
772 818706066009805738885373697
773 856274315785390496917042623
774 895541223634453737170861700
775 936582471642665221619936065
776 979477064614961266838735955
777 1024307473828974272613269459
778 1071159786918595430457520168
779 1120123864142788028655401686
780 1171293501310285725171989830
781 1224766599636945469285996950
782 1280645342829151520895732908
783 1339036381693499057543079693
784 1400051026590805140673731920
785 1463805448060089282719905665
786 1530420885957266555226197956
787 1600023867461724430037638447
788 1672746434324432492619914124
789 1748726379740573592021617728
790 1828107495251643310927355141
791 1911039828092299422898765830
792 1997679949420792586195936213
793 2088191233883231022982055497
794 2182744150987192303975367338
795 2281516568772802601285516847
796 2384694070296503573270903000
797 2492470283456627635617608567
798 2605047224718979967551405621
799 2722635657315936227132632165
800 2845455464523769466053148659
801 2973736038639766803996837728
802 3107716686314188380826269947
803 3247647050910641846837562710
804 3393787552604397737474294724
805 3546409846948514204177084928
806 3705797302676237894704313825
807 3872245499530474299681871140
808 4046062746952565781795029296
809 4227570624487100070533873148
810 4417104544803979042961283533
811 4615014340265809362906820114
812 4821664874016478022194474923
813 5037436676596159452632199112
814 5262726609139346860810051354
815 5497948554244657779628921116
816 5743534135660323431573542824
817 5999933467964442679725452224
818 6267615937478344534864500911
819 6547071015689847941034056318
820 6838809106526886528618013612
821 7143362428863965657648797080
822 7461285935712349778575939068
823 7793158271590736974876448656
824 8139582769646721976466527720
825 8501188490149396005211130876
826 8878631302052479669890453663
827 9272595009381976567759094310
828 9683792524287305958334014508
829 10112967088654393764736836436
830 10560893546270546575610989120
831 11028379667595799830861047816
832 11516267529293637968046517183
833 12025434950744646621666580570
834 12556796989872248303597928051
835 13111307500686617669656902856
836 13689960755066412551128514278
837 14293793131381709593682558703
838 14923884872683629334854325278
839 15581361917277264479861636788
840 16267397804625830524964362880
841 16983215659633076996430553151
842 17730090258492216228070201370
843 18509350179397398878345632441
844 19322380041565655029750737810
845 20170622836134361558572229840
846 21055582352662672588707907470
847 21978825705092634894108549984
848 22941985961201450982889446783
849 23946764879714615989362757977
850 24994935759438705512898800120
851 26088346404922735311758703164
852 27228922213360392367464349187
853 28418669387608434697293101482
854 29659678280415359108693104697
855 30954126875131338798915577687
856 32304284408405837013102638117
857 33712515140571244961133544177
858 35181282279664168086877507858
859 36713152065244190180784898496
860 38310798018442458705813189513
861 39977005364898224057188876984
862 41714675637534687965234900030
863 43526831466370314675173802053
864 45416621562877272141993961218
865 47387325906664015250852827650
866 49442361142598531406552372065
867 51585286196776317771096399925
868 53819808120102495865904335114
869 56149788168569010769912190725
870 58579248129700999378022426837
871 61112376904983874794620729418
872 63753537358505735320675957469
873 66507273442415169295276493692
874 69378317610249797426715051913
875 72371598529586599313257159132
876 75492249105955008448001768800
877 78745614830382124268849103548
878 82137262463466640213157358268
879 85672989069341715085821220251
880 89358831413454424705288769018
881 93201075738591131326182964286
882 97206267934188739389109606465
883 101381224114514605058715038299
884 105733041621955014480833260459
885 110269110472239303549439913740
886 114997125259133900617723222950
887 119925097536775604192898077485
888 125061368698574490390837676936
889 130414623372303533854589562496
890 135993903351811084933842792973
891 141808622086534770813071603267
892 147868579750876836324916004090
893 154183978916303493981405531374
894 160765440849979435592516542501
895 167624022464616071921540504918
896 174771233945232889616900813405
897 182219057079468684061508361450
898 189979964319177980137167331365
899 198066938602060764988534131941
900 206493493963255845283884069407
901 215273696967922304735070356698
902 224422188997105711638289632444
903 233954209420367601599400951832
904 243885619690025749222366517595
905 254232928393129178869654927575
906 265013317298765010628199399117
907 276244668439672607313889262739
908 287945592268725687983688578306
909 300135456932331311485398439854
910 312834418704500376732245844036
911 326063453626950933982297238047
912 339844390402441015417004549449
913 354199944590261942282886291755
914 369153754154797964351043148123
915 384730416419929828563957161138
916 400955526484184806604772263699
917 417855717153555587888583463636
918 435458700451196752046268012191
919 453793310765386998848188774185
920 472889549699605186768306125584
921 492778632690919601594589694316
922 513493037465536419016302256611
923 535066554402889854988578830539
924 557534338882503792705887220514
925 580932965690590620476710218794
926 605300485566416199412299371054
927 630676483971410573455663287592
928 657102142167299376159407999768
929 684620300692712821418226013561
930 713275525331274145686335749831
931 743114175667600275512773954991
932 774184476331460899110153501336
933 806536591034041069717035585728
934 840222699504354483969315762446
935 875297077437842075314897021466
936 911816179573602876949511193031
937 949838726021002199161961646327
938 989425791961148082853068181317
939 1030640900853359374891200039226
940 1073550121281853326173401572439
941 1118222167582872768952534162278
942 1164728504397963018506633322632
943 1213143455304487958270132772402
944 1263544315680379282145670316085
945 1316011469965908774919549226915
946 1370628513491623488045941171383
947 1427482379047827804665193578583
948 1486663468377825160691104206593
949 1548265788783858552928830063931
950 1612387095042032339678824867636
951 1679129036829742963830662105408
952 1748597311877042658535811445651
953 1820901825061163336836159565978
954 1896156853671918648435644686591
955 1974481219084105522735697124716
956 2055998465082155999213602462882
957 2140837043091338989622373474518
958 2229130504579627420376700901569
959 2321017700904089234362402601931
960 2416642990886213990222679087862
961 2516156456411076307263268094651
962 2619714126356583020760597107030
963 2727478209170343068319308483921
964 2839617334423896047795574235698
965 2956306803686190516176538203127
966 3077728851071314602951041088028
967 3204072913828564402889375064158
968 3335535913357029636443587670133
969 3472322547040956295866567880291
970 3614645591317295462245800526064
971 3762726216401999761215518476594
972 3916794313117912111503705814526
973 4077088832283395979743200339878
974 4243858137138357278226062393188
975 4417360369301851011500742375211
976 4597863828774274611216322235822
977 4785647368516023752729330408157
978 4981000804154699964428961904694
979 5184225339393263354125921809461
980 5395634007713245833072472574184
981 5615552130988980956305318443940
982 5844317795652148538303535002510
983 6082282347069424053956294095519
984 6329810902821104441762649750893
985 6587282885593847664307430623447
986 6855092576427612865243105918592
987 7133649689084059352418476117560
988 7423379966332617663448119326189
989 7724725798979664422018642992058
990 8038146868497340954486506987896
991 8364120814139972896392113557473
992 8703143925469467959075275114802
993 9055731861244847922052827397055
994 9422420395666972504164593796537
995 9803766193005828007815072117278
996 10200347611676319181327260937847
997 10612765538867541777134453485616
998 11041644256871938354002204034439
999 11487632342302703790116114936846
1000 11951403599432301306839759232310