Given a string **S** consisting of digits [0-9], count the number of ways this string can be split into continuous substrings such that each substring is a prime number. Each digit must be in one substring and the entire string must be used.

**Note:**
The input string does not contain leading zeros.
Each number split of the given number must be in the range `2 to 1e6` inclusive.
Since the answer can be large, return the answer modulo `1e9+7`.


**Constraints**
1 <= | S | <= 1e5

**Example**
_input_
11373
_output_
6
_Explanation_
[11, 3, 7, 3], [11, 3, 73], [11, 37, 3], [113, 7, 3], [113, 73], [11, 373].


Can anyone help me out?
Thanks in advance.
Happy Coding...
 
P.S.: This is my first blog, so correct me if I'm wrong anywhere.

Feel free to share your approach.