Конфігурації мінімумів#12915

Конфігурації мінімумів

3 секунди
256 мегабайтів
Середня

Задано два цілі числа та . Знайдіть кількість пар цілих масивів довжиною , для яких виконуються наступні умови:

Оскільки ця кількість може бути великою, виведіть її за модулем .

Вхідні дані

У єдиному рядку вводу містяться два цілі числа (1 \leq n, m \leq 10^6).

Вихідні дані

Виведіть одне ціле число  — відповідь до задачі за модулем .

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі будь-яка пара масивів ([x], [y]) з 1 \leq x, y \leq 3 задовольняє умовам задачі, їх .

У другому прикладі ось відповідні пари масивів:

  • ([1, 1], [1, 1]);

  • ([1, 1], [1, 2]);

  • ([1, 1], [2, 1]);

  • ([1, 1], [2, 2]);

  • ([1, 2], [1, 1]);

  • ([1, 2], [1, 2]);

  • ([2, 1], [1, 1]);

  • ([2, 1], [2, 1]);

  • ([2, 2], [1, 1]);

  • ([2, 2], [2, 2]).