时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：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 
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:
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 
and 
are both positive integers and coprime. If there exists a non-negative integer 
less than satisfying %20%3D%20p)
, we call the integer the result of modulo .
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 '
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
输入描述:
Each test consists of multiple test cases.
The first line contains a single integer(
) — the number of test cases.
Each line of the following
It is guaranteed that there are no more than two tiles of the same type in the start hand.
输出描述:
For the-th test case, print a line containing "
" where
and
is the answer to the test case.