Numbers of len (n), consecutive digits with difference > |3|

/**
 *  BasselBakr (2016)
 */

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair < int, int >pii;

#ifndef ONLINE_JUDGE
auto __redirect__ = freopen("in", "r", stdin);
#else
#  include<bits/stdc++.h>
#endif

#define ln '\n'
#define del(x) if(x)delete x

#define lsb(x) (x&-x)

#define rep(i,a,b) for(int i = a; i < b; ++i)
#define repq(i,a,b) for(int i = a; i <= b; ++i)

#define per(i,a,b) for(int i = a; i >= b; --i)
#define revn(i,a,b) for(int i = a; i > b; --i)

#define repc(i,a,cond) for(int i = a; cond; ++i)
#define revc(i,a,cond) for(int i = a; cond; --i)

#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) (x/__gcd(x,y)*y)

#define p(x,y) pair<x,y>
typedef p(int, int) pii;
typedef vector < int >vi;
typedef vector < pii > vpii;

int const N = 1e6 + 16;
int const M = 1e9 + 7;

int digits[][6] = {
  {4, 5, 6, 7, 8, 9},           //0
  {5, 6, 7, 8, 9},              //1
  {6, 7, 8, 9},                 //2
  {7, 8, 9},                    //3
  {0, 8, 9},                    //4
  {0, 1, 9},                    //5
  {0, 1, 2},                    //6
  {0, 1, 2, 3},                 //7
  {0, 1, 2, 3, 4},              //8
  {0, 1, 2, 3, 4, 5},           //9
};

int sz[10] = {
  6, 5, 4, 3, 3, 3, 3, 4, 5, 6
};

// [length][last_digit]
ll dp[N][10];

// n = length
ll f(int n) {
  rep(i, 0, 10) {
    dp[1][i] = 1;
    dp[2][i] = sz[i] - (i >= 4);
  }

  repq(i, 3, n)                  // length
    rep(d, 0, 10)               // last digit
      rep(j, 0, sz[d])          // digit before last
        dp[i][d] = (dp[i][d] + dp[i - 1][(digits[d][j])]) % M;

  ll cnt = 0;
  rep(i, 0, 10)
    cnt += dp[n][i];
  return cnt % M;
}

int main() {
  printf("%lld\n", f(3));
}