Prime String

Split the entire digit string, keeping its original order, into several primes, where each segment has no leading zeros and each prime lies in 2..10⁶; count the number of ways modulo 10⁹+7. The upper bound 10⁶ is restored from the original snapshot, not the 10⁸ mistakenly written in the catalog. This catalog entry shares its source with an earlier problem; it keeps its own problem ID and is verified independently.

输入格式

One line containing a digit string of length 1..100000 whose first digit is not 0.

输出格式

Output the single integer required by the problem.

样例 1

输入：

11375

输出：

3

样例 2

输入：

2

输出：

1

样例 3

输入：

101

输出：

1

样例说明

The answers to the three public examples are, in order: 3; 1; 1. The examples were rechecked by independent enumeration, state search, or direct simulation.