题目描述

在网格中取一个N x 1的矩形，并把它当作一个无向图。这个图有2(N+1)个顶点，有3(N-1)+4条边。这个图有多少个生成树？

输入格式

读入一个数N。1<=N<=1000。

样例数据

input

1

output

4

数据规模与约定

时间限制：$1 text {s}$

空间限制：$256 text {MB}$

注：

由于结果可能很大，你只需要输出这个答案mod 12345的值。