Есептің шарты

JOI-кун бастауыш мектептің $1$-ші сыныбында оқиды. JOI-кун жаңа ғана үйренген қосу мен азайту амалдарын өте жақсы көреді, сондықтан тізіліп тұрған цифрларды көрсе, соңғы $2$ цифрдың арасына = белгісін қойып, ал қалған көршілес цифрлардың арасына міндетті түрде + немесе - белгісін қойып, теңдік құрастырып ойнайды. Мысалы, 8 3 2 4 8 7 2 4 0 8 8 тізбегінен 8+3-2-4+8-7-2-4-0+8=8 теңдігін құрастыруға болады.

JOI-кун теңдікті құрастырғаннан кейін оның дұрыс теңдік екенін есептеп тексереді. Алайда JOI-кун әлі теріс сандарды білмейді және $20$-дан асатын сандармен есептеу жүргізе алмайды. Сондықтан дұрыс теңдіктердің ішінде сол жақ бөлігін солдан оңға қарай есептегенде есептеу барысында пайда болатын барлық сандар $0$ мен $20$ аралығында (қоса алғанда) болатын теңдіктер ғана JOI-кун тексере алатын дұрыс теңдіктер болып табылады. Мысалы, 8+3-2-4-8-7+2+4+0+8=8 — дұрыс теңдік, бірақ есептеу барысында кездесетін 8+3-2-4-8 мәні теріс сан болғандықтан, JOI-кун бұл теңдіктің дұрыс-бұрыстығын тексере алмайды.

Кіріс деректері ретінде цифрлар тізбегі берілгенде, JOI-кун құрастырып, тексере алатын дұрыс теңдіктердің санын табатын программа жазыңыз.

Кіріс деректері

Кіріс файлы $2$ жолдан тұрады. $1$-ші жолда тізілген цифрлар санын білдіретін бүтін сан $N$ ($3 \le N \le 100$) жазылған. $2$-ші жолда бос орын арқылы бөлінген $0$ мен $9$ аралығындағы (қоса алғанда) $N$ бүтін сан жазылған.

Берілген кіріс деректерінің $60\%$-ында JOI-кун құрастырып, тексере алатын дұрыс теңдіктер саны $2^{31}-1$ шамасынан аспайды. Сондай-ақ, барлық берілген кіріс деректерінде JOI-кун құрастырып, тексере алатын дұрыс теңдіктер саны $2^{63}-1$ шамасынан аспайды.

Шығыс деректері

$1$ жолда JOI-кун құрастырып, тексере алатын дұрыс теңдіктердің санын білдіретін бүтін санды шығарыңыз.

Кіріс және шығыс мысалдары

Кіріс мысалы 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-кун келесі $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$ биттік таңбалы бүтін сандар диапазонына сыймайтынына назар аударыңыз.

($2015$ жылғы $2$ айдың $21$ күні қосылды) Пайдаланушының ескертуі бойынша Кіріс мысалы $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 түріне түзетілді.