pviz

Time limit: 0.02s
Memory limit: 64MB
Input: pviz.in
Output: pviz.out

Fie N un număr natural nenul şi P o permutare de lungime N a numerelor din multimea {1, 2, ..., N}. Definim un element vizibil în permutarea P ca fiind un număr PiP_i care are proprietatea că Pj<PiP_j < P_i, 1 ≤ j < i sau i=1.

Cerinţă

Determinaţi numărul X de permutări de lungime N care au ca elemente vizibile exact M elemente date.

Date de intrare

Fişierul de intrare pviz.in conţine pe prima linie două numere naturale N şi M, cu semnificaţia din enunţ, separate printr-un spaţiu. A doua linie a fişierului conţine M numere naturale distincte, ordonate crescător, separate prin câte un spaţiu, reprezentând elementele vizibile.

Date de ieşire

Fişierul de ieşire pviz.out va conţine o singură linie pe care va fi scris un număr natural reprezentând restul împărţirii numărului X la 10007.

Restricţii şi precizări

  • 1 ≤ N ≤ 2000
  • 1 ≤ M ≤ N
  • Elementele vizibile sunt scrise în fişierul de intrare în ordine crescătoare.
  • Pentru 10% din teste N ≤ 10
  • Pentru 20% din teste N ≤ 14
  • Pentru 60% din teste N ≤ 375

Exemplu

pviz.in

4 2
2 4

pviz.out

3	

Sunt 3 permutări, de lungime 4, care au pe 2 şi 4 ca elemente vizibile:

2 4 3 1
2 4 1 3
2 1 4 3

Permutarea 2 3 4 1 nu corespunde cerinţei deoarece are ca elemente vizibile atât pe 2 şi 4 cât şi pe 3.

Problem info

ID: 164

Editor: liviu

Author:

Source: ONI 2008 XI-XII: Ziua 1 Problema 3

Tags:

ONI 2008 XI-XII

Log in or sign up to be able to send submissions!