נתונה לכם סדרה של הספרות $1$ ו-$2$. בצעד אחד אפשר:
- להכניס $1$ למקום הנמצא מימין לכל שאר הספרות $1$ (או לכל מקום אם אין ספרות $1$).
- להפוך כל $2$ ל-$1$, אם אין ספרות $1$ מימין ל-$2$ הזה.
- למחוק את ה-$1$ הימני ביותר (שימו לב שפעולה זו הפוכה לפעולה 1).
- להפוך את ה-$1$ הימני ביותר ל-$2$ (שימו לב שפעולה זו הפוכה לפעולה 2).
למשל, אפשר לקבל את הסדרות הבאות בצעד אחד מהסדרה 11212122:
- באמצעות פעולה 1:
112121122,112121212,112121221. - באמצעות פעולה 2:
11212112,11212121. - באמצעות פעולה 3:
1121222. - באמצעות פעולה 4:
11212222.
עליכם לחשב את מספר הדרכים להפוך סדרה של בדיוק $a$ ספרות $2$ לסדרה של בדיוק $b$ ספרות $2$, באמצעות בדיוק $t$ פעולות.
קלט
השורה היחידה של הקלט מכילה שלושה מספרים שלמים $a$, $b$ ו-$t$ ($0 \le a,b,t \le 10^6$).
פלט
הדפיסו את מספר הדרכים לקבל סדרה של $b$ ספרות $2$ מתוך סדרה של $a$ ספרות $2$ בבדיוק $t$ צעדים. מכיוון שמספר זה עשוי להיות גדול מאוד, הדפיסו אותו מודולו המספר הראשוני $998\,244\,353$.
דוגמאות
קלט 1
0 0 4
פלט 1
3
קלט 2
1 4 6
פלט 2
60
הערה
בדוגמה הראשונה עליכם לקבל סדרה ריקה מתוך סדרה ריקה ב-4 צעדים. הדרכים לעשות זאת הן ($\varepsilon$ מציין סדרה ריקה):
$$\varepsilon \to 1 \to \varepsilon \to 1 \to \varepsilon$$
$$\varepsilon \to 1 \to 11 \to 1 \to \varepsilon$$
$$\varepsilon \to 1 \to 2 \to 1 \to \varepsilon$$