Задача №112619. Исполнитель Калькулятор-2

Исполнитель Калькулятор работает с целыми числами. Он хранит в памяти одно число и может выполнять с ним арифметические действия. Программа для Калькулятора – это последовательность команд, в которой могут использоваться только разрешённые команды Калькулятора (неограниченное число раз). Определите количество различных программ, которые преобразуют число A в число B .

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

Первая строка содержит два натуральных числа: A и B . Гарантируется, что 1 ≤ A , B ≤ 4000 . Во второй строке записано натуральное число K – количество разрешённых команд Калькулятора. В следующих K строках записаны эти команды в формате:

<знак операции><число>

В командах могут использоваться два набора операций: 1) сложение (+) и умножение (*); или 2) вычитание (-) и деление (/).

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

Программа должна вывести одно целое число: количество различных программ, которые преобразуют число A в число B . Гарантируется, что искомое число конечно и не превышает 2 31 - 1 .

Примеры
Входные данные
1 25
2
+1
*3
Выходные данные
18
Сдать: для сдачи задач необходимо войти в систему