Într-o ţară există N oraşe numerotate de la 1 la N şi un număr oarecare de străzi unidirecţionale ce leagă perechi ordonate de oraşe distincte. Analizând sistemul stradal din ţara respectivă Vasile a observat că există cel puţin un şir de oraşe x₁, x₂, ... x_k (k>=3) cu x₁=x_k şi cu proprietatea că există o stradă de la x_i la x_i+1 pentru orice 1<=i<k. Curios din fire Vasile se întreabă acum câte sisteme stradale distincte cu această proprietate există. Două sisteme stradale sunt distincte dacă şi numai dacă există două oraşe x şi y astfel încât în unul dintre sisteme să existe o stradă de la x la y, iar în celălalt nu.

Cerinţă

Scrieţi un program care să îl ajute pe Vasile să determine numărul căutat modulo P.

Date de intrare

Fişierul de intrare circuit.in conţine pe prima linie numerele naturale N şi P separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire circuit.out va conţine o singură linie pe care va fi afişat numărul căutat modulo P.

Restricţii

• 1 ≤ N ≤ 1500
• 2 ≤ P ≤ 32000
• Între două oraşe x şi y poate exista cel mult o stradă de la x la y.
• Pentru un număr de teste în valoare de 50 de puncte 1 ≤ N ≤ 300.

Exemple

circuit.in	circuit.out	Explicaţie
2 100	1	Singurul sistem stradal posibil este cel în care există o stradă de la oraşul 1 la oraşul 2 şi invers.
circuit.in	circuit.out	Explicaţie
4 9999	3553	Sunt prea multe sisteme stradale pentru a le enumera.

Vlad Tudose

Facultatea de Informatica Iaşi