בעיה

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.