المسألة

JOI-kun طالب في الصف $1$ الابتدائي. يحب JOI-kun عمليتي الجمع والطرح اللتين تعلّمهما للتو كثيراً، وعندما يرى سلسلة من الأرقام مصطفة، فإنه يلعب بتكوين معادلة عن طريق وضع = بين آخر رقمين ($2$)، ووضع + أو - دائماً بين بقية الأرقام المتجاورة. على سبيل المثال، من 8 3 2 4 8 7 2 4 0 8 8 يمكنه تكوين المعادلة 8+3-2-4+8-7-2-4-0+8=8.

بعد تكوين المعادلة، يقوم JOI-kun بحسابها للتحقق مما إذا كانت معادلة صحيحة. ومع ذلك، لا يعرف JOI-kun الأعداد السالبة بعد، ولا يمكنه حساب أعداد تتجاوز $20$. وبالتالي، من بين المعادلات الصحيحة، فإن المعادلات التي تكون فيها جميع الأعداد التي تظهر أثناء الحساب عند تقييم الطرف الأيسر من اليسار إلى اليمين أكبر من أو تساوي $0$ وأقل من أو تساوي $20$ هي فقط المعادلات الصحيحة التي يمكن لـ JOI-kun التحقق منها. على سبيل المثال، 8+3-2-4-8-7+2+4+0+8=8 هي معادلة صحيحة، ولكن بما أن 8+3-2-4-8 الذي يظهر أثناء الحساب هو عدد سالب، فلا يمكن لـ JOI-kun التحقق من صحة هذه المعادلة.

بإعطائك سلسلة من الأرقام كمدخلات، اكتب برنامجاً لإيجاد عدد المعادلات الصحيحة التي يمكن لـ JOI-kun تكوينها والتحقق منها.

المدخلات

يتكون ملف الإدخال من سطرين ($2$). يحتوي السطر $1$ على عدد صحيح $N$ ($3 \le N \le 100$) يمثل عدد الأرقام المصطفة. ويحتوي السطر $2$ على $N$ من الأعداد الصحيحة التي لا تقل عن $0$ ولا تزيد عن $9$، مفصولة بمسافات.

في $60\%$ من بيانات الإدخال المعطاة، لا يتجاوز عدد المعادلات الصحيحة التي يمكن لـ JOI-kun تكوينها والتحقق منها القيمة $2^{31}-1$. كما أنه في جميع بيانات الإدخال المعطاة، لا يتجاوز عدد المعادلات الصحيحة التي يمكن لـ JOI-kun تكوينها والتحقق منها القيمة $2^{63}-1$.

المخرجات

اطبع في سطر واحد ($1$) عدداً صحيحاً يمثل عدد المعادلات الصحيحة التي يمكن لـ JOI-kun تكوينها والتحقق منها.

أمثلة الإدخال والإخراج

مثال الإدخال 1

11
8 3 2 4 8 7 2 4 0 8 8

مثال الإخراج 1

10

مثال الإدخال 2

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

مثال الإخراج 2

7069052760

في مثال الإدخال $1$، يمكن لـ JOI-kun تكوين والتحقق من المعادلات الصحيحة الـ $10$ التالية:

• 8+3-2-4+8-7-2-4-0+8=8
• 8+3-2-4+8-7-2-4+0+8=8
• 8+3+2+4-8-7+2-4-0+8=8
• 8+3+2+4-8-7+2-4+0+8=8
• 8+3+2-4+8-7+2+4-0-8=8
• 8+3+2-4+8-7+2+4+0-8=8
• 8-3+2+4-8+7+2+4-0-8=8
• 8-3+2+4-8+7+2+4+0-8=8
• 8-3+2-4+8+7+2-4-0-8=8
• 8-3+2-4+8+7+2-4+0-8=8

لذلك، نطبع $10$.

في مثال الإدخال $2$، لاحظ أن الإجابة لا تتسع ضمن نطاق عدد صحيح ذي إشارة بحجم $32$ بت.

(إضافة بتاريخ $21$ / $2$ / $2015$) بناءً على ملاحظة من أحد المستخدمين، تبيّن وجود خطأ في المعادلات الواردة في شرح مثال الإدخال $1$. وقد تم تصحيحه الآن. كانت المعادلة رقم $5$ هي 8+3-2-4+8-7+2+4-0-8=8 وتم تصحيحها إلى 8+3+2-4+8-7+2+4-0-8=8. وكذلك كانت المعادلة رقم $6$ هي 8+3-2-4+8-7+2+4+0-8=8 وتم تصحيحها إلى 8+3+2-4+8-7+2+4+0-8=8.