0 1
1 0
2 0
3 1
4 0
5 0
6 1
7 0
8 1
9 1
10 0
11 1
12 2
13 1
14 1
15 2
16 2
17 5
18 3
19 2
20 6
21 4
22 12
23 7
24 6
25 17
26 9
27 26
28 19
29 14
30 41
31 21
32 51
33 47
34 37
35 86
36 52
37 99
38 103
39 91
40 171
41 115
42 196
43 212
44 206
45 328
46 246
47 384
48 418
49 437
50 616
51 503
52 749
53 793
54 889
55 1142
56 993
57 1441
58 1475
59 1725
60 2104
61 1905
62 2716
63 2705
64 3256
65 3828
66 3587
67 5020
68 4898
69 5989
70 6901
71 6618
72 9105
73 8779
74 10809
75 12289
76 12027
77 16216
78 15583
79 19181
80 21630
81 21529
82 28430
83 27375
84 33594
85 37595
86 38014
87 49150
88 47604
89 58086
90 64617
91 66234
92 83906
93 81936
94 99345
95 109791
96 114012
97 141638
98 139588
99 168116
100 184655
101 193920
102 236687
103 235435
104 281717
105 307512
106 326237
107 391825
108 393285
109 467605
110 507520
111 543094
112 643071
113 650849
114 769253
115 830447
116 895278
117 1046875
118 1067573
119 1254545
120 1348138
121 1462177
122 1691207
123 1736316
124 2029291
125 2171986
126 2367414
127 2712197
128 2801295
129 3256702
130 3474503
131 3801628
132 4319369
133 4484885
134 5187573
135 5520276
136 6057755
137 6832977
138 7128158
139 8204315
140 8713827
141 9582342
142 10740275
143 11250625
144 12887630
145 13669023
146 15053138
147 16778045
148 17639877
149 20113356
150 21313896
151 23492214
152 26055174
153 27482588
154 31197277
155 33042268
156 36434111
157 40231724
158 42558368
159 48104586
160 50939525
161 56169531
162 61781936
163 65521644
164 73758484
165 78108075
166 86103698
167 94375330
168 100314202
169 112485240
170 119144982
171 131272713
172 143431872
173 152760389
174 170662411
175 180828380
176 199094082
177 216920861
178 231430785
179 257648036
180 273113383
181 300443023
182 326513907
183 348879838
184 387122133
185 410555273
186 451201934
187 489234429
188 523425367
189 578998549
190 614356128
191 674468440
192 729819030
193 781683671
194 862160893
195 915273047
196 1003709478
197 1084073595
198 1162185510
199 1278340982
200 1357764608
201 1487228979
202 1603644230
203 1720494846
204 1887626438
205 2005851663
206 2194501319
207 2362756410
208 2536458972
209 2776222995
210 2951410823
211 3225092696
212 3467728918
213 3724410945
214 4067403104
215 4325830094
216 4721222078
217 5070336583
218 5447522240
219 5936851234
220 6316393446
221 6885353949
222 7386555398
223 7937888286
224 8634168245
225 9189181319
226 10004816647
227 10722741919
228 11524608891
229 12512853539
230 13321059988
231 14486095333
232 15512143590
233 16672870042
234 18072071149
235 19244159708
236 20902539077
237 22365615536
238 24038269310
239 26014579260
240 27707645140
241 30060475112
242 32141956018
243 34542032138
244 37326984480
245 39763160782
246 43090683153
247 46045114391
248 49474995551
249 53390501797
250 56882858581
251 61574530118
252 65758294456
253 70640869331
254 76133595879
255 81121861181
256 87717598876
257 93628383502
258 100553275666
259 108241645512
260 115341530011
261 124587963534
262 132919125758
263 142705923210
264 153444464050
265 163515352185
266 176442590307
267 188157674662
268 201942411192
269 216909420292
270 231147287658
271 249173227798
272 265608075973
273 284960986419
274 305778031398
275 325842334922
276 350914397790
277 373916492145
278 401002262456
279 429896412893
280 458083316896
281 492870321648
282 524988801594
283 562783832095
284 602807882554
285 642285726287
286 690437544779
287 735181383578
288 787768098156
289 843098481774
290 898227590328
291 964725409000
292 1026913853437
293 1099878067182
294 1176217662789
295 1252983139124
296 1344611599563
297 1430848329064
298 1531815209368
299 1636936319801
300 1743533092285
301 1869514973152
302 1988828863440
303 2128183740360
304 2272659444466
305 2420280623329
306 2593129214695
307 2757837806466
308 2949694424559
309 3147881005426
310 3351778875482
311 3588439890247
312 3815311376814
313 4078809215536
314 4350164513095
315 4631074453646
316 4954454182137
317 5266267110319
318 5627307379392
319 5998155672099
320 6384204527392
321 6825210323957
322 7252844132218
323 7746407399507
324 8252299306150
325 8781556654203
326 9381818286668
327 9967048786819
328 10640285010210
329 11329146049813
330 12053030075588
331 12868521752059
332 13667753702985
333 14584093390818
334 15520419508580
335 16508233441628
336 17614088588590
337 18703328761505
338 19947945263415
339 21218382067013
340 22563347709411
341 24060247184874
342 25541720222430
343 27228773109057
344 28949525402867
345 30776791144022
346 32799428216320
347 34810360291086
348 37092587447949
349 39419240852520
350 41896494814421
351 44624772225526
352 47349035347112
353 50430432365254
354 53570954696114
355 56922463527261
356 60596285115504
357 64279804727843
358 68432362473023
359 72664283618694
360 77189435757887
361 82128214085594
362 87099325898485
363 92685087615337
364 98378170000419
365 104475924841093
366 111104274771111
367 117800573092276
368 125300662476669
369 132946766411076
370 141147844420797
371 150029370728317
372 159033066568556
373 169085828784210
374 179338202638472
375 190347396066727
376 202229067050386
377 214313475297021
378 227764525169818
379 241489411865326
380 256241120146459
381 272111456059296
382 288302027166749
383 306269821980765
384 324614151213262
385 344345158920979
386 365510437670647
387 387164757053504
388 411126397407908
389 435606441729955
390 461951162109595
391 490135076956232
392 519047580295342
393 550950916265218
394 583568249067087
395 618683180123808
396 656157000613024
397 694695833491931
398 737105753328698
399 780498694338877
400 827224830617995
401 876977167144404
402 928262812561603
403 984551871794876
404 1042193022106359
405 1104267493230032
406 1170225437917248
407 1238363520993538
408 1312960040280438
409 1389413571255212
410 1471745069610386
411 1559061876189552
412 1649446175644950
413 1748156702034964
414 1849413044299912
415 1958439776142705
416 2073868639330815
417 2193574930409661
418 2324002837978618
419 2457913465705325
420 2602067763471779
421 2754446838932414
422 2912744135743973
423 3084832331301581
424 3261673869953345
425 3451984453868525
426 3652865466358984
427 3861878774037454
428 4088612460153973
429 4321817629313177
430 4572689340068575
431 4837151269507797
432 5112719670985276
433 5411035243811491
434 5718138818220908
435 6048360837922777
436 6396061932332537
437 6758848155296603
438 7150807327536878
439 7554668825294742
440 7988716783848245
441 8445253056135410
442 8922176476347042
443 9436481203066589
444 9966863367893209
445 10536578946031811
446 11135236418662110
447 11761321490683438
448 12435266391639369
449 13130870520399694
450 13877625473130289
451 14661637637642539
452 15482395367679451
453 16364381070130046
454 17275468353750128
455 18252949380160215
456 19278402257973315
457 20352894769726562
458 21505659721637052
459 22697423343032649
460 23975211870664707
461 25314778184717103
462 26719557786849189
463 28224329244915990
464 29781227335577999
465 31449395872313878
466 33197129673527888
467 35031296127056508
468 36993115958429327
469 39024432840494236
470 41199440086129906
471 43476926157020680
472 45868612328162797
473 48423162649028669
474 51070138669985173
475 53902382017342527
476 56866614378801436
477 59981294412396755
478 63303636176796852
479 66748598434839552
480 70432079479351721
481 74285544297593247
482 78336664913789894
483 82652413680644831
484 87130456586564736
485 91915137561023470
486 96918703695920223
487 102181273456352193
488 107780877284127469
489 113594788937989974
490 119802372789257849
491 126291754472446127
492 133119695703333776
493 140376657379589721
494 147915973728977245
495 155960035474525358
496 164366795450230258
497 173215077348162540
498 182609187128822927
499 192374489975889446
500 202786133135516795
501 213664451123272928
502 225117292502352830
503 237264219246714688
504 249898089620450937
505 263358611029277432
506 277419365944392735
507 292226135433888201
508 307915079192521905
509 324241488929720358
510 341623925260531305
511 359778046222096841
512 378898915178713112
513 399140470373389866
514 420214862384649278
515 442636781384647385
516 466050334334770714
517 490714274305235399
518 516801213880368344
519 543974108424615663
520 572864623664963621
521 603028742546923304
522 634807133625193059
523 668391528397116809
524 703389230231087159
525 740573990145979937
526 779393568245310612
527 820293530070508747
528 863484501304047198
529 908511406739935872
530 956320277640605782
531 1006226345221854395
532 1058808963041740870
533 1114296472986442670
534 1172164635117055891
535 1233568010700117392
536 1297659992111790103
537 1365189937722723127
538 1436401409887224153
539 1510694470583114065
540 1589475659838651529
541 1671701288111031505
542 1758335997798665138
543 1849634292992843120
544 1944914706137460834
545 2045887750601819509
546 2151270401077909780
547 2262299049834671558
548 2379232493640251045
549 2501303232512238666
550 2630587878591041962
551 2765513560407698675
552 2907658668331921528
553 3057276534333424617
554 3213511311115706375
555 3378879826939080791
556 3551459166153440268
557 3733256912682068956
558 3924507148564818631
559 4124266710319890693
560 4335580936402754668
561 4556105344156760244
562 4788384708820021589
563 5032614909374695961
564 5287771386925731436
565 5557533020445950410
566 5839049053351865115
567 6135534938613080594
568 6447122827233483684
569 6772719608685341247
570 7116762467218791034
571 7475794381259931399
572 7853866148341104268
573 8251012372945932672
574 8666093818352678646
575 9104453978839738944
576 9561911941810043159
577 10043556596811982025
578 10549280792137203106
579 11077934618480976854
580 11635943223661985851
581 12218263931304612544
582 12831272909151815960
583 13474664102373895107
584 14147329854094898299
585 14856984432712807974
586 15597562410739879982
587 16377032966284431203
588 17194817986061804069
589 18049928152898377932
590 18951612032702924759
591 19892594230799376930
592 20882811426465133033
593 21921320593091853946
594 23007357260109049928
595 24151993691554016511
596 25346527755364642599
597 26603321615946176797
598 27920950369747983203
599 29299020526630266401
600 30750769270763267829
601 32265817921181584472
602 33859513368254174837
603 35529802512173153884
604 37276860244142303462
605 39116490565202260791
606 41036351834905720434
607 43055457554144977420
608 45170944546239836573
609 47383819405670938924
610 49712925844155935884
611 52143632745549924932
612 54699450480434029833
613 57376481044802685293
614 60176910373232753255
615 63123177806747890172
616 66197992866043378419
617 69430372344990874095
618 72815107239804590187
619 76356017784154914639
620 80079791918604569628
621 83966063764488612113
622 88050582518272615205
623 92326490623096074243
624 96799833598558994222
625 101502314361311563673
626 106410027515197610104
627 111566941606640296234
628 116964140076858632735
629 122610656454794972504
630 128544107507342487111
631 134736535489083186149
632 141241929613311722353
633 148048817739436608656
634 155170200189255046016
635 162650661242622915215
636 170457630558798657943
637 178657297665763907123
638 187235037042457227559
639 196209065522769848794
640 205632169417357204661
641 215466562160131217785
642 225793268142110698124
643 236593792374167290011
644 247893156666870616244
645 259753795237338891881
646 272132066110886853878
647 285127009576746911092
648 298715407687206191505
649 312931098044526656525
650 327847855767163075831
651 343415521714763643216
652 359754989095249100695
653 376837304925767658845
654 394707658670040453297
655 413453148436737138227
656 433016433482431515049
657 453544883758147813753
658 475002617435780776547
659 497449363575105840648
660 520987863836463556819
661 545552957774880012828
662 571324058942957371452
663 598256956217347395571
664 626429912701522656525
665 655964030821364548345
666 686785759667648019507
667 719113252749393707060
668 752892336331461731036
669 788224798565684097649
670 825253285235206459809
671 863895408067820989947
672 904416108855316849342
673 946749358173677847184
674 991026688913970292179
675 1037416019526405660219
676 1085825877928824208460
677 1136577659800550679652
678 1189591300684448207763
679 1245035809981604323573
680 1303108751376904255211
681 1363709625247665216791
682 1427227880352267094044
683 1493566926931089646249
684 1562942840295738334406
685 1635587960024278416493
686 1711393252971083197424
687 1790830130710006930624
688 1873782656310034588468
689 1960525838778487775802
690 2051332819328538362813
691 2146087139616513756042
692 2245358843473431646683
693 2349009479494390120798
694 2457387648302536506167
695 2570814377385979297913
696 2689167734894849552161
697 2813136361086770363175
698 2942555774315401311089
699 3077866236525345394361
700 3219445001479381426066
701 3367167753949685637662
702 3521865626751431573058
703 3683344256726349827909
704 3852157803010193466694
705 4028749577177692317878
706 4212997487081121931705
707 4405903744986094016460
708 4607239955377875385833
709 4817701491037132452319
710 5037809329144670968245
711 5267450204772686760924
712 5507831590820537352640
713 5758686676897415929623
714 6020885553846907027579
715 6295040592525547579328
716 6581056567402076928098
717 6880387063194199665896
718 7192722352144223237924
719 7519148275244981468252
720 7860384862112044754571
721 8216367517440318630245
722 8588844739696474962514
723 8977459431917258710399
724 9383563364390915382779
725 9808003533457692286145
726 10250762912916802487907
727 10713943192427923133295
728 11197135753736187971786
729 11702019578314664488923
730 12229591595520905564057
731 12779904850369483733554
732 13355483792118384296817
733 13955864781229355756357
734 14583128754977032015891
735 15238449950433733833110
736 15921981067844063016080
737 16636752337001024579115
738 17382242736430082591012
739 18161026212071267996024
740 18974487007691894914417
741 19822916037089703770875
742 20709948358113108994448
743 21635005007994475907762
744 22601263730981989089053
745 23610357920725034538876
746 24662766589263423498833
747 25762847762085736634425
748 26909966664158582019202
749 28108039492380894275438
750 29358995749134247553696
751 30663566671841889358212
752 32026974136708406609167
753 33448533549085193063739
754 34933063044360846125885
755 36482844689453697025171
756 38098943924148120367510
757 39787614451875643195021
758 41548133257237263708137
759 43386418703577675143349
760 45305173438485704042902
761 47305901383897222730292
762 49396088323693908823470
763 51574991635245737696349
764 53849870179728215509122
765 56223929296023965606509
766 58699243457012075686511
767 61284769234305938278111
768 63979773223503938672605
769 66793145653086617243793
770 69728693872984075808521
771 72789229511249139883435
772 75985464452541411682548
773 79316716686505713444938
774 82793859624043464941634
775 86421422984748853828104
776 90203164973599711725718
777 94151891912055529650049
778 98267032978670389990859
779 102561869939599473780657
780 107041800992527202885365
781 111711793309028256919198
782 116587151841780624135086
783 121667499804374167826608
784 126969040732336793359313
785 132498218955526214786855
786 138261538391068267322381
787 144277284380924582354772
788 150545386955213468573869
789 157085590912636354842169
790 163905603046552821657057
791 171013872365802670691570
792 178432238831379003044168
793 186161090697166090235026
794 194224460969128280227323
795 202631582687260485697813
796 211393357386543986194545
797 220535864142850587292210
798 230060150399763771408671
799 239995437355775867950570
800 250352806327548804024792
801 261146240469439822881314
802 272406873980063481498701
803 284136677727392854302461
804 296371144761519836315192
805 309123598230187325198735
806 322411881130869104825674
807 336273155678173868783948
808 350710660810788098841921
809 365767465416324263755375
810 381459615878696044100032
811 397809775789762624221417
812 414862295470208331859206
813 432622128364143067661785
814 451141487350697508675473
815 470439731372740709304156
816 490545528450478668838079
817 511511800517205370589732
818 533345790335665381414920
819 556110739518889573096225
820 579830041463772000845999
821 604539824729400681616282
822 630303233075987522363565
823 657130534773602946994603
824 685098264158186885810302
825 714234733823132577884519
826 744585320865625707204679
827 776225359550902764125761
828 809169082079496979181246
829 843509033617407401884800
830 879279530701811352899092
831 916537391020741078772442
832 955372488377903007173750
833 995804210051648717778017
834 1037944373702977772222916
835 1081834630141361832761818
836 1127545921031469617842417
837 1175185463132241625838737
838 1224779304942920236888621
839 1276462448653521847175729
840 1330285511124475699453443
841 1386336838179573859681435
842 1444744335897408282244968
843 1505542611798962912774468
844 1568894542530092246849328
845 1634861712670708156378278
846 1703553876510057684542229
847 1775123624733710782379640
848 1849616507560486070621744
849 1927228896124288746206290
850 2008035798065792245717879
851 2092173258164100279124547
852 2179823322755593233748963
853 2271045469911881887002982
854 2366076297030747205653095
855 2465007246319893988728303
856 2568006597924255958180713
857 2675291552452797726916189
858 2786939244090556604754813
859 2903234556719221953154542
860 3024289060075255559296705
861 3150310500373345279257286
862 3281558040455597033359746
863 3418131115238808283562487
864 3560372542228054403674824
865 3708418546151395181538992
866 3862525124183031664548470
867 4023001536328795127312481
868 4189975290857979102637089
869 4363858681193668709278781
870 4544818135831115239947075
871 4733168564723840505963381
872 4929279047553588885873564
873 5133312324763945877766281
874 5345763970648360283771762
875 5566837415411077860154411
876 5796919408423292032017584
877 6036450471243473034625027
878 6285637436105785444965407
879 6545075663861198654381231
880 6815013911234101897209957
881 7095926424341739479661262
882 7388339062315690753623028
883 7692513692427526431615312
884 8009165190615630705919535
885 8338597830003574236539337
886 8681392300650943815828605
887 9038176416179745591633191
888 9409280571116373203356735
889 9795562730000325932538849
890 10197395148861742709922405
891 10615487869522642741779433
892 11050590534514533211986021
893 11503118671793839791928162
894 11974101494209987475720788
895 12463994484286398481350794
896 12973664708173231798760518
897 13504007411589143941085295
898 14055543661290115456699755
899 14629507547254355781266636
900 15226456407244919811941070
901 15847447732498033199987869
902 16493550815467918712854633
903 17165417296488582125072795
904 17864526292131735469086153
905 18591559747599414785150059
906 19347805861863521337571137
907 20134542008503458978487832
908 20952581070485019251317857
909 21803695113234720144932651
910 22688718460763964212227643
911 23609218565094245248309873
912 24566721609933454769914972
913 25562239239294117341752300
914 26597893653318386286191029
915 27674705431260823368534980
916 28794579737849731453377224
917 29959340312446136355988053
918 31170243395810564751412809
919 32429829546915578343145885
920 33739346897226632487361723
921 35101108672910320144521098
922 36517294514052239548428676
923 37989461182931404736464782
924 39520648971944487444714602
925 41112383874677669292732862
926 42767471776354240935903701
927 44488518057928580169685570
928 46277448153730860500045949
929 48137899128265548535679813
930 50071736086340184890488522
931 52082359237375276524254894
932 54172883307865163864541845
933 56345685355081893392407475
934 58605114909227160842858105
935 60953450703012943066568830
936 63394809367831399968000563
937 65932915061689971785807197
938 68570697315788641761879099
939 71313356032583301114098439
940 74163674169446730558344404
941 77126631325871966745137105
942 80206680910436766095590700
943 83407427408406773215933667
944 86735085446264088917925820
945 90193052277712307417170668
946 93787346254852641631817555
947 97523293480468265449328345
948 101405321985916758925962019
949 105440856952086202330707177
950 109634043570523303897076383
951 113992149679999419369797056
952 118521545801937561256173778
953 123227663602461666389014521
954 128119372111122743035442047
955 133201726604656096005749333
956 138483496898768969515947192
957 143972303508893430939120271
958 149674799784907964705355384
959 155601576479195196238374333
960 161758795552637686323489100
961 168157031153293900113982709
962 174805399878965767764330437
963 181712040525926053649227461
964 188889596482572521177589204
965 196345574601860405615632864
966 204092715241358561682045006
967 212141925648854316672828700
968 220503148837364408579392221
969 229191474837543220154640370
970 238216043821457331684205556
971 247592195250255557271566449
972 257332979592170782725163570
973 267450528988635229130949139
974 277962849159644194719717492
975 288881062593615349465711759
976 300223625444898360785053261
977 312006153358051940216815590
978 324243431984665858812949837
979 336956941017887053316511426
980 350160207266017143780254654
981 363875422132615627916178693
982 378121271380859679354290417
983 392915753971046630813720249
984 408284487954206063083511203
985 424243914399988569672083733
986 440820698830855363670534004
987 458037201304774911762170497
988 475915308373500335259965021
989 494485566962242157256779772
990 513767948198243271747188601
991 533794473903529575017050193
992 554591901244527450073468318
993 576186815916633361820279824
994 598615634154673728757912511
995 621902600280201290050599502
996 646086145232858754959683914
997 671198287905003621250327606
998 697271289169650557205930819
999 724348553169992074318412152
1000 752459493648995975422176410