קבוצה של מספרים שלמים אי־שליליים היא נאה אם ורק אם כל המספרים בקבוצה קטנים מ־$T$ וסכומם שקול ל־$rem$ מודולו $n$. משימתכם היא למצוא את מספר הקבוצות הנאות השונות.

קלט

השורה הראשונה של הקלט מכילה את המספרים השלמים $n$ ו־$rem$, המופרדים ברווח ($0 \le rem < n \le 10^4$). השורה השנייה של הקלט מכילה מספר שלם יחיד $T$ ($1 \le T \le 10^{100\,000}-1$).

פלט

הדפיסו את מספר הקבוצות הנאות השונות. מכיוון שמספר זה עשוי להיות גדול מאוד, יש להדפיס אותו מודולו המספר הראשוני $998\,244\,353$.

דוגמאות

קלט 1

3 2
5

פלט 1

8

קלט 2

1 0
20

פלט 2

1048576

הערה

בדוגמה הראשונה אפשר לכלול את המספרים $0$ ו־$3$ או להשמיטם באופן חופשי, בלי לשנות את השארית. מבין המספרים $\{1,2,4\}$ יש שתי קבוצות נאות: $\{2\}$ ו־$\{1,4\}$. לכן התשובה היא $2 \cdot 2 \cdot 2 = 8$.

בדוגמה השנייה כל תת־קבוצה של $\{0,1,\ldots,19\}$ היא נאה, ולכן התשובה היא $2^{20} = 1\,048\,576$.