The SumSum
Для данной конечной последовательности длины NN, a0,a1,a2,…,aN−1a_0,a_1, a_2,\ldots,a_{N-1}, давайте сначала удалим первый элемент последовательности. Затем определим последовательность частичных сумм ее оставшихся элементов как a1,a1+a2,a1+a2+a3,…,∑i=1N−1aia_1, a_1+a_2,a_1+a_2+a_3, \ldots ,\sum_{i=1}^{N-1} a_i.
Для этой последовательности длины N−1 повторим операции «удаления первого элемента» и «генерации новой последовательности из частичных сумм», чтобы получить последовательности длин N−2,N−3,N−4,…,N−(N−1)N-2, N-3, N-4, \ldots,N-(N-1), пока в итоге не получим последовательность из одного элемента. Мы называем этот элемент SumSum исходной последовательности.
Например, для 10-элементной последовательности 1,2,3,4,5,6,7,8,9,101, 2, 3, 4, 5, 6, 7, 8, 9, 10, SumSum этой последовательности равен 16,796.
Ваша цель: Для N=1010N=10^{10} и p=1010+19p=10^{10}+19 найдите SumSum по модулю pp последовательности a0,…,aN−1a_0,\ldots,a_{N-1}, определяемой как ai=(Ni)a_i={N \choose i}.
Бонус «*» будет присужден за нахождение для N=1011N=10^{11} и p=1011+3p=10^{11}+3 значения SumSum по модулю pp для последовательности, заданной как ai=13ia_i = 13^i.
