Crisan Daniela Alexandra (URA) RAU-Gigel își sărbătorește ziua de naștere și dorește să împartă bomboane colegilor săi de la cercul de informatică. Sărbătoritul speră că are un număr suficient de bomboane și ar vrea ca fiecare coleg să primească cel puțin una.
RAU-Gigel nu își amintește exact câți colegi are, dar își amintește un detaliu important: la lecția despre divizibilitate, profesorul le-a cerut elevilor să se așeze într-un șir indian, pe poziții numerotate de la 1 în sus, respectând regula ca toți elevii să ocupe poziții coprime cu Q. RAU-Gigel, fiind ultimul în șir, a primit (ce surpriză!) un număr de ordine egal cu numărul său norocos.
Cerința
Date fiind numerele Q reprezentând constanta din enunț, N numărul norocos al lui RAU-Gigel, și M numărul total de bomboane disponibile, să se răspundă la întrebările:
1. Câți elevi sunt la cercul de informatică? Știm că RAU-Gigel și colegii lui nu lipsesc niciodată de la întâlnirile cercului.
2. Îi ajung lui RAU-Gigel bomboanele pentru toți colegii? Dacă da, să se afle în cate moduri poate împărți toate cele M bomboane colegilor săi, astfel încât fiecare coleg să primească cel puțin o bomboană. RAU-Gigel, deși tare pofticios, nu gustă nici măcar una.
Date de intrare
Fișierul de intrare bomboane.in va conține pe prima linie trei numere naturale nenule Q, N și M, separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire bomboane.out va conține pe prima linie numărul de elevi de la cercul de informatică, iar pe a doua linie numărul de moduri în care RAU-Gigel poate împărți bomboanele colegilor săi, modulo 10^9+7, dacă are suficiente bomboane pentru colegi, respectiv NU, în caz contrar.
Restricții și precizări
- 2 ≤ Q, N, M ≤ \( {10}^{6} \)
- Pentru teste în valoare de
10de puncte:Q = 2,N ≤ 100,Meste egal cu numărul de colegi ai lui RAU-Gigel - Pentru alte teste în valoare de
10de puncte:Q = 30,N ≤ 100,Meste egal cu numărul de colegi ai lui RAU-Gigel - Pentru alte teste în valoare de
10de puncte:Q,Nfără restricții suplimentare,Meste egal cu numărul de colegi ai lui RAU-Gigel - Pentru alte teste în valoare de
20de puncte:Q≤30,Nfără restricții suplimentare,Meste cu1mai mare decât numărul de colegi ai lui RAU-Gigel - Pentru alte teste în valoare de
10de puncte:Q≤30,Meste mai mic decât numărul de colegi ai lui RAU-Gigel - Pentru restul testelor se păstrează restricțiile inițiale din enunț
- Se garantează că
Neste coprim cuQ
Exemplul 1:
bomboane.in
30 23 7
bomboane.out
7 6
Explicație
Avem Q=30, N=23, M=7. Numărul norocos al lui RAU-Gigel este 23, deci la exercițiul propus la cerc, elevii au stat în șir indian pe pozițiile: 1,7,11,13,17,19,23. Sunt, așadar, 7 elevi.
Cele 7 bomboane pot fi împărțite în 6 moduri astfel:
- primul coleg poate primi 2 bomboane, iar restul colegilor câte una;
- cel de-al doilea coleg poate primi 2 bomboane, iar restul colegilor câte una;
- șamd.
Exemplul 2:
bomboane.in
30 23 5
bomboane.out
7 NU
Explicație
Sunt 7 elevi la cercul de informatică, iar cele 5 bomboane nu sunt suficiente pentru colegii lui RAU-Gigel.