Рик и Морти пришли в магазин. Как вы уже поняли, Рик очень любит давать Морти разные задания. И этот случай не является исключением! Сейчас ему нужно подсчитать количество способов купить k продуктов. Всего в магазине n продуктов. Стоимость i-го продукта равняется ci. Рик будет q раз давать Морти два числа — l и r, Морти в свою очередь должен сказать, сколько существует способов купить k продуктов, чтобы их суммарная стоимость была не меньше l и не больше r. Обозначим покупку, как набор индексов {i1, i2, ..., ik}, где ij — номер товара, который был куплен j-м. Два способа покупки A и B называются различными, если (индекс товара, купленным d-м будем обозначать как Ad) существует такой индекс d, что Ad ≠ Bd. Таким образом (1, 2) и (2, 1) это два разных способа покупки товаров. Так же, заметьте, что один продукт можно покупать сколько угодно раз.
В первой строке входного файла содержатся три числа n, k, q, (1 ≤ n, q ≤ 105), (1 ≤ k ≤ 105). Во второй строке находится n целых чисел ci обозначающих стоимости товаров. Товар с индексом i имеет стоимость ci. (1 ≤ ci ≤ 5·104). Следующие q строк содержат два числа l и r обозначающие вопрос от Рика, (1 ≤ l ≤ r ≤ 5·104). Морти должен сказать, сколько существует способов купить k продуктов, чтобы их суммарная стоимость была не меньше l и не больше r.
В q строках выведите ответы на запросы Рика. Так как ответ может быть очень большим, выведите его по модулю 786433.
5 1 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 5
2
3
4
5
4
2 2 1
1 1
1 10000
4