Программа: исполнитель с параметрами команд, обязательное и запрещённое число

Исполнитель Шагомер преобразует целое число, записанное на экране. У исполнителя три команды, которым присвоены номера: 1. Прибавить a 2. Прибавить b 3. Умножить на k Программа для исполнителя — это последовательность команд. Траектория программы — последовательность чисел, получаемых на экране после выполнения каждой команды (исходное число в траекторию не входит, конечное — входит). Напишите программу, которая определяет, сколько существует программ для Шагомера, преобразующих исходное число S в число T, при этом траектория содержит число M и не содержит числа X. Входные данные: одна строка с семью целыми числами S T a b k M X через пробел: 1 ≤ S < T ≤ 2000; 1 ≤ a < b ≤ 10; 2 ≤ k ≤ 5; M = 0 или S < M < T; X = 0 или S < X < T, причём X ≠ M. Значение M = 0 означает, что условия «траектория содержит M» нет, а X = 0 — что нет условия «траектория не содержит X». Выходные данные: одно целое число — количество программ (оно может быть очень большим). Если таких программ нет, выведите 0. Пример. Входные данные:

2 30 1 3 2 10 17

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

14742