## Perfectly Even Numbers (Extreme)

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\]

## Comments