题目描述

长度为N的由大写字母构成的字符串，其中有多少种不同字符串的子序列包括ZIME这四个字母？

在计算机编程中，子序列是指一个字符串中可连续也可不连续的一段字符序列。


例如，在字符串”HelloWorld”中，”Hello”、”Wd”、”HW” 等都是该字符串的子序列，但是 ”Hello HanHan”、”ori”、”sb” 不是该字符串的子序列。


你能帮忙编写一个程序实现以上功能吗？

输入格式

多个N，每个N的询问独立。

有37.5%的样例N≤6。（暴力）


有50.0%的样例N≤7。（减枝+Set） 


有75.0%的样例N≤8。（减枝+容斥） 


有100.0%的样例0ΣN≤N*100。（容斥+记忆化）

输出格式

如题要求所示的一个整数，由于答案很大，你需要对1e9+7取模。

3
4
6

0
1
9526

提示

注意1：ZIMEHANHAN仅算一种合法字符串，交换两HANHAN的位置也不算两种不同的合法字符串。