{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou are given an integer array $$$a_1, a_2, \\ldots, a_n$$$.\u003c/p\u003e\u003cp\u003eThe array $$$b$$$ is called to be a \u003cspan class\u003d\"tex-font-style-it\"\u003esubsequence\u003c/span\u003e of $$$a$$$ if it is possible to remove some elements from $$$a$$$ to get $$$b$$$.\u003c/p\u003e\u003cp\u003eArray $$$b_1, b_2, \\ldots, b_k$$$ is called to be \u003cspan class\u003d\"tex-font-style-it\"\u003egood\u003c/span\u003e if it is not empty and for every $$$i$$$ ($$$1 \\le i \\le k$$$) $$$b_i$$$ is divisible by $$$i$$$.\u003c/p\u003e\u003cp\u003eFind the number of good subsequences in $$$a$$$ modulo $$$10^9 + 7$$$. \u003c/p\u003e\u003cp\u003eTwo subsequences are considered different if index sets of numbers included in them are different. That is, the values of the elements do not matter in the comparison of subsequences. In particular, the array $$$a$$$ has exactly $$$2^n - 1$$$ different subsequences (excluding an empty subsequence).\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer $$$n$$$ ($$$1 \\le n \\le 100\\,000$$$)\u0026nbsp;— the length of the array $$$a$$$.\u003c/p\u003e\u003cp\u003eThe next line contains integers $$$a_1, a_2, \\ldots, a_n$$$ ($$$1 \\le a_i \\le 10^6$$$).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint exactly one integer\u0026nbsp;— the number of good subsequences taken modulo $$$10^9 + 7$$$.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n2 2 1 22 14\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example, all three non-empty possible subsequences are good: $$$\\{1\\}$$$, $$$\\{1, 2\\}$$$, $$$\\{2\\}$$$\u003c/p\u003e\u003cp\u003eIn the second example, the possible good subsequences are: $$$\\{2\\}$$$, $$$\\{2, 2\\}$$$, $$$\\{2, 22\\}$$$, $$$\\{2, 14\\}$$$, $$$\\{2\\}$$$, $$$\\{2, 22\\}$$$, $$$\\{2, 14\\}$$$, $$$\\{1\\}$$$, $$$\\{1, 22\\}$$$, $$$\\{1, 14\\}$$$, $$$\\{22\\}$$$, $$$\\{22, 14\\}$$$, $$$\\{14\\}$$$.\u003c/p\u003e\u003cp\u003eNote, that some subsequences are listed more than once, since they occur in the original array multiple times.\u003c/p\u003e"}}]}