久莲 adalah seorang gadis yang suka bermain.

Liburan musim panas akhirnya tiba. 久莲 memutuskan untuk mengundang teman-temannya berenang. Dia berencana terlebih dahulu membatasi sebuah kawasan laut berbentuk persegi panjang di depan pantai pribadi keluarganya untuk dijadikan tempat berenang. Namun, laut memiliki berbagai bahaya: di beberapa tempat airnya terlalu dalam, dan di tempat lain terdapat ubur-ubur berbisa. Dia ingin seluruh kawasan laut yang dibatasi itu aman.

Setelah analisis awal, dia memodelkan kawasan laut ini sebagai kisi persegi panjang dengan panjang sisi bawah $N$ meter dan tinggi $1001$ meter. Sisi bawah kisi bersesuaian dengan pantai pribadi keluarganya, dan setiap persegi kecil berukuran $1\times 1$ mewakili satu unit kawasan laut. Dia meminta ayahnya memeriksa besok apakah setiap persegi kecil aman. Setelah memperoleh informasi tersebut, dia tinggal membatasi tempat berenang yang diinginkannya.

Tempat berenang idealnya memenuhi tiga syarat berikut:

• Harus aman. Artinya, setiap unit kawasan laut di dalam tempat berenang harus aman.
• Harus berbentuk persegi panjang. Artinya, tempat berenang harus berupa subkisi berukuran $a\times b$ dari keseluruhan kisi.
• Harus bersebelahan dengan pantai. Artinya, batas bawah tempat berenang harus menempel pada batas bawah kisi.

Sebagai contoh, saat $N=5$, misalkan hasil pemeriksaannya sebagai berikut (karena $1001$ terlalu besar, di sini hanya ditampilkan informasi tiga baris terbawah kisi; seluruh bagian lainnya berbahaya).

Dia dapat memilih kawasan laut bagian berukuran $1\times 4$ pada baris terbawah, atau kawasan laut bagian berukuran $3\times 1$ di kolom ketiga. Perhatikan bahwa dia tidak boleh memilih kawasan laut bagian berukuran $1\times 5$ pada baris teratas, karena kawasan itu tidak bersebelahan dengan pantai.

Agar teman-temannya senang, dia ingin luas tempat berenangnya sebesar mungkin. Oleh karena itu, dia akan memilih kawasan laut bagian berukuran $1\times 4$ pada baris terbawah sebagai rencana akhirnya.

Walaupun baru besok dia akan mengetahui apakah setiap unit kawasan laut aman, sekarang dia sudah ingin mulai memperkirakan luas tempat berenangnya. Setelah perkiraan sederhana, dia mengasumsikan bahwa setiap unit kawasan laut, secara independen, memiliki peluang $q$ untuk aman dan peluang $1-q$ untuk tidak aman. Dia ingin mengetahui peluang bahwa luas tempat berenang terbesar yang dapat dipilihnya tepat $K$.

Namun, 久莲 tidak tertarik pada matematika, sehingga dia ingin kamu membantunya menghitung nilai tersebut.

Masukan

Baca data dari berkas pool.in.

Masukan terdiri atas satu baris berisi empat bilangan bulat positif $N,K,x,y$, dengan $1\le x<y<998244353$. Nilai $q$ adalah $\frac{x}{y}$.

Keluaran

Tuliskan keluaran ke berkas pool.out.

Keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan nilai jawaban modulo $998244353$.

Dengan kata lain, misalkan jawaban dalam bentuk pecahan paling sederhana adalah $\frac{a}{b}$, dengan $a$ dan $b$ relatif prima. Keluarkan bilangan bulat $x$ sehingga $bx\equiv a\pmod{998244353}$ dan $0\le x<998244353$. Dapat dibuktikan bahwa bilangan bulat $x$ seperti itu unik.

Contoh

Masukan 1

10 5 1 2

Keluaran 1

342025319

Contoh 2

Lihat pool/pool2.in dan pool/pool2.ans di direktori peserta.

Contoh 3

Lihat pool/pool3.in dan pool/pool3.ans di direktori peserta.

Petunjuk

$x^{p-1}\equiv 1\pmod p$, dengan $p$ bilangan prima dan $x\in[1,p)$.

Subtugas