26710번 - Zbiory niezależne 다국어

Drzewo T = (V, E) to nieskierowany spójny graf prosty bez cykli. W naszym zadaniu rozpatrujemy cpokolorowane drzewa – czyli takie, których każdy wierzchołek jest pomalowany na jeden z c kolorów.

Dwa pokolorowane drzewa T₁ = (V₁, E₁), T₂ = (V₂, E₂) są równe, jeśli:

• istnieje bijekcja π : V₁ → V₂ taka, że dla każdej pary wierzchołków u, v ∈ V₁, zależność {u, v} ∈ E₁ zachodzi wtedy i tylko wtedy, gdy {π(u), π(v)} ∈ E₂; oraz
• dla każdego wierzchołka v ∈ V₁, kolor przypisany v w drzewie T₁ jest taki sam, jak kolor przypisany wierzchołkowi π(v) w drzewie T₂.

Zbiorem niezależnym w drzewie T = (V, E) nazwiemy dowolny podzbiór wierzchołków S ⊆ V taki, że żadne dwa różne wierzchołki należące do S nie są połączone krawędzią. Rozmiarem zbioru niezależnego S jest liczba wierzchołków należących do S.

Otrzymujesz trzy liczby ℓ, r oraz c. Ile istnieje różnych c-pokolorowanych drzew, których maksymalny zbiór niezależny ma rozmiar co najmniej ℓ i co najwyżej r? Ponieważ wynik może być bardzo duży, podaj jedynie jego resztę z dzielenia przez 998 244 353.

Pierwszy i jedyny wiersz wejścia zawiera trzy liczby całkowite ℓ, r, c (1 ≤ ℓ ≤ r ≤ 500 000, 1 ≤ c ≤ 998 244 352).

W pierwszym i jedynym wierszu wyjścia podaj jedną liczbę: resztę z dzielenia przez 998 244 353 liczby wszystkich różnych c-pokolorowanych drzew, których maksymalny zbiór niezależny ma rozmiar z przedziału [ℓ, r].

Wyjaśnienie pierwszego przykładu: wszystkie różne 1-pokolorowane drzewa o maksymalnym zbiorze niezależnym rozmiaru 1, 2 lub 3 są przedstawione poniżej: