お題、灘中入試っぽい問題

開始点S から、終点G まで、最短距離9 で移動する方法は、何通りあるか？

移動は右か下へ、1ずつ移動できるが、* は通れない所である。
数字は通れる所で、単に分かりやすくするために座標を書いただけで、移動コストではない

S23456
12*456
1234*6
123456
12345G