0 1
1 0
2 1
3 0
4 2
5 1
6 2
7 3
8 4
9 4
10 8
11 7
12 12
13 13
14 19
15 22
16 30
17 35
18 47
19 54
20 74
21 85
22 109
23 131
24 165
25 194
26 247
27 289
28 359
29 427
30 523
31 617
32 757
33 889
34 1078
35 1272
36 1529
37 1799
38 2154
39 2529
40 3013
41 3528
42 4187
43 4894
44 5779
45 6748
46 7937
47 9241
48 10844
49 12599
50 14724
51 17089
52 19912
53 23048
54 26801
55 30964
56 35892
57 41414
58 47886
59 55132
60 63632
61 73126
62 84195
63 96623
64 111018
65 127172
66 145861
67 166814
68 190957
69 218070
70 249193
71 284127
72 324148
73 369052
74 420343
75 477902
76 543492
77 617050
78 700691
79 794481
80 900884
81 1020119
82 1155185
83 1306426
84 1477406
85 1668830
86 1884825
87 2126452
88 2398774
89 2703151
90 3045618
91 3428283
92 3858156
93 4338071
94 4876640
95 5477410
96 6150636
97 6901286
98 7741357
99 8677259
100 9723663
101 10888496
102 12189287
103 13636521
104 15250842
105 17045491
106 19045541
107 21267341
108 23740847
109 26486921
110 29541108
111 32929345
112 36694544
113 40868609
114 45502808
115 50636973
116 56332190
117 62637436
118 69626101
119 77358216
120 85921356
121 95389352
122 105866850
123 117443827
124 130245546
125 144381771
126 160001777
127 177239263
128 196272642
129 217263739
130 240425568
131 265954521
132 294104090
133 325111738
134 359280179
135 396895323
136 438317706
137 483892561
138 534048304
139 589200059
140 649858524
141 716521257
142 789795299
143 870278534
144 958691133
145 1055748770
146 1162308025
147 1279223521
148 1407511316
149 1548193733
150 1702474288
151 1871571956
152 2056914750
153 2259953449
154 2482378542
155 2725918489
156 2992572174
157 3284393491
158 3603748372
159 3953073952
160 4335165313
161 4752915410
162 5209623394
163 5708716207
164 6254089384
165 6849797945
166 7500434630
167 8210797159
168 8986296369
169 9832599263
170 10756080085
171 11763426805
172 12862139206
173 14060106668
174 15366148087
175 16789557622
176 18340701252
177 20030520200
178 21871186328
179 23875571420
180 26057960552
181 28433479732
182 31018884570
183 33831939225
184 36892279403
185 40220751693
186 43840356323
187 47775533715
188 52053206925
189 56702013768
190 61753444243
191 67241027609
192 73201578942
193 79674321184
194 86702264263
195 94331267532
196 102611541885
197 111596663176
198 121345222685
199 131919763441
200 143388606769
201 155824726009
202 169307735396
203 183922712534
204 199762388547
205 216925883681
206 235521131734
207 255663554141
208 277478701305
209 301100878281
210 326676058885
211 354360419690
212 384323566755
213 416747016391
214 451827716474
215 489776489126
216 530821921686
217 575208724002
218 623202037511
219 675085760261
220 731167260167
221 791775685782
222 857267182568
223 928023141831
224 1004455978950
225 1087007392099
226 1176154699881
227 1272409131733
228 1376322851629
229 1488487240502
230 1609540679449
231 1740166916924
232 1881103631128
233 2033140910339
234 2197130756158
235 2373985655552
236 2564689116729
237 2770294454121
238 2991936413891
239 3230830209731
240 3488284444084
241 3765700407132
242 4064586412505
243 4386557516810
244 4733351384038
245 5106828481378
246 5508989736423
247 5941977275936
248 6408094032637
249 6909805235138
250 7449760164052
251 8030794476794
252 8655954455336
253 9328500315551
254 10051933160967
255 10829999555721
256 11666721504309
257 12566402421684
258 13533660588679
259 14573436788619
260 15691031539483
261 16892114777952
262 18182767358532
263 19569492998240
264 21059264640776
265 22659539104146
266 24378308742066
267 26224119321710
268 28206127706431
269 30334123307279
270 32618592594789
271 35070744806811
272 37702583919416
273 40526939351056
274 43557546439200
275 46809082688622
276 50297257854810
277 54038856757424
278 58051839896941
279 62355393879198
280 66970044053945
281 71917713414140
282 77221848774178
283 82907489633353
284 89001409258379
285 95532195001500
286 102530406382856
287 110028668204070
288 118061847735238
289 126667162768239
290 135884379917854
291 145755939741078
292 156327179083264
293 167646475316580
294 179765495667714
295 192739363630905
296 206626938220439
297 221491005601303
298 237398592350653
299 254421185402913
300 272635083431987
301 292121649439907
302 312967704550633
303 335265817592679
304 359114746983678
305 384619771923332
306 411893188140232
307 441054686804106
308 472231910348246
309 505560885319295
310 541186646170829
311 579263728846745
312 619956870658326
313 663441573204795
314 709904887277394
315 759546053988474
316 812577385676007
317 869224995151655
318 929729784015978
319 994348272119762
320 1063353706084787
321 1137037001612929
322 1215707987474277
323 1299696474981154
324 1389353653489502
325 1485053304026423
326 1587193364507937
327 1696197305471599
328 1812515886240273
329 1936628713290645
330 2069046209919148
331 2210311381077528
332 2361002022308433
333 2521732716496230
334 2693157311613378
335 2875971178629030
336 3070913989736590
337 3278772270823009
338 3500382516491160
339 3736634073067952
340 3988472631524611
341 4256903482441627
342 4542995431242279
343 4847884471868452
344 5172778175298852
345 5518959832675751
346 5887793374279091
347 6280728040477314
348 6699303893342320
349 7145157080783614
350 7620026012107843
351 8125757286692887
352 8664312612961667
353 9237775483524848
354 9848358924482083
355 10498413008255327
356 11190433532651848
357 11927070471479538
358 12711137693739286
359 13545622466584016
360 14433696335878726
361 15378725808613059
362 16384284533124009
363 17454165300971276
364 18592393679924590
365 19803241494991663
366 21091242082947594
367 22461205429309412
368 23918235236274296
369 25467745910978048
370 27115481658953422
371 28867535545618502
372 30730370849719860
373 32710842443495432
374 34816220671708857
375 37054215322297534
376 39433002324424198
377 41961250617304728
378 44648151992303925
379 47503451200028098
380 50537479303393698
381 53761187400249883
382 57186183892707929
383 60824772250845636
384 64689992647899527
385 68795664235359204
386 73156431649949005
387 77787812322439208
388 82706248415281464
389 87929159752411035
390 93475001808149346
391 99363324907091257
392 105614838960569487
393 112251479658063265
394 119296480720559147
395 126774447892249093
396 134711439565650925
397 143135049467693532
398 152074496613192477
399 161560717679436639
400 171626467345248693
401 182306421465680665
402 193637288971779287
403 205657927074537977
404 218409466037290597
405 231935437775715358
406 246281914953175707
407 261497654501697873
408 277634252652345762
409 294746305063666382
410 312891579583286846
411 332131194858919787
412 352529812817247288
413 374155837845537322
414 397081631195012282
415 421383733042648676
416 447143101274089089
417 474445358992684319
418 503381060396896388
419 534045966590525403
420 566541341570796252
421 600974259496670986
422 637457934137663823
423 676112061107495018
424 717063184478473947
425 760445077874352658
426 806399152364277006
427 855074880721925883
428 906630251162758931
429 961232239551904041
430 1019057314031612608
431 1080291960481286252
432 1145133243636284034
433 1213789391665736155
434 1286480419989635535
435 1363438781483406575
436 1444910059856611713
437 1531153692695043062
438 1622443742013359368
439 1719069698108584456
440 1821337335714705466
441 1929569607510100589
442 2044107595191782737
443 2165311502424243736
444 2293561711161002839
445 2429259884855732355
446 2572830141456558852
447 2724720278870737740
448 2885403077260227617
449 3055377660022720487
450 3235170939376323714
451 3425339127515932292
452 3626469340951097327
453 3839181278070823635
454 4064128999322157284
455 4302002789125907730
456 4553531130809692877
457 4819482772699514885
458 5100668918704339133
459 5397945520521765072
460 5712215706957458985
461 6044432326478907974
462 6395600640802511502
463 6766781144562261310
464 7159092551358990037
465 7573714920143591911
466 8011892964861356617
467 8474939520228889370
468 8964239209386884433
469 9481252285151434283
470 10027518693656447412
471 10604662330951401489
472 11214395544556650460
473 11858523849405502104
474 12538950913622568803
475 13257683782367737287
476 14016838398924061211
477 14818645390068349311
478 15665456178834161177
479 16559749390553912275
480 17504137619520980520
481 18501374520949722578
482 19554362300146374518
483 20666159562396238610
484 21839989600310496330
485 23079249081025538922
486 24387517215205949308
487 25768565369091736421
488 27226367207163206091
489 28765109325585937876
490 30389202469962706893
491 32103293296567105172
492 33912276777014049878
493 35821309204543718984
494 37835821908808569354
495 39961535636468203668
496 42204475711842789164
497 44570987934191455756
498 47067755333824623627
499 49701815742914103101
500 52480580311789443864
501 55411852926079749866
502 58503850664619808665
503 61765225253168829045
504 65205085663742299576
505 68833021814399471941
506 72659129529935298282
507 76694036718408532473
508 80948930935315553068
509 85435588290708691812
510 90166403883374985909
511 95154423717946708308
512 100413378302317450483
513 105957717882233518817
514 111802649524614129302
515 117964176007863089321
516 124459136746096649450
517 131305250707290568344
518 138521161568829585985
519 146126485072804025544
520 154141858842288242575
521 162588994623842668777
522 171490733236728746974
523 180871102197519849009
524 190755376321341767195
525 201170141272702988965
526 212143360389435838483
527 223704444757761555245
528 235884326886186754156
529 248715537962111248620
530 262232289064919453381
531 276470556326449943091
532 291468170440675393338
533 307264910521578134105
534 323902602741516085775
535 341425223758334470812
536 359879009396360098629
537 379312568600365393006
538 399777003163058690264
539 421326033257502786242
540 444016129313482842879
541 467906650283211156782
542 493059988876880821502
543 519541723829550400124
544 547420779824690648521
545 576769595154001847473
546 607664297787516757523
547 640184889954050704683
548 674415441958560308248
549 710444295359757041146
550 748364276291377455828
551 788272919076509021901
552 830272700980127803639
553 874471288278497012870
554 920981794557280986882
555 969923051450056915622
556 1021419892801313696678
557 1075603452502405222884
558 1132611477063039559386
559 1192588653207904773950
560 1255686951645848093643
561 1322065987347376161559
562 1391893397569863054813
563 1465345238017460761233
564 1542606398475048045540
565 1623871038360303965933
566 1709343043641344219918
567 1799236505627771616930
568 1893776223199871195482
569 1993198229054359859484
570 2097750341658901805772
571 2207692743572213128867
572 2323298587959941478288
573 2444854634050378216157
574 2572661913509995870911
575 2707036428579184795941
576 2848309884111013511851
577 2996830454460163997452
578 3152963587541217486837
579 3317092847121846194051
580 3489620795861666402133
581 3670969920292807133873
582 3861583600461197577810
583 4061927125568990603852
584 4272488758562801452641
585 4493780851167830921159
586 4726341012557821441128
587 4970733333336614219807
588 5227549668287874169526
589 5497410979762749943181
590 5780968745451127938377
591 6078906432620306746392
592 6391941042881044627903
593 6720824729800083804011
594 7066346493760762535420
595 7429333956650166777665
596 7810655221145073257205
597 8211220817460751065276
598 8631985742737919502501
599 9073951596245511889097
600 9538168816012684985366
601 10025739020412870498414
602 10537817460788821446635
603 11075615589020927372872
604 11640403746644919971872
605 12233513979837476180539
606 12856342987438039772951
607 13510355206782881079157
608 14197086045130089906736
609 14918145261953825041477
610 15675220510550420057904
611 16470081044785146597753
612 17304581600143934257818
613 18180666455523183036731
614 19100373685705742319157
615 20065839611618869133715
616 21079303459174783797120
617 22143112234515293838987
618 23259725827387836303547
619 24431722351270184433613
620 25661803732977848469574
621 26952801561243064647439
622 28307683208094397528254
623 29729558233479645510249
624 31221685088151304360504
625 32787478126302184444910
626 34430514944263571998577
627 36154544057896959193045
628 37963492936398245582755
629 39861476406395779786108
630 41852805445589897270430
631 43941996381183846689708
632 46133780514014887958695
633 48433114185131728549355
634 50845189307533699710962
635 53375444381452982445642
636 56029576017858781394152
637 58813550990352942508255
638 61733618842269575305963
639 64796325071101778541257
640 68008524919388315808138
641 71377397796316978829693
642 74910462361699043941353
643 78615592298903089088259
644 82501032811142731608163
645 86575417870251984285596
646 90847788255322217784031
647 95327610413112854676265
648 100024796180847351242931
649 104949723406340539114738
650 110113257509587057093020
651 115526774024067125060442
652 121202182165724191884482
653 127151949471481934292789
654 133389127559410871925235
655 139927379056352789526521
656 146781005749628908570865
657 153964978012936990697738
658 161494965567971729298283
659 169387369636558971334172
660 177659356550170581482637
661 186328892876720184314528
662 195414782137300422337340
663 204936703178330608357880
664 214915250278071989825931
665 225371975059048442317647
666 236329430292169442072673
667 247811215670707893090064
668 259842025647360225242329
669 272447699419746596800124
670 285655273165652404871838
671 299493034621217794496005
672 313990580112145212572526
673 329178874139681827364139
674 345090311640972016154367
675 361758783034845740131568
676 379219742182985606783603
677 397510277387674315245111
678 416669185567301928987291
679 436737049741870541503209
680 457756319981879670749033
681 479771397964839951817532
682 502828725306053301638488
683 526976875820978167781432
684 552266651900209305480332
685 578751185168615519367803
686 606486041625292159148927
687 635529331451345703921470
688 665941823699136651699949
689 697787066066831856424258
690 731131509990313617175273
691 766044641274608057642182
692 802599116516879615206733
693 840870905563065452592984
694 880939440271908869833251
695 922887769850117804892925
696 966802723055972781684239
697 1012775077558653017372156
698 1060899736776184405284858
699 1111275914504867752327942
700 1164007327690854655094739
701 1219202397684545533593014
702 1276974460358604523055485
703 1337441985460497899375341
704 1400728805613046087378913
705 1466964355366744572611049
706 1536283920752822920590147
707 1608828899776490216075397
708 1684747074337828054542319
709 1764192894058557270123678
710 1847327772543903346061544
711 1934320396599905535283327
712 2025347048980703823855732
713 2120591945231897631502534
714 2220247585253656882752388
715 2324515120199363401599393
716 2433604735386775288329444
717 2547736049891438149615548
718 2667138533557159967716040
719 2792051942151847591201611
720 2922726771466229616883549
721 3059424731147352994992302
722 3202419239132385377276960
723 3351995937543631232789792
724 3508453230984039351087911
725 3672102848169025682071197
726 3843270427913845870316856
727 4022296130493643269352104
728 4209535275482100077318313
729 4405359007174034441294853
730 4610154988791857075023124
731 4824328126676949494207530
732 5048301325767756487367901
733 5282516277669498133291264
734 5527434282727730321395598
735 5783537107523298694468751
736 6051327879320612497340436
737 6331332019008961439305733
738 6624098214198522710187512
739 6930199434143285425855647
740 7250233988293122306077262
741 7584826630290919251126728
742 7934629709369327915000599
743 8300324371118852348857113
744 8682621809746888355683812
745 9082264573968340619702478
746 9500027928826267073523042
747 9936721275766284504444316
748 10393189633456919175396135
749 10870315181878124550846539
750 11369018872380010120459229
751 11890262106449131120743256
752 12435048486111705463295604
753 13004425638944243943409700
754 13599487120867167696185594
755 14221374399944538226639247
756 14871278924632112892465987
757 15550444279970586567145153
758 16260168435454987458287278
759 17001806088373650502359566
760 17776771106660405056307402
761 18586539075374675019631934
762 19432649951191663580515656
763 20316710829365319704843996
764 21240398827912784249921618
765 22205464093859923028631411
766 23213732936693429164257894
767 24267111094267299011340298
768 25367587136738672363605385
769 26517236014222864649950613
770 27718222754207488808497424
771 28972806314894104515128465
772 30283343601010459153659884
773 31652293648779947021607241
774 33082221987135886236121633
775 34575805182428210605028697
776 36135835574299446365788045
777 37765226210584803936425332
778 39467015989550866349913111
779 41244375017984966390489913
780 43100610194139603911804728
781 45039171024755322972459264
782 47063655685912764150377656
783 49177817337707089210391765
784 51385570703302892893901482
785 53690998923195765544308395
786 56098360696111986923148895
787 58612097718273753991812778
788 61236842433406081051924526
789 63977426106187804904545994
790 66838887232544499407155751
791 69826480300540511281371878
792 72945684916372797529675753
793 76202215310364701738682631
794 79602030238657128724553248
795 83151343296729266518074552
796 86856633661738185204773322
797 90724657281144046611940156
798 94762458526007010516465348
799 98977382327865773255075491
800 103377086819093872355982779
801 107969556497204233025818232
802 112763115934630462768424794
803 117766444056142649640991586
804 122988589007190657766648704
805 128438983637156801660720292
806 134127461622718045030990579
807 140064274257271528936477880
808 146260107933684735136178837
809 152726102348455608638662940
810 159473869456771399766064966
811 166515513208855354078718336
812 173863650099496992506358403
813 181531430563644939943103169
814 189532561252558788915171119
815 197881328226089609105168351
816 206592621098395503558325655
817 215681958175569217964101722
818 225165512625519876623164120
819 235060139721727217954008813
820 245383405204489684604560603
821 256153614804678624110387343
822 267389844977162153987180079
823 279111974892577306603499590
824 291340719738439905726078446
825 304097665382231210675389836
826 317405304451582745089743308
827 331287073888476057373979417
828 345767394037041042632237307
829 360871709326489580543531463
830 376626530613586598121967555
831 393059479251184640470621611
832 410199332952426813459133295
833 428076073522531908463248989
834 446720936533383865107780340
835 466166463018656812642552462
836 486446553270762229580237027
837 507596522823630409275062190
838 529653160709159296036124125
839 552654790078123716713315885
840 576641331280444584127634370
841 601654367502930988594661889
842 627737213067021959398003981
843 654934984492542035501147199
844 683294674438229155585413150
845 712865228633577033518631537
846 743697625921634079938485933
847 775844961536504828069125364
848 809362533744782165973481621
849 844307933984588716765951494
850 880741140641799371738523167
851 918724616607841102690873428
852 958323410769802299455179256
853 999605263588812113123077927
854 1042640716929462357168992742
855 1087503228308709334135171606
856 1134269289740016908327447374
857 1183018551354638541948763083
858 1233833949989810585160607571
859 1286801842940274716169763385
860 1342012147078014279004371529
861 1399558483552284737426144819
862 1459538328291122293845984909
863 1522053168533303860224072374
864 1587208665629520558379320230
865 1655114824359956828474781902
866 1725886169025993169918422561
867 1799641926582872062294433068
868 1876506217091485108051969678
869 1956608251777307349763103341
870 2040082538996675660357747016
871 2127069098421281293010586986
872 2217713683764834452548592394
873 2312168014387400775316163828
874 2410590016126983324970551107
875 2513144071720402985211141097
876 2620001281190664244314017730
877 2731339732591483455221440599
878 2847344783515931153006227042
879 2968209353790720274589314543
880 3094134229795172900844169806
881 3225328380859653962192362497
882 3362009288217079889517414994
883 3504403286998133390255166517
884 3652745921781053189496341350
885 3807282316225257148776562923
886 3968267557339819653025018043
887 4135967094957686580987901230
888 4310657157009913323056782933
889 4492625181215661087172458025
890 4682170263828851909161047250
891 4879603626105543304445246556
892 5085249099183144187644599073
893 5299443628087597625177407058
894 5522537795613754754825213346
895 5754896366851154225816828687
896 5996898855158711456730358667
897 6248940110420951780688429817
898 6511430930452067100783536033
899 6784798696445510390169695781
900 7069488033403020421885807481
901 7365961496510886373034529119
902 7674700284470162420719209095
903 7996204980824133485579403809
904 8330996324368160167503867909
905 8679616009766501245345997650
906 9042627519545684791848799726
907 9420616988676569511630904751
908 9814194103005591892128531072
909 10223993032841603331962486398
910 10650673403056689647745925490
911 11094921301108867439480218431
912 11557450324450446229243026588
913 12039002668839215506174298102
914 12540350259129708354225667835
915 13062295924179327159303056325
916 13605674617568721055816544925
917 14171354685897819581917623141
918 14760239186488379749587723277
919 15373267256390740658852611210
920 16011415534667142746371406619
921 16675699639995994657151671090
922 17367175705721732295009761539
923 18086941974552523488535378893
924 18836140455194349190998936056
925 19615958643293607403553797498
926 20427631309153127250494639367
927 21272442354776557491333594835
928 22151726742895779650288149509
929 23066872500733023171548523347
930 24019322801356507142470506454
931 25010578125592935894404225629
932 26042198507575338477501324339
933 27115805867117284726062757522
934 28233086432228284032179501840
935 29395793255206361574717947175
936 30605748825876830029251742301
937 31864847785676760262987601698
938 33175059746427613445264474207
939 34538432217778978700870058615
940 35957093647459991217498677801
941 37433256578626234350598987904
942 38969220928755022359142808124
943 40567377394704742266800931426
944 42230210988731336728760114963
945 43960304710430210903748536612
946 45760343359762470243400510400
947 47633117496512945946448214015
948 49581527551732286330525962358
949 51608588096918288997065600578
950 53717432276911715829872913904
951 55911316412700147997776182543
952 58193624780559875781975107181
953 60567874574200701708825038327
954 63037721056832550753046461415
955 65606962910325468239170730197
956 68279547788907473700490982103
957 71059578085116554452915733864
958 73951316916016231934624798740
959 76959194337976500037028347257
960 80087813798636836285335840267
961 83341958834982429981476571464
962 86726600026803024004755628056
963 90246902215141925499250148022
964 93908231995706059343927076923
965 97716165497571569434484958808
966 101676496457909697445638337088
967 105795244603848658378207086606
968 110078664353006335664578614758
969 114533253844648990290612234660
970 119165764313881276991562304633
971 123983209821724784649819100953
972 128992877354425681532831499544
973 134202337305817851129181762173
974 139619454357086966264113418690
975 145252398768803133394415888895
976 151109658100647109305532597798
977 157200049374816334580315293482
978 163532731699695505658780772342
979 170117219370979581045839277048
980 176963395468079702004121907511
981 184081525964290695411072248180
982 191482274369888735792357339493
983 199176716928024249009383077044
984 207176358384015823188368750165
985 215493148349399260207379243391
986 224139498282881054970313908418
987 233128299111149619983481908278
988 242472939513351161213837556289
989 252187324893900878049443207165
990 262285897069216431997984189121
991 272783654694888500687673102623
992 283696174460786742317611935446
993 295039633082596156028755110674
994 306830830119334450069799487018
995 319087211647471498144546372430
996 331826894823404939683510521515
997 345068693367195638111071436043
998 358832144001682640871392128701
999 373137533882331901375494213632
1000 388005929054477914702512079698