Başsındırıcı
Siz maraqlı bir tapmaca ilə qarşılaşdınız. Bu tapmaca tam binar ağacın n hündürlüyünə malikdir, yəni kökdən hər hansı bir yarpağa qədər olan yolda n zirvə var. Ağacın zirvələri belə nömrələnir: kök 1 nömrəsinə malikdir və yarpaq olmayan hər hansı bir zirvə x üçün iki övlad var: 2x (sol oğul) və 2x + 1 (sağ oğul).
Hər bir zirvə iki vəziyyətdən birində ola bilər: 0 və ya 1. Siz zirvələrin vəziyyətini dəyişdirə bilərsiniz, istənilən zirvədən zərbə reaksiyası başladaraq. Zərbə reaksiyası belə işləyir: əvvəlcə reaksiyanın başladığı zirvə öz vəziyyətini əksinə dəyişir. Əgər bu zirvə yarpaq deyilsə, onun övladlarında zəncirvari reaksiya başlayır: əgər zirvənin vəziyyəti zərbədən əvvəl 0 idisə, reaksiya sol oğulda, əks halda sağ oğulda başlayır. Beləliklə, zərbə reaksiyası başlanğıc zirvədən dəqiq bir yarpağa qədər olan bütün yolda davam edir.
Hər hansı bir zirvədə zərbə reaksiyası başladıqdan sonra onun tamamlanmasını gözləmək lazımdır və yalnız bundan sonra növbəti reaksiyanı başlatmaq olar. Hər bir zirvə zərbə reaksiyasının başlanğıcı üçün istənilən sayda istifadə edilə bilər.
Sizə bütün zirvələrin başlanğıc vəziyyətləri verilir. Məqsəd, ən az sayda zərbə reaksiyası başlatmaqla bütün zirvələrin vəziyyətlərini 0-a gətirməkdir.
Zirvələrin sayı kifayət qədər böyük ola biləcəyi üçün, biz onların başlanğıc vəziyyətini birbaşa verməyəcəyik. Bütün vəziyyətləri aşağıdakı alqoritmə uyğun olaraq yaradacağıq. Giriş olaraq tam ədədlər a, b, c, p və T verilir, burada p - sadə, b - təbii ədəddir. Bu ədədləri istifadə edərək, x[i] ardıcıllığını yaradacağıq:
x[1] = a
x[i] = (x[i-1] ∙ b + c) mod p, burada i > 1
Hər bir zirvə i üçün əgər x[i] ≥ T, onda i-ci zirvənin başlanğıc vəziyyəti 1-ə bərabərdir, əks halda 0.
Giriş məlumatları
Yeganə sətir altı tam ədəd n, a, b, c, p və T (1 ≤ n ≤ 60, 0 ≤ a < p, 1 ≤ b < p, 0 ≤ c < p, 2 ≤ p ≤ 10^6, 0 < T < p) ehtiva edir. p-nin sadə olduğu təmin edilir.
Çıxış məlumatları
Bütün zirvələrin vəziyyətlərini 0-a gətirmək üçün lazım olan ən az zərbə reaksiyalarının sayını çıxarın.