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

module module_sort
    use iso_fortran_env
    implicit none

    interface quicksort
        module procedure :: int32_qsort
        module procedure :: int64_qsort
    end interface quicksort
contains

    recursive function int32_qsort(m) result(res)
        integer(int32), intent(in) :: m(:)
        integer(int32) :: n, pm, pn, pv, res(size(m))

        n = size( m, 1 )

        if (n <= 1) then
          res = m
        else
          pv = m( n/2 )
          pm = max( m(1), m(n) )
          pn = min( m(1), m(n) )
          if ( pv > pm ) pv = pm
          if ( pv < pn ) pv = pn
          res = [ int32_qsort( pack(m(:), m(:) > pv) ), &
                               pack(m(:), m(:) == pv), &
                  int32_qsort( pack(m(:), m(:) < pv) ) ]
        endif

    end function int32_qsort

    recursive function int64_qsort(m) result(res)
        integer(int64), intent(in) :: m(:)
        integer(int64) :: n, pm, pn, pv, res(size(m))

        n = size( m, 1 )

        if (n <= 1) then
          res = m
        else
          pv = m( n/2 )
          pm = max( m(1), m(n) )
          pn = min( m(1), m(n) )
          if ( pv > pm ) pv = pm
          if ( pv < pn ) pv = pn
          res = [ int64_qsort( pack(m(:), m(:) > pv) ), &
                               pack(m(:), m(:) == pv), &
                  int64_qsort( pack(m(:), m(:) < pv) ) ]
        endif

    end function int64_qsort

end module module_sort


program main
    use module_modint
    use module_sort
    use iso_fortran_env
    implicit none
    integer(int64) :: n, k
    integer(int64),allocatable :: ai(:)
    integer(int64),allocatable :: ma(:), pa(:)
    integer(int64) :: mi, pi, i, mmax, pmax
    type(modint) :: ans

    read *, n, k
    allocate( ai(n) )
    read *, ai(1:n)
    ans = modint(1)

    if ( n == k ) then
        do i = 1, k
            ans = ans * modint( ai(i) )
        enddo
        print *, ans%n()
        stop
    endif

    allocate( ma(1) )
    allocate( pa(1) )

    ma = pack( ai, ai < 0 )
    pa = pack( ai, ai >= 0 )

    if ( size( ma, 1 ) == 0 ) then
        pa = quicksort( pa )
        do i = 1, k
            ans = ans * modint( pa(i) )
        enddo
        print *, ans%n()
        stop
    endif

    if ( size( pa, 1 ) == 0 ) then
        ma = quicksort( ma )
        if ( mod(k, 2) == 0 ) then
            ma( size(ma,1):1:-1 ) = ma(:)
            do i = 1, k
                ans = ans * modint( ma(i) )
            enddo
        else
            do i = 1, k
                ans = ans * modint( ma(i) )
            enddo
        endif
        print *, ans%n()
        stop
    endif

    ma = quicksort( ma )
    ma( size(ma,1):1:-1 ) = ma(:)
    pa = quicksort( pa )

    pi = 1
    mi = 1
    pmax = size(pa, 1)
    mmax = size(ma, 1)
    i = 0
    do
        if ( i == k ) then
            print *, ans%n()
            stop
        else
            if ( (pi <= pmax) .and. (mi <= mmax-1) ) then
                if ( i <= k-2 ) then
                    if ( (pa(pi) * pa(pi+1)) >= (ma(mi) * ma(mi+1)) ) then
                        ans = ans * modint(pa(pi))
                        pi = pi + 1
                        i = i + 1
                    else
                        ans = ans * modint(ma(mi)) * modint(ma(mi+1))
                        mi = mi + 2
                        i = i + 2
                    endif
                else
                    ans = ans * modint( pa(pi) )
                    pi = pi + 1
                    i = i + 1
                endif
            elseif ( pi > pmax ) then
                ans = ans * modint( ma(mi) )
                mi = mi + 1
                i = i + 1
            elseif ( mi > mmax-1 ) then
                ans = ans * modint( pa(pi) )
                pi = pi + 1
                i = i + 1
            endif
        endif
    enddo

end program main

Measured memory_bytes: 11836