### 问题描述 小飞最近迷上了细菌培养，他准备培养 $4$ 种细菌。这 $4$ 种细菌有着神奇的相互转化的能力，转化规则如下：每经过一天，$1$ 只细菌 $A$ 会变为 $1$ 只细菌 $B$ 和 $1$ 只细菌 $C$，$1$ 只细菌 $B$ 会变为 $2$ 只细菌 $C$，$1$ 只细菌 $C$ 会变为 $1$ 只细菌 $A$ 和 $1$ 只细菌 $D$，$1$ 只细菌 $D$ 会变为 $1$ 只细菌 $A$ 和 $1$ 只细菌 $B$ 和 $1$ 只细菌 $C$。 以某一天为起点，接下来在每个第 $2^k$ （$k$ 为非负整数）天时，小飞都会往培养皿中投入 $4$ 种细菌各 $1$ 只。 初始的培养皿是空的，现在请给出第 $k$ 天时培养皿中各种细菌的数量，由于结果可能很大，请输出对 $10^9 + 7$ 取模后的结果。 ### 输入格式 一个整数 $k$。 ### 输出格式 输出一行四个整数，分别表示细菌 $A,B,C,D$ 第 $k$ 天时的数量。 ### 样例输入 ```text 2 ``` ### 样例输出 ```text 3 3 5 2 ``` ### 评测数据规模 对于 $100$% 的评测数据，$1 \leq k \leq 10^{15}$。