\(x=a+3b\ (0\leq a\leq 2)\) と置きます．すると，\((a+3b)^i\) のほとんどの部分は \(\mathrm{mod}\ 3^{19}\) で消えます．\(\sum p_i (a+3b)^i\) を分解して消えない部分を書き下すと

• \((3b)^0(p_0a^0+p_1a^1+p_2a^2+\ldots)\)
• \((3b)^1(1p_1a^0+2p_2a^1+3p_3a^2+\ldots)\)
• \(\vdots\)
• \(\displaystyle (3b)^k\sum_{i=0}^{\infty}\dbinom{i}{k}p_i a^{i-k}\)
• \(\vdots\) （\(k=18\) まで）

のようになり，これの総和が \(f(a+3b)\) になります．

よって，各 \(a, k (0\leq a\leq 2, 0\leq k\leq 18)\) に対して \(\displaystyle \sum_{i=0}^{\infty}\dbinom{i}{k}p_ia^{i-k}\) を前計算しておくことで，\(f(q_i)\) を \(1\) つあたり \(O(\log \mathrm{mod})\) で計算できます．

https://atcoder.jp/contests/xmascon25/submissions/71952203 (Python 4654ms)