问题描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。

输入格式
输入包含两个正整数，K和L。

输出格式
输出一个整数，表示答案对1000000007取模后的值。
样例输入
4 2
样例输出
7
数据规模与约定
对于30%的数据，KL <= 106；

对于50%的数据，K <= 16， L <= 10；

对于100%的数据，1 <= K,L <= 100。

这里k和L的数据规模都是100，那么我现在考虑的有两个解法。一种是回溯法，一位一位的遍历每一种情况。如果是K进制，L位的话，那么总共要遍历K的L次方种情况。毕竟每一位上都可以是0到
K-1，当然回溯到不合题意的情况。
第二种是动态规划。求L位K进制数中K好数的数目，可以先求出L-1位K好数，L-2位K好数......1位K好数。设F[i][j]表示i位以数字j结尾的K好数数目，1<=i<=L,0<=j<K，状态转移方程：
F[i][j] = F[i-1][p](p遍历0到k-1的情况)的总和。那么这个算法的复杂度也是K的L次方次加法。
那么问题来了~~动态规划的节约时间的优点体现在哪里呢？或者说我用回溯法会时间超时，动态规划却不会的原因在哪里呢？
不知道我有么有清楚的描述我的问题~~~~求指点

自顶~~~