Description

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

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

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

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

All turned off (counts as one pattern)

Turn on one device, totaling 3 patterns

Turn on two devices, only 1 pattern

Calculating for 30 devices is more challenging, 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 should submit an integer only. Do not include any extraneous content.

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

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

Source

Final exam questions from the 9th Lanqiao Cup C/C++ Group B National Finals in 2018