说明

众所周知的是，数字王国的公民有质数，也有合数，每个数字便是一个公民。现在我们要为1到n的公民设计排列方案，要求素有的质数公民都被放在质数索引上（索引从1开始），你来算一算一共有多少种排列方案吧！

质数：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。

由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果。

输入格式

一个正整数n（1<=n<=100）

输出格式

排列方案对 10^9+7 取模后的结果

样例

5

12

提示

样例输入 #2
100


样例输出 #2
682289015