\(s_1=\)L, \(s_{N+M}=\)R のケースを解きます． その他のケースは以下と同様に解けます．

すぬけ君が折り返す（進行方向が変わる）タイミングのみを考えます．便利のため，最後の子供を捕まえたタイミングも折り返しのタイミングだと考えます． 座標が負の地点で折り返す回数を \(k\) とおきます． まず，折り返すときに捕まえた子供の集合を決めると，これを達成する \(s\) がちょうど一つ存在するので，折り返すときに捕まえた子供の集合すべてについてゲーム終了までの時間を考えます．

ゲーム終了までの時間を式で書くと，各折り返しについてなんらかの値を足すという形になります． より具体的には，負の座標で \(j\) 回目に折り返したとき，最初座標 \(-L_i\) にいた子供を捕まえたとすると，最終的なゲーム終了時刻への寄与は，\(4L_i \times 9^{k-j}\) となります． 正の座標での折り返しも同様な式になるため，以下では負の折り返しの寄与だけ計算します．

左端と右端の子供は必ず折り返しに使うため，これ以外の子供に注目してみます． 結局，以下の問題が解ければよいです．

• 各 \(1 \leq k\) について，以下の和を求めよ．
  • 数列 \((L_1,L_2,\cdots,L_{N-1})\) から \(k-1\) 個選ぶ．また，\((R_1,R_2,\cdots,R_{M-1})\) からも \(k-1\) 個選ぶ．これらの方法すべてについて，\(L_i\) が \(j\) 番目に選ばれたなら，\(4L_i \times 9^{k-j}\) を足す．

まず，\(L_i\) を反転することで，選ばれた \(j\) 番目の値について\(4L_i \times 9^j\) を足す，と変形します． つぎに，「\((R_1,R_2,\cdots,R_{M-1})\) から \(k-1\) 個選ぶ」のではなく，「\((R_1,R_2,\cdots,R_{M-1})\) から折り返しに使わない \(M-k\) 個を選ぶ」とします．これを \(k\) を動かして和を取ると，\(L,R\) から合計で \(M-1\) 個選ぶ方法をすべて試す，ということになります．

結局，以下の問題が解ければよいです．

• 長さ \(N-1+M-1\) の列から \(M-1\) 個のものを選ぶ．各 \(1 \leq i \leq N-1\) について，\(i\) が \(j\) 番目に選ばれた場合は \(9^j\) の重みを足す．各 \(i\) について，選び方すべてについての重みの総和を求めよ．

これを式で書くと，各 \(i\) について \(\sum_j \binom{i-1}{j-1} \times \binom{N+M-2-i}{M-1-j} \times 9^j\) となります． この式は，\(i\) に依存する項，\(j\) に依存する項，そして \(i-j\) に依存する項の積で書けるため，FFT を用いると，すべての \(i\) について上の値を \(O(N\log N)\) で計算できます．

省略した左端や右端の子供に関する寄与は個別に計算できます． よって，この問題は \(O(N \log N)\) で解けます．