TopCoder Statistics - Problem Statement

Problem Statement

Manao has a rectangular board divided into n times m cells. The rows of the board are numbered from 1 to n and the columns are numbered from 1 to m. The cell in row i, column j is referred to as (i, j). Each cell contains an uppercase letter of the English alphabet.

Having such a board, Manao likes to traverse it. The traversal always starts in the cell (1, 1). In each step of the traversal Manao moves either one cell down or one cell to the right. That is, from any cell (x, y) Manao will move either to (x+1, y) or to (x, y+1). The traversal always ends in the cell (n, m). During the traversal Manao records the letters in the visited cells (including the first and the last cell). The obtained string is called a string path for the given board.

You are given the ints n and m, and two distinct Strings A and B. Manao claims that he performed two different traversals of his n x m board and obtained the string paths A and B. Compute the number of different boards for which this is possible. Return this number modulo 1,000,000,009.

Definition

Class:: StringPath
Method:: countBoards
Parameters:: int, int, String, String
Returns:: int
Method signature:: int countBoards(int n, int m, String A, String B)
(be sure your method is public)

Constraints

n will be between 1 and 8, inclusive.
m will be between 1 and 8, inclusive.
A and B will be exactly n+m-1 characters long.
A and B will consist of uppercase letters ('A'-'Z') only.
A and B will be distinct.

Examples

2

2

"ABC"

"ADC"

Returns: 2

The two possible boards are: AB AD DC BC
2

2

"ABC"

"ABD"

Returns: 0

It is impossible for two string paths to have a different last letter.
3

4

"ABCDDE"

"ACCBDE"

Returns: 1899302
8

8

"ZZZZZZZZZZZZZZZ"

"ZABCDEFGHIJKLMZ"

Returns: 120390576
1

1

"A"

"B"

Returns: 0
1

3

"AAA"

"ABA"

Returns: 0
4

1

"AADA"

"ABDA"

Returns: 0
5

3

"AAAAAAA"

"AAAAAAB"

Returns: 0
4

4

"BAAAAAA"

"AAAAAAA"

Returns: 0
3

2

"LLFF"

"LLWF"

Returns: 52
5

6

"AVOOKRJOHS"

"AOOONRJOHS"

Returns: 159569115
8

6

"RZEEDBRYSRVFZ"

"RZEEDBRYSRWFW"

Returns: 0
7

7

"RKZIIMJYEICWR"

"RKNIIMJYEIOWM"

Returns: 0
7

7

"TFIDFZHZMWVFM"

"TVJYPVWZVESXM"

Returns: 308302309
8

8

"GECMLMHTREFZAPE"

"GECMLGHTREAZAPE"

Returns: 109794146
8

8

"ZOQBBQSXZIXZUMB"

"ZOIBBQHXGIXZUGB"

Returns: 424332600
8

8

"NNHYGLIDNEZTZNQ"

"NHRURQRKBCWKLPQ"

Returns: 120390576
8

8

"GCABMDHZJYYJDYO"

"GOCSMQCCPEKHUFO"

Returns: 85835631
8

8

"CWALSSXJLTSMKGO"

"CTLLHZYANPFMFGO"

Returns: 639810403
5

7

"MVOLIBDVUUB"

"MLIPIBDOUUB"

Returns: 57032821
5

3

"SJDCLTR"

"SJCQLER"

Returns: 52018252
3

3

"FWVGA"

"FWWGA"

Returns: 70350
7

8

"BFEUHVKHQACGNT"

"BFEBIVKHLZCDNT"

Returns: 954175085
6

6

"FIKVSHCNYAT"

"FIJERHLXYDT"

Returns: 932663518
6

5

"OBRWTUAULP"

"OSRWTVAULP"

Returns: 744603864
4

4

"DUOQBOJ"

"DUPABOJ"

Returns: 540370627
3

5

"LPCIJHU"

"LXCYKSU"

Returns: 2094404
4

8

"QFVEPPSYXVF"

"QFVHRJVHVVF"

Returns: 32476962
4

3

"KRILPX"

"KRZVPX"

Returns: 2808000
8

5

"HGNMNTTFYCNK"

"HGNMDTRUMMNK"

Returns: 832578234
2

7

"NAYFENYN"

"NZNFKNAN"

Returns: 2
8

5

"NDELPMRADEXW"

"NUQYLMBAREMW"

Returns: 136154458
4

8

"ZDCSILFDIEO"

"ZWNSIEYDIHO"

Returns: 536476865
5

5

"MMYHSHPPR"

"MWYHSHXXR"

Returns: 82794554
8

4

"JJEQNHEJIZT"

"JJEQNHEDIIT"

Returns: 642558071
2

8

"GFNWUARGD"

"GFNWUAKYD"

Returns: 23762752
5

8

"GKPRLTWIEFQI"

"GKPRLTWIKFCI"

Returns: 930432415
4

8

"VJCNQZVWVWG"

"VWENQJVWCBG"

Returns: 309408522
3

3

"VDVIN"

"VDHSN"

Returns: 2752
8

8

"RAGKFIFVTKQJMRI"

"RAGKFIFATKQJMRI"

Returns: 671444282

Statistics

Problem Statement for "StringPath"

Problem Statement

Definition

Constraints

Examples