Граничение по времени: 1.5 секунд Ограничение по памяти: 512 мегабайт

Граничение по времени: 1.5 секунд
Ограничение по памяти: 512 мегабайт
Имеется рекуррентная последовательность A1, A2, …, AN, строящаяся по следующему правилу:
A1 = K
Ai+1 = (Ai ? M) % (232 – 1) % L
Требуется найти сумму всех нечетных по порядку элементов в отсортированной по неубыванию последовательности по модулю L.
Для входных данных
5 7 13 100
последовательность будет такой:
{7; 7 ? 13%100 = 91; 91 ? 13%100 = 83; 83 ? 13%100 = 79; 79 ? 13%100 = 27}, то есть {10; 91; 83; 79; 27}.
Отсортированная последовательность {7; 27; 79; 83; 91}.
Сумма элементов на нечетных местах = (7 + 79 + 91)%100 = 77.
Формат входных данных:
N K M L
5000000 ? N ? 60000000, 0 ? K, L, M ? 232 – 1
Формат выходных данных:
RESULT
Примеры:
Стандартный ввод Стандартный вывод
5 7 13 100 77
Замечание. Для представления элементов последовательности необходимо использовать тип данных unsigned int.
Для получения массива используйте цикл:
a[0] = K;
for (int i = 0; i < N-1; i++)
a[i+1] = (unsigned int) ((a[i]*unsigned long long)M)&0xFFFFFFFFU)%L;
Внимание! Изменение типа данных и/или метода генерации элементов массива может привести (и на различных компиляторах приводит) к другой последовательности!