由0和1组成的串中,不能被分解为多个相同子串的字符串称为本原串。例如,100100不是本原串,因为它能被分解为两个100;而1101是本原串,因为它不能被分解为多个相同的子串。请你计算长度为n(0<n<=100000000)的0-1串中,有多少个本原串?由于最终的结果可能会很大,因此请输出答案%2017(答案数取模2017)。
例如:
n = 1, 则输出:2
n = 2, 则输出:2
说明:长度为1的本原串有两个,分别为"0"、"1"; 长度为2的本原串也有两个,分别为"01"、"10"。
输入:n = 1
输出:2