31275번 - СТЕПЕН 다국어

문제

Дадена е таблица, съставена от n + 1 реда и n стълба. В първия ред на таблицата са записани цели положителни числа, а на следващите n реда са пресметнати и записани съответно вторите, третите и т. н. степени на числата от първия ред.

Например, в следващата таблица n = 4 и тя съдържа степените на числата 3, 5, 2 и 1 до петата им степен:

Напишете програма power, която събира числата от диагонала на таблицата (както е показан на фигурата с получерен шрифт) и извежда резултата по модул, който е зададен като цяло положително число m.

За примера, ако m = 3, тогава резултатът ще бъде 1, защото остатъкът при делене с 3 на сумата 9+125+16+1 е равен на 1.

입력

От първия ред на стандартния вход програмата въвежда целите положителни числа n и m. На втория ред във входа са записани (разделени с интервали) числата от първия ред на таблицата.

출력

Програмата трябва да изведе на стандартния изход пресметнатата сума като едно цяло число.

제한

• n ≤ 1000000
• m ≤ 10000000
• Числата в първи ред на таблицата са цели, положителни и са по-малки от 100 000.

힌트