Z 国坐落于遥远而又神奇的东方半岛上，在小Z 的统治时代公路成为这里主
要的交通手段。Z 国共有n 座城市，一些城市之间由双向的公路所连接。非常神
奇的是Z 国的每个城市所处的经度都不相同，并且最多只和一个位于它东边的
城市直接通过公路相连。Z 国的首都是Z 国政治经济文化旅游的中心，每天都有
成千上万的人从Z 国的其他城市涌向首都。

为了使Z 国的交通更加便利顺畅，小Z 决定在Z 国的公路系统中确定若干条
规划路线，将其中的公路全部改建为铁路。

我们定义每条规划路线为一个长度大于1 的城市序列，每个城市在该序列中
最多出现一次，序列中相邻的城市之间由公路直接相连(待改建为铁路)。并且，
每个城市最多只能出现在一条规划路线中，也就是说，任意两条规划路线不能有
公共部分。

当然在一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出
发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的
城市之间，因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首
都。

我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的
次数，而Z 国的交通系统的“不便利值”为所有城市的不便利值的最大值，很明
显首都的“不便利值”为0。小Z 想知道如何确定规划路线修建铁路使得Z 国的
交通系统的“不便利值”最小，以及有多少种不同的规划路线的选择方案使得“不
便利值”达到最小。当然方案总数可能非常大，小Z 只关心这个天文数字mod Q
后的值。

注意：规划路线1-2-3 和规划路线3-2-1 是等价的，即将一条规划路线翻转
依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不
属于另一个方案。