この値は非常に大きくなり得るので 1,000,000,007(=109+7) で割った値を求めよ。
と問題文に記載されてますが
割った余りを求めよの間違いでは？

間違いでした。修正しました。