#include <iostream>
#include <string>
 
//
// a class for computing the n-bit sequences with no adjacent 1's
//
// Approach taken was to search the entire solution space for all n-bit 
// sequences that satisfy the criteria
// An small optimization was made to prune the solution space by not checking 
// the lower bits of a sequence if 
// an adjacent pair of 1's is found in the higher bits.
//
class NBitSequenceTest
{
public:
	//
	// constructor takes the number of bits in the sequence
	//
	NBitSequenceTest(unsigned int n);
 
	//
	// outputs all n bit sequences with no consecutive 1's to standard output. 
	// returns the number of sequences found.
	//
	unsigned int Evaluate() const;
 
private:
 
	//
	// returns the position of the least significant bit of the pair of
	// adjacent 1's in the number. returns -1 if there are no adjacent 1s
	// in the bit pattern.
	//
	int hasAdjacentBitSetAtPosition(unsigned int number) const;
 
	//
	// helper function for numberToBinaryString tests if a bit at a certain position is set. 
	//
	bool isBitSet(unsigned int number, unsigned int nBit) const;
 
	//
	// outputs the input number as a string in binary format 
	//
	std::string numberToBinaryString(unsigned int number) const;
 
	//
	// store the number of bits in the sequence
	//
	unsigned int m_nDigits;
 
};
 
inline bool NBitSequenceTest::isBitSet(unsigned int number, unsigned int nBit) const
{
	return (number & 1 << nBit) != 0;
}
 
NBitSequenceTest::NBitSequenceTest(unsigned int n) : m_nDigits(n)
{}
 
std::string NBitSequenceTest::numberToBinaryString(unsigned int number) const
{
	std::string strBinary(m_nDigits, '0');
	int bitPos = 0;
	for (std::string::reverse_iterator i = strBinary.rbegin(); i != strBinary.rend(); i++)
	{
		if (isBitSet(number,bitPos++))
			*i = '1';
	}
 
	return strBinary;
}
 
int NBitSequenceTest::hasAdjacentBitSetAtPosition(unsigned int number) const
{
	//
	// our minimum condition is 2 adjacent bits set,
	// so our test will loop through the bits looking for this pattern
	//
	const unsigned int twoBits = 1 | 1 << 1;
	int pos = -1;
	bool bStopChecking = false;
	for (unsigned int i = 0; i < (m_nDigits - 1) && !bStopChecking; i++)
	{
		unsigned int currentMask = twoBits << i;
		if ((number & currentMask) == currentMask)
		{
			pos = i;
			bStopChecking = true; 
		}
		else if (number < currentMask)
		{
			//
			// no point chekcing any further as the bits will all be zero
			//
			bStopChecking = true;
		}
	}
 
	return pos;
}
 
unsigned int NBitSequenceTest::Evaluate() const
{
	const unsigned int upperBound = (1 << m_nDigits);
	unsigned int i = 0;
	unsigned int count = 0;
	do
	{
		int posBitPair = hasAdjacentBitSetAtPosition(i);
		if (posBitPair < 0)
		{
			std::cout << numberToBinaryString(i++) << std::endl;
			count++;
		}
		else
		{
			//
			// optimization... if we found a pair of adjacent bits they will remain set 
			// until the lsb of the bit pair flips back to zero when the remaining lower 
			// significant bits overflow and reset
			// back to all zeros. so we can skip these candidates
			//
			i += (1 << posBitPair);
		}
 
	} while (i < upperBound);
 
	return count;
}
 
 
int main() {
	int n;
	std::cin >> n;
 
	NBitSequenceTest b(n);
 
	std::cout << b.Evaluate() << " results found" << std::endl;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgoKLy8KLy8gYSBjbGFzcyBmb3IgY29tcHV0aW5nIHRoZSBuLWJpdCBzZXF1ZW5jZXMgd2l0aCBubyBhZGphY2VudCAxJ3MKLy8KLy8gQXBwcm9hY2ggdGFrZW4gd2FzIHRvIHNlYXJjaCB0aGUgZW50aXJlIHNvbHV0aW9uIHNwYWNlIGZvciBhbGwgbi1iaXQgCi8vIHNlcXVlbmNlcyB0aGF0IHNhdGlzZnkgdGhlIGNyaXRlcmlhCi8vIEFuIHNtYWxsIG9wdGltaXphdGlvbiB3YXMgbWFkZSB0byBwcnVuZSB0aGUgc29sdXRpb24gc3BhY2UgYnkgbm90IGNoZWNraW5nIAovLyB0aGUgbG93ZXIgYml0cyBvZiBhIHNlcXVlbmNlIGlmIAovLyBhbiBhZGphY2VudCBwYWlyIG9mIDEncyBpcyBmb3VuZCBpbiB0aGUgaGlnaGVyIGJpdHMuCi8vCmNsYXNzIE5CaXRTZXF1ZW5jZVRlc3QKewpwdWJsaWM6CgkvLwoJLy8gY29uc3RydWN0b3IgdGFrZXMgdGhlIG51bWJlciBvZiBiaXRzIGluIHRoZSBzZXF1ZW5jZQoJLy8KCU5CaXRTZXF1ZW5jZVRlc3QodW5zaWduZWQgaW50IG4pOwoKCS8vCgkvLyBvdXRwdXRzIGFsbCBuIGJpdCBzZXF1ZW5jZXMgd2l0aCBubyBjb25zZWN1dGl2ZSAxJ3MgdG8gc3RhbmRhcmQgb3V0cHV0LiAKCS8vIHJldHVybnMgdGhlIG51bWJlciBvZiBzZXF1ZW5jZXMgZm91bmQuCgkvLwoJdW5zaWduZWQgaW50IEV2YWx1YXRlKCkgY29uc3Q7Cgpwcml2YXRlOgoKCS8vCgkvLyByZXR1cm5zIHRoZSBwb3NpdGlvbiBvZiB0aGUgbGVhc3Qgc2lnbmlmaWNhbnQgYml0IG9mIHRoZSBwYWlyIG9mCgkvLyBhZGphY2VudCAxJ3MgaW4gdGhlIG51bWJlci4gcmV0dXJucyAtMSBpZiB0aGVyZSBhcmUgbm8gYWRqYWNlbnQgMXMKCS8vIGluIHRoZSBiaXQgcGF0dGVybi4KCS8vCglpbnQgaGFzQWRqYWNlbnRCaXRTZXRBdFBvc2l0aW9uKHVuc2lnbmVkIGludCBudW1iZXIpIGNvbnN0OwoKCS8vCgkvLyBoZWxwZXIgZnVuY3Rpb24gZm9yIG51bWJlclRvQmluYXJ5U3RyaW5nIHRlc3RzIGlmIGEgYml0IGF0IGEgY2VydGFpbiBwb3NpdGlvbiBpcyBzZXQuIAoJLy8KCWJvb2wgaXNCaXRTZXQodW5zaWduZWQgaW50IG51bWJlciwgdW5zaWduZWQgaW50IG5CaXQpIGNvbnN0OwoKCS8vCgkvLyBvdXRwdXRzIHRoZSBpbnB1dCBudW1iZXIgYXMgYSBzdHJpbmcgaW4gYmluYXJ5IGZvcm1hdCAKCS8vCglzdGQ6OnN0cmluZyBudW1iZXJUb0JpbmFyeVN0cmluZyh1bnNpZ25lZCBpbnQgbnVtYmVyKSBjb25zdDsKCQoJLy8KCS8vIHN0b3JlIHRoZSBudW1iZXIgb2YgYml0cyBpbiB0aGUgc2VxdWVuY2UKCS8vCgl1bnNpZ25lZCBpbnQgbV9uRGlnaXRzOwoKfTsKCmlubGluZSBib29sIE5CaXRTZXF1ZW5jZVRlc3Q6OmlzQml0U2V0KHVuc2lnbmVkIGludCBudW1iZXIsIHVuc2lnbmVkIGludCBuQml0KSBjb25zdAp7CglyZXR1cm4gKG51bWJlciAmIDEgPDwgbkJpdCkgIT0gMDsKfQoKTkJpdFNlcXVlbmNlVGVzdDo6TkJpdFNlcXVlbmNlVGVzdCh1bnNpZ25lZCBpbnQgbikgOiBtX25EaWdpdHMobikKe30KCnN0ZDo6c3RyaW5nIE5CaXRTZXF1ZW5jZVRlc3Q6Om51bWJlclRvQmluYXJ5U3RyaW5nKHVuc2lnbmVkIGludCBudW1iZXIpIGNvbnN0CnsKCXN0ZDo6c3RyaW5nIHN0ckJpbmFyeShtX25EaWdpdHMsICcwJyk7CglpbnQgYml0UG9zID0gMDsKCWZvciAoc3RkOjpzdHJpbmc6OnJldmVyc2VfaXRlcmF0b3IgaSA9IHN0ckJpbmFyeS5yYmVnaW4oKTsgaSAhPSBzdHJCaW5hcnkucmVuZCgpOyBpKyspCgl7CgkJaWYgKGlzQml0U2V0KG51bWJlcixiaXRQb3MrKykpCgkJCSppID0gJzEnOwoJfQoKCXJldHVybiBzdHJCaW5hcnk7Cn0KCmludCBOQml0U2VxdWVuY2VUZXN0OjpoYXNBZGphY2VudEJpdFNldEF0UG9zaXRpb24odW5zaWduZWQgaW50IG51bWJlcikgY29uc3QKewoJLy8KCS8vIG91ciBtaW5pbXVtIGNvbmRpdGlvbiBpcyAyIGFkamFjZW50IGJpdHMgc2V0LAoJLy8gc28gb3VyIHRlc3Qgd2lsbCBsb29wIHRocm91Z2ggdGhlIGJpdHMgbG9va2luZyBmb3IgdGhpcyBwYXR0ZXJuCgkvLwoJY29uc3QgdW5zaWduZWQgaW50IHR3b0JpdHMgPSAxIHwgMSA8PCAxOwoJaW50IHBvcyA9IC0xOwoJYm9vbCBiU3RvcENoZWNraW5nID0gZmFsc2U7Cglmb3IgKHVuc2lnbmVkIGludCBpID0gMDsgaSA8IChtX25EaWdpdHMgLSAxKSAmJiAhYlN0b3BDaGVja2luZzsgaSsrKQoJewoJCXVuc2lnbmVkIGludCBjdXJyZW50TWFzayA9IHR3b0JpdHMgPDwgaTsKCQlpZiAoKG51bWJlciAmIGN1cnJlbnRNYXNrKSA9PSBjdXJyZW50TWFzaykKCQl7CgkJCXBvcyA9IGk7CgkJCWJTdG9wQ2hlY2tpbmcgPSB0cnVlOyAKCQl9CgkJZWxzZSBpZiAobnVtYmVyIDwgY3VycmVudE1hc2spCgkJewoJCQkvLwoJCQkvLyBubyBwb2ludCBjaGVrY2luZyBhbnkgZnVydGhlciBhcyB0aGUgYml0cyB3aWxsIGFsbCBiZSB6ZXJvCgkJCS8vCgkJCWJTdG9wQ2hlY2tpbmcgPSB0cnVlOwoJCX0KCX0KCglyZXR1cm4gcG9zOwp9Cgp1bnNpZ25lZCBpbnQgTkJpdFNlcXVlbmNlVGVzdDo6RXZhbHVhdGUoKSBjb25zdAp7Cgljb25zdCB1bnNpZ25lZCBpbnQgdXBwZXJCb3VuZCA9ICgxIDw8IG1fbkRpZ2l0cyk7Cgl1bnNpZ25lZCBpbnQgaSA9IDA7Cgl1bnNpZ25lZCBpbnQgY291bnQgPSAwOwoJZG8KCXsKCQlpbnQgcG9zQml0UGFpciA9IGhhc0FkamFjZW50Qml0U2V0QXRQb3NpdGlvbihpKTsKCQlpZiAocG9zQml0UGFpciA8IDApCgkJewoJCQlzdGQ6OmNvdXQgPDwgbnVtYmVyVG9CaW5hcnlTdHJpbmcoaSsrKSA8PCBzdGQ6OmVuZGw7CgkJCWNvdW50Kys7CgkJfQoJCWVsc2UKCQl7CgkJCS8vCgkJCS8vIG9wdGltaXphdGlvbi4uLiBpZiB3ZSBmb3VuZCBhIHBhaXIgb2YgYWRqYWNlbnQgYml0cyB0aGV5IHdpbGwgcmVtYWluIHNldCAKCQkJLy8gdW50aWwgdGhlIGxzYiBvZiB0aGUgYml0IHBhaXIgZmxpcHMgYmFjayB0byB6ZXJvIHdoZW4gdGhlIHJlbWFpbmluZyBsb3dlciAKCQkJLy8gc2lnbmlmaWNhbnQgYml0cyBvdmVyZmxvdyBhbmQgcmVzZXQKCQkJLy8gYmFjayB0byBhbGwgemVyb3MuIHNvIHdlIGNhbiBza2lwIHRoZXNlIGNhbmRpZGF0ZXMKCQkJLy8KCQkJaSArPSAoMSA8PCBwb3NCaXRQYWlyKTsKCQl9CgoJfSB3aGlsZSAoaSA8IHVwcGVyQm91bmQpOwoKCXJldHVybiBjb3VudDsKfQoKCmludCBtYWluKCkgewoJaW50IG47CglzdGQ6OmNpbiA+PiBuOwoKCU5CaXRTZXF1ZW5jZVRlc3QgYihuKTsKCglzdGQ6OmNvdXQgPDwgYi5FdmFsdWF0ZSgpIDw8ICIgcmVzdWx0cyBmb3VuZCIgPDwgc3RkOjplbmRsOwp9

MTA=

10