AMC 12 2013a Problem 7

The sequence $S_1, S_2, S_3, \cdots, S_{10}$ has the property that every term beginning with the third is the sum of the previous two. That is, $$S_n = S_{n-2} + S_{n-1} \text{ for } n \ge 3.$$ Suppose that $S_9 = 110$ and $S_7 = 42$. What is $S_4$?

\textbf{(A)}\ 4 \textbf{(B)}\ 6 \textbf{(C)}\ 10 \textbf{(D)}\ 12 \textbf{(E)}\ 16