Fibonacci là một dãy số huyền bí được phát minh ra từ xa xưa, là nghiệm của \(1\) bài toán ít người biết đến trong bộ sách … gì gì đó ko nhớ nữa :))) . Những con số đầu tiên của dãy là \((1;1;2;3;5;8; ...)\). Trinh rất thích dãy số này, và thường xuyên cho Tấn xem những gì cô mới chơi đùa được với dãy số ấy. Tấn cũng đã học về dãy số ấy và phát hiện nó có một điều gì đó rất bất bình thường. Sau một hồi khám phá, cuối cùng mọi thứ được đúc kết trong câu đố của cậu cho Trinh:

Cho \(T\) số \(n\). Với mỗi số \(n\), tìm tổng các ước số của số Fibonacci thứ \(n\) mà nó là số Fibonacci, sao cho các ước không được trùng nhau (\(2\) số \(1\) đầu dãy được tính làm \(1\)).

Trinh, dù thích câu đố này, nhưng không thể làm nó vì cô đang bận xem bóng đá Vòng Loại thứ \(3\) World Cup khu vực Châu Á (hay ít nhất là cô nói với cậu thế). Trinh nhờ các bạn giải giúp câu đố này.

Nhưng mọi chuyện vẫn chưa kết thúc tại đây. Tấn còn ác hơn khi cho các số \(n\) của cậu ẩn trong \(1\) xâu kí tự \(S\), trong đó các số \(n\) được bao giữa các dấu ngoặc tròn “( )”, và số \(T\) của cậu bị ẩn và bạn sẽ chẳng biết được số \(T\) này. Mục đích của việc này là làm cho các bạn loạn mắt lên thôi chứ chẳng có gì cả :))) Trinh “trả giá” độ khó bài này vì các bạn và cuối cùng Tấn chỉ cho thêm \(1\) cái điều kiện “giảm bớt” là: Các cặp ngoặc không lồng vào nhau, chúng độc lập với nhau và không tác động lên các cặp ngoặc kia. Trinh đành chấp nhận thử thách của cậu và nhờ các bạn. Các bạn hãy giúp Trinh nhé 🙁 Các kết quả của cùng 1 số n in ra mỗi kết quả mỗi dòng.

Input

• Gồm \(1\) dòng duy nhất là xâu \(S\), chứa \(T\) số \(n\) (\(T\) ẩn và \(T≤100\) cùng với các \(n≤10^{12}\)).

Output

• Với mỗi số \(n\), mỗi dòng in \(1\) kết quả là tổng các ước số của số Fibonacci thứ n mà nó là số Fibonacci sau khi mod \(10^9+7\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n≤10^3.\)
• Subtask \(2\) (\(25\%\) số điểm): \(n≤10^6.\)
• Subtask \(3\) (\(25\%\) số điểm): \(n≤10^9.\)
• Subtask \(4\) (\(25\%\) số điểm): \(n≤10^{12}.\)

Example

12345(15)12345

618