22236번 - 가희와 비행기

가희는 김포 공항에서 김해 공항까지 비행기를 타고 가려고 합니다.

비행기가 수평 방향으로 1만큼 이동하였을 때, 비행기의 고도는 1만큼 변화합니다. (상승 또는 하강)

비행기가 상승하거나 하강할 때에는 이동한 수평 거리 당, 고도 변화량이 동일합니다. 그림 1은 이 조건을 만족하지만, 그림 2는 그렇지 않습니다.

[그림 1] 비행기가 상승할 때와 하강할 때

[그림 2] 문제의 조건을 만족하지 않는 비행 경로 

김포 공항에서 김해 공항까지 수평 거리는 d입니다. 아래 조건을 만족하는 비행기가 비행할 수 있는 가짓수를 구해 주세요.

[그림 3] 김포공항에서 김해공항 방항으로 날아가는 비행기

• 김포 공항에서 이륙하면 김해 공항에 착륙할 때 까지 다른 어떠한 지점에도 착륙하지 않습니다. 고도가 0이 되었을 때, 착륙하였다고 합니다.
• 비행기는 수평 거리 d만큼 이동합니다.  수평거리 d만큼 이동했을 때 고도가 0인 지점에 김해 공항이 있습니다.
• 비행기는 이륙할 때부터 착륙할 때 까지 비행 방향을 바꾸지 않습니다. 즉, 김포 공항에서부터 김해 공항까지 일직선으로 날아갑니다.
• 비행기는 지구를 한 바퀴 이상 돌지 않으며, 김해 공항이 있는 방향 반대편(북서쪽)으로 비행하지 않습니다.
• 김포 공항과 김해 공항의 고도는 0이며, 비행기가 날아가는 경로 상에는 장애물이 존재하지 않습니다.

첫 줄에 d와 m이 주어집니다.

문제에 대한 답을 m으로 나눈 나머지를 출력해 주세요.

• 1 ≤ d ≤ 4 × 10³
• d는 짝수입니다.
• m은 소수이며, [2, 2×10⁹] 에 속하는 정수입니다.