لديك متتالية من الرقمين $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$$