n teams play in a tournament. There are n games in the tournament, and each game is played by k teams. During each game, each participating team is assigned one of k colors, and each of those teams must have a distinct color. The k colors are represented by the first k uppercase letters in the alphabet. Each team must play exactly k games, and they must be assigned a different color in each of their games. In addition, all teams participating in the same game must have the same experience. The experience of a team is the number of games it has played before the current game.
You are given a schedule of the tournament in the String schedule. The i-th element of schedule represents the i-th game. The j-th character of the i-th element of schedule can have one of the following values:
'-' if the jth team doesn't play in the ith game;
an uppercase letter representing the color assigned to the j-th team in the i-th game;
'?' if it is unknown whether the j-th team participates in the i-th game (if it does participate, the color assigned to the j-th team in this game is also unknown).
Return the number of different valid ways to complete the given schedule. Two schedules are different if there is at least one position at which they contain different characters. Of course, there must be no '?' characters in a complete schedule.