0 1
1 0
2 1
3 1
4 2
5 2
6 4
7 4
8 7
9 8
10 12
11 14
12 21
13 24
14 34
15 41
16 55
17 66
18 88
19 105
20 137
21 165
22 210
23 253
24 320
25 383
26 478
27 574
28 708
29 847
30 1039
31 1238
32 1507
33 1794
34 2167
35 2573
36 3094
37 3660
38 4378
39 5170
40 6153
41 7245
42 8591
43 10087
44 11914
45 13959
46 16424
47 19196
48 22519
49 26252
50 30701
51 35717
52 41646
53 48342
54 56224
55 65121
56 75547
57 87331
58 101066
59 116600
60 134647
61 155038
62 178651
63 205343
64 236131
65 270928
66 310962
67 356169
68 408046
69 466610
70 533623
71 609237
72 695578
73 792906
74 903811
75 1028764
76 1170827
77 1330772
78 1512301
79 1716486
80 1947826
81 2207851
82 2501928
83 2832214
84 3205191
85 3623697
86 4095605
87 4624711
88 5220436
89 5887816
90 6638248
91 7478186
92 8421448
93 9476370
94 10659543
95 11981699
96 13462885
97 15116626
98 16967206
99 19031739
100 21339417
101 23911834
102 26784253
103 29983571
104 33552415
105 37524344
106 41950627
107 46873053
108 52353455
109 58443396
110 65217506
111 72739457
112 81098953
113 90374472
114 100674037
115 112093786
116 124763797
117 138801828
118 154364067
119 171594522
120 190680895
121 211798491
122 235172861
123 261017329
124 289602259
125 321186852
126 356095340
127 394641603
128 437214305
129 484193270
130 536043530
131 593224104
132 656291385
133 725798623
134 802411183
135 886795381
136 979745604
137 1082063336
138 1194696815
139 1318608064
140 1454928240
141 1604811073
142 1769604112
143 1950689437
144 2149671688
145 2368203564
146 2608194590
147 2871619379
148 3160747519
149 3477935703
150 3825880113
151 4207389269
152 4625663839
153 5084047903
154 5586336956
155 6136508817
156 6739061662
157 7398721010
158 8120814033
159 8910949753
160 9775430911
161 10720908961
162 11754836210
163 12885091293
164 14120479365
165 15470324960
166 16945022324
167 18555597523
168 20314312649
169 22234192364
170 24329692015
171 26616184918
172 29110697565
173 31831360282
174 34798214855
175 38032623080
176 41558159460
177 45399973905
178 49585774460
179 54145147465
180 59110637816
181 64517020845
182 70402496542
183 76807909204
184 83778062903
185 91360893907
186 99608918036
187 108578349895
188 118330703303
189 128931854054
190 140453804468
191 152973696559
192 166575755711
193 181350249106
194 197395636376
195 214817471128
196 233730774618
197 254258890939
198 276536105168
199 300706448427
200 326926597263
201 355364629259
202 386203227436
203 419638401890
204 455883029522
205 495165541765
206 537733848780
207 583853998450
208 633814519647
209 687925076238
210 746521272980
211 809963310412
212 878641319492
213 952974031019
214 1033414689617
215 1120449773392
216 1214605549194
217 1316446859433
218 1426584408757
219 1545673644474
220 1674422848222
221 1813592164482
222 1964002586262
223 2126535165504
224 2302141016135
225 2491840754407
226 2696735626362
227 2918007260051
228 3156930044792
229 3414871256893
230 3693304861665
231 3993812092792
232 4318096832235
233 4667986767382
234 5045450531946
235 5452599544644
236 5891707148593
237 6365211262359
238 6875735742946
239 7426094034768
240 8019313019148
241 8658637830305
242 9347558524221
243 10089816267629
244 10889433151557
245 11750720031501
246 12678309863608
247 13677167462472
248 14752626827646
249 15910403138953
250 17156634544056
251 18497896803878
252 19941250084020
253 21494256663533
254 23165033390553
255 24962272942015
256 26895302622102
257 28974109784575
258 31209407753999
259 33612666039319
260 36196184312171
261 38973128147763
262 41957612038559
263 45164741562447
264 48610706550555
265 52312830630202
266 56289675871795
267 60561100804647
268 65148377949546
269 70074261628265
270 75363119986492
271 81041014007489
272 87135845905727
273 93677450971882
274 100697764357235
275 108230927677725
276 116313476485996
277 124984463720098
278 134285670534315
279 144261748983491
280 154960459107441
281 166432833655195
282 178733444707987
283 191920593501837
284 206056610382020
285 221208073219442
286 237446144837776
287 254846824084280
288 273491325418369
289 293466367097673
290 314864598313791
291 337784929571198
292 362333013281588
293 388621622196933
294 416771190144910
295 446910244983573
296 479176017116743
297 513714934314753
298 550683306432456
299 590247890521985
300 632586661258577
301 677889455679899
302 726358840145338
303 778210845273265
304 833675941407361
305 892999875828239
306 956444770222301
307 1024290073577189
308 1096833796972469
309 1174393597317632
310 1257308166453069
311 1345938462976581
312 1440669274775946
313 1541910618134446
314 1650099495343153
315 1765701482735836
316 1889212707429677
317 2021161648846961
318 2162111361623690
319 2312661517974176
320 2473450907307247
321 2645159750251914
322 2828512508954705
323 3024280507623332
324 3233285091659847
325 3456400593590766
326 3694557884045648
327 3948747726792255
328 4220024769448006
329 4509511336959300
330 4818401915776489
331 5147967440816276
332 5499560333558504
333 5874619344324504
334 6274675211653137
335 6701356129532565
336 7156394103557447
337 7641631120821200
338 8159026287682383
339 8710662789505165
340 9298755904572312
341 9925660851702198
342 10593881786185014
343 11306080644661709
344 12065087241870227
345 12873909235390179
346 13735743455603140
347 14653987127930851
348 15632250584165256
349 16674369895761719
350 17784421132558027
351 18966734579055924
352 20225910725571008
353 21566836260248344
354 22994701999532577
355 24515020870919218
356 26133648014313139
357 27856800996016075
358 29691082339040343
359 31643502237601240
360 33721503804691101
361 35932988587346438
362 38286344853846542
363 40790476245322858
364 43454833461739081
365 46289446425135644
366 49304959765329635
367 52512668913117108
368 55924559833559922
369 59553349516249696
370 63412530455007317
371 67516416057054420
372 71880190425563068
373 76519959269162235
374 81452805608348415
375 86696846834010554
376 92271297029097027
377 98196530900175710
378 104494153485056734
379 111187071763659425
380 118299572610992862
381 125857402986167993
382 133887857087131326
383 142419866120127205
384 151484095721525844
385 161113046423345521
386 171341162529179091
387 182204944518509402
388 193743070697080632
389 205996522924627449
390 219008722509444148
391 232825670799824763
392 247496100959165605
393 263071635135689323
394 279606953937339401
395 297159972088568140
396 315792027628783508
397 335568078178429325
398 356556912112470109
399 378831367796419728
400 402468569236747601
401 427550170912900395
402 454162620685936948
403 482397433144586312
404 512351482864189479
405 544127309510462542
406 577833444882904127
407 613584753381925512
408 651502796651979753
409 691716213416390786
410 734361125958872602
411 779581563774245320
412 827529916593411642
413 878367406791101624
414 932264594178238802
415 989401902651047774
416 1049970182550640460
417 1114171297641788553
418 1182218751474269102
419 1254338341449702661
420 1330768856324388939
421 1411762804861338702
422 1497587192396350885
423 1588524332392706893
424 1684872710854376411
425 1786947890010252949
426 1895083470315181090
427 2009632096493343745
428 2130966527927951375
429 2259480758405732356
430 2395591206865098713
431 2539737963415758156
432 2692386113711151457
433 2854027125175882724
434 3025180319703089890
435 3206394415528046051
436 3398249164533331989
437 3601357066873460570
438 3816365190923218152
439 4043957079595838143
440 4284854772908750723
441 4539820926972516007
442 4809661061286097541
443 5095225913624145886
444 5397413936539826153
445 5717173913859375784
446 6055507733486270977
447 6413473293956984773
448 6792187583524102600
449 7192829908261212046
450 7616645310591505840
451 8064948153774480389
452 8539125916569909449
453 9040643172636401907
454 9571045801904325380
455 10131965407500226633
456 10725123988693663436
457 11352338842462757595
458 12015527747618380503
459 12716714403098276433
460 13458034178093846516
461 14241740144649007894
462 15070209454380794496
463 15945950029006991816
464 16871607630614650318
465 17849973280416653939
466 18883991096532142005
467 19976766518637444064
468 21131574994957721864
469 22351871098590876683
470 23641298153940938257
471 25003698339443686447
472 26443123353068015729
473 27963845606040513965
474 29570370037402632567
475 31267446514198337550
476 33060082916496253251
477 34953558871485175657
478 36953440242944778649
479 39065594339896430773
480 41296205958364887586
481 43651794219765106589
482 46139230328065417275
483 48765756209104438839
484 51539004163069609761
485 54467017493575712957
486 57558272253881935501
487 60821700073971137735
488 64266712219309318398
489 67903224845537117019
490 71741685610997313558
491 75793101612177583716
492 80069068815916136193
493 84581802954613853041
494 89344172071194632587
495 94369730681588542427
496 99672755755398910279
497 105268284484498172541
498 111172154055226837556
499 117401043396402560062
500 123972517135036533402
501 130905071734963332849
502 138218184067810961405
503 145932362395147023939
504 154069200030155348825
505 162651431662012470697
506 171702992631788937270
507 181249081148147774329
508 191316223753804809330
509 201932344037016883439
510 213126834922992581190
511 224930634546475980182
512 237376306066300848896
513 250498121431234894684
514 264332149485950477713
515 278916348435752474201
516 294290663089235142157
517 310497126908187724907
518 327579969316783146960
519 345585728311567980115
520 364563368859889597533
521 384564407142190991698
522 405643041164360955207
523 427856287811379791593
524 451264126910242612004
525 475929652391289179051
526 501919231161234106337
527 529302669797260085048
528 558153389724574914145
529 588548611009620090849
530 620569545484605304830
531 654301599361221387242
532 689834586107002808656
533 727262949771042722704
534 766685999595215897463
535 808208156129977836484
536 851939209758940424844
537 897994591887509226796
538 946495659773650714435
539 997569995296593049076
540 1051351718721696782111
541 1107981817802557304377
542 1167608493365647594895
543 1230387521769013972862
544 1296482635474909008065
545 1366065922184103821734
546 1439318243874466417533
547 1516429676254136989154
548 1597599970083488727035
549 1683039034945758959024
550 1772967447041816882260
551 1867616981666234185592
552 1967231172071892108802
553 2072065895466067349568
554 2182389987988476285478
555 2298485889509297136531
556 2420650320253380031207
557 2549194990194034717038
558 2684447343391880870031
559 2826751338338824088548
560 2976468266666730334052
561 3133977611409907268489
562 3299677947381168061958
563 3473987884993292791720
564 3657347060303360031396
565 3850217172769459240067
566 4053083073734075077962
567 4266453907297749480722
568 4490864306854937978932
569 4726875649147836206327
570 4975077369390317124808
571 5236088339529739680058
572 5510558313503681963591
573 5799169441793015702454
574 6102637859460155578634
575 6421715350231402325176
576 6757191091173187035172
577 7109893480804759149085
578 7480692055589977451057
579 7870499497962927250445
580 8280273741257570136180
581 8711020175039708511008
582 9163793956676727824639
583 9639702433021305606390
584 10139907678550966053898
585 10665629154255111579954
586 11218146494162623874502
587 11798802424258299911290
588 12409005821281130467937
589 13050234916654380851852
590 13724040653693530940932
591 14432050203892949768330
592 15175970651148243056811
593 15957592850320020579024
594 16778795469769782950128
595 17641549224937532997252
596 18547921313434150151243
597 19500080059446398447614
598 20500299778844581820983
599 21550965873589515291973
600 22654580167826960283622
601 23813766495142054370117
602 25031276550448498558133
603 26309996016945004797115
604 27652950982796672070433
605 29063314659025794114444
606 30544414414557381843488
607 32099739141056397749812
608 33732946964903714823313
609 35447873320209930499003
610 37248539401739951726241
611 39139161013029476901046
612 41124157830227225054028
613 43208163098456853493380
614 45396033783040457295620
615 47692861194033075075709
616 50103982108378193527790
617 52634990409945014021495
618 55291749273899614431873
619 58080403917652128003483
620 61007394947163759530764
621 64079472323022463479652
622 67303709977608988638318
623 70687521110131156582797
624 74238674193610159921699
625 77965309723186414064996
626 81875957742834920388358
627 85979556182687757141260
628 90285470047325316118547
629 94803511490326281892959
630 99543960818998263859984
631 104517588467957327832945
632 109735677989352773718712
633 115210050102095052654846
634 120953087852099225346553
635 126977762929931043136540
636 133297663202455459176046
637 139927021509273732907893
638 146880745785540388559460
639 154174450566748045386266
640 161824489942502132436279
641 169847992020114299022855
642 178262894970944742800523
643 187087984726041035160537
644 196342934400431213788176
645 206048345518857761619838
646 216225791129302318967350
647 226897860883893486782647
648 238088208181153104563599
649 249821599456595947293156
650 262123965723910831623395
651 275022456461831852416485
652 288545495957925302619961
653 302722842213225510799388
654 317585648528730355410721
655 333166527887309292400227
656 349499620262676082708262
657 366620662979463487470145
658 384567064267623853374773
659 403377980146618413887893
660 423094394795201515278747
661 443759204554711769967820
662 465417305735356845618075
663 488115686386966086797084
664 511903522218571136526619
665 536832276843061637869644
666 562955806547445223176546
667 590330469781048077872570
668 619015241579761887478328
669 649071833136193460225777
670 680564816752928062173258
671 713561756407838477862570
672 748133344189415820988785
673 784353542851820676716398
674 822299734770198282674329
675 862052877568560178373636
676 903697666725300981204200
677 947322705453253462701448
678 993020682186000220977241
679 1040888555994115459417755
680 1091027750292011808658522
681 1143544355188192749292199
682 1198549338871046409016891
683 1256158768414668820290473
684 1316494040431031010071555
685 1379682121987446507979901
686 1445855802252782375415074
687 1515153955328858686384263
688 1587721814770809786368762
689 1663711260293620355951275
690 1743281117212413525040488
691 1826597469158033155858148
692 1913833984663071104270085
693 2005172258208076311699379
694 2100802166374759891056655
695 2200922239748324652489819
696 2305740051271833029922894
697 2415472621751688713596367
698 2530346843278058822060542
699 2650599921321202209499928
700 2776479836333664119809659
701 2908245825686558229956851
702 3046168886841691278995184
703 3190532302660828251171626
704 3341632189831788848817505
705 3499778071392065753562529
706 3665293474414249600591220
707 3838516553920195800699024
708 4019800744180031800307585
709 4209515438556617130822662
710 4408046699151196571097089
711 4615797997512597010529736
712 4833190987773836435859527
713 5060666313588976823411093
714 5298684450351416293333515
715 5547726584186414214776337
716 5808295529326343127780379
717 6080916685491702347340764
718 6366139037024492976678967
719 6664536195538375712813253
720 6976707487982028774833088
721 7303279092033596041128169
722 7644905220885152486904355
723 8002269359501641737442450
724 8376085554589475020744308
725 8767099760540006103563506
726 9176091243774233213461934
727 9603874047950085988939177
728 10051298522665952664986909
729 10519252918334618749297744
730 11008665050086063109050372
731 11520504033604159155076008
732 12055782095999458055374352
733 12615556464873548193898007
734 13200931338941413729288786
735 13813059943638933110453757
736 14453146675368403628577146
737 15122449338103844989545522
738 15822281476319489561076557
739 16554014808282698624242423
740 17319081764011285463193300
741 18118978132282909431082684
742 18955265821361301267194422
743 19829575738202581830086381
744 20743610791201749885123418
745 21699149021649788150188016
746 22698046869389835829276459
747 23742242578284264911104876
748 24833759747445263280687007
749 25974711034319177730845237
750 27167302016080102655531934
751 28413835215941466168785567
752 29716714301385896950836524
753 31078448461484007582928887
754 32501656970892533680082443
755 33989073948311306609052143
756 35543553317628735385293578
757 37168073980194936140548422
758 38865745207144526449943285
759 40639812260922874328892277
760 42493662255687614995738145
761 44430830266513379396025840
762 46455005697883496329689967
763 48570038922235143714080866
764 50779948199920892655057607
765 53088926892261295640789632
766 55501350980003364891712158
767 58021786899843106066814402
768 60654999712357504188554833
769 63405961615069129183910780
770 66279860815104364187802561
771 69282110776321558151287296
772 72418359856577686917004872
773 75694501351258270334041718
774 79116683960046158352299038
775 82691322694405445335877730
776 86425110244170676579127620
777 90325028822180557460779636
778 94398362506877120862630857
779 98652710103393001118281512
780 103095998544704216315135961
781 107736496855084799736943704
782 112582830699232951692199192
783 117643997541159546580835511
784 122929382438147736292445697
785 128448774495881171807248222
786 134212384012147304748314211
787 140230860337384467248870295
788 146515310481748360155479311
789 153077318499315587736672991
790 159928965681554296199297500
791 167082851593220589980329187
792 174552115985465376078017246
793 182350461622058910312626837
794 190492178056388547179701980
795 198992166398109824913714336
796 207865965110210862235085557
797 217129776878585334266309499
798 226800496598230840155518580
799 236895740521644787585596228
800 247433876617164027386927929
801 258434056186579922358807558
802 269916246793698906264789950
803 281901266557245117824776051
804 294410819864016927549808847
805 307467534560088608252009220
806 321095000680554064506700891
807 335317810780354649735195947
808 350161601931643811573473124
809 365653099455365909049283998
810 381820162457858040398160397
811 398691831245702733881350756
812 416298376695428582011499547
813 434671351657285437685225599
814 453843644475946005675600291
815 473849534713843134167547909
816 494724751166752964670250615
817 516506532264338305600771028
818 539233688952564252399580994
819 562946670158269317917125329
820 587687630940692590597345652
821 613500503438417632529641267
822 640431070725055215488235775
823 668527043690959806783110339
824 697838141073506657619618687
825 728416172762767318597445271
826 760315126515052353440482958
827 793591258211466720488238141
828 828303185804683868788449554
829 864511987102216773146882551
830 902281301540987316525039778
831 941677436113495182196051310
832 982769475612908711813739809
833 1025629397370362150704631800
834 1070332190665301318403263503
835 1116955980996181284077711264
836 1165582159406954707058413797
837 1216295517071790918114200497
838 1269184385349222649735104097
839 1324340781524502080053409670
840 1381860560468374104210912850
841 1441843572448689722421485853
842 1504393827341429408875028962
843 1569619665496602061214081155
844 1637633935525408057987278700
845 1708554179284685945280627054
846 1782502824346420585051491775
847 1859607384250515605129786499
848 1940000666851690651885615134
849 2023820991082646295329227268
850 2111212412469265288023058675
851 2202324957745826832836083312
852 2297314868932878629010255836
853 2396344857253618597719203982
854 2499584367280428278425236300
855 2607209851717485472926832607
856 2719405057242381555143865555
857 2836361321845118332242909264
858 2958277884121157216845476565
859 3085362204991898864633408224
860 3217830302345668632836791957
861 3355907099110343688587341928
862 3499826785289960954100449244
863 3649833194517167442817525138
864 3806180195696198973584898508
865 3969132100332172565625163515
866 4138964086167046955802737807
867 4315962637765405848797638159
868 4500426004719665348455076019
869 4692664678168941483465099940
870 4893001886354281319413485304
871 5101774109959573606257837213
872 5319331618018097092996894223
873 5546039025193409799458329041
874 5782275871276264809800391684
875 6028437223770282582903361851
876 6284934304474610108255383072
877 6552195141005320261356890073
878 6830665244235514502448174341
879 7120808312670286698796323503
880 7423106964813830922966819000
881 7738063500625050086756066880
882 8066200693202283938135151441
883 8408062611879951931880597660
884 8764215477967542723352555624
885 9135248554406902615044868941
886 9521775070675041968845405871
887 9924433184308801707242169104
888 10343886980482894238145306313
889 10780827511125837389044510421
890 11235973875117673420529566242
891 11710074341170550320033090586
892 12203907515057135268254879408
893 12718283552913518650597981498
894 13254045422412020634642453846
895 13812070213665851052494950631
896 14393270501801555288394201104
897 14998595763206940934302572425
898 15629033847541785102506502364
899 16285612507676008992993324701
900 16969400989805658964859847530
901 17681511686080476303114890047
902 18423101852168994126793746248
903 19195375392277063158027796274
904 19999584714234858060811292801
905 20837032657364398713622321508
906 21709074495946291177910747147
907 22617120021208931747003904553
908 23562635704878174207648853292
909 24547146947438131910940917455
910 25572240414377237440390919052
911 26639566463815107146412592978
912 27750841669038556773551728228
913 28907851439605958572277550738
914 30112452744821978920353991814
915 31366576943525715891840667334
916 32672232724288908580976117776
917 34031509160272776821439644793
918 35446578883157316056606310103
919 36919701380720493092566709179
920 38453226422822538425183181058
921 40049597620726775430036164116
922 41711356124879595090138499918
923 43441144466462008965640474690
924 45241710548230803679207311243
925 47115911790371750656822039753
926 49066719437308415646304260875
927 51097223031630252830103428493
928 53210635061541417066559758910
929 55410295788468763332106233764
930 57699678261723152290851908463
931 60082393527363385137220159770
932 62562196038686976805442974671
933 65142989276046717402799430781
934 67828831583987527159390206405
935 70623942233993856725981503577
936 73532707721455648538664114295
937 76559688305779205274994363323
938 79709624802910936024562680741
939 82987445639884559517302285559
940 86398274181369602845196475292
941 89947436338567741097069767397
942 93640468471198321008432261714
943 97483125593711171130880541339
944 101481389897289181212160767538
945 105641479599630043487677578876
946 109969858134952705135966350098
947 114473243697133394504720188983
948 119158619149366371260959736340
949 124033242314238685810347338518
950 129104656658635178961845806256
951 134380702388421506069315268357
952 139869527968419285606189282683
953 145579602083759230339866895644
954 151519726059306715338283505845
955 157699046754469191551047223384
956 164127069951348852970035330496
957 170813674254865326720434561414
958 177769125524175908679494979973
959 185004091855432081025989543808
960 192529659136666150452635755303
961 200357347196366609704901213150
962 208499126568112133586985824142
963 216967435894456402466743809877
964 225775199994127598802671680168
965 234935848617490479597440576044
966 244463335916155362989096339100
967 254372160653568768128025261903
968 264677387184426427026563163505
969 275394667231771032439166704608
970 286540262491717716771816726519
971 298131068096848404496138591748
972 310184636970476940544917939242
973 322719205105167186809795718919
974 335753717800133042682997959412
975 349307856893417827214188040332
976 363402069026089528363063065334
977 378057594977051587450208213837
978 393296500108507015055741307493
979 409141705963578437851335537989
980 425617023059131108916589965143
981 442747184918419821774014920529
982 460557883389839174434897224609
983 479075805299747646032922463036
984 498328670489116856411572174638
985 518345271285574086950683194318
986 539155513464318379882694897544
987 560790458753342136040830682676
988 583282368940443274032805489789
989 606664751641609378817725466883
990 630972407792559576890425266127
991 656241480927481581743688590450
992 682509508311367829031052861545
993 709815473994773010216746269093
994 738199863862355746807958809875
995 767704722749164377436321076446
996 798373713701353858670601361585
997 830252179460809883789314200708
998 863387206256083492268834110826
999 897827689985034388054702726695
1000 933624404877723008811705095741