Есептің шарты
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=88+3-2-4+8-7-2-4+0+8=88+3+2+4-8-7+2-4-0+8=88+3+2+4-8-7+2-4+0+8=88+3+2-4+8-7+2+4-0-8=88+3+2-4+8-7+2+4+0-8=88-3+2+4-8+7+2+4-0-8=88-3+2+4-8+7+2+4+0-8=88-3+2-4+8+7+2-4-0-8=88-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 түріне түзетілді.