Problem Description
　　We call a number interesting, if and only if:
　　1. Its digits consists of only 0, 1, 2 and 3, and all these digits occurred at least once.
　　2. Inside this number, all 0s occur before any 1s, and all 2s occur before any 3s.
　　Therefore, the smallest interesting number according to our definition is 2013. There are two more interseting number of 4 digits: 2031 and 2301.

Your task is to calculate the number of interesting numbers of exactly n digits. As the answer might be very large, you only need to output the answer modulo 1000000007.

Input Format

The input has one line consisting of one positive integer n (4 ≤ n ≤ 10^15).

Output Format

The output has just one line, containing the number of interesting numbers of exactly n digits, modulo 1000000007.

Input Sample

4

Output Sample

3

我用了两个dfs，当4的时候是对的，但是10的时候数据差据很大，我把数据打出来感觉没错，不知道这道题怎么做了？

#include<iostream>
#include<cstdio>
#define N 1000000007

using namespace std;

int data[4]={1,1,1,1};
int dfs2(int n,int* num,int u);
int count = 0;
int temp[100]={0};

int dfs1(int n,int u)
{
    if (n>u) {
        return 0;
    }
    
    if (n==u) {
        dfs2(0,data,u+4);
    }
    else {
        for(int i=0;i<4;i++) {
            data[i]++;
            dfs1(n+1,u);
            data[i]--;
        }
    }
}

int dfs2(int n,int* num,int u)
{
    if (n>u) {
        return 0;
    }
     
    if (n==u) {
        count=count%N;
        count++;
        /*    for(int i=0;i<n;i++)
        cout<<temp[i]<<" ";
        cout<<endl;*/ 
    } 
    else {
        for (int i=0;i<4;i++) {
            if (i==1 && num[0]>0) {
                continue;
            }
            
            if (i==3 && num[2]>0) {
                continue;
            }
            
            if (i==0 && n==0)
                continue;
                
            if (num[i]>0) {
                num[i]--;
                temp[n]=i;
                dfs2(n+1,num,u);
                num[i]++;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    dfs1(0,n-4);
    cout << count;
}