a143. TOI 2019/10 潛力組：道路鋪設

題目描述

一條道路長 L，每種整數長度 1 到 L 的磁磚都有無限片。磁磚依序鋪設，不能重疊、不能留空，也不能切割。請計算鋪滿道路的方法數；若各片磁磚由左至右的長度順序不同，就視為不同方法。

輸入格式

第一行為詢問數 T，接著 T 行各有一個長度 L。 1 ≤ T ≤ 10000；1 ≤ L ≤ 1000000000。

輸出格式

每個詢問輸出一行，為方法數除以 1000000007 的餘數。

來源

TOI 2019/10/21~2019/10/31 潛力組〈道路鋪設〉。本題以自寫文字重述規則，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/201910/A2-Roads.pdf