UTF-8 is one of the methods for coding multibyte characters.

Characters are treated as bytes on the computer. If it is only English, it can be expressed in 1 byte even if the Latin alphabet, numbers and symbols are combined, but unfortunately it is not possible to express the characters used all over the world in 1 byte, so the characters are expressed using multiple bytes. There is a need.

Here, for example, when a 2-byte string of 12354 (0x3042) is assigned to the character "a", if the byte strings are arranged as they are, it is indistinguishable whether it is 2 characters with 0x30,0x42 or 1 character with 0x3042.

For this reason, UTF-8, which is a multi-byte character encoding method, overcomes this problem by making it possible to know the length of the byte string that continues in the first byte. The specific bit pattern is as follows.

Here, x is an arbitrary bit of 0/1. Also, y can be any bit of 0/1, but one of them must be 1. It is assumed that all characters are 1, 2, 3, or 4-byte characters.

Here, the restriction that at least one bit of y is 1 is due to the following reasons. For example, when encoding'/' (0x2f) into a byte string, there are two methods, 0x2f and 1-byte coding, or 0xc0 0xaf and 2-byte coding, but allowing such ambiguity is for security reasons. This is because it may be a source of threats.

After hearing the above story, you were wondering how much freedom UTF-8 has. Specifically, how many combinations of bytes are possible as UTF-8 when some bits of a given byte sequence are unknown.

At this time, find the number of possible combinations of byte strings and output the remainder divided by 1,000,000.

Notes on Test Cases

Multiple datasets are given in the above input format. Create a program that outputs each data set in the above output format.

When N is 0, it indicates the end of input.

见题面

见题面