405852: GYM102135 E Equation

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.

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.

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

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

a*b=4*2

4

x*y*1=7*9*8*8

42

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