Пусть 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⁹+7 = 325951319.

Найдите S(9,10,1112131415) mod 10⁹+7.