Recall that a binary string is a string consisting of the characters 0 and/or 1. A substring of a binary string is defined as its continuous subsequence.

Suppose you have a binary string $$$s$$$. You can perform the following sequence of operations on it:

• during the first operation, you can either do nothing or select any substring of length $$$1$$$ consisting of zeros in $$$s$$$ and remove it;
• during the second operation, you can either do nothing or select any substring of length $$$2$$$ consisting of zeros in $$$s$$$ and remove it;
• during the third operation, you can either do nothing or select any substring of length $$$4$$$ consisting of zeros in $$$s$$$ and remove it;
• and so on (during the $$$i$$$-th operation, a substring of length $$$2^{i-1}$$$ is selected).

After each removal, the resulting parts of the string are glued together in the same order. The operations can be terminated at any moment (including leaving the string unchanged).

We call a binary string beautiful if it is possible to remove all zeros from it using such a sequence of operations. For example:

• 000 is a beautiful string: 000 $$$\rightarrow$$$ 00 $$$\rightarrow$$$ $$$\varepsilon$$$ (where $$$\varepsilon$$$ denotes the empty string);
• 10100000000100 is a beautiful string: 10100000000100 $$$\rightarrow$$$ 1100000000100 $$$\rightarrow$$$ 11000000001 $$$\rightarrow$$$ 11000000001 $$$\rightarrow$$$ 111;
• 111 is a beautiful string, as it already contains no zeros;
• 010100 is not a beautiful string.

Your task is to count the number of beautiful binary strings of length $$$n$$$.