小红想知道，深度为 的满二叉树有多少条长度为 的简单路径？由于答案可能很大，请将答案对 取模后输出。 在本题中，两条简单路径所包含的点集不同时，被视为不同的。例如，路径 与路径 被视为相同的，因为它们均包含点 与点 。 一棵深度为 的满二叉树由恰好 个节点组成，每一个节点要么是叶子节点，要么有 个儿子，并且全部叶子节点的深度均为 。 简单路径是指这样一条路径，其经过的顶点和边互不相同。

输入描述:

在一行上输入一个正整数 代表满二叉树的深度。

输出描述:

输出一个整数，代表深度为 的满二叉树中，长度为 的简单路径的数量。由于答案可能很大，请将答案对 取模后输出。