4 1
5 1
6 2
7 3
8 5
9 4
10 7
11 9
12 11
13 15
14 18
15 23
16 34
17 46
18 54
19 79
20 93
21 130
22 158
23 214
24 253
25 331
26 394
27 510
28 596
29 767
30 900
31 1129
32 1329
33 1649
34 1951
35 2371
36 2831
37 3438
38 4095
39 4917
40 5847
41 6998
42 8361
43 9908
44 11819
45 13950
46 16662
47 19531
48 23241
49 27170
50 32289
51 37586
52 44470
53 51651
54 60958
55 70565
56 82998
57 95905
58 112489
59 129607
60 151438
61 174340
62 203173
63 233333
64 271143
65 311190
66 360400
67 413221
68 477315
69 546520
70 629823
71 720434
72 827951
73 946466
74 1085473
75 1239198
76 1418183
77 1617492
78 1847171
79 2105169
80 2399519
81 2731235
82 3107698
83 3533972
84 4013610
85 4559534
86 5170124
87 5866417
88 6642114
89 7528292
90 8510733
91 9635793
92 10879040
93 12301794
94 13870646
95 15667621
96 17643423
97 19906182
98 22390340
99 25232978
100 28351418
101 31913843
102 35818252
103 40275938
104 45158491
105 50721194
106 56814544
107 63745455
108 71338310
109 79954821
110 89397804
111 100094218
112 111821158
113 125071294
114 139607513
115 155998915
116 173991715
117 194229740
118 216461243
119 241416759
120 268846273
121 299563658
122 333349960
123 371111469
124 412668494
125 459011404
126 510045546
127 566849760
128 629434561
129 698957528
130 775587358
131 860569082
132 954274949
133 1058001831
134 1172413389
135 1298873428
136 1438385008
137 1592348417
138 1762228766
139 1949454898
140 2156046665
141 2383435926
142 2634335666
143 2910180164
144 3214519897
145 3548738864
146 3917419484
147 4321916537
148 4768010368
149 5256985959
150 5796091158
151 6386548450
152 7037307668
153 7749508723
154 8534132738
155 9392269290
156 10337242880
157 11370108812
158 12506935344
159 13748825274
160 15114995997
161 16606675702
162 18246712659
163 20036610019
164 22003389264
165 24148987629
166 26505212246
167 29074700557
168 31894656825
169 34968810645
170 38340484115
171 42014919169
172 46042413984
173 50430256634
174 55236572368
175 60471493921
176 66201962525
177 72441829322
178 79267974688
179 86699041604
180 94823027487
181 103664945960
182 113325142383
183 123836491922
184 135313463472
185 147798878088
186 161422697698
187 176240283369
188 192399055438
189 209969820451
190 229119532457
191 249937872501
192 272613621594
193 297259881883
194 324089710673
195 353244138336
196 384964071044
197 419424427566
198 456896659137
199 497596667006
200 541830647930
201 589863332488
202 642040170397
203 698683603436
204 760183537884
205 826931812717
206 899368188260
207 977965504984
208 1063221423323
209 1155704602504
210 1255977501138
211 1364721418660
212 1482573629198
213 1610347140439
214 1748765064502
215 1898793371414
216 2061254116439
217 2237292814211
218 2427844639955
219 2634262100988
220 2857613109358
221 3099490677172
222 3361114604212
223 3644355849923
224 3950611936317
225 4282074690647
226 4640347935441
227 5027991734536
228 5446850801300
229 5899910865236
230 6389295987202
231 6918478060399
232 7489910295269
233 8107622907605
234 8774450730242
235 9495062760769
236 10272741820594
237 11112887673747
238 12019305758128
239 12998228498459
240 14054073586758
241 15194025998298
242 16423216834377
243 17749913683713
244 19180084708659
245 20723232252688
246 22386298532466
247 24180189509067
248 26112987331562
249 28197195466027
250 30442223395048
251 32862387886974
252 35468647652283
253 38277382460951
254 41301352019545
255 44559275219538
256 48066011156744
257 51842936351919
258 55907346207561
259 60283630951558
260 64991917908958
261 70060019587506
262 75511344622514
263 81377584632919
264 87685954228644
265 94472547690173
266 101768981144288
267 109616340862171
268 118051334341692
269 127120712711101
270 136867061726155
271 147343554106153
272 158599560551333
273 170695542935923
274 183688686458465
275 197647719918088
276 212638828759574
277 228740123490028
278 246028138016153
279 264591627329429
280 284519014905999
281 305911139483496
282 328870070861005
283 353510359418444
284 379949722651041
285 408318283222755
286 438751678600225
287 471397711313672
288 506412531486616
289 543964016301814
290 584231770538966
291 627406474978663
292 673694522514460
293 723312498750693
294 776497378957622
295 833495172449002
296 894577730439850
297 960024495121746
298 1030147061303940
299 1105262860449383
300 1185728742255461
301 1271905296412457
302 1364200872307861
303 1463025111284350
304 1568844905208493
305 1682125629358634
306 1803400711387551
307 1933198857409329
308 2072129034352984
309 2220791907395086
310 2379882173645067
311 2550082265067705
312 2732184096882429
313 2926962979776139
314 3135321036676441
315 3358139104754226
316 3596444124791310
317 3851236777898681
318 4123685357097384
319 4414926653248423
320 4726288890935138
321 5059063388785172
322 5414759299189755
323 5794843387132841
324 6201029321471617
325 6634982962921109
326 7098649141447954
327 7593919660413457
328 8123000426308859
329 8688039520442875
330 9291537694879060
331 9935933713805134
332 10624061068238047
333 11358688053466974
334 12143023660059484
335 12980209728795196
336 13873878713954485
337 14827595676985982
338 15845470619909555
339 16931548035625269
340 18090476152603234
341 19326842290070613
342 20645901251373176
343 22052854896020508
344 23553641256996274
345 25154157492506739
346 26861111236772531
347 28681186221498756
348 30621956456668061
349 32690995039263823
350 34896851328339834
351 37248103756952024
352 39754399227671639
353 42425452017151140
354 45272143986775149
355 48305472490203159
356 51537708379440872
357 54981297524871703
358 58650073076861470
359 62558115870472443
360 66721015434533531
361 71154697121725079
362 75876725055341759
363 80905104871644112
364 86259619856664182
365 91960620707009416
366 98030384508985167
367 104491904910204427
368 111370260506321338
369 118691421968208901
370 126483615085627012
371 134776163064521022
372 143600825829680058
373 152990700331053440
374 162981515048966049
375 173610613393335515
376 184918179013270891
377 196946331642697171
378 209740255754485082
379 223347442094127223
380 237818686939277242
381 253207517748020629
382 269571027980489199
383 286969528324316424
384 305467176135305388
385 325131901148146472
386 346035784151495691
387 368255309940825617
388 391871444737291722
389 416970275739187112
390 443642731907549903
391 471985675651769230
392 502101203955992812
393 534098265329996149
394 568091474693028171
395 604203333567642556
396 642562483851314618
397 683306619722221425
398 726580099214115824
399 772537641949506300
400 821341210775186315
401 873164598255878007
402 928189484187287713
403 986611022439998549
404 1048632970400687664
405 1114474397453948294
406 1184363778421189504
407 1258546951135090855
408 1337280056100353158
409 1420838883746552597
410 1509510535410643635
411 1603604307541296747
412 1703441942413488222
413 1809370206505946583
414 1921749592893304105
415 2040968760916350873
416 2167431542426869747
417 2301573420074193520
418 2443846687177238624
419 2594739147934811322
420 2754757272170615425
421 2924447313794754017
422 3104376296866957658
423 3295155754180858957
424 3497420377926828897
425 3711854588096040370
426 3939168678484026391
427 4180128432627626121
428 4435528591055709788
429 4706225739045727700
430 4993108924991551745
431 5297136045955414718
432 5619301446417679700
433 5960676034888980454
434 6322371696038642821
435 6705585371154948616
436 7111560124516138423
437 7541633419613648345
438 7997194689788051281
439 8479738041984158277
440 8990816191373719758
441 9532097818850687778
442 10105317749140790351
443 10712339178552261710
444 11355099994562479805
445 12035680081780170081
446 12756243704796086252
447 13519112085097984885
448 14326701800807339421
449 15181602806855584696
450 16086512839473836227
451 17044321032063701968
452 18058038353418727688
453 19130886941027695309
454 20266226652123105586
455 21467650203599736325
456 22738905971144203697
457 24083998984925815973
458 25507110173981993220
459 27012703223856695696
460 28605440539932312237
461 30290295915513882585
462 32072467568376296199
463 33957496513057533963
464 35951177121204941895
465 38059681017516198364
466 40289465716677363858
467 42647403791412147192
468 45140690260622382998
469 47776976684298576156
470 50564278103512354884
471 53511111629060174400
472 56626403884350515546
473 59919633538738919547
474 63400740359366705605
475 67080271030902160317
476 70969291107697928276
477 75079533321190270352
478 79423313907416669081
479 84013682476580402936
480 88864344413872036932
481 93989811213256149109
482 99405330874029573977
483 105127037450630893449
484 111171891628524111574
485 117557828044606420759
486 124303708490139672283
487 131429465376283317439
488 138956070326049631046
489 146905671931945564819
490 155301582798875550246
491 164168409543336070939
492 173532061717381312125
493 183419871727728001441
494 193860629428920020158
495 204884689420063146748
496 216524035507294437248
497 228812372544708989131
498 241785225375512951194
499 255480012127155193823
500 269936182728114483126
501 285195270242672022868
502 301301074509760110766
503 318299687842972133855
504 336239729889357893273
505 355172343650646618606
506 375151488183261631168
507 396233900622018271351
508 418479453943033900208
509 441951080298018001860
510 466715201642649663640
511 492841609387395185362
512 520403976385250467013
513 549479687514945199988
514 580150442139786402776
515 612502029963522375916
516 646625033832889362189
517 682614544788021431442
518 720570975779378696786
519 760599709578656871871
520 802812034783501464286
521 847324719873376061368
522 894261083627222465215
523 943750488362032408224
524 995929557786797968500
525 1050941582107305862335
526 1108937897110870478005
527 1170077193667826192087
528 1234527072794700932709
529 1302463251759612086945
530 1374071310711157627425
531 1449545787530407337007
532 1529092132590586651799
533 1612925684293082251592
534 1701273849389693870637
535 1794374951178317443849
536 1892480653864193724033
537 1995854675316067466014
538 2104775474791253674977
539 2219534822400300613301
540 2340440770589282477612
541 2467816072535167808039
542 2602001458651234342861
543 2743353896615753947034
544 2892250195209216977754
545 3049085099025921118601
546 3214275242792652810075
547 3388257074569101187049
548 3571491184747655311034
549 3764460052208288013200
550 3967672772958222916038
551 4181662624873273618140
552 4406992221935777659109
553 4644250894236606402662
554 4894060294460331804834
555 5157071591465517428230
556 5433971556569214613903
557 5725479570584713127870
558 6032354218023827915891
559 6355390109701110738164
560 6695425013758054438712
561 7053336498132629548880
562 7430049627711034754556
563 7826533433909082528965
564 8243809207887921819652
565 8682946807459401138085
566 9145073576479492401936
567 9631370503116180791379
568 10143081795974256282783
569 10681510911640653682783
570 11248030818022490779324
571 11844079913985430122421
572 12471173010544143652632
573 13130897170401339950495
574 13824923437298692454846
575 14555002629368842468331
576 15322977846814706427318
577 16130780259372304422599
578 16980442421741437777065
579 17874094103034876977637
580 18813976438982645877873
581 19802437859113823939157
582 20841949103635106090365
583 21935099313498383027056
584 23084611938957311977957
585 24293341067402266628884
586 25564288249179795073391
587 26900599149364095050276
588 28305581315134385803992
589 29782701249678995012041
590 31335603143410937318587
591 32968106481835677791056
592 34684225761337822424103
593 36488168757195448615774
594 38384357242233344248589
595 40377426057694366735200
596 42472244850881207173019
597 44673918108836602962876
598 46987807928494224430927
599 49419535192483372574087
600 51975003382777563900914
601 54660401098781357926533
602 57482226922215899554715
603 60447293500556544266108
604 63562753468394810581294
605 66836105343575596183345
606 70275220506832142815192
607 73888351185261427456428
608 77684158488980608737353
609 81671722785188111587989
610 85860572787511703745172
611 90260698655295549381158
612 94882582128362295954663
613 99737212720106837747193
614 104836118887026805248062
615 110191387720768814090736
616 115815697139685996729481
617 121722339523879433493701
618 127925254913314096723795
619 134439059072766405519587
620 141279077679097652305615
621 148461379348147148939345
622 156002810792713562878411
623 163921035392100386080505
624 172234569301781906117455
625 180962826199059855617964
626 190126154325318710549639
627 199745888097168481687749
628 209844386064419817569542
629 220445090135759129927934
630 231572564438133412739214
631 243252562970790474005399
632 255512069356028375798346
633 268379373803821766738882
634 281884113750963613663539
635 296057361091236131131416
636 310931663708483302322788
637 326541144006236397946207
638 342921541351244901329389
639 360110323019192393421379
640 378146727580372861559163
641 397071889466643004042660
642 416928883348668799679682
643 437762863624091512454396
644 459621109857150430006992
645 482553182588483504687508
646 506610969935608526143280
647 531848861230469390771871
648 558323794910471755855168
649 586095451604751937529328
650 615226303483003672107352
651 645781828530716099415064
652 677830561568105579810281
653 711444331582521632591071
654 746698314681810259851771
655 783671296487785274848237
656 822445727347662901700889
657 863108011936740502896345
658 905748567123239734583913
659 950462141078886575220197
660 997347874271888240580517
661 1046509650548007129735809
662 1098056161818865117778135
663 1152101293745277627264243
664 1208764194793916857377502
665 1268169699336774624236460
666 1330448401869865895523692
667 1395737120534196384204580
668 1464178977424675575649042
669 1535923905742630906006342
670 1611128737279986752111567
671 1689957756625944108948660
672 1772582797083590702546589
673 1859183845585187472553412
674 1949949148495101818252926
675 2045075871126797777128382
676 2144770215105787343185747
677 2249248136639458335517908
678 2358735477361604019269091
679 2473468745776253911182706
680 2593695263778175080691387
681 2719674015982344906443960
682 2851675814426209581844675
683 2989984220797556156045554
684 3134895732163982401812480
685 3286720781441273517281520
686 3445783947378389677002881
687 3612425038947969785667878
688 3786999333236855914609383
689 3969878749809450931521439
690 4161452120625147229996900
691 4362126460810984610595753
692 4572327275241991374105633
693 4792499932577617384541821
694 5023110013719519451695943
695 5264644796400625228807608
696 5517613651363213089434103
697 5782549645266184465723320
698 6060009991127024729752881
699 6350577777806997439762121
700 6654862482025394269254436
701 6973501833222846546270431
702 7307162395304504854853612
703 7656541576247891927571770
704 8022368288652715183050129
705 8405405114078128671913052
706 8806449052500644428160707
707 9226333852012257586747381
708 9665930858396024782812098
709 10126151521528588179614544
710 10607948357508486002960110
711 11112317643851546927820512
712 11640300507935880412472413
713 12192985823897826958119760
714 12771511442622152965064800
715 13377067304109547219187379
716 14010896825824217657301144
717 14674300245253335427331322
718 15368636185169284719668447
719 16095325242102886780813895
720 16855851748961124301892296
721 17651767626242041186829895
722 18484694364517801338034124
723 19356327156388539299497514
724 20268437123574207467475447
725 21222875748896000482185580
726 22221577375168434075501813
727 23266563957868595319293764
728 24359947865658739981073930
729 25503936975919052529527890
730 26700837809619278867686408
731 27953060993504625304190590
732 29263124765145326839873652
733 30633660827350328589758838
734 32067418262621720648725957
735 33567269807277657377227726
736 35136216218195027881088427
737 36777392996232867247797350
738 38494075252135387715650275
739 40289684911106084736964172
740 42167796129032906500798827
741 44132143012564224599410785
742 46186625641488090217262453
743 48335318341347330380405387
744 50582476372825737098941243
745 52932544796909659282998960
746 55390165897594702064004327
747 57960188682800778307981879
748 60647677112575646132712855
749 63457920282510223645821766
750 66396441535986139465158399
751 69469009380653339586272987
752 72681647570108835215868509
753 76040646808221200459677142
754 79552575893044080728386619
755 83224294268336055392866192
756 87062964330475610340732450
757 91076064891563803372870393
758 95271404758737431300425772
759 99657137178701409704424300
760 104241774808089084405198818
761 109034205215301314547797893
762 114043707370585179203649353
763 119279968287586144685254007
764 124753101172565481949793556
765 130473663295284163562714614
766 136452675948398022156510883
767 142701643645118692505525025
768 149232576052290889038705185
769 156058008620896373941121980
770 163191026669790037765542281
771 170645287564484351201124559
772 178435047142953771413557211
773 186575183568460586079411100
774 195081226304433462891042841
775 203969381778304466002880421
776 213256565129185864465651631
777 222960427832033827309347067
778 233099392459878474261741902
779 243692682431054510783019017
780 254760360047077376223728289
781 266323358540426590692605628
782 278403523670019067155202539
783 291023648263082543600934060
784 304207517672520600449196745
785 317979947024041649497483674
786 332366830863810304799133461
787 347395183341161741763355224
788 363093192400767834463347752
789 379490263152305055257380256
790 396617076989185584275554538
791 414505638419438314807198216
792 433189339522895805832388312
793 452703010542617083887362985
794 473082990124565832662411829
795 494367179996196438249944592
796 516595121467104320350615940
797 539808054551275900218397032
798 564049001244302427583044077
799 589362829478281077379062602
800 615796343730980046375540529
801 643398354237924430379821668
802 672219775531725227015594105
803 702313701374547844348702520
804 733735511871770153618891971
805 766542954630252408322764669
806 800796261139953799817900635
807 836558234709354113117235915
808 873894376861705398630377605
809 912872982649088117124946052
810 953565277867088036991841305
811 996045522403445338415257169
812 1040391159136240219066194588
813 1086682926032515177357550246
814 1135005017660994363103578582
815 1185445206820631978590750463
816 1238095019669699586885960931
817 1293049867734536922917116028
818 1350409237733044325086382289
819 1410276834890323536010523526
820 1472760788616420489165295708
821 1537973808138710791020186894
822 1606033405281800270602761065
823 1677062063516791063302780820
824 1751187479185846798559310895
825 1828542745166674557063717391
826 1909266611986050718505910490
827 1993503687404433698873499709
828 2081404718972149769795507015
829 2173126810954837037163162998
830 2268833730003744689987775614
831 2368696140968335915110461991
832 2472891937478720777142255613
833 2581606498328138590264637055
834 2695033044901804420366123410
835 2813372919959869309373803316
836 2936835973993492091485168071
837 3065640868399322046520545632
838 3200015493001344788969667731
839 3340197295781824758568369694
840 3486433733977181247935911268
841 3638982632718827098975807685
842 3798112672294059461882316971
843 3964103778254448035462087650
844 4137247647629362180347547304
845 4317848173280790066561392243
846 4506222012068891828958549895
847 4702699046471672363568431833
848 4907622997929927660735595178
849 5121351929009524930447639408
850 5344258905398655187661110288
851 5576732542171146443346274871
852 5819177718173368934259216159
853 6072016170250667960679083658
854 6335687264046130363418345616
855 6610648640380724176205539358
856 6897377046793007720322591950
857 7196369040618751354736630717
858 7508141885931300452123495374
859 7833234318250541413183710583
860 8172207511899901559374597989
861 8525645911689565476345683773
862 8894158276090039742630598716
863 9278378581683117444094196310
864 9678967147965758003089618197
865 10096611620846828775226043838
866 10532028185341050844656238911
867 10985962634913003841501658323
868 11459191678801775228149990373
869 11952524104578776814897332452
870 12466802187362063331880524301
871 13002902953564791074142910765
872 13561739699817121050352859853
873 14144263366540587067718476507
874 14751464174998143379602322117
875 15384373120040493786667665850
876 16044063734354794255019997236
877 16731653710495641754910247777
878 17448306802103709762346252054
879 18195234586161320005012804840
880 18973698511708342216331087265
881 19785011814154034338524178684
882 20630541722832717122202405504
883 21511711540165619895525442019
884 22430003020278348023120464314
885 23386958626843093117974952607
886 24384184095928478204522847931
887 25423350887470298649771681135
888 26506198946547775406576239951
889 27634539364635236234471586315
890 28810257354602539299905200864
891 30035315139198121559178049746
892 31311755156262589777318992929
893 32641703193291298414969744222
894 34027371840634723617617909471
895 35471063892495144302149635754
896 36975176067273766224491120162
897 38542202696977565308741977782
898 40174739735368548195994623368
899 41875488759503636363353107984
900 43647261287955186602117934316
901 45492983120086888728217618602
902 47415698988355140011821268491
903 49418577262948594809951864450
904 51504914964058624460928647386
905 53678142861688427513043161659
906 55941830875806746233617179467
907 58299693603478097575095167297
908 60755596137000343835643393684
909 63313560053030358150699760077
910 65977769681164394707674619451
911 68752578592449080386438434065
912 71642516353408350567110922244
913 74652295554250202356345708108
914 77786819086088384219961020799
915 81051187752298123204804638823
916 84450708109642650840570346806
917 87990900709609986907961120368
918 91677508547348088466606876839
919 95516505983450681330828671194
920 99514107848050882159968690694
921 103676779097432034111701520876
922 108011244624345914367263421605
923 112524499708028447116786900167
924 117223820585817755725757734533
925 122116775759673179530093311961
926 127211237388490984930679141936
927 132515393519084555133331694178
928 138037760363259194455938072876
929 143787195526433096548232363264
930 149772911238559892255088618853
931 156004488659185712443497254530
932 162491892136730669199450330303
933 169245484674810402549499926906
934 176276043300233385848335656597
935 183594775781901875778883630702
936 191213337194185889107589189367
937 199143847986687383566720934681
938 207398911836446021533361052017
939 215991635174341471889455726378
940 224935646426913063421632167466
941 234245117113221522811400193370
942 243934782584959789192985929703
943 254019964816244971515318590176
944 264516594759209524428931433196
945 275441236958483365348190431634
946 286811113648626635166721360375
947 298644131335045100060074371291
948 310958906769511808229232746443
949 323774795649980962402781686889
950 337111920621095878089026391125
951 350991202256887597894940405945
952 365434389244645269320044476036
953 380464091826857533198163359686
954 396103814339184395976077112306
955 412377991301293451227732981670
956 429312022492993476456386803892
957 446932311897891345532894173851
958 465266305516094230045606796754
959 484342533379948228819688501938
960 504190650317170718600543095126
961 524841481274397939247377635050
962 546327065261249237078064065257
963 568680704235098960159556266444
964 591937010474498007028726651279
965 616131959297575715920466174440
966 641302940132538239824304396889
967 667488813362506010144510834257
968 694729965381585058487979811216
969 723068369880845289839852939496
970 752547647200824040238994732201
971 783213130396872279153119697355
972 815111929223025030659616970026
973 848293001340194897537585596197
974 882807221292251391075872972148
975 918707457247660922110604818462
976 956048645356504446849935546183
977 994887872445275112248690225504
978 1035284456173566231561462842049
979 1077300034133003021577883270800
980 1120998650254619913128932497093
981 1166446850796462389140934191849
982 1213713777487404428776741072325
983 1262871270923994094738016446312
984 1313993970973828909580250966872
985 1367159428140902217203897843573
986 1422448211791841197503140650902
987 1479944030090546929447997030303
988 1539733846653829188485781322271
989 1601908009700715046768932942760
990 1666560377790496029757089814807
991 1733788458879949271921496604161
992 1803693545846800624218952556347
993 1876380866199478906533668839676
994 1951959728142739396880218542820
995 2030543681739731311266576289315
996 2112250676334307522250192928726
997 2197203234024387323008252156744
998 2285528619317583671319447884804
999 2377359025838399298410690454361
1000 2472831759160566618231209054357