Головоломка
Вы обнаружили странную головоломку которая выглядит как полное бинарное дерево высоты n (имеется n вершин на пути от корня до любого из листов). Вершины дерева пронумерованы следующим образом: корень имеет номер 1, любая вершина x не являющаяся листом, имеет двух детей с номерами 2x (левый сын) и 2x + 1 (правый сын).
Каждая вершина может находиться в одном из двух состояний - 0 или 1. Вы можете изменять состояние вершин, запустив ударную реакцию с любой вершины. Ударная реакция работает следующим образом. Сначала вершина, в которой была запущена сама реакция, изменяет свое состояние на противоположное. Далее, если эта вершина не лист, запускается цепная реакция у ее детей: если состояние вершины было 0 до удара, то реакция запускается у левого сына, иначе у правого сына. Таким образом ударная реакция продолжается по всему пути от стартовой вершины до в точности одного листа.
После запуска ударной реакции в некоторой вершине, необходимо подождать ее завершения, только после чего можно запускать следующую. Каждая вершина может быть стартовой для ударной реакции произвольное количество раз.
Вам заданы начальные состояния всех вершин. Задача состоит в установлении состояний всех вершин в 0, запустив наименьшее количество ударных реакций.
Поскольку количество вершин может быть довольно большим, мы не будем задавать их начальное состояние непосредственно. Все состояния сгенерируем согласно следующего алгоритма. На вход подаются целые числа a, b, c, p и T, где p - простое, b - натуральное. Используя эти числа, сгенерируем последовательность x[i]:
x[1] = a
x[i] = (x[i-1] ∙ b + c) mod p, где i > 1
Для каждой вершины i если x[i] ≥ T, то начальное состояние i-й вершины равно 1, иначе 0.
Входные данные
Единственная строка содержит шесть целых чисел n, a, b, c, p и T (1 ≤ n ≤ 60, 0 ≤ a < p, 1 ≤ b < p, 0 ≤ c < p, 2 ≤ p ≤ 10^6, 0 < T < p). Гарантируется, что p простое.
Выходные данные
Вывести наименьшее количество ударных реакций, необходимых для установления состояний всех вершин в 0.