Fișierul intrare/ieșire	palat.in, palat.out	Sursă	Concurs Nerdvana
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.15 sec	Limită de memorie	524288 KB
Scorul tău	N/A	Dificultate	2.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Palat (clasele 9-12)

Un palat are n² camere, toate de dimensiuni diferite. Pentru fiecare 1 ≤ i ≤ n și 1 ≤ j ≤ n există exact o cameră de i × j m². Figura arată cele 16 camere ale palatului pentru n=4.

Regele dorește să paveze toate camerele cu dale. În fiecare cameră independent, regele alege dale pătrate, toate egale ca mărime, cît mai mari posibil astfel încît să poată pava camera doar cu dale întregi. De exemplu, o cameră de dimensiuni 3 × 4 poate fi pavată cu 12 dale de dimensiuni 1 × 1, iar o cameră de dimensiuni 2 × 4 poate fi pavată cu 2 dale de dimensiuni 2 × 2.

Calculați numărul de dale necesare pentru a pava toate camerele. Întrucît această valoare poate fi mare, calculați răspunsul modulo o valoare m dată la intrare.

Date de intrare

Fișierul de intrare palat.in conține pe prima linie numerele n și m.

Date de ieșire

În fișierul de ieșire palat.out afișați numărul de dale necesare, modulo m.

Restricții

• 1 ≤ n ≤ 1.000.000
• 2 ≤ m ≤ 1.000.000.000
• Testele nu sînt grupate.

Exemplu

Explicație

Conform figurii, sînt necesare (1 + 2 + 3 + 4) + (2 + 1 + 6 + 2) + (3 + 6 + 1 + 12) + (4 + 2 + 12 + 1) = 62 de dale. Răspunsul este 62 mod 40 = 22.