AMC 12 2006a Problem 25

How many non-empty subsets $S$ of $\lbrace 1,2,3,\ldots ,15\rbrace$ have the following two properties?

$(1)$ No two consecutive integers belong to $S$.

$(2)$ If $S$ contains $k$ elements, then $S$ contains no number less than $k$.

$\mathrm{(A) \ } 277 \mathrm{(B) \ } 311 \mathrm{(C) \ } 376 \mathrm{(D) \ } 377 \mathrm{(E) \ } 405$