Рекуррентные последовательности

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

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, B не равно C.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num, misnum (1<= A <= 10, 2 <= B,C <= 10, 1 <= S <= 100, 1 <= F <= 10³, S <= num < misnum <= F). Каждое число вводится с новой строки.

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

Примеры

№	Входные данные	Выходные данные
1	1 2 3 3 46 12 25	120

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

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, A не равно B.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num1, num2 (1<= A,B,C <= 10, 1 <= S <= 100, 1 <= F <= 10³, S >= num1 > num2 >= F). Каждое число вводится с новой строки.

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

Примеры

№	Входные данные	Выходные данные
1	1 3 3 22 2 11 4	369

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь 1
2. увеличь каждый разряд числа на 1

Первая команда увеличивает число на 1, вторая - увеличивает каждый разряд числа на 1, если он не равен 9. 
Например, число 45 с помощью команды 2 превратится в 56, а 49 в 59 (так как младший разряд равен 9 и он остается без изменений).
Программа для Счетовода – это последовательность команд.
Сколько существует программ, которые число S преобразуют в число F? 


Входные данные
Программа получает на вход два числа (каждое число записано в отдельной строке): S и F ( 1 <= S <= 100, 10 <= F <= 1000, S < F). 

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

Примеры

№	Входные данные	Выходные данные
1	26 49	22

Дано натуральное число A > 1. Определите, каким по счету числом Фибоначчи оно является, то есть выведите такое число n, что fn=A. Если A не является числом Фибоначчи, выведите число -1.

Входные данные
Программа получает на вход натуральное число.

Выходные данные
Выведите ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные
1	8	6
2	10	-1

Последовательность Фибоначчи определяется так: \(f_0 = 0, f_1 = 1, ..., f_n = f_{n-1}+f_{n-2}\).

По данному числу n определите n-е число Фибоначчи fn.

Входные данные
Программа получает на вход натуральное число n.

Выходные данные
Выведите ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные
1	6	8