Страшний сон
Обмеження: 2 сек., 256 МіБ
Для того щоб прокинутись, обчисліть: \[result = \sum_{i=1}^{p} \prod_{j=0}^{m-1} \sum_{\substack{k=1, \\ k \equiv j \bmod m}}^{n} k^{i}.\]
Вхідні дані
Єдиний рядок містить три цілих числа \(p\), \(m\) і \(n\).
Вихідні дані
В одному рядку виведіть ціле число — результат за модулем простого числа \(10^9+7\).
Обмеження
\(1 \le p \le 10\),
\(1 \le m \le 50\),
\(1 \le n \le 10^{12}\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
2 3 8 | 277830 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
3 4 1 | 0 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 5 6 | 321427757 |
Примітки
\(a \equiv b\ (\bmod \ c)\) означає, що \(a\) й \(b\) конгруентні за модулем \(c\).
У першому прикладі відповідь дорівнює \((3+6)\cdot(1+4+7)\cdot(2+5+8)+(9+36)\cdot(1+16+49)\cdot(4+25+64)=277830\).
У другому прикладі відповідь — \(0 \cdot 1 \cdot 2 \cdot 3 + 0 \cdot 1 \cdot 4 \cdot 9 + 0 \cdot 1 \cdot 8 \cdot 27=0\).
Джерело: Відкрита індивідуальна першість ЛНУ 2021
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|