你告别了 Crazycth 继续上路，又遇到了不喜欢数学的 DavidXu_JJ 讲故事。

DavidXu_JJ 有一天和他的队友在训练时，遇到这么一道题：

有一个长度为 的数组 ，数组中的每个元素可以是 中的任意一个整数。如果它所有元素之和 是 的倍数，那么就称它为有趣的数组，你需要求出所有长度为 的数组中有多少种数组是有趣的。

DavidXu_JJ 和他的队友决定构造它的 生成函数 并使用 快速傅立叶变换 来计算这个值，但在复盘时发现这题有极其简单的方法能够算出答案，导致他们当场脑淤血晕倒过去。

DavidXu_JJ 从病床上想到了一个更加困难的问题，但他因为心理阴影导致无法独立解决这个问题，请问你能否帮助他解决？题目描述如下：

有一个长度为 的数组 ，数组中的每个元素可以是 中的任意一个整数。现将其下标为奇数的元素和偶数的元素分别取出，组成两个数组 和 。例如：数组 被分为数组 和数组 。

如果 是 的倍数且 数组是 的倍数，那么就称 为"不有趣的数组''，请求出所有长度为 的不有趣数组的个数。由于答案可能很大，你只需要输出答案对 取模后的结果。

第一行包含一个整数  ，表示数组  的长度。

在一行输出一个整数，表示所有长度为  的不有趣数组的个数对 取模后的结果。

2

8

5

4008

114514

549375874