問題
atcoder.jp
ただし、答えは非常に大きくなる可能性があるので、(109+7)で割った余りを出力してください。
解法（実装）
解法については、公式解説などを読んでもらうとして、実装上の気付きをメモ。
この問題、(109+7)で割った余りを出力という指定があるが、全部計算してから余り計算だと計算途中の桁が大きくなりすぎるためだろうが、計算時間がかかりPythonではTLEになってしまう。
ループで行われる掛け算の1回1回のあとに(109+7)で余り計算をすることで、実行速度が速くなりACとなる。
実装
