405852: GYM102135 E Equation

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Equationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string s consisting only of digits '1'-'9', characters 'a'-'z', '*' and '=' representing the equation. The equation contains only multiplication operations (symbol '*'), positive integers less than 10 and unknown variables. Variables can only be located on the left side of the equation, may occur more than once, and their names are lowercase letters of the English alphabet.

If, instead of unknown variables, you substitute some positive integers so that the result of operations on the left side of the equation equals to the result on the right side, then this set of numbers is called the solution of this equation.

You need to determine how many solutions this equation has. Two solutions are considered different if there is at least one variable present in the equation, the value of which is different.

Input

You are given a single string s (|s| ≤ 1 000) — the original equation. The string has exactly one character '='.

It is guaranteed that at least one unknown variable is present in the equation.

Output

In a single line print one integer — the number of solutions of this equation modulo 109 + 7.

Print '-1' if the equation has an infinite number of solutions.

ExamplesInput
a*b=4*2
Output
4
Input
x*y*1=7*9*8*8
Output
42
Note

All solutions for the equation from the first example:

  1. a = 1, b = 8
  2. a = 2, b = 4
  3. a = 4, b = 2
  4. a = 8, b = 1

加入题单

上一题 下一题 算法标签: