20分解法

由于n最大只有1e3，所以只需要开出两个数组a，b，递推得到a[n]%mode的值和b[n]%mode的值，然后将他们的乘积%mode后返回即可，时间复杂度o（n），空间复杂度o（n）

50分解法

此时n最大为1e7，递推的时间复杂度和空间复杂度都为o(n),虽然此时时间上还是够的，但是32MB开不下1e7的空间，哪怕ab共用一个数组也会爆内存。此时考虑每一项的值只和前两项有关，所以可以使用滚动数组优化一下递推，从而使递推的空间复杂度变成o（1）（时间复杂度仍为o（n））

100分解法

n最大为1e18，此时o（n）的做法显然会超时了，考虑转移是一个递推式，我们只要构造两个矩阵进行矩阵快速幂即可在实现时间复杂度o（logn），空间复杂度o（1）算出an和bn。当然，这样就变成了一个矩阵快速幂模板题。本题出题的本意是想让大家找规律从而更简单地解决本问题。a,b数组其实可以分别化简成a[n]=3a[n-1],b[n]=5b[n-1],我们使用快速幂算法就可以直接算出an，bn（当然也可以合并推出c的公式直接算出cn的值，c数组的公式为c[n]=c[n-1]*15）。快速幂做法的时间复杂度与空间复杂度和矩阵快速幂相同，但显然常数要小得多。一次两个矩阵相乘远比两个数直接相乘慢。比如本题目如果改成求5e6次询问，经测试矩阵快速幂的时间大约是快速幂的10倍，但本意是出比较简单的题目所以也没有卡这一点。对于公式的找法如果对数学公式不是很敏感也可以打表找一下规律，也很容易找到规律，下面是快速幂做法的代码

const int mode=1e9+7;
class Solution {
public:
    /**
     * 返回c[n]%1000000007的值
     * @param n long长整型 即题目中的n
     * @return int整型
     */
     long long Mode(long long a, long long b){
        long long sum = 1;
        while (b) {
            if (b%2) {
                sum =(sum*a)%mode;
                b--;
            }
            b/=2;
            a=a*a%mode;
      }
    return sum;
}
    int Answerforcn(long long n) {
        // write code here
        long long an=2*Mode(3,n-1)%mode;
        long long bn=7*Mode(5,n-1)%mode;
        long long cn=an*bn%mode;
        int ans=cn;
        return ans;
    }
};