module mod_t_list
  implicit none
  type :: t_list
    integer :: vol
    integer, pointer :: arr(:)
  end type t_list
  private
  public :: t_list, init_list, push_back, pop_back
  public :: poll_back, get_at, size_of_list
contains
  subroutine init_list(list)
    implicit none
    type(t_list), intent(inout) :: list
    list%vol = 0
    nullify(list%arr)
    allocate(list%arr(1))
    return
  end subroutine init_list
  subroutine push_back(list,n)
    implicit none
    type(t_list), intent(inout) :: list
    integer, intent(in) :: n
    integer, allocatable :: tmp(:)
    if (size(list%arr).eq.list%vol) then
      allocate(tmp(list%vol))
      tmp = list%arr
      deallocate(list%arr)
      allocate(list%arr(2*list%vol))
      list%arr(1:list%vol) = tmp
      deallocate(tmp)
    end if
    list%vol = list%vol+1
    list%arr(list%vol) = n
    return
  end subroutine push_back
  function pop_back(list) result(n)
    implicit none
    type(t_list), intent(inout) :: list
    integer :: n
    n = list%arr(list%vol)
    list%vol = list%vol-1
    return
  end function pop_back
  subroutine poll_back(list)
    implicit none
    type(t_list), intent(inout) :: list
    list%vol = list%vol-1
    return
  end subroutine poll_back
  function get_at(list,i) result(n)
    implicit none
    type(t_list), intent(in) :: list
    integer, intent(in) :: i
    integer :: n
    n = list%arr(i)
    return
  end function get_at
  function size_of_list(list) result(s)
    implicit none
    type(t_list), intent(in) :: list
    integer :: s
    s = list%vol
    return
  end function size_of_list
end module mod_t_list
module mod_t_graph
  use mod_t_list
  implicit none
  integer(8), parameter :: md = 1000000007_8
  logical, allocatable :: used(:)
  integer(8) :: k
  type :: t_graph
    type(t_list), pointer :: edges(:)
  end type t_graph
  private
  public :: k, t_graph, init_graph, add, dfs
contains
  subroutine init_graph(graph,n)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer, intent(in) :: n
    integer :: i
    allocate(used(n))
    used = .false.
    allocate(graph%edges(n))
    do i = 1, n
      call init_list(graph%edges(i))
    end do
    return
  end subroutine init_graph
  subroutine add(graph,i,pos)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer, intent(in) :: i, pos
    call push_back(graph%edges(i),pos)
    return
  end subroutine add
  recursive subroutine dfs(graph,v,m)
    implicit none
    type(t_graph), intent(in) :: graph
    integer, intent(in) :: v
    integer(8), intent(inout) :: m
    integer :: i, e
    integer(8) :: x, c
    used(v) = .true.
    c = 1_8
    do i = 1, size_of_list(graph%edges(v))
      e = get_at(graph%edges(v),i)
      if (used(e)) c = c+1_8
    end do
    do i = 1, size_of_list(graph%edges(v))
      e = get_at(graph%edges(v),i)
      if (used(e)) cycle
      m = mod(m*max(0_8,k-c),md)
      c = c+1_8
      call dfs(graph,e,m)
    end do
    return
  end subroutine dfs
end module mod_t_graph
program virus_tree_2
  use mod_t_graph
  implicit none
  type(t_graph) :: tree
  integer :: n, a, b, i
  integer(8) :: m
  read(*,*) n, k
  call init_graph(tree,n)
  do i = 1, n-1
    read(*,*) a, b
    call add(tree,a,b)
    call add(tree,b,a)
  end do
  m = k
  call dfs(tree,1,m)
  write(*,'(i0)') m
  stop
end program virus_tree_2

Measured memory_bytes: 17408