Bellatrix Lestrange is a sinister, but a very astute witch. After Lord Voldemort’s downfall, she now runs a fortune-telling business for which her primary tool is a character matrix which she uses to con her customers as follows:
a) She places her finger on any cell in the first column and starts tracing it through the matrix. From each cell she moves to immediate next cell (straight or diagonally) in the next column and continues the process till she reaches the last column (but not moving out of the matrix in the way). Thus a string is formed comprising of the letters she picked along the way, arranged chronologically.
b) After forming all possible strings using the above process, she computes the sum of pair-wise hamming distance for them. This is the price that she demands for her services.
Seeing as there is no spell to calculate the price that she can expect from a given matrix, you are asked to find the result modulo 1000000007.
The Possible Strings formed are : “ab”, “ad”, “cb”, “cd”
Hamming(“ab”, “ad”) = 1
Hamming(“ab”, “cb”) = 1
Hamming(“ab”, “cd”) = 2
Hamming(“ad”, “cb”) = 2
Hamming(“ad”, “cd”) = 1
Hamming(“cb”, “cd”) = 1
Answer : (1 + 1 + 2 + 2 + 1 + 1) % 1000000007 = 8.