셔플 테이프

준규는 카드를 섞는 기계를 만들었다. 이 기계에는 먼저 1부터 N까지의 수가 적힌 카드 N장을 순서대로 올려 둔다. 기계는 맨 처음 카드의 현재 순서를 읽어 테이프의 첫 줄에 출력한다. 그다음 주어진 셔플 수열대로 카드를 한 번 섞고, 다시 카드의 순서를 읽어 다음 줄에 출력한다. 이후에도 같은 셔플을 한 번씩 적용한 뒤 새 줄을 출력하는 과정을 반복한다.

기계를 시험한 뒤, 준규는 출력 테이프의 한 조각을 발견했다. 이 조각의 모든 줄에서는 앞에서부터 C개의 수와 뒤에서부터 D개의 수가 지워져 있었다.

섞기 전의 순서를 1번째 수열이라고 하자. A번째 수열부터 B번째 수열까지 중에서, 지워지지 않고 남아 있는 모든 위치의 값이 처음 섞기 전의 순서와 같은 수열이 몇 개인지 구해야 한다.

첫째 줄에 정수 N, A, B, C, D가 차례로 주어진다 (1 <= N <= 500000, A <= B <= 10^12, 0 <= C, D <= N, C + D < N).

둘째 줄에는 셔플 수열이 주어진다. 이 수열에는 1부터 N까지의 수가 정확히 한 번씩 등장한다. 수열의 k번째 수가 x라면, 한 번 셔플할 때 현재 k번째에 있는 카드를 x번째 위치로 옮긴다는 뜻이다.

준규가 찾는 수열의 개수를 출력한다.