Определим функцию \(f(p)\) от перестановки \(p\) следующим образом. Пусть \(g_i\) — наибольший общий делитель (НОД) чисел \(p_1\), \(p_2\), ..., \(p_i\) (другими словами, НОД на префиксе длины \(i\)). Тогда \(f(p)\) равно числу различных значений среди \(g_1\), \(g_2\), ..., \(g_n\).
Пусть \(f_{max}(n)\) — максимальное значение \(f(p)\) среди всех перестановок \(p\) чисел \(1\), \(2\), ..., \(n\).
Вам дано число \(n\), подсчитайте число перестановок \(p\) чисел \(1\), \(2\), ..., \(n\) таких, что \(f(p)\) равно \(f_{max}(n)\). Так как ответ может быть большим, выведите остаток от деления этого числа на \(1000\,000\,007 = 10^9 + 7\).
Примечание
Рассмотрим второй пример: ниже перечислены перестановки длины \(3\):
- \([1,2,3]\), \(f(p)=1\).
- \([1,3,2]\), \(f(p)=1\).
- \([2,1,3]\), \(f(p)=2\).
- \([2,3,1]\), \(f(p)=2\).
- \([3,1,2]\), \(f(p)=2\).
- \([3,2,1]\), \(f(p)=2\).
Максимальное значение \(f_{max}(3) = 2\), и существуют \(4\) перестановки \(p\) такие, что \(f(p)=2\).