Задача 747
Треугольная пицца

Матушка Треуголо испекла треугольную пиццу. Она хочет разрезать ее на $n$ кусков. Сначала она выбирает точку $P$ внутри (не на границе) треугольной пиццы, а затем делает $n$ разрезов, которые начинаются в точке $P$ и идут по прямой до границы пиццы, так что все получившиеся $n$ кусков являются треугольниками и имеют одинаковую площадь.

Пусть $\psi(n)$ будет количеством разных способов, как матушка Треуголо может разрезать пиццу, следуя указанным выше условиям.
Например, $\psi(3)=7$.

Также, $\psi(6)=34$ и $\psi(10)=90$.

Пусть $\Psi(m)=\displaystyle\sum_{n=3}^m \psi(n)$. Известно, что $\Psi(10)=345$ и $\Psi(1000)=172166601$.

Найдите $\Psi(10^8)$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net