Statistics

Problem Statement for "StringSequences"

Problem Statement

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Farmer John and Eel Brus are studying string theory at the university. One day John found a very interesting sequence of strings s1, s2, ..., sK and told Brus about it. Brus only remembers the following information:
  • Each string in the sequence consists of lowercase letters only.
  • The sequence starts with A. In other words, s1 = A.
  • The sequence ends with B. In other words, sK = B.
  • For each i between 1 and K-1, inclusive, si+1 can be obtained by inserting one lowercase letter to si. For example, if s1 is "tco", valid options for s2 include "qtco", "trco", "tcso", and "tcot", but not "xco", "txoc", or "srm".
Return the number of sequences that match Brus's information, modulo 1,000,000,007. Brus's memory is always correct, so it is guaranteed that at least one such sequence exists.

Definition

Class:
StringSequences
Method:
countSequences
Parameters:
String, String
Returns:
int
Method signature:
int countSequences(String A, String B)
(be sure your method is public)

Constraints

  • A will contain between 1 and 49 characters, inclusive.
  • Each character in A will be a lowercase letter ('a'-'z').
  • B will contain between N+1 and 50 characters, inclusive, where N is the number of characters in A.
  • Each character in B will be a lowercase letter ('a'-'z').
  • There will be at least one sequence that matches Brus's information in the problem statement.

Examples

  1. "oxoxox"

    "foxfoxfox"

    Returns: 6

    The following six sequences match Brus's information: "oxoxox", "foxoxox", "foxfoxox", "foxfoxfox" "oxoxox", "foxoxox", "foxoxfox", "foxfoxfox" "oxoxox", "oxfoxox", "foxfoxox", "foxfoxfox" "oxoxox", "oxfoxox", "oxfoxfox", "foxfoxfox" "oxoxox", "oxoxfox", "foxoxfox", "foxfoxfox" "oxoxox", "oxoxfox", "oxfoxfox", "foxfoxfox"

  2. "aaaaa"

    "aaaaaaaa"

    Returns: 1

    Only the sequence "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa" matches Brus's information.

  3. "tco"

    "tcotco"

    Returns: 18

  4. "a"

    "alnfrlrealjnsliejsraijneroav"

    Returns: 135925750

  5. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 1

  6. "m"

    "mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm"

    Returns: 1

  7. "h"

    "vjvvbbhhhbvvjvvvvhvvhhhbvbvvvvvhhnjhvvhvbbhhvhhhhv"

    Returns: 567233984

  8. "sssssssssssssssssssssssssssssssssssssssssssssssss"

    "ssssssssssssssssssssssssssssssssssssssssssssssssss"

    Returns: 1

  9. "wmmemmemmpmmmwmmmmmmmmpmmmmmmmmmmmmmmmmmmemmmmmmw"

    "wmmemmemmpmmmmwmmmmmmmmpmmmmmmmmmmmmmmmmmmemmmmmmw"

    Returns: 1

  10. "ggggggggg"

    "gggggggggggggggggggggggggggggggggggggggggggggggggg"

    Returns: 1

  11. "bbbbbbbbbbbbbb"

    "bbbbbbbbbbbbbbbbbbbbbb"

    Returns: 1

  12. "qqqqqqqqqqqqqqqqqqqqqq"

    "qqqqqqqqqqqqqqqqqqqqqfqqqqqqqqqqqqqqqqqqqqfqqqqqqq"

    Returns: 317868247

  13. "n"

    "ns"

    Returns: 1

  14. "ppmtmtttppmtmpppmtmtmp"

    "ppmmmpmtmpttmttptpmttptmtmppmppttpmtpppppmmtmmmptp"

    Returns: 856841145

  15. "mmm"

    "ummfmfmmmm"

    Returns: 2233

  16. "yrhy"

    "yyyyyyryyryyhyryyyyyhhyyghyyyyyyhyryyhghyyhyhhyhyr"

    Returns: 228902867

  17. "oooozzzzszzz"

    "ojozjooozzzzsozzzz"

    Returns: 1500

  18. "ututhhhvtuhvdtthtthttttvuvtttuhvtudhvttvtudtd"

    "ututhhhvttuhvdttthtthttttvuvtttuhvtudhvtttdtvtudtd"

    Returns: 120

  19. "g"

    "jjugxgjjuxxucxjxjgxgx"

    Returns: 322284528

  20. "kawzwwmwmmkzzwwwwzzwazwwwwzmzkwwwmwwz"

    "kwwawmzwmwwmwmmkzzwwwwzwnwzwazwwwwzwmzkkwwwzmwzwzw"

    Returns: 891887979

  21. "mccbmmcpb"

    "cbmbccpcmbbmpbemcyebbcccbccbpcmmcbcbmcpcbccc"

    Returns: 543695066

  22. "dscscrfcsrssryyssssrssscys"

    "dfscccschysddsrfcsrssrcfhssyysrsfsssrssyscyyssyfhh"

    Returns: 367020026

  23. "kjddydqjddddjqqjqqqjdqddjqqyjdyjdyjeejqddeqkq"

    "kjddydjqjdjdddjqqjqqqjdqddjqqyjdyjdyjqeejqqddeqkq"

    Returns: 24

  24. "aoazhocozzazzcbaaczhcaabochoozzzhbz"

    "aboaoazhzocozzazazcbaaczhozaczzaczoabochooczzczhbz"

    Returns: 565811799

  25. "bdjjzr"

    "rdbjddrdjjbddjdbzzdbdzdbzdjjrd"

    Returns: 592000699

  26. "dothgjgwohwog"

    "dohhghgdgotgwvghoovwjtghjtdvjowwgogowowohwohgowgjj"

    Returns: 656855350

  27. "umtumemmt"

    "ueukueuumetuetmueeemmte"

    Returns: 21585348

  28. "ziozoozzozozhiso"

    "msszioozooszzhzzuzihozjzoikfoojjuzzihihszsoujuhhoi"

    Returns: 70317818

  29. "kbkkbzzzuzkzzzzbbzbhkkkkkz"

    "kzbkxkbzzzzxzuzkzzkzzbzbzbhzktkkkkkz"

    Returns: 5443200

  30. "hhhccdfccqfoqvqfdohoc"

    "cfhchhofqqcdchcdocfdochhhchcqcfohoqcovfqofdohqfhoc"

    Returns: 780045212

  31. "iltljhoww"

    "ilotouttlljlllojtohohllwwojlutll"

    Returns: 281796213

  32. "jtddjjdjjdxjdjtjdsjdjjdmvv"

    "xxjvtddtjjdjxtxjdttxjdjxjtjdjsjjxjddjjjdmvjjtjxvxx"

    Returns: 210407968

  33. "qgzwqqqkuwwqgdzuduquqqgvqkqtvqutzwkgqu"

    "qgztwqqqkgvkquwwqgdqzududquqtwqqtgvqkqtvqustzwkgqu"

    Returns: 330559993

  34. "hhnhhmjjnnbhmhhjnhqhmhmwhmjm"

    "hjhhnhhjhmjjnnhbhhmhhjkhjhnhjhhqmahamhnhmwhmmjmbhj"

    Returns: 969309634

  35. "yspppgouf"

    "gyspuppgougf"

    Returns: 6

  36. "wuucedpexxeqqdde"

    "pwqrrccxeguxucpoedbucpxwxexcgcxeeqxxdqxxuwdexdcpce"

    Returns: 169823218

  37. "buful"

    "uuxufubufyxtwtufxuxfufgufulxtdfxxdff"

    Returns: 428644465

  38. "fhhhlhwfbffhfdiflofhh"

    "fhhhhwlhhalflbwrlwhlofwbfflhlbwfdiwrbflloofhhlflhv"

    Returns: 919988566

  39. "scnungnhhbatt"

    "scnunygnhhbatt"

    Returns: 1

  40. "svhakuv"

    "kkhuacduvqvursvvsheviiovekracrvkvrcvvvrvaivrvkkukv"

    Returns: 167504566

  41. "odhviotztodptttodzpohom"

    "odhphviotztodptttodzhpohztodm"

    Returns: 1080

  42. "rrylpotpvoptaalny"

    "rzarryltbzbpoborbptptnvrhooplbovatbzpayralnbyrzotz"

    Returns: 715740723

  43. "ipvxl"

    "iooxlslspvldvxlpyodli"

    Returns: 789741546

  44. "zkkzkjgtkkkzkzcerjkkkzknrkkkkkenk"

    "jzrkukjzkjgztkzlekkzkzcerjkkknztkejnrkkkkekkejnkez"

    Returns: 138409283

  45. "torooooioioopttpoo"

    "toroooooioiitoopoopptftpoo"

    Returns: 50400

  46. "nensenctinstnnncrgnnsaatsssintstgwgaswacwhnaw"

    "tnensennctinstnnncsrgnnsgaantsssintstgwgaswacwhnaw"

    Returns: 120

  47. "hhgchococqqcoq"

    "cchlphjoggchhgnoccoqpcqgcqhccoqchmmpgt"

    Returns: 164407325

  48. "oqazcfqckqkc"

    "gqaosocyoqogoaadscdqkqizdrqqcfceqidkaoqacikqzkqqjc"

    Returns: 280654639

  49. "ydecdctheyecihhfcymeeeshbbcmhyhhnpti"

    "yydecddecthecyescishhfcsymeelelcshbmbcymhyhhnzpti"

    Returns: 227020758

  50. "xly"

    "iqyyyqqoqxqolpyqyyowywwywyyynxxlyolwomiglmyylixwpx"

    Returns: 341178437

  51. "f"

    "utzztfo"

    Returns: 330

  52. "wwdwugcccscdbdqlsdbnebncdwuslgmnbmwbnmcccdxwwqqcs"

    "wwdwugcccscdbdqlsdbnebncdwuslgmnbmwbnmcdccdxwwqqcs"

    Returns: 1

  53. "qxvtozgrotx"

    "qxvfteozpgrotax"

    Returns: 24

  54. "wjpthvzvutlzczjwrhgggeznnonpnip"

    "zwfjjjpythgvnznvjuctlzczjwrthdglggfeyfzcnnoanpnhip"

    Returns: 778658157

  55. "iz"

    "sippriezapjmejyybnfprzubznm"

    Returns: 155943236

  56. "hxxovmtnhlpdhrglelvtt"

    "enbhmhxdxyovmtznzheemvlatetrpdhhtdrgglelzlvhpdtltt"

    Returns: 427001322

  57. "inibynybyfqzkzhjdg"

    "ishcjnibynyibyhfzffzqzihkhzdzihjindgiy"

    Returns: 272843716

  58. "ssuacksjfdfeaawsugsujcscc"

    "ssyueqeackusnejefdfhckesjaesawskusgksrwusjecssccby"

    Returns: 367276990

  59. "skmpepz"

    "skmtpuexdrpafzm"

    Returns: 40320

  60. "pwnixaxphazncxisbrianwbdguzrbgonbgbpge"

    "oxpwpnrirxaxphazncxisbriphbgaynwbdguzrabgaonbgbpge"

    Returns: 479001600

  61. "wpyuwbqbzeuwlupqzvquyvpbzmvgbo"

    "wwpyuwbqbzeuwlupqzvquyvpbzmvgbo"

    Returns: 1

  62. "a"

    "aa"

    Returns: 1

  63. "a"

    "ababababababababababababababababababababababababab"

    Returns: 600342224

  64. "aaaaaaaaaaaaaaaaaaaaaaaaa"

    "ababababababababababababababababababababababababab"

    Returns: 440732388

  65. "a"

    "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 1

  66. "a"

    "bbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 217822480

  67. "bab"

    "bbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 362649138

  68. "ab"

    "bbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 540715854

  69. "abcdefghijklmnopqrstuvwxy"

    "abcdefghijklmnopqrstuvwxyabcdefghijklmnopqrstuvwxy"

    Returns: 18309623

  70. "c"

    "abcdefghijklmnopqrstuvwxyabcdefghijklmnopqrstuvwxy"

    Returns: 396869543

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: