29816번 - 사랑의 묘약

문제

후배와 친해지고 싶었던 김한양은 학과에서 진행하는 짝선짝후 행사를 신청했다. 짝선짝후 행사는 선후배가 서로 친해질 수 있도록 짝을 맞추어 주는 행사이다. 금사빠 김한양은 자신의 짝후배 한누리에게 첫눈에 반해버렸다. 사랑에 빠진 김한양이 한누리와 어떻게 친해질 수 있을지 고민하던 사이, 어디선가 특이한 옷차림의 과학자가 나타나서 김한양에게 말을 걸었다.

"여기 1ドル$부터 $N$까지의 숫자가 하나씩 적혀있는 $N$개의 숫자 카드들이 있다... 이 $N$개의 카드 중에서 원하는 만큼 카드를 뽑았을 때... 뽑은 모든 카드에 적힌 숫자의 합이 2023ドル$과 서로소인 경우는 총 몇 가지일까...? 정답을 말하면 특별히 내가 만든 사랑의 묘약을 주도록 하지..."

조금 수상하다고 생각했지만, 이미 사랑에 빠진 김한양을 막을 순 없었다! 김한양이 사랑의 묘약을 얻을 수 있도록 도와주자.

입력

첫째 줄에 양의 정수 $K\ (1 \leq K \leq 10^9)$가 주어진다.

출력

$N = 2023 \times K$일 때, 과학자가 김한양에게 물어본 경우의 수를 10ドル^{9}+7$로 나눈 나머지를 출력한다.

제한

힌트