SP4839 PA06ANT - Ant

在一个由顶点 A、B、C、D、E、F、G 和 H 组成的立方体的边上，有一只来自 Byteotia 的蚂蚁正在行走。 这只蚂蚁想要找到从一个给定的顶点到另一个给定顶点的路径。路径要求恰好经过 **k** 条边（即路途中每经过一条边，都会走到这条边的另一端，不会中途折返）。如果某条边被通过了 **x** 次，那么这条边会被计算 **x** 次。蚂蚁对行走路线有一个额外要求：每次到达新顶点时，它不会沿着刚才使用的边返回，这样才能保证路线的趣味性。 然而，蚂蚁的智商有限，只能用 0 到 **p-1** 之间的整数进行计数。因此，你需要计算出总的路径数，并对 **p** 取模。

第一行输入两个大写英文字母 **v $ _{1} $** 和 **v $ _{2} $**，用空格隔开，分别表示蚂蚁旅行路线的起始点和终止点。第二行输入两个整数 **k** 和 **p**，用空格隔开。

输出一个整数，表示从起始点 **v $ _{1} $** 到终止点 **v $ _{2} $** 的所有符合要求的路径数，并对 **p** 取模。 **本翻译由 AI 自动生成**