\(s\) の先頭の F の数だけ進めておく. この座標を \((x_0, 0)\) とする.

残りは T が現れると上下好きな方向に移動でき, さらに T が現れると左右好きな方向に移動でき,… と続く.

上下方向に移動できる距離を \(\{ u_i \}\), 左右方向に移動できる距離を \(\{ v_i \}\) とする.

以降は上下方向と左右方向は別々に考えていい.

\(i\) 回目の上下方向の移動ごとに \(u_i\) か \(-u_i\) 移動できるので, DPを使って計算すればいい. ビットシフトとビットORで計算できるので高速に計算できる.

左右方向の移動も同様である.