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

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

3 seconds
256 megabytes
Medium

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

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

Input

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

Output

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

У першому прикладі будь-яка пара масивів ([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]).