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 ψ(n) die Anzahl der verschiedenen Möglichkeiten, unter diesen Einschränkungen die Pizza zu schneiden.
Zum Beispiel ist ψ(3)=7.

Weiterhin gilt ψ(6)=34 und ψ(10)=90.

Sei Ψ(m)=mn=3ψ(n). Es gilt Ψ(10)=345 und Ψ(1000)=172166601.

Finden Sie Ψ(108). Geben Sie Ihre Antwort modulo 1000000007.