ישנה קופסה אחת המסומנת בכל מספר שלם מ-$1$ עד $N$. כמו כן, עבור כל מספר שלם מ-$1$ עד $N$, ישנם $M$ כדורים המסומנים במספר שלם זה.
$NM$ הכדורים הללו מעורבבים ולאחר מכן מחולקים ל-$N$ הקופסאות, כך שבכל קופסה מוכנסים בדיוק $M$ כדורים.
ישנן $\frac{(NM)!}{(M!)^N}$ דרכים אפשריות למקם את הכדורים (אם מתייחסים לכל הכדורים כניתנים להבחנה), וכל הסידורים הללו מתרחשים בהסתברות שווה.
אתם תבצעו פעולות על הקופסאות והכדורים הללו. פעולה אחת מורכבת מהשלבים הבאים:
- בחרו קופסה אחת ועמדו מול הקופסה הזו.
- אם אין אף כדור בקופסה הזו, סיימו את הפעולה.
- בחרו כדור אחד כלשהו מהקופסה הזו והשליכו אותו מחוץ לקופסה.
- לבסוף, עמדו מול הקופסה שהתווית שלה תואמת לתווית של הכדור שהושלך אחרון, וחזרו לשלב $2$.
נגדיר את הניקוד שלכם כמספר הפעולות הנדרשות עד שכל $NM$ הכדורים הושלכו. אתם רוצים למזער את הניקוד הזה.
מצאו את התוחלת של הניקוד כאשר אתם פועלים באופן אופטימלי, מודולו $998244353$.
Input
השורה הראשונה מכילה את $N$ ואת $M$ בסדר זה, מופרדים ברווחים. ($1 \le N \le 10^5, 1 \le M \le 100$)
Output
הדפיסו את התשובה.
Examples
Input 1
2 2
Output 1
166374060
Input 2
3 1
Output 2
831870296
Input 3
100000 100
Output 3
402978825
Note
עבור הדוגמה הראשונה, סידורי הכדורים האפשריים ודרכי הפעולה האופטימליות המתאימות הם כדלקמן:
- הכנסת שני כדורים המסומנים ב-$1$ לקופסה $1$, ושני כדורים המסומנים ב-$2$ לקופסה $2$. (הסתברות $1/6$)
- בפעולה הראשונה, עמדו מול קופסה $1$. משם, הוציאו כדור המסומן ב-$1$ ועמדו מול קופסה $1$. לאחר מכן הוציאו כדור נוסף המסומן ב-$1$ ועמדו שוב מול קופסה $1$. בשלב זה, קופסה $1$ ריקה, ולכן סיימו את הפעולה.
- בפעולה השנייה, עמדו מול קופסה $2$. משם, הוציאו כדור המסומן ב-$2$ ועמדו מול קופסה $2$. לאחר מכן הוציאו כדור נוסף המסומן ב-$2$ ועמדו שוב מול קופסה $2$. בשלב זה, קופסה $2$ ריקה, ולכן סיימו את הפעולה.
- במקרה זה, הניקוד המינימלי שניתן להשיג הוא $2$.
- הכנסת כדור אחד המסומן ב-$1$ וכדור אחד המסומן ב-$2$ לכל אחת מהקופסאות $1$ ו-$2$. (הסתברות $2/3$)
- בפעולה הראשונה, עמדו מול קופסה $1$. משם, הוציאו כדור המסומן ב-$1$ ועמדו מול קופסה $1$. לאחר מכן הוציאו כדור המסומן ב-$2$ ועמדו מול קופסה $2$. לאחר מכן הוציאו כדור המסומן ב-$2$ ועמדו מול קופסה $2$. לאחר מכן הוציאו כדור המסומן ב-$1$ ועמדו מול קופסה $1$. בשלב זה, קופסה $1$ ריקה, ולכן סיימו את הפעולה.
- במקרה זה, הניקוד המינימלי שניתן להשיג הוא $1$.
- הכנסת שני כדורים המסומנים ב-$2$ לקופסה $1$, ושני כדורים המסומנים ב-$1$ לקופסה $2$. (הסתברות $1/6$)
- בפעולה הראשונה, עמדו מול קופסה $1$. משם, הוציאו כדור המסומן ב-$2$ ועמדו מול קופסה $2$. לאחר מכן הוציאו כדור המסומן ב-$1$ ועמדו מול קופסה $1$. לאחר מכן הוציאו כדור המסומן ב-$2$ ועמדו מול קופסה $2$. לאחר מכן הוציאו כדור המסומן ב-$1$ ועמדו מול קופסה $1$. בשלב זה, קופסה $1$ ריקה, ולכן סיימו את הפעולה.
- במקרה זה, הניקוד המינימלי שניתן להשיג הוא $1$.
לסיכום, הניקוד המינימלי הוא $2$ בהסתברות $1/6$, והניקוד המינימלי הוא $1$ בהסתברות $5/6$, ולכן תוחלת הניקוד הכוללת היא $7/6$. לפיכך, יש להדפיס $166374060$, המייצג ערך זה מודולו $998244353$.
הגדרת תוחלת מודולו $998244353$
ניתן להוכיח שהתוחלת שיש למצוא היא תמיד מספר רציונלי. כמו כן, תחת האילוצים של בעיה זו, אם התוחלת נכתבת כשבר מצומצם $\frac{y}{x}$, מובטח כי $x$ אינו מתחלק ב-$998244353$.
במקרה זה, קיים מספר שלם יחיד $z$ בין $0$ ל-$998244352$, כולל, המקיים $xz \equiv y \pmod{998244353}$. הדפיסו את $z$ זה.