P3473 [POI 2008] UCI-The Great Escape

阿尔·拜通，这个臭名昭著的小偷，计划进行银行抢劫。 他非常清楚，一旦他抢劫银行，追捕就会开始。不幸的是，阿尔·拜通是个糟糕的司机，左转对他来说是个大麻烦。这就是为什么他试图设计一个逃跑路线，使得在每个路口他要么直行，要么右转。他也知道，一旦他经过任何一个路口，警察就会到达并留在那里等他。 因此，他最多只能经过每个路口一次。 此外，警察总是在某些路口待命，所以阿尔·拜通也必须避开这些路口（银行附近和阿尔·拜通藏身处附近的路口没有警察）。阿尔·拜通正在计划他的逃跑路线。令你非常（且相当不愉快）惊讶的是，他拜访了你，并要求你计算符合上述要求的从银行到他藏身处的不同逃跑路线的数量。不用说，阿尔·拜通不接受“拒绝”作为答案…… Byteburg 的街道形成一个矩形网格。每条街道要么是南北方向，要么是东西方向，并且每两条不平行的街道相交。银行位于最西南路口的南边。 阿尔·拜通将开始他的伟大逃亡，向北行驶。 任务 编写一个程序： 从标准输入读取藏身处的位置、警察所在路口的描述和一个正整数 $k$，计算符合上述要求的从银行到藏身处的不同逃跑路线的数量，并将该数量对 $k$ 取模的结果写入标准输出。

标准输入的第一行有三个整数 $n$、$m$ 和 $k$（$1\le n,m\le 100$，$1\le k\le 10^9$）。 数字 $n$ 和 $m$ 分别表示东西方向和南北方向的街道数量。 第二行包含两个整数 $x$ 和 $y$（$1\le x\le n$，$1\le y\le m$）。 这些代表藏身处的位置——在第 $x$ 条南北方向街道和第 $y$ 条东西方向街道的交叉口。

你的程序应在标准输出的第一行写出逃跑路线数量对 $k$ 取模的结果。

题面翻译由 ChatGPT-4o 提供。