令 $F(r,c,n)$ 为对具有 $r$ 行和 $c$ 列的矩形网格进行着色的方法数，使用最多 $n$ 种颜色，使得没有两个相邻单元格共享相同的颜色。彼此成对角线的单元格不被视为相邻。

例如，$F(2,2,3)=18$、$F(2,2,20)=130340$ 和 $F(3,4,6)=102923670$。

设 $S(r,c,n)=\sum _{k=1}^{n}F(r,c,k)$。

例如，$S(4,4,15)mod{10}^9+7=325951319$。

求 $S(9,10,1112131415)mod{10}^9+7$。