Enunț

Deși Trixie este considerată un membru vital al echipei, care își scoate deseori prietenii din bucluc, prințesa poate să fie și neîndemânatică. Transportarea robotului de la baza turnului până în laborator și invers mereu a fost o provocare pentru echipa. Trixie se grăbește să aducă robotul din laborator până la baza turnului. A fost nevoie de un singur pas greșit ca robotul să își inceapă coborârea pe cont propriu. Trixie observă că acesta se lovește de fiecare dintre cele n trepte, de fiecare dată lasând, în urma impactului, un număr de șuruburi. Numărul de șuruburi urmează o regulă fixă. Prima dată lasă în urmă un șurub, apoi tot un șurub, apoi 2 șuruburi, apoi 3 șuruburi, apoi 5 șuruburi, apoi 8 șuruburi ș.a.m.d. Practic numărul de șuruburi de pe treapta(i) = numărul de șuruburi de pe treapta (i - 1) + numărul de șuruburi de pe treapta (i - 2), pentru un i ≥ 3. Se vor da 3 numere naturale : n, m și ct. În funcție de ct, Trixie va avea una din 2 cerințe:

• Pentru ct = 1, să se determine produsul numerelor prime distincte, luate o singură dată, care apar în descompunerea în factori primi a numerelor de șuruburi, de pe trepte separate, mai mici decât 10 * m.
• Pentru ct = 2, să se determine restul împărțirii(%) numărului de șuruburi de pe treapta n la m.

Cerința

Scrieți un program care să citească numerele naturale ct, n, m și să afișeze datele cerute în funcție de ct.

Date de intrare

Programul citește de la tastatură numerele ct, n, m, separate prin spații.

Date de ieșire

Programul va afișa pe ecran:

• Produsul numerelor prime, distincte, luate o singura dată, care sunt divizori ai numerelor de șuruburi mai mici strict ca 10 * m de pe trepte, daca ct = 1.
• Restul împărțirii lui numărului de șuruburi de pe treapta n la m, daca ct = 2.

Restricții și precizări

• ct ∊ {1,2}
• 1 ≤ n ≤ 10^18
• 2 ≤ m ≤ 10^5

Exemplul 1:

Intra

1 5 3

Ieșire

2730

Explicație

Numerele de șuruburi, de pe trepte separate, mai mici decat 3 * 10 sunt : 1, 1, 2, 3, 5, 8, 13, 21. Divizorii primi mai mici ca 21 care divid cel putin un termen al șirului sunt 2, 3, 5, 7 și 13, al căror produs e 2730.

Exemplul 2:

Intra

2 9 7

Ieșire

6

Explicație

Pe treapta 9 sunt 34 șuruburi. 34 % 7 = 6.