В один ряд стоят \(n\) компьютеров, первоначально все выключены, и Феникс хочет всех их включить. Он будет лично включать их по одному. Однако в любой момент времени, если компьютеры \(i-1\) и \(i+1\) оказались включены, то компьютер \(i\) \((2 \le i \le n-1)\) включится сам автоматически (если он еще не включен). Заметим, что Феникс не может включить компьютер, который уже включился автоматически.
Рассмотрим только последовательности компьютеров, включенных непосредственно Фениксом, сколько существует таких последовательностей, включающих все компьютеры? Две последовательности различны, если либо множество компьютеров, включенных лично Фениксом, различается, либо порядок их включения различен. Так как ответ может быть слишком большим, выведите его по модулю \(M\).
Выходные данные
Выведите одно число — количество способов включить все компьютеры по модулю \(M\).
Примечание
В первом примере, для Феникса есть \(6\) последовательностей, при которых он включит все компьютеры:
- \([1,3]\). Включить компьютер \(1\), потом \(3\). Заметим, что компьютер \(2\) включится автоматически после того, как компьютер \(3\) будет включен Фениксом, но мы учитываем только компьютеры, включенные непосредственно Фениксом.
- \([3,1]\). Включить компьютер \(3\), потом \(1\).
- \([1,2,3]\). Включить компьютеры \(1\), потом \(2\), затем \(3\).
- \([2,1,3]\)
- \([2,3,1]\)
- \([3,2,1]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 100000007
|
6
|
|
2
|
4 100000007
|
20
|
|
3
|
400 234567899
|
20914007
|