一开始黑板上有一个正奇数 $x\ (3\le x<10^6)$，每次你可以选定黑板上已有的正整数 $a,b$（可以相等），将 $a+b$ 或 $a \oplus b$ 写在黑板上，其中 $\oplus$ 表示异或运算，最终目标是将 $1$ 写在黑板上。要求写数字不超过 $10^5$ 次且写上的数字不超过 $5*10^{18}$ 。

给定 $n$ 和两个长 $n$ 的 $01$ 串 $S$ 与 $T$。

设入栈序列为 $S$，出栈序列为 $T$ 的所有栈操作序列中，$T_1$ 可能对应的 $S$ 中的下标集合为 $A$。

求 $\sum\limits_{x\in A}x$。

例如 $S=100$，$T=001$ 时答案为 $5$，因为共有 $2$ 种栈操作序列满足入栈序列为 $S$，出栈序列为 $T$：

• 进，进，进，出，出，出，此时 $T_1$ 来自 $S_3$；
• 进，进，出，进，出，出，此时 $T_1$ 来自 $S_2$；

所以答案为 $3+2=5$。

$1\le n\le 5\times 10^6$。

有一个 $n\times n$ 的棋盘，你要在上面放最少数量的”半皇后“，使得每个格子都能被攻击到。

一个位于 $(x,y)$ 的 ”半皇后“ 能攻击到 $(a,b)$ 当且仅当满足以下条件中至少一个：

• $a=x$；
• $b=y$；
• $a-b=x-y$；

输出方案。

$1\le n\le 10^5$。

给定 $n$，求满足以下条件的集合 $S\in\{0,1,2,\dots,2^n-1\}$ 的个数：

对于所有 $S$ 的非空子集 $T\in S$，$T$ 均满足以下条件中的至少一个：

• $|T|$ 是奇数；
• $T$ 中元素的异或和非零；

对 $998244353$ 取模。

$1\le n\le 2\times 10^5$。

给定一个整数 $K$。求一个 $K$ 的正整数倍 $S$，使得 $S$ 的数位累加和最小。

$2 \le K \le {10}^5$。

给定 $n$，求

$\sum\limits_{m>0,a_i>0,\sum a_i=n}\prod_{i=1}^m F_{a_i}$

对 $10^9 + 7$ 取模。

$1\le n\le 10^{100}$。

你有 $n$ 个数 $a_1,a_2,\dots,a_n$ 要进行 $k$ 次操作，每次随机选择一个数 $x \in [1,n]$，把 $a_x$ 减一，并将答案增加除 $a_x$ 外所有数的乘积。

求最终答案的期望，答案对 $10^9 + 7$ 取模。

$1\le n\le 5000$。