0 1
1 0
2 0
3 1
4 1
5 4
6 3
7 8
8 6
9 13
10 11
11 20
12 17
13 31
14 34
15 47
16 56
17 78
18 103
19 125
20 167
21 203
22 281
23 315
24 433
25 487
26 673
27 745
28 989
29 1101
30 1472
31 1623
32 2116
33 2386
34 3052
35 3430
36 4347
37 4948
38 6168
39 7104
40 8673
41 10068
42 12210
43 14234
44 17047
45 20007
46 23671
47 27869
48 32739
49 38609
50 45010
51 53194
52 61586
53 72676
54 83737
55 98837
56 113412
57 133601
58 152739
59 179622
60 204947
61 240279
62 273532
63 320064
64 363929
65 424518
66 481929
67 560807
68 636535
69 738090
70 837069
71 968288
72 1097849
73 1266036
74 1434831
75 1650368
76 1870247
77 2144679
78 2429362
79 2779540
80 3148157
81 3592027
82 4066583
83 4630040
84 5239977
85 5952024
86 6732302
87 7631821
88 8628806
89 9761741
90 11029452
91 12455708
92 14064913
93 15855264
94 17889684
95 20136849
96 22703414
97 25516127
98 28744117
99 32262424
100 36313842
101 40705682
102 45775006
103 51252241
104 57582445
105 64402338
106 72286829
107 80766866
108 90570763
109 101098238
110 113258910
111 126313984
112 141371298
113 157534562
114 176143545
115 196126999
116 219082780
117 243758036
118 272027563
119 302450610
120 337209565
121 374664471
122 417332226
123 463384135
124 515679350
125 572219892
126 636227770
127 705540624
128 783764284
129 868634842
130 964105689
131 1067862654
132 1184231456
133 1310913282
134 1452567196
135 1607026033
136 1779238458
137 1967318166
138 2176447542
139 2405138175
140 2658767682
141 2936517516
142 3243781059
143 3580633263
144 3952443300
145 4360488698
146 4809913373
147 5303562017
148 5846189420
149 6442696241
150 7097208939
151 7817085301
152 8605675589
153 9473491691
154 10422695900
155 11467568948
156 12608916111
157 13865615173
158 15236679265
159 16746409294
160 18391763663
161 20203584938
162 22176289204
163 24348220926
164 26711075798
165 29312122393
166 32139740370
167 35251376208
168 38631969248
169 42350824783
170 46388946406
171 50829059182
172 55648177278
173 60944483545
174 66690671509
175 73002166807
176 79847630032
177 87362164933
178 95510303149
179 104448928228
180 114139166002
181 124762535435
182 136277185017
183 148891615795
184 162562566071
185 177528695762
186 193746500149
187 211487634567
188 230710899332
189 251724476897
190 274492006108
191 299361268947
192 326304814983
193 355714034317
194 387574721451
195 422325152238
196 459970811949
197 501001260890
198 545448232841
199 593856577159
200 646293641153
201 703364145777
202 765181512314
203 832414601183
204 905235921086
205 984384184068
206 1070105895436
207 1163214177878
208 1264048401527
209 1373502342075
210 1492028912194
211 1620608756908
212 1759833703322
213 1910778389044
214 2074202788925
215 2251282982036
216 2442981022983
217 2650584032201
218 2875295138973
219 3118522264039
220 3381755334839
221 3666535256237
222 3974690378865
223 4307908820498
224 4668416934376
225 5058066504286
226 5479550412801
227 5934904168508
228 6427363923863
229 6959173108024
230 7534199738174
231 8154923770556
232 8825944658220
233 9550013443314
234 10332574459562
235 11176692691858
236 12088783661126
237 13072276254818
238 14134702402068
239 15279917269684
240 16516729182535
241 17849492190705
242 19288474977731
243 20838620935340
244 22511860221986
245 24313831147596
246 26258357120282
247 28351900577601
248 30610431330727
249 33041386925334
250 35663173157219
251 38484388202192
252 41526190607123
253 44798551877261
254 48325746323902
255 52119380128927
256 56207237304219
257 60602858647777
258 65337992526441
259 70428475642626
260 75910513145002
261 81802655900634
262 88146129182009
263 94962699192220
264 102299228595018
265 110181268064490
266 118662023741331
267 127771517989946
268 137570064799698
269 148092938737813
270 159408447865117
271 171558039546490
272 184618978323758
273 198639942392805
274 213708252206085
275 229881060177820
276 247256954972151
277 265902968349688
278 285930346155196
279 307417657941401
280 330490322355848
281 355240323220622
282 381809007157408
283 410303952062169
284 440884355887476
285 473675872924197
286 508857755617222
287 546576608454031
288 587034188595161
289 630401285702146
290 676904968357342
291 726743970512663
292 780173770735446
293 837425281961988
294 898785974171635
295 964523795904993
296 1034962183616992
297 1110411618250467
298 1191236054089055
299 1277794797934286
300 1370497426698842
301 1469759136784184
302 1576040974442638
303 1689822131299591
304 1811621649535779
305 1941991814480836
306 2081517184030607
307 2230833484292014
308 2390599213346270
309 2561545192060864
310 2744413496381578
311 2940043270459810
312 3149271044262605
313 3373059112477764
314 3612350889522314
315 3868248664807620
316 4141816730727436
317 4434316245530391
318 4746948422078253
319 5081154612409157
320 5438291035734303
321 5820003178968648
322 6227822907777857
323 6663626863514268
324 7129145911269182
325 7626518085514904
326 8157699880205749
327 8725124850996413
328 9331005205434203
329 9978108219311323
330 10668936128554891
331 11406632903136319
332 12194029600481262
333 13034695031477212
334 13931833192629531
335 14889491847863412
336 15911297876082308
337 17001838532909037
338 18165220311614008
339 19406637972541822
340 20730741779691988
341 22143410101780682
342 23649909787225273
343 25256888188867339
344 26970311066527669
345 28797690291550968
346 30745783817339426
347 32823075153670496
348 35037219886336441
349 37397792989266157
350 39913466996605167
351 42595042620678538
352 45452344117785531
353 48497548168443409
354 51741783057493367
355 55198769672647742
356 58881112260821242
357 62804264122126666
358 66982499543010904
359 71433214938842064
360 76172573509618783
361 81220150531208606
362 86594244879165836
363 92316874462931694
364 98408751969453672
365 104894633079355974
366 111797957416517326
367 119146548645334601
368 126966925964446169
369 135290350394060538
370 144146817376946676
371 153571438473339539
372 163598131573142233
373 174266321110208592
374 185614348776580891
375 197686468777870096
376 210526010274731018
377 224182635615221396
378 238705293921905919
379 254149702416731160
380 270571140662220039
381 288032104102367246
382 306594999470892052
383 326329909177287819
384 347307260995020920
385 369605629110498999
386 393304463813291613
387 418491842145514648
388 445257359927023770
389 473699728146381850
390 503919944869253242
391 536028619150836169
392 570139559366140437
393 606376686189218789
394 644868193165105478
395 685752892099826112
396 729175124387561750
397 775290359366672662
398 824261056238819109
399 876261314790037420
400 931473915740417637
401 990093795226666348
402 1052326516044916228
403 1118390314486044207
404 1188516285956318398
405 1262948720416650501
406 1341947315521827475
407 1425785489631549897
408 1514754970955319922
409 1609161742283884745
410 1709333386048701982
411 1815612284615212578
412 1928366142946889775
413 2047978027465465379
414 2174860522665778779
415 2309442160590447098
416 2452185712068907843
417 2603570514062042298
418 2764115435543856650
419 2934356575309406718
420 3114875490950050761
421 3306271693143002856
422 3509196766120056925
423 3724321048657165858
424 3952374327961369174
425 4194106046896267247
426 4450333294395784081
427 4721893844295448696
428 5009702220015653632
429 5314694818226317462
430 5637894868083231708
431 5980348859275342817
432 6343201271906250544
433 6727621477816885904
434 7134889156891882544
435 7566310810633479495
436 8023316836964519104
437 8507366745975457005
438 9020058900638399450
439 9563023502660591711
440 10138046058858266496
441 10746947161188587826
442 11391720767669895162
443 12074399788178186600
444 12797210315343190848
445 13562421992910735760
446 14372519350524298141
447 15230035933462371073
448 16137743931018136287
449 17098471026526695400
450 18115309512234603804
451 19191414838722192741
452 20330235432566187134
453 21535291922355091042
454 22810428856872904648
455 24159573633581025947
456 25587011317400916142
457 27097122319257414499
458 28694681473420028107
459 30384573594697998104
460 32172117945015380152
461 34062760856743925479
462 36062426643014572215
463 38177186592836718046
464 40413637323450767526
465 42778545553433571578
466 45279254771116288453
467 47923305368364062314
468 50718870399513779556
469 53674350804532662964
470 56798840865475244029
471 60101698485698964315
472 63593040789222671580
473 67283289643731016874
474 71183697618493439652
475 75305869240753822872
476 79662317314405298734
477 84265960696941029327
478 89130710665039935284
479 94270946405201502423
480 99702130820849375953
481 105440265305982446562
482 111502534002955142678
483 117906739935623139235
484 124671976330895209900
485 131818046691400329245
486 139366161307056397747
487 147338344457591698201
488 155758153760491068211
489 164650078323105964279
490 174040277951749214462
491 183955976844302901152
492 194426219087843998440
493 205481263232606251250
494 217153349782667468272
495 229476102919089610065
496 242485304929373328517
497 256218312294341156678
498 270714831135779816667
499 286016355953645524855
500 302166939300138098676
501 319212662581869053177
502 337202392114141079586
503 356187292708467927323
504 376221561225472962381
505 397361994966936256441
506 419668692664768678676
507 443204691211880366047
508 468036622777805969214
509 494234434982943345569
510 521871991470723534876
511 551026892333868165585
512 581781004092217236730
513 614220398990237674857
514 648435798741434563650
515 684522653319363427511
516 722581481258703136787
517 762718110585106514395
518 805043896746220960361
519 849676150585016540873
520 896738213161851980414
521 946360098035149237242
522 998678400337708147251
523 1053837183098026150291
524 1111987696008699732819
525 1173289538156380985466
526 1237910159798361173935
527 1306026336681132985969
528 1377823426043324352257
529 1453497190564202448592
530 1533252777623038034825
531 1617306933986022043072
532 1705886675054465239800
533 1799231934618094593126
534 1897593888529015315433
535 2001238087100883651124
536 2110442395330184534176
537 2225500659001153824054
538 2346720221161336702587
539 2474426176551914041613
540 2608958421689732652764
541 2750676555889115789749
542 2899956419998293606123
543 3057195706017388070206
544 3222809937149366654357
545 3397238851956486659688
546 3580941776196710864644
547 3774404851252088063822
548 3978135746073883294187
549 4192671803685415883414
550 4418574039537019353571
551 4656436283829045287840
552 4906878410701448918710
553 5170556558179406266012
554 5448155531097211514930
555 5740400184356426733723
556 6048046940979891595787
557 6371896428488877224478
558 6712784052543538366917
559 7071593979897031853159
560 7449248707317050061940
561 7846724488520316667421
562 8265039837890550932122
563 8705272502222251155375
564 9168546838885731462962
565 9656052436773915379590
566 10169030309583619281838
567 10708793273278389823402
568 11276710896432718334354
569 11874231744670901219358
570 12502867032485337771054
571 13164214847264046934108
572 13859942449912157004967
573 14591812593492527458786
574 15361664424248890354029
575 16171442011149135696656
576 17023173803798745963668
577 17919003490578631074104
578 18861167976587999380320
579 19852030688063181499097
580 20894058040838737127810
581 21989855308914788554224
582 23142141563429436250950
583 24353788221652472495947
584 25627792446890007538496
585 26967318492748211805446
586 28375669567397348683987
587 29856332084431874478694
588 31412946009044519439859
589 33049352123425903753798
590 34769560889622277593021
591 36577802831532172062386
592 38478495967832205186326
593 40476299406870796808326
594 42576079425276085726575
595 44782966363428039886316
596 47102319449246318666666
597 49539787073332999449004
598 52101270485701950650770
599 54792987517740751090684
600 57621435309766815840911
601 60593457535228479209210
602 63716206352103992248199
603 66997213169054179201924
604 70444350051267905941944
605 74065904052690399969254
606 77870538350146698275488
607 81867370145994025643603
608 86065931850289699996567
609 90476252538385862511809
610 95108819553724556426201
611 99974663480194179853040
612 105085320593843414215519
613 110452921285581375631850
614 116090153853433088732443
615 122010356281245981072756
616 128227481930322726802422
617 134756194550213426049599
618 141611836504142760732508
619 148810526852742078640490
620 156369132827362536542664
621 164305370792585623970138
622 172637781771320935470060
623 181385835050443252688939
624 190569908655648601707067
625 200211395324296155967794
626 210332688933040887085563
627 220957292514320275399064
628 232109811750518383274079
629 243816064664069558398572
630 256103083414426694216766
631 268999225238498240835847
632 282534183915008867206210
633 296739101479895808156620
634 311646590865153880384729
635 327290847854119876524780
636 343707686550280391598949
637 360934650980669986360126
638 379011065213534832445582
639 397978143952986521335158
640 417879059295621127859443
641 438759049597777846067366
642 460665505048231798029310
643 483648074020661087446282
644 507758769834310468083810
645 533052073739232484002834
646 559585065450453269486691
647 587417521841102868804404
648 616612074056901071508445
649 647234300926590315897681
650 679352915704473455611747
651 713039853134282765334477
652 748370489118369027142696
653 785423720305630548669498
654 824282220257162061503893
655 865032510358545868994984
656 907765256332753761658552
657 952575329215894978119775
658 999562146372961878072102
659 1048829721210683547173679
660 1100487053165894737129785
661 1154648164777684545679062
662 1211432545456770068517920
663 1270965174484484201157426
664 1333377023722188694865425
665 1398805065066431632080159
666 1467392837633046532426355
667 1539290438161304155038301
668 1614655158594547419570069
669 1693651457909238090805471
670 1776451676429777614690497
671 1863235987545812125588922
672 1954193195525656005129231
673 2049520665599503650740745
674 2149425212491726631779982
675 2254123007369849141620765
676 2363840564785454771149479
677 2478814625042923239721146
678 2599293247737524043733961
679 2725535668167895193365945
680 2857813506171863036333649
681 2996410595314854920434939
682 3141624316268630509809964
683 3293765397638191754404698
684 3453159383685704294659211
685 3620146405837719843658499
686 3795082795146832566073213
687 3978340823730182570362742
688 4170310472966475653838704
689 4371399144384165794087665
690 4582033595229850200126445
691 4802659618634479720155954
692 5033744158842061109036716
693 5275774960861633624893508
694 5529262878334179507788154
695 5794741493312145592704560
696 6072769630445891823560864
697 6363930948051434899882150
698 6668836673037921690576180
699 6988125165012522599279438
700 7322464887126866931619842
701 7672553945657361488067506
702 8039123312742282441683669
703 8422936344653312128499823
704 8824792273206301477972872
705 9245525706837128938020144
706 9686010408319417695739551
707 10147158783764902221157319
708 10629925965150679526138304
709 11135309293512960036887161
710 11664352725697009053428651
711 12218146319296819310669144
712 12797830983972004655999557
713 13404597977137562804203730
714 14039694021166799207112103
715 14704420820449683945366938
716 15400140566801059004389583
717 16128275490318372246316515
718 16890313776359067180799727
719 17687809164638811004039438
720 18522387302217701063990027
721 19395745407519207178745770
722 20309659084891093488589341
723 21265982072703092471083243
724 22266653546208395136210494
725 23313697971625665854968282
726 24409232925244751386492772
727 25555469078424996546881505
728 26754718562152721988625623
729 28009395111230005315139290
730 29322023004814575961918279
731 30695237401750097142411664
732 32131793889002506228072575
733 33634569044118450717543225
734 35206570624929756102385433
735 36850938399559115919683003
736 38570955012289759661557938
737 40370047126390744368812785
738 42251797002665618430702233
739 44219944005677609565831088
740 46278396933202369882516528
741 48431235942231087075896505
742 50682725669361473693165158
743 53037317639293086107534538
744 55499664218126111324139746
745 58074621573948759698380670
746 60767264507078573163666613
747 63582890039859505440507954
748 66527033170090553344560576
749 69605471175308660616807070
750 72824240338026864965340994
751 76189641058651724387303022
752 79708255603729294386494445
753 83386954131259947399608427
754 87232913515914043918417327
755 91253624400958933806935348
756 95456911157431175545531889
757 99850940088167540696844677
758 104444240581196965561972948
759 109245714603618200951113366
760 114264659113056707045785809
761 119510776992340121749479991
762 124994200786772556074849743
763 130725505244858478881789059
764 136715732453460387880923120
765 142976406165223816106413297
766 149519558408374469321272068
767 156357745798168264251993068
768 163504077703297779017879430
769 170972234756583330592549499
770 178776498665668187729779863
771 186931773157524716111428256
772 195453615527443820436311017
773 204358260272698799335106160
774 213662652480796188772541739
775 223384474430040825296865891
776 233542180925773455036053546
777 244155029169600153637639189
778 255243116160846746536418946
779 266827412162123010210856632
780 278929800292733963638886989
781 291573113945945957049893096
782 304781178711565559455460181
783 318578854130138755417789231
784 332992078093567663185114241
785 348047913353398418498389284
786 363774594561214534525541378
787 380201579982504092927824410
788 397359601352934836828327973
789 415280721285983976798550548
790 433998386136998086036171137
791 453547489632234652751840426
792 473964428950264332746553567
793 495287175142149636222419552
794 517555332659202246152130677
795 540810217179274684283944268
796 565094918831534660389862320
797 590454388092095375194282558
798 616935502980348490939424366
799 644587163738939598401405133
800 673460364302792977082380704
801 703608296533648939239129936
802 735086426292147001430380435
803 767952608056404024268237113
804 802267165960065481256769111
805 838093019687477892447806698
806 875495770876422687530708957
807 914543841250138996415689504
808 955308564823165628577528462
809 997864339302550893468768847
810 1042288724578918007420080537
811 1088662608506446451257217345
812 1137070312209716064709590837
813 1187599771434300431960240077
814 1240342649253093073787900862
815 1295394534267529783896637843
816 1352855061355972014396356737
817 1412828128099356070357066635
818 1475422024278801269688190424
819 1540749668000028598888851747
820 1608928744718689964109979146
821 1680081964644884353900290206
822 1754337212152926195853358512
823 1831827826161863742021681304
824 1912692760872713174527536049
825 1997076890942844110176057984
826 2085131184588145159584985913
827 2177013035499805820619979464
828 2272886449452957575731157472
829 2372922405053375754934143234
830 2477299055107975010905031127
831 2586202118437903952127652143
832 2699825097391419964200463633
833 2818369703118393700378551103
834 2942046090742861986555910771
835 3071073320663757522253152640
836 3205679613054645804539407885
837 3346102847936328403158482107
838 3492590840835147999922806452
839 3645401884566869462012761142
840 3804805048064689741323460617
841 3971080763020115751420965064
842 4144521148087798634306182275
843 4325430643750269680785810614
844 4514126364321264206376526340
845 4710938784636827036865158895
846 4916212122512513493974393185
847 5130305081115913116557155133
848 5353591264788696512510318910
849 5586459981224892117919282131
850 5829316693846789301914415336
851 6082583888202036689411513321
852 6346701564386092614730304456
853 6622128172379174062049837696
854 6909341148338070263956977665
855 7208837923924319561947292115
856 7521136510648208043405122489
857 7846776588592186970704661789
858 8186320143380900618184411891
859 8540352640082180978837070818
860 8909483717802911864563560695
861 9294348454954088033727515494
862 9695608126934484642173233143
863 10113951569380093347713890621
864 10550096004900467418070148589
865 11004788511396543075981445120
866 11478806924359749865351991317
867 11972961417840214106461943771
868 12488095489411276797191108509
869 13025087661902788365178910564
870 13584852558775576769780388350
871 14168342735306855366426086839
872 14776549852816120528181206960
873 15410506648602382719640612750
874 16071288218217303706405596390
875 16760014134112540992122440430
876 17477849845974115320364085090
877 18226008958743702868071184567
878 19005754761913141564842634146
879 19818402678342247330783691869
880 20665321934371263602456440135
881 21547938191671244710058352071
882 22467735371068593983748516297
883 23426258480539278843611018622
884 24425115606761571022542105003
885 25465980953304367922982018927
886 26550597015136020471654041354
887 27680777842067781424688841334
888 28858411412757341407948823028
889 30085463139553654347444027374
890 31363978459948502161644884337
891 32696086600137545650822074988
892 34084003403402311796719633213
893 35530035370957844215857963441
894 37036582748396774326220989209
895 38606143863746581483854513240
896 40241318494888604477207298280
897 41944812526202028933293415534
898 43719441621790900566693586767
899 45568136223659071558783367169
900 47493945557650497852109855185
901 49500042997785211603874454158
902 51589730434050811202779685309
903 53766444029346901324906609534
904 56033758980673633038705987634
905 58395395697088076024495233085
906 60855224988428514956458362411
907 63417274694795764665725634121
908 66085735339746493044437799998
909 68864967244083956407285311028
910 71759506683461575189652427617
911 74774073521717827365723106503
912 77913577916071187697917665124
913 81183128507873738654481947819
914 84588039722064092976957978577
915 88133840556062377173243427308
916 91826282523900296371221011405
917 95671349087049580820777789487
918 99675264297683448488338949765
919 103844502918543249574770854083
920 108185799824127371884961435056
921 112706160860271864356065026067
922 117412873066730146920813736441
923 122313516330997728983293772171
924 127415974500765501133614367823
925 132728447890675335221981811469
926 138259465358523222799617898956
927 144017897728119171218727991208
928 150012970908914839914755459948
929 156254280302980502603700706327
930 162751805053959926391341866671
931 169515923511401661962742181660
932 176557428701636519200512549875
933 183887544928336337039731802587
934 191517944565096450794862097941
935 199460765877179328110516296784
936 207728631243304275324010193248
937 216334666290098250731540003195
938 225292519658882485690612744997
939 234616383551439541452478992497
940 244321015166486138953768948780
941 254421758763012352100546703522
942 264934568900681017998608717755
943 275876034135250157894442100262
944 287263402207392352216334907609
945 299114605493618993848640474772
946 311448288299014933710050584360
947 324283834196698173887507693058
948 337641395591771844104572131538
949 351541923092728684801990032397
950 366007197526588436992613863767
951 381059861496854666312368145827
952 396723454043395952833459905222
953 413022444553645765857963400459
954 429982270275362016643777444344
955 447629372760801131144514944925
956 465991238456126345360911398672
957 485096437872356505420155947038
958 504974669491962070091561998151
959 525656801875570237751366909961
960 547174921144271176491263998561
961 569562376247439535371733134364
962 592853830298556500249967351955
963 617085309247176654047938036931
964 642294257366749520261509673185
965 668519589592820045713144068263
966 695801751483502314647610522607
967 724182775506560308646079098083
968 753706345816955095334224540055
969 784417858797624528011010323075
970 816364493024006507957376104650
971 849595274387246407525433514626
972 884161151642914843082345497040
973 920115066471155297743886070287
974 957512035036095777878654131230
975 996409223365247067590775989728
976 1036866035377494949883332021848
977 1078944193994028984858365265672
978 1122707836126444318934536402259
979 1168223599963785494134814599731
980 1215560727448345478672325509487
981 1264791158218228940617765066603
982 1315989640137085000757322835288
983 1369233830409117295184818312498
984 1424604414770408096613681274204
985 1482185216333739397902921877696
986 1542063324093560136687796488053
987 1604329210101546461173885880909
988 1669076867984841414704569535473
989 1736403939100217544503435408518
990 1806411861816208723785058909360
991 1879206007344291096117063061586
992 1954895840590170672853374157746
993 2033595066414848932689645400867
994 2115421802918894048283468397123
995 2200498738944888374155536841144
996 2288953320721269277907972308999
997 2380917921480792310605496429803
998 2476530042457786901606531561439
999 2575932495565233764849293964450
1000 2679273619811357007944980367161