0 1
1 0
2 1
3 1
4 2
5 3
6 4
7 6
8 8
9 12
10 15
11 21
12 28
13 37
14 49
15 63
16 83
17 105
18 138
19 171
20 223
21 275
22 353
23 433
24 551
25 673
26 846
27 1031
28 1282
29 1558
30 1922
31 2327
32 2848
33 3440
34 4179
35 5032
36 6078
37 7293
38 8763
39 10482
40 12534
41 14943
42 17797
43 21146
44 25090
45 29719
46 35138
47 41493
48 48908
49 57578
50 67669
51 79441
52 93104
53 109002
54 127424
55 148791
56 173511
57 202108
58 235132
59 273240
60 317185
61 367756
62 425992
63 492861
64 569734
65 657819
66 758933
67 874554
68 1007077
69 1158340
70 1331432
71 1528675
72 1754036
73 2010419
74 2302901
75 2635170
76 3013613
77 3442953
78 3931219
79 4484415
80 5112601
81 5823450
82 6629453
83 7540456
84 8571939
85 9736440
86 11053127
87 12537996
88 14214631
89 16103415
90 18233369
91 20630309
92 23329921
93 26364852
94 29778833
95 33613076
96 37921166
97 42754830
98 48179737
99 54260679
100 61077950
101 68712485
102 77262488
103 86828626
104 97530990
105 109494487
106 122865751
107 137799418
108 154474517
109 173081780
110 193839750
111 216983208
112 242778573
113 271514226
114 303514836
115 339133661
116 378766141
117 422844201
118 471848877
119 526307370
120 586804461
121 653982193
122 728550931
123 811291408
124 903065433
125 1004820948
126 1117602596
127 1242559330
128 1380956231
129 1534184015
130 1703772764
131 1891403709
132 2098925617
133 2328367904
134 2581962083
135 2862155068
136 3171636985
137 3513354762
138 3890548003
139 4306761372
140 4765892051
141 5272199162
142 5830365297
143 6445502806
144 7123232061
145 7869682644
146 8691593407
147 9596306425
148 10591892429
149 11687137289
150 12891696947
151 14216074203
152 15671809850
153 17271447446
154 19028765808
155 20958732058
156 23077780916
157 25403754095
158 27956235165
159 30756473580
160 33827781819
161 37195445521
162 40887190242
163 44933077018
164 49366049673
165 54221815672
166 59539482725
167 65361429115
168 71734038845
169 78707563312
170 86336968937
171 94681793263
172 103807116229
173 113783419263
174 124687692329
175 136603302685
176 149621255200
177 163840079327
178 179367257508
179 196319146145
180 214822588227
181 235014882334
182 257045602650
183 281076633259
184 307284215790
185 335859075555
186 367008719474
187 400957679720
188 437950093431
189 478250094107
190 522144702572
191 569944408498
192 621986405894
193 678635407216
194 740287268647
195 807370086318
196 880348255624
197 959723914711
198 1046041488765
199 1139889547895
200 1241905903544
201 1352779957907
202 1473258421346
203 1604148251147
204 1746323069444
205 1900726794012
206 2068380858752
207 2250388653908
208 2447943657174
209 2662334827907
210 2894955774303
211 3147311255620
212 3421027542318
213 3717860201748
214 4039705821273
215 4388611289662
216 4766787080072
217 5176618256095
218 5620679556074
219 6101748384082
220 6622821961242
221 7187132612054
222 7798167289833
223 8459685496837
224 9175741553808
225 9950705538941
226 10789288712490
227 11696567929043
228 12678014690637
229 13739523532546
230 14887445267926
231 16128619915975
232 17470414767030
233 18920762519933
234 20488204889773
235 22181936693938
236 24011855851585
237 25988614260382
238 28123675139829
239 30429371679372
240 32918972815556
241 35606750746182
242 38508056411867
243 41639397122816
244 45018523172221
245 48664517021807
246 52597892676687
247 56840698050971
248 61416628990421
249 66351146665406
250 71671608363952
251 77407402045630
252 83590096322216
253 90253594573952
254 97434306900637
255 105171326535320
256 113506626898915
257 122485263460884
258 132155599458934
259 142569536758479
260 153782774319723
261 165855072100224
262 178850546868279
263 192837973790463
264 207891124809862
265 224089113162642
266 241516780282516
267 260265089211287
268 280431566746598
269 302120752575518
270 325444704278631
271 350523509904979
272 377485864504502
273 406469654916895
274 437622617605801
275 471103005678156
276 507080339083594
277 545736165189140
278 587264913919558
279 631874764741781
280 679788620918749
281 731245097549020
282 786499630963598
283 845825604373005
284 909515610592595
285 977882734064869
286 1051261987407744
287 1130011771147129
288 1214515507246810
289 1305183300654670
290 1402453796049721
291 1506796068493863
292 1618711732955879
293 1738737095037164
294 1867445546650883
295 2005450011782643
296 2153405666084491
297 2312012717210147
298 2482019490859634
299 2664225590472450
300 2859485397715037
301 3068711662052973
302 3292879469911472
303 3533030321191534
304 3790276628168301
305 4065806343484353
306 4360888057635727
307 4676876251180065
308 5015217068520650
309 5377454276396428
310 5765235801434343
311 6180320487588423
312 6624585496004476
313 7100033965772566
314 7608803387219268
315 8153174283589914
316 8735579682770201
317 9358614952533011
318 10025048511414242
319 10737832966769808
320 11500117223322282
321 12315259092052096
322 13186838974644511
323 14118674132457644
324 15114834147356419
325 16179657063526970
326 17317766850321384
327 18534091656217295
328 19833883527190174
329 21222739042035768
330 22706621571228437
331 24291884596039971
332 25985296828267017
333 27794068552973717
334 29725879968843460
335 31788910936456177
336 33991872943308350
337 36344042686316248
338 38855298115372919
339 41536156331337347
340 44397814217408802
341 47452191192934736
342 50711975004130686
343 54190669939746369
344 57902648422559795
345 61863205366680804
346 66088616289046329
347 70596198570873694
348 75404376895640155
349 80532752269272905
350 86002175688959051
351 91834825879848430
352 98054292207972671
353 104685662206870841
354 111755614869934892
355 119292519169080798
356 127326538998515202
357 135889744031664205
358 145016227740530227
359 154742232098358708
360 165106280269017907
361 176149316842410712
362 187914856978797001
363 200449144064710837
364 213801317309192540
365 228023588932426461
366 243171432447875753
367 259303781745694266
368 276483242559628366
369 294776316086365256
370 314253636430891882
371 334990221714686442
372 357065740622426702
373 380564794298872084
374 405577215487353627
375 432198384902418098
376 460529566859498436
377 490678264242498136
378 522758594980304133
379 556891690209239119
380 593206116460979255
381 631838322155911951
382 672933110933118869
383 716644142208401930
384 763134461707982237
385 812577062489741944
386 865155479445500687
387 921064417924743653
388 980510419752247084
389 1043712567418739972
390 1110903230031517097
391 1182328851953863198
392 1258250788076010426
393 1338946186806531252
394 1424708925128808867
395 1515850596984541768
396 1612701559780365202
397 1715612040467028371
398 1824953306495434678
399 1941118903300635260
400 2064525964189232305
401 2195616594500770930
402 2334859336557304726
403 2482750717511314006
404 2639816887321495765
405 2806615349226893269
406 2983736790748647284
407 3171807017875843212
408 3371489001355154973
409 3583485038056145522
410 3808539037324202649
411 4047438935639565231
412 4301019250598490194
413 4570163777919868250
414 4855808443717439703
415 5158944316169651538
416 5480620790185335553
417 5821948949673696409
418 6184105122521348260
419 6568334633418848014
420 6975955771301379210
421 7408363977146004017
422 7867036270726719912
423 8353535922742388031
424 8869517392946025404
425 9416731541449544214
426 9997031136064563473
427 10612376663711204650
428 11264842471214153752
429 11956623244485330537
430 12690040854118060756
431 13467551577488007401
432 14291753728356984189
433 15165395705317265900
434 16091384493336620366
435 17072794631146912809
436 18112877682319682139
437 19215072224365651126
438 20383014397628410741
439 21620549030117573838
440 22931741384356722515
441 24320889544438244053
442 25792537494077560797
443 27351488906179513995
444 29002821699871207391
445 30751903388143979895
446 32604407277709456684
447 34566329547186229265
448 36644007271405607595
449 38844137421318818045
450 41173796914053663444
451 43640463746409426934
452 46252039293730687467
453 49016871811744690534
454 51943781231386279379
455 55042085289044825189
456 58321627091088816288
457 61792804160572608647
458 65466599074634997541
459 69354611746652043071
460 73469093472205971295
461 77822982799864656479
462 82429943357360953162
463 87304403701962177614
464 92461599338218459426
465 97917616980632299773
466 103689441218209774890
467 109795003668258792754
468 116253234791442196805
469 123084118466465494765
470 130308749512857070009
471 137949394272551636658
472 146029554456720588903
473 154574034382359834986
474 163609011824739037792
475 173162112625652006164
476 183262489305074443727
477 193940903833395912972
478 205229814835353426905
479 217163469402059737218
480 229777999807980094837
481 243111525330689180858
482 257204259498415042905
483 272098622987078293707
484 287839362522648668616
485 304473676037106926566
486 322051344467561496168
487 340624870476373279107
488 360249624518770714730
489 380983998568660011190
490 402889567969564396204
491 426031261757883849511
492 450477541969714697227
493 476300592318915505705
494 503576516806206697441
495 532385548691892336973
496 562812270445199524747
497 594945845152591642044
498 628880260056366576256
499 664714582761022078932
500 702553230842637818455
501 742506255459768030012
502 784689639771210604850
503 829225612826646447537
504 876242979812406605155
505 925877469392997533338
506 978272099114991035670
507 1033577559696379575670
508 1091952619260546934491
509 1153564548429049526985
510 1218589567433891927747
511 1287213316264063807861
512 1359631349118447601558
513 1436049654290833005756
514 1516685200881442523360
515 1601766513583106917309
516 1691534277070715939003
517 1786241971377041151262
518 1886156539930895105061
519 1991559091789448554977
520 2102745639902419146649
521 2220027877103804668872
522 2343733991846434855540
523 2474209525555465742419
524 2611818273811033881747
525 2756943233434839721454
526 2909987597904910303626
527 3071375803391932582389
528 3241554628076382540384
529 3420994347280373928002
530 3610189947331438098701
531 3809662400956698954995
532 4019960007407901534630
533 4241659800406641848962
534 4475369027421208498149
535 4721726703684148051622
536 4981405244803341654530
537 5255112181727105340804
538 5543591962290862567427
539 5847627843491997859422
540 6168043879131803064285
541 6505707007395244779533
542 6861529243458999278428
543 7236469982164243320859
544 7631538416340239680261
545 8047796076326612426311
546 8486359496824228749526
547 8948403017183996196091
548 9435161721860333669183
549 9947934527754789867426
550 10488087425831466641451
551 11057056884405880301721
552 11656353422207419604604
553 12287565359358897398712
554 12952362755161579297620
555 13652501541642970920946
556 14389827862620362155636
557 15166282628129973304131
558 15983906294922965959648
559 16844843883856976947002
560 17751350245924350330207
561 18705795588818926848351
562 19710671276922838569721
563 20768595917791719814007
564 21882321749269903797990
565 23054741341603686138081
566 24288894630054632510988
567 25587976293794441865107
568 26955343498085407221811
569 28394524017076880577563
570 29909224755867889547193
571 31503340690863429889158
572 33180964248878331101622
573 34946395145875461661272
574 36804150707768384409281
575 38758976696211866816651
576 40815858663975175326419
577 42980033865052238796933
578 45257003746474742314603
579 47652547049425100427099
580 50172733549212108418805
581 52823938464381173125409
582 55612857567365277046131
583 58546523029877315631466
584 61632320038562960752686
585 64878004217320861641954
586 68291719895217063965763
587 71882019259909980715031
588 75657882439242572610386
589 79628738554759195965166
590 83804487793885512096403
591 88195524548732429827136
592 92812761672728751683958
593 97667655907643110726289
594 102772234537086168340688
595 108139123324086119602286
596 113781575794173611932418
597 119713503927074465093653
598 125949510324292542407757
599 132504921921703187729000
600 139395825320832965771244
601 146639103814532564718293
602 154252476187709445051769
603 162254537376029961102580
604 170664801070900638522716
605 179503744361514477282998
606 188792854510626977944838
607 198554677963459119495699
608 208812871695524081452632
609 219592257008188984530614
610 230918875887748572750428
611 242820050047112551305347
612 255324442776788916257214
613 268462123735512109601539
614 282264636819113350957037
615 296765071250273213785061
616 311998136040770209455695
617 328000237982296249159581
618 344809563331670474918778
619 362466163361196645559431
620 381012043955523616134631
621 400491259441785104077065
622 420950010851335291720535
623 442436748817367635351781
624 465002281325248527243877
625 488699886538978957869086
626 513585430940829793052701
627 539717493028450522702816
628 567157492828563142978046
629 595969827494348229006062
630 626222013269719688364108
631 657984834112496608086915
632 691332497285953967362589
633 726342796237945129202521
634 763097281105761275925371
635 801681437195594307921241
636 842184871806064896188996
637 884701509777069026434145
638 929329798167548605818582
639 976172920478783316708242
640 1025339020864055296641841
641 1076941438779850281561052
642 1131098954560072019138395
643 1187936046410511541236139
644 1247583159349354252073085
645 1310176986636870086227250
646 1375860764268384859202064
647 1444784579123749539425975
648 1517105691400086500298533
649 1592988871975640788848227
650 1672606755388950452011607
651 1756140209140719612648098
652 1843778720065219502667884
653 1935720798543541364176882
654 2032174401373772673591528
655 2133357374141223968121104
656 2239497913978158306688779
657 2350835053633337401003227
658 2467619167821894002269282
659 2590112502859980634715207
660 2718589730643028543149425
661 2853338528063767362115522
662 2994660183025071746439395
663 3142870228243718647436160
664 3298299104104958871110050
665 3461292851872879328449387
666 3632213838630659268235307
667 3811441515374338860058596
668 3999373209758588527211498
669 4196424955047346506510091
670 4403032356903277882836719
671 4619651499709711342190683
672 4846759894206522881515643
673 5084857468286964054799254
674 5334467602897526771515859
675 5596138215054836256245463
676 5870442890096540245638933
677 6157982065362028082406977
678 6459384267610322153945074
679 6775307406568963430809866
680 7106440127128458765916626
681 7453503222791655237564811
682 7817251113118153780869257
683 8198473388007757160694648
684 8597996421808522792856781
685 9016685060348793335999935
686 9455444384145878881505385
687 9915221551168693560354033
688 10397007722697648127761122
689 10901840075961541940145977
690 11430803907410947794025651
691 11985034830636910081846577
692 12565721073138420220438154
693 13174105876305510123210523
694 13811490003195579729405636
695 14479234358859266836497841
696 15178762728200416260299469
697 15911564636550087907285583
698 16679198338381720453118205
699 17483293939808132724650705
700 18325556660768727659973724
701 19207770243048632677902394
702 20131800510561408067543618
703 21099599088581887088678022
704 22113207288929677530110868
705 23174760168382258726411303
706 24286490767936651689956791
707 25450734540842588234772175
708 26669933977698403748630747
709 27946643437232618478521562
710 29283534191793086831972536
711 30683399696927564230133035
712 32149161094871630838821944
713 33683872962154755642420786
714 35290729312003322688702875
715 36973069862650027348244248
716 38734386583166043785363259
717 40578330528901801333519604
718 42508718979171414660064029
719 44529542890327469885798209
720 46644974677967821020079437
721 48859376342573582683493580
722 51177307953522029488437757
723 53603536507025477273384704
724 56143045174245465808395104
725 58801042956493051052909328
726 61582974765182473268097225
727 64494531944925728560245939
728 67541663258975112998303706
729 70730586357004878566527802
730 74067799746111041501827531
731 77560095286761718330310255
732 81214571236392341354701702
733 85038645864268614685595009
734 89040071662282315428579047
735 93226950177355128320954627
736 97607747492254920365268959
737 102191310382727450976764173
738 106986883180069970405680290
739 112004125369467758939043391
740 117253129955740223536229391
741 122744442629441904394852985
742 128489081767699936019871217
743 134498559305581176425796033
744 140784902515338264031772282
745 147360676732417987674977498
746 154239009068801244868152718
747 161433613155910753564063249
748 168958814961149232373809271
749 176829579723941575203743778
750 185061540059133463971016921
751 193671025277565669648069706
752 202675091975787251606242735
753 212091555949006732787959046
754 221939025483703048413980649
755 232236936088637132567926538
756 243005586725521333248190553
757 254266177603121409857585982
758 266040849601291865279332881
759 278352725394177973823455502
760 291225952344770921210004380
761 304685747245968031002261935
762 318758442986488971575416089
763 333471537223216712107490582
764 348853743144997128674887028
765 364935042416422298693286185
766 381746740393875879660965399
767 399321523709906023565834148
768 417693520326056668964820523
769 436898362158395528342712303
770 456973250384380261711364497
771 477957023544158717727178126
772 499890228554167927183872676
773 522815194755726488197792089
774 546776111126479527036309997
775 571819106787791914433062735
776 597992334946778260478628599
777 625346060417334737725884223
778 653932750870594123814805625
779 683807171971378216929091166
780 715026486563779667731787927
781 747650358075673406579733330
782 781741058319058414265281659
783 817363579870356395042708470
784 854585753222481615157498618
785 893478368908325378052411948
786 934115304803621489769386779
787 976573658825641088262940389
788 1020933887253175188101715851
789 1067279948902451523183321283
790 1115699455403385442882619204
791 1166283827830516761803518903
792 1219128459953541441079505125
793 1274332888383125386382407399
794 1332000969899113910865192000
795 1392241066259922441773565172
796 1455166236804260333619101153
797 1520894439168978078256525384
798 1589548738460210910372612363
799 1661257525228675246822096049
800 1736154742614456050833830577
801 1814380123041436580904678567
802 1896079434857191701267254539
803 1981404739330200947497549935
804 2070514658433191557872872787
805 2163574653858777404811950468
806 2260757317731901991797748702
807 2362242675502377086626198325
808 2468218501520651202757677760
809 2578880647820268745672991692
810 2694433386651944815385033184
811 2815089767336175195134803129
812 2941071988024517518655357533
813 3072611782983476751931844518
814 3209950826040038016246632056
815 3353341150853634920131559264
816 3503045588706497221262289472
817 3659338224532171733402550707
818 3822504871931376216149949815
819 3992843567954470453847395070
820 4170665088461582143774093680
821 4356293484904006924216023612
822 4550066643404834325197162028
823 4752336867051987742371870210
824 4963471482353984595305281669
825 5183853470846826747696910406
826 5413882126880557806402480538
827 5653973742655225273016594939
828 5904562321619360971807212952
829 6166100321388639981869286648
830 6439059427389262025591157330
831 6723931358478759097412692498
832 7021228705847604879252704733
833 7331485806557063031543831524
834 7655259653123472989770198097
835 7993130840615446574893977177
836 8345704552789625469850054779
837 8713611588851473356101435876
838 9097509432491519391641351241
839 9498083364913204852311929164
840 9916047623637572212806962498
841 10352146608941073272037639621
842 10807156139857412983558364299
843 11281884761751106606320128307
844 11777175107551060378412623869
845 12293905314815424960302202243
846 12832990500886070289769459536
847 13395384298480637661614661805
848 13982080454164202324263387069
849 14594114492239383532836620448
850 15232565446695345680053085855
851 15898557663960703870274571271
852 16593262679315077205072059389
853 17317901169926982956115294788
854 18073744987604258143755271909
855 18862119274465187034424780372
856 19684404664866459813768295636
857 20542039577055835238059398283
858 21436522598155523720652874820
859 22369414966224579364439503682
860 23342343153297731179382986326
861 24357001553451708983869939512
862 25415155280111122518170463289
863 26518643076971823780943773375
864 27669380347093476956090249451
865 28869362304892140260593409511
866 30120667255951251657548083303
867 31425460009762735601706686251
868 32785995430712408174918954650
869 34204622132832545448289481570
870 35683786324062975269763543900
871 37226035805987305741683803989
872 38834024135246686405617478878
873 40510514953076613033502664503
874 42258386489666705726133191851
875 44080636250305762924095819782
876 45980385890548901201965571866
877 47960886287926725425438285465
878 50025522818012633635890554828
879 52177820842969877056740525862
880 54421451421019492081961010811
881 56760237245599862496574416325
882 59198158823333316682886685115
883 61739360900270809312052908841
884 64388159146257485902362306691
885 67149047107645598811919554758
886 70026703438982196325199346513
887 73025999424712879198008553003
888 76152006802375338932673298090
889 79410005899202811060978001225
890 82805494094523898958623603661
891 86344194620826712075759900474
892 90032065716858108532667447432
893 93875310146648105600365603375
894 97880385098891712898633108495
895 102054012481680425101686666723
896 106403189628160183942581847777
897 110935200429296455738525051056
898 115657626910557292963653777311
899 120578361269976325064684948411
900 125705618395737011464269921414
901 131047948882121450045173969995
902 136614252563399370933476296965
903 142413792585989709863337046031
904 148456210040016511257888802470
905 154751539172196697947183877537
906 161310223202847998893179558604
907 168143130770684673671704234806
908 175261573029985536611882693604
909 182677321425666573731066531950
910 190402626172778487202043611591
911 198450235467970987162878039600
912 206833415461530320736796469515
913 215565971019697357334945680462
914 224662267308120710717765637784
915 234137252228485627859576960902
916 244006479741595332879799279069
917 254286134111459719233579792359
918 264993055106277819387476255986
919 276144764193577669411338198927
920 287759491768211591690778885199
921 299856205453388647922806706719
922 312454639516471130907602620523
923 325575325442860359763171282279
924 339239623712961300613028232738
925 353469756828937335629052830073
926 368288843639758965733784553263
927 383720935014904831844886983505
928 399791050919003851278044962355
929 416525218941704763401447198688
930 433950514339138214750095668510
931 452095101645487765655079218245
932 470988277915424720857572299773
933 490660517660478362571036714957
934 511143519544823471954723403610
935 532470254908461668295159995984
936 554675018188368197658458707986
937 577793479310861894531343861588
938 601862738131249917184546369429
939 626921380999690885782717467462
940 653009539535227727562882469904
941 680168951693055067594379595753
942 708443025213323620729723702846
943 737876903543135810655021012796
944 768517534326871747407853229192
945 800413740563592677535416101112
946 833616294534019852727429273456
947 868177994603470272242942689558
948 904153745011167536244692853236
949 941600638760525833472691839728
950 980578043729349330372875905362
951 1021147692123387583369454260755
952 1063373773401362410203648899457
953 1107323030804422524736692840830
954 1153064861628012446901109224401
955 1200671421379351302835342365685
956 1250217731969129392362224945479
957 1301781794091635365315476506175
958 1355444703953349800729267110690
959 1411290774516071478743982037255
960 1469407661426907031426701759826
961 1529886493813942550178090585289
962 1592822010133154593520083254434
963 1658312699259097543920692974784
964 1726460947019153062342798493689
965 1797373188378635250369406514900
966 1871160065491841943595936583378
967 1947936591842218229380477984714
968 2027822322703183995765756268320
969 2110941532159863153998521340649
970 2197423396940970686986207301125
971 2287402187319455153114824465810
972 2381017465350192706150417215163
973 2478414290723074629403024983893
974 2579743434520259323493134406235
975 2685161601177162489968419664926
976 2794831658957973006961004490512
977 2908922879268097912664390709858
978 3027611185137996765580615198518
979 3151079409225355062673635780256
980 3279517561695508907342367918087
981 3413123108353460822909953885765
982 3552101259414761914982116293163
983 3696665269316971123278452965795
984 3847036747988382459220195871018
985 4003445984006229123576023573410
986 4166132280092675719842716188743
987 4335344301413590317485329885170
988 4511340437162395570317233803871
989 4694389175929227099352832598189
990 4884769495374228947781393355298
991 5082771266743085577137574604396
992 5288695674782881125798474675338
993 5502855653637085879077417111740
994 5725576339319953268593869776281
995 5957195539392865623454413962131
996 6198064220488252299132197031697
997 6448547014350618219505809797800
998 6709022743089026215864280852010
999 6979884964361072560951582860280
1000 7261542537235046864372026256021