class Solution {
public:
    
    vector<pair<int,int>>p = {{2,1},{1,2},{1,-2},{2,-1},{-1,2},{-2,1},{-1,-2},{-2,-1}};
    
    bool numbered(int x,int y)
    {
        if(x>=0 && x<=2 && y>=0 &&y<=2)
            return true;
        if(x==3&&y==1)
            return true;
        return false;
    }
    
    long long int dp[4][3][5002];
    
    long long int solve(int i, int j, long long moves)
    {
        if(moves==0)
            return 1;
        int ans = 0;
        if(dp[i][j][moves]!=-1)
            return (dp[i][j][moves]%1000000007);
        
        set<pair<int,int>>s;
        for(auto x:p)
        {
            if(numbered(i+x.first,j+x.second))
            {
                s.insert(make_pair(i+x.first,j+x.second));   
            }
            
        }
        for(auto i:s)
        {
            int x = i.first;
            int y = i.second;
            ans+= (dp[x][y][moves-1]!=-1?(dp[x][y][moves-1]%(1000000007)):(solve(x,y,moves-1)%(1000000007)));
            
        }
        
           // cout<<i<<' '<<j<<' '<<moves<<' '<<ans<<'\n';
        return (dp[i][j][moves] = ans%(1000000007));
    }
    
    int knightDialer(int N) {
        
        memset(dp,-1,sizeof(dp));
        long long ans = 0;
        set<pair<int,int>>s;
        for(int i=0;i<=3;i++)
        {
            for(int j = 0;j<=2;j++)
            {
                if(numbered(i,j))
                {
                    s.insert(make_pair(i,j));
                }
            }
            
        }
        for(auto i:s)
        {
            int x = i.first;
            int y = i.second;
            ans+=(solve(x,y,N-1))%1000000007;
            
        }
                
        
        return (ans%1000000007);
        
    }
};