Bruce và Carl cùng chơi trò chơi “Tree Tiles” như sau:

• Carl sẽ chọn ra một tập con các loại hình của tập gồm 5 loại hình sau:

• Bruce sẽ đếm số lượng cách xếp các loại hình mà Carl đã chọn để phủ kín cây nhị phân đầy đủ độ sâu .

Ví dụ một cách phủ bằng loại hình 1 và loại hình 2

Yêu cầu: Cho biết các loại hình mà Carl chọn và số , hãy giúp Bruce đếm số lượng các xếp các loại hình mà Carl đã chọn để phủ kín cây nhị phân đầy đủ độ sâu .

Input

• Dòng đầu số nguyên dương  (
• Tiếp theo là 5 dòng, dòng  ghi số 0 – không chọn loại hình  hoặc số 1 – chọn loại hình .

Output

• Ghi số cách xếp chia dư cho 10¹⁵.