The witch’s accountant

0

0 votes
Easy-Medium
Problem

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.

Input :

  • Two integers, N and M, denoting the number of rows and columns of the matrix respectively.
  • Then follow N lines each containing M characters.

Output :

  • Output a single integer, the price modulo 1000000007.

Constraints :

  • 1N, M3000
  • Matrix only contains lower-case English alphabets.

Note:

  • The Hamming distance between two strings of equal length is the number of positions at which the corresponding characters are different.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?