回想一下,二叉搜索树是一棵有根二叉树,其节点每个都存储一个键,并且每个节点最多有两个不同的子树,即左子树和右子树。每个节点中的键必须大于左子树中存储的任何键,并且小于右子树中存储的任何键。
顶点的深度是从顶点到根的简单路径上的边数。特别是,根的深度是$$$0$$$。
如果不存在具有相同顶点数但其顶点深度总和严格较小的二叉搜索树,我们称二叉搜索树为完美平衡。
如果每个顶点 $$$v$$$ 都满足以下两个条件,我们就调用带有整数键条带化的二叉搜索树:
- 如果 $$$v$$$ 有一个根为 $$$u$$$ 的左子树,则 $$$v$$$ 的键奇偶校验与 $$$u$$$ 的键奇偶校验不同。
- 如果 $$$v$$$ 有一个根为 $$$w$$$ 的右子树,则 $$$v$$$ 的键奇偶校验与 $$$w$$$ 的键奇偶校验相同。
给你一个整数$$$n$$$。查找具有 $$$n$$$ 顶点且具有介于 $$$1$$$ 和 $$$n$$$(含)之间的不同整数键的完美平衡条带二叉搜索树的数量。输出该数字对 $$$998\,244\,353$$$ 取模。
输入
唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$),表示所需的顶点数。
输出
输出具有 $$$n$$$ 顶点和 $$$1$$$ 和 $$$n$$$(含)之间不同整数键的完美平衡条带二叉搜索树的数量,模 $$$998\,244\,353$$$。
示例
输入 #1
4
输出 #1
1
输入 #2
3
输出 #2
0
注意
在第一个示例中,这是唯一满足条件的树:
在第二个示例中,以下是不满足某些条件的各种树: