Uber assigns a unique rideCode to each completed trip. This code is represented as a numeric string. To ensure security and fraud prevention, the system needs to evaluate the number of valid ways the rideCode can be partitioned into secure tokens.

Each secure token must meet the following conditions:

• It must represent a prime number between 2 and 10^6 (inclusive).
• It must not have leading zeros.
• All digits of the rideCode must be used in the partition.
• The digits must remain in their original order.

Since the number of valid partitions may be very large, return the result modulo (10^9 + 7).

Example

rideCode = "11375" Output: 3 Explanation: The partitions are: [11, 37, 5] [11, 3, 7, 5] [113, 7, 5]

Constraints

• 1 < length of rideCode ≤ 100,000
• rideCode does not start with '0'.
• Each secure token must lie within [2, 10^6]
• No two partitions can overlap.