Morse code, also known as Morse code, is a kind of on-off signal code, which expresses different English letters, numbers and punctuation symbols through different order. It was invented in 1837 and is an early form of digital communication. Different from modern digital communication, Morse code consists of two basic signals: short point signal "•" and reading "drop"; Keep the long signal "-" for a certain time and read "Da".

In order to increase the difficulty of decoding, the communication group decided that there must be more than one short message number "•" between every two long signals "-" in Morse code of any length, otherwise it will be regarded as invalid code. For example, the number of schemes of an effective Morse code with a length of 3 is 5, which are respectively: - • -, - • •, - • -, • • -, • • •.

Here is the length of Morse code. Do you know the number of effective Morse code schemes?

The input has multiple cases (no more than 100) of test data.

Each test case occupies one line, which is a positive integer N（1 ≤ N ≤ 1000000） represents the length of the Morse code given to you.

The end of input will be represented by a line of test case where A equal to 0. This test case should not be processed.

Each test case outputs a line, which is an integer, that is, the modular result of 2021 by the number of schemes of effective Morse code.