Şarkılar Salonu#13109

Şarkılar Salonu

1 saniye
256 megabayt

Bir meyhanede müzisyen çalmaktadır. Başlangıçta her müzisyen tam olarak bir şarkı bilir ve şarkının hepsi farklıdır.

Her akşamki gösteriden sonra meyhaneci, müzisyenin tamamı arasından eşit olasılıkla bir müzisyen seçer, ardından diğer n - 1 müzisyen arasından eşit olasılıkla bir müzisyen seçer, yani b \ne a. Müzisyen bildiği şarkıyı unutur ve o anda müzisyen 'nin bildiği şarkıyı öğrenir. Tüm seçimler bağımsızdır. Böylece her müzisyen her zaman tam olarak bir şarkı bilir, ancak birden fazla müzisyen aynı şarkıyı biliyor olabilir.

akşam sonra müzisyenlerin bildiği farklı şarkı sayısının beklenen değerini bulun.

Giriş

Tek satırda iki tam sayı ve verilir (2 \le n \le 100, 0 \le k \le 10^{18}) — müzisyen sayısı ve akşam sayısı.

Çıktı

Bir tam sayı yazdırın. Beklenen değerin, paydası sayısı ile bölünmeyen bir \frac{p}{q} rasyonel sayısı olduğu gösterilebilir. p \cdot q^{-1} \bmod 998\,244\,353 değerini, yani 0 \le x < 998\,244\,353 ve x \cdot q \equiv p \pmod{998\,244\,353} koşullarını sağlayan tam sayısını yazdırın.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Örnek 3

Loading
Loading

Örnek 4

Loading
Loading

Not

Birinci örnekte n = 4 ve k = 2. Birinci akşamdan sonra dört müzisyenden ikisi aynı şarkıyı bilir, diğer ikisinin her biri ise kendi şarkısını bilir, yani şarkı vardır. İkinci akşam, eğer kendi şarkısını bilen iki müzisyenden biriyse, o şarkı kaybolur ve şarkı kalır; aksi hâlde şarkı kalır. Bu durumların her biri \frac{2}{4} olasılıkla gerçekleşir, dolayısıyla beklenen şarkı sayısı \frac{1}{2} \cdot 2 + \frac{1}{2} \cdot 3 = \frac{5}{2} olur ve 499\,122\,179 \cdot 2 \equiv 5 \pmod{998\,244\,353}. Şekilde olası bir birinci akşam (a = 2, b = 1; her daire bir müzisyenin şarkısını gösterir, müzisyenlerin numaraları üsttedir) ve ikinci akşamın her iki tür sonucu gösterilmiştir; alttaki ve sağdaki sayılar farklı şarkı sayılarıdır.

İkinci örnekte n = 6 ve k = 1. Birinci akşam müzisyen kendi şarkısını başka bir şarkıyla değiştirir, yani tam olarak bir şarkı kaybolur ve şarkı kalır.

Üçüncü örnekte n = 2. Birinci akşamdan sonra iki müzisyen de aynı şarkıyı bilir ve o andan itibaren tam olarak şarkı bilinir.

Dördüncü örnekte k = 0, yani şarkının hepsi hâlâ bilinmektedir.