n（1<=n<=100000000）头奶牛被关在一排房间中弹琴，琴的类型有m（1<=m<=100000000）种，如果相邻的奶牛使用同样一种琴弹琴的话，就可能造成争吵，问一共有多少种情况发生争吵。答案对100003取模。

假设有 $f(i)$ 种方法表示前 $i$ 头奶牛弹琴的争吵情况，则 $f(n)$ 就是我们要求的答案。我们可以考虑如何求解 $f(i)$。

对于第 $i$ 头奶牛，它可以选择与前一头奶牛弹同一种琴或者不同一种琴。如果它和前一头奶牛弹同一种琴，则前 $i-1$ 头奶牛的争吵情况就只和前 $i-2$ 头奶牛有关；如果它和前一头奶牛弹不同一种琴，则前 $i-1$ 头奶牛的争吵情况就只和前 $i-1$ 头奶牛有关。因此，我们可以得到以下递推式：

$$f(i) = (m-1)f(i-1) + f(i-2)$$

其中 $f(1) = m$，$f(2) = m^2$。这个递推式可以使用动态规划求解，时间复杂度为 $O(n)$。

最后，别忘了对答案取模。完整代码如下：

相关问题

Farmer John 正在分配他的 N (1 <= N <= 25,000) 头奶牛在谷仓周围做一些清洁杂务。 他将一天分为 T 个时间段（1 <= T <= 1,000,000）编号为1...T。每头奶牛只能在一天中的某个连续的时间段进行清洁工作。 任何被选中执行清洁任务的奶牛都将在整个工作时间段内工作。您的任务是帮助 Farmer John 分配一些奶牛轮班，以便每个时间段至少分配一头奶牛，并且参与清洁的奶牛尽可能少。 如果无法为每个班次分配一头奶牛，则输出 -1。

这是一个算法问题，我可以回答。这个问题可以使用贪心算法来解决。首先，将所有奶牛的可用时间段按照结束时间从早到晚排序。然后，从第一个时间段开始，选择能够在这个时间段内工作的奶牛中结束时间最早的那头奶牛进行分配。接着，从下一个时间段开始，选择能够在这个时间段内工作的奶牛中结束时间最早的那头奶牛进行分配，以此类推。如果在某个时间段无法找到可用的奶牛，则输出 -1。

有一个无向图，共 N 个节点，编号 1 至 N，共 M 条边。FJ 在节点 1，它想到达节点 N。FJ 总是会选择最短路径到达节点 N。作为捣蛋的奶牛 Bessie，它想尽量延迟 FJ 到达节点 N 的时间，于是 Bessie 决定从 M 条边之中选择某一条边，使得改边的长度变成原来的两倍，由于智商的问题，Bessie 不知道选择加倍哪条边的长度才能使得 FJ 到达 N 号节点的时间最迟。注意：不管 Bessie 选择加倍哪条边的长度，FJ 总是会从 1 号节点开始走最短路径到达 N 号点。 输入描述 第一行，两个整数 N 和 M. 1 <=N<=250, 1<=M<=250000。 接下来有 M 行，每行三个整数：A，B，L，表示节点 A 和节点 B 之间有一条长度为 L 的无向边。1<=L<=1000000。

这是一道图论问题，可以使用 Dijkstra 算法求解。具体步骤如下：

1. 构建图的邻接表，存储每个节点的相邻节点和边的长度；
2. 使用 Dijkstra 算法找到节点 1 到节点 N 的最短路径，并记录下这条路径经过的边；
3. 枚举每条经过的边，将该边的长度翻倍，再重新使用 Dijkstra 算法求解节点 1 到节点 N 的最短路径；
4. 记录下每种方案下节点 1 到节点 N 的最短路径的长度；
5. 输出这些长度中的最大值。

具体实现可以参考下面的代码（其中用到了 C++ STL 中的优先队列）：