The foggy moors of Devonshire hold a secret that has haunted the Baskerville bloodline for centuries.

Sherlock Holmes has discovered that the creature's genes do not change randomly. They follow an ancient, ritualistic mutation pattern known as the "Descent of the Beast" .

If a creature $$$A$$$ is the direct progenitor of creature $$$B$$$, then for every gene position $$$i$$$, the transition must obey these laws:

The Fallen Gene : A type '1' gene is dominant but unstable; its child can remain a '1' or degrade into a '0'.

The Alpha Spark: A type '0' gene usually remains '0', but once in a millennium, it sparks into an Alpha Gene, denoted as '?'.

The Alpha's Burden: An Alpha Gene '?' is too powerful to sustain itself; its child cannot be another '?'. It must revert to either a '0' or a '1'.

Holmes has $$$Q$$$ new samples from his latest clash on the moors. For each sample string $$$X$$$, he tasks you, his trusted assistant, with two investigations:

Type 1: How many recorded strings $$$S_i$$$ in the archives could have been a direct parent of $$$X$$$?

Type 2: How many recorded strings $$$S_i$$$ in the archives could be a direct child of $$$X$$$?

Young Sherlock Holmes has just received his first official data set from Scotland Yard. It is a simple chronological record of $$$n$$$ crime reports from various districts in London.

To challenge himself, Sherlock decides he will only investigate the district with the highest number of reported crimes. If there are multiple districts with the same maximum number of crimes, Sherlock, being a man of efficiency, will choose the one that appeared earliest in the records.

https://wx9ydm.csb.app/

There are $$$n$$$ residents in the Medina, numbered from $$$1$$$ to $$$n$$$. After the crime, each resident gives exactly one statement during the police interrogation:

Some residents claim innocence, represented as $$$a_i = -1$$$.

Others point fingers at exactly one other resident, represented as $$$a_i = j$$$ ($$$1 \le j \le n, j \ne i$$$).

The local police are overwhelmed by the complexity of the case. As the night progresses and new evidence surfaces from various surveillance cameras in the Medina's narrow streets, the investigators realize that the reliability of witnesses keeps changing.

Sherlock is given $$$q$$$ intelligence reports. Each report states: "Exactly $$$k$$$ residents are telling the truth." For each report, Holmes must determine which residents could possibly be guilty. It is guaranteed that exactly one person committed the crime.

While investigating a peculiar case in Baker Street, Sherlock Holmes discovers a strange mechanical device left by Professor Moriarty. The device consists of N coins placed in a straight line on a table. Each coin shows either Head (H) or Tail (T).

Sherlock notices that the device follows very specific rules:

Sherlock can remove a coin only if it shows Head.

When Sherlock removes the coin at position i, a hidden mechanical switch activates and flips the state of the coins that were originally adjacent to it:

The coin that was originally to its left, if it exists.

The coin that was originally to its right, if it exists.

Two coins are considered neighbors only if they were adjacent in the initial arrangement, regardless of which coins have been removed afterward.

Sherlock Holmes has uncovered a secret society led by his archenemy — Professor Moriarty. Each member of this criminal network possesses a mysterious integer known as their Cipher Code.

Whenever two members meet, they produce a Conspiracy Signal equal to the bitwise XOR of their cipher codes.

Holmes is interested in analyzing entire groups of suspects. For any group, he defines the Grand Conspiracy Signal as the XOR of the Conspiracy Signals produced by every pair of suspects in the group.

Formally, for a range of suspects from index $$$l$$$ to $$$r$$$, the Grand Conspiracy Signal is:

$$$$$$ \bigoplus_{l \le i \lt j \le r} (a_i \oplus a_j) $$$$$$

However, the investigation is ongoing, and Dr. Watson frequently updates the suspects' cipher codes as new evidence appears.

Your task is to help Sherlock Holmes process the updates and answer his queries.

where $$$\oplus$$$ denotes the bitwise XOR operation.

Constraints

$$$1 \le n, q \le 2 \times 10^5$$$ ; $$$0 \le a_i, \text{val} \lt 10^{7}$$$ ; $$$1 \le \text{pos} \le n$$$ ; $$$1 \le l \le r \le n$$$

Sherlock Holmes has determined that the Grand Conspiracy Signal ($$$\mathcal{G}$$$) for any group of $$$k$$$ suspects chosen from the range $$$[l, r]$$$ is not merely the xor of their codes, but a complex interaction of their indices' internal bitwise structures.

Formal Definition Given an array $$$a$$$ of size $$$n$$$, and $$$q$$$ operations (updates or queries), define the Grand Conspiracy Signal for a range $$$[l, r]$$$ and subset size $$$k$$$ as:$$$$$$\mathcal{G}(l, r, k) = = \bigoplus_{l \le i_1 \lt i_2 \lt \dots \lt i_k \le r} \left( a_{\left( \bigoplus_{j_1 \subseteq i_1} j_1 \right)} \oplus a_{\left( \bigoplus_{j_2 \subseteq i_2} j_2 \right)} \oplus \dots \oplus a_{\left( \bigoplus_{j_k \subseteq i_k} j_k \right)} \right)$$$$$$

Where:

$$$\bigoplus$$$ denotes the bitwise XOR operation.

$$$j \subseteq i_m$$$ denotes that $$$j$$$ is a bitwise submask of $$$i_m$$$.

The outermost XOR sum is taken over all possible combinations of $$$k$$$ distinct indices within the interval $$$[l, r]$$$.

Operations :

1. Update($$$pos, val$$$): Change the suspect's cipher code at index $$$pos$$$ such that $$$a_{pos} = val$$$.

2. Query($$$l, r, k$$$): Calculate the current value of $$$\mathcal{G}(l, r, k)$$$.

London, 1891. Sherlock Holmes wants to send a secret message to Dr. Watson.

There are $$$N$$$ identical iron posts in a courtyard. Holmes may write one digit (0–9) on any post and may leave some posts blank. Later, Watson will see the courtyard, but because of fog and moved lanterns, he cannot know the order of the posts. He only knows how many times each digit appears. The order does not matter.

Before Watson arrives, a clerk may use a cipher wheel. Every time the wheel is used, each written digit $$$d$$$ is replaced by $$$ d \rightarrow (a \cdot d + b) \bmod 10 $$$ where:

• $$$a$$$ is chosen from a given set $$$S_a \subseteq \{1,3,7,9\}$$$,
• $$$b$$$ is chosen from a given set $$$S_b \subseteq \{0,1,\dots,9\}$$$.

The wheel may be used any number of times (possibly zero). Each use can choose any $$$a \in S_a$$$ and any $$$b \in S_b$$$. So the final effect is a composition of such transformations.

Holmes and Watson know $$$N$$$, $$$S_a$$$, and $$$S_b$$$, but Watson does not know which transformations were applied.

Because Watson only sees digit counts:

• A writing is completely described by a multiset of digits.
• Its size is between $$$1$$$ and $$$N$$$.

Two writings are indistinguishable if one can be obtained from the other by applying some allowed sequence of cipher wheel operations (and then shuffling).

Your task is to compute how many different secrets Holmes can encode so that Watson can always decode them correctly.

Watson is on a foggy mountain represented by an $$$n \times m$$$ grid.

Each cell contains one of:

• . (empty),
• * (a butterfly),
• # (a rock, impassable).

Watson can move in 4 directions (up, down, left, right) to a neighboring cell in one step. He cannot step on rocks.

Because of fog, Watson can only plan to catch the next butterfly if it is reachable within at most $$$k$$$ steps from his current position, where $$$1 \le k \le 10$$$.

Watson catches a butterfly when he visits its cell. He may choose the first butterfly to catch freely. After catching one butterfly, he may move to another butterfly only if the shortest path length between their cells (avoiding rocks) is at most $$$k$$$. Watson cannot catch the same butterfly twice.

Your task is to compute the maximum number of butterflies Watson can catch.

You are given an $$$n \times n$$$ grid of bits (each cell is either 0 or 1). Initially, the grid is filled with 0.

The grid is placed on a torus: row and column indices are taken modulo $$$n$$$. Formally, for any integer $$$x$$$ define $$$ wrap(x) = ((x-1) \bmod n) + 1. $$$

You may apply the following operation any number of times:

• choose a size $$$s \in \{2, k\}$$$ and a top-left cell $$$(i, j)$$$ ($$$1 \le i,j \le n$$$),
• for all $$$0 \le a,b \lt s$$$, flip the cell $$$ (\,wrap(i+a),\; wrap(j+b)\,) $$$ (i.e. 0 becomes 1, 1 becomes 0).

You are given $$$q$$$ target grids. For each target grid, determine whether it can be obtained from the all-zero grid using the operations above.

Watson runs along a straight road from position $$$0$$$ to the Palace at position $$$L$$$.

• Watson runs with constant speed $$$v$$$.
• The Hound starts behind Watson at position $$$-S$$$ and runs with constant speed $$$k \cdot v$$$.
• There are $$$n$$$ smoke bombs on the road. Bomb $$$i$$$ is located at position $$$p_i$$$ and has a duration $$$b_i$$$ seconds.

Watson runs only forward (toward increasing positions), and the Hound always runs forward as well.

Smoke Bombs When Watson reaches position $$$p_i$$$, he immediately picks up bomb $$$i$$$ (this takes no time). At any later moment, Watson may use any bomb he has already picked up. When Watson uses bomb $$$i$$$, the Hound stops moving for exactly $$$b_i$$$ seconds, while Watson continues running normally. Each bomb can be used at most once, and Watson may use at most $$$T$$$ bombs total. If Watson uses a bomb while the Hound is already stopped, the remaining stop time increases accordingly.

Capture rule Watson is caught if the Hound reaches Watson before Watson reaches the Palace.

Watson is considered safe if he reaches the Palace before the Hound catches him, or if their first meeting happens exactly at the Palace gates (position $$$L$$$).

Task Determine whether Watson can reach the Palace safely.

In the shadowy aftermath of The Final Problem, Sherlock Holmes prepares for his greatest confrontation.Professor James Moriarty — the "Napoleon of Crime" — has assembled a vast and intricate network, threatening the very order of London. Holmes knows that even his unmatched intellect may not suffice this time. To defeat his greatest enemy, he must form a carefully balanced League of Detectives.

There are $$$n$$$ distinct investigative skills, numbered from $$$1$$$ to $$$n$$$, encompassing everything from forensic chemistry to cryptanalysis and disguise. Each detective is described by the set of skills they possess.The pool of candidates is limitless and contains every possible combination of skills.

Sherlock Holmes himself possesses exactly $$$k$$$ skills. To maintain command and coherence within the League, Holmes refuses to recruit anyone who surpasses him in expertise.

Furthermore, to ensure flawless cooperation against Moriarty's web, he imposes strict rules:Collaboration:

1. Any two detectives in the League must share at least one common skill, so that no pair is ever unable to collaborate.

2. Hierarchy: All selected detectives must possess the same number of skills, say $$$x$$$. This number must be at most $$$k$$$ ($$$1 \le x \le k$$$).

3. Uniqueness: No two detectives may have identical sets of skills.

Holmes wishes to recruit as many detectives as possible under these constraints, forming the largest League capable of bringing Moriarty to justice.

Determine the maximum possible size of the League.Since the answer may be large, output it modulo $$$998244353$$$.

Detective Sherlock Holmes stared at the crime scene photos, his pipe emitting thoughtful curls of smoke. The Lestrade Manor banquet had ended in what appeared to be a meticulously orchestrated mass murder.

He turned to you, his assistant. "The police have recorded every constraint, but missed the crucial connections. We need to count every possible scenario consistent with their fragmented evidence. It's a straight forward combinatorial problem, really."

Sherlock Holmes needs to count the number of possible crime scenarios that fit the police evidence. A "scenario" consists of two independent parts: assigning suspects and scheduling actions.

Part 1: There are $$$S$$$ suspects and $$$K$$$ cases. Suspects were assigned to these cases under rigid constraints: every case had at least one suspect, and every suspect was assigned to at least one case.

Part 2: For each of the $$$K$$$ case files, the forensic team has identified exactly $$$L$$$ distinct actions that occurred during the crime. However, the exact order of these actions is not fully known. To model this, the police have represented the $$$L$$$ actions of a single case as a Directed Acyclic Graph (DAG). If there is a directed edge from action $$$u$$$ to action $$$v$$$, it means action $$$u$$$ must happen before action $$$v$$$ in the sequence.The structure of the DAG is identical for all $$$K$$$ cases.The "Global Timeline" consists of all actions from all cases combined.

Global Sequence: You must merge the actions from all $$$K$$$ cases into one single sequence of length $$$N = K \times L$$$. You can interleave actions from different cases however you like, as long as the internal order for each case is preserved.

Calculate the total number of valid scenarios modulo $$$10^9 + 7$$$.A scenario is valid if it satisfies all rules in Part 1 and Part 2.

Sherlock Holmes is stuck and cannot leave until he solves this puzzle. There are $$$n$$$ lamps in another chamber and $$$m$$$ switches in his current room. Each lamp can have up to $$$k$$$ distinct heat levels, which Sherlock can sense with his hands. He is very sensitive and can detect subtle changes, and after Valentine's Day, he finds himself with nothing but switches and lamps for company. Don't worry, all coders understand: love may crash, but programs run forever.

Sherlock needs to determine with absolute certainty which switch controls which lamp $$$(n \le m)$$$, knowing that he can enter the lamp room at most $$$t$$$ times. Each time he enters, he can observe for every lamp whether it is on or off and its temperature level.

Determine whether it is possible for Sherlock to map every lamp to its switch under these constraints.

Some nodes are crime scenes that must be watched. Holmes can place stakeout teams on some nodes. A team placed at node $$$u$$$ watches every node $$$v$$$ such that:

• $$$u$$$ is an ancestor of $$$v$$$ in the rooted tree (possibly $$$u=v$$$),
• and $$$\operatorname{dist}(u,v)\le k$$$, where $$$\operatorname{dist}$$$ is the number of edges on the unique path.

Every crime scene must be watched by at least one team. Your task is to find the minimum number of teams needed.

Important: the list of crime scenes may contain duplicates; a node is a crime scene if it appears at least once.

A single rat is hiding in one of these tunnels. Warlock Gnomes wants to capture it, but the rat is elusive and follows a strict ritual:

• The Midnight Scuttle: Every night, the rat must move from its current tunnel $$$i$$$ to an adjacent tunnel ($$$i-1$$$ or $$$i+1$$$). If the rat is at an end (tunnel $$$1$$$ or $$$n$$$), it must move to the only possible neighbor ($$$2$$$ or $$$n-1$$$, respectively).

•The Daylight Hunt: During the day, Warlock Gnomes can choose exactly one tunnel $$$k$$$ to inspect. If the rat is currently in tunnel $$$k$$$, it is captured! Otherwise, the rat hears the cat's footsteps and retreats deep into its current tunnel, making it impossible to catch for the rest of that day.

Shimlock Gnomes does not know the rat's starting position. Your task is to provide a sequence of tunnel inspections such that, regardless of where the rat starts or how it moves, the cat is guaranteed to capture the rat at some point during the sequence.