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

一行一个正整数n (4 <= n <= 1000)

一行一个正整数

算法 组合数学 递归 DFS