Пусть $P_{a,b}$ обозначает путь на координатной сетке $a\times b$ со следующими свойствами:

• Путь начинается в точке $(0,0)$ и заканчивается в точке $(a,b)$.
• Путь состоит только из единичных шагов в направлении вверх или направо, т.е. координаты с каждым шагом увеличиваются.

Обозначим площадь под путем $A(P_{a,b})$. На примере пути $P_{4,3}$, данном ниже, площадь равна 6.

Определим $G(P_{a,b},k)=k^{A(P_{a,b})}$. Пусть $C(a,b,k)$ будет равно сумме $G(P_{a,b},k)$ для всех отвечающих требованиям путей на координатной сетке $a\times b$.

Известно, что

• $C(2,2,1)=6$
• $C(2,2,2)=35$
• $C(10,10,1)=184\,756$
• $C(15,10,3) \equiv 880\,419\,838 \mod 1\,000\,000\,007$
• $C(10\,000,10\,000,4) \equiv 395\,913\,804 \mod 1\,000\,000\,007$

Вычислите $\displaystyle\sum_{k=1}^7 C(10^k+k, 10^k+k,k)$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$