E. Уравнение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка s состоящая только из цифр «1»-«9», символов «a»-«z», «*» и «=» представляющая из себя уравнение. В уравнении присутствуют только операции умножения (символ «*»), целые положительные числа меньшие 10, а также неизвестные переменные. Переменные могут находиться только по левую сторону уравнения, могут встречаться несколько раз, а их имена являются строчными буквами латинского алфавита.

Если вместо неизвестных переменных подставить некотороые целые положительные числа так, что результат выполнения операций левой части уравнения совпадет с результатом правой, то такой набор чисел называется решением данного уравнения.

Определите, сколько всего решений существует у данного уравнения. Два решения считаются различными, если найдется хотя бы одна присутсвующая в уравнении переменная, значение которой отличается.

Входные данные

Вам дана единственная строка s (|s| ≤ 1 000) — исходное уравнение. В строке присутсвует ровно один символ «=».

Гарантируется, что в уравнении присутсвует как минимум одна неизвестная переменная.

Выходные данные

В единственной строке выведите одно целое число — количество решений данного уравнения по модулю 109 + 7.

Выведите «-1», если уравнение имеет бесконечное количество решений.

Примеры
Входные данные
a*b=4*2
Выходные данные
4
Входные данные
x*y*1=7*9*8*8
Выходные данные
42
Примечание

Все решения для уравнения из первого примера:

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