이 문제는 루미의 생일파티장 꾸미기와 , 의 제한만 다르다.
루미의 친구들은 루미를 위한 깜짝 생일파티를 준비하느라 바쁘다. 케이크와 선물, 장소 대관까지 모든 것이 준비되었다! 그런데 문제가 하나 있다. 대관한 장소의 벽이 너무 밋밋하다. 그래서 친구들은 직사각형 타일로 벽을 꾸미기로 했다.
친구들은 다음 조건을 모두 만족하는 직사각형 타일을 고르려 한다.
- 타일의 가로 길이와 세로 길이는 양의 정수이다.
- 가로 길이는 세로 길이 이상이다.
- 가로 길이는 루미가 가장 좋아하는 양의 정수 의 배수이다.
- 가로 길이는 이하이다.
- 가로 길이와 세로 길이는 서로소이다.
조건을 만족하는 타일 중 서로 합동이 아닌 모양이 몇 가지인지 구해 친구들을 도와주자.
첫째 줄에 양의 정수 , 이 공백으로 구분되어 주어진다.
조건을 만족하는 모양의 수를 출력한다. 답이 클 수 있으므로 으로 나눈 나머지를 출력한다.
예제 5의 참값은 이다.
