Distinct Islands

You are given a grid represented as a sequence of strings. Each string consists of characters '0' and '1' where '1' represents land and '0' represents water. An island is a group of adjacent lands connected horizontally or vertically. Two islands are considered the same (i.e. not distinct) if and only if one island can be translated (without rotation or reflection) to equal the other.

Your task is to determine the number of distinct islands in the given grid.

Note: The grid is provided as an input where the first line contains an integer n denoting the number of rows in the grid, and the following n lines each represent a row of the grid.

The relative positions of the cells in each island determine its signature. Islands with the same signature are not counted as distinct. When generating the signature, you may use \(\text{latex}\) for any formulas if necessary.

inputFormat

The input is given via standard input (stdin) and has the following format:

n
row1
row2
...
rown

Where n is the number of rows, and each row is a string comprising characters '0' and '1'. Note that the number of columns is equal to the length of the first row.

outputFormat

The output is a single integer (via standard output - stdout) which denotes the number of distinct islands in the grid.

## sample

4
1100
1100
0010
0000

2

</p>