牛牛是一个爱 Froggy 的男孩子。

活点地图上显示，在 Hogwarts 的黑湖上，有 个石墩，编号为 到 ，第 个石墩上有 只青蛙。

牛牛想进行 次独立的操作，每次只保留编号在 中的石墩。

牛牛想起了麻瓜的 OI，想起了二叉树。他决定将这些石墩用一些边连起来，并指定一个根，使之成为一棵二叉树。

二叉树虽然是麻瓜发明的，但是牛牛觉得二叉树的中序遍历充满魔力，于是他希望对这棵二叉树中序遍历得到的编号序列恰好为 。

牛牛今天又从全年级第一的麻瓜出身的 Hermione 那学了一种新的数据结构——堆。他希望借这棵二叉树复习一下堆的结构，所以他又规定这棵二叉树需要满足任意一个不为根的石墩的青蛙数量不少于这个石墩的父亲的青蛙数量。

对于每次操作，请你帮助牛牛求出有多少种符合条件的不同的二叉树。

两棵二叉树不同当且仅当满足下列条件之一：

• 根的编号不同；
• 存在两个石墩 满足恰好在其中一棵树中存在边 。

由于答案可能很大，你只需要输出答案对 取模的结果即可。