Фермер Джон (снова) придумал новый режим утренней зарядки для коров!

Как и прежде, n коров фермера Джона выстроились в линию. i - ая корова слева имеет метку i для каждого i (1 ≤ i ≤ n). Он говорит им повторять следующий шаг до тех пор, пока коровы не будут в том же порядке, что и при старте.

Дана перестановка A длины n, коровы меняют свой порядок так, что i-ая корова слева до изменения становится Ai-ой слева после изменения.

Например, если A = (1, 2, 3, 4, 5) то коровы совершают один шаг. Если A = (2, 3, 1, 5, 4), то коровы совершат шесть шагов. Порядок коров слева направо после каждого шага будет следующим:

0 шаг: (1, 2, 3, 4, 5)

1 шаг: (3, 1, 2, 5, 4)

2 шаг: (2, 3, 1, 4, 5)

3 шаг: (1, 2, 3, 5, 4)

4 шаг: (3, 1, 2, 4, 5)

5 шаг: (2, 3, 1, 5, 4)

6 шаг: (1, 2, 3, 4, 5)

Вычислите произведение количества шагов, необходимых для всех n! возможных перестановок A длины n.

Поскольку это число может быть очень большим, выведите ответ по модулю m.

Участники, использующие C++, могут найти следующий код из KACTL полезным. Известный как редукция Барретта, он позволяет вычислять a % b в несколько раз быстрее обычного, где b > 1 константа, неизвестная во время компиляции (к сожалению, нам не известно о такой оптимизации для Java).

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};
FastMod F(2);

int main() {
    int M = 1000000007; F = FastMod(M);
    ull x = 10ULL*M+3; 
    cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}

Входные данные

В одной строке заданы числа n (1 ≤ n ≤ 7500) и m (108 ≤ m ≤ 109 + 7, m простое).

Выходные данные

Выведите одно число.

Пример

Для каждого i (1 ≤ i ≤ n), i - ый элемент следующего массива - это количество перестановок, которые заставляют коров делать i шагов: [1, 25, 20, 30, 24, 20]. Ответ равен 11 * 225 * 320 * 430 * 524 * 620 = 369329541 (mod 109 + 7).