SP11947 GSWORDS - Counting Words

Supervin 热衷于计数，并邀请你一起参与。 他将由字符 'o' 和 'x' 组成的字符串称为「单词」。此外，这些「单词」还需满足：每个长度为质数的子串中，'o' 的数量必须不少于 'x'。 现在，Supervin 给了你一个整数 $N$（$1 \leq N \leq 10^{12}$），他要你计算出总共有多少种长度为 $N$ 的「单词」。 考虑到答案可能非常庞大，最终请输出这些「单词」的数量对 $1\,000\,000\,007$ 取余的结果。

输入为一行，一个整数 $N$。

输出为一行，表示长度为 $N$ 的「单词」的数量对 $1\,000\,000\,007$ 取余的整数。 **本翻译由 AI 自动生成**