Задача SnakeWay Вінницькі зоологи досліджують поведінку норної змії - дуже екзотичної для подільских місцин тварини. Вони помістили одну особину у тераріум з системою підземних ходів і з виходами на поверхню рівно у двох місцях - кутках тераріуму. Поверхня тераріуму поділена на рівні квадрати по 1 дециметру, при чому тераріум має розміри 3хN дециметрів.Науковці помітили, що змія виповзає на поверхню рівно один раз на добу. При цьому змія обповзає усі клітини на поверхні поля, до того ж відтворює маршрут, який пройшла найдавніше (два маршрути вважаються різними, якщо різна послідовність відвідування клітин).Зоологи цікавляться, скільки днів їм треба, щоб побачити один і той же маршрут двічі.

Технічні умови Програма SnakeWay читає з пристрою стандартного введення два рядки. У першому записано натуральне число N  (N < 106) - довжина тераріуму по одній зі сторін. У наступному рядку записано єдину літеру в залежності від розташування виходів у тераріумі. Літера означає, що тунелі розташовано по діаметрально протилежних кінцях тераріуму, літера означає, що між тунелями рівно 3 клітини (враховуючи клітини, де знаходяться тунелі), а літера L означає, що між тунелями рівно клітин (знову-таки, враховуючи клітини, де знаходяться тунелі).Програма  виводить на екран єдине число - кількість днів по модулю 1000000007, які мають очікувати зоологи перш ніж двічі побачити один і той самий маршрут змії. Дні першого і другого спостережень слід враховувати у відповідь. Якщо змія не може проповзти, виконавши умову задачі, слід вивести -1 у якості відповіді.

Приклади

Введення

Виведення

Коментар

3

D

3

У змії два можливих маршрути:

 

таким чином, змія спершу проповзе одним шляхом, потім іншим, а на третій день повторить свій перший шлях

1

L

-1

За умовою задачі виходить, що тунелі знаходяться у одній і тій самій точці, а тому змія не може виповзти звідти, проповзти усі клітини рівно один раз і повернутися туди ж

1

S

2

Змія має єдиний можливий маршрут, а тому на другий день він має повторитися

 

© LIKT 1998-2018