0 1
1 0
2 1
3 0
4 1
5 1
6 3
7 2
8 3
9 3
10 8
11 8
12 11
13 14
14 19
15 19
16 29
17 37
18 47
19 61
20 79
21 85
22 114
23 141
24 168
25 210
26 257
27 309
28 395
29 468
30 556
31 685
32 816
33 966
34 1162
35 1380
36 1667
37 1988
38 2340
39 2777
40 3305
41 3900
42 4571
43 5423
44 6348
45 7385
46 8700
47 10188
48 11846
49 13876
50 16118
51 18757
52 21846
53 25369
54 29342
55 33954
56 39267
57 45333
58 52305
59 60298
60 69278
61 79816
62 91577
63 105069
64 120510
65 138081
66 158052
67 180774
68 206382
69 235672
70 268723
71 306272
72 348558
73 396757
74 450776
75 512018
76 581003
77 658928
78 747099
79 846112
80 957097
81 1082804
82 1223719
83 1382139
84 1559762
85 1759754
86 1983392
87 2234685
88 2515680
89 2830743
90 3183024
91 3576775
92 4017076
93 4510174
94 5059386
95 5672960
96 6357379
97 7121021
98 7971403
99 8919765
100 9974118
101 11149604
102 12456566
103 13909865
104 15524540
105 17318293
106 19310496
107 21522736
108 23976199
109 26697582
110 29713758
111 33058084
112 36759161
113 40860519
114 45398453
115 50418438
116 55970206
117 62110327
118 68892325
119 76387621
120 84665210
121 93798596
122 103878940
123 115003346
124 127262325
125 140780619
126 155678270
127 172085880
128 190154699
129 210050521
130 231934803
131 256018780
132 282504992
133 311617195
134 343615665
135 378779622
136 417397833
137 459801300
138 506352422
139 557429694
140 613466372
141 674933910
142 742307134
143 816170318
144 897112189
145 985763482
146 1082859537
147 1189180315
148 1305532190
149 1432862419
150 1572162155
151 1724496991
152 1891063877
153 2073139307
154 2272097641
155 2489484331
156 2726927970
157 2986181194
158 3269222924
159 3578159639
160 3915221289
161 4282938544
162 4683985094
163 5121250697
164 5597931096
165 6117443436
166 6683464950
167 7300089515
168 7971652011
169 8702829143
170 9498811318
171 10365109890
172 11307708948
173 12333154085
174 13448449880
175 14661165794
176 15979615769
177 17412660039
178 18969873059
179 20661777961
180 22499578100
181 24495366039
182 26662411539
183 29014881360
184 31568036293
185 34338572533
186 37344335360
187 40604579340
188 44140315772
189 47973975448
190 52129808844
191 56634114193
192 61515178757
193 66803389776
194 72531798188
195 78735803248
196 85453575755
197 92726483128
198 100598874751
199 109118501933
200 118337139044
201 128310231050
202 139097506500
203 150763574904
204 163377747792
205 177014520166
206 191754510252
207 207684103340
208 224896270211
209 243491330862
210 263577060326
211 285268853216
212 308691767372
213 333979625274
214 361276241814
215 390736631390
216 422527120914
217 456826273347
218 493826534526
219 533734004761
220 576770245133
221 623173577993
222 673199621345
223 727122410763
224 785237123251
225 847859905881
226 915329915269
227 988011696956
228 1066296155978
229 1150602187923
230 1241380110619
231 1339111795138
232 1444314886529
233 1557544168243
234 1679394233836
235 1810502238721
236 1951552112304
237 2103275875118
238 2266458183296
239 2441939897074
240 2630621872603
241 2833468630539
242 3051514085149
243 3285864226905
244 3537704370306
245 3808303449758
246 4099019281778
247 4411305246518
248 4746718086717
249 5106922158217
250 5493699242608
251 5908955141825
252 6354729039619
253 6833201340317
254 7346705816746
255 7897735346230
256 8488957807505
257 9123224868721
258 9803584412238
259 10533294535804
260 11315838544184
261 12154936712545
262 13054566667268
263 14018976302077
264 15052704461546
265 16160599690040
266 17347840657689
267 18619955948918
268 19982852456418
269 21442835080388
270 23006634877135
271 24681437748224
272 26474914682898
273 28395250186840
274 30451182266564
275 32652031028690
276 35007742362081
277 37528926437661
278 40226902599404
279 43113740904662
280 46202318689775
281 49506364476941
282 53040518463599
283 56820389826440
284 60862619572820
285 65184943894231
286 69806272230800
287 74746752408737
288 80027857275790
289 85672468978695
290 91704965736007
291 98151315979817
292 105039189880463
293 112398052788183
294 120259290613484
295 128656327939461
296 137624754676536
297 147202464362634
298 157429806578321
299 168349726855937
300 180007944990722
301 192453118953289
302 205737036323006
303 219914803252812
304 235045065058573
305 251190206125043
306 268416602943581
307 286794867857735
308 306400102986812
309 327312186835503
310 349616080528342
311 373402115319055
312 398766352168411
313 425810925142587
314 454644409008235
315 485382224526872
316 518147066481988
317 553069322437364
318 590287578153670
319 629949106856257
320 672210384406384
321 717237669273345
322 765207612355091
323 816307845150761
324 870737692546505
325 928708865616778
326 990446203401091
327 1056188479300034
328 1126189256972919
329 1200717739723389
330 1280059765074710
331 1364518786515067
332 1454416910626432
333 1550096045539069
334 1651919107227472
335 1760271212156563
336 1875561064815061
337 1998222361526680
338 2128715242258338
339 2267527906612579
340 2415178290277898
341 2572215762202766
342 2739223084004307
343 2916818352239182
344 3105657043600183
345 3306434288600802
346 3519887222818377
347 3746797377006642
348 3987993377214961
349 4244353706990706
350 4516809571870163
351 4806348050712000
352 5114015412490916
353 5440920426087489
354 5788238177306217
355 6157213897846846
356 6549166954163470
357 6965495286763050
358 7407679984362759
359 7877289973226199
360 8375987258350386
361 8905532291496798
362 9467789572213236
363 10064733769191016
364 10698456094545931
365 11371170852008851
366 12085222721323010
367 12843094232716314
368 13647413503877168
369 14500962787247752
370 15406687317236126
371 16367704406976714
372 17387313529736811
373 18469006672440441
374 19616479147868568
375 20833641379341200
376 22124631118044748
377 23493826144285682
378 24945858159936437
379 26485627121880071
380 28118316234755338
381 29849408191514179
382 31684702126807234
383 33630331155806438
384 35692781530912114
385 37878912456049843
386 40195976795682477
387 42651643529416966
388 45254021002423738
389 48011681264885411
390 50933686404677433
391 54029615846706043
392 57309594952279342
393 60784325814886921
394 64465119377013015
395 68363928930111285
396 72493386237225080
397 76866839148151510
398 81498390915629515
399 86402942539989762
400 91596236770595326
401 97094904237367193
402 102916513025183116
403 109079620206177673
404 115603825900309226
405 122509831235254693
406 129819498730404847
407 137555915537914147
408 145743461317470645
409 154407878797469415
410 163576347887114406
411 173277564906464610
412 183541825197365070
413 194401109795090016
414 205889177992262521
415 218041663909873412
416 230896177817190589
417 244492414297055566
418 258872264970024905
419 274079937021273965
420 290162079348535732
421 307167914293935626
422 325149376021325645
423 344161257743663668
424 364261365482233801
425 385510679627673828
426 407973526573913084
427 431717758209841981
428 456814940330385460
429 483340552916399558
430 511374199178809749
431 540999825516491057
432 572305954737165486
433 605385929926012322
434 640338170638326631
435 677266444643311883
436 716280152082792242
437 757494623949081692
438 801031438378399014
439 847018751686546152
440 895591645922964036
441 946892497078718930
442 1001071360116612679
443 1058286373876166544
444 1118704189187221383
445 1182500417117926196
446 1249860099624619264
447 1320978207794283694
448 1396060162876740487
449 1475322384019891410
450 1558992866787909949
451 1647311789318835064
452 1740532148801013557
453 1838920433940174182
454 1942757328765919261
455 2052338452628525859
456 2167975140786388118
457 2289995262479055732
458 2418744079475553019
459 2554585153045501786
460 2697901293095461187
461 2849095555615723966
462 3008592294115036739
463 3176838261899673468
464 3354303769111810140
465 3541483902707575374
466 3738899804571207761
467 3947100013813785149
468 4166661881248685974
469 4398193051752749656
470 4642333019799188346
471 4899754769553676426
472 5171166492195085181
473 5457313389940105024
474 5758979574570713753
475 6076990058261270597
476 6412212842657645229
477 6765561118473754631
478 7137995569764158885
479 7530526794179674468
480 7944217848316791937
481 8380186916473898104
482 8839610110439772013
483 9323724416297234973
484 9833830781530707034
485 10371297356070202976
486 10937562898795948344
487 11534140350092495682
488 12162620579205110600
489 12824676324872972683
490 13522066323651038034
491 14256639644403244714
492 15030340241343064631
493 15845211727756364507
494 16703402382741765027
495 17607170413688612321
496 18558889470196837597
497 19561054429729029936
498 20616287473676892802
499 21727344457054985337
500 22897121588222732400
501 24128662446037108822
502 25425165330559788343
503 26789990976734360691
504 28226670650278498262
505 29738914633695794122
506 31330621124020286201
507 33005885575374770271
508 34769010486343170880
509 36624515666594312514
510 38577149007289897640
511 40631897771135838886
512 42794000427360685587
513 45068959072282190711
514 47462552439483984835
515 49980849545092993847
516 52630223998099704824
517 55417368996744790489
518 58349313046207790171
519 61433436448425183925
520 64677488572830455285
521 68089605965153410762
522 71678331331306671381
523 75452633429955219590
524 79421927918626912120
525 83596099212863228267
526 87985523378983724938
527 92601092132834148405
528 97454237990643150325
529 102556960616415696715
530 107921854429814032046
531 113562137543769340042
532 119491682067822707806
533 125725045866980180131
534 132277505834043531375
535 139165092741847503081
536 146404627752546878612
537 154013760674422635776
538 162011010017858837947
539 170415804965255409856
540 179248529329747230860
541 188530567591492524384
542 198284353112802930981
543 208533418647210876341
544 219302449214463315244
545 230617337489539370064
546 242505241800150000797
547 254994646854337976701
548 268115427330566427437
549 281898914471280307230
550 296377965786622078005
551 311587038054872165832
552 327562263740985873609
553 344341530997432784047
554 361964567418646371709
555 380473027727525864304
556 399910585541468631087
557 420323029456803065394
558 441758363607815771444
559 464266912919474570628
560 487901433275095802025
561 512717226826094784815
562 538772262649869400628
563 566127303047987837662
564 594846035703616164746
565 624995211978350078006
566 656644791634926013451
567 689868094279219848064
568 724741957796617383351
569 761346904161865394267
570 799767312898047278155
571 840091602558149641050
572 882412420600929125016
573 926826842037814347805
574 973436577214801139795
575 1022348189215011520667
576 1073673321241490195555
577 1127528934473076279586
578 1184037556871255494367
579 1243327543414205400921
580 1305533348255336494517
581 1370795809419195377086
582 1439262446505862034970
583 1511087772044304728612
584 1586433617109865254732
585 1665469471832472583885
586 1748372841438822082376
587 1835329618608694531724
588 1926534472770880988252
589 2022191257171769486322
590 2122513434507324371446
591 2227724521913781216348
592 2338058556180492272921
593 2453760580181587219391
594 2575087151332353195093
595 2702306873147022723047
596 2835700950934567311304
597 2975563772643986111694
598 3122203516006329528071
599 3275942783216964688592
600 3437119264234328769408
601 3606086430091065139830
602 3783214257531643996740
603 3968889986303206061090
604 4163518910571825283263
605 4367525206083132240985
606 4581352794453007684551
607 4805466246377546994043
608 5040351725476708844103
609 5286517974478638897724
610 5544497345661309064486
611 5814846877599031677706
612 6098149420033155115765
613 6395014809193952282272
614 6706081095748432861175
615 7032015827580841447789
616 7373517389894767724839
617 7731316405268361233134
618 8106177196026515124728
619 8498899311880729673351
620 8910319125679207011708
621 9341311500112725389520
622 9792791528577755758541
623 10265716353555490512720
624 10761087065576025904481
625 11279950686596761236392
626 11823402241408139431817
627 12392586920726430023328
628 12988702340135600517459
629 13613000899164362399341
630 14266792244485279552731
631 14951445842096593326932
632 15668393663186307981574
633 16419132988379463211532
634 17205229335720138662603
635 18028319517854387316529
636 18890114833579838747630
637 19792404400016926539480
638 20737058631417321059239
639 21726032870635234600353
640 22761371180152158409426
641 23845210299683147498647
642 24979783776996167208689
643 26167426279951094427312
644 27410578097462614691926
645 28711789837194424189539
646 30073727328791863173599
647 31499176741581744929016
648 32991049925378373043314
649 34552389984591561116999
650 36186377095539530063798
651 37896334576937645464831
652 39685735224869251803548
653 41558207923724555175524
654 43517544544137584903228
655 45567707140965737185674
656 47712835463996729135821
657 49957254794212065552222
658 52305484120081064769125
659 54762244668453410859237
660 57332468804339394221608
661 60021309316203742165668
662 62834149102991592779058
663 65776611279335155315221
664 68854569717393201355391
665 72074160044029632729602
666 75441791111630437453995
667 78964156963653951216805
668 82648249315831345176162
669 86501370573940622880796
670 90531147411826162493325
671 94745544933407723910817
672 99152881442188257943490
673 103761843845265022857187
674 108581503718338454058102
675 113621334058665703203251
676 118891226756050542559477
677 124401510812175829747565
678 130162971338481037884107
679 136186869366737976134329
680 142484962506324810277776
681 149069526482635786549077
682 155953377594852712116926
683 163149896131797451876483
684 170673050784399423455724
685 178537424098344123332276
686 186758239010178081277635
687 195351386510793242428028
688 204333454485097173038073
689 213721757776981525956112
690 223534369529022670275207
691 233790153852107979488868
692 244508799880139194878409
693 255710857266055296003199
694 267417773180939110950623
695 279651930878873708822448
696 292436689890594085119796
697 305796427915997656614410
698 319756584485820777778376
699 334343706463966386171600
700 349585495469130261016691
701 365510857295293606462882
702 382149953411490541559694
703 399534254629785388979432
704 417696597030743967472436
705 436671240237557094829176
706 456493928138653829443754
707 477201952159657552162138
708 498834217187411362612313
709 521431310258544303965771
710 545035572126173019535592
711 569691171820767038111748
712 595444184331491477906812
713 622342671536432784642581
714 650436766512058041598390
715 679778761364643079118631
716 710423198727719160240448
717 742426967072983414382506
718 775849399994998435499171
719 810752379632062554656211
720 847200444389393874641883
721 885260901145007803820502
722 925003942121017217186209
723 966502766607924429584377
724 1009833707744313505025075
725 1055076364558149087094380
726 1102313739480503041702125
727 1151632381559827748753207
728 1203122535608526022991642
729 1256878297519414182988854
730 1312997776008525647464339
731 1371583261045125168648744
732 1432741399236365786273600
733 1496583376455083094792490
734 1563225108003820497761936
735 1632787436616788468047764
736 1705396338623434091270520
737 1781183138603614291870704
738 1860284732873828566031584
739 1942843822168376062372901
740 2029009153886507962277497
741 2118935774287439710330403
742 2212785291042149770393259
743 2310726146559206342136775
744 2412933902514282012539048
745 2519591536042561557795111
746 2630889748063197242206445
747 2747027284219004851153426
748 2868211268947429651721443
749 2994657553209616709075773
750 3126591076421325881330785
751 3264246243164977846351253
752 3407867315274967098355986
753 3557708819907462614587509
754 3714035974244919654021040
755 3877125127500966716854473
756 4047264220912426923360295
757 4224753266448264690646662
758 4409904844983390337592323
759 4603044624708846670940389
760 4804511900598035921946181
761 5014660155767991900938260
762 5233857645603207915132289
763 5462488005561592549669593
764 5700950883604782257468275
765 5949662598226908972273195
766 6209056823113635462244107
767 6479585299489266994625859
768 6761718577246236768701546
769 7055946786013523557412881
770 7362780437352038115408137
771 7682751259305099705086965
772 8016413064601826370556247
773 8364342653845742385467072
774 8727140755067657428374114
775 9105433001098106309156388
776 9499870946254502846724879
777 9911133123889656975496845
778 10339926146434301475841184
779 10786985849609951646569329
780 11253078482548824626911975
781 11739001945649029760793724
782 12245587078046749564301588
783 12773698996652391717246165
784 13324238488801237795691278
785 13898143460626839430911243
786 14496390443342037014410100
787 15119996159724468144092656
788 15770019153171697047909969
789 16447561481773612085483075
790 17153770479977589240166189
791 17889840590495730704681101
792 18657015269200168135746745
793 19456588965889348213458088
794 20289909183895832590136768
795 21158378621612541612890137
796 22063457399167795217693999
797 23006665373575217480675667
798 23989584545808796825662586
799 25013861563418491923123702
800 26081210322415438731228887
801 27193414672288546319722547
802 28352331228203531712989983
803 29559892294559070107246129
804 30818108904228172904732477
805 32129073978017116645692116
806 33494965609018805579211119
807 34918050476706120756462111
808 36400687395841120836285199
809 37945331005432358235518626
810 39554535603169674909639531
811 41230959131013576198305630
812 42977367317800155333252469
813 44796637984935417044518724
814 46691765521534401834571979
815 48665865535562399428290559
816 50722179687779865278652820
817 52864080715596436507198071
818 55095077654175834784438969
819 57418821262399413495387905
820 59839109661641011445533758
821 62359894195560545714048679
822 64985285519434512705627913
823 67719559927911674577064614
824 70567165930381154552982817
825 73532731083474554752236895
826 76621069090646775359505694
827 79837187179105321868471512
828 83186293764743385529335875
829 86673806416187462535248532
830 90305360129449997758182710
831 94086815925095600390059238
832 98024269780347715390283376
833 102124061908973903979972249
834 106392786402270805368220810
835 110837301245031361901187464
836 115464738720851209302437380
837 120282516221656960001595633
838 125298347476976528923242086
839 130520254218989601243212239
840 135956578300000401867672851
841 141615994279661634912261041
842 147507522499880498334160164
843 153640542665994438261463164
844 160024807953582972937446739
845 166670459660938495755039524
846 173588042427970837684542313
847 180788520043167333496532940
848 188283291860984088019794763
849 196084209852862471449146948
850 204203596316026984820881425
851 212654262265043210488145274
852 221449526532051328545662544
853 230603235602632584678390484
854 240129784215212698697870388
855 250044136752929325116030081
856 260361849458068029078625185
857 271099093500207109960148573
858 282272678930378642913440324
859 293900079554834643376799058
860 305999458763192450397975024
861 318589696347006040510064329
862 331690416346262874314237199
863 345322015962600381330915033
864 359505695579489449587961751
865 374263489931207785216357419
866 389618300463909148138051655
867 405593928933682271770503697
868 422215112288274792477161094
869 439507558880779394617146750
870 457497986065386606727553868
871 476214159227248286000804258
872 495684932300347442183972823
873 515940289829243783771977044
874 537011390632755859523464217
875 558930613129672590972581826
876 581731602388822814473035836
877 605449318968224781035767481
878 630120089610347029751398310
879 655781659862961686229927058
880 682473248697772390280895608
881 710235605201526959175180875
882 739111067417105300246981742
883 769143623415020889833767118
884 800378974678643974259376515
885 832864601889504183705794180
886 866649833202345846389387294
887 901785915102766918599781275
888 938326085943716245648941754
889 976325652260751115287510167
890 1015842067969533909515927825
891 1056935016552822307490714816
892 1099666496348294382285291954
893 1144100909052476172763242605
894 1190305151560302208705279331
895 1238348711264315108829253122
896 1288303764941947024947066972
897 1340245281364010708313387167
898 1394251127762553123833799663
899 1450402180301107460335321198
900 1508782438695658334495245462
901 1569479145140142354044963822
902 1632582907695815816284259465
903 1698187828309622759532450975
904 1766391635632883102230939971
905 1837295822817678278564806205
906 1911005790474846504779095623
907 1987630994984277580738954510
908 2067285102355035052863062563
909 2150086147840005789367930370
910 2236156701517392504435778245
911 2325624040058881179116504880
912 2418620324912384466239729113
913 2515282787135621950577048131
914 2615753919125251046383185857
915 2720181673495143750569427688
916 2828719669366768801703740782
917 2941527406343956846334548583
918 3058770486454288350205315723
919 3180620844349632480436617079
920 3307256986068840595794428487
921 3438864236676557613488016218
922 3575634997103639687095247148
923 3717769010526202682115458880
924 3865473638632617517975714672
925 4018964148140446081154695041
926 4178464007938243927421063056
927 4344205197240697779614760211
928 4516428525159748809677469528
929 4695383962108610617290529830
930 4881330983470753181686854075
931 5074538925981523465115707422
932 5275287357286058409993651962
933 5483866459153853252738657309
934 5700577424847777289538543060
935 5925732871162958374999483805
936 6159657265669644515888897986
937 6402687369713348394230518615
938 6655172697745305068725696769
939 6917475993576864846468233190
940 7189973724172891022167260839
941 7473056591620993608112219516
942 7767130063936431619320106907
943 8072614925386144505363971313
944 8389947847039698316941126049
945 8719581978280312352709901268
946 9061987560035478069866966793
947 9417652560513523895755726607
948 9787083334260826484718283213
949 10170805305383389879176369030
950 10569363675806512638247677983
951 10983324159477493244115676839
952 11413273743448716010627055604
953 11859821476811560139745241597
954 12323599288486400523156521177
955 12805262834909685012788167352
956 13305492378695998676558862420
957 13824993699391468515755071514
958 14364499037474637593094658263
959 14924768072801697107885481441
960 15506588938735818241013011228
961 16110779273244192495715582228
962 16738187308291829053448952855
963 17389692998908428196700294736
964 18066209193353505020352356229
965 18768682845855120031099169320
966 19498096273450192134348339613
967 20255468458508263544057222807
968 21041856398576490152443839672
969 21858356505241717181813982705
970 22706106053765452824608104288
971 23586284685309275410126580678
972 24500115963632846253734921932
973 25448868988212884173014850735
974 26433860065800123410054567817
975 27456454442502626416417366330
976 28518068098557421341035144618
977 29620169608028281367453059433
978 30764282065746787647248784261
979 31951985083895021096879839442
980 33184916860712615907808312921
981 34464776323898478852896903151
982 35793325351367705074470460139
983 37172391072117420637760297560
984 38603868250052574259079797031
985 40089721753722355753860632099
986 41631989115021443162362060735
987 43232783180017710100645547354
988 44894294855178704761214034154
989 46618795952383576574418509626
990 48408642136226409917200653643
991 50266275977239079792203334947
992 52194230114788821488610811868
993 54195130533537375532293430247
994 56271699957484198846831984877
995 58426761365756524034865830364
996 60663241634455233669269595643
997 62984175309015264378515299623
998 65392708511694960811145707658
999 67892102988970193529792647213
1000 70485740303775208305048667031