{"trustable":false,"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":"MD","content":"\u003cp\u003eYou are given an integer array $$$a_1, a_2, \\ldots, a_n$$$.\u003c/p\u003e\n\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\n\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\n\u003cp\u003eFind the number of good subsequences in $$$a$$$ modulo $$$10^9 + 7$$$. \u003c/p\u003e\n\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\n给你一个整数数组 $a_1, a_2, \\ldots, a_n$.\n如果从数组 $a$ 中移除一些元素得到数组 $b$ ,那么 $b$ 被称作 $a$ 的子序列.\n数组 $b_1,b_2,\\ldots ,b_k$ 被称作好数组,当且仅当它是非空的,而且对于每个 $i (1 \\leqslant i \\leqslant k) b_i$ 都可以被 $i$ 整除。\n求出 $a$ 的所有是好数组的子序列的个数,答案模 $10^9+7$.\n 只要存在在 $a$ 中选择的元素的下标不同,那么两个子序列就不同,子序列是否相同与其中元素是否相同无关。具体地,数组 $a$ 有 $2^n-1$ 个不同的子序列,除去空集。"}},{"title":"Input","value":{"format":"MD","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\n\u003cp\u003eThe next line contains integers $$$a_1, a_2, \\ldots, a_n$$$ ($$$1 \\le a_i \\le 10^6$$$).\u003c/p\u003e\n第一行包含一个整数 $$$n$$$ ($$$1 \\le n \\le 100\\,000$$$) ,代表 $a$ 的长度。\n下一行包含 $n$ 个整数,分别为 $$$a_1, a_2, \\ldots, a_n$$$ ($$$1 \\le a_i \\le 10^6$$$)"}},{"title":"Output","value":{"format":"MD","content":"\u003cp\u003ePrint exactly one integer\u0026nbsp;— the number of good subsequences taken modulo $$$10^9 + 7$$$.\u003c/p\u003e\n输出一个整数,代表是好数组的子序列的总数,答案模 $10^9+7$"}},{"title":"Examples","value":{"format":"MD","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e2\u003cbr\u003e1 2\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e3\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e5\u003cbr\u003e2 2 1 22 14\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e13\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"MD","content":"\u003cp\u003eIn the first example, all three non-empty possible subsequences are good: $$$\\{1\\}$$$, $$$\\{1, 2\\}$$$, $$$\\{2\\}$$$\u003c/p\u003e\n\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\n\u003cp\u003eNote, that some subsequences are listed more than once, since they occur in the original array multiple times.\u003c/p\u003e\n在第一个例子中,一共有三个非空的好数组子序列: $\\{1\\}, \\{1, 2\\}, \\{2\\}$\n在第二个例子中,是好数组的子序列是: $$$\\{2\\}$$$, $$$\\{2, 2\\}$$$, $$$\\{2, 22\\}$$$, $$$\\{2, 14\\}$$$, $$$\\{2\\}$$$, $$$\\{2, 22\\}$$$, $$$\\{2, 14\\}$$$, $$$\\{1\\}$$$, $$$\\{1, 22\\}$$$, $$$\\{1, 14\\}$$$, $$$\\{22\\}$$$, $$$\\{22, 14\\}$$$, $$$\\{14\\}$$$.\n注意,有一些子序列被列出来多于一次,因为它们在原数组中出现多次"}}]}