题目描述

我们考虑普通的二叉搜索树（BST）。查找一个元素时，从根开始比较：若目标更小则进入左子树，若目标更大则进入右子树。向 BST 插入一个新元素时，也沿着相同的查找路径前进，直到第一次到达空位置并插入。

查找某个已经存在的元素 $X$ 时，所需时间与和 $X$ 比较过的 BST 节点数成正比。

定义：

• 若一棵 BST 使“查找任意元素时的最大比较次数”尽可能小，则称它为最坏情况最优（WC optimal）；
• 若从树中所有元素等概率随机选择一个目标，且该 BST 使“比较次数的期望”尽可能小，则称它为平均情况最优（AC optimal）；
• 若一棵 BST 是 WC optimal 但不是 AC optimal，称为 only WC optimal；
• 若一棵 BST 是 AC optimal 但不是 WC optimal，称为 only AC optimal。

任意一个 $0,1,\ldots,N-1$ 的排列都可以确定一棵 BST：初始树为空，按照排列中的顺序依次插入这些数。不同排列可能得到同一棵 BST。

设：

• $OWC$ 为能够生成 only WC optimal BST 的排列数量；
• $OAC$ 为能够生成 only AC optimal BST 的排列数量。

请计算 $OWC$ 和 $OAC$ 对 $10^9+7$ 取模后的结果。

输入格式

输入仅一行，一个整数 $N$。

输出格式

为了与测试数据的统一数组格式保持一致，输出两行：

• 第一行固定输出整数 2，表示答案数组长度；
• 第二行输出两个整数 OWC OAC。

数据范围

$1\le N\le4000$。

样例输入

4

样例输出

2
4 0

样例说明

当 $N=4$ 时，有 $4$ 个排列生成的 BST 只在最坏情况下最优，而不存在只在平均情况下最优的排列。