282. Ambiguous Coordinates (Count)

You had a 2D coordinate like '(x, y)' but removed the comma, decimal points, and spaces, leaving a string of digits wrapped in parentheses. Return the number of ways to restore it to a valid coordinate. Each number has no extraneous leading zeros and no trailing zeros after a decimal point. Input: a quoted string like "(123)".

Input: A quoted digit string in parentheses.

Output: Integer — number of valid coordinates.

Examples

Input: "(123)"
Output: 4
Explanation: (1, 23),(12, 3),(1.2, 3),(1, 2.3).

Input: "(0123)"
Output: 2
Explanation: Limited by leading-zero rules.

Input: "(00011)"
Output: 0
Explanation: No valid split.

Constraints

• 4<=s.length<=12
• digits wrapped in parentheses

Asked by