TSOC '15 Contest 2 #3 - Funny Anagrams

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 513M

Authors:
Problem types

The remaining group continues to traverse the caves when suddenly, they are ambushed! Gigantic spiders tear Tom to pieces, and in the scuffle, Paul is pinned to the ground by a falling boulder. Max, Mehdi, Joey and Alex have no choice but to leave Paul behind as the spider creatures swarm over him. He is gone now.

To cheer up the group, Max tells the group about funny anagrams, an anagram of a base string that contains a funny substring. For example, Boris's name anagrams to "Bikini Rhos Rusk", which contains the word "Bikini". Now isn't that quite hilarious! Given a base string and funny substring, tell Max how many funny anagrams he can make!

Here are the rules of anagramming, according to an interview with Master Max himself.

Well, my rules are sort of different. First, I get just enough of my alphabet toys to spell out the base string. Then, I use some of them to spell out the funny substring, and I glue them together in order. I now consider the substring as a single, unique character. I can't move any individual alphabet toys from the substring anymore, as they are glued together, but I can move the entire substring around. Afterward, I mix them up and see how many combinations I can make!

Input Specification

The input will consist of lowercase alphabet characters (a-z) and a newline.

The first line of input has the funny substring, with length 1 \le length \le 100. The characters may repeat in any way.

The second line of input will have the base string, with length 1 \le length \le 100.

Output Specification

A single integer: The number of funny anagrams that Max can create (modulo 10^9+7).

Sample Input

ab
aab

Sample Output

2

Explanation

Max glues an a and b together from the base string to get the unique character ab. By the definition of an anagram, he has to use the remaining a from the base string:

An anagram is a type of wordplay, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once.

Therefore Max can make two anagrams, a+ab and ab+a.


Comments


  • 0
    pyrexshorts  commented on April 21, 2015, 9:19 p.m.

    Is his comment still true, or is the problem edited?


    • 0
      kobortor  commented on April 21, 2015, 9:37 p.m.

      In fact, this input is not valid.

      The characters will not all be the same


      • 0
        pyrexshorts  commented on April 21, 2015, 10:26 p.m.

        If the base string is aabcd, and the funny string is bcd, then is a + bcd + a the same thing as the two a's swapped?


        • 0
          kobortor  commented on April 22, 2015, 12:46 p.m.

          Yes. Again, Max will not be able to supervise this contest.

          Max


  • 2
    FatalEagle  commented on April 20, 2015, 9:48 p.m. edit 2

    First of all, don't make announcements in the problem statement. That's what the comment section is for.

    Second of all, if your statement and testdata disagree, the only way to handle it professionally is to make the data confirm to the statement, not the other way around.

    Please refer to https://dmoj.ca/help/externalcontests/.


    • 1
      bobhob314  commented on April 20, 2015, 10:16 p.m.

      Thanks.


  • 1
    nullptr  commented on April 20, 2015, 8:23 p.m.

    In the case:

    a
    aa

    Is the answer 1 or 2?


    • 5
      GHETTO  commented on April 20, 2015, 8:34 p.m.

      Hello dear friend, colleague and fellow software programmer. The answer to this conundrum is 2.


      • 1
        FatalEagle  commented on April 20, 2015, 8:37 p.m.

        In fact, this input is not valid.

        The characters will not all be the same.


        • 0
          bobhob314  commented on April 20, 2015, 8:51 p.m.

          In the substring.


        • 0
          bobhob314  commented on April 20, 2015, 8:51 p.m. edit 3

          In the substring.

          Edit sry for repost sent from the road

          I will edit the problem when I get back soon

          Even with all repeated letters the problem is still solvable w/o nontrivial additions to same code

          Sorry for all inconveniences

          Also who tf is GHETTO?