Hide

Problem C
Doubleplusgood

/problems/doubleplusgood/file/statement/en/img-0001.jpg
Image by Keith Gentry (Shutterstock), Used under license

In many programming languages, the “plus” symbol (‘+’) has at least two standard meanings:

  • arithmetic addition

  • string concatenation

Inspired by the old adage, “Variety is the spice of life,” the designers of the Doubleplusgood (DPG) language (launched to great fanfare in 1984 by the Ministry of Truth Tables) decided that, in certain contexts, the meaning of the plus symbol would be decided dynamically and randomly at run time. In particular, for expressions consisting of alternating integers and plus symbols, every time the same program is executed, the meaning of each plus symbol is randomly chosen to be either addition or string concatenation. It follows that a single expression of this form can potentially evaluate to many different integers. For example, consider

\[ 1+9+8+4 \]

For clarity, we’ll use $\boxplus $ to denote a plus symbol that the DPG runtime environment decides to interpret as string concatenation, which, it is important to note, has higher precedence than addition in DPG. Then $1+9+8+4$ can evaluate to $7$ distinct values:

\begin{align*} 1\boxplus 9 \boxplus 8 \boxplus 4 \, & =\, 1984\\ 1 \boxplus 9 \boxplus 8 + 4 \, & =\, 198 + 4 \, =\, 202\\ 1 \boxplus 9 + 8 \boxplus 4 \, & =\, 19 + 84 \, =\, 103\\ 1 \boxplus 9 + 8 + 4 \, & =\, 19 + 8 + 4 \, =\, 31\\ 1 + 9 \boxplus 8 \boxplus 4 \, & =\, 1 + 984 \, =\, 985\\ 1 + 9 \boxplus 8 + 4 \, & =\, 1 + 98 + 4 \, =\, 103\\ 1 + 9 + 8 \boxplus 4 \, & =\, 1 + 9 + 84 \, =\, 94\\ 1 + 9 + 8 + 4 \, & =\, 22 \end{align*}

(Note that $103$ was formed in two different ways.) Given a sequence of alternating integers and plus symbols, your task is to determine the number of distinct integers to which the expression can evaluate.

Input

The input is a single line consisting of alternating positive integers and plus symbols. The line begins and ends with a positive integer, and is guaranteed to contain at least one plus symbol. The maximum number of digits in the input is $18$.

Output

Output the number of distinct integers to which the input expression can evaluate in DPG.

Sample Input 1 Sample Output 1
1+9+8+4
7
Sample Input 2 Sample Output 2
1+2+3+4+5+6+7+8+9
188
Sample Input 3 Sample Output 3
42+42+8+8+8+1+10+100
100

Please log in to submit a solution to this problem

Log in