Саша и Артём поспорили на настольную игру, что Саша поедет следующим летом на стажировку в Google. Саша любит настольные игры, так что решительно намерена выиграть спор. Но для того, чтобы поехать стажироваться, нужно сначала пройти собеседование.

Саша выяснила, что на собеседовании соискателю предлагается решить одну задачу, от которой и зависит, проходишь ты или нет. Причём, данную задачу можно разбивать на подзадачи, а именно, если вам досталась задача с номером $$$\overline{a_1 \dots a_n}$$$, вы можете вместо неё решить задачи с номерами $$$\overline{a_1 \dots a_k}$$$ и $$$\overline{a_{k+1} \dots a_n}$$$ (например, вместо 571-й задачи можно решить задачи 5 и 71). Эти задачи, в свою очередь, тоже можно разбивать на подзадачи.

Саша считает задачу простой, если её номер является простым числом, и собирается, получив на собеседовании задачу, разбить её на простые подзадачи и решать их. Также девушка хочет, чтобы все эти подзадачи были небольшими, а именно, чтобы длина их номера не превышала $$$k$$$.

Саша получила задачу номер $$$n$$$, сколькими способами она может разбить её на нужные (небольшие и простые) подзадачи?

Так как число способов может быть большим, выведите его по модулю $$$10^9 + 7$$$.