给出个顶点，你可以将这个顶点构成一棵树，若这棵树恰好只有三个分叉，那么我们称这种树为树。 现在给出个顶点，请你求出可以由这个顶点构建的树有多少种？

输入描述:

输入的第一行给出顶点的个数。

输出描述:

由这个顶点构建的树有多少种？，结果对取模。输出取模后的结果。