题号：NC221650
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
There are 
factories numbered from 
to , producing magical crystals in Keya’s village. And to help producing, there are 
different fuel stations named 
, 
and 
. Each factory is responsible for one magical crystal producing process, and each fuel station provides one kind of raw material. Raw materials and semi-finished products can be transported between factories and fuel stations through pipelines, and each pipeline can carry any variety of raw materials and semi-finished products at the same time. Pipes are connected as follows:
① for factory
, there’s one pipe connecting to factory 
.
② for fuel station
&preview=true)
, it connects each factory with one pipe.
Obviously, there are
pipes in total. Now Keya has to shut down some of the pipes for maintenance. He wants to shut down as many pipes as possible at one time, but he wants to make sure that by using the remaining open pipes, his factories could still produce magical crystals, meaning that the factories and fuel stations should still be connected through the open pipes. Can you tell Keya how many ways he can select a subset of pipes for maintenance?
① for factory
② for fuel station
Obviously, there are
输入描述:
The first line is an integer，represents the number of factories.
输出描述:
Outputs one line containing an integer, representing the number of ways in which Kaia maintains the pipelines.Since the answer could be large, print it modulo.