C-小红的二叉树_牛客周赛 Round 79

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红想知道，深度为 $n$ 的满二叉树 $^{\texttt{[1]}}$ 有多少条长度为 $2$ 的简单路径 $^{\texttt{[2]}}$ ？由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。
$\hspace{15pt}$ 在本题中，两条简单路径所包含的点集不同时，被视为不同的。例如，路径 $u-v$ 与路径 $v-u$ 被视为相同的，因为它们均包含点 $u$ 与点 $v$ 。

$\hspace{15pt}$ 一棵深度为 $h$ 的满二叉树 $^{\texttt{[1]}}$ 由恰好 $2^h-1$ 个节点组成，每一个节点要么是叶子节点，要么有 $2$ 个儿子，并且全部叶子节点的深度均为 $h$ 。
$\hspace{15pt}$ 简单路径 $^{\texttt{[2]}}$ 是指这样一条路径，其经过的顶点和边互不相同。

输入描述:

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

输出描述:

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

示例1

输入

复制

输出

复制

说明

在这个样例中，深度为  的满二叉树只有  个节点，所以没有长度为  的简单路径。

示例2

输入

复制

输出

复制

说明

在这个样例中，所给出的满二叉树如下图所示：