现已知学校的天花板可近似看成3 * n的长方形，小 Z 的粉刷工具每次可以粉刷 1*3的区域，可以竖 着或者横着粉刷。由于材料有限，粉刷过的区域不会重复粉刷。请你帮校长算一下小 Z 最后粉刷出来的 天花板可能有几种不一样的方案。由于方案数可能很大，输出它模10^9+7 的余数即可。 注意：小 Z 在粉刷的时候必须完全刷满整个天花板，并且每一个小方格不能被重复刷2次。

输入格式

一行一个整数 。

输出格式

一行一个整数，表示方案数模 10^9+7的余数。