Function Composition

合成関数は結合法則が成立します．証明(数学の景色様)
また$f$の定義の仕方により，最後に$(10^5+3)$で割った余りを求めるのも， 合成をしながら$(10^5+3)$で割った余りを求めるのも計算結果は変わりません．

よって，ダブリングテーブルを前計算しておくことによって 各クエリに時間計算量$O(\log n_i)$で答えることができます．
問題全体としての時間計算量は $m = \max (n_i),P=10^5+3$として $O((P+Q) \log m)$となり， この問題の条件下では十分高速です． 整数型のサイズに上限がある言語で実装する場合はオーバーフローに気を付けてください．

実装例