Dreieckige Pizza
Problem 747
Mama Triangolo hat eine dreieckige Pizza gebacken. Sie will die Pizza in $n$ Stücke schneiden. Sie wählt zuerst einen Punkt $P$ im Inneren (nicht am Rand) der Dreieckspizza und führt dann $n$ gerade Schnitte durch, die alle bei $P$ beginnen und am Rand der Pizza enden, so dass die $n$ Stücke alle Dreiecke darstellen und die gleiche Fläche haben.
Sei $\psi(n)$ die Anzahl der verschiedenen Möglichkeiten, unter diesen Einschränkungen die Pizza zu schneiden.
Zum Beispiel ist $\psi(3) = 7.$
Weiterhin gilt $\psi(6)=34$ und $\psi(10)=90$.
Sei $\Psi(m)=\displaystyle\sum_{n=3}^m \psi(n).$ Es gilt $\Psi(10)=345$ und $\Psi(1000)=172166601$.
Finden Sie $\Psi(10^8)$. Geben Sie Ihre Antwort modulo $1\,000\,000\,007$.