Cerința
Dorel tocmai a învățat la școală despre permutări. El a reținut faptul că n
persoane pot fi aranjate pe n
locuri în n!
moduri, unde \( n!=1\cdot 2\cdot 3\cdot … \cdot n\). Pentru a vă pune pe voi la încercare Dorel mai alege un număr p
și vă întreabă în câte moduri putem aranja n
persoane numerotate de la 1
la n
pe n
locuri, numerotate şi ele de la 1
la n
, astfel încât suma dintre numărul persoanei și numărul locului să fie divizibilă cu p
?
Date de intrare
Programul citește de la tastatură numerele n
și p
, separate prin spații.
Date de ieșire
Programul va afișa pe ecran numărul m
, reprezentând numărul de moduri cerut. Deoarece acest număr ar putea fi foarte mare, rezultatul se va afișa modulo 100019
.
Restricții și precizări
1 ≤ p ≤ n ≤ 100.000
- locurile și persoanele sunt numerotate de la
1
lan
Exemplu:
Intrare
8 4
Ieșire
16
Explicație
Avem 8
persoane și 8
locuri. Persoanele 1
și 5
se pot așeza pe locurile 3
și 7
în 2!
moduri, persoanele 2
și 6
pe locurile 2
și 6
în 2!
moduri, persoanele 3
și 7
pe locurile 1
și 5
în 2!
moduri, iar persoanele 4
și 8
pe locurile 4
și 8
în 2!
moduri. În total vom avea 2
4
=16
moduri de aranjare.