정원 만들기 timer 0.3s memory 1024MB

정올이는 정원을 만드는 취미가 있다. 그는 2N개의 돌을 사용해 정원을 만든다. 돌의 절반은 녹색이고, 1부터 N까지 번호가 하나씩 적혀 있다. 다른 절반은 회색이고, 마찬가지로 1부터 N까지 번호가 하나씩 적혀 있다. 정원을 만들기 위해 정올이는 모든 돌들을 일렬로 놓는데, 연속한 두 돌 사이의 거리가 정확히 1이 되도록 한다.

정올이는 자신의 정원에 대해 하나의 미신을 가지고 있다. 같은 번호가 적힌 두 돌 사이의 거리가 M의 배수인 것이 있다면, 그 정원은 M-불운이라고 간주된다. 그렇지 않은 정원은 M-행운이라고 간주된다.

정올이는 만들 수 있는 모든 M-행운 정원을 만들려고 한다. 그는 2N개의 돌로 이루어진 M-행운 정원이 몇 개나 있는지 알고 싶어한다. 두 정원 A와 B는 다음과 같은 조건을 만족하는 정수 i(1\leq i\leq 2N)가 존재할 때 다르다고 간주된다:

• 정원 A의 i번째 돌의 색깔이 정원 B의 i번째 돌의 색깔과 다르거나,

• 정원 A의 i번째 돌에 적힌 번호가 정원 B의 i번째 돌에 적힌 번호와 다르다.