John is obsessed with security.
He is writing a letter to his friend Brus and he wants nobody else to be able to read it.
He uses a simple substitution cipher to encode his message.
Each letter in the message is replaced with its corresponding letter in a substitution alphabet.
A substitution alphabet is a permutation of all the letters in the original alphabet.
In this problem, the alphabet will consist of only lowercase and uppercase letters ('a'-'z', 'A'-'Z').
John wants to be sure that his encryption is safe, so he will not choose a cipher where a letter is encoded to either itself or to its lowercase or uppercase equivalent. For example, he will not choose a cipher where the letter 'j' is encoded to either 'j' or 'J'.
Given the original message msg and encoded message encMsg, determine the number of simple substitution ciphers that fit John's requirements and encode msg to encMsg.
Return this number modulo 1234567891.
|