A. 后缀表达式求值

Problem A. 后缀表达式求值

题目英文名：calc

时空限制：1s/256MB

题目描述：

每个四则运算算式都可以被写成一棵算式二叉树，算式二叉树的叶子节点放的是表达式中的数值，其他节点（保证它们一定有两个子节点）则放着算式中的运算符。

算式二叉树上，每个节点的值是：

• 如果这个节点上写的是数字，那么这个数字就是它的值。

• 否则（如果这个节点上写的是运算符），那么它一定有两个子节点；如果左子节点的值是，右子节点的值是，那么这个节点的值是。

算式二叉树的值（也是它所代表的表达式的值）就是它的根节点的值。

为了避免除零等情况出现，本题中的运算符只会是的一种，其中表示乘法。

为了方便输入，所有存放数值的节点存放的都是之间的整数，因此输入中每一位数字都代表一个节点。

算式二叉树的后序遍历是一个字符串：

• 如果这个算式二叉树是空的，那么它的后序遍历也是空串。

• 否则，它的后续遍历是：根节点左子树的后序遍历，加上根节点右子树的后续遍历，加上代表根节点上的数字或运算符的字符。

现在给出一个算式二叉树的后序遍历，请你求出：

1. 有多少种可能的算式二叉树。

2. 所有可能的算式二叉树的值的和。

由于出题人不想写高精度，两问输出的值都对取模。

输入格式：

输入一个字符串，表示算式二叉树的后序遍历。

输出格式：

第一行输出：有多少种可能的算式二叉树。

第二行输出：所有可能的算式二叉树的值的和。

两行输出的数都对取模。

注意，取模后的答案范围为，例如第二问的答案如果为，你应该输出。

样例输入：

43+43-*

样例输出：

1
7

样例解释：

唯一的一种可能的二叉树如下：

     *
   /   \
  +     -
 / \   / \
4   3 4   3

它的值是。

数据范围：

对于40%的数据：字符串长度不超过

对于100%的数据：字符串长度不超过，字符只有可能是之一