【描述】H1N1病毒在校园里肆虐，LazyChild与RQ上周因为感冒相继回家，当然，他们都健康归来。但他们不想就此罢休，决心破译H1N1的遗传密码。经过一番努力，两人有了重大突破。他们发现H1N1病毒DNA中的腺嘌呤与胞嘧啶总是成对出现的，即腺嘌呤的出现次数是偶数次，胞嘧啶的出现次数也是偶数次（不必相同，也可以没有）！为了进一步进行破译，他们想知道在已发现的规律下由N个碱基组成的H1N1病毒有多少种可能的排列方式。例如当N=2时，共有如下六种可能的排列：TT、TG、GT、GG、AA、CC。为了全机房的和谐与团结，这个光荣的使命在再次交给了你。
【输入格式】第一行：一个整数N，如题目中描述。
【输出格式】一行一个整数表示可能的排列总数，答案对7222222取模。
【输入样例】2
【输出样例】6
【数据范围】
* 10%：1<=N<=7
* 100%：1<=N<=1000000000