새해를 맞아 일류 개발자가 되기로 마음먹은 코딩 꿈나무 일레이나(15, 중2)는 파이썬을 공부하고 있다.


일레이나는 반복문을 공부하면서 연습삼아 아래와 같은 코드를 작성하였다.


t = 0

n = 10

for i in range(1, n+1):

  t += 1

print(t)


위 코드를 실행해 10 이란 출력을 얻어 매우 기쁘다.


쇳불도 단김에 빼라고 일레이나는 반복문을 정복하기로 마음먹고 아래와 같이 반복문 안에 반복문을 하나 더 작성했다.


t = 0

n = 10

for i in range(1, n+1):

  for j in range(i, n+1):

    t += 1

print(t)


위 코드를 실행해 55 란 결과를 얻어 매우 기쁘다.


일레이나는 내친김에 반복문 안에 반복문을 하나 더 작성했다.


t = 0

n = 10

for i in range(1, n+1):

  for j in range(i, n+1):

    for k in range(j, n+1):

      t += 1

print(t)


위 코드를 실행했더니 220 이 출력되었다.


일레이나는 문득 위와 같은 방식으로 반복문 안에 반복문을 계속 추가하면 어떤 결과가 출력될 지 궁금해졌다.


마법을 부리기 귀찮은 일레이나를 도와 n이 주어지고 반복문이 k번 겹쳐졌을 때 출력될 t 값을 계산하는 프로그램을 만들어주자


이 때 t 가 너무 커질 게 불 보듯 뻔하므로 t 를 2000003 으로 나눈 나머지를 출력하자


조건:

1 <= n <= 10^15

1 <= k <= 10^15

일레이나는 바쁜 사람이므로 프로그램은 1초 안에 종료되어야 한다.


예시:

n = 10, k = 2 -> 답: 55

n = 10, k = 3 -> 답: 220

n = 10000, k = 100000 -> 답: 1967352

설명: n = 10000 이고 위와 같은 반복문이 십만번 겹쳐지만 출력될 t를 p로 나눈 값은 위와 같다.

n = 7701, k = 7701 -> 답: 822855

n = 10^15, k = 10^15 -> 답: 0



ㅇㅅㅇ


수정: 들여쓰기 고침, 설명 추가, 예시 수정