4 1
5 0
6 1
7 1
8 3
9 3
10 5
11 6
12 10
13 12
14 18
15 22
16 32
17 39
18 54
19 67
20 89
21 110
22 144
23 177
24 228
25 280
26 354
27 433
28 542
29 659
30 816
31 989
32 1214
33 1464
34 1784
35 2142
36 2593
37 3101
38 3730
39 4444
40 5318
41 6310
42 7514
43 8886
44 10534
45 12413
46 14656
47 17214
48 20249
49 23711
50 27790
51 32447
52 37908
53 44134
54 51404
55 59690
56 69322
57 80292
58 92998
59 107453
60 124141
61 143107
62 164930
63 189710
64 218144
65 250384
66 287285
67 329083
68 376798
69 430782
70 492270
71 561749
72 640722
73 729850
74 830946
75 944911
76 1073940
77 1219209
78 1383391
79 1568028
80 1776338
81 2010333
82 2273910
83 2569640
84 2902256
85 3275026
86 3693668
87 4162345
88 4687967
89 5275756
90 5934090
91 6669519
92 7492144
93 8410154
94 9435752
95 10579096
96 11854938
97 13275846
98 14859592
99 16621720
100 18583636
101 20764433
102 23189926
103 25883529
104 28876271
105 32196821
106 35882482
107 39968209
108 44498836
109 49516899
110 55076168
111 61228355
112 68037908
113 75567452
114 83894232
115 93093986
116 103259102
117 114481050
118 126870266
119 140536937
120 155612995
121 172230963
122 190548208
123 210723940
124 232945706
125 257404326
126 284323204
127 313930758
128 346492684
129 382282078
130 421614692
131 464816448
132 512262308
133 564340720
134 621496396
135 684191820
136 752953959
137 828332543
138 910951550
139 1001463675
140 1100606867
141 1209155237
142 1327980798
143 1458000393
144 1600243630
145 1755795182
146 1925869438
147 2111748384
148 2314863084
149 2536726813
150 2779024674
151 3043541160
152 3332258478
153 3647278913
154 3990932240
155 4365692376
156 4774295430
157 5219649810
158 5704965824
159 6233659637
160 6809494825
161 7436479805
162 8119023402
163 8861824714
164 9670043840
165 10549184802
166 11505282246
167 12544776940
168 13674720918
169 14902644610
170 16236782116
171 17685930731
172 19259697366
173 20968350202
174 22823089652
175 24835891013
176 27019802138
177 29388778319
178 31958008382
179 34743741657
180 37763646596
181 41036629007
182 44583226382
183 48425418949
184 52587062092
185 57093690568
186 61972994624
187 67254616629
188 72970675050
189 79155556086
190 85846489133
191 93083334273
192 100909216320
193 109370308156
194 118516529442
195 128401329271
196 139082454628
197 150621734425
198 163085927368
199 176546508192
200 191080603020
201 206770783238
202 223706095966
203 241981869056
204 261700849327
205 282973021280
206 305916864738
207 330659194953
208 357336550294
209 386095060081
210 417091979565
211 450495590433
212 486486898934
213 525259580670
214 567021857616
215 611996496935
216 660422889968
217 712557114239
218 768674236904
219 829068456724
220 894055653994
221 963973628247
222 1039184926430
223 1120077191153
224 1207066298270
225 1300596840424
226 1401145605996
227 1509222221643
228 1625373015623
229 1750181843501
230 1884274379790
231 2028319162487
232 2183032357968
233 2349179060510
234 2527578590158
235 2719106084028
236 2924698388202
237 3145355992907
238 3382149582762
239 3636222369159
240 3908797380512
241 4201180248239
242 4514767322970
243 4851048988696
244 5211618695552
245 5598176880942
246 6012541032384
247 6456650299064
248 6932576704382
249 7442530555730
250 7988872935128
251 8574122021548
252 9200967016022
253 9872275499933
254 10591108962662
255 11360731349153
256 12184626370396
257 13066507406053
258 14010336815118
259 15020337372886
260 16101013815522
261 17257166030543
262 18493913089324
263 19816708428328
264 21231366670142
265 22744081054878
266 24361453376712
267 26090513975458
268 27938755143822
269 29914154018650
270 32025209876120
271 34280970293781
272 36691072788136
273 39265774686368
274 42015999604060
275 44953371507408
276 48090266608219
277 51439852145919
278 55016144332696
279 58834052472545
280 62909443649679
281 67259192864816
282 71901255266582
283 76854723053572
284 82139906126466
285 87778396622608
286 93793158954628
287 100208602933060
288 107050684295968
289 114346987475476
290 122126837835546
291 130421395293557
292 139263779605736
293 148689176183282
294 158734975951940
295 169440894842039
296 180849129904608
297 193004494164591
298 205954590850006
299 219749965476561
300 234444300292829
301 250094585663950
302 266761337056412
303 284508788066883
304 303405132510832
305 323522741695418
306 344938434508244
307 367733721809747
308 391995107721699
309 417814364391024
310 445288868014418
311 474521907574536
312 505623059578884
313 538708534756410
314 573901595911592
315 611332947072107
316 651141199320934
317 693473307372016
318 738485088838608
319 786341713746545
320 837218283275056
321 891300378396174
322 948784704763514
323 1009879707332443
324 1074806288868088
325 1143798498137563
326 1217104330304426
327 1294986497193969
328 1377723318713460
329 1465609584609336
330 1558957547124132
331 1658097884670909
332 1763380807021326
333 1875177132549400
334 1993879518440972
335 2119903664408867
336 2253689681848150
337 2395703438304197
338 2546438080977538
339 2706415537871829
340 2876188212675320
341 3056340660222252
342 3247491471707202
343 3450295143967257
344 3665444175989766
345 3893671153736968
346 4135751081116104
347 4392503704380966
348 4664796103315086
349 4953545281793707
350 5259721047649238
351 5584348898944019
352 5928513223972014
353 6293360515928598
354 6680102927967862
355 7090021852400491
356 7524471869391680
357 7984884730801461
358 8472773745143728
359 8989738210412765
360 9537468282556766
361 10117749906290142
362 10732470219279510
363 11383623035269465
364 12073314841609324
365 12803770894721674
366 13577341874799404
367 14396510659910007
368 15263899708331655
369 16182278584718892
370 17154572147850006
371 18183868909934499
372 19273430115819768
373 20426699024940692
374 21647310976945736
375 22939103695308205
376 24306128444117388
377 25752661462640326
378 27283216329069167
379 28902556646600703
380 30615709741850420
381 32427980735720011
382 34344967717289486
383 36372577346472477
384 38517041658903786
385 40784935362471994
386 43183194444647506
387 45719135341891962
388 48400475538355752
389 51235354805500850
390 54232358000665972
391 57400538594368565
392 60749443898459490
393 64289141121063870
394 68030245277355708
395 71983948036518746
396 76162048594154746
397 80576985602462999
398 85241871311542790
399 90170526903848743
400 95377520242638581
401 100878204964244484
402 106688762206389170
403 112826243847450206
404 119308618624871084
405 126154819950188710
406 133384796868918377
407 141019566923218263
408 149081272450267928
409 157593239011735669
410 166580037577397612
411 176067549092972816
412 186083033150252740
413 196655199321985066
414 207814282980148830
415 219592124089186191
416 232022250899853758
417 245139966961367855
418 258982443490398408
419 273588815438220352
420 289000283414108640
421 305260219726380291
422 322414280826384664
423 340510524333716159
424 359599533062242674
425 379734544139495852
426 400971585781260674
427 423369619724399703
428 446990692031172426
429 471900090175192595
430 498166509282232032
431 525862225340442440
432 555063278422717702
433 585849663636260786
434 618305533022556164
435 652519406019811949
436 688584391901877540
437 726598421700059144
438 766664493224154824
439 808890926579471576
440 853391634011619560
441 900286401362732985
442 949701185198884172
443 1001768422776741953
444 1056627359151128968
445 1114424388472003494
446 1175313414030216490
447 1239456223977768117
448 1307022887554809194
449 1378192168624215887
450 1453151961635709744
451 1532099746691810107
452 1615243069146390218
453 1702800040276766030
454 1794999864787378782
455 1892083391553190701
456 1994303693708600116
457 2101926674354153346
458 2215231704357650738
459 2334512288384036326
460 2460076766024041998
461 2592249044017718059
462 2731369366861073130
463 2877795121651669704
464 3031901684907617744
465 3194083307074758645
466 3364754042930315962
467 3544348723457960266
468 3733323977906785461
469 3932159301468891238
470 4141358177826279934
471 4361449251862634856
472 4592987562362782824
473 4836555829859841000
474 5092765810062112078
475 5362259707886110302
476 5645711663178528276
477 5943829303023830184
478 6257355372412660258
479 6587069438044898596
480 6933789677780552224
481 7298374750394865051
482 7681725758939548916
483 8084788302256907215
484 8508554628788788908
485 8954065887128990650
486 9422414488357175264
487 9914746574514967912
488 10432264609220657964
489 10976230084708545816
490 11547966362311065600
491 12148861640612837268
492 12780372069385667584
493 13444025003493649472
494 14141422416044767640
495 14874244464958951767
496 15644253233474790207
497 16453296638771927884
498 17303312530562639062
499 18196332973862605470
500 19134488739220000332
501 20120013994676884032
502 21155251224264815188
503 22242656367410368878
504 23384804205681152957
505 24584393991387867326
506 25844255346218226524
507 27167354424602665766
508 28556800371853645654
509 30015852072015832024
510 31547925217466315042
511 33156599695493958261
512 34845627326038743936
513 36618939946174644734
514 38480657877808826326
515 40435098774608242681
516 42486786887081704310
517 44640462742332127508
518 46901093280041415330
519 49273882441792781764
520 51764282258114601106
521 54378004431040323932
522 57121032459593526146
523 59999634306786930409
524 63020375658792137176
525 66190133775781034132
526 69516111988576960336
527 73005854841662968350
528 76667263940420247105
529 80508614504332353825
530 84538572688040554852
531 88766213673332990549
532 93201040598257216768
533 97853004327965345196
534 102732524138102297170
535 107850509317063452368
536 113218381762898974358
537 118848099583120255206
538 124752181778517777126
539 130943734021412988800
540 137436475615181510124
541 144244767647891230636
542 151383642433052384484
543 158868834253025294459
544 166716811504700018756
545 174944810266009536702
546 183570869390003411856
547 192613867148395063339
548 202093559538962079232
549 212030620282434684361
550 222446682631477387438
551 233364383021532387873
552 244807406694976118108
553 256800535332932074242
554 269369696835713054140
555 282542017291295952423
556 296345875283042675284
557 310810958581667490215
558 325968323383682859500
559 341850456147497978030
560 358491338201266399420
561 375926513180464082143
562 394193157482060210878
563 413330153800767487902
564 433378167947976077862
565 454379729027114104116
566 476379313180840616944
567 499423430992892553467
568 523560718775925095316
569 548842033838150069794
570 575320553977269640998
571 603051881305466580161
572 632094150672435142456
573 662508142802234946724
574 694357402430859532768
575 727708361573490808638
576 762630468229775502752
577 799196320670541616971
578 837481807637402201722
579 877566254614484335014
580 919532576528626155081
581 963467437054603010664
582 1009461414908550287162
583 1057609177325087451211
584 1108009661130226761116
585 1160766261626280884642
586 1215987029732009577424
587 1273784877616859348988
588 1334277793306115170250
589 1397589064520539126946
590 1463847512263517865120
591 1533187734446280420587
592 1605750360103225321348
593 1681682314517377233676
594 1761137095850070145198
595 1844275063627002437753
596 1931263739720111646688
597 2022278122212438952985
598 2117501012834315982600
599 2217123358396227600719
600 2321344606959385998218
601 2430373079210961671867
602 2544426355841840936060
603 2663731681439149925377
604 2788526385752686333846
605 2919058322896821908434
606 3055586329413080959942
607 3198380701808627919126
608 3347723694567117121280
609 3503910039305525973066
610 3667247486150242579124
611 3838057368069545010264
612 4016675189318575645436
613 4203451238802997222346
614 4398751229606769124940
615 4602956965565280739122
616 4816467036225605603120
617 5039697541156678966151
618 5273082845055033492314
619 5517076364697492020426
620 5772151389298478369977
621 6038801935419560247229
622 6317543638109680567014
623 6608914679528171110132
624 6913476756859264286598
625 7231816090883594340920
626 7564544477155887488608
627 7912300381277386676477
628 8275750080363690988506
629 8655588852330076960158
630 9052542215258327641359
631 9467367218611950849454
632 9900853788739972022288
633 10353826130593218777406
634 10827144188283226467404
635 11321705166577954149099
636 11838445116169253727960
637 12378340584990832812587
638 12942410338642519720832
639 13531717152399566320823
640 14147369678100933409202
641 14790524388612005065007
642 15462387603412438512598
643 16164217598239335180201
644 16897326802613301656686
645 17663084088431814883458
646 18462917153755949942166
647 19298315005250193715707
648 20170830543723211404114
649 21082083256527330363044
650 22033762021611573605088
651 23027628027308610138881
652 24065517813024489304032
653 25149346435260680054672
654 26281110764540496401320
655 27462892918047209505608
656 28696863833980610859988
657 29985286992848021442691
658 31330522292165056125344
659 32735030080224232981947
660 34201375355911773930206
661 35732232140708784206141
662 37330388030401537927586
663 38998748933154019297426
664 40740344002054161479376
665 42558330769345862374088
666 44456000491090545664793
667 46436783710074503667602
668 48504256046387277729064
669 50662144224140271354444
670 52914332344485233294974
671 55264868414107436959410
672 57717971140144550888888
673 60278037001468409351518
674 62949647608133426851986
675 65737577359752458757305
676 68646801415522649352158
677 71682503987551699138382
678 74850086971197018267880
679 78155178925028960781485
680 81603644415197150893782
681 85201593737848551706158
682 88955393035525253973650
683 92871674822310794603715
684 96957348934890688991410
685 101219613925505211998246
686 105665968915293381339872
687 110304225925311394190797
688 115142522705160529964314
689 120189336077916458507644
690 125453495822841667815254
691 130944199116093043769123
692 136671025552572133919226
693 142643952770770245501264
694 148873372705549834186390
695 155370108492483779896071
696 162145432050625791338482
697 169211082369242191085518
698 176579284527458487812456
699 184262769474409571209173
700 192274794601086656195246
701 200629165133689886635664
702 209340256382091107546488
703 218423036875609576317081
704 227893092422301216430833
705 237766651126545149799574
706 248060609403922797430236
707 258792559030955713209665
708 269980815271705737847428
709 281644446121802814169594
710 293803302715142137303226
711 306478050937048442046978
712 319690204292634202431692
713 333462158077633107863034
714 347817224904186325534836
715 362779671632616559486737
716 378374757765703828972228
717 394628775360542222852364
718 411569090518835004624008
719 429224186515064261566569
720 447623708628066028821852
721 466798510740140265347813
722 486780703774255092396076
723 507603706038529533977683
724 529302295553964042511936
725 551912664440046960780230
726 575472475440026022804794
727 600020920666335210129132
728 625598782654226544989822
729 652248497810409059356883
730 680014222351478432522404
731 708941900825735101667265
732 739079337320417008550310
733 770476269455260173233390
734 803184445272202667097660
735 837257703130019376114620
736 872752054722079823664076
737 909725771334491381201213
738 948239473471827796484384
739 988356223976825820549887
740 1030141624780935423742782
741 1073663917421920577994448
742 1118994087475809688915892
743 1166205973049952423231860
744 1215376377495677603570174
745 1266585186498669636659832
746 1319915489717593698533242
747 1375453707141308419558793
748 1433289720348133744921179
749 1493517008850658577627480
750 1556232791723461858556740
751 1621538174711370578271457
752 1689538303030574428069072
753 1760342520075426108298836
754 1834064532259309594021110
755 1910822580218756583096701
756 1990739616626454768706636
757 2073943490859909558933044
758 2160567140789951225334846
759 2250748791954751536675790
760 2344632164403471534583234
761 2442366687495525497370775
762 2544107722960995127448548
763 2650016796530022825851621
764 2760261838459721952601702
765 2875017433289911616452010
766 2994465079180925542957090
767 3118793457190036331507208
768 3248198710866289000551356
769 3382884736547402549688192
770 3523063484767044490096974
771 3668955273185276210146751
772 3820789111481095167465376
773 3978803038651180746951016
774 4143244473186654626729584
775 4314370576605599698028904
776 4492448630848462009824516
777 4677756430050215261215535
778 4870582687234331126604844
779 5071227456481251032434364
780 5280002571157115973992615
781 5497232098797141727368548
782 5723252813273106794111480
783 5958414684884117070380221
784 6203081389047039814626594
785 6457630834273856788995180
786 6722455710162701688247076
787 6997964056141466801422589
788 7284579851744813400934198
789 7582743629218912420300712
790 7892913109292782993872156
791 8215563860970079412835228
792 8551189986242476995533370
793 8900304830642408798821788
794 9263441720603143053748210
795 9641154728612548304305691
796 10034019467200259870489688
797 10442633912818222256556691
798 10867619260731280687925310
799 11309620812056819080459135
800 11769308894152689524697906
801 12247379815577236798274846
802 12744556856909249848300070
803 13261591298742649634227511
804 13799263488238778529930608
805 14358383945648751244216438
806 14939794512290674167572274
807 15544369541498965195424302
808 16173017134139925168434132
809 16826680420323197237969363
810 17506338889020541316254688
811 18213009767342142387432902
812 18947749451307654326804444
813 19711654989991543573872824
814 20505865625014813165168724
815 21331564387401406348534463
816 22189979753916002382624462
817 23082387365050297485847287
818 24010111806929563447458262
819 24974528459466146452131275
820 25977065413197968931105687
821 27019205457309809858998992
822 28102488141453682010004636
823 29228511914049558223619207
824 30398936339873857101800172
825 31615484399813658924084652
826 32879944875798899837725750
827 34194174824001415877739670
828 35560102139532641707245562
829 36979728215954923220848478
830 38455130703073566482934708
831 39988466366566931896842130
832 41581974053173887710451368
833 43237977765255694149345882
834 44958889848721889236502150
835 46747214298415652341001084
836 48605550185237813079504694
837 50536595209403344444937111
838 52543149384419805873655136
839 54628118856501303360957486
840 56794519864339888864360185
841 59045482844290563803349515
842 61384256686247981969450534
843 63814213145638092663169468
844 66338851417184374022214460
845 68961802876265172142464470
846 71686835993930512922690354
847 74517861431816214272624683
848 77458937323461448904306292
849 80514274748718900717935117
850 83688243408232549001591710
851 86985377505155644182288288
852 90410381841586069309270056
853 93968138137409422973470240
854 97663711579564779092193150
855 101502357609977983658966949
856 105489528960753290633068690
857 109630882945462040559819746
858 113932289015735771939005208
859 118399836592638373442413985
860 123039843182684834157254452
861 127858862788662096338427228
862 132863694625826346026107568
863 138061392154361266427756005
864 143459272439428218759490824
865 149064925850473365429475632
866 154886226111932642988240460
867 160931340717835134521250867
868 167208741723312702736745190
869 173727216926410833046206502
870 180495881454136463871615486
871 187524189767095097543266568
872 194821948097646068179144326
873 202399327336952907191462328
874 210266876386920472550905436
875 218435535993492389185772299
876 226916653078437762168988576
877 235721995587274248130251324
878 244863767871673391026292998
879 254354626625251088036059405
880 264207697392391176422798474
881 274436591670348701975159316
882 285055424625673949815337926
883 296078833446641463340877903
884 307521996354215490523643574
885 319400652294774186214040492
886 331731121338718322690833188
887 344530325809832283733575419
888 357815812171228501735659753
889 371605773694503275320727380
890 385919073939759251500324992
891 400775271075005258833200270
892 416194643064539753705167240
893 432198213756842305421749502
894 448807779903665900399830488
895 466045939143008189355366757
896 483936118979885788781934132
897 502502606799892992240922624
898 521770580951855042190196404
899 541766142937020302697611651
900 562516350743652794281954016
901 584049253367103074763713695
902 606393926556946782321077598
903 629580509834084766574638714
904 653640244822310551889066360
905 678605514940249720933264936
906 704509886501294800673477358
907 731388151270658874498707394
908 759276370530504448732354982
909 788211920705711548968459949
910 818233540604804242053963338
911 849381380332277517141910724
912 881697051930651703146580794
913 915223681812427617630067890
914 950005965044339555254103508
915 986090221548281050474684071
916 1023524454285650146713482296
917 1062358409493979646048824667
918 1102643639047247318266339128
919 1144433565013530423718967034
920 1187783546486366589530759414
921 1232750948768613459912039781
922 1279395214990476568591305400
923 1327777940245977339569147353
924 1377962948335201388184922956
925 1430016371202453642585323892
926 1484006731163718992066126118
927 1540005026019810010884132838
928 1598084817155072927822482826
929 1658322320724715798672145859
930 1720796502037544298148692738
931 1785589173244307627997811313
932 1852785094445825686328717558
933 1922472078338725323034993546
934 1994741098520845700692706572
935 2069686401582285389991829321
936 2147405623112576999102078862
937 2227999907758661092567499715
938 2311574033473143876631958216
939 2398236540096801005675460686
940 2488099862424421926884764646
941 2581280467907878792669292295
942 2677898999155776458728645024
943 2778080421394162559466328096
944 2881954175058612034102379544
945 2989654333693478339196542126
946 3101319767340325792235012041
947 3217094311603414764825422026
948 3337126942586745976767422210
949 3461571957903432438397935834
950 3590589163965241609320283802
951 3724344069766844962669102985
952 3863008087386854586707236036
953 4006758739434882510523047128
954 4155779873681900123979369222
955 4310261885118823577736305747
956 4470401945696824803049847762
957 4636404242011041837293343011
958 4808480221198502929668781278
959 4986848845329813728498726569
960 5171736854583901911550875882
961 5363379039504446793589968266
962 5562018522647010437668925200
963 5767907049935858346126904942
964 5981305292060532965564002250
965 6202483156252895827252464584
966 6431720108797160441699020036
967 6669305508636817145087529833
968 6915538952454936424739727604
969 7170730631616491249874448678
970 7435201701374754289061534998
971 7709284662756806414570165996
972 7993323757557492568201097616
973 8287675376885023069165958112
974 8592708483716660248620965746
975 8908805049937732341713919378
976 9236360508353462046187011228
977 9575784220178901617923836170
978 9927499958529581044425830120
979 10291946408452349147504618585
980 10669577684054341081259630092
981 11060863863306018604913878681
982 11466291541113896316170938614
983 11886364401277794905005699076
984 12321603807968421515347274844
985 12772549417381600383989187206
986 13239759810247812299251414280
987 13723813145897605161353719739
988 14225307838607239178858683819
989 14744863256972305624440522124
990 15283120447082420492884330093
991 15840742880295038320906102496
992 16418417226433456430235465054
993 17016854153260695441045639220
994 17636789153109737408135348564
995 18278983397578999996812931952
996 18944224621232605965674978656
997 19633328035275302660092491082
998 20347137272204574622868297612
999 21086525362474810665104566641
1000 21852395744243212725093880384