Задача . Счетовод - 4

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. возведи в квадрат
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 10³)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

№	Входные данные	Выходные данные
1	1 2 2 38	266