1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cstdio>
#include <algorithm>
#include <vector>
#define MOD 998244353
#define MAX_ZAK 100
using namespace std;

vector<pair<int, int>> ile[MAX_ZAK][MAX_ZAK][MAX_ZAK];
long long wyn[MAX_ZAK][MAX_ZAK];
long long ZAK;

long long potMod(long long base, long long pow) {
    if (pow == 0) return 1;
    long long w = potMod(base, pow >> 1);
    w = (w * w) % MOD;
    return pow & 1 ? (w * base) % MOD : w;
}

inline long long fMod(long long l) {
    return l >= MOD ? l - MOD : l;
}

long long binom(long long n, long long k) {
    long long top = 1;
    long long bot = 1;
    for (long long i = 1; i <= k; i++) {
        top = (top * (n - i + 1)) % MOD;
        bot = (bot * i) % MOD;
    }

    return (top * potMod(bot, MOD - 2)) % MOD;
}

int main() {
    int l, r, c;
    scanf("%d%d%d", &l, &r, &c);
    ZAK = (r + 1) * 2;

    ile[1][0][1].emplace_back(c, 0);

    wyn[1][1] = c;

    long long WYN = 0;

    for (int size = 2; size < ZAK; size++) {
        for (int noTopNz = 0; noTopNz <= size; noTopNz++) {
            int s = noTopNz >= size / 2 ? 1 : size / 2;
            for (int topNz = s; topNz <= size; topNz++) {
                ile[size][noTopNz][topNz].emplace_back(0, 0);
                long long sum = 0;
                int el = 1;
                for (int maxKidSize = 1; maxKidSize < size; maxKidSize++) {
                    for (int kidNoTopNz = 0; kidNoTopNz <= maxKidSize; kidNoTopNz++) {
                        int s2 = kidNoTopNz >= maxKidSize / 2 ? 1 : maxKidSize / 2;
                        for (int kidTopNz = s2; kidTopNz <= maxKidSize; kidTopNz++) {
                            for (int maxKidCount = 1; maxKidCount * maxKidSize < size; maxKidCount++) {
                                int leftSize = size - maxKidCount * maxKidSize;
                                int leftNoTopNz = noTopNz - maxKidCount * max(kidTopNz, kidNoTopNz);
                                int leftTopNz = topNz - maxKidCount * kidNoTopNz;

                                if (leftSize <= 0 || leftTopNz < 0 || leftNoTopNz < 0) continue;
                                if (leftSize < leftNoTopNz || leftSize < leftTopNz) continue;

                                long long X;

                                auto &ileL = ile[leftSize][leftNoTopNz][leftTopNz];
                                auto &ileC = ile[maxKidSize][kidNoTopNz][kidTopNz];

                                int pp = 0; int kp = ileL.size() - 1;
                                if (kp < pp) continue;
                                while (kp != pp) {
                                    int mid = (pp + kp) >> 1;
                                    if (ileL[mid].second < el - 1) pp = mid + 1;
                                    else kp = mid;
                                }
                                X = ileL[pp].first;

                                long long Y = !ileC.empty() ? ileC[ileC.size() - 1].first : 0;

                                if (X == 0 || Y == 0) continue;
                                long long C = binom(Y + maxKidCount - 1, maxKidCount);
                                long long C2 = (X * C) % MOD;

                                sum = fMod(sum + C2);

                                if (size % 2 == 0 && maxKidSize == size / 2) {
                                    long long notDoubleCounted = 0;

                                    // only mirrored trees will noe be doublecounted
                                    if (kidTopNz == leftTopNz && kidNoTopNz == leftNoTopNz) {
                                        notDoubleCounted += Y;
                                        //printf("IS MIRROR (%lld, %lld)\n", C2, Y);
                                    }

                                    // now we aree sure every tree with double centroid was doublecounted
                                    long long doubleCounted = fMod(C2 + notDoubleCounted);

                                    // Add double-centroid trees, but divided by two, to dix doublecounting
                                    wyn[size][max(noTopNz, topNz)] =
                                            (wyn[size][max(noTopNz, topNz)] + doubleCounted * potMod(2, MOD - 2)) % MOD;
                                }
                            }

                            if (sum == ile[size][noTopNz][topNz][ile[size][noTopNz][topNz].size() - 1].first) {
                                ile[size][noTopNz][topNz][ile[size][noTopNz][topNz].size() - 1].second++;
                            } else {
                                ile[size][noTopNz][topNz].emplace_back(sum, el);
                            }
                            el++;
                        }
                    }

                    if (size % 2 == 0) {
                        // Poj. Centroid
                        if (maxKidSize == size / 2 - 1) {
                            wyn[size][max(noTopNz, topNz)] =
                                    (wyn[size][max(noTopNz, topNz)] + sum) % MOD;
                        }
                    } else {
                        // Poj centroid
                        if (maxKidSize == size / 2) {
                            wyn[size][max(noTopNz, topNz)] =
                                    (wyn[size][max(noTopNz, topNz)] + sum) % MOD;
                        }
                    }
                }
            }
        }
    }

    for (int i = 1; i < ZAK; i++) {
        for (int j = l; j <= r; j++) WYN = fMod(WYN + wyn[i][j]);
    }
    printf("%lld\n", WYN);
}