const
y = 2009;
maxn = 50;
var
n, i, j, s: longint;
c: array[0..maxn, 0..maxn] of longint;
begin
s := 0;
read(n);
c[0, 0] := 1;
for i := 1 to n do
begin
c[i, 0] := 1;
for j := 1 to i - 1 do
c[i, j] := c[i-1, j-1] + c[i-1, j];
c[i, i] := 1;
end;
for i := 0 to n do
s := (s + c[n, i]) mod y;
write(s);
end.
输入:17
输出：487