P95263

Problem S4: Interesting Numbers 加强版  

难度 未定
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 256 MB

题目描述

  We call a number interesting, if and only if:
  1. Its digits consists of only 0, 1, 2 and 3, and all these digits occurred at least once.
  2. Inside this number, all 0s occur before any 1s, and all 2s occur before any 3s.
  Therefore, the smallest interesting number according to our definition is 2013. There are two more interseting number of 4 digits: 2031 and 2301.
  Your task is to calculate the number of interesting numbers of exactly n digits. As the answer might be very large, you only need to output the answer modulo 1000000007.
 

输入

  The input has one line consisting of one positive integer n (4 ≤ n ≤ 10^15).
 

输出

  The output has just one line, containing the number of interesting numbers of exactly n digits, modulo 1000000007.
 

样例

样例 1
输入
4
输出
3

来源

蓝桥杯

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交