A perfectly even number is defined as a positive integer whose digits are all multiples of \(2\). One example of a perfectly even number is \(804\).

Given a positive integer \(N\) \((1 \le N \le 10^{1000})\), calculate the amount of perfectly even numbers that are strictly under \(N\). Since there are a lot of them, output the answer modulo \(10^9 + 7\).

Input Specification

The first line of the input will contain one integer \(N\).

Output Specification

Output an integer, representing the amount of perfectly even numbers that are strictly under \(N\), modulo \(10^9 + 7\).

Sample Input

28

Sample Output

8

Sample Explanation

There are \(8\) perfectly even numbers under \(28\):

\[2, 4, 6, 8, 20, 22, 24, 26\]