module mod_union_find
  implicit none
  type union_find
    integer :: n = 0
    integer, pointer :: par(:), rnk(:), siz(:) => null()
  contains
    procedure :: init => inituf
    procedure :: release => releaseuf
    procedure :: find => find
    procedure :: same => same
    procedure :: unite => unite
    procedure :: size => size_of
  end type
  interface union_find
    module procedure :: newuf
  end interface union_find
contains
  function newuf(n) result(ret)
    integer, intent(in) :: n
    type(union_find) :: ret
    integer :: i
    ret%n = n
    allocate(ret%par(n),ret%rnk(n),ret%siz(n))
    ret%rnk = 0
    ret%siz = 1
    ret%par = [(i,i=1,n)]
  end
  subroutine inituf(this,n)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: n
    integer :: i
    if (this%n /= n) then
      if (this%n /= 0) deallocate(this%par,this%rnk,this%siz)
      allocate(this%par(n),this%rnk(n),this%siz(n))
    end if
    this%n = n
    this%rnk = 0
    this%siz = 1
    this%par = [(i,i=1,n)]
  end
  subroutine releaseuf(this)
    class(union_find), intent(inout) :: this
    if (this%n /= 0) deallocate(this%par,this%rnk,this%siz)
    this%n = 0
  end
  recursive function find(this,i) result(ret)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: i
    integer :: ret
    if (this%par(i) /= i) this%par(i) = find(this,this%par(i))
    ret = this%par(i)
  end
  logical function same(this,i,j)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: i, j
    same = find(this,i) == find(this,j)
  end
  subroutine unite(this,i,j)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: i, j
    integer :: x, y
    x = find(this,i)
    y = find(this,j)
    if (x == y) return
    if (this%rnk(x) < this%rnk(y)) then
      this%par(x) = y
      this%siz(y) = this%siz(y)+this%siz(x)
    else
      this%par(y) = x
      this%siz(x) = this%siz(x)+this%siz(y)
      if (this%rnk(x) == this%rnk(y)) this%rnk(x) = this%rnk(x)+1
    end if
  end
  integer function size_of(this,i)
    class(union_find), intent(inout) :: this
    integer, intent(in) :: i
    size_of = this%siz(find(this,i))
  end
end module mod_union_find
program bichrome_spanning_tree
  use mod_union_find
  implicit none
  integer(8), parameter :: md = 1000000007_8
  type(union_find) :: uf
  integer :: n, m, e(2000,3) = 0, i, j
  integer(8) :: x, s, k1 = 1_8, k2 = 2_8
  read(*,*) n, m
  read(*,*) x
  do i = 1, m
    read(*,*) e(i,:)
  end do
  call merge_sort(e(1:m,:),3)
  do i = 2, m
    call uf%init(n)
    call uf%unite(e(i,1),e(i,2))
    s = int(e(i,3),8)
    do j = 1, m
      if (uf%same(e(j,1),e(j,2))) cycle
      call uf%unite(e(j,1),e(j,2))
      s = s+int(e(j,3),8)
    end do
    if (s > x) then
      k2 = mod(2_8*k2,md)
    else if (s == x) then
      k1 = mod(2_8*k1,md)
    end if
  end do
  write(*,'(i0)') mod((k1-1_8)*k2,md)
contains
  subroutine merge_sort(a,k)
    integer, intent(inout) :: a(:,:)
    integer, intent(in) :: k
    integer :: n, m, l, i, u
    n = size(a,1)
    m = n
    l = 1
    do while (m > 1)
      do i = 1, m/2
        u = min(2*i*l,n)
        call merger(a(2*(i-1)*l+1:(2*i-1)*l,:),a((2*i-1)*l+1:u,:),k)
      end do
      l = 2*l
      m = (m+1)/2
    end do
  end
  subroutine merger(a1,a2,k)
    integer, intent(inout) :: a1(:,:), a2(:,:)
    integer, intent(in) :: k
    integer :: a(size(a1,1)+size(a2,1),size(a1,2))
    integer :: i1, i2, n1, n2
    i1 = 1
    i2 = 1
    n1 = size(a1,1)
    n2 = size(a2,1)
    do while (i1 <= n1 .and. i2 <= n2)
      if (a1(i1,k) <= a2(i2,k)) then
        a(i1+i2-1,:) = a1(i1,:)
        i1 = i1+1
      else
        a(i1+i2-1,:) = a2(i2,:)
        i2 = i2+1
       end if
    end do
    if (i1 <= n1) then
      a(i1+i2-1:n1+n2,:) = a1(i1:n1,:)
    else
      a(i1+i2-1:n1+n2,:) = a2(i2:n2,:)
    end if
    a1 = a(1:n1,:)
    a2 = a(n1+1:n1+n2,:)
  end
end program bichrome_spanning_tree

Measured memory_bytes: 256