P16935 The Grand Librarian

:::info[Problem Background] The grand hall beyond the stone gate was even quieter than any place the three had seen before. This quiet was not the dead silence of emptiness. It was more like a heavy stillness left behind after an extremely long span of years had been pressed down layer by layer. Towering stone pillars stretched up to a dome that was almost impossible to see clearly. Broken lamp stands, leaning bookshelves, and flaking stone carvings lay scattered around. A golden glow still covered the entire hall, but it no longer felt warm. Instead, it was like some old afterglow that had been frozen for far too long, staying here quietly, refusing to fully fade away. The three walked slowly along the long stairs in the center of the hall. The closer they got to the end, the thicker the magic in the air became. It was not the sharp, oppressive force given off by the traps or monsters before. It was something deeper, older, and harder to describe. It did not show hostility at once, yet it made people instinctively not want to get any closer, as if taking one more step forward would mean stepping into a past that should never be touched again. “Is this... the core of the library?” Fern asked softly. “Yes.” Frieren nodded lightly, but her eyes stayed fixed on the very top of the platform. There, the throne still stood in silence. It was even taller than it had looked from outside the door. The stone patterns spreading behind it were like an ancient star map sealed away layer after layer. But what made it impossible to look away was not the throne itself, but the mass that clung above it. It was a mass of magic that was hard to describe accurately with words. It had no fixed shape, like light yet like mist; like a very slowly flowing liquid, yet like an entire piece of starlight forcibly compressed together. Pale gold and white light intertwined within it, slowly rotating. From time to time, extremely tiny crack-like patterns would appear, as if time itself had shifted slightly on its surface. Just looking at it created a strange illusion—as if the breath of this very moment had been quietly stretched longer; or as if fragments from long ago were rising up again from the depths of memory. Stark frowned and lowered his voice instinctively. “What on earth is that thing?” Frieren watched quietly for a long time before speaking slowly. “It’s ancient magic at very high concentration,” she said. “And it’s not just remaining here... it has frozen the time around this area as well.” Fern froze slightly. Freezing time was not something ordinary spells could do. To keep the core of an entire library intact for a thousand years, and even now not truly collapse—this mass of magic itself was probably close to a dangerous miracle. But precisely because of that, no one could easily give an answer about how it should be handled. Leaving it alone was obviously not an option. Destroying it recklessly was just as dangerous. “It feels like... touching it will cause a huge disaster,” Stark muttered. “Yes.” Frieren’s tone remained calm. “It probably really will.” But she did not step back. She simply walked forward a few steps, stood before the throne, raised her head slightly, and stared at the ancient magic that seemed to compress a thousand years within it. After a moment, as if finally confirming something, she slowly lifted her hand and began to probe her magic toward it bit by bit. “Lady Frieren?” Fern spoke instinctively. “I’ll try to resonate with it first,” Frieren said softly. “Direct touch is too dangerous, but if we can figure out what kind of spell structure it is maintaining now, maybe we’ll know how to deal with it.” That thread of magic was extremely thin and light, like an almost invisible filament, carefully sinking into the frozen light. In the next instant, the entire hall trembled slightly. Not violently, but like something that had slept for a thousand years finally being awakened in this moment. That high-density ancient magic suddenly flared up. Pale gold and white light spread outward layer by layer, like silent ripples being lifted open, and in an instant swept across the whole hall. Fern instinctively stepped back half a step, and Stark immediately gripped his weapon, but there was no explosion, no shockwave—what truly began to change was time. The moss on the walls faded away at a speed visible to the naked eye. The dust that had accumulated on the floor over countless years slowly vanished. Those ancient books that had been rotten, blackened, and curled at the corners began to regain neatness and brightness on the shelves row by row: the patterns on their covers became clear, the pages turned white again. Even the broken, toppled lamp stands and stone carvings seemed to be patiently set upright by an invisible hand, returning to their original positions. The entire “Sunken Star Library” seemed to have its thousand years of weathering reversed in that single moment. The once-ruined and silent core hall gradually returned to a magnificent and complete appearance. Crystal lamps lit up one by one. Gentle light flowed along the dome and stone pillars. The bookshelves stood tall and orderly. Ancient spell patterns quietly extended across the floor, like a star map finally awakening again. Even faint human voices and the soft sound of pages turning appeared in the air, as if those everyday scenes long erased by time had not truly disappeared—only sealed for ages within this magic, and now finally projected again. Fern stared blankly around, even unconsciously softening her breathing. “This isn’t an illusion...” she murmured. “Yes.” Looking at the old scene unfolding before her, Frieren’s voice also became lighter. “It’s projecting the time it once froze directly outward.” And within that glory that returned, a real figure finally appeared upon the throne. It was not some monster, nor an empty shadow. A figure in an ancient robe sat high above, quietly looking down at the reawakened library. The patterns on the robe were solemn and complex. A thick tome that had not yet been closed lay at his side. His expression was so calm that it was almost without ripples, as if he had long been used to watching over this endless collection of books and time. Seated on that throne was the Grand Librarian from a thousand years ago. In that era more than a thousand years in the past, the analysis and reproduction of spell formulas had not yet become as mature as it is today. Once many powerful magics were lost, almost no one could restore them from memory. Therefore, magic could only be carefully recorded, copied, and sealed in grimoires. For this reason, the Grand Librarian who guarded a nation’s collection and the inheritance of spell formulas was never merely someone who watched over books—in some ancient countries founded on magic, their weight was even completely equal to that of a chief mage. Frieren’s gaze quickly fell on the heavy tome in the Grand Librarian’s hands. Its cover was not flashy. It even looked especially quiet because of its age. Yet the faint light flowing across it echoed with the frozen time of the entire “Sunken Star Library.” She realized almost immediately that it was the most valuable book in this library—“The Book of Time.” If one could truly master the spell formulas recorded within, it might not only delay or freeze time, but even hold the possibility of reversing time and crossing space. “Maybe... I could see Himmel once more.” Such a thought passed very lightly through Frieren’s mind. In the next moment, she leaned slightly forward and saluted the Grand Librarian on the throne. Seeing this, Fern and Stark also quietly bowed their heads with her. The calm figure above did not speak at once. He only watched them in silence with eyes that seemed to have seen through everything. After a moment, the Grand Librarian finally slowly closed the pages. His voice was deep and distant, as if passing through a thousand years, yet still clearly falling within this library. “I have long foreseen that visitors from the future would arrive here, and covet the ‘Book of Time’ in my hands.” “But anyone who wishes to take it must first prove they have the qualification worthy of it.” As he said this, his gaze swept over Frieren, Fern, and Stark in turn, and an ancient, solemn aura slowly spread across the hall along with it. ## 题目描述

In the library managed by the librarian, there are $n$ tomes arranged in a row, numbered $1\sim n$. Tome $i$ has importance $a_i$, so the tomes can be approximately viewed as a sequence $a$. For any non-empty sequence $S$, we define an “index sequence” $T$ of the **same length** as follows: $T_i$ represents the number of elements $S_j$ in $S$ such that $S_j\geq i$, that is, $T_i=\sum_{j=1}^{|S|}\mathbb{I}[S_j\geq i]$. We define the value $E(S)$ of sequence $S$ as the sum of the product of indices and the square of the “index sequence”, that is: $E(S)=\sum_{i=1}^{|S|} i\times T_i^2$. The librarian asks Frieren’s group $q$ questions. Each question contains two positive integers $l$ and $r$, meaning: after taking out the consecutive tomes with numbers in $[l, r]$ to form a tome sequence $S$, what is the value $E(S)$ of these tomes? For each question, output $E(S)$ modulo $10^9+7$.

The first line contains two integers $n, q(1\leq n, q\leq 10^5)$, representing the number of tomes and the number of queries asked by the librarian. The second line contains $n$ integers $a_1, a_2, ..., a_n(1\leq a_i\leq 10^9)$, representing the importance of tome $i$. The next $q$ lines each contain two integers $l, r(1\leq l\leq r\leq n)$, representing the left endpoint and right endpoint of a query.

Output $q$ lines. Each line outputs one integer, the result of the corresponding query’s $E(S)$ modulo $10^9+7$.

For the first query, $S=[3, 1, 4, 1, 5]$, the “index sequence” $T=[5, 3, 3, 2, 1]$, and the value is $1\times 5^2+2\times 3^2+3\times 3^2+4\times 2^2+5\times 1^2=91$. For the second query, $S=[1, 4, 1]$, the “index sequence” $T=[3, 1, 1]$, and the value is $1\times 3^2+2\times 1^2+3\times 1^2=14$. For the third query, $S=[4]$, the “index sequence” $T=[1]$, and the value is $1\times 1^2=1$. $\mathbb{I}[·]$ is the indicator function. If the expression inside the brackets is true, then the function value is $1$; otherwise, it is $0$. :::info[Problem Background] --- The Grand Librarian watched them in silence for a long time. That gaze was not sharp, nor did it deliberately press down with威压 (weiya). It only felt like, after endless years, he had finally waited for someone worthy to entrust with an answer. After a moment, he slowly nodded. In that expression that had always been calm and without ripples, there finally appeared a hint of something close to relief. The throne above was still covered in a soft and solemn glow. He only gently closed the heavy and ancient “Book of Time”, then raised his hand and handed it toward Frieren below the steps. “Your performance is satisfactory enough. Use it well, and you will surely make the right choice.” Frieren quietly walked forward, extended both hands, and solemnly received the tome that carried a thousand years of time. And at the instant her fingertips touched the cover, the entire hall suddenly trembled slightly. It was not the violent roar of battle. It was more like a dream that had been forcibly continued until now finally reaching its end. The warm, magnificent light around them dimmed little by little. The faint voices and the sound of page-turning in the air gradually drifted away. The tomes on the shelves that had just been new and neat began to rot and blacken again at a speed visible to the naked eye: pages curled, corners crumbled. Mottled cracks reappeared on the surfaces of the tall stone pillars. Dark red rust slowly crawled along the edges of the metal lamp stands and the throne. The floor lost its previous smoothness and completeness. Dampness seeped out again from the cracks. Fine moss slowly covered the stone seams, as if a thousand years of wind and frost were, along a断面 (duanmian) of time, falling back onto this “Sunken Star Library” once more. The figure on the throne also faded little by little within this slowly collapsing old scene, until only a quiet and blurry outline remained. Fern stared blankly around and gently held her breath. Stark also instinctively tightened his grip on the weapon in his hand, only slowly relaxing after confirming that everything was merely returning to normal. Only Frieren lowered her head to glance at the “Book of Time” in her arms, then raised her head and looked toward the hall that had become broken and silent again. Her tone was still calm, like she was stating a completely natural fact. “Looks like we’re back.” Translated by ChatGPT 5