Баш решил сделать перерыв в своем пути к становлению величайшим мастером покемонов, и поиграть с функциями.
Баш определил функцию f0(n), которая равна числу способов разложить число n на два множителя p и q такие, что gcd(p, q) = 1. Другими словами, f0(n) — число упорядоченных пар натуральных чисел (p, q) таких, что p·q = n и gcd(p, q) = 1.
Но Баш почувствовал, что эту функцию слишком просто посчитать. Поэтому он определил набор функций, где fr + 1 определена как:
где (u, v) — упорядоченная пара натуральных чисел, при этом они не обязательно взаимно простые.
Теперь Баш хочет узнать некоторые значения fr(n) для различных r и n. Так как эти значения могут быть большими, он хочет узнать остаток от деления этих значений на 109 + 7. Помогите ему!