== include(page="template/taskheader" task_id="jap2") ==
Bercea a primit sarcină de la mentorul său să facă o poveste frumoasă pentru următoarea problemă care va fi dată la Algoreea 2010. Înainte de asta, Bercea ar vrea să ştie cum se rezolvă şi vă cere ajutorul în schimbul unui cadou pe facebook. Problema sună aşa:
Bercea a primit sarcină de la mentorul său să facă o poveste frumoasă pentru următoarea problemă care va fi dată la Algoreea 2010. Înainte de asta, Bercea ar vrea să ştie cum se rezolvă şi vă cere ajutorul în schimbul unui cadou pe Facebook. Problema sună aşa:
Se dă un număr prim $P$ mai mic sau egal cu $100 007$ şi ni se pun $Q$ intrebări de forma „Cu cât este egal Combinări de $A$ luate câte $B$ modulo $P$?”
Fiind dat un număr prim $P$ mai mic sau egal cu $100 007$ să se răspundă rapid la $Q$ intrebări de forma „Cu cât este egal (Combinări de $A$ luate câte $B$) modulo $P$?”
h2. Date de intrare
Pe prima linie a fişierului de intrare $jap2.in$ se vor afla două
Pe prima linie a fişierului de intrare $jap2.in$ se vor afla două numere naturale $P$ şi $Q$ cu semnificaţiile din enunţ. Pe fiecare din următoarele $Q$ linii se vor afla câte două numere naturale $A$ şi $B$ reprezentând o întrebare.
h2. Date de ieşire
În fişierul de ieşire $jap2.out$ ...
În fişierul de ieşire $jap2.out$ se va afişa pe linia $i$ răspunsul la cea de $i$-a întrebare.
h2. Restricţii şi precizări
* $1 ≤ P ≤ 100 007$, $P$ prim.
* $90 000 ≤ Q ≤ 100 000$.
* $1 ≤ Q ≤ 100 000$.
* $1 ≤ B ≤ A ≤ 10^18^$.
* Combinări de $A$ luate câte $B$ este egal cu $^A!^/{~B!*(A-B)!~}$, unde $A! = 1 * 2 * 3 * ... * A$.
* Pentru $10%$ din teste, $A, B ≤ 2 000$
* Pentru $50%$ din teste, $A, B ≤ 1 000 000 000$
* Pentru $70%$ din teste, $P ≤ 4 000$
h2. Exemplu
table(example). |_. jap2.in |_. jap2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 13 10
3 3
5 3
3 2
13 1
7 4
10 3
10 8
3 2
5 5
7 4
| 1
10
3
0
9
3
6
3
1
9
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="jap2") ==
