3 1
4 0
5 1
6 2
7 3
8 3
9 6
10 7
11 11
12 14
13 20
14 25
15 35
16 43
17 58
18 73
19 95
20 118
21 152
22 187
23 237
24 291
25 363
26 443
27 549
28 665
29 815
30 985
31 1197
32 1437
33 1737
34 2075
35 2491
36 2966
37 3539
38 4195
39 4984
40 5882
41 6955
42 8183
43 9633
44 11291
45 13246
46 15474
47 18085
48 21066
49 24536
50 28495
51 33092
52 38321
53 44370
54 51254
55 59179
56 68185
57 78532
58 90266
59 103706
60 118938
61 136328
62 156011
63 178438
64 203773
65 232575
66 265085
67 301946
68 343496
69 390529
70 443461
71 503261
72 570491
73 646291
74 731401
75 827215
76 934643
77 1055385
78 1190622
79 1342361
80 1512112
81 1702322
82 1914841
83 2152636
84 2418043
85 2714592
86 3045212
87 3414174
88 3825051
89 4283010
90 4792492
91 5359644
92 5989950
93 6690835
94 7468953
95 8333239
96 9291862
97 10355469
98 11534045
99 12840381
100 14286535
101 15887856
102 17659006
103 19618250
104 21783361
105 24176213
106 26818164
107 29735354
108 32953565
109 36503864
110 40417295
111 44730911
112 49481850
113 54714259
114 60472687
115 66809483
116 73777975
117 81440398
118 89860294
119 99111538
120 109269954
121 120422954
122 132660854
123 146087213
124 160809224
125 176949447
126 194635202
127 214011119
128 235228196
129 258457256
130 283876870
131 311688556
132 342103543
133 375359057
134 411704623
135 451419563
136 494797971
137 542168407
138 593877475
139 650310930
140 711876761
141 779027888
142 852243657
143 932055304
144 1019025848
145 1113777451
146 1216970685
147 1329333992
148 1451641183
149 1584744382
150 1729549659
151 1887052465
152 2058312658
153 2244492720
154 2446830719
155 2666682980
156 2905495003
157 3164847452
158 3446426435
159 3752073171
160 4083752094
161 4443606184
162 4833922835
163 5257193614
164 5716079643
165 6213476287
166 6752476202
167 7336441300
168 7968963597
169 8653943084
170 9395548350
171 10198301016
172 11067034182
173 12006986295
174 13023757476
175 14123411342
176 15312431752
177 16597833465
178 17987117029
179 19488391686
180 21110328771
181 22862295327
182 24754308894
183 26797183062
184 29002481319
185 31382678694
186 33951115082
187 36722171433
188 39711226284
189 42934848106
190 46410752446
191 50158015489
192 54197032723
193 58549752298
194 63239639562
195 68291932459
196 73733609468
197 79593673248
198 85903123257
199 92695266399
200 100005699973
201 107872652428
202 116336974054
203 125442515561
204 135236128698
205 145768081914
206 157092077760
207 169265709865
208 182350495158
209 196412381747
210 211521799010
211 227754216440
212 245190220565
213 263916130653
214 284024100891
215 305612805075
216 328787568913
217 353661125018
218 380353786604
219 408994280869
220 439719964012
221 472677748427
222 508024365884
223 545927391860
224 586565571721
225 630129953462
226 676824278504
227 726866242585
228 780487961580
229 837937366777
230 899478764830
231 965394382988
232 1035985028169
233 1111571807794
234 1192496902518
235 1279125473256
236 1371846573199
237 1471075262585
238 1577253669295
239 1690853344747
240 1812376494432
241 1942358591781
242 2081369812239
243 2230017935037
244 2388949997174
245 2558855526999
246 2740468448105
247 2934570670493
248 3141994289824
249 3363625577465
250 3600407500985
251 3853344171125
252 4123503726474
253 4412023275940
254 4720112208075
255 5049057686143
256 5400228422515
257 5775080803502
258 6175163188874
259 6602122722754
260 7057710240433
261 7543787844141
262 8062334477052
263 8615454367021
264 9205383352494
265 9834498275511
266 10505324170022
267 11220544712710
268 11983010362331
269 12795750006370
270 13661980169111
271 14585117970055
272 15568791551075
273 16616854495992
274 17733397603998
275 18922764955907
276 20189567198175
277 21538699419606
278 22975356149394
279 24505051249207
280 26133634807551
281 27867315296996
282 29712678591744
283 31676712619747
284 33766828780172
285 35990889371380
286 38357231665109
287 40874698446849
288 43552665060900
289 46401073383143
290 49430462211811
291 52652005056882
292 56077544237403
293 59719632941592
294 63591573461899
295 67707463969336
296 72082241395770
297 76731733446865
298 81672706633210
299 86922924134359
300 92501199571237
301 98427461332889
302 104722812780016
303 111409603748816
304 118511497880760
305 126053552129901
306 134062292028080
307 142565800035483
308 151593799676802
309 161177753705984
310 171350958069769
311 182148651000770
312 193608117912883
313 205768812571696
314 218672474186041
315 232363261972915
316 246887885757674
317 262295755434551
318 278639126576569
319 295973266357662
320 314356615881640
321 333850974349072
322 354521679896340
323 376437814027892
324 399672403002582
325 424302644659399
326 450410132655462
327 478081108094211
328 507406709053573
329 538483249732932
330 571412498026800
331 606301985073732
332 643265313980105
333 682422503019105
334 723900328810018
335 767832706814609
336 814361072692560
337 863634803990593
338 915811643846765
339 971058168242513
340 1029550256526447
341 1091473609119796
342 1157024269868676
343 1226409199452210
344 1299846855164899
345 1377567825896306
346 1459815475369042
347 1546846645237425
348 1638932368513455
349 1736358647840424
350 1839427246610161
351 1948456550277294
352 2063782443271300
353 2185759262104044
354 2314760767100924
355 2451181196764455
356 2595436344361059
357 2747964724062259
358 2909228763253996
359 3079716092136719
360 3259940863833090
361 3450445180108694
362 3651800552674910
363 3864609479077922
364 4089507059738302
365 4327162739573830
366 4578282096896974
367 4843608767676900
368 5123926424150051
369 5420060900441155
370 5732882380297438
371 6063307744775400
372 6412302990582180
373 6780885822353111
374 7170128325349597
375 7581159827227756
376 8015169850951255
377 8473411273552039
378 8957203587826729
379 9467936388040953
380 10007072971949229
381 10576154186503924
382 11176802404569259
383 11810725767099488
384 12479722572470056
385 13185685954874875
386 13930608728081444
387 14716588543865085
388 15545833235787419
389 16420666505936976
390 17343533818972865
391 18317008669825209
392 19343799083330363
393 20426754520864491
394 21568873045942187
395 22773308933575129
396 24043380568281526
397 25382578825787748
398 26794575776535742
399 28283233916295828
400 29852615754959547
401 31506993980232521
402 33250862019430102
403 35088945228133845
404 37026212521383542
405 39067888688254585
406 41219467197693161
407 43486723749890116
408 45875730372362416
409 48392870329181353
410 51044853634215346
411 53838733451105117
412 56781923162259264
413 59882214405400410
414 63147795850399764
415 66587273031618738
416 70209688999418481
417 74024546122940697
418 78041828798469704
419 82272027414137139
420 86726163314896495
421 91415815138226649
422 96353146254672392
423 101550933703689882
424 107022598348828773
425 112782236664772355
426 118844653869102293
427 125225398834618311
428 131940800484593579
429 139008006130547587
430 146445021444212554
431 154270752549404364
432 162505049913639326
433 171168754552839873
434 180283746217959379
435 189872994105135477
436 199960609747033229
437 210571902658012740
438 221733438378462559
439 233473099523779650
440 245820149472029817
441 258805299329474566
442 272460777796630987
443 286820404610987513
444 301919667176530410
445 317795801095337956
446 334487874200135115
447 352036874843369325
448 370485804030523986
449 389879772197310864
450 410266100206189347
451 431694425408609936
452 454216812337718056
453 477887868926219133
454 502764867803719578
455 528907873621006109
456 556379875944171236
457 585246928722055737
458 615578295860459002
459 647446603964645830
460 680928001774726292
461 716102327418749110
462 753053282998412543
463 791868617699521397
464 832640318934873534
465 875464812781663386
466 920443173214843056
467 967681341474733535
468 1017290355063578564
469 1069386587790391384
470 1124092000355139519
471 1181534402976156515
472 1241847729549695218
473 1305172324937478894
474 1371655244868958558
475 1441450570152071180
476 1514719734680927968
477 1591631869036653318
478 1672364159173761959
479 1757102222099616567
480 1846040498043855879
481 1939382661143985254
482 2037342048153509648
483 2140142107323243089
484 2248016866974856544
485 2361211426052410694
486 2479982466185015444
487 2604598787690524352
488 2735341869073831386
489 2872506452601251519
490 3016401155529432501
491 3167349109734726902
492 3325688629348919869
493 3491773909322851642
494 3665975754559354732
495 3848682342722154338
496 4040300020403777522
497 4241254135959788131
498 4451989908738160528
499 4672973338225604122
500 4904692152895712508
501 5147656802507342082
502 5402401493702403388
503 5669485272896968248
504 5949493156385418174
505 6243037311914159184
506 6550758291728281315
507 6873326321625729010
508 7211442646117046540
509 7565840934526307958
510 7937288748234977269
511 8326589074226622598
512 8734581925254615373
513 9162146012132622614
514 9610200488605029853
515 10079706774667108828
516 10571670458939679719
517 11087143286364504634
518 11627225231994044887
519 12193066667563080350
520 12785870621803951679
521 13406895141648605294
522 14057455755484635323
523 14738928046097073788
524 15452750334695622220
525 16200426484179086730
526 16983528823294372800
527 17803701200404100315
528 18662662168801245340
529 19562208312888099030
530 20504217717473422476
531 21490653590148098799
532 22523568039341370384
533 23605106018712991613
534 24737509440862808474
535 25923121471759165282
536 27164391009290804379
537 28463877358139954629
538 29824255104846818817
539 31248319206123613788
540 32738990294795186802
541 34299320217348438003
542 35932497808029894434
543 37641854914461139957
544 39430872680328433715
545 41303188101182925969
546 43262600859578904055
547 45313080456732581373
548 47458773647670349701
549 49704012198274984293
550 52053320972010463566
551 54511426366057901408
552 57083265105525488725
553 59773993416888014836
554 62588996590290252260
555 65533898953393452453
556 68614574267460613235
557 71837156570004832916
558 75208051475849103880
559 78733947962690614864
560 82421830654283417074
561 86278992629227792060
562 90313048769860627162
563 94531949681280946577
564 98943996196503069077
565 103557854499971739122
566 108382571887072439120
567 113427593194230462813
568 118702777919019145820
569 124218418067416837593
570 129985256749571326411
571 136014507563950081505
572 142317874793353335120
573 148907574455606806521
574 155796356234715540722
575 162997526338466072585
576 170524971310756145932
577 178393182848050223479
578 186617283650964759635
579 195213054364043017781
580 204196961637684233759
581 213586187369236611242
582 223398659160426254117
583 233653082052381593501
584 244368971578918637542
585 255566688203910678431
586 267267473187199832270
587 279493485949796309255
588 292267842986928204179
589 305614658404984741774
590 319559086135380952107
591 334127363907077077813
592 349346859035623422798
593 365246116116599554950
594 381854906686558688177
595 399204280945949355159
596 417326621612817502242
597 436255700008856527665
598 456026734452776888708
599 476676451070211826066
600 498243147101802098438
601 520766756826908367322
602 544288920191833140388
603 568853054268848568794
604 594504427642750647193
605 621290237860772058287
606 649259692051047601497
607 678464090855727286226
608 708956915793116503073
609 740793920205970296318
610 774033223920260557105
611 808735411783430853208
612 844963636217196957682
613 882783723966701168625
614 922264287192709893297
615 963476839102416294331
616 1006495914278115459111
617 1051399193914131269574
618 1098267636134846476153
619 1147185611620160555370
620 1198241044725927572899
621 1251525560342842062433
622 1307134636697212706162
623 1365167764355557188778
624 1425728611653608917513
625 1488925196831538459552
626 1554870067114527541212
627 1623680485041861499937
628 1695478622303711374615
629 1770391761411776823271
630 1848552505484578393800
631 1930098996498322593098
632 2015175142307489722618
633 2103930852812680614920
634 2196522285605092411923
635 2293112101493811857280
636 2393869730272499569714
637 2498971647162478260225
638 2608601660318178190014
639 2722951209865093121466
640 2842219678887901839262
641 2966614716874580790227
642 3096352576068344228404
643 3231658461271609108204
644 3372766893590715934510
645 3519922088706854825777
646 3673378350201720127232
647 3833400478567736838037
648 4000264196474270482713
649 4174256590967410119891
650 4355676573221004286146
651 4544835356567865894317
652 4742056953478705379012
653 4947678692272931331445
654 5162051754282618830846
655 5385541732313168969067
656 5618529211179906678346
657 5861410371227970528050
658 6114597615677185094481
659 6378520222767930604487
660 6653625023616954206973
661 6940377106832959811329
662 7239260550873403912516
663 7550779185271674090559
664 7875457381794153857476
665 8213840876741675592981
666 8566497625538927051524
667 8934018690918036105054
668 9317019165930456877429
669 9716139133191946987640
670 10132044661692267144952
671 10565428842680369499235
672 11017012866061654197753
673 11487547138931962716219
674 11977812447797897750886
675 12488621166230519160417
676 13020818509623644811058
677 13575283838935359106101
678 14152932015214835808354
679 14754714806934442784774
680 15381622352070110559167
681 16034684677101796091302
682 16714973275028601358113
683 17423602744733586807301
684 18161732493955877662750
685 18930568508380450024670
686 19731365189278620201549
687 20565427262397962364036
688 21434111760723365900336
689 22338830084010318855417
690 23281050137915020410578
691 24262298555839776863698
692 25284163006536510688105
693 26348294590820268629259
694 27456410330670205508615
695 28610295754320684468031
696 29811807580872204147307
697 31062876508294088906753
698 32365510108619855568827
699 33721795834496336221846
700 35133904141178986547871
701 36604091728444988989544
702 38134704906829852329976
703 39728183092992538201460
704 41387062438951533882298
705 43113979600354829773184
706 44911675648888045839780
707 46783000134367979235456
708 48730915302014532829262
709 50758500470860854612930
710 52868956579212318909401
711 55065610903556974688437
712 57351921957286770408096
713 59731484576107509290098
714 62208035196978731275798
715 64785457337971629045681
716 67467787286403814144042
717 70259220003186476240686
718 73164115251298634508075
719 76187003956911547102173
720 79332594811674837212093
721 82605781125317834629131
722 86011647937718613447800
723 89555479400270594050403
724 93242766436387291722819
725 97079214691700812500155
726 101070752784533301248411
727 105223540867975512186278
728 109543979514944622588398
729 114038718938390589072943
730 118714668558874211720665
731 123579006932582081224484
732 128639192052914857896692
733 133902972039674950683342
734 139378396229970177553730
735 145073826685889960648201
736 150997950134122334493962
737 157159790353673512274110
738 163568721027986601064822
739 170234479078806354617788
740 177167178499297115395093
741 184377324705031547261008
742 191875829421655910872924
743 199674026129212011161431
744 207783686083314410564955
745 216217034934623817417967
746 224986769968309206203098
747 234106077986505502501908
748 243588653857061580122112
749 253448719753264095593407
750 263701045109549933433488
751 274360967319692141234374
752 285444413204314390559418
753 296967921276147304743195
754 308948664831856900885991
755 321404475900925365234726
756 334353870082531892894952
757 347816072303128773886541
758 361811043527930468279640
759 376359508461384245235566
760 391482984272273340297589
761 407203810381064385321963
762 423545179347757894262004
763 440531168900578361362729
764 458186775146557715673059
765 476537947007267772997640
766 495611621923750583068210
767 515435762877029532480299
768 536039396771459418504132
769 557452654230648185186584
770 579706810856647282341226
771 602834330005731262321793
772 626868907135147722354750
773 651845515778001112497317
774 677800455204598146340474
775 704771399831533915590843
776 732797450441074168395608
777 761919187276520025729894
778 792178725080638931952943
779 823619770147567462851509
780 856287679460119604414319
781 890229521987959260567210
782 925494142223764582413651
783 962132226038252895830243
784 1000196368936755797737344
785 1039741146804005174849889
786 1080823189225775166578051
787 1123501255480241135975768
788 1167836313294077223988586
789 1213891620462790376787563
790 1261732809437139163147812
791 1311427974982239145901295
792 1363047765018511132216970
793 1416665474758677155909412
794 1472357144257783429446832
795 1530201659498591787329287
796 1590280857137692143106088
797 1652679633043384889426415
798 1717486054759647306284040
799 1784791478036550258343086
800 1854690667571029984726811
801 1927281922108350429864350
802 2002667204058424069434363
803 2080952273787992869383395
804 2162246828753819050459275
805 2246664647649298256594756
806 2334323739741394879176730
807 2425346499582518855203262
808 2519859867286814758144088
809 2617995494568539943099749
810 2719889916745450810126825
811 2825684730918840234440312
812 2935526780547531185956964
813 3049568346642406764763115
814 3167967345814169387959379
815 3290887535416884221856874
816 3418498726036457426496512
817 3550977001583687558685087
818 3688504947258642207352345
819 3831271885664265302231649
820 3979474121354790233126245
821 4133315194116396296638965
822 4293006141285811348478021
823 4458765769425181174435771
824 4630820935680430209478202
825 4809406839163759742439887
826 4994767322710518650194920
827 5187155185374959559113302
828 5386832506039715554166186
829 5594070978529022633508781
830 5809152258626821204147668
831 6032368323417031046269427
832 6264021843375244279534481
833 6504426567658276450780065
834 6753907723050867222723421
835 7012802427047119696673667
836 7281460115558084060466090
837 7560242985756361942378677
838 7849526454583458186647876
839 8149699633466327184269038
840 8461165819805517154005828
841 8784343005819367473332410
842 9119664405345854311004910
843 9467578999227148873264962
844 9828552099920359835188134
845 10203065936002910458412295
846 10591620257260763274114538
847 10994732961074292517437878
848 11412940740837816818969312
849 11846799757177104397603837
850 12296886332751926445178220
851 12763797671460858286592896
852 13248152602889949569579362
853 13750592352878951740565376
854 14271781341104986186994942
855 14812408006617672293436874
856 15373185662287826161743482
857 15954853379168180366343551
858 16558176901794693195090946
859 17183949595495702811330545
860 17832993426808466336444341
861 18506159978143810131200984
862 19204331497874217817282137
863 19928421987064530970999397
864 20679378324101511514772931
865 21458181428525198664595649
866 22265847465404710952138092
867 23103429091650846600071963
868 23972016745700377738643387
869 24872739982059852111670518
870 25806768852242274567533405
871 26775315333686383332447361
872 27779634808297016912760148
873 28821027592305056227490079
874 29900840519197648968634878
875 31020468577533295009036594
876 32181356605512268276002055
877 33385001044240857671464737
878 34632951751687729673454916
879 35926813879403125072646751
880 37268249814135611448692244
881 38658981186558211297045060
882 40100790949384205820204596
883 41595525527235005391249106
884 43145097040695730468030203
885 44751485607081552883265552
886 46416741720516194353510983
887 48142988714017044936258166
888 49932425306365146422763959
889 51787328236637377972321503
890 53710054989367763856379243
891 55703046613410330767467653
892 57768830637671713799604825
893 59910024086994048336093020
894 62129336601571058537607158
895 64429573663399863662068601
896 66813639933380439879495662
897 69284542702802026870243903
898 71845395463072697765530100
899 74499421597683903984442300
900 77249958200526747502365879
901 80100460024821099706994826
902 83054503567052171625037358
903 86115791290462845229628995
904 89288155992792673289833486
905 92575565323118100925477845
906 95982126452800774499313745
907 99512090905725030851311557
908 103169859553168330440506590
909 106959987778833887064748998
910 110887190819748460416342114
911 114956349288925753820238823
912 119172514885881343503821219
913 123540916301295300232009254
914 128066965322316694770998059
915 132756263145227990199168118
916 137614606902398727526663925
917 142647996410696172426269636
918 147862641148746244588761912
919 153264967470691690487599248
920 158861626064335300218231772
921 164659499661825971398560091
922 170665711011302445129274633
923 176887631118196954130840036
924 183332887765175285124515646
925 190009374319995701713399068
926 196925258840861803678544060
927 204088993489170056761428886
928 211509324259864924280503728
929 219195301039961166233125568
930 227156288006125910870053659
931 235401974372582056173410719
932 243942385500949798238466116
933 252787894384035778716327507
934 261949233515958228056064405
935 271437507161414436138285953
936 281264204037300946001499014
937 291441210420341693603673765
938 301980823694810194910816030
939 312895766354905293222370295
940 324199200476799410857345050
941 335904742675882067792252076
942 348026479565211260498128568
943 360578983731721456731674057
944 373577330247259158580195146
945 387037113732087549106799416
946 400974465989058391440243029
947 415406074227256501310369594
948 430349199894515445301218435
949 445821698138849184373606949
950 461842037919476755447974768
951 478429322788804535501375849
952 495603312367404561404560150
953 513384444534758841879150266
954 531793858359257751667532228
955 550853417791718864359530421
956 570585736147457799822338841
957 591014201402770695302415972
958 612163002332503214362679852
959 634057155516261959901111152
960 656722533241692755018186288
961 680185892334187475762545098
962 704474903943306421517300983
963 729618184317200252522566977
964 755645326597301156043276036
965 782586933666613550513725390
966 810474652085984449662212459
967 839341207153861876898102261
968 869220439126167808884689735
969 900147340634112279249595102
970 932158095338965989774270327
971 965290117864085344590407490
972 999582095045751787659192305
973 1035074028545745122513092605
974 1071807278869920619584071375
975 1109824610838503855723120167
976 1149170240555254738500000174
977 1189889883924188079112640151
978 1232030806764068509386006200
979 1275641876572530989987502027
980 1320773615993307403824070320
981 1367478258041776842981526271
982 1415809803145791517966249978
983 1465824078060577501045817433
984 1517578796718355553219578978
985 1571133623075291644692547231
986 1626550236020351594846081551
987 1683892396412723027316395990
988 1743226016316558929787904404
989 1804619230504018076657827719
990 1868142470299802905125635590
991 1933868539842756873483146457
992 2001872694842451359735294394
993 2072232723911202843359884960
994 2145029032554480821637938846
995 2220344729905336165890685620
996 2298265718291160544351803370
997 2378880785723925258674563131
998 2462281701407900102943695740
999 2548563314361869542470794101
1000 2637823655255897865090365045