Crazy squares!!!

A integer, positive number of small identical squares form a big square with a side of N small squares. These small squares can be connected forming rectangles and squares. It is posible to use any number of squares, mínimum 1 and máximum the number of small squares the big square has. Small squares can only be connected with squares that are adjacent, but the adjacent ones can be connected to other that are adjacent forming bigger structures. Example of square: a N=2 square side has 9 connections because it is posible to form 9 different squares/rectangles:the 4 small initial squares, the big square formed with 4 squares and 4 rectangles formed with 2 squares each. Find the last three digits of the number of connections that are posible to form in a square with a side of 73 small squares.