Let $f(i)= \begin{cases} f(i-1)+2f(i-2)+4f(i-3), i>3\\ i, i\le3 \end{cases}$

We define a polynomial $p(x)=x^n+a_{n-1}x^{n-1}+...+a_1x+a_0$ where ${a_i=f(2^i)}$ mod $M$

Let the roots of $P(x)$ be $b_1,b_2,...,b_n$

Let $$S(k)=\sum_{i=1}^{n}{b_i^{k}}$$

Find $S(k)$ mod $M$. for $n=60,~k=123456789987654321,~M=998244353$