0 1
1 0
2 0
3 1
4 1
5 0
6 1
7 1
8 3
9 2
10 1
11 3
12 5
13 6
14 4
15 5
16 12
17 11
18 14
19 13
20 17
21 29
22 28
23 30
24 40
25 46
26 68
27 67
28 75
29 99
30 116
31 149
32 158
33 175
34 237
35 266
36 327
37 354
38 402
39 528
40 591
41 683
42 782
43 886
44 1127
45 1249
46 1425
47 1654
48 1893
49 2310
50 2572
51 2902
52 3419
53 3879
54 4626
55 5158
56 5818
57 6837
58 7752
59 9027
60 10142
61 11399
62 13361
63 15074
64 17322
65 19498
66 21942
67 25498
68 28713
69 32619
70 36842
71 41383
72 47770
73 53602
74 60504
75 68362
76 76753
77 87835
78 98441
79 110510
80 124880
81 139925
82 159082
83 177911
84 199137
85 224625
86 251319
87 283891
88 317160
89 353958
90 398556
91 444958
92 500147
93 557886
94 621471
95 697858
96 777784
97 870285
98 969637
99 1078072
100 1207460
101 1343002
102 1497535
103 1665978
104 1849488
105 2065467
106 2293393
107 2549298
108 2832283
109 3139067
110 3496371
111 3875187
112 4296968
113 4766385
114 5275072
115 5859867
116 6484409
117 7174066
118 7945887
119 8780357
120 9730545
121 10750161
122 11871279
123 13127113
124 14485124
125 16015879
126 17668132
127 19476772
128 21503573
129 23693476
130 26143801
131 28798462
132 31698072
133 34940374
134 38445735
135 42340127
136 46575531
137 51190325
138 56339766
139 61906551
140 68059470
141 74766038
142 82064443
143 90181248
144 98962544
145 108622042
146 119172103
147 130636487
148 143348300
149 157104027
150 172184051
151 188668017
152 206566912
153 226344840
154 247761012
155 271165638
156 296765040
157 324534825
158 355128060
159 388264005
160 424395347
161 463907193
162 506745166
163 553793091
164 604773455
165 660247834
166 720891629
167 786593485
168 858563405
169 936556740
170 1021296934
171 1113856206
172 1214087925
173 1323602412
174 1442300977
175 1571084777
176 1711625145
177 1863725989
178 2029556561
179 2209273733
180 2404049335
181 2616356325
182 2846024979
183 3095919437
184 3366706689
185 3659877066
186 3979064390
187 4324170721
188 4699028276
189 5105094086
190 5544354056
191 6021979207
192 6538159082
193 7097950059
194 7704130686
195 8359319891
196 9070856115
197 9839436121
198 10671828149
199 11572747730
200 12545812314
201 13601220182
202 14740711600
203 15973268445
204 17306593990
205 18745666600
206 20304658590
207 21986991198
208 23804756186
209 25769902911
210 27889552521
211 30183124808
212 32656947390
213 35327226121
214 38212159322
215 41321908614
216 44683132711
217 48306606542
218 52214348716
219 56433266114
220 60978235539
221 65885521576
222 71172973817
223 76870449037
224 83017303659
225 89635219736
226 96773673770
227 104460982424
228 112738119189
229 121661565195
230 131263358036
231 141610626908
232 152747523262
233 164730235523
234 177639271221
235 191521640676
236 206468750925
237 222547617053
238 239836024832
239 258447267956
240 278450696583
241 299970380819
242 323106801061
243 347967588419
244 374711468248
245 403439920873
246 434321980400
247 467505560792
248 503140597724
249 541447523333
250 582574874663
251 626752555858
252 674196313561
253 725114820061
254 779813342574
255 838507520986
256 901511103602
257 969134647919
258 1041669799522
259 1119536752967
260 1203047829142
261 1292630801476
262 1388729523843
263 1491750979332
264 1602272569094
265 1720743155912
266 1847747565431
267 1983913975408
268 2129811497161
269 2286230244333
270 2453813034100
271 2633358841475
272 2825751744999
273 3031785899771
274 3252541400603
275 3488932417230
276 3742052574402
277 4013136884547
278 4303294050734
279 4613996295613
280 4946538544186
281 5302416570020
282 5683347995926
283 6090876739247
284 6527008295298
285 6993565649672
286 7492596782876
287 8026476924145
288 8597354608594
289 9207956053102
290 9860837523098
291 10558800276402
292 11305117332292
293 12102770283298
294 12955463470525
295 13866762127272
296 14840499039320
297 15881164412607
298 16992890010631
299 18180701115823
300 19449551658505
301 20804679203241
302 22252226323748
303 23797902036081
304 25448520641670
305 27210933587436
306 29092295827290
307 31100981042301
308 33244862751855
309 35533168526482
310 37975341743624
311 40581142122306
312 43361958396801
313 46328617651615
314 49493608672719
315 52869894818595
316 56470778132036
317 60311704611337
318 64407531130387
319 68775138620529
320 73432267550639
321 78397017787494
322 83690297383300
323 89332434994229
324 95346232547488
325 101755883258209
326 108585986789884
327 115864779470636
328 123620014668008
329 131882452668500
330 140684995285651
331 150061016369223
332 160048585229556
333 170685488596721
334 182013186838826
335 194076289462585
336 206920010642392
337 220595576234386
338 235154317639010
339 250652043479031
340 267149087453824
341 284706591183772
342 303393380566353
343 323279007022698
344 344438515850844
345 366953291430884
346 390905884812766
347 416388609281769
348 443495495509704
349 472327317076492
350 502993610417593
351 535605623358368
352 570286999534596
353 607164556758144
354 646373460216326
355 688060792687987
356 732376227779842
357 779485112336586
358 829558120282305
359 882776286350985
360 939336714762400
361 999440400482248
362 1063308165221139
363 1131169185504811
364 1203265624361891
365 1279861070564739
366 1361224983108580
367 1447651835499733
368 1539448737108180
369 1636939144719758
370 1740474915661392
371 1850416628302115
372 1967156462615750
373 2091105093770620
374 2222693982117339
375 2362391932480330
376 2510680639706734
377 2668081669449506
378 2835143135445280
379 3012439707554589
380 3200594961662889
381 3400251236156518
382 3612101274197650
383 3836875184753566
384 4075337316340886
385 4328315692063854
386 4596665436635031
387 4881305380984424
388 5183206299201508
389 5503383304673078
390 5842934183205557
391 6202995354865563
392 6584783957549875
393 6989588390582157
394 7418754893736706
395 7873736594171722
396 8356041269691508
397 8867279024897892
398 9409156888428309
399 9983457581581093
400 10592101767516209
401 11237086576724871
402 11920539213526054
403 12644717471469824
404 13411978713940511
405 14224857792243293
406 15085995802313849
407 15998199353193866
408 16964449890134900
409 17987860064405923
410 19071770645230389
411 20219668700398875
412 21435252477259146
413 22722452659424583
414 24085373365361014
415 25528411302766759
416 27056163396014505
417 28673496342676365
418 30385584373770879
419 32197831066680985
420 34116015066547454
421 36146187004279724
422 38294742992577276
423 40568483865640459
424 42974514168513027
425 45520418593642850
426 48214149353276742
427 51064101614671241
428 54079201202427335
429 57268775867212659
430 60642767912016562
431 64211613210736998
432 67986316758032561
433 71978576457679963
434 76200622186929291
435 80665469742096881
436 85386794745226683
437 90379004736922359
438 95657409428504303
439 101238021658779136
440 107137859402311746
441 113374818208455297
442 119967736428230297
443 126936623266512567
444 134302416583458332
445 142087339100915821
446 150314776140324006
447 159009328236279540
448 168197112062025872
449 177905468566110285
450 188163381456299790
451 199001368028824769
452 210451513629408438
453 222547861907587419
454 235326068410286686
455 248823888433379016
456 263081093406872813
457 278139478647471237
458 294043364422922833
459 310839188852906308
460 328576074554300266
461 347305785064371723
462 367082697724696740
463 387964438980195068
464 410011413374172154
465 433287456904268024
466 457859854852658447
467 483799267926036111
468 511180531924930665
469 540082118953137508
470 570586888239172066
471 602782190281300885
472 636759735246330237
473 672616589840316192
474 710454571909161762
475 750381107316113995
476 792509455337906524
477 836958504025351132
478 883854006029517890
479 933327908405983568
480 985519327680932839
481 1040574937256386473
482 1098648676355130613
483 1159903270275962660
484 1224509505626204915
485 1292647332811880919
486 1364506470662640892
487 1440286011065442457
488 1520196280982155703
489 1604458076391110308
490 1693303906067485119
491 1786978877841632918
492 1885740184972979992
493 1989859372422074436
494 2099621556404462368
495 2215326819767134652
496 2337291464954807347
497 2465847364250421034
498 2601344708609965373
499 2744151246957403104
500 2894653849908455957
501 3053260228682167697
502 3220398138981785900
503 3396518697972164273
504 3582095699022728796
505 3777627356697727630
506 3983638620222341508
507 4200680218985527929
508 4429332654502087996
509 4670205660397829478
510 4923940151161776984
511 5191211280185037077
512 5472727328974595415
513 5769234491439780128
514 6081516582488465427
515 6410397209948953049
516 6756743768810086963
517 7121466179293765605
518 7505522609766064043
519 7909919562337803503
520 8335714302398884791
521 8784020012694533330
522 9256004410399271789
523 9752896570558158351
524 10275987568586988724
525 10826633201639509028
526 11406260585032182173
527 12016366690957669618
528 12658526474491775499
529 13334394294974478090
530 14045706987944462132
531 14794292233971386078
532 15582067104512497314
533 16411047716439634686
534 17283351732377102249
535 18201201848601938696
536 19166936349753235959
537 20183007776734252209
538 21251994392464885240
539 22376604129565296535
540 23559678600371183469
541 24804206321452141468
542 26113321690066409203
543 27490318581492744659
544 28938656229801101457
545 30461963886873337433
546 32064057319206873180
547 33748938337623007313
548 35520810928565697933
549 37384089661894310507
550 39343405193934112342
551 41403624743548701850
552 43569852536845035731
553 45847448935294550019
554 48242042139636535414
555 50759534779110952824
556 53406129243116033736
557 56188329508277548438
558 59112963847352129801
559 62187200766736476607
560 65418557037640088737
561 68814928915099836490
562 72384596002701824811
563 76136248224627114919
564 80079007194394834109
565 84222436137720720941
566 88576578274156623372
567 93151963556605482508
568 97959640771010352539
569 103011205792888311262
570 108318814039581989439
571 113895227522054321526
572 119753825593655386589
573 125908643203091296187
574 132374407880380746915
575 139166555530365166708
576 146301288015006624758
577 153795589348036096814
578 161667271404930109565
579 169935021874570155816
580 178618424513765127682
581 187738029469238715965
582 197315376819476144419
583 207373051309574991138
584 217934744073885488059
585 229025278778823860897
586 240670697409119162761
587 252898293547709117887
588 265736678132562922917
589 279215858353482222347
590 293367271609455080801
591 308223890010428148764
592 323820266505090246693
593 340192614088605840816
594 357378906116971136066
595 375418920529832056093
596 394354367078030016494
597 414228950187346804353
598 435088464713231128258
599 456980922818384586878
600 479956611712062358787
601 504068248412756525694
602 529371064339284901310
603 555922921410977740676
604 583784471875239506739
605 613019233686654344142
606 643693778740349180329
607 675877845401322681173
608 709644479789254318702
609 745070236301066832373
610 782235276023267050538
611 821223595588980787182
612 862123175538057715525
613 905026152760575074382
614 950029071294468030674
615 997233010585696376784
616 1046743863804090414021
617 1098672531816630033453
618 1153135134388605525899
619 1210253322878337367835
620 1270154447157430219519
621 1332971894081117782672
622 1398845339406198179746
623 1467921007169259735664
624 1540352058617785321028
625 1616298808880730379309
626 1695929138815508548651
627 1779418820105324105233
628 1866951834768151842072
629 1958720857731421694047
630 2054927537458858911048
631 2155782997245399334991
632 2261508252575658363516
633 2372334605615387903793
634 2488504242867511850533
635 2610270597564268672527
636 2737898960291943339583
637 2871667012121757036340
638 3011865312878416594910
639 3158798039923815100566
640 3312783454946463269216
641 3474154648165333653879
642 3643260216529755710529
643 3820464869138618899904
644 4006150339187348302598
645 4200715983423040022423
646 4404579689941210184021
647 4618178737472949917260
648 4841970547441967455676
649 5076433808033681561647
650 5322069242000247302801
651 5579400714758946505901
652 5848976319460650825875
653 6131369312354432639112
654 6427179496852371100644
655 6737034204104555006493
656 7061589646843761870192
657 7401532285085170015035
658 7757579990910317318650
659 8130483750802765024461
660 8521028914748005924581
661 8930036851523865263816
662 9358366662862868495300
663 9806916634956440874185
664 10276626330624819423667
665 10768478176131053951892
666 11283499486865357193159
667 11822764613093151074167
668 12387396750001410039472
669 12978570506893687252605
670 13597513918141585092578
671 14245510923895796237079
672 14923904049931987211536
673 15634096665379333637697
674 16377556135961191827153
675 17155816366029744765535
676 17970480839026558172281
677 18823225956898225840554
678 19715803856882636666769
679 20650046279290716413046
680 21627867773652671438531
681 22651269427592096129257
682 23722343020200394031341
683 24843274535899788842603
684 26016348906875103622298
685 27243954047531901894743
686 28528585430885930616523
687 29872851244678209704315
688 31279476774236288447902
689 32751310214913762924485
690 34291327738373562778805
691 35902639112051234906132
692 37588494089866187929584
693 39352287876764736932064
694 41197568250765886534069
695 43128041911698883793270
696 45147581385347880864296
697 47260232932031992796937
698 49470223356989710110081
699 51781968734522217982496
700 54200082348854024338464
701 56729383179932454043220
702 59374905677238836462638
703 62141908242215648835718
704 65035883913090338144407
705 68062570278440150007085
706 71227959911157349372547
707 74538312431588549646799
708 78000165066052881526015
709 81620345730224964975197
710 85405985384365107579582
711 89364530865802324775966
712 93503759760760113477986
713 97831793536998012927948
714 102357113562328775908398
715 107088576476806051466587
716 112035429978855686795109
717 117207331139482952993163
718 122614362724351169232847
719 128267052802748513482937
720 134176393843946092677594
721 140353862138690633184993
722 146811440330938880522003
723 153561637686439358800698
724 160617514094743547818399
725 167992703755865272078060
726 175701439076349560098711
727 183758578363789348939275
728 192179630975036534663477
729 200980786691412743037833
730 210178945058202198781424
731 219791744785045230693440
732 229837597758310904595924
733 240335720215007183402785
734 251306168690900235240745
735 262769876312192416684056
736 274748688966144890264058
737 287265407039098338837564
738 300343824025561373753596
739 314008770514047412677817
740 328286159021997336257526
741 343203028488458784188006
742 358787595456439606460621
743 375069301845363600373734
744 392078868766314547971970
745 409848351843243251249996
746 428411195932698288692842
747 447802297844094682788985
748 468058065396579255392348
749 489216483250482841517512
750 511317181090172105205399
751 534401500903607149809350
752 558512573794231821108804
753 583695392918677763778654
754 609996894007180546100550
755 637466039305323239910470
756 666153900272960793129847
757 696113751596762740311547
758 727401161189361790864177
759 760074088659275271675499
760 794192988548200672908144
761 829820911946982779662702
762 867023621497986654919967
763 905869702343151443682593
764 946430682525211862104326
765 988781159829300132752536
766 1032998926597260244169293
767 1079165110330369170607959
768 1127364310340023837700912
769 1177684744934756752254211
770 1230218407118795785529458
771 1285061217835232629479420
772 1342313197783667394676983
773 1402078635575213800734191
774 1464466267628384384134685
775 1529589469117148046802055
776 1597566442036180546571039
777 1668520425060900940760213
778 1742579900289704197855630
779 1819878813064869965512437
780 1900556805953481957609226
781 1984759449435967494789558
782 2072638498116147289146790
783 2164352144683039181472583
784 2260065288453143768115559
785 2359949821847165841244868
786 2464184913223864219200044
787 2572957319535974450430728
788 2686461698034217524375385
789 2804900934239272175696295
790 2928486492422985031824681
791 3057438762192440659770019
792 3191987439866401805328429
793 3332371910729202607893659
794 3478841649472939003403115
795 3631656648661973226675633
796 3791087843212596398270082
797 3957417575396788127454472
798 4130940063236070172678332
799 4311961889275498928079380
800 4500802524014151984443811
801 4697794845499093068036866
802 4903285706065480465816010
803 5117636505822274172611542
804 5341223789054883642286757
805 5574439883230453856334544
806 5817693534666309258187514
807 6071410598983242764614278
808 6336034742721425560298277
809 6612028170822109432038594
810 6899872406219833237845737
811 7200069067068980163316769
812 7513140707585960776126261
813 7839631675768448253302357
814 8180109000456319243990407
815 8535163341836581965157609
816 8905409941209024735394284
817 9291489644566720828062244
818 9694069950380730049968361
819 10113846090842882628611093
820 10551542190053112569791701
821 11007912423947002946171672
822 11483742265847707132868042
823 11979849765506335413114223
824 12497086866537191451427271
825 13036340816830181103293977
826 13598535584321995169389095
827 14184633372060783629015622
828 14795636178452019684845637
829 15432587401843560749497788
830 16096573557120256214776521
831 16788726002730228270542022
832 17510222782870889375095080
833 18262290529455386503115999
834 19046206415650289307557094
835 19863300243960429653767323
836 20714956551709947225565501
837 21602616850102749989079741
838 22527781941211421672958931
839 23492014295359735172560362
840 24496940589737446682151616
841 25544254273757278911892906
842 26635718289440812278286423
843 27773167892144511058365702
844 28958513542525080412612837
845 30193743991271372300698223
846 31480929402965012244625402
847 32822224659963116155702122
848 34219872794206310536118024
849 35676208503615591356411340
850 37193661898524158607380935
851 38774762303411737004059340
852 40422142267876638421861789
853 42138541739311964541373940
854 43926812336688038072033297
855 45789921898349010041700961
856 47730959106054527181599923
857 49753138352443591727773807
858 51859804811459368378755401
859 54054439630316242483910288
860 56340665447395109975955831
861 58722252013216456546063364
862 61203122094963470647590109
863 63787357634150335283311305
864 66479206051197399804734416
865 69283086937147273385814061
866 72203598882628922094428046
867 75245526637532307303624701
868 78413848584748124834380490
869 81713744392264823631064500
870 85150603124617714977561456
871 88730031534757639467698870
872 92457862742230689786326512
873 96340165299131186857476641
874 100383252473471553128484552
875 104593692077024788176481990
876 108978316527875721648287462
877 113544233364918458761052229
878 118298836239164864129410554
879 123249816170901037372403946
880 128405173451716338999913531
881 133773229849092793436129835
882 139362641340650636885138374
883 145182411432471905503585454
884 151241904803354661375925779
885 157550861712305508279963782
886 164119412793079323812115154
887 170958094470497560960852403
888 178077865089908425579618579
889 185490121446967484568485320
890 193206716220305632726827111
891 201239975895929466346637218
892 209602719422899568682545531
893 218308277737100702232682424
894 227370513777416954915708450
895 236803843569515048181265955
896 246623257930678919381997097
897 256844345036225658012331564
898 267483314039854559384369412
899 278557019300145198116861781
900 290082985869116686572012805
901 302079435760949197386092163
902 314565315237705912823647084
903 327560323371481555174988629
904 341084941353102614220501233
905 355160463292431525492251140
906 369809027994106110950763230
907 385053651935833844524018609
908 400918263789278204740052770
909 417427739860429203644350735
910 434607941292778366034465057
911 452485752484790455688665953
912 471089120931889708403861892
913 490447098928986706955134315
914 510589886405283155672274837
915 531548875842333900400237358
916 553356698697965279892045447
917 576047273520412443455376206
918 599655856302575238219793891
919 624219092229838417147045200
920 649775069890135469590851502
921 676363377344768406325491406
922 704025160208004914283629033
923 732803182419417383668372288
924 762741888730256606656958298
925 793887470100375217129335879
926 826287931387128027169085837
927 859993161425168981378339549
928 895055006338473451503516514
929 931527344958657711099991310
930 969466167684618042120425868
931 1008929658156879174797880372
932 1049978277781732454556054043
933 1092674854130009475578364160
934 1137084671921718194475578310
935 1183275568080572951568066927
936 1231318030235920574812320097
937 1281285298625701065194806363
938 1333253472638771065634418364
939 1387301620528270469405182612
940 1443511893939906535526898808
941 1501969646651886552981478939
942 1562763557378608415701981625
943 1625985758123371462038700059
944 1691731966415324275538264700
945 1760101623244641273281655513
946 1831198036131301731888589763
947 1905128527054428070763014281
948 1982004587012461186792328428
949 2061942035335243032898728656
950 2145061185742404625714399878
951 2231487018645674360245145686
952 2321349359270247516297640182
953 2414783063692800132564527598
954 2511928210685763817337230657
955 2612930301551850872793944323
956 2717940467538139707449429823
957 2827115684222111615993864351
958 2940618995342383550577388691
959 3058619743714808623468078398
960 3181293811616264937682473646
961 3308823870352370475803616031
962 3441399638184219332123878523
963 3579218149514923599088153822
964 3722484032711518873501720544
965 3871409799149789311949823008
966 4026216143368277408137945050
967 4187132253249699817571102332
968 4354396133618099974855466380
969 4528254940346795872465939564
970 4708965327775747599381449413
971 4896793809545579594004026730
972 5092017131465879704278625605
973 5294922660359085344364937744
974 5505808785681894410555408918
975 5724985336936942344194573620
976 5952774017264336110052711714
977 6189508851480583620544732450
978 6435536653132464067201999495
979 6691217507064325031642404854
980 6956925270726828799031160732
981 7233048094970972129431390143
982 7519988962190792153776725726
983 7818166247088714326676582301
984 8128014296253133639930741839
985 8449984029988721581675071650
986 8784543567583114777555788191
987 9132178873408878827037624950
988 9493394429930444052865814627
989 9868713933495807136420353631
990 10258681016560257721092276595
991 10663859998065082273816158472
992 11084836658840515077944520984
993 11522219048995705650625456948
994 11976638322872732227688829681
995 12448749605407569387001278755
996 12939232892277585924892911700
997 13448793980103460292178442195
998 13978165434669324365647920508
999 14528107592450235009262344388
1000 15099409599470330068961984934