module module_modint
    use, intrinsic :: iso_fortran_env
    implicit none
    private
    public :: modint, set_modulus, modulo_utils, permutation, combination

    type modint
        private
        integer(int64) :: val
    contains
        procedure :: n => get
        procedure :: add
        procedure :: sub
        procedure :: mul
        procedure :: inv
        procedure :: div
        procedure :: pow
        generic :: operator(+) => add
        generic :: operator(-) => sub
        generic :: operator(*) => mul
        generic :: operator(/) => div
        generic :: operator(**) => pow
    end type

    integer(int64) :: modulus = 1000000007
    type(modint), allocatable :: f(:), invf(:)

    interface modint
        module procedure :: init_modint
    end interface modint

    interface modulo_utils
        module procedure :: init_modulo_utils
    end interface modulo_utils

contains

    elemental integer(int64) function mval(i) result(res)
        integer(int64), intent(in) :: i

        if ( (0_int64 <= i) .and. (i < modulus) ) then
            res = i
        else
            res = modulo(i, modulus)
        endif

    end function mval


    elemental integer(int64) function to_int64(i) result(res)
        class(*), intent(in) :: i

        select type(i)
        type is (integer(int64))
            res = int(i, int64)
        type is (integer(int32))
            res = int(i, int64)
        type is (integer(int16))
            res = int(i, int64)
        type is (integer(int8))
            res = int(i, int64)
        end select

    end function to_int64


    subroutine set_modulus(m)
        class(*), intent(in) :: m

        select type(m)
        type is (modint)
            modulus = m%val
        class default
            modulus = to_int64(m)
        end select

    end subroutine set_modulus


    elemental type(modint) function init_modint(i) result(res)
        class(*), intent(in) :: i

        select type(i)
        type is (modint)
            res%val = i%val
        class default
            res%val = mval( to_int64(i) )
        end select

    end function init_modint


    elemental function get(this) result(res)
        class(modint), intent(in) :: this
        integer(int64) :: res

        res = this%val

    end function get


    elemental type(modint) function add(this, other) result(res)
        class(modint), intent(in) :: this
        type(modint), intent(in) :: other

        res%val = mval( this%val + other%val )

    end function add


    elemental type(modint) function sub(this, other) result(res)
        class(modint), intent(in) :: this
        type(modint), intent(in) :: other

        res%val = mval( this%val - other%val )

    end function sub


    elemental type(modint) function mul(this, other) result(res)
        class(modint), intent(in) :: this
        type(modint), intent(in) :: other

        res%val = mval( this%val * other%val )

    end function mul


    elemental type(modint) function div(this, other) result(res)
        class(modint), intent(in) :: this
        type(modint), intent(in) :: other

        res = this%mul( other%inv() )

    end function div


    elemental type(modint) function inv(this) result(res)
        class(modint), intent(in) :: this
        integer(int64) :: a, b, u, v, t, n

        a = this%val
        b = modulus
        u = 1
        v = 0

        do while ( b /= 0 )
            t = a / b
            a = a - t * b
            n = b
            b = a
            a = n
            u = u - t * v
            n = v
            v = u
            u = n
        enddo

        res%val = modulo(u, modulus)

    end function inv

    elemental type(modint) function pow(this, other) result(res)
        class(modint), intent(in) :: this
        class(*), intent(in) :: other
        integer(int64) :: n
        type(modint) :: i

        res%val = mval( to_int64(1) )
        i%val = this%val
        n = to_int64(other)

        do while (n > 0_8)
            if (btest(n, 0)) res = res%mul(i)
            i = i%mul(i)
            n = rshift(n, 1)
        end do

    end function pow

    subroutine init_modulo_utils(i)
        class(*), intent(in) :: i
        integer(int64) :: k, n

        if ( allocated(f) ) deallocate(f)
        if ( allocated(invf) ) deallocate(invf)

        select type(i)
        type is (modint)
            n = i%val
        class default
            n = to_int64(i)
        end select

        allocate( f(0:n) )
        allocate( invf(0:n) )

        f(0) = modint(1)
        do k = 1, n
            f(k) = f(k-1) * modint(k)
        enddo

        invf(n) = f(n)%inv()
        do k = n, 1, -1
            invf(k-1) = invf(k) * modint(k)
        enddo

    end subroutine init_modulo_utils


    type(modint) function permutation(n, k)
        class(*), intent(in) :: n, k
        integer(int64) :: nt, kt

        select type(n)
        type is (integer(int64))
            nt = n
        class default
            nt = to_int64(n)
        end select

        select type(k)
        type is (integer(int64))
            kt = k
        class default
            kt = to_int64(k)
        end select

        if ( (kt > nt) .or. (nt < 0) .or. (kt < 0) ) return
        permutation = f(nt) * invf(nt-kt)

    end function permutation


    type(modint) function combination(n, k)
        class(*), intent(in) :: n, k
        integer(int64) :: nt, kt

        select type(n)
        type is (integer(int64))
            nt = n
        class default
            nt = to_int64(n)
        end select

        select type(k)
        type is (integer(int64))
            kt = k
        class default
            kt = to_int64(k)
        end select

        combination = permutation(nt, kt) * invf(kt)

    end function combination

end module module_modint

program main
    use iso_fortran_env
    use module_modint
    implicit none
    integer(int64) :: n, m, k
    type(modint) :: a, b, c, d, ans

    read *, n, m
    call modulo_utils(m)
    ans = modint(0)

    d = permutation(m, n)

    do k = 0, n
        a = permutation(m-k, n-k)
        b = combination(n, k)
        c = (modint(-1)) ** k
        ans = ans + a * b * c
    enddo

    ans = ans * d

    print *, ans%n()

end program main


Measured memory_bytes: 10676