小红的无向图变身

小红的无向图变身

题号：NC275528
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红有一个 $n$ 个点的完全无向图，你可以将每条边 $(u, v)$ 变成四种边之一：
- 有向边 $(u \to v)$
- 有向边 $(v \to u)$
- 蓝色无向边
- 红色无向边
并且你需要保证：
- 新图不存在至少包含一条有向边的环；
- 不存在蓝色四元环（ $A,B,C,D$ ），如图一，其中 $A,B,C,D$ 互不相同；
- 不存在红色结构（ $A,B,C,X,Y,Z$ ），如图二，其中 $A,B,C,X,Y,Z$ 互不相同。

定义图上一个的环是一个顶点序列 $\{v_1,v_2, \dots,v_k,v_{k+1}\}$ , 满足 $v_1$ 到 $v_k$ 这 $k$ 个顶点两两不同，并且 $v_{k+1} =v_1$ ,并且对于 $i$ 等于 $1$ 到 $k$ ，边 $(v_i,v_{i+1})$ 要么是一条无向边，要么是一条 $v_i$ 指向 $v_{i+1}$ 的有向边。

小红想知道有多少种方案可以满足上述条件。

输入描述:

第一行一个整数 ，表示无向图的点数。

输出描述:

输出一个整数，表示答案对  取模的结果。

示例1

输入

复制

输出

复制

说明

一共有 1 条边，可以把这条边变成 4 种边之一。

示例2

输入

复制

输出

复制