How to Write a Message
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
One day, you decided to write a message to your girl friend consisting of N uppercase English letters.
Your girlfriend's alphabet is limited to only two letters: 'A' and 'B'. She recognizes only the words that are of length M containing letters from her alphabet.
There are some words that your girlfriend hates. You are given two strings X and Y, which represent some two words she recognizes. Your girlfriend hates words X, Y and also each word that she recognizes and is lexicographically greater than X and smaller than Y .
For example, if M = 3, X = "ABA" and Y = "BBA" then all words the girlfriend hates are: "ABA", "ABB", "BAA", "BAB" and "BBA". Note that she doesn't hate words "AAA", "BB", "AC" or "BCAD".
The message that you will send to the girlfriend should not contain any of words she hates as a substring. Note that the message can contain letters the girl doesn't recognize. The message will contain N uppercase English letters. Find the number of different messages you can send. Since the answer can be large, output it modulo (109 + 7).
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and M.
The second line contains the string X and the third line contains the string Y, both of length M.
For each test case, output a single line containing the answer to the corresponding test case, modulo (109 + 7).
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 19
- X and Y will consist only of letters 'A' and 'B'.
- X will not be lexicographically greater than Y.
Input: 1 1 1 A B Output: 24
Example case 1. Out of all 26 possible messages in this case only two are invalid (i.e. "A" and "B"). Thus, the answer is 26 - 2 = 24.
|Tags||cook56, dynamic-programming, easy-medium, recursion, witua|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.