Prime String — Count Ways to Split into Primes

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.

输入格式

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. All examples have been verified by independent small-scale enumeration or state search.