30799번 - 가희와 터널

문제

가희의 오빠는 터널 모양의 노즈 워크 장난감을 사 왔습니다. 가희는 이 장난감 안에 들어가 오빠가 숨겨 놓은 고구마 간식을 찾아서 먹으려고 합니다. 이 장난감 안에는 간식을 숨길 수 있는 위치가 $s$개 있습니다. 각 위치마다 번호가 순서대로 1ドル$번부터 $s$번까지 적혀 있습니다.

이 장난감에는 특별한 규칙이 있습니다.

• 1ドル$번 위치부터 방문합니다.
• $i$번 위치를 방문한 후에 $i+1$번 위치를 방문합니다.
  • 즉 간식을 숨길 수 있는 위치가 $s$개 있을 때 가희는 1ドル$번, 2ドル$번, 3ドル$번, ... , $s$번 순서대로 방문합니다.
• 간식이 숨겨져 있는 위치에 방문하면 가희는 고구마 간식을 먹거나 그냥 갈 수 있습니다.
• 같은 위치를 다시 방문할 수 없습니다.
• 많아야 7ドル$개의 간식을 먹을 수 있습니다.

고구마 간식은 빨간색, 주황색, 노란색, 초록색, 파란색, 남색, 보라색 이렇게 7ドル$가지 종류가 있습니다. 아래 조건을 만족하도록 $s$개의 위치에 고구마 간식을 넣는 방법은 몇 가지인가요? $s$개의 위치 중에 어느 하나라도 넣어진 고구마 간식의 종류가 다르면 다른 가짓수로 취급합니다.

• 각 위치에는 7ドル$가지 종류 중 하나를 선택하여 고구마 간식을 반드시 한 개 넣어야 합니다.
• 가희가 특별한 규칙을 만족하면서 빨간색, 주황색, 노란색, 초록색, 파란색, 남색, 보라색 종류 순서대로 먹어야 하며, 그 방법은 하나 이상 있습니다.

입력

첫 줄에 $s$가 주어집니다.

출력

문제에 대한 답을 998ドル,244円,353円$으로 나눈 나머지를 출력해 주세요.

제한

• 1ドル \le s \le 50,299円$
• 빨간색, 주황색, 노란색, 초록색, 파란색, 남색, 보라색 고구마 간식은 $s$개보다 많이 있습니다.

힌트