Pracsiu Dan (dnprx) În teoria grafurilor, un graf planar este un graf care poate fi încorporat într-un plan, adică poate fi desenat în plan în așa fel încât muchiile sale să se intersecteze doar în noduri. Cu alte cuvinte, aceste poate fi desenat în așa fel încât oricare două muchii să nu se intersecteze. Florin urmează în perioada 2023-2029 studii în informatică. Pasionat de numere prime, a aflat că numărul 20232029 este un număr prim. Își pregătește o lucrare din capitolul grafurilor și are nevoie de ajutorul vostru.
Fiind date NR = 2 * N noduri fixe (asemănător cu ceasul clasic) în planul xOy și N muchii, Florin vrea să determine numărul grafurilor distincte planare în care fiecare nod va avea gradul 1.
Exemple:
Pentru N = 6 una din cele 5 variante de reprezentare este:
Pentru N = 4 există două soluții:
Cerința
Scrieţi un program care să determine numărul de grafuri obținute de Florin.
- Cerința1: Numărul de grafuri se va afișa modulo
20232029 - Cerința2: Numărul de grafuri se va afișa în întregime
Date de intrare
Fișierul de intrare planar.in conține pe prima linie două numere naturale C și NR reprezentând cerința și numărul par de noduri ale grafului.
Date de ieșire
Fișierul de ieșire planar.out va conține o singură linie pe care va fi scris rezultatul obținut.
Restricții și precizări
1 ≤ NR ≤ 10.000C = 1, 2
Exemplul 1:
planar.in
1 4
planar.out
2
Exemplul 2:
planar.in
1 50
planar.out
7744491
Explicație
4861946401452 % 20232029 = 7744491
Exemplul 3:
planar.in
2 50
planar.out
4861946401452