对于正整数 ，满足以下条件的有根二叉树被定义为 次美丽二叉树。
给定 ，请输出 次美丽二叉树的个数，答案对 取模。
输入为一行，包含一个整数 。
输出一个整数，表示答案。
1
2
6
222
987355927
222222
675337738
满足条件的二叉树只有一种，即根节点上写有 的单节点树。
满足条件的二叉树共有 种。
