Ели дефинира следната безкрайна редица. В началото редицата съдържа единствено цифрата нула. На всяка стъпка момичето копира досегашната редица, заменя нулите с единици, и единиците – с нули, и накрая долепя промененото копие до досегашната редица. Така първите няколко операции изглеждат по следния начин: 0 → 01 → 0110 → 01101001 → 0110100110010110 → 01101001100101101001011001101001 → …. Както можете да забележите, при прилагане на операцията първите символи на редицата се запазват, а дължината ѝ нараства двойно.

Учителката по информатика на Ели беше възхитена от редицата ѝ, и сега е дала за домашно на останалите ученици да имплементират генератор на тази редица. За да провери дали генераторите им са верни, техните програми трябва да могат да отговарят на въпроси от типа "Колко единици има между L-тата и R-тата позиция, включително?".

Можете ли и вие да се справите с този проблем, отговаряйки на N въпроса от този вид? На единствен ред на стандартния вход ще бъдат зададени пет цели числа N, F, A, B, и M. С тях можете да генерирате 2 * N цели числа: P₁, P₂, …, P_2N. Първото число P₁ e F, а всяко следващо e P_i+1 = (P_i * A + B) % M.

Интервалите, чиито брой единици трябва да намерите, са {[P₁, P₂], [P₃, P₄], … [P_2N-1, P_2N]}. Считаме за валидни интервали и тези, в които първият индекс е по-голям от втория – например [13, 42] е еквивалентен на [42, 13]. Индексирането в редицата започва от нула; тоест първата цифра в редицата (първата нула) е с индекс 0, втората цифра (първата единица) е с индекс 1, и т.н. Тъй като изходът може да стане много голям, вместо броя единици във всеки от N-те интервала, от вас се иска да изведете на стандартния изход едно единствено число – XOR-ът на намерените числа.

• 1 ≤ N ≤ 10,000,000
• 0 ≤ F, A, B < M ≤ 1,000,000,007

Примерен Вход	Примерен Изход
6 5 3 7 31	8
1337666 42 131 55 1000000007	282762915