Task DescriptionDiscussion (0)

Your program must read from the standard input the following data:

• Line 1 contains the integer N, the number of plants in the garden.

• Line 2 contains the integer M.

• Line 3 contains a string of N characters ‘L’ (lotus) or ‘P’ (papyrus) that represents a balanced garden.

Your program must write to the standard output a single line containing one integer between 0 and M‐1

(inclusive), the number assigned to the garden described in the input, modulo M.

Task :: Linear Garden

Ramesses II has just returned victorious from battle. To commemorate his victory, he has decided to build a majestic garden. The garden will contain a long line of plants that will run all the way from his palace at Luxor to the temple of Karnak. It will consist only of lotus plants and papyrus plants, since they

symbolize Upper and Lower Egypt respectively.

The garden must contain exactly N plants. Also, it must be balanced: in any contiguous section of the garden, the numbers of lotus and papyrus plants must not differ by more than 2.

A garden can be represented as a string of letters ‘L’ (lotus) and ‘P’ (papyrus). For example, for N=5 there are 14 possible balanced gardens. In alphabetical order, these are: LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, and PPLPL.

The possible balanced gardens of a certain length can be ordered alphabetically, and then numbered starting from 1. For example, for N=5, garden number 12 is the garden PLPPL.

TASK

Write a program that, given the number of plants N and a string that represents a balanced garden, calculates the number assigned to this garden modulo some given integer M.

Note that for solving the task, the value of M has no importance other than simplifying computations.

CONSTRAINTS

1 <= N <= 1,000,000

7 <= M <= 10,000,000

symbolize Upper and Lower Egypt respectively.

The garden must contain exactly N plants. Also, it must be balanced: in any contiguous section of the garden, the numbers of lotus and papyrus plants must not differ by more than 2.

A garden can be represented as a string of letters ‘L’ (lotus) and ‘P’ (papyrus). For example, for N=5 there are 14 possible balanced gardens. In alphabetical order, these are: LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, and PPLPL.

The possible balanced gardens of a certain length can be ordered alphabetically, and then numbered starting from 1. For example, for N=5, garden number 12 is the garden PLPPL.

TASK

Write a program that, given the number of plants N and a string that represents a balanced garden, calculates the number assigned to this garden modulo some given integer M.

Note that for solving the task, the value of M has no importance other than simplifying computations.

CONSTRAINTS

1 <= N <= 1,000,000

7 <= M <= 10,000,000

**INPUT:**

Your program must read from the standard input the following data:

• Line 1 contains the integer N, the number of plants in the garden.

• Line 2 contains the integer M.

• Line 3 contains a string of N characters ‘L’ (lotus) or ‘P’ (papyrus) that represents a balanced garden.

**OUTPUT:**

Your program must write to the standard output a single line containing one integer between 0 and M‐1

(inclusive), the number assigned to the garden described in the input, modulo M.

Input:

Output:

**5**

7

PLPPL

7

PLPPL

Output:

5

5

Input:

Output:

**12**

10000

LPLLPLPPLPLL

10000

LPLLPLPPLPLL

Output:

**2**

39

39

Submit Solution

Available Languages

Task info

Name: | Linear Garden |

Time: | 1 sec. |

Memory: | 64 MB |

#Tests: | 25 |

AddedBy: | rjmantilla |

Source: | Linear Garden |

Task Ratings

Difficulty: | 3.8 (6 votes) |

Quality: | 4.6 (7 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

RobertGerbicz | 0.065 s. |

tamaki | 0.097 s. |

crusader | 0.105 s. |

sakib_rulez | 0.11 s. |

The_Philosopher | 0.115 s. |

mmilisic | 0.148 s. |

1010011010 | 0.162 s. |

vjudge1 | 0.22 s. |

alex_mat | 0.223 s. |

vjudge2 | 0.226 s. |

Solved By