式を左から見ていったときに、現在の状態を \(A+B*C\) または \(A+B*\) という風に持つことを考えます。

\(A+B*C\) の状態で、

次に数字 \(d\) が来た場合は、\(A+B*(10*C+d)\) という風に更新できます。

次に文字 \(+\) が来た場合は、\((A+B*C)+1*\) という風に更新できます。

次に文字 \(*\) が来た場合は、\(A+(B*C)*\) という風に更新できます。

\(A+B*\) の状態で、

次に数字 \(d\) が来た場合は、 \(A+B*d\) という風に更新できます。

そこで、 \(i\) 文字目まで見た時の \(A+B*C\) の状態の数を \(N_i\) 、この状態全ての \(A,B,B*C\) の総和をそれぞれ \(A_i,B_i,D_i\) とし、 \(A+B*\) の状態の数を \(N_i^*\)、この状態全ての \(A,B\) の総和をそれぞれ \(A_i^*,B_i^*\) とすると、\(N_{i+1},A_{i+1},B_{i+1},D_{i+1},N_{i+1}^*A_{i+1}^*,B_{i+1}^*\) が \(N_i,A_i,B_i,D_i,N_i^*,A_i^*,B_i^*\) の線形和で表せるようになります。

したがって行列累乗を用いることで \(N_N,A_N,B_N,D_N,N_N^*,A_N^*,B_N^*\) を求められ、この問題を解くことができます。

時間計算量は \(O(logN)\) です。