Description

To enhance the festive atmosphere, Planet X has arranged 30 laser devices in a straight line, projecting beams into space.

During installation and debugging, it was discovered that, for some unknown reason, two adjacent laser devices cannot be turned on simultaneously!

The king is very curious to know how many different laser effects can be produced given this bug.

Clearly, if there were only 3 devices, a total of 5 patterns could be formed, namely:

All turned off (counts as one pattern)

One device turned on, totaling 3 patterns

Two devices turned on, but only 1 pattern is possible

Calculating for 30 devices is more complicated, so the king has asked for your help.

You are required to submit an integer representing the number of possible patterns for 30 laser devices.

Input Format

None

Output Format

Note: You must submit an integer without any additional content.

```input1 无 ``` ```output1 一个整数（题目答案） ``` ## Hint

Note that you need to submit an integer only, do not include any extraneous content.

Source

2018 9th Lanqiao Cup C/C++ Group B National Finals Original Problem