#H1011. Pdw 的憨憨树

Pdw 的憨憨树

题目描述

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

举个例子,当 n=4n=4 时,这些点长这样:

4          o

3       o  o

2    o  o  o

1 o  o  o  o
  1  2  3  4

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

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

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

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

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

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

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

由于答案可能很大,请把答案对 2333333333323333333333 取模。

输入格式

仅一个正整数 nnnn 的定义见题目描述。

输出格式

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

3
2
4
6

数据规模与约定

对于 10%10\% 的数据,n100n\leq 100
对于 25%25\% 的数据,n2000n\leq 2000
对于 45%45\% 的数据,n4×105n\leq 4\times 10^5
对于 50%50\% 的数据,n2×107n\leq 2\times 10^7
对于 90%90\% 的数据,n1010n\leq 10^{10}
对于另外 10%10\% 的数据,1012n101810^{12}\leq n\leq 10^{18}
对于 100%100\% 的数据,n2n\geq 2