题目描述

平面直角坐标系中有 $\frac{n(n+1)}{2}$ 个点，在直线 $x=i(1\leq i\leq n)$ 上分布着 $i$ 个点，其中第 $j$ 个点位于坐标 $(i,j)$。

举个例子，当 $n=4$ 时，这些点长这样：

4          o

3       o  o

2    o  o  o

1 o  o  o  o
  1  2  3  4

现在 Pdw 想要在这些点之间连满足如下条件的无向边：

• 对于位于坐标 $(i,j)(1\leq i<n,1\leq j\leq i)$ 的点来说，它可以选择是否向 $(i+1,j)$ 或者 $(i+1,j+1)$ 连边（可以选择都连，但不能选择都不连）。连边时必须保证这条边的两端都是上一步骤中生成的点。

举个例子，当 $n=4$ 时，一个合法的连边方案长这样：

4          o
          /
3       o--o
          /
2    o--o--o
    /
1 o--o--o--o
  1  2  3  4

Pdw 想要知道，有多少种不同的连边方案，使得连完这些边后的图，是一棵以 $(1,1)$ 为根节点的二叉树，并且所有节点的儿子（如果有）的横坐标都比该节点大。两种连边方案不同，当且仅当存在至少一个点 $(i,j)$，它在两种连边方案中连的边不一样。

举个例子，当 $n=4$ 时，一个形成合法二叉树的连边方案长这样：

4          o
          /
3       o  o
       /  / 
2    o--o  o
    /     /
1 o--o--o--o
  1  2  3  4

由于答案可能很大，请把答案对 $23333333333$ 取模。

输入格式

仅一个正整数 $n$，$n$ 的定义见题目描述。

输出格式

一个正整数，表示你的答案。

3

2

4

6

数据规模与约定

对于 $10\%$ 的数据，$n\leq 100$；
对于 $25\%$ 的数据，$n\leq 2000$；
对于 $45\%$ 的数据，$n\leq 4\times 10^5$；
对于 $50\%$ 的数据，$n\leq 2\times 10^7$；
对于 $90\%$ 的数据，$n\leq 10^{10}$；
对于另外 $10\%$ 的数据，$10^{12}\leq n\leq 10^{18}$。
对于 $100\%$ 的数据，$n\geq 2$。