Genijalac

Ο Mirko είναι ιδιοφυΐα. Όμως ο σκοπός των εφευρέσεών του δεν είναι πάντα προφανής. Η τελευταία του εφεύρεση, το Shuffle-o-matic ~3175~, είναι μία από αυτές. Το Shuffle-o-matic χρησιμοποιείται με πολύ ιδιαίτερο τρόπο. Πρώτα ο Mirko τοποθετεί ~N~ χάρτινες κάρτες, με τους αριθμούς ~1~ μέχρι ~N~ τυπωμένους πάνω τους, στην επιφάνεια εργασίας του Shuffle-o-matic. Μετά εισάγει την ακολουθία τυχαίας αναπαραγωγής στην ειδική κονσόλα εισόδου και πατά το κουμπί. Το μηχάνημα διαβάζει τις χάρτινες κάρτες και εκτυπώνει την ακολουθία ανάγνωσης των αριθμούς στην ταινία εξόδου του. Στη συνέχεια ανακατεύει τα χαρτιά σύμφωνα με την ακολουθία τυχαίας αναπαραγωγής. Μετά από αυτό διαβάζει τη νέα ακολουθία και τη γράφει σε μια νέα γραμμή στην ταινία εξόδου του. Στη συνέχεια ανακατεύει ξανά τις κάρτες σύμφωνα με την ίδια σειρά τυχαίας αναπαραγωγής, σαρώνει και γράφει την έξοδο στο ταινία-κασέτα. Το μηχάνημα το κάνει αυτό μέχρι να τελειώσει η ταινία.
Αφού πειραματίστηκε με το μηχάνημα, ο Mirko αποφάσισε να ξεκουραστεί λίγο στο πάτωμα. Εκεί παρατήρησε ένα κομμάτι ταινίας εξόδου. Το κομμάτι είναι προσεκτικά κομμένο λίγο πριν από το ~A~-η σειρά εξόδου και ακριβώς μετά τη ~B~-η σειρά εξόδου. Λείπει επίσης οι πρώτοι ~C~ αριθμοί και οι τελευταίοι αριθμοί ~D~ σε όλες τις σειρές.
Τώρα αναρωτιέται πόσες σειρές σε αυτό το χαρτί έχουν την ιδιότητα αυτή, όλοι οι αριθμοί στη σειρά, που είναι ακόμα στο χαρτί, είναι ακριβώς στο ίδιο σημείο που βρίσκονταν πριν ξεκινήσει όλο το ανακάτεμα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N~, ~A~, ~B~, ~C~ και ~D~ με αυτή τη σειρά ~(1 \le N \le 500\,000,\;A \le B \le 10^{12},\;0 \le C,\;D \le N,\;C + D < N)~.
Η δεύτερη γραμμή περιέχει την ακολουθία τυχαίας αναπαραγωγής. Η ακολουθία δίνεται ως μία μετάθεση των αριθμών ~1~ έως ~N~. Εάν ο ~k~-οστός αριθμός στην ακολουθία τυχαίας αναπαραγωγής είναι ~x~, μετά από κάθε ανακάτεμα το ~k~-οστό στοιχείο στην ακολουθία που προκύπτει είναι το ~x~-οστό στοιχείο στην προηγούμενη σειρά.

Έξοδος

Στην πρώτη και μοναδική γραμμή εξόδου εκτυπώστε τον αριθμό των σειρών που έχουν την ιδιότητα που ψάχνει ο Mirko.

Βαθμολογία

Τα αρχεία δοκιμής αξίας ~40~% των συνολικών πόντων έχουν ~A,\;B,\;C,\;D,\;N \le 2\,000~.

Παραδείγματα

input

4 1 5 0 1
1 3 4 2

output

2

Επεξήγηση του 1ου παραδείγματος

Το Shuffle-o-matic εκτυπώνεί:

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

Ο Mirko βρίσκει:

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

Η πρώτη και τέταρτη γραμμήε ενδιαφέρουν τον Mirko.

input

7 3 8 1 2
2 3 1 6 4 7 5

output

0

Επεξήγηση του 2ου Παραδείγματος

Το Shuffle-o-matic εκτυπώνεί:

1 2 3 4 5 6 7
2 3 1 6 4 7 5
3 1 2 7 6 5 4
1 2 3 5 7 4 6
2 3 1 4 5 6 7
3 1 2 6 4 7 5
1 2 3 7 6 5 4
2 3 1 5 7 4 6
3 1 2 4 5 6 7
1 2 3 6 4 7 5

input

6 2 11 3 0
6 3 5 4 2 1

output

1

Επεξήγηση του 3ου Παραδείγματος

Το Shuffle-o-matic εκτυπώνεί:

1 2 3 4 5 6
6 3 5 4 2 1
1 5 2 4 3 6
6 2 3 4 5 1
1 3 5 4 2 6
6 5 2 4 3 1
1 2 3 4 5 6
6 3 5 4 2 1
1 5 2 4 3 6
6 2 3 4 5 1
1 3 5 4 2 6