Non‐crossing Chord Matching on a Circle

Kagamine Rin had a circle with n evenly‐distributed points. Initially, m chords (line segments connecting two distinct points) were drawn on the circle in such a way that any two chords do not intersect (note that sharing an endpoint or overlapping is allowed, and intersection only counts if the chords cross in their interiors). One day all the chords disappeared. Rin only remembers that the chords were drawn without any crossing. Sometimes she even remembers extra information – for each point she may recall the number of chords incident to it (which, in a non‐crossing matching, is either 0 or 1).

Your task is to count the number of possible ways to re‐draw exactly m chords satisfying Rin’s memory. Since the answer can be huge, output it modulo \(10^9+7\).

Note. In this problem we assume that if the extra degree information is provided then each point’s degree is either 0 or 1, so the chords form a non‐crossing matching (i.e. each point is incident to at most one chord). It can be shown that:

• If no degree info is provided, the answer is
  \(\displaystyle \binom{n}{2m} \cdot C_{m}\ \bmod (10^9+7)\),
• If the degree info is provided (as an array of n numbers, each 0 or 1), then if the number of ones is not exactly \(2m\) the answer is 0; otherwise the answer is
  \(C_m \bmod (10^9+7)\),

Here \(C_m\) denotes the \(m\)th Catalan number, which may be computed by

[ C_m = \frac{1}{m+1}\binom{2m}{m} \quad \text{or} \quad C_m = \binom{2m}{m} - \binom{2m}{m+1}. ]

You are to implement this counting. It is guaranteed that the input values are such that a factorial precomputation up to at least \(\max(n,2m)\) is sufficient.

inputFormat

The input is given in the following format:

n m
[d1 d2 ... dn]

The first line contains two integers n and m. The second line is optional. If it is present, it contains n integers where the i-th integer (either 0 or 1) represents the remembered degree at point i. If the second line is missing, then no degree information is provided.

outputFormat

Output a single integer – the number of valid ways modulo \(10^9+7\).

sample

4 1

6