A. Amusing Enhancements
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Leon has just finished his talk and now wants to take a photo of the participants for his social media. The photo consists of a row of people arranged in a horizontal line. Ryei was chosen to assemble a photo with a total fun level of exactly $$$D$$$, where each person added to the photo increases the fun level by $$$1$$$.

Ryei initially planned to just line up $$$D$$$ normal people to reach the required fun level, but Leon wanted more variety. He decided that, when assembling the photo, any person added can be enhanced using AI, making them contribute $$$2$$$ to the total fun level instead of $$$1$$$.

Leon is now interested in the number of different enhancement configurations for photos that have fun exactly $$$D$$$ with any number of people, considering that each person is indistinguishable; that is, the number of possible orders of normal and enhanced participants that result in a picture with fun level $$$D$$$ . Since this number can be large, Leon wants it modulo $$$2026$$$, because he's a modern entity.

Leon's AI enhancement

Since Ryei can't stop laughing whenever he sees an enhanced photo, he needs your help to write a program that counts what Leon wants.

Input

The input consists of a single integer $$$D$$$ $$$(1 \leq D \leq 10^6)$$$, the total fun level required by Leon.

Output

Your program should print a single integer on one line: the number of enhancement configurations that produce photos with fun exactly $$$D$$$, modulo $$$2026$$$.

Examples
Input
1
Output
1
Input
4
Output
5
Input
2026
Output
1
Note

For the Second sample ($$$D = 4$$$), there are $$$5$$$ possible configurations:

  • $$$1+1+1+1$$$
  • $$$2+1+1$$$
  • $$$1+2+1$$$
  • $$$1+1+2$$$
  • $$$2+2$$$