Chiitoitsu
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Serval is learning Japanese Mahjong recently in order to play Mahjong Soul with his friends, HomuraCat, RanshiinSaikou, and Mocha.

Serval learned that in Japanese Mahjong, there are 34 different types of tiles, and there are 4 tiles of each type. According to the suits and the tile types, the tiles can be divided into four groups. Three of them form the numbered suits, each with sequences from one to nine. They are the manzu, the pinzu, and the souzu. The other group is the jihai, which can be further divided into the kazehai and the sangenpai.

Serval uses two characters to describe a tile. The former is a number and the latter is one of '', '', '' and ''. Specifically, the manzu, the pinzu and the souzu with the number k are described as '', '' and '', respectively. For example, San man (the manzu tile with the number 3) is described as '', Rou pin (the pinzu tile with the number 6) is discribed as '', Kyuu sou (the souzu tile with the number 9) is discribed as ''. As for jihai, Ton, Nan, Shaa, Pei, Haku, Hatsu, Chun are described as '' to '', respectively. All types of tiles are listed below.



You may know that in Japanese Mahjong, winning a hand requires at least one yaku, where hand denotes the tiles a player holds. There are a large number of yaku types, and among them, Serval loves chiitoitsu most. Chiitoitsu is the hand that consists of seven distinct pairs. In other words, chiitoitsu consists of seven distinct types of tiles and two tiles of each type. In this problem, there is no need for you to learn what yaku exactly is. You only need to focus on chiitoitsu.

Serval loves chiitoitsu so much that he wants to practice winning hands with chiitoitsu. Note that the rules that Serval practices seeking chiitoitsu are different from those of Japanese Mahjong. At first, all the tiles are shuffled and placed face-down on the board as the stockpile. Then the only player, Serval, is dealt 13 tiles, which means that he will get 13 tiles from the stockpile. These 13 tiles are called the start hand. In each turn, Serval can draw and discard in the following order:

  • Draw a tile from the stockpile.

    Serval gets a random tile from the stockpile. After that, he will hold 14 tiles.

  • Tsumo if the hand reaches chiitoitsu.

    Serval declares a win immediately if his hand reaches chiitoitsu, and the game is over at the same time.

  • Discard a tile from the hand.

    Serval chooses a tile and removes it from his hand. After that, he will hold 13 tiles. The discarded tile will be placed face-up on the board, which means it will not return to the stockpile.

Now Serval gets his start hand, and he wonders the expected number of turns to reach chiitoitsu if he carries out the optimal strategy. Surprisingly, Serval finds that there are no more than two tiles of the same type in his start hand. Serval simply concatenates the notation of each tile in the start hand, forming a string of 26 characters to describe the start hand. However, Serval cannot find out the answer, so he tells you his start hand and asks you to help him. You only need to tell him the answer modulo .

It can be shown that the answer can be represented as a fraction , where p and q are both positive integers and coprime. If there exists a non-negative integer r less than satisfying , we call the integer r the result of modulo .

输入描述:

Each test consists of multiple test cases.

The first line contains a single integer T () — the number of test cases.

Each line of the following T lines describes a test case and contains a string of 26 characters — the start hand.

It is guaranteed that there are no more than two tiles of the same type in the start hand.

输出描述:

For the i-th test case, print a line containing "" where i is the number of the test case starting from 1 and x is the answer to the test case.
示例1

输入

复制
2
1m9m1p9p1s9s1z2z3z4z5z6z7z
1m1m4m5m1p4m2m2m2p2p2s2s2z

输出

复制
Case #1: 927105416
Case #2: 100000041