Problem 522
Hilbert’s Blackout
Despite the popularity of Hilbert’s infinite hotel, Hilbert decided to try managing extremely large finite hotels, instead.
To cut costs, Hilbert wished to power the new hotel with his own special generator. Each floor would send power to the floor above it, with the top floor sending power back down to the bottom floor. That way, Hilbert could have the generator placed on any given floor (as he likes having the option) and have electricity flow freely throughout the entire hotel.
Unfortunately, the contractors misinterpreted the schematics when they built the hotel. They informed Hilbert that each floor sends power to another floor at random, instead. This may compromise Hilbert’s freedom to have the generator placed anywhere, since blackouts could occur on certain floors.
For example, consider a sample flow diagram for a three-story hotel:
If the generator were placed on the first floor, then every floor would receive power. But if it were placed on the second or third floors instead, then there would be a blackout on the first floor. Note that while a given floor can receive power from many other floors at once, it can only send power to one other floor.
To resolve the blackout concerns, Hilbert decided to have a minimal number of floors rewired. To rewire a floor is to change the floor it sends power to. In the sample diagram above, all possible blackouts can be avoided by rewiring the second floor to send power to the first floor instead of the third floor.
Let F(n) be the sum of the minimum number of floor rewirings needed over all possible power-flow arrangements in a hotel of n floors. For example, F(3) = 6, F(8) = 16276736, and F(100) mod 135707531 = 84326147.
Find F(12344321) mod 135707531.
希尔伯特的停电
尽管无穷旅馆非常火爆，希尔伯特还是决定尝试经营一些有限但非常庞大的旅馆。
为了节省开支，希尔伯特希望使用他自己的特制发电机为旅馆供电。旅馆的每一层都会向其上一层供电，而最顶层则向最底层供电。这样一来，希尔伯特可以把他的发电机安放在任意一层（他喜欢有这样的选择权）同时保证电流在整个旅馆畅通无阻。
不幸的是，建造商在修建旅馆时误解了他的安排。他们通知希尔伯特，每一层并不是向其上一层供电，而是向随机的另一层供电。这使得希尔伯特可能丧失了部分安放发电机的自由，因为在特定的安排下可能在部分楼层出现停电的情况。
例如，考虑下面这个三层旅馆的一个电线排线布局样例：
如果发电机安放在一层，那么每一层都能够得到供电。但如果发电机被安放在二层或三层，那么第一层将会停电。请注意，尽管每一层可以同时从多个其它楼层接收电力，它只能向某一个其它楼层提供电力。
为了解决停电的顾虑，希尔伯特决定尽可能少地进行重新布线。对某一楼层重新布线意味着改变这个楼层向哪个楼层供电。在上述布局样例中，只需让二层不再向一层而是向三层供电，就能解决所有可能的停电问题。
假定现在旅馆有n层，考虑所有可能的排线布局，记所需的最小重新布线数之和为F(n)。例如，F(3) = 6，F(8) = 16276736，以及F(100) mod 135707531 = 84326147。
求F(12344321) mod 135707531。