Description

某日药水哥直播的时候，教塔子哥背九九乘法表。当塔子哥连背了几遍“九六七十二”之后，药水哥有点绝望，便想从更基础的问题教起——数数，现在请你也和塔子哥一起数。
首先在正整数集上定义函数\(g(n)\)：
1.\(g(1)=1\)
2.如果\(n\)能表示成若干个两两不同质数的乘积，那么\(g(n)=1\),否则\(g(n)=0\)
现在有一张纸上面，从左到右写了\(g(1),g(2),...,g(n)\)，药水哥问塔子哥这个数是多少，也就是把\(g(1)g(2)g(3)...g(n)\)连起来看成一个\(10\)进制数，其中\(g(1)\)是最高位，那么这个数是多少。
这个数可能很大，请输出这个数对于\(1000000007\)取模的结果。

Format

Input

每个测试点仅包含一组输入数据，一行一个正整数\(n（1<=n<=10^{11})\)

Output

输出一行一个正整数代表本题答案。

Sample 1

Input

4

Output

1110

Limitation

1s, 1GB for each test case.

Source

Vijos Original