1998 AIME Problem 13

If \left\{a_{1}, a_{2}, a_{3}, \ldots, a_{n}\right\} is a set of real numbers, indexed so that a_{1}<a_{2}<a_{3}<\ldots<a_{n}, its complex power sum is defined to be a_{1} i+a_{2} i^{2}+a_{3} i^{3}+\cdots+a_{n} i^{n}, where i^{2}=-1. Let S_{n} be the sum of the complex power sums of all nonempty subsets of \{1,2, \ldots, n\}. Given that S_{8}=-176-64 i and S_{9}=p+q i, where p and q are integers, find |p|+|q|.