|Central-European Olympiad in Informatics, CEOI 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)|
The mythic world of Chess Land is a rectangular grid of squares with $$$R$$$ rows and $$$C$$$ columns, $$$R$$$ being greater than or equal to $$$C$$$. Its rows and columns are numbered from $$$1$$$ to $$$R$$$ and $$$1$$$ to $$$C$$$, respectively.
The inhabitants of Chess Land are usually mentioned as pieces in everyday language, and there are $$$5$$$ specific types of them roaming the land: pawns, rooks, bishops, queens and kings. Contrary to popular belief, chivalry is long dead in Chess Land, so there are no knights to be found.
Each piece is unique in the way it moves around from square to square: in one step,
Recently, Chess Land has become a dangerous place: pieces that are passing through the land can get captured unexpectedly by unknown forces and simply disappear. As a consequence, they would like to reach their destinations as fast (i.e. in as few moves) as possible, and they are also interested in the number of different ways it is possible for them to reach it, using the minimal number of steps – because more paths being available could mean lower chances of getting captured. Two paths are considered different if they differ in at least one visited square.
For this problem, let us assume that pieces are entering Chess Land in a given column of row $$$1$$$, and exit the land in a given column of row $$$R$$$. Your task is to answer $$$Q$$$ questions: given the type of a piece, the column it enters row $$$1$$$ and the column it must reach in row $$$R$$$ in order to exit, compute the minimal number of moves it has to make in Chess Land, and the number of different ways it is able to do so.
The first line contains three space-separated integers $$$R$$$, $$$C$$$, and $$$Q$$$ $$$(1 \leq Q \leq 1000$$$, $$$2 \leq C \leq 1000$$$ and $$$C \leq R \leq 10^9)$$$ – the number of rows and columns of Chess Land, and the number of questions, respectively. Then $$$Q$$$ lines follow.
Each line consists of
You have to print $$$Q$$$ lines, the $$$i$$$-th one containing two space separated integers, the answer to the $$$i$$$-th question: the first one is the minimal number of steps needed, the second is the number of different paths available using this number of steps. Since the answer can be quite large, you have to compute it modulo $$$10^9+7$$$.
If it is impossible to reach the target square, output the line "0 0".
8 8 5 P 1 2 R 4 8 Q 2 3 B 3 6 K 5 5
0 0 2 2 2 5 2 2 7 393
You can download the above example and an additional (bigger) sample input here: https://gofile.io/d/GDzwfC