Tam Steiner Topologiyaları#3508
Bir full Steiner topology, verilmiş P = \{p_1, p_2, …, p_n\} nöqtə dəsti üçün istiqamətsiz bir ağacdır T = (V, E). Burada V = \{v_1, v_2, …, v_n, v_{n+1}, …, v_{2n-2}\} zirvələr dəstidir və kənarların dəstidir. -nin fərqli etiketli yarpaqları, v_1, v_2, …, v_n, müvafiq olaraq p_1, p_2, …, p_n-ə uyğundur; qalan n - 2 zirvələr, v_{n+1}, v_{n+2}, …, v_{2n-2}, Steiner zirvələri adlanır, bir-birindən fərqlənməzdir və hər biri üç dərəcəyə malikdir. Şəkil 1 P = \{p_1, p_2, p_3\} üçün yeganə full Steiner topology-ni göstərir. Şəkil 2 P = \{p_1, p_2, p_3, p_4\} üçün üç fərqli full Steiner topology-ni göstərir.
Şəkil 1: P = \{p_1, p_2, p_3\} üçün full Steiner topology
Şəkil 2: P = \{p_1, p_2, p_3, p_4\} üçün full Steiner topology-lar
Verilmiş , -nin kardinalı, fərqli full Steiner topology-larının sayını hesablayın.
Giriş bir neçə test halını ehtiva edir. Hər bir test halı ayrı bir sətirdə tək bir tam ədəd (3 ≤ n ≤ 10^7) ilə verilir. Giriş EOF ilə bitir.
Hər bir test halı üçün cavabı ayrı bir sətirdə çap edin. Cavabı dörd əhəmiyyətli rəqəmə yuvarlaqlaşdırılmış şəkildə çap etməlisiniz. m \cdot 10^e yuvarlaqlaşdırılmış cavabın elmi forması olsun, siz me çap etməlisiniz, burada -in bütün dörd əhəmiyyətli rəqəmini verərək və -dən əvvəlki hər hansı aparıcı sıfırları çıxararaq.
Nümunə 1