모듈러 연산을 이용해 해결한다. 그리고 입력값의 최대값이 21억 이상이므로 long long형을 사용한다. 또한 시간 제한이 있기 때문에 반복문으로 해결이 불가능하다. 때문에 재귀함수를 이용하여 해결한다.