Automatizare

What did you dream?
It's all right, we told you what to dream

Cerință

O permutare a numerelor $1, 2, \ldots, n$ era sortată crescător. Cineva a scos un singur element și l-a reinserat pe altă poziție (de exemplu, 1 2 3 4 5 → 1 4 2 3 5). Asemenea incidente se întâmplă des, așa că vrei să automatizezi repararea. Problema este că orice element poate fi mutat oriunde și nu poți prezice ce se va întâmpla, așa că trebuie să iei în calcul toate posibilitățile. De aceea, dorești să aplici algoritmul.

Algoritmul

Un algoritm de lungime $T$ este o secvență de $T$ operații $(i_1, r_1), (i_2, r_2), \ldots, (i_T, r_T)$, unde $i_k \in \{1, \ldots, n-1\}$ este o poziție, iar $r_k \in \{\text{reușită}, \text{eșec}\}$. Algoritmul se aplică unei permutări $a$ executând operațiile în ordine. Operația $(i_k, r_k)$ interschimbă elementele $a_{i_k}$ și $a_{i_k+1}$ doar dacă $r_k = \text{reușită}$ și $a_{i_k} > a_{i_k+1}$; altfel nu face nimic.

Un algoritm este bun dacă, aplicat oricărei permutări obținute din permutarea sortată prin mutarea unui singur element, o sortează crescător. Același algoritm, cu aceleași poziții și aceleași reușite, trebuie să funcționeze pentru toate aceste permutări.

Algoritmul se generează aleator: fiecare poziție $i_k$ se alege uniform din $\{1, \ldots, n-1\}$, iar fiecare $r_k$ este „reușită” cu probabilitatea $p = \frac{P}{100}$ și „eșec” cu probabilitatea $1 - p$. Toate aceste alegeri sunt independente.

Să se determine probabilitatea ca algoritmul generat să fie bun.

Date de intrare

Pe prima linie se găsesc trei numere întregi, $n$, $T$ și $P$.

Date de ieșire

Pe prima linie se va afișa un singur număr întreg, probabilitatea cerută modulo $998 \ 244 \ 353$.

Restricții și precizări

• $2 \leq n \leq 100$;
• $1 \leq T \leq 20 \ 000$;
• $1 \leq P \leq 100$;
• Se poate demonstra că probabilitatea cerută se poate scrie ca o fracție ireductibilă $\frac{x}{y}$, unde $y$ nu este divizibil cu $998 \ 244 \ 353$. Se cere valoarea $x \cdot y^{-1} \bmod 998 \ 244 \ 353$, unde $y^{-1}$ este inversul modular al lui $y$.
• Pentru 15 puncte, $n \leq 4$ și $T \leq 8$;
• Pentru alte 35 de puncte, $n \leq 30$ și $T \leq 1 \ 000$.

Exemplul 1

stdin

3 4 100

stdout

499122177

Explicație

Toate operațiile reușesc, iar pozițiile formează unul dintre cei $2^4 = 16$ algoritmi posibili, toți la fel de probabili. Exact $8$ dintre ei sunt buni: de exemplu, $(1, 2, 1, 2)$ este bun, iar $(1, 1, 2, 2)$ nu este, deoarece nu sortează permutarea 2 3 1. Probabilitatea este $\frac{1}{2}$, iar $2^{-1} \bmod 998 \ 244 \ 353 = 499 \ 122 \ 177$.

Exemplul 2

stdin

4 6 80

stdout

315856191

Explicație

Probabilitatea ca algoritmul să fie bun este aproximativ $0.0320038628$.