解题思路

设字符串为 $s$ ，长度为 $n$ 。

在相邻两个数字之间，一共有 $n-1$ 个位置，每个位置都只有 $2$ 种选择：

题目内容

给定一个仅由数字 $1$ 到 $9$ 组成的字符串。你可以在字符串 $s$ 中任意两个相邻的数字字符之间插入加号运算符 ‘ $+$ ’。每对相邻数字可选择插入一个加号或不插入加号。

通过不同的插入方式，可以构成多种不同的数学表达式。例如，对于字符串 " $1234$ "，以下是全部的合法表达式：

然而，像 " $1+2++3+4$ " 这样的插入方式是不合法的，因为在 ‘ $2$ ’ 和 ‘ $3$ ’ 之间插入了多个加号。

对于给定的字符串。，请计算所有通过合法插入‘ $+$ ’，构成的数学表达式中，有多少个表达式的计算结果是一个质数。

【名词解释】

在一行上输入一个长度为 $1≤len(s)≤15$ ，仅由数字字符 ‘ $1$ ’ 到 ‘ $9$ ’ 组成的字符串 $s$ 。

输出一个整数，代表计算结果为质数的合法表达式的数量。

输入

输出

说明

在这个样例中，一共有 $8$ 种可能的表达式，其中以下三种表达式的结果为质数：

因此，结果为质数的表达式共有 $3$ 个。

输入

输出

说明

在这个样例中，所有合法的表达式及其计算结果如下：

没有表达式的结果是质数，因此输出 $0$ 。