动物园最近进行了选举。总共有 7 个主要政党:其中一个是小象政党,其他 6 个政党的名字不太朗朗上口。
政党发现自己在选票中的数字非常重要。总共有 m 个可能的数字:1, 2, ..., m。这 7 个参与方中的每一方都将以某种方式分配给一个号码,此时,两个不同的参与方不能收到相同的号码。
小象政党成员相信幸运数字4和7。他们想评估自己在选举中的机会。为此,他们需要找出有多少个正确的分配,使得小象政党选票中的幸运数字数量严格大于其他6个政党选票中的幸运数字总数。
帮助小象政党,算算这个数字。由于答案可能相当大,因此打印除以 1000000007 (109 + 7) 所得的余数。
输入
单行包含一个正整数 m (7 ≤ m ≤ 109) — 选票中可能的数字数量。
输出
在一行中打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。
示例
输入 #1
7
输出 #1
0
输入 #2
8
输出 #2
1440