俗话说，跳蚤国王下江南，火车司机出秦川，共价大爷游长沙。

但是这道题可能跟上面几句话没什么关系。
共价爷想构造一棵 个点的有根树，其中 号点是根。
显然的，对于一棵有根树，我们可以定义每个点的深度为，这个点到根的路径上点的个数（包括端点），也就是说， 号点深度为 。
共价爷希望，深度为奇数的点的个数，刚好为 个。
他想知道有多少棵不同的满足条件的有根树，你只需要输出答案对 取模的结果。

我们认为两棵树不同，当且仅当存在一对点 ，满足 和 在一棵树中有边相连，而在另一棵树中没有边相连。