5354 - 数位动态：有趣的数

我们把一个数称为有趣的，当且仅当 1、它的数字只包含0、1、2、3，且这四个数字都出现过至少1次 2、所有的0都出现所有的1之前，而所有的2都出现在所有的3之前 3、最高位数字不为0 因此，符合我们定义的最小的有趣的数是2013，除此之外，4位的有趣的数还有两2个：2031和2301 请计算恰好有n位有趣的数的个数，由于答案可能比较大，需要对答案除以1000000007的余数

输入只有一行，包含恰好一个正整数n，（4<=n<=1000)

输出只有1行，包含恰好n位的整数中有趣的数的个数除以1000000007的余数