Виконавець Калькулятор працює з цілими числами. Він зберігає у пам'яті одне число і може виконувати із нею арифметичні дії. Програма для Калькулятора – це послідовність команд, в якій можуть використовуватись лише дозволені команди Калькулятора (необмежену кількість разів).

Визначте кількість різних програм, які перетворюють число \(A\) на число \(B\) .

Формат вхідних даних

Перший рядок містить два натуральні числа: \(A\) і \(B\) . Гарантується, що \(1 \le A , B \le 4000\) .

У другому рядку записано натуральне число \(K\) – кількість дозволених команд калькулятора.

У наступних \(K\) рядках записані ці команди у форматі:

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

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

Формат вихідних даних

Програма повинна вивести одне ціле число: кількість різних програм, які перетворюють число \(A\) на число \(B\) . Гарантується, що число, що шукається, звичайно і не перевищує \(2^{31} - 1\) .

Приклад вхідних даних

1 25
2
+1
*3

Приклад вихідних даних

18