Counting Graphs with a Given Minimum Vertex Cover Parity

Consider a simple undirected graph (G=(V,E)) where (V={1,2,\ldots,n}). A vertex cover of (G) is a subset (S\subseteq V) such that for every edge ((u,v)\in E), at least one of (u) or (v) is in (S). The size of a vertex cover is (|S|). The minimum vertex cover size of a graph is the minimum size among all vertex covers of (G).

Given a positive integer (n) and an integer (k), count how many simple undirected graphs (G=(V,E)) with (V={1,2,\ldots,n}) have a minimum vertex cover size exactly equal to (k). Two graphs (G_1=(V,E_1)) and (G_2=(V,E_2)) are considered different if there exists a pair (u,v\in V) such that ((u,v)) belongs to exactly one of (E_1) or (E_2).

Since the answer might be large, output the answer modulo (2) (i.e. the remainder after division by (2)).

Observation: Note that for any graph (G) on (n\ge2) vertices, the total number of graphs is (2^{\binom{n}{2}}) which is even. In fact, one can show that among all graphs on (V), only the edgeless graph (with minimum vertex cover size (0)) and the complete graph (with minimum vertex cover size (n-1)) occur in odd numbers, while all other cases occur an even number of times. For (n=1), the only graph has no edges and hence its minimum vertex cover size is (0).

Thus, the answer modulo (2) is:

• If \(n=1\): answer is \(1\) when \(k=0\) and \(0\) otherwise.
• If \(n\ge2\): answer is \(1\) if \(k=0\) or \(k=n-1\); otherwise, the answer is \(0\).

This is the key observation used to solve the problem.

inputFormat

The input consists of a single line containing two integers (n) and (k) where (n) is a positive integer representing the number of vertices and (k) is an integer such that (0\le k\le n-1) (for (n\ge2); when (n=1), only (k=0) is valid).

outputFormat

Output a single integer, the number of graphs on (n) vertices whose minimum vertex cover size is exactly (k), taken modulo (2).

sample

1 0

1