Problem J
A Vicious Pikeman (Hard)
Note that this is a harder version of the problem pikemaneasy.
One of the reasons for this somewhat peculiar theory was the finding of ancient pike, a combat spear. Scientists have found many of these throughout the years. They come with a special symbol carved into them, usually the symbol of the tribe. This one didn’t have a symbol carved into it, it had pseudo code for Fenwick trees, as well as a config file for some kind of editor. Scientists are unsure which editor it might have been, but they believe it was some version of the closed Emacs beta.
Instead of looking for more evidence, the archeologists started speculating what strategy the pikemen used in these programming contests. They must have been well prepared, since this guy had algorithms carved into his spear. The contest rules were probably as follows: When submiting a solution to the judge, the time in minutes from contest start was added to a penalty counter. So in order to plan his problem solving, a pikeman must have been good at approximating the number of minutes required to solve each problem.
You are given a number of problems which were designed for a contest in which the pikeman participated. For each problem, you are given the estimated time in minutes for solving the problem. Calculate the maximum number of problems a pikeman can solve in the contest, and the minimum penalty he can get, under the assumptions that these estimations are correct. You may assume that the pikemen are very efficient: submissions are always correct, and after submitting a problem they start solving the next problem immediately.
Input
Input starts with two integers on a single line $1 \le N \le 10^9$ and $ 1 \le T \le 10^{18}$, the number of problems in the ancient contest and the total length of the contest in minutes. Then follows a line with four integers $1 \le A, B, C, t_0 \le 10^6$, where $t_0$ $(t_0\leq C)$ specifies the time in minutes required for solving the first problem, and the rest of the times $t_1, \dots , t_{N-1}$ are given by:
\begin{equation*} t_ i = ((At_{i-1}+B) \text {mod } C) + 1, i \in [1,N-1] \end{equation*}Output
Output should consist of two integers: the maximum number of problems a pikeman can solve within the time limit, and the total penalty he will get for solving them. As the penalty might be huge, print it modulo $1\, 000\, 000\, 007$. Print them on the same line, separated by a single space.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 3 2 2 2 1 |
1 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 10 2 2 2 2 |
2 4 |
