2009 Fermat Problem 24

Starting with the input (m, n), Machine A gives the output (n,\ \text{m}). Starting with the input (m, n), Machine B gives the output (m + 3n, n). Starting with the input (m, n), Machine C gives the output (m - 2n, n). Natalie starts with the pair (0, 1) and inputs it into one of the machines. She takes the output and inputs it into any one of the machines. She continues to take the output that she receives and inputs it into any one of the machines. (For example, starting with (0, 1), she could use machines B, B, A, C, B in that order to obtain the output (7, 6).) Which of the following pairs is impossible for her to obtain after repeating this process any number of times?

\textbf{(A)}\ (2009,1016)\quad \textbf{(B)}\ (2009,1004)\quad \textbf{(C)}\ (2009,1002)\quad \textbf{(D)}\ (2009,1008)\quad \textbf{(E)}\ (2009,1032)

If there are no answer choices shown, enter a numerical answer.

Full credit to this problem is given to the CEMC, you may view all Fermat contests here.