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