get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_number(A, B) :-
    get_number(A),
    get_number(B).

get_number(A, B, C) :-
    get_number(A, B),
    get_number(C).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n\r\t', '', _, String).

get_chars(Xs) :-
    get_string(S),
    string_chars(S, Xs).

get_numbers(0, []).
get_numbers(N, [X|Xs]) :- 
    get_number(X), 
    N2 is N - 1, 
    get_numbers(N2, Xs).

get_numbers_2(0, _, []).
get_numbers_2(N1, N2, [X|Xs]) :- 
    get_numbers(N2, X), 
    N12 is N1 - 1, 
    get_numbers_2(N12, N2, Xs).

put_numbers([]).
put_numbers([X|Xs]) :-
    writeln(X),
    put_numbers(Xs).

get_i_to_x_rbtree0(N, T) :-
    rb_empty(T2),
    get_i_to_x_rbtree(N, 0, T2, T).

get_i_to_x_rbtree1(N, T) :-
    rb_empty(T2),
    get_i_to_x_rbtree(N, 1, T2, T).

get_i_to_x_rbtree(0, _, T, T).
get_i_to_x_rbtree(N, I, T2, T) :-
    get_number(X),
    rb_insert(T2, I, X, T3),    
    N2 is N - 1,
    I2 is I + 1,
    get_i_to_x_rbtree(N2, I2, T3, T).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)
    length(S, L),
    sub_string

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==

    between(L,U,X): L <= X <= U
    nth0(I, Xs, Y), nth1(I, Xs, Y): (Xs,Y) -> I, (I, Xs) -> Y 

    sort(Key, Order, List, Sorted): Keyは通常0?, Orderは=なしが重複削除，=は重複保持
    \+ P(X) : not P(X)

    sum_list(Xs, Sum)

    orは!忘れに注意(末尾再帰なら直前)

    include(f, Xs, Ys) : filter f

    findall(使う変数のタプル, (hoge), hogeが通るタプルのリスト)
*/

facts(N, M, T) :- 
    rb_empty(C), 
    rb_insert(C, 0, 1, C2),
    P is 1,
    facts(N, 1, P, M, C2, T).

facts(N, I, _, _, C, C) :- N < I, !.
facts(N, I, P, M, C, T) :-
    X is P * I mod M,
    rb_insert(C, I, X, C2),
    I2 is I + 1,
    facts(N, I2, X, M, C2, T).

mod_pow(_, 0, _, 1) :- !.
mod_pow(X, N, M, Z) :-
    N mod 2 =:= 0, !,
    X2 is X * X mod M,
    N2 is N div 2,
    mod_pow(X2, N2, M, Z).
mod_pow(X, N, M, Z) :-
    N mod 2 =:= 1, !,
    X2 is X * X mod M,
    N2 is N div 2,
    mod_pow(X2, N2, M, Z2),
    Z is Z2 * X mod M.

mod_div(X, Y, M, Z) :-
    T is M - 2,
    mod_pow(Y, T, M, Y_inv),
    Z is X * Y_inv mod M.

nCr(N, R, M, T, Z) :-
    rb_lookup(N, A, T),
    U is N - R,
    rb_lookup(U, B, T),
    rb_lookup(R, C, T),
    D is B * C mod M,
    mod_div(A, D, M, Z).

nPr(N, R, M, T, Z) :-
    rb_lookup(N, A, T),
    U is N - R,
    rb_lookup(U, B, T),
    D is B mod M,
    mod_div(A, D, M, Z).

f(N, _, I, _, _, C, C) :- N < I, !.

f(N, M, I, MOD, T, C, Z) :-
    I mod 2 =:= 0, !,
    nCr(N, I, MOD, T, A),
    MM is M - I,
    NN is N - I,
    nPr(MM, NN, MOD, T, B),
    C2 is (C + (A * B mod MOD)) mod MOD,
    I2 is I + 1,
    f(N, M, I2, MOD, T, C2, Z). 

f(N, M, I, MOD, T, C, Z) :-
    I mod 2 =:= 1, !,
    nCr(N, I, MOD, T, A),
    MM is M - I,
    NN is N - I,
    nPr(MM, NN, MOD, T, B),
    C2 is (C + MOD - (A * B mod MOD)) mod MOD,
    I2 is I + 1,
    f(N, M, I2, MOD, T, C2, Z). 
    
main :-
    MOD is 1_000_000_007,
    get_number(N, M),
    facts(max(N, M) + 100, MOD, T),
    f(N, M, 0, MOD, T, 0, Z),
    nPr(M, N, MOD, T, V),
    Z2 is Z * V mod MOD,    
    writeln(Z2).

    % statistics(inferences, IC), writeln(IC).
