Polygon Partitions

Given a regular N-gon, count two kinds of noncrossing dissections: dissections using only triangles and dissections using only quadrilaterals.

Every added segment must connect two vertices, and no two added segments may cross. Cases that differ only by rotation or reflection are still counted as different.

The first line contains an integer N.

• 3 <= N <= 1,000

Because the answers can be large, output each answer modulo 1,000,000,000.

Print the number of dissections using only triangles on the first line. Print the number of dissections using only quadrilaterals on the second line.