# P3473 [POI2008]UCI-The Great Escape

• 8通过
• 13提交
• 题目提供者 洛谷
• 评测方式 云端评测
• 标签 动态规划,动规,dp POI 2008 高性能
• 难度 NOI/NOI+/CTSC
• 时空限制 1000ms / 128MB
• 提示：收藏到任务计划后，可在首页查看。

## 题目描述

Al Bytone, the infamous thief, plans a bank robbery.

He knows only too well that the moment he robs the bank a pursuit will be commenced. Unfortunately, Al Bytone is a poor driver and turning left causes him great trouble. This is why he tries to devise such an escape route that at each intersection he would either ride straight ahead or turn right. He is also aware that once he passes through any intersection, the police will come and remain there, waiting for him.

Therefore he may pass through any intersection at most once.

Furthermore, the police are always present at certain intersections, so Al Bytone will have to avoid these intersections as well (there's no police at the intersections near the bank and near Al Bytone's hideout.) Al Bytone is planning his escape route. To your great (and rather unpleasant) surprise, he paid you a visit and told to calculate the number of different escape routes leading from the bank to his hideout complying the aforementioned requirements. Needless to say, Al Bytone does not take 'no' as an answer...

The streets of Byteburg form a rectangular grid.

Every street runs either in the North-South or East-West direction, and every two non-parallel streets intersect.

The bank is situated to the south of the south-western-most intersection.

Al Bytone will start his great escape driving north.

reads from the standard input the location of hideout, descriptions of intersections with police and a positive integer , calculates the number of different escape routes leading from the bank to the hideout complying the aforementioned requirements, writes out to the standard output this number's residue modulo .

给一个n*m 的地图，计算从(n,1) 到第 x 列的第y 行的路径条数 mod k ，走过的点不能再走，转弯只能向右转。

## 输入输出格式

输入格式：

There are three integers in the first line of the standard input, , and (, ).

The numbers and denote the number of streets leading in East-West and North-South direction, respectively.

The second line contains two integers and (, ).

These represent the hideout's location - at the intersection of street leading in Nort…

输出格式：

Your programme should write out the residue of the number of escape routes modulo in the first and only line of the standard output.

## 输入输出样例

输入样例#1： 复制
3 5 10
4 2
+++++
++*++
++++*

输出样例#1： 复制
2

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。