久莲 est une fille qui aime s'amuser.

Les vacances d'été sont enfin arrivées. 久莲 décide d'inviter ses amis à nager. Elle compte d'abord délimiter une zone rectangulaire en mer, devant la plage privée de sa famille, pour en faire un lieu de baignade. Mais la mer recèle toutes sortes de dangers : certains endroits sont trop profonds, et d'autres sont fréquentés par des méduses venimeuses. Elle veut que toute la zone délimitée soit sûre.

Après une première analyse, elle représente cette zone par une grille rectangulaire dont la base mesure $N$ mètres et la hauteur $1001$ mètres. La base correspond à la plage privée de sa famille, et chaque petit carré de $1\times1$ représente une unité de zone maritime. Elle a demandé à son père de vérifier demain si chaque carré est sûr. Une fois ces informations connues, elle pourra délimiter son lieu de baignade.

Son lieu de baignade idéal doit respecter les trois conditions suivantes :

• Il doit être sûr : chaque unité de zone maritime qui le compose doit être sûre.
• Il doit être rectangulaire : il doit former une sous-grille $a\times b$ de la grille entière.
• Il doit être adjacent à la plage : son bord inférieur doit coïncider avec le bord inférieur de la grille.

Par exemple, lorsque $N=5$, supposons que les vérifications donnent le résultat ci-dessous. Comme $1001$ est trop grand, seules les trois rangées les plus basses sont dessinées ; tout le reste est dangereux.

Elle peut choisir la sous-zone $1\times4$ de la rangée du bas, ou la sous-zone $3\times1$ de la troisième colonne. Attention : elle ne peut pas choisir la sous-zone $1\times5$ de la rangée du haut, car celle-ci n'est pas adjacente à la plage.

Pour que ses amis s'amusent bien, elle souhaite une surface aussi grande que possible. Elle choisira donc finalement la sous-zone $1\times4$ de la rangée du bas.

Bien qu'elle ne connaisse la sûreté de chaque unité de zone maritime que demain, elle veut dès maintenant estimer la surface de son lieu de baignade. Après une estimation simple, elle suppose que chaque unité est sûre avec une probabilité $q$ et dangereuse avec une probabilité $1-q$, indépendamment des autres. Elle veut connaître la probabilité que la surface du plus grand lieu de baignade qu'elle peut choisir soit exactement $K$.

Mais 久莲 ne s'intéresse pas aux mathématiques et souhaite que vous calculiez cette valeur pour elle.

Entrée

Lire les données dans le fichier pool.in.

Une ligne contient quatre entiers strictement positifs $N,K,x,y$, où $1\le x<y<998244353$. La valeur de $q$ est $\frac xy$.

Sortie

Écrire dans le fichier pool.out.

Afficher sur une ligne un entier représentant la réponse modulo $998244353$.

Plus précisément, si la réponse sous forme de fraction irréductible est $\frac ab$, où $a,b$ sont premiers entre eux, afficher l'entier $x$ tel que $bx\equiv a\pmod{998244353}$ et $0\le x<998244353$. On peut prouver que cet entier $x$ est unique.

Exemples

Entrée 1

10 5 1 2

Sortie 1

342025319

Exemple 2

Voir les fichiers pool/pool2.in et pool/pool2.ans dans le répertoire des candidats.

Exemple 3

Voir les fichiers pool/pool3.in et pool/pool3.ans dans le répertoire des candidats.

Remarque

$x^{p-1}\equiv1\pmod p$, où $p$ est premier et $x\in[1,p)$.

Sous-tâches