Головоломка
Ви знайшли цікаву головоломку, що виглядає як повне бінарне дерево висоти 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.