DZY очень любит быстрое преобразование Фурье.

Быстрое преобразование Фурье — это алгоритм, используемый для эффективного подсчета свертки. В частности, если a, b и c — последовательности длины n, элементы которых индексированы от 0 до n - 1, и

Можно эффективно посчитать элементы последовательности c с помощью быстрого преобразования Фурье.

DZY внес небольшое изменение в формулу свертки. Теперь

Чтобы упростить себе задачу, будем считать, что a — перестановка целых чисел от 1 до n, а b — последовательность, состоящая только из 0 и 1. Даны a и b, DZY нужна ваша помощь, чтобы подсчитать c по новой формуле.

DZY крайне капризный, поэтому последовательности a и b заданы по-особенному. Заданы три целых числа n, d, x. Используйте приведенный ниже код, чтобы сгенерировать a и b.

//x - это 64-битная переменная
function getNextX() {
    x = (x * 37 + 10007) % 1000000007;
    return x;
}
function initAB() {
    for(i = 0; i < n; i = i + 1){
        a[i] = i + 1;
    }
    for(i = 0; i < n; i = i + 1){
        swap(a[i], a[getNextX() % (i + 1)]);
    }
    for(i = 0; i < n; i = i + 1){
        if (i < d)
            b[i] = 1;
        else
            b[i] = 0;
    }
    for(i = 0; i < n; i = i + 1){
        swap(b[i], b[getNextX() % (i + 1)]);
    }
}

Операция x % y обозначает остаток от деления x на y. Функция swap(x, y) меняет местами два значения, x и y.