#arc124a. [arc124_a]LR Constraints
[arc124_a]LR Constraints
Problem Statement
We have cards arranged in a row from left to right. We will write an integer between and (inclusive) on each of these cards, which are initially blank.
Given are restrictions numbered through . Restriction is composed of a character and an integer . If is L
, the -th card from the left in the row must be the leftmost card on which we write . If is R
, the -th card from the left in the row must be the rightmost card on which we write .
Note that for each integer from through , there must be at least one card on which we write .
Find the number of ways to write integers on the cards under the restrictions, modulo .
Constraints
- is
L
orR
. - if .
Input
Input is given from Standard Input in the following format:
Output
Find the number of ways to write integers on the cards under the restrictions in the Problem Statement, modulo .
Sample Input 1
Sample Output 1
- The only way to meet the two restrictions is to write from left to right on the three cards.
Sample Input 2
Sample Output 2
- Be sure to find the count modulo .