module mod_sort
    implicit none
    private
    
    interface sort
        module procedure msort_int4, msort_int8, msort_int16, msort_string
    end interface sort

    interface swap
        module procedure swap_int4, swap_int8, swap_int16, msort_string
    end interface swap

    public :: sort, swap
        
contains
subroutine swap_int4(a, b)
    implicit none
    integer, intent(inout) :: a, b
    integer :: c

    c = a
    a = b
    b = c

end subroutine swap_int4

recursive subroutine msort_int4(x)
    implicit none
    integer, intent(inout) :: x(:)
    integer :: n, mid, i, j, k
    integer, allocatable :: tmp(:)

    n = size(x)

    if(n == 1) then
        return
    end if

    mid = n / 2
    call msort_int4(x(:mid))
    call msort_int4(x(mid+1:))

    allocate(tmp(n))
    tmp = x

    do k = n, mid+1, -1
        tmp(k) = x(mid + n - k + 1)
    end do

    i = 1
    j = n

    do k = 1, n
        if(tmp(i) <= tmp(j)) then
        x(k) = tmp(i)
        i = i + 1
        else
        x(k) = tmp(j)
        j = j - 1
        end if
    end do

    deallocate(tmp)
    return
end subroutine msort_int4

subroutine swap_int8(a, b)
    implicit none
    integer(8), intent(inout) :: a, b
    integer(8) :: c

    c = a
    a = b
    b = c

end subroutine swap_int8

recursive subroutine msort_int8(x)
    implicit none
    integer(8), intent(inout) :: x(:)
    integer :: n, mid, i, j, k
    integer(8), allocatable :: tmp(:)

    n = size(x)

    if(n == 1) then
        return
    end if

    mid = n / 2
    call msort_int8(x(:mid))
    call msort_int8(x(mid+1:))

    allocate(tmp(n))
    tmp = x

    do k = n, mid+1, -1
        tmp(k) = x(mid + n - k + 1)
    end do

    i = 1
    j = n

    do k = 1, n
        if(tmp(i) <= tmp(j)) then
        x(k) = tmp(i)
        i = i + 1
        else
        x(k) = tmp(j)
        j = j - 1
        end if
    end do

    deallocate(tmp)
    return
end subroutine msort_int8

subroutine swap_int16(a, b)
    implicit none
    integer(16), intent(inout) :: a, b
    integer(16) :: c

    c = a
    a = b
    b = c

end subroutine swap_int16

recursive subroutine msort_int16(x)
    implicit none
    integer(16), intent(inout) :: x(:)
    integer :: n, mid, i, j, k
    integer(16), allocatable :: tmp(:)

    n = size(x)

    if(n == 1) then
        return
    end if

    mid = n / 2
    call msort_int16(x(:mid))
    call msort_int16(x(mid+1:))

    allocate(tmp(n))
    tmp = x

    do k = n, mid+1, -1
        tmp(k) = x(mid + n - k + 1)
    end do

    i = 1
    j = n

    do k = 1, n
        if(tmp(i) <= tmp(j)) then
        x(k) = tmp(i)
        i = i + 1
        else
        x(k) = tmp(j)
        j = j - 1
        end if
    end do

    deallocate(tmp)
    return
end subroutine msort_int16

subroutine swap_string(a, b, d)
    implicit none
    integer :: d
    character(d), intent(inout) :: a, b
    character(d) :: c

    c = a
    a = b
    b = c

end subroutine swap_string

recursive subroutine msort_string(x, d)
    implicit none
    integer :: d
    character(d), intent(inout) :: x(:)
    integer :: n, mid, i, j, k
    character(d), allocatable :: tmp(:)

    n = size(x)

    if(n == 1) then
        return
    end if

    mid = n / 2
    call msort_string(x(:mid), d)
    call msort_string(x(mid+1:), d)

    allocate(tmp(n))
    tmp = x

    do k = n, mid+1, -1
        tmp(k) = x(mid + n - k + 1)
    end do

    i = 1
    j = n

    do k = 1, n
        if(tmp(i) <= tmp(j)) then
        x(k) = tmp(i)
        i = i + 1
        else
        x(k) = tmp(j)
        j = j - 1
        end if
    end do

    deallocate(tmp)
    return
end subroutine msort_string
end module mod_sort

program prob
    use mod_sort
    implicit none
    integer(8) :: n
    integer(8), allocatable :: a(:)
    integer(8) :: p(10)
    integer(8) :: s(10)
    integer(8) :: i, j
    integer(8) :: ans
    integer(8) :: cnt
    character(10) :: tmp
    integer(8) :: inttmp
 
    read(*,*) n
    allocate(a(n))
 
    p(1) = 1
    do i = 2, 10
        p(i) = p(i-1) * 32
    end do
    do i = 1, n
        read(*,*) tmp
        do j = 1, 10
            s(j) = ichar(tmp(j:j)) - ichar('a')
        end do
        call sort(s)
        a(i) = dot_product(s, p)
    end do
 
    call sort(a)
 
    cnt = 1
    inttmp = a(1)
    ans = 0
    do i = 2, n
        if(a(i) == inttmp)then
            cnt = cnt + 1
        else
            ans = ans + cnt * (cnt - 1) / 2
            inttmp = a(i)
            cnt = 1
        end if
    end do
    ans = ans + cnt * (cnt - 1) / 2
 
    write(*,*) ans
 
    deallocate(a)
     stop
contains
end program prob


Measured memory_bytes: 4308