Qara və ağ

Marti, zebraların əksəriyyətlə ağ fonda qara zolaqlara sahib olduğuna inanır. Qara fonda ağ zolaqlı zebraların nadir olduğunu sübut etmək üçün Marti, Aleksə maraqlı bir oyun təklif edir.

Onlar hazırda bir təpədən otlağa baxırlar. Otlaq sonsuz bir dama taxtası kimi təsəvvür edilə bilər və hər bir hüceyrədə bir zebra dayanır. Oyun n gedişdən ibarətdir, gedişlər 1-dən n-ə qədər nömrələnmişdir: i-ci gedişdə Marti, tərəfi i + 1 olan kvadrat bir otlaq sahəsi seçir. Bu sahədə yalnız bir hüceyrədə qara fonda ağ zolaqlı zebra dayanır, qalan bütün zebralar isə ağ fonda qara zolaqlıdır. Aleksin vəzifəsi, qara fonda ağ zolaqlı zebranın hansı hüceyrədə olduğunu tapmaqdır.

Marti hər dəfə əvvəllər seçilmiş heç bir kvadratla kəsişməyən bir kvadrat seçir. Aleks isə ağ fonda qara zolaqlı zebraları qara fonda ağ zolaqlı zebralardan ayırmağı bacarmadığı üçün, hər seçimi təsadüfi olaraq, bərabər ehtimalla göstərilən kvadratdakı təsadüfi bir hüceyrəni seçərək edir. Aleksin heç bir qara fonda ağ zolaqlı zebranı tapmama ehtimalını hesablayın.

Giriş məlumatları

Bir tam ədəd n (1 ≤ n ≤ 10^18) - oyundakı gedişlərin sayı.

Çıxış məlumatları

İki tam ədəd p və q çıxarın, boşluqla ayrılmış sadələşdirilməyən kəsrin surəti və məxrəci, axtarılan ehtimala bərabərdir.

Nümunə

Nümunədə, birinci gedişdə Aleks Martinin seçdiyi zebranı p[1] = 3 / 4 ehtimalla tapmayacaq, ikinci gedişdə isə p[2] = 8 / 9 ehtimalla. Buna görə də, Aleksin heç bir qara fonda ağ zolaqlı zebranı tapmama ehtimalı p = 2 / 3 bərabərdir.