// Задача "MP3-плеер"
// 4-я Интернет-олимпиада сезона 2009-2010, усложненный уровень
// Автор задачи: Маским Носенко, nosenkomax@gmail.com
// Автор решения: Владимир Ульянцев, ulyantsev@rain.ifmo.ru

uses
	sysutils;
type
	int = longint;
const
	MAXN = 2000;
	MAXM = 1000000000;
var
	n, m, i, j : int;
	old, new : array [-1..MAXN + 1] of int64;

begin
	reset(input, 'mp3.in');
	rewrite(output, 'mp3.out');

	read(n, m);
	assert((1 <= n) and (n <= MAXN) and (1 <= m) and (m <= MAXM));
	
	fillchar(old, sizeof(old), 0);
	fillchar(new, sizeof(new), 0);

	old[0] := 1;
	
	for i := 1 to n - 1 do begin
		for j := 0 to i do begin
			new[j] := old[j - 1] + (j + 1) * old[j + 1] + (i - j) * old[j];
		end;

		for j := 0 to n do begin
			old[j] := new[j] mod m;
			//write(old[j], ' ');
		end;
		//writeln;
	end;
	
	writeln(old[0]);
end.
