Cheerleaders
Cica is a cheerleader and she and her group are given a task of making the programming contest enjoyable.During the contest they will perform in costumes and each costume will have a single colour(2 or more costumes can be of the same colour).They will be placed in a line facing north and then some of them will leave the arena(it is possible that none of them will leave,but at least one must remain).They want to leave the arena so that viewers from the east side can see the same order of colours(of the remaining cheerleaders) as the viewers from the west.So they ask programmers for help:In how many ways can they do it?
InputThe first line contains the number of cheerleaders n(1<=n<=5000).
The next line contains the order of cheerleaders before any of them left(string of n symbols).The i-th char represents the colour of the i-th cheerleader.The same chars represent the same colour and the different ones represent different colours.
The next line contains the order of cheerleaders before any of them left(string of n symbols).The i-th char represents the colour of the i-th cheerleader.The same chars represent the same colour and the different ones represent different colours.
OutputThe first line should contain the number of ways they can leave the arena so that the condition above is met mod 1.000.000.007.
Input
Output
5
patkaOutput
8Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.