Задачи
Наибольшая возрастающая подпоследовательность
Наибольшая возрастающая подпоследовательность
Рассмотрим последовательность \textbf{x_i}, заданную следующими соотношениями:
\textbf{x_0 = a + b}, \textbf{x_1 = a -- b},
\textbf{x_i = (a·x_\{i \}_\{- 2\} + b·x_\{i \}_\{- 1\}) mod m, i > 1}
Для заданного натурального \textbf{n} найти длину наибольшей возрастающей подпоследовательности \textbf{x_0}, \textbf{x_1}, \textbf{x_2}, …, \textbf{x_n}.
\InputFile
Каждый тест состоит из одной строки, содержащей четыре натуральных числа \textbf{a}, \textbf{b}, \textbf{m}, \textbf{n} (\textbf{a} ≥ \textbf{b}, \textbf{1} ≤ \textbf{a}, \textbf{b}, \textbf{m}, \textbf{n} ≤ \textbf{10^6}). Количество тестовых случаев в одном тесте не превышает \textbf{20}.
\OutputFile
Для каждого теста в отдельной строке вывести длину наибольшей возрастающей подпоследовательности.
Входные данные #1
3 1 20 10 5 2 1000 2000
Выходные данные #1
5 70