Mahnılar Salonu#13109

Mahnılar Salonu

1 saniyə
256 meqabayt

Meyxanada musiqiçi çalır. Əvvəlcə hər musiqiçi dəqiq bir mahnı bilir və bütün mahnı müxtəlifdir.

Hər axşamkı çıxışdan sonra meyxana sahibi bütün musiqiçi arasından bərabər ehtimalla bir musiqiçi seçir, sonra isə qalan n - 1 musiqiçi arasından bərabər ehtimalla bir musiqiçi seçir, yəni b \ne a. Musiqiçi bildiyi mahnını unudur və həmin anda musiqiçi -nin bildiyi mahnını öyrənir. Bütün seçimlər müstəqildir. Beləliklə, hər musiqiçi həmişə dəqiq bir mahnı bilir, lakin bir neçə musiqiçi eyni mahnını bilə bilər.

axşamdan sonra musiqiçilərin bildiyi müxtəlif mahnıların sayının riyazi gözləməsini tapın.

Giriş

Yeganə sətirdə iki tam ədəd və verilir (2 \le n \le 100, 0 \le k \le 10^{18}) — musiqiçilərin sayı və axşamların sayı.

Çıxış

Bir tam ədəd çıxarın. Göstərmək olar ki, riyazi gözləmə \frac{p}{q} rasional ədədidir, burada ədədi -ə bölünmür. p \cdot q^{-1} \bmod 998\,244\,353 qiymətini, yəni elə tam ədədini çıxarın ki, 0 \le x < 998\,244\,353 və x \cdot q \equiv p \pmod{998\,244\,353} olsun.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Nümunə 3

Loading
Loading

Nümunə 4

Loading
Loading

Qeyd

Birinci nümunədə n = 4 və k = 2. Birinci axşamdan sonra dörd musiqiçidən ikisi eyni mahnını bilir, digər ikisinin hər biri isə öz mahnısını bilir, deməli mahnı var. İkinci axşam, əgər öz mahnısını bilən iki musiqiçidən biridirsə, həmin mahnı itir və mahnı qalır; əks halda mahnı qalır. Bu halların hər biri \frac{2}{4} ehtimalı ilə baş verir, deməli mahnıların sayının riyazi gözləməsi \frac{1}{2} \cdot 2 + \frac{1}{2} \cdot 3 = \frac{5}{2} olur və 499\,122\,179 \cdot 2 \equiv 5 \pmod{998\,244\,353}. Şəkildə birinci axşamın mümkün variantlarından biri (a = 2, b = 1; hər dairə bir musiqiçinin mahnısını göstərir, musiqiçilərin nömrələri yuxarıda yazılıb) və ikinci axşamın hər iki növ nəticəsi təsvir olunub; aşağıdakı və sağdakı ədədlər müxtəlif mahnıların sayıdır.

İkinci nümunədə n = 6 və k = 1. Birinci axşam musiqiçi öz mahnısını başqa bir mahnı ilə əvəz edir, deməli dəqiq bir mahnı itir və mahnı qalır.

Üçüncü nümunədə n = 2. Birinci axşamdan sonra hər iki musiqiçi eyni mahnını bilir və bundan sonra dəqiq mahnı məlum olur.

Dördüncü nümunədə k = 0, deməli mahnının hamısı hələ də məlumdur.