문제

차원 공간을 생각하자. 이 공간에 점 여러 개를 찍는다. (단, 점들의 모양은 모두 동일하다.) 이 때, 총 개의 점이 찍혀있다고 하자. 각 점에 의 번호를 매겨주면, 번째 점의 위치는 으로 나타낼 수 있다. 이 때, 임의의 , 에 대하여 는 언제나 정수이다. 또한, 정수 에 대하여 를 만족한다.

이 공간에는 점 외에는 어떠한 것도 존재하지 않는다. 바꿔 말하면, 점들 간의 상대적인 위치만 알 수 있고 정확한 위치를 알 수 없다. 바꿔 말하면, 번부터 번까지의 점 전체를 동일한 길이로 평행이동을 한 것은 같은 모양으로 볼 수 있다. 예를 들어, 2차원 공간에서 과 의 위치에 두 점이 놓여있는 모양과 , 에 두 점이 놓인 모양은 같은 모양으로 생각할 수 있다. 하지만 점들의 쌍을 회전한 것은 같은 모양이 아니다. 예를 들어, , , 의 점 배치와 , , 의 점 배치는 서로 다른 것으로 본다. 이 때, 점을 찍어서 만들 수 있는 모양으로 가능한 것의 개수를 으로 나눈 나머지를 구하여라.

입력

첫째 줄에 가 주어진다. 둘째 줄에 가 공백을 사이에 두고 주어진다. 셋째 줄에 이 주어진다.

출력

첫째 줄에 점을 찍어서 만들 수 있는 모양으로 가능한 것의 개수를 으로 나눈 나머지를 출력한다.

서브태스크