Dãy ước liên tiếp (Bản dễ)

Xem PDF




Thời gian:
Scratch 15.0s

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một số \(n\) bất kì luôn có \(1\) tập ước số không chứa \(1\) riêng của nó, dù là số nguyên tố hay hợp số. Ví dụ như số \(6\) có tập ước số không chứa \(1\)\((2;3;6)\), còn số \(420\) có tập ước số không chứa \(1\)\((2;3;4;5;6;7;10;12;14;15;20;21;28;35;60;84;105;140;210;420)\). Trinh mới học thêm về số nguyên tố và hợp số, liền về nhà lấy giấy ra viết \(1\) số \(420\) và dãy ước không chứa \(1\) của chính số \(420\) ấy. Viết xong rồi, cậu nhìn lại thì thắc mắc: Ủa? Sao có nhiều đoạn số liên tiếp thế này? Có đoạn có tới \(6\) số liên tiếp lận? (Nếu bạn thắc mắc là đoạn nào, thì đó là đoạn \((2;3;4;5;6;7)\) đấy) Rồi cô nghĩ tiếp: Thế nếu mình muốn tạo ra \(1\) số \(n\) bất kì mà trong dãy ước ấy có ít nhất \(1\) đoạn liên tiếp có \(k\) số thì làm thế nào nhỉ? Cô bí bài này nên cô muốn nhờ các bạn ở LQDOJ rằng: Cho \(1\) số tự nhiên \(k(k\le 100)\), hãy tìm số nguyên dương \(n\) bé nhất có thể mà trong dãy ước số không chứa \(1\) của nó có ít nhất \(1\) đoạn số liên tiếp có chiều dài không nhỏ hơn \(k\).

Input

  • Duy nhất \(1\) số \(k\)

Output

  • Ans mod cho \(10^9+7\).

Example

Test 1

Input
2
Output
6
Note

Giải thích: Tuy số \(420\) như VD trên kia có dãy ước của chính nó cũng có \(7\) đoạn thỏa mãn (là \((2;3;4;5;6;7)\) (gồm \(5\) đoạn liên tiếp độ dài \(k\) nhỏ hơn), \((14;15)\)\((20;21)\)), nhưng vì chính số \(6\) cũng có đoạn thỏa mãn (là \((2;3)\)) và \(6\) là số bé nhất nên đáp án là số \(6\).


Bình luận