Statement

In recent months, William has become passionate about word search puzzles. A word search puzzle consists of a grid of letters, in which there are one or more words to be searched in a vertical, horizontal or diagonal way. William's version of this puzzle is a bit harder. There is only one word to be searched, but you are not limited to vertical/horizontal/diagonal words. You can compose a word in any way you like, starting from some letter and moving in any direction as long as you move to an adjacent cell: that means, you can move in 8 possible directions (two vertical, two horizontal and four diagonal). Note that William's rules do not forbid you to step on the same letter more than once: you have the freedom to compose the word even by reusing letters. Compute how many times a given word appears in the word puzzle. This number can be quite large, so it's enough to print its value modulo 1000000007.