237 : 4 × n のゲーム盤上を進む順路

$T(n)$を、以下のルールに従い4 × n のゲーム盤上を進む順路の数と定義する：

• 左上の角から始める

• 1マス分の上下左右の移動を繰り返す

• 各マスを全てちょうど1回ずつ通る

• 左下の角で終わる

下の図は 4 × 10 の盤上の順路の一例である：

$T(10)$は 2329 である。$T(10^{12})$を$10^8$で割った余りを求めよ。