A refinery's pipeline runs in a straight line made up of n numbered segments, indexed 1 through n from the inlet to the outlet. Each segment either houses a shutoff valve (marked 1) or has no valve (marked 0). For safety, a maintenance plan partitions the pipeline into one or more contiguous zones — every segment belongs to exactly one zone, the zones are non-overlapping, and together they cover the whole pipeline in order — such that each zone contains exactly one shutoff valve. Two partition plans are considered different if there is some segment boundary chosen in one plan but not the other.
Count the number of valid partition plans, modulo 1,000,000,007. If no valid partition exists (for example, when the pipeline has no valves at all), the answer is 0.
Line 1: an integer n. Line 2: n integers, each 0 or 1, the valve markers for segments 1 through n in order.
A single integer: the number of valid zoning plans, modulo 1,000,000,007.
Example 1
Input
5 0 1 0 0 1
Expected
3
Explanation
Using 0-indexed positions, valves sit at indices 1 and 4. Segment 1 (index 0) must join the first valve's zone, and segment 5 (index 4) is itself the second valve, so the only freedom is where the single internal boundary between the two valves falls: right after index 1, after index 2, or after index 3 — 3 possible places. So there are 3 valid partition plans.
Example 2
Input
4 1 1 0 1
Expected
2
Explanation
Using 0-indexed positions, valves sit at indices 0, 1, and 3. Consecutive valves at indices 0 and 1 leave no free segment between them, so there is exactly 1 way to place that boundary (immediately between them). Consecutive valves at indices 1 and 3 have one free segment (index 2) between them, giving 2 choices for that boundary. Multiplying the independent choices for each gap gives 1 * 2 = 2 valid partitions.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →