Recovering the Three Words

According to a popular belief, a typical computer programmer only knows three words – often misspelled – and drinks a lot of coffee. A book titled The \( \textbf{Dictionary}\ of\ the\ Three\ Words\ Every\ Typical\ Programmer\ Should\ Know \) was published to help with these spelling mistakes. Unfortunately, after spilling coffee on your copy, some characters are now unreadable. Fortunately, the three words in the dictionary are distinct and are printed in lexicographical order.

Your task is to determine in how many different ways you can recover the missing characters such that, after restoration, the three words (denoted by \(w_1\), \(w_2\), and \(w_3\)) satisfy the conditions:

• \(w_1 < w_2\) and \(w_2 < w_3\) in lexicographical order.

In each word, any missing character is represented by a question mark ? and must be replaced by a lowercase English letter (a--z). When comparing words lexicographically, treat the end of a string as a termination symbol that is smaller than any letter. Since the number of possible ways may be large, output the result modulo \(10^9+9\).

Note: Two words are compared character by character. If a difference is found the word with the smaller corresponding character is smaller. If one word is a prefix of the other, the shorter word is considered smaller.

inputFormat

The input consists of three lines. Each line is a non-empty string representing one word. Each word consists of lowercase letters ('a'-'z') and/or question marks ('?'), where a question mark indicates a missing character.

The words are originally in lexicographical order, although due to missing characters they might not look so. Your task is to count the number of ways to replace the '?' characters so that after replacement the three words satisfy \(w_1 < w_2 < w_3\).

outputFormat

Output a single integer: the number of valid ways to replace the missing characters so that the words are in strict lexicographical order, modulo \(10^9+9\).

sample

a
b
c

1