// File: @openzeppelin/contracts/access/Ownable.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (access/Ownable.sol)

pragma solidity ^0.8.0;

import "../utils/Context.sol";

/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;

    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);

    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _transferOwnership(_msgSender());
    }

    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        _checkOwner();
        _;
    }

    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }

    /**
     * @dev Throws if the sender is not the owner.
     */
    function _checkOwner() internal view virtual {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
    }

    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _transferOwnership(address(0));
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _transferOwnership(newOwner);
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Internal function without access restriction.
     */
    function _transferOwnership(address newOwner) internal virtual {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}

// File: @openzeppelin/contracts/proxy/Clones.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (proxy/Clones.sol)

pragma solidity ^0.8.0;

/**
 * @dev https://eips.ethereum.org/EIPS/eip-1167[EIP 1167] is a standard for
 * deploying minimal proxy contracts, also known as "clones".
 *
 * > To simply and cheaply clone contract functionality in an immutable way, this standard specifies
 * > a minimal bytecode implementation that delegates all calls to a known, fixed address.
 *
 * The library includes functions to deploy a proxy using either `create` (traditional deployment) or `create2`
 * (salted deterministic deployment). It also includes functions to predict the addresses of clones deployed using the
 * deterministic method.
 *
 * _Available since v3.4._
 */
library Clones {
    /**
     * @dev Deploys and returns the address of a clone that mimics the behaviour of `implementation`.
     *
     * This function uses the create opcode, which should never revert.
     */
    function clone(address implementation) internal returns (address instance) {
        /// @solidity memory-safe-assembly
        assembly {
            // Cleans the upper 96 bits of the `implementation` word, then packs the first 3 bytes
            // of the `implementation` address with the bytecode before the address.
            mstore(0x00, or(shr(0xe8, shl(0x60, implementation)), 0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000))
            // Packs the remaining 17 bytes of `implementation` with the bytecode after the address.
            mstore(0x20, or(shl(0x78, implementation), 0x5af43d82803e903d91602b57fd5bf3))
            instance := create(0, 0x09, 0x37)
        }
        require(instance != address(0), "ERC1167: create failed");
    }

    /**
     * @dev Deploys and returns the address of a clone that mimics the behaviour of `implementation`.
     *
     * This function uses the create2 opcode and a `salt` to deterministically deploy
     * the clone. Using the same `implementation` and `salt` multiple time will revert, since
     * the clones cannot be deployed twice at the same address.
     */
    function cloneDeterministic(address implementation, bytes32 salt) internal returns (address instance) {
        /// @solidity memory-safe-assembly
        assembly {
            // Cleans the upper 96 bits of the `implementation` word, then packs the first 3 bytes
            // of the `implementation` address with the bytecode before the address.
            mstore(0x00, or(shr(0xe8, shl(0x60, implementation)), 0x3d602d80600a3d3981f3363d3d373d3d3d363d73000000))
            // Packs the remaining 17 bytes of `implementation` with the bytecode after the address.
            mstore(0x20, or(shl(0x78, implementation), 0x5af43d82803e903d91602b57fd5bf3))
            instance := create2(0, 0x09, 0x37, salt)
        }
        require(instance != address(0), "ERC1167: create2 failed");
    }

    /**
     * @dev Computes the address of a clone deployed using {Clones-cloneDeterministic}.
     */
    function predictDeterministicAddress(
        address implementation,
        bytes32 salt,
        address deployer
    ) internal pure returns (address predicted) {
        /// @solidity memory-safe-assembly
        assembly {
            let ptr := mload(0x40)
            mstore(add(ptr, 0x38), deployer)
            mstore(add(ptr, 0x24), 0x5af43d82803e903d91602b57fd5bf3ff)
            mstore(add(ptr, 0x14), implementation)
            mstore(ptr, 0x3d602d80600a3d3981f3363d3d373d3d3d363d73)
            mstore(add(ptr, 0x58), salt)
            mstore(add(ptr, 0x78), keccak256(add(ptr, 0x0c), 0x37))
            predicted := keccak256(add(ptr, 0x43), 0x55)
        }
    }

    /**
     * @dev Computes the address of a clone deployed using {Clones-cloneDeterministic}.
     */
    function predictDeterministicAddress(address implementation, bytes32 salt)
        internal
        view
        returns (address predicted)
    {
        return predictDeterministicAddress(implementation, salt, address(this));
    }
}

// File: @openzeppelin/contracts/security/ReentrancyGuard.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (security/ReentrancyGuard.sol)

pragma solidity ^0.8.0;

/**
 * @dev Contract module that helps prevent reentrant calls to a function.
 *
 * Inheriting from `ReentrancyGuard` will make the {nonReentrant} modifier
 * available, which can be applied to functions to make sure there are no nested
 * (reentrant) calls to them.
 *
 * Note that because there is a single `nonReentrant` guard, functions marked as
 * `nonReentrant` may not call one another. This can be worked around by making
 * those functions `private`, and then adding `external` `nonReentrant` entry
 * points to them.
 *
 * TIP: If you would like to learn more about reentrancy and alternative ways
 * to protect against it, check out our blog post
 * https://blog.openzeppelin.com/reentrancy-after-istanbul/[Reentrancy After Istanbul].
 */
abstract contract ReentrancyGuard {
    // Booleans are more expensive than uint256 or any type that takes up a full
    // word because each write operation emits an extra SLOAD to first read the
    // slot's contents, replace the bits taken up by the boolean, and then write
    // back. This is the compiler's defense against contract upgrades and
    // pointer aliasing, and it cannot be disabled.

    // The values being non-zero value makes deployment a bit more expensive,
    // but in exchange the refund on every call to nonReentrant will be lower in
    // amount. Since refunds are capped to a percentage of the total
    // transaction's gas, it is best to keep them low in cases like this one, to
    // increase the likelihood of the full refund coming into effect.
    uint256 private constant _NOT_ENTERED = 1;
    uint256 private constant _ENTERED = 2;

    uint256 private _status;

    constructor() {
        _status = _NOT_ENTERED;
    }

    /**
     * @dev Prevents a contract from calling itself, directly or indirectly.
     * Calling a `nonReentrant` function from another `nonReentrant`
     * function is not supported. It is possible to prevent this from happening
     * by making the `nonReentrant` function external, and making it call a
     * `private` function that does the actual work.
     */
    modifier nonReentrant() {
        _nonReentrantBefore();
        _;
        _nonReentrantAfter();
    }

    function _nonReentrantBefore() private {
        // On the first call to nonReentrant, _status will be _NOT_ENTERED
        require(_status != _ENTERED, "ReentrancyGuard: reentrant call");

        // Any calls to nonReentrant after this point will fail
        _status = _ENTERED;
    }

    function _nonReentrantAfter() private {
        // By storing the original value once again, a refund is triggered (see
        // https://eips.ethereum.org/EIPS/eip-2200)
        _status = _NOT_ENTERED;
    }
}

// File: @openzeppelin/contracts/token/ERC721/ERC721.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (token/ERC721/ERC721.sol)

pragma solidity ^0.8.0;

import "./IERC721.sol";
import "./IERC721Receiver.sol";
import "./extensions/IERC721Metadata.sol";
import "../../utils/Address.sol";
import "../../utils/Context.sol";
import "../../utils/Strings.sol";
import "../../utils/introspection/ERC165.sol";

/**
 * @dev Implementation of https://eips.ethereum.org/EIPS/eip-721[ERC721] Non-Fungible Token Standard, including
 * the Metadata extension, but not including the Enumerable extension, which is available separately as
 * {ERC721Enumerable}.
 */
contract ERC721 is Context, ERC165, IERC721, IERC721Metadata {
    using Address for address;
    using Strings for uint256;

    // Token name
    string private _name;

    // Token symbol
    string private _symbol;

    // Mapping from token ID to owner address
    mapping(uint256 => address) private _owners;

    // Mapping owner address to token count
    mapping(address => uint256) private _balances;

    // Mapping from token ID to approved address
    mapping(uint256 => address) private _tokenApprovals;

    // Mapping from owner to operator approvals
    mapping(address => mapping(address => bool)) private _operatorApprovals;

    /**
     * @dev Initializes the contract by setting a `name` and a `symbol` to the token collection.
     */
    constructor(string memory name_, string memory symbol_) {
        _name = name_;
        _symbol = symbol_;
    }

    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override(ERC165, IERC165) returns (bool) {
        return
            interfaceId == type(IERC721).interfaceId ||
            interfaceId == type(IERC721Metadata).interfaceId ||
            super.supportsInterface(interfaceId);
    }

    /**
     * @dev See {IERC721-balanceOf}.
     */
    function balanceOf(address owner) public view virtual override returns (uint256) {
        require(owner != address(0), "ERC721: address zero is not a valid owner");
        return _balances[owner];
    }

    /**
     * @dev See {IERC721-ownerOf}.
     */
    function ownerOf(uint256 tokenId) public view virtual override returns (address) {
        address owner = _ownerOf(tokenId);
        require(owner != address(0), "ERC721: invalid token ID");
        return owner;
    }

    /**
     * @dev See {IERC721Metadata-name}.
     */
    function name() public view virtual override returns (string memory) {
        return _name;
    }

    /**
     * @dev See {IERC721Metadata-symbol}.
     */
    function symbol() public view virtual override returns (string memory) {
        return _symbol;
    }

    /**
     * @dev See {IERC721Metadata-tokenURI}.
     */
    function tokenURI(uint256 tokenId) public view virtual override returns (string memory) {
        _requireMinted(tokenId);

        string memory baseURI = _baseURI();
        return bytes(baseURI).length > 0 ? string(abi.encodePacked(baseURI, tokenId.toString())) : "";
    }

    /**
     * @dev Base URI for computing {tokenURI}. If set, the resulting URI for each
     * token will be the concatenation of the `baseURI` and the `tokenId`. Empty
     * by default, can be overridden in child contracts.
     */
    function _baseURI() internal view virtual returns (string memory) {
        return "";
    }

    /**
     * @dev See {IERC721-approve}.
     */
    function approve(address to, uint256 tokenId) public virtual override {
        address owner = ERC721.ownerOf(tokenId);
        require(to != owner, "ERC721: approval to current owner");

        require(
            _msgSender() == owner || isApprovedForAll(owner, _msgSender()),
            "ERC721: approve caller is not token owner or approved for all"
        );

        _approve(to, tokenId);
    }

    /**
     * @dev See {IERC721-getApproved}.
     */
    function getApproved(uint256 tokenId) public view virtual override returns (address) {
        _requireMinted(tokenId);

        return _tokenApprovals[tokenId];
    }

    /**
     * @dev See {IERC721-setApprovalForAll}.
     */
    function setApprovalForAll(address operator, bool approved) public virtual override {
        _setApprovalForAll(_msgSender(), operator, approved);
    }

    /**
     * @dev See {IERC721-isApprovedForAll}.
     */
    function isApprovedForAll(address owner, address operator) public view virtual override returns (bool) {
        return _operatorApprovals[owner][operator];
    }

    /**
     * @dev See {IERC721-transferFrom}.
     */
    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) public virtual override {
        //solhint-disable-next-line max-line-length
        require(_isApprovedOrOwner(_msgSender(), tokenId), "ERC721: caller is not token owner or approved");

        _transfer(from, to, tokenId);
    }

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId
    ) public virtual override {
        safeTransferFrom(from, to, tokenId, "");
    }

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes memory data
    ) public virtual override {
        require(_isApprovedOrOwner(_msgSender(), tokenId), "ERC721: caller is not token owner or approved");
        _safeTransfer(from, to, tokenId, data);
    }

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`, checking first that contract recipients
     * are aware of the ERC721 protocol to prevent tokens from being forever locked.
     *
     * `data` is additional data, it has no specified format and it is sent in call to `to`.
     *
     * This internal function is equivalent to {safeTransferFrom}, and can be used to e.g.
     * implement alternative mechanisms to perform token transfer, such as signature-based.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function _safeTransfer(
        address from,
        address to,
        uint256 tokenId,
        bytes memory data
    ) internal virtual {
        _transfer(from, to, tokenId);
        require(_checkOnERC721Received(from, to, tokenId, data), "ERC721: transfer to non ERC721Receiver implementer");
    }

    /**
     * @dev Returns the owner of the `tokenId`. Does NOT revert if token doesn't exist
     */
    function _ownerOf(uint256 tokenId) internal view virtual returns (address) {
        return _owners[tokenId];
    }

    /**
     * @dev Returns whether `tokenId` exists.
     *
     * Tokens can be managed by their owner or approved accounts via {approve} or {setApprovalForAll}.
     *
     * Tokens start existing when they are minted (`_mint`),
     * and stop existing when they are burned (`_burn`).
     */
    function _exists(uint256 tokenId) internal view virtual returns (bool) {
        return _ownerOf(tokenId) != address(0);
    }

    /**
     * @dev Returns whether `spender` is allowed to manage `tokenId`.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function _isApprovedOrOwner(address spender, uint256 tokenId) internal view virtual returns (bool) {
        address owner = ERC721.ownerOf(tokenId);
        return (spender == owner || isApprovedForAll(owner, spender) || getApproved(tokenId) == spender);
    }

    /**
     * @dev Safely mints `tokenId` and transfers it to `to`.
     *
     * Requirements:
     *
     * - `tokenId` must not exist.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function _safeMint(address to, uint256 tokenId) internal virtual {
        _safeMint(to, tokenId, "");
    }

    /**
     * @dev Same as {xref-ERC721-_safeMint-address-uint256-}[`_safeMint`], with an additional `data` parameter which is
     * forwarded in {IERC721Receiver-onERC721Received} to contract recipients.
     */
    function _safeMint(
        address to,
        uint256 tokenId,
        bytes memory data
    ) internal virtual {
        _mint(to, tokenId);
        require(
            _checkOnERC721Received(address(0), to, tokenId, data),
            "ERC721: transfer to non ERC721Receiver implementer"
        );
    }

    /**
     * @dev Mints `tokenId` and transfers it to `to`.
     *
     * WARNING: Usage of this method is discouraged, use {_safeMint} whenever possible
     *
     * Requirements:
     *
     * - `tokenId` must not exist.
     * - `to` cannot be the zero address.
     *
     * Emits a {Transfer} event.
     */
    function _mint(address to, uint256 tokenId) internal virtual {
        require(to != address(0), "ERC721: mint to the zero address");
        require(!_exists(tokenId), "ERC721: token already minted");

        _beforeTokenTransfer(address(0), to, tokenId, 1);

        // Check that tokenId was not minted by `_beforeTokenTransfer` hook
        require(!_exists(tokenId), "ERC721: token already minted");

        unchecked {
            // Will not overflow unless all 2**256 token ids are minted to the same owner.
            // Given that tokens are minted one by one, it is impossible in practice that
            // this ever happens. Might change if we allow batch minting.
            // The ERC fails to describe this case.
            _balances[to] += 1;
        }

        _owners[tokenId] = to;

        emit Transfer(address(0), to, tokenId);

        _afterTokenTransfer(address(0), to, tokenId, 1);
    }

    /**
     * @dev Destroys `tokenId`.
     * The approval is cleared when the token is burned.
     * This is an internal function that does not check if the sender is authorized to operate on the token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     *
     * Emits a {Transfer} event.
     */
    function _burn(uint256 tokenId) internal virtual {
        address owner = ERC721.ownerOf(tokenId);

        _beforeTokenTransfer(owner, address(0), tokenId, 1);

        // Update ownership in case tokenId was transferred by `_beforeTokenTransfer` hook
        owner = ERC721.ownerOf(tokenId);

        // Clear approvals
        delete _tokenApprovals[tokenId];

        unchecked {
            // Cannot overflow, as that would require more tokens to be burned/transferred
            // out than the owner initially received through minting and transferring in.
            _balances[owner] -= 1;
        }
        delete _owners[tokenId];

        emit Transfer(owner, address(0), tokenId);

        _afterTokenTransfer(owner, address(0), tokenId, 1);
    }

    /**
     * @dev Transfers `tokenId` from `from` to `to`.
     *  As opposed to {transferFrom}, this imposes no restrictions on msg.sender.
     *
     * Requirements:
     *
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     *
     * Emits a {Transfer} event.
     */
    function _transfer(
        address from,
        address to,
        uint256 tokenId
    ) internal virtual {
        require(ERC721.ownerOf(tokenId) == from, "ERC721: transfer from incorrect owner");
        require(to != address(0), "ERC721: transfer to the zero address");

        _beforeTokenTransfer(from, to, tokenId, 1);

        // Check that tokenId was not transferred by `_beforeTokenTransfer` hook
        require(ERC721.ownerOf(tokenId) == from, "ERC721: transfer from incorrect owner");

        // Clear approvals from the previous owner
        delete _tokenApprovals[tokenId];

        unchecked {
            // `_balances[from]` cannot overflow for the same reason as described in `_burn`:
            // `from`'s balance is the number of token held, which is at least one before the current
            // transfer.
            // `_balances[to]` could overflow in the conditions described in `_mint`. That would require
            // all 2**256 token ids to be minted, which in practice is impossible.
            _balances[from] -= 1;
            _balances[to] += 1;
        }
        _owners[tokenId] = to;

        emit Transfer(from, to, tokenId);

        _afterTokenTransfer(from, to, tokenId, 1);
    }

    /**
     * @dev Approve `to` to operate on `tokenId`
     *
     * Emits an {Approval} event.
     */
    function _approve(address to, uint256 tokenId) internal virtual {
        _tokenApprovals[tokenId] = to;
        emit Approval(ERC721.ownerOf(tokenId), to, tokenId);
    }

    /**
     * @dev Approve `operator` to operate on all of `owner` tokens
     *
     * Emits an {ApprovalForAll} event.
     */
    function _setApprovalForAll(
        address owner,
        address operator,
        bool approved
    ) internal virtual {
        require(owner != operator, "ERC721: approve to caller");
        _operatorApprovals[owner][operator] = approved;
        emit ApprovalForAll(owner, operator, approved);
    }

    /**
     * @dev Reverts if the `tokenId` has not been minted yet.
     */
    function _requireMinted(uint256 tokenId) internal view virtual {
        require(_exists(tokenId), "ERC721: invalid token ID");
    }

    /**
     * @dev Internal function to invoke {IERC721Receiver-onERC721Received} on a target address.
     * The call is not executed if the target address is not a contract.
     *
     * @param from address representing the previous owner of the given token ID
     * @param to target address that will receive the tokens
     * @param tokenId uint256 ID of the token to be transferred
     * @param data bytes optional data to send along with the call
     * @return bool whether the call correctly returned the expected magic value
     */
    function _checkOnERC721Received(
        address from,
        address to,
        uint256 tokenId,
        bytes memory data
    ) private returns (bool) {
        if (to.isContract()) {
            try IERC721Receiver(to).onERC721Received(_msgSender(), from, tokenId, data) returns (bytes4 retval) {
                return retval == IERC721Receiver.onERC721Received.selector;
            } catch (bytes memory reason) {
                if (reason.length == 0) {
                    revert("ERC721: transfer to non ERC721Receiver implementer");
                } else {
                    /// @solidity memory-safe-assembly
                    assembly {
                        revert(add(32, reason), mload(reason))
                    }
                }
            }
        } else {
            return true;
        }
    }

    /**
     * @dev Hook that is called before any token transfer. This includes minting and burning. If {ERC721Consecutive} is
     * used, the hook may be called as part of a consecutive (batch) mint, as indicated by `batchSize` greater than 1.
     *
     * Calling conditions:
     *
     * - When `from` and `to` are both non-zero, ``from``'s tokens will be transferred to `to`.
     * - When `from` is zero, the tokens will be minted for `to`.
     * - When `to` is zero, ``from``'s tokens will be burned.
     * - `from` and `to` are never both zero.
     * - `batchSize` is non-zero.
     *
     * To learn more about hooks, head to xref:ROOT:extending-contracts.adoc#using-hooks[Using Hooks].
     */
    function _beforeTokenTransfer(
        address from,
        address to,
        uint256, /* firstTokenId */
        uint256 batchSize
    ) internal virtual {
        if (batchSize > 1) {
            if (from != address(0)) {
                _balances[from] -= batchSize;
            }
            if (to != address(0)) {
                _balances[to] += batchSize;
            }
        }
    }

    /**
     * @dev Hook that is called after any token transfer. This includes minting and burning. If {ERC721Consecutive} is
     * used, the hook may be called as part of a consecutive (batch) mint, as indicated by `batchSize` greater than 1.
     *
     * Calling conditions:
     *
     * - When `from` and `to` are both non-zero, ``from``'s tokens were transferred to `to`.
     * - When `from` is zero, the tokens were minted for `to`.
     * - When `to` is zero, ``from``'s tokens were burned.
     * - `from` and `to` are never both zero.
     * - `batchSize` is non-zero.
     *
     * To learn more about hooks, head to xref:ROOT:extending-contracts.adoc#using-hooks[Using Hooks].
     */
    function _afterTokenTransfer(
        address from,
        address to,
        uint256 firstTokenId,
        uint256 batchSize
    ) internal virtual {}
}

// File: @openzeppelin/contracts/token/ERC721/extensions/IERC721Metadata.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (token/ERC721/extensions/IERC721Metadata.sol)

pragma solidity ^0.8.0;

import "../IERC721.sol";

/**
 * @title ERC-721 Non-Fungible Token Standard, optional metadata extension
 * @dev See https://eips.ethereum.org/EIPS/eip-721
 */
interface IERC721Metadata is IERC721 {
    /**
     * @dev Returns the token collection name.
     */
    function name() external view returns (string memory);

    /**
     * @dev Returns the token collection symbol.
     */
    function symbol() external view returns (string memory);

    /**
     * @dev Returns the Uniform Resource Identifier (URI) for `tokenId` token.
     */
    function tokenURI(uint256 tokenId) external view returns (string memory);
}

// File: @openzeppelin/contracts/token/ERC721/IERC721.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (token/ERC721/IERC721.sol)

pragma solidity ^0.8.0;

import "../../utils/introspection/IERC165.sol";

/**
 * @dev Required interface of an ERC721 compliant contract.
 */
interface IERC721 is IERC165 {
    /**
     * @dev Emitted when `tokenId` token is transferred from `from` to `to`.
     */
    event Transfer(address indexed from, address indexed to, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables `approved` to manage the `tokenId` token.
     */
    event Approval(address indexed owner, address indexed approved, uint256 indexed tokenId);

    /**
     * @dev Emitted when `owner` enables or disables (`approved`) `operator` to manage all of its assets.
     */
    event ApprovalForAll(address indexed owner, address indexed operator, bool approved);

    /**
     * @dev Returns the number of tokens in ``owner``'s account.
     */
    function balanceOf(address owner) external view returns (uint256 balance);

    /**
     * @dev Returns the owner of the `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function ownerOf(uint256 tokenId) external view returns (address owner);

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token by either {approve} or {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId,
        bytes calldata data
    ) external;

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`, checking first that contract recipients
     * are aware of the ERC721 protocol to prevent tokens from being forever locked.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must exist and be owned by `from`.
     * - If the caller is not `from`, it must have been allowed to move this token by either {approve} or {setApprovalForAll}.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function safeTransferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external;

    /**
     * @dev Transfers `tokenId` token from `from` to `to`.
     *
     * WARNING: Note that the caller is responsible to confirm that the recipient is capable of receiving ERC721
     * or else they may be permanently lost. Usage of {safeTransferFrom} prevents loss, though the caller must
     * understand this adds an external call which potentially creates a reentrancy vulnerability.
     *
     * Requirements:
     *
     * - `from` cannot be the zero address.
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     * - If the caller is not `from`, it must be approved to move this token by either {approve} or {setApprovalForAll}.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(
        address from,
        address to,
        uint256 tokenId
    ) external;

    /**
     * @dev Gives permission to `to` to transfer `tokenId` token to another account.
     * The approval is cleared when the token is transferred.
     *
     * Only a single account can be approved at a time, so approving the zero address clears previous approvals.
     *
     * Requirements:
     *
     * - The caller must own the token or be an approved operator.
     * - `tokenId` must exist.
     *
     * Emits an {Approval} event.
     */
    function approve(address to, uint256 tokenId) external;

    /**
     * @dev Approve or remove `operator` as an operator for the caller.
     * Operators can call {transferFrom} or {safeTransferFrom} for any token owned by the caller.
     *
     * Requirements:
     *
     * - The `operator` cannot be the caller.
     *
     * Emits an {ApprovalForAll} event.
     */
    function setApprovalForAll(address operator, bool _approved) external;

    /**
     * @dev Returns the account approved for `tokenId` token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     */
    function getApproved(uint256 tokenId) external view returns (address operator);

    /**
     * @dev Returns if the `operator` is allowed to manage all of the assets of `owner`.
     *
     * See {setApprovalForAll}
     */
    function isApprovedForAll(address owner, address operator) external view returns (bool);
}

// File: @openzeppelin/contracts/token/ERC721/IERC721Receiver.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.6.0) (token/ERC721/IERC721Receiver.sol)

pragma solidity ^0.8.0;

/**
 * @title ERC721 token receiver interface
 * @dev Interface for any contract that wants to support safeTransfers
 * from ERC721 asset contracts.
 */
interface IERC721Receiver {
    /**
     * @dev Whenever an {IERC721} `tokenId` token is transferred to this contract via {IERC721-safeTransferFrom}
     * by `operator` from `from`, this function is called.
     *
     * It must return its Solidity selector to confirm the token transfer.
     * If any other value is returned or the interface is not implemented by the recipient, the transfer will be reverted.
     *
     * The selector can be obtained in Solidity with `IERC721Receiver.onERC721Received.selector`.
     */
    function onERC721Received(
        address operator,
        address from,
        uint256 tokenId,
        bytes calldata data
    ) external returns (bytes4);
}

// File: @openzeppelin/contracts/utils/Address.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (utils/Address.sol)

pragma solidity ^0.8.1;

/**
 * @dev Collection of functions related to the address type
 */
library Address {
    /**
     * @dev Returns true if `account` is a contract.
     *
     * [IMPORTANT]
     * ====
     * It is unsafe to assume that an address for which this function returns
     * false is an externally-owned account (EOA) and not a contract.
     *
     * Among others, `isContract` will return false for the following
     * types of addresses:
     *
     *  - an externally-owned account
     *  - a contract in construction
     *  - an address where a contract will be created
     *  - an address where a contract lived, but was destroyed
     * ====
     *
     * [IMPORTANT]
     * ====
     * You shouldn't rely on `isContract` to protect against flash loan attacks!
     *
     * Preventing calls from contracts is highly discouraged. It breaks composability, breaks support for smart wallets
     * like Gnosis Safe, and does not provide security since it can be circumvented by calling from a contract
     * constructor.
     * ====
     */
    function isContract(address account) internal view returns (bool) {
        // This method relies on extcodesize/address.code.length, which returns 0
        // for contracts in construction, since the code is only stored at the end
        // of the constructor execution.

        return account.code.length > 0;
    }

    /**
     * @dev Replacement for Solidity's `transfer`: sends `amount` wei to
     * `recipient`, forwarding all available gas and reverting on errors.
     *
     * https://eips.ethereum.org/EIPS/eip-1884[EIP1884] increases the gas cost
     * of certain opcodes, possibly making contracts go over the 2300 gas limit
     * imposed by `transfer`, making them unable to receive funds via
     * `transfer`. {sendValue} removes this limitation.
     *
     * https://diligence.consensys.net/posts/2019/09/stop-using-soliditys-transfer-now/[Learn more].
     *
     * IMPORTANT: because control is transferred to `recipient`, care must be
     * taken to not create reentrancy vulnerabilities. Consider using
     * {ReentrancyGuard} or the
     * https://solidity.readthedocs.io/en/v0.5.11/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
     */
    function sendValue(address payable recipient, uint256 amount) internal {
        require(address(this).balance >= amount, "Address: insufficient balance");

        (bool success, ) = recipient.call{value: amount}("");
        require(success, "Address: unable to send value, recipient may have reverted");
    }

    /**
     * @dev Performs a Solidity function call using a low level `call`. A
     * plain `call` is an unsafe replacement for a function call: use this
     * function instead.
     *
     * If `target` reverts with a revert reason, it is bubbled up by this
     * function (like regular Solidity function calls).
     *
     * Returns the raw returned data. To convert to the expected return value,
     * use https://solidity.readthedocs.io/en/latest/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions[`abi.decode`].
     *
     * Requirements:
     *
     * - `target` must be a contract.
     * - calling `target` with `data` must not revert.
     *
     * _Available since v3.1._
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, "Address: low-level call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`], but with
     * `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but also transferring `value` wei to `target`.
     *
     * Requirements:
     *
     * - the calling contract must have an ETH balance of at least `value`.
     * - the called Solidity function must be `payable`.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, value, "Address: low-level call with value failed");
    }

    /**
     * @dev Same as {xref-Address-functionCallWithValue-address-bytes-uint256-}[`functionCallWithValue`], but
     * with `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(address(this).balance >= value, "Address: insufficient balance for call");
        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
        return functionStaticCall(target, data, "Address: low-level static call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        (bool success, bytes memory returndata) = target.staticcall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionDelegateCall(target, data, "Address: low-level delegate call failed");
    }

    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        (bool success, bytes memory returndata) = target.delegatecall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }

    /**
     * @dev Tool to verify that a low level call to smart-contract was successful, and revert (either by bubbling
     * the revert reason or using the provided one) in case of unsuccessful call or if target was not a contract.
     *
     * _Available since v4.8._
     */
    function verifyCallResultFromTarget(
        address target,
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        if (success) {
            if (returndata.length == 0) {
                // only check isContract if the call was successful and the return data is empty
                // otherwise we already know that it was a contract
                require(isContract(target), "Address: call to non-contract");
            }
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }

    /**
     * @dev Tool to verify that a low level call was successful, and revert if it wasn't, either by bubbling the
     * revert reason or using the provided one.
     *
     * _Available since v4.3._
     */
    function verifyCallResult(
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal pure returns (bytes memory) {
        if (success) {
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }

    function _revert(bytes memory returndata, string memory errorMessage) private pure {
        // Look for revert reason and bubble it up if present
        if (returndata.length > 0) {
            // The easiest way to bubble the revert reason is using memory via assembly
            /// @solidity memory-safe-assembly
            assembly {
                let returndata_size := mload(returndata)
                revert(add(32, returndata), returndata_size)
            }
        } else {
            revert(errorMessage);
        }
    }
}

// File: @openzeppelin/contracts/utils/Context.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/Context.sol)

pragma solidity ^0.8.0;

/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }

    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}

// File: @openzeppelin/contracts/utils/introspection/ERC165.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/introspection/ERC165.sol)

pragma solidity ^0.8.0;

import "./IERC165.sol";

/**
 * @dev Implementation of the {IERC165} interface.
 *
 * Contracts that want to implement ERC165 should inherit from this contract and override {supportsInterface} to check
 * for the additional interface id that will be supported. For example:
 *
 * ```solidity
 * function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
 *     return interfaceId == type(MyInterface).interfaceId || super.supportsInterface(interfaceId);
 * }
 * ```
 *
 * Alternatively, {ERC165Storage} provides an easier to use but more expensive implementation.
 */
abstract contract ERC165 is IERC165 {
    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        return interfaceId == type(IERC165).interfaceId;
    }
}

// File: @openzeppelin/contracts/utils/introspection/IERC165.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/introspection/IERC165.sol)

pragma solidity ^0.8.0;

/**
 * @dev Interface of the ERC165 standard, as defined in the
 * https://eips.ethereum.org/EIPS/eip-165[EIP].
 *
 * Implementers can declare support of contract interfaces, which can then be
 * queried by others ({ERC165Checker}).
 *
 * For an implementation, see {ERC165}.
 */
interface IERC165 {
    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified[EIP section]
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30 000 gas.
     */
    function supportsInterface(bytes4 interfaceId) external view returns (bool);
}

// File: @openzeppelin/contracts/utils/math/Math.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (utils/math/Math.sol)

pragma solidity ^0.8.0;

/**
 * @dev Standard math utilities missing in the Solidity language.
 */
library Math {
    enum Rounding {
        Down, // Toward negative infinity
        Up, // Toward infinity
        Zero // Toward zero
    }

    /**
     * @dev Returns the largest of two numbers.
     */
    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        return a > b ? a : b;
    }

    /**
     * @dev Returns the smallest of two numbers.
     */
    function min(uint256 a, uint256 b) internal pure returns (uint256) {
        return a < b ? a : b;
    }

    /**
     * @dev Returns the average of two numbers. The result is rounded towards
     * zero.
     */
    function average(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b) / 2 can overflow.
        return (a & b) + (a ^ b) / 2;
    }

    /**
     * @dev Returns the ceiling of the division of two numbers.
     *
     * This differs from standard division with `/` in that it rounds up instead
     * of rounding down.
     */
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b - 1) / b can overflow on addition, so we distribute.
        return a == 0 ? 0 : (a - 1) / b + 1;
    }

    /**
     * @notice Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
     * @dev Original credit to Remco Bloemen under MIT license (https://xn--2-umb.com/21/muldiv)
     * with further edits by Uniswap Labs also under MIT license.
     */
    function mulDiv(
        uint256 x,
        uint256 y,
        uint256 denominator
    ) internal pure returns (uint256 result) {
        unchecked {
            // 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
            // use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
            // variables such that product = prod1 * 2^256 + prod0.
            uint256 prod0; // Least significant 256 bits of the product
            uint256 prod1; // Most significant 256 bits of the product
            assembly {
                let mm := mulmod(x, y, not(0))
                prod0 := mul(x, y)
                prod1 := sub(sub(mm, prod0), lt(mm, prod0))
            }

            // Handle non-overflow cases, 256 by 256 division.
            if (prod1 == 0) {
                return prod0 / denominator;
            }

            // Make sure the result is less than 2^256. Also prevents denominator == 0.
            require(denominator > prod1);

            ///////////////////////////////////////////////
            // 512 by 256 division.
            ///////////////////////////////////////////////

            // Make division exact by subtracting the remainder from [prod1 prod0].
            uint256 remainder;
            assembly {
                // Compute remainder using mulmod.
                remainder := mulmod(x, y, denominator)

                // Subtract 256 bit number from 512 bit number.
                prod1 := sub(prod1, gt(remainder, prod0))
                prod0 := sub(prod0, remainder)
            }

            // Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
            // See https://cs.stackexchange.com/q/138556/92363.

            // Does not overflow because the denominator cannot be zero at this stage in the function.
            uint256 twos = denominator & (~denominator + 1);
            assembly {
                // Divide denominator by twos.
                denominator := div(denominator, twos)

                // Divide [prod1 prod0] by twos.
                prod0 := div(prod0, twos)

                // Flip twos such that it is 2^256 / twos. If twos is zero, then it becomes one.
                twos := add(div(sub(0, twos), twos), 1)
            }

            // Shift in bits from prod1 into prod0.
            prod0 |= prod1 * twos;

            // Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
            // that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
            // four bits. That is, denominator * inv = 1 mod 2^4.
            uint256 inverse = (3 * denominator) ^ 2;

            // Use the Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also works
            // in modular arithmetic, doubling the correct bits in each step.
            inverse *= 2 - denominator * inverse; // inverse mod 2^8
            inverse *= 2 - denominator * inverse; // inverse mod 2^16
            inverse *= 2 - denominator * inverse; // inverse mod 2^32
            inverse *= 2 - denominator * inverse; // inverse mod 2^64
            inverse *= 2 - denominator * inverse; // inverse mod 2^128
            inverse *= 2 - denominator * inverse; // inverse mod 2^256

            // Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
            // This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
            // less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
            // is no longer required.
            result = prod0 * inverse;
            return result;
        }
    }

    /**
     * @notice Calculates x * y / denominator with full precision, following the selected rounding direction.
     */
    function mulDiv(
        uint256 x,
        uint256 y,
        uint256 denominator,
        Rounding rounding
    ) internal pure returns (uint256) {
        uint256 result = mulDiv(x, y, denominator);
        if (rounding == Rounding.Up && mulmod(x, y, denominator) > 0) {
            result += 1;
        }
        return result;
    }

    /**
     * @dev Returns the square root of a number. If the number is not a perfect square, the value is rounded down.
     *
     * Inspired by Henry S. Warren, Jr.'s "Hacker's Delight" (Chapter 11).
     */
    function sqrt(uint256 a) internal pure returns (uint256) {
        if (a == 0) {
            return 0;
        }

        // For our first guess, we get the biggest power of 2 which is smaller than the square root of the target.
        //
        // We know that the "msb" (most significant bit) of our target number `a` is a power of 2 such that we have
        // `msb(a) <= a < 2*msb(a)`. This value can be written `msb(a)=2**k` with `k=log2(a)`.
        //
        // This can be rewritten `2**log2(a) <= a < 2**(log2(a) + 1)`
        // → `sqrt(2**k) <= sqrt(a) < sqrt(2**(k+1))`
        // → `2**(k/2) <= sqrt(a) < 2**((k+1)/2) <= 2**(k/2 + 1)`
        //
        // Consequently, `2**(log2(a) / 2)` is a good first approximation of `sqrt(a)` with at least 1 correct bit.
        uint256 result = 1 << (log2(a) >> 1);

        // At this point `result` is an estimation with one bit of precision. We know the true value is a uint128,
        // since it is the square root of a uint256. Newton's method converges quadratically (precision doubles at
        // every iteration). We thus need at most 7 iteration to turn our partial result with one bit of precision
        // into the expected uint128 result.
        unchecked {
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            return min(result, a / result);
        }
    }

    /**
     * @notice Calculates sqrt(a), following the selected rounding direction.
     */
    function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = sqrt(a);
            return result + (rounding == Rounding.Up && result * result < a ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 2, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 128;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 64;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 32;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 16;
            }
            if (value >> 8 > 0) {
                value >>= 8;
                result += 8;
            }
            if (value >> 4 > 0) {
                value >>= 4;
                result += 4;
            }
            if (value >> 2 > 0) {
                value >>= 2;
                result += 2;
            }
            if (value >> 1 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 2, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log2(value);
            return result + (rounding == Rounding.Up && 1 << result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 10, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >= 10**64) {
                value /= 10**64;
                result += 64;
            }
            if (value >= 10**32) {
                value /= 10**32;
                result += 32;
            }
            if (value >= 10**16) {
                value /= 10**16;
                result += 16;
            }
            if (value >= 10**8) {
                value /= 10**8;
                result += 8;
            }
            if (value >= 10**4) {
                value /= 10**4;
                result += 4;
            }
            if (value >= 10**2) {
                value /= 10**2;
                result += 2;
            }
            if (value >= 10**1) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 10, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log10(value);
            return result + (rounding == Rounding.Up && 10**result < value ? 1 : 0);
        }
    }

    /**
     * @dev Return the log in base 256, rounded down, of a positive value.
     * Returns 0 if given 0.
     *
     * Adding one to the result gives the number of pairs of hex symbols needed to represent `value` as a hex string.
     */
    function log256(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 16;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 8;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 4;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 2;
            }
            if (value >> 8 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 10, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log256(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log256(value);
            return result + (rounding == Rounding.Up && 1 << (result * 8) < value ? 1 : 0);
        }
    }
}

// File: @openzeppelin/contracts/utils/Strings.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (utils/Strings.sol)

pragma solidity ^0.8.0;

import "./math/Math.sol";

/**
 * @dev String operations.
 */
library Strings {
    bytes16 private constant _SYMBOLS = "0123456789abcdef";
    uint8 private constant _ADDRESS_LENGTH = 20;

    /**
     * @dev Converts a `uint256` to its ASCII `string` decimal representation.
     */
    function toString(uint256 value) internal pure returns (string memory) {
        unchecked {
            uint256 length = Math.log10(value) + 1;
            string memory buffer = new string(length);
            uint256 ptr;
            /// @solidity memory-safe-assembly
            assembly {
                ptr := add(buffer, add(32, length))
            }
            while (true) {
                ptr--;
                /// @solidity memory-safe-assembly
                assembly {
                    mstore8(ptr, byte(mod(value, 10), _SYMBOLS))
                }
                value /= 10;
                if (value == 0) break;
            }
            return buffer;
        }
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation.
     */
    function toHexString(uint256 value) internal pure returns (string memory) {
        unchecked {
            return toHexString(value, Math.log256(value) + 1);
        }
    }

    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation with fixed length.
     */
    function toHexString(uint256 value, uint256 length) internal pure returns (string memory) {
        bytes memory buffer = new bytes(2 * length + 2);
        buffer[0] = "0";
        buffer[1] = "x";
        for (uint256 i = 2 * length + 1; i > 1; --i) {
            buffer[i] = _SYMBOLS[value & 0xf];
            value >>= 4;
        }
        require(value == 0, "Strings: hex length insufficient");
        return string(buffer);
    }

    /**
     * @dev Converts an `address` with fixed length of 20 bytes to its not checksummed ASCII `string` hexadecimal representation.
     */
    function toHexString(address addr) internal pure returns (string memory) {
        return toHexString(uint256(uint160(addr)), _ADDRESS_LENGTH);
    }
}

// File: @polly-tools/core/contracts/modules/Json.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import '../Polly.sol';

contract Json is PMReadOnly {

  enum Type {
    STRING, BOOL, NUMBER, OBJECT, ARRAY
  }

  enum Format {
    KEY_VALUE, VALUE, ARRAY, OBJECT
  }

  struct Item {
    Type _type;
    string _key;
    string _string;
    bool _bool;
    uint _uint;
  }

  string public constant override PMNAME = 'Json';
  uint public constant override PMVERSION = 1;

  function encode(Item[] memory items_, Format format_) public pure returns(string memory){

      bytes[] memory parts_ = new bytes[](items_.length);
      bytes memory append_ = ',';
      bool include_key_;

      for (uint i = 0; i < items_.length; i++) {

        Item memory item = items_[i];

        if(i+1 == items_.length) {
          append_ = '';
        }

        if((format_ == Format.OBJECT || format_ == Format.KEY_VALUE))
          include_key_ = true;
        else
          include_key_ = false;

        if (item._type == Type.OBJECT || item._type == Type.ARRAY) {
          parts_[i] = abi.encodePacked(include_key_ ? _getKeyJson(item._key) : '', item._string, append_);
        } else if (item._type == Type.STRING) {
          parts_[i] = abi.encodePacked(include_key_ ? _getKeyJson(item._key) : '', '"', item._string, '"', append_);
        } else if (item._type == Type.BOOL) {
          parts_[i] = abi.encodePacked(include_key_ ? _getKeyJson(item._key) : '', item._bool ? 'true' : 'false', append_);
        } else if (item._type == Type.NUMBER) {
          parts_[i] = abi.encodePacked(include_key_ ? _getKeyJson(item._key) : '', Strings.toString(item._uint), append_);
        }

      }

      bytes memory open_;
      bytes memory close_;

      if(format_ == Format.ARRAY){
        open_ = '[';
        close_ = ']';
      }
      else if(format_ == Format.OBJECT){
        open_ = '{';
        close_ = '}';
      }

      bytes memory json_;
      for (uint i = 0; i < parts_.length; i++) {
        json_ = abi.encodePacked(json_, parts_[i]);
      }
      json_ = abi.encodePacked(open_, json_, close_);

      return string(json_);
  }


  function _getKeyJson(string memory key_) private pure returns(string memory){
    return string(abi.encodePacked('"', key_,'":'));
  }

}

// File: @polly-tools/core/contracts/modules/Meta.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import '../Polly.sol';
import '../PollyConfigurator.sol';
import './Json.sol';


contract Meta is PMClone {

  Json private _json_parser;
  string public constant override PMNAME = 'Meta';
  uint public constant override PMVERSION = 1;

  struct Item {
    Json.Type _type;
    string _key;
    string _inject;
  }

  mapping(uint => mapping(string => Polly.Param)) private _keys;
  mapping(uint => mapping(string => bool)) private _locked_id_keys;
  mapping(string => bool) private _locked_keys;
  mapping(uint => bool) private _locked_ids;

  modifier onlyManager() {
    require(hasRole('manager', msg.sender), 'ONLY_MANAGER');
    _;
  }

  constructor() PMClone(){
    _setConfigurator(address(new MetaConfigurator()));
  }

  function setJsonParser(address json_parser) public onlyManager {
    _json_parser = Json(json_parser);
  }

  function _reqValidKeyID(uint id_, string memory key_) private view {
    require(!isLockedId(id_), string(abi.encodePacked('ID_KEY_LOCKED', Strings.toString(id_))));
    require(!isLockedKey(key_), string(abi.encodePacked('KEY_LOCKED', key_)));
    require(!isLockedIdKey(id_, key_), string(abi.encodePacked('KEY_LOCKED', Strings.toString(id_), ':', key_)));
  }



  /// JSON
  function getJSON(uint id_, Item[] memory items_, Json.Format format_) public view returns (string memory) {

    Json.Item[] memory json_items_ = new Json.Item[](items_.length);
    Item memory item;

    for (uint i = 0; i < items_.length; i++) {

      item = items_[i];

      json_items_[i]._key = item._key;
      json_items_[i]._type = item._type;

      if(item._type == Json.Type.ARRAY || item._type == Json.Type.OBJECT) {
        json_items_[i]._string = item._inject;
      } else if (item._type == Json.Type.STRING) {
        json_items_[i]._string = _keys[id_][item._key]._string;
      } else if (item._type == Json.Type.BOOL) {
        json_items_[i]._bool = _keys[id_][item._key]._bool;
      } else if (item._type == Json.Type.NUMBER) {
        json_items_[i]._uint = _keys[id_][item._key]._uint;
      }

    }

    string memory json_ = _json_parser.encode(json_items_, format_);

    return string(json_);

  }

  function _getKeyJson(string memory key_) private pure returns(string memory){
    return string(abi.encodePacked('"', key_,'":'));
  }


  /// Access
  function lockKey(string memory key_) public onlyManager {
    _locked_keys[key_] = true;
  }

  function lockId(uint id_) public onlyManager {
    _locked_ids[id_] = true;
  }

  function lockIdKey(uint id_, string memory key_) public onlyManager {
    _locked_id_keys[id_][key_] = true;
  }

  function isLockedKey(string memory key_) public view returns (bool) {
    return _locked_keys[key_];
  }

  function isLockedId(uint id_) public view returns (bool) {
    return _locked_ids[id_];
  }

  function isLockedIdKey(uint id_, string memory key_) public view returns (bool) {
    return _locked_id_keys[id_][key_];
  }

  function isLocked(uint id_, string memory key_) public view returns (bool) {
    return isLockedKey(key_) || isLockedId(id_) || isLockedIdKey(id_, key_);
  }


  /// Setters
  function set(uint id_, string memory key_, Polly.Param memory value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._string = value_._string;
    _keys[id_][key_]._uint = value_._uint;
    _keys[id_][key_]._int = value_._int;
    _keys[id_][key_]._bool = value_._bool;
    _keys[id_][key_]._address = value_._address;
  }

  function setString(uint id_, string memory key_, string memory value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._string = value_;
  }

  function setUint(uint id_, string memory key_, uint value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._uint = value_;
  }

  function setInt(uint id_, string memory key_, int value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._int = value_;
  }

  function setBool(uint id_, string memory key_, bool value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._bool = value_;
  }

  function setAddress(uint id_, string memory key_, address value_) public onlyManager {
    _reqValidKeyID(id_, key_);
    _keys[id_][key_]._address = value_;
  }

  function wipeKey(uint id_, string memory key_) public onlyManager {
    _reqValidKeyID(id_, key_);
    delete _keys[id_][key_];
  }



  /// Getters

  /// @dev Get a key param value
  /// @param id_ The id of the param
  /// @param key_ The key of the param
  /// @return The param value
  function get(uint id_, string memory key_) public view returns (Polly.Param memory) {
    return _keys[id_][key_];
  }

  /// @dev a function to retrieve a string value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getString(uint id_, string memory key_) public view returns (string memory) {
    return _keys[id_][key_]._string;
  }

  /// @dev a function to retrieve a uint value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getUint(uint id_, string memory key_) public view returns (uint) {
    return _keys[id_][key_]._uint;
  }

  /// @dev a function to retrieve a int value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getInt(uint id_, string memory key_) public view returns (int) {
    return _keys[id_][key_]._int;
  }

  /// @dev a function to retrieve a bool value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getBool(uint id_, string memory key_) public view returns (bool) {
    return _keys[id_][key_]._bool;
  }

  /// @dev a function to retrieve a address value from a key
  /// @param id_ the id of the key
  /// @param key_ the key to retrieve
  /// @return the value of the key
  function getAddress(uint id_, string memory key_) public view returns (address) {
    return _keys[id_][key_]._address;
  }


  function getBatchForId(uint id_, string[] memory keys_) public view returns (Polly.Param[] memory) {
    Polly.Param[] memory params_ = new Polly.Param[](keys_.length);
    for (uint i = 0; i < keys_.length; i++) {
      params_[i] = _keys[id_][keys_[i]];
    }
    return params_;
  }

  function setBatchForId(uint id_, string[] memory keys_, Polly.Param[] memory values_) public onlyManager {
    require(keys_.length == values_.length, "KEY_VALUE_LENGHT_MISMATCH");
    for (uint i = 0; i < keys_.length; i++) {
      _reqValidKeyID(id_, keys_[i]);
      _keys[id_][keys_[i]] = values_[i];
    }
  }

}


contract MetaConfigurator is PollyConfigurator {

  function outputs() public pure override returns (string[] memory) {

    string[] memory outputs_ = new string[](1);
    outputs_[0] = "module || Meta || address of the Meta module clone";

    return outputs_;

  }

  function run(Polly polly_, address for_, Polly.Param[] memory) public override payable returns(Polly.Param[] memory){

    // Clone a Meta module)
    Meta meta_ = Meta(polly_.cloneModule('Meta', 1));

    // Set the json module to use
    meta_.setJsonParser(polly_.getModule('Json', 1).implementation);

    // Grant roles to the address calling the configurator
    _transfer(address(meta_), for_);

    // Return the cloned module as part of the return parameters
    Polly.Param[] memory return_ = new Polly.Param[](1);
    return_[0]._string = 'Meta';
    return_[0]._address = address(meta_); // The address of newly cloned and configured meta module
    return_[0]._uint = 1; // The version of the module

    return return_;

  }


}

// File: @polly-tools/core/contracts/modules/Token721.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import "@openzeppelin/contracts/token/ERC721/ERC721.sol";
import "@openzeppelin/contracts/security/ReentrancyGuard.sol";
import '../Polly.sol';
import '../PollyConfigurator.sol';
import '../PollyAux.sol';
import '../PollyToken.sol';
import './Json.sol';
import './Meta.sol';

contract Token721 is PollyToken, ERC721, ReentrancyGuard {


  string public constant override PMNAME = 'Token721';
  uint public constant override PMVERSION = 1;

  uint internal _minted;

  constructor() ERC721("", "") {
    _setConfigurator(address(new Token721Configurator()));
  }


  /*

  ERC721

  */


  function name() public view override returns (string memory) {
    return getMeta(0, 'collectionName')._string;
  }

  function symbol() public view override returns (string memory) {
    return getMeta(0, 'collectionSymbol')._string;
  }

  function exists(uint id_) public view returns (bool) {
    return _exists(id_);
  }

  function totalSupply() public view returns (uint) {
    return _minted;
  }


  /*

  TOKENS

  */

  /// @dev create a new token
  function createToken(PollyToken.MetaEntry[] memory meta_, address mint_) public returns (uint) {

    _requireRole('manager', msg.sender);

    uint id_ = _createToken(meta_);

    if(mint_ != address(0))
      _mintFor(mint_, id_, true, PollyAux.Msg(msg.sender, 0, msg.data, msg.sig));

    return id_;

  }



  /// @dev mint a token
  /// @param id_ the id of the token
  function _mintFor(address for_, uint id_, bool pre_, PollyAux.Msg memory msg_) private {

    address hook_ = getHookAddress('action_BeforeMint721');
    if(hook_ != address(0))
      _call(hook_, abi.encodeWithSignature('action_BeforeMint721(address,uint256,bool,(address,uint256,bytes,bytes4))', for_, id_, pre_, msg_));

    _mint(for_, id_);
    _minted++;

    hook_ = getHookAddress('action_AfterMint721');
    if(hook_ != address(0))
      _call(hook_, abi.encodeWithSignature('action_AfterMint721(address,uint256,bool,(address,uint256,bytes,bytes4))', for_, id_, pre_, msg_));

  }




  /// @dev mint a token
  /// @param id_ the id of the token
  function mint(uint id_) public payable nonReentrant {
    _mintFor(msg.sender, id_, false, PollyAux.Msg(msg.sender, msg.value, msg.data, msg.sig));
    _postMintTransfer(id_, msg.value);
  }


  /// @dev get the token uri
  /// @param id_ the id of the token
  function tokenURI(uint id_) public view override returns(string memory) {
    require(exists(id_), 'TOKEN_DOES_NOT_EXIST');
    return _tokenUri(id_);
  }


  /// Override
  function supportsInterface(bytes4 interfaceId) public view virtual override(PollyToken, ERC721) returns (bool){
      return super.supportsInterface(interfaceId);
  }


}







contract Token721Configurator is PollyConfigurator, ReentrancyGuard {

  function inputs() public pure override virtual returns (string[] memory) {

    string[] memory inputs_ = new string[](1);
    inputs_[0] = '...address || Aux addresses || addresses of the aux contracts to attach';
    return inputs_;
  }

  function outputs() public pure override virtual returns (string[] memory) {

    string[] memory outputs_ = new string[](2);

    outputs_[0] = 'module || Token721 || the main Token721 module address';
    outputs_[1] = 'module || Meta || the meta handler address';

    return outputs_;

  }

  function run(Polly polly_, address for_, Polly.Param[] memory inputs_) public override payable nonReentrant returns(Polly.Param[] memory) {

    Polly.Param[] memory rparams_ = new Polly.Param[](3);

    // Clone the Token721 module
    Token721 token_ = Token721(polly_.cloneModule('Token721', 1));
    rparams_[0]._string = 'Token721';
    rparams_[0]._address = address(token_);
    rparams_[0]._uint = 1;

    // Configure a Meta module
    Polly.Param[] memory meta_params_ = polly_.configureModule(
      'Meta', // module name
      1, // version
      new Polly.Param[](0), // No inputs
      false, // Don't store
      '' // No config name
    );

    token_.setMetaHandler(meta_params_[0]._address);
    token_.grantRole('manager', meta_params_[0]._address);

    Meta meta_ = Meta(meta_params_[0]._address);
    meta_.grantRole('manager', address(token_));

    rparams_[1] = meta_params_[0];


    /// Configure all the Token721Aux modules passed to the configurator
    if(inputs_.length > 0){
      for(uint i = 0; i < inputs_.length; i++){
        token_.registerAux(inputs_[i]._address);
      }
    }


    // Transfer to sender
    _transfer(address(token_), for_);
    _transfer(meta_params_[0]._address, for_);

    return rparams_;

  }


}

// File: @polly-tools/core/contracts/Polly.sol



/*

       -*%%+++*#+:              .+     --
        =@*     *@*           -#@-  .=#%
        %@.      @@:          .@*    :@:
       -@*       @@.          =@.    #*  :=     --
       #@.      =@#  +*+#:    @=    =@: *=%*    *@
      .@*      :@#.-%-  =@   +%    .@*.+  +@    =#
      *@.    .+%= =%.   =@. :@-    *@     =@:   *-
     :@#---===-  -@-    #@  %%    :@-     -@-  .#
     #@:        .@*    .@+ +@:    ##      -@-  #.
    :@%         *@.    *% .@+    :@.      -@- =:
    #@-         @*    -@. +%  =. %+ .=    -@::=
   :@#          @=   -@- .@-==  +@-+-     -@-*
   *@-          #*  *#.  #@*.  :@@+       =@+
.:=++=:.         ===:    +:    :=.        +=
                                         +-
                                       =+.
                                  +*-=+.

v1

*/

//SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

import "@openzeppelin/contracts/proxy/Clones.sol";
import "@openzeppelin/contracts/access/Ownable.sol";
import "./PollyModule.sol";
import "./PollyConfigurator.sol";
import "./PollyFeeHandler.sol";

/// @title Polly main contract
/// @author polly.tools

/**
 *
 * Polly is a modular smart contract framework that allows anyone to deploy registered modules as proxy contracts onchain.
 * The framework is built and designed by continuousengagement.xyz and is open source.
 */

contract Polly is Ownable {


    enum ModuleType {
        READONLY, CLONE
    }

    enum ParamType {
      UINT, INT, BOOL, STRING, ADDRESS
    }

    /// @dev struct for an uninstantiated module
    struct Module {
      string name;
      uint version;
      address implementation;
      bool clone;
    }

    /// @dev struct for an instantiated module
    struct ModuleInstance {
      string name;
      uint version;
      address location;
    }

    /// @dev struct for a module configuration
    struct Config {
      string name;
      string module;
      uint version;
      Param[] params;
    }

    /// @dev struct for a general type parameter
    struct Param {
      uint _uint;
      int _int;
      bool _bool;
      string _string;
      address _address;
    }


    /// PRIVATE PROPERTIES ///
    string[] private _module_names; // names of registered modules
    mapping(string => mapping(uint => address)) private _modules; // mapping of registered modules and their versions - name => (id => implementation)
    uint private _module_count; // the total number of registered modules
    mapping(string => uint) private _module_versions; // mapping of registered modules and their latest version - name => version
    mapping(address => mapping(uint => Config)) private _configs; // mapping of module configs - owner => (id => config)
    mapping(address => uint) private _configs_count; // mapping of owner config count - owner => count
    mapping(address => bool) private _configurators; // mapping of configurators - address => bool
    PollyFeeHandler private _fee_handler; // fee handler contract
    //////////////////



    /// EVENTS ///
    event moduleUpdated(
      string indexed indexedName, string name, uint version, address indexed implementation
    );

    event moduleCloned(
      string indexed indexedName, string name, uint version, address location
    );

    event moduleConfigured(
      string indexedName, string name, uint version, Polly.Param[] params
    );


    /// CONSTRUCTOR ///

    constructor() {
      _fee_handler = new PollyFeeHandler();
    }


    /// FEE ///
    function fee(address for_, uint value_) public view returns (uint) {
      return _fee_handler.get(for_, value_);
    }


    /// MODULES ///

    /// @dev adds or updates a given module implemenation
    /// @param implementation_ address of the module implementation
    function updateModule(address implementation_) public onlyOwner {

      string memory name_ = PollyModule(implementation_).PMNAME();
      uint version_ = PollyModule(implementation_).PMVERSION();

      require(_modules[name_][version_] == address(0), "MODULE_VERSION_EXISTS");
      require(version_ == _module_versions[name_]+1, "MODULE_VERSION_INVALID");

      _modules[name_][version_] = implementation_; // add module implementation address
      _module_versions[name_] = version_; // update module latest version

      if(version_ == 1)
        _module_names.push(name_); // This is a new module, add to module names mapping

      address configurator_ = getConfigurator(name_, version_); // get configurator address

      if(configurator_ != address(0))
        _configurators[configurator_] = true; // Store the configurator address for this module

      emit moduleUpdated(name_, name_, version_, implementation_); // emit event moduleUpated

    }


    /// @dev retrieves a specific module version base
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return address of the module implementation
    function getModule(string memory name_, uint version_) public view returns(Module memory){

      if(version_ < 1)
        version_ = getLatestModuleVersion(name_); // version_ is 0, get latest version

      require(moduleExists(name_, version_), string(abi.encodePacked('INVALID_MODULE_OR_VERSION: ', name_, '@', Strings.toString(version_))));

      Polly.ModuleType type_ = PollyModule(_modules[name_][version_]).PMTYPE(); // get module info from stored implementation
      bool clone_ = type_ == Polly.ModuleType.CLONE;

      return Module(name_, version_, _modules[name_][version_], clone_); // return module

    }


    /// @dev returns a list of modules available
    /// @param limit_ uint maximum number of modules to return
    /// @param page_ uint page of modules to return
    /// @param ascending_ bool sort modules ascending (true) or descending (false)
    /// @return Module[] array of modules
    function getModules(uint limit_, uint page_, bool ascending_) public view returns(Module[] memory){

      uint count_ = _module_names.length; // get total number of modules

      if(limit_ < 1 || limit_ > count_)
        limit_ = count_; // limit_ is 0, get all modules

      if(page_ < 1)
        page_ = 1; // page_ is 0, get first page

      uint i; // iterator
      uint index_; // index of module name in _module_names


      if(ascending_)
        index_ = page_ == 1 ? 0 : (page_-1)*limit_; // ascending, set index to last module result set
      else
        index_ = page_ == 1 ? count_ : count_ - (limit_*(page_-1)); // descending, set index to first module on result set


      if(
        (ascending_ && index_ >= count_) // ascending, index is greater than total number of modules
        || // or
        (!ascending_ && index_ == 0) // descending, index is 0
      )
        return new Module[](0); // no modules available - bail early


      Module[] memory modules_ = new Module[](limit_); // create array of modules

      if(ascending_){

        // ASCENDING
        while(index_ < limit_){
            modules_[i] = getModule(_module_names[index_], 0);
            ++i;
            ++index_;
        }

      }
      else {

        /// DESCENDING
        while(index_ > 0 && i < limit_){
            modules_[i] = getModule(_module_names[index_-1], 0);
            ++i;
            --index_;
        }

      }


      return modules_; // return modules

    }


    /// @dev retrieves the most recent version number for a module
    /// @param name_ string name of the module
    /// @return uint version number of the module
    function getLatestModuleVersion(string memory name_) public view returns(uint){
      return _module_versions[name_];
    }


    /// @dev check if a module version exists
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return exists_ bool true if module version exists
    function moduleExists(string memory name_, uint version_) public view returns(bool exists_){
      if(_modules[name_][version_] != address(0))
        exists_ = true;
      return exists_;
    }


    /// @dev get the configurator for a given module
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return address of the module configurator
    function getConfigurator(string memory name_, uint version_) public view returns(address){
      return PollyModule(_modules[name_][version_]).configurator();
    }

    /// @dev get the configurator fee for a given module
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return fee_ uint fee in points
    function getConfiguratorFee(address for_, string memory name_, uint version_, Polly.Param[] memory params_) public view returns(uint){

      address conf_address_ = getConfigurator(name_, version_);
      if(conf_address_ == address(0))
        return 0;
      return PollyConfigurator(conf_address_).fee(this, for_, params_);

    }


    /// @dev clone a given module
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @return address of the cloned module implementation
    function cloneModule(string memory name_, uint version_) public returns(address) {

      if(version_ == 0)
        version_ = getLatestModuleVersion(name_); // version_ is 0, get latest version

      require(moduleExists(name_, version_), string(abi.encodePacked('INVALID_MODULE_OR_VERSION: ', name_, '@', Strings.toString(version_))));
      require(PollyModule(_modules[name_][version_]).PMTYPE() == Polly.ModuleType.CLONE, 'MODULE_NOT_CLONABLE'); // module is not clonable

      address implementation_ = _modules[name_][version_]; // get module implementation address

      PollyModule module_ = PollyModule(Clones.clone(implementation_)); // clone module implementation
      module_.init(msg.sender); // initialize module


      emit moduleCloned(name_, name_, version_, address(module_)); // emit module cloned event
      return address(module_); // return cloned module address

    }


    /// @dev if a module is configurable run the configurator
    /// @param name_ string name of the module
    /// @param version_ uint version of the module
    /// @param params_ array of configuration input parameters
    /// @return rparams_ array of configuration return parameters
    function configureModule(string memory name_, uint version_, Polly.Param[] memory params_, bool store_, string memory config_name_) public payable returns(Polly.Param[] memory rparams_) {

      if(version_ == 0)
        version_ = getLatestModuleVersion(name_); // version_ is 0, get latest version

      Module memory module_ = getModule(name_, version_); // get module
      address configurator_ = PollyModule(module_.implementation).configurator(); // get module configurator address
      require(configurator_ != address(0), 'NO_MODULE_CONFIGURATOR'); // module is not configurable - revert

      PollyConfigurator config_ = PollyConfigurator(configurator_); // get configurator instance

      // Fee
      uint fee_ = config_.fee(this, msg.sender, params_); // get configurator fee info
      if(!_configurators[msg.sender]){
        fee_ = fee_+_fee_handler.get(msg.sender, fee_);
      }

      require(fee_ == msg.value, 'INVALID_FEE');

      // Configure
      rparams_ = config_.run{value: fee_}(this, msg.sender, params_); // run configurator with params

      // Store
      if(store_){

        uint new_count_ = _configs_count[msg.sender] + 1; // get new config count for storing
        _configs[msg.sender][new_count_].name = config_name_; // store config name
        _configs[msg.sender][new_count_].module = name_; // store module name
        _configs[msg.sender][new_count_].version = version_; // store module name

        for (uint i = 0; i < rparams_.length; i++){ // store each config params
          _configs[msg.sender][new_count_].params.push(rparams_[i]);
        }

        _configs_count[msg.sender] = new_count_; // update config count

      }

      emit moduleConfigured(name_, name_, version_, rparams_); // emit module configured event
      return rparams_;  // return configuration params

    }

    /// @dev retrieves the stored configurations for a given address
    /// @param address_ address of the user
    /// @param limit_ maximum number of configurations to return
    /// @param page_ page of configurations to return
    /// @param ascending_ sort configurations ascending (true) or descending (false)
    /// @return PollyConfigurator.Config[] array of configurations
    function getConfigsForAddress(address address_, uint limit_, uint page_, bool ascending_) public view returns(Config[] memory){

      uint count_ = _configs_count[address_]; // get total number of configs for address

      if(limit_ < 1 || limit_ > count_)
        limit_ = count_;  // limit is 0 or greater than total number of configs, set limit to total number of configs

      if(page_ < 1)
        page_ = 1; // page is less than 1, set page to 1

      uint i; // counter
      uint id_; // config id

      if(ascending_)
        id_ = page_ == 1 ? 1 : ((page_-1)*limit_)+1; // calculate ascending start id
      else
        id_ = page_ == 1 ? count_ : count_ - (limit_*(page_-1)); // calculate descending start id


      if(
        (ascending_ && id_ > count_) // ascending and id is greater than total number of configs
        ||
        (!ascending_ && id_ == 0) // descending and id is 0
      )
        return new Config[](0); // no modules available - bail early


      Config[] memory configs_ = new Config[](limit_);  // create array of configs


      if(ascending_){

        // ASCENDING
        while(id_ <= count_ && i < limit_){
            configs_[i] = _configs[address_][id_];
            ++i;
            ++id_;
        }

      }
      else {

        /// DESCENDING
        while(id_ > 0 && i < limit_){
            configs_[i] = _configs[address_][id_];
            ++i;
            --id_;
        }

      }

      return configs_;

    }


    /// @dev retrieve a stored configuration for a given address and config index
    /// @param address_ address of the user
    /// @param index_ index of the configuration
    /// @return Polly.Config configuration
    function getConfigForAddress(address address_, uint index_) public view returns(Config memory){
      require(index_ > 0 && index_ <= _configs_count[address_], 'INVALID_CONFIG_INDEX'); // invalid config index
      return _configs[address_][index_]; // return config
    }


}

// File: @polly-tools/core/contracts/PollyAux.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import "./Polly.sol";

abstract contract PollyAux {

  struct Msg {
    address _sender;
    uint _value;
    bytes _data;
    bytes4 _sig;
  }

  fallback() external {}
  function hooks() external view virtual returns (string[] memory);
  function filter(string memory, uint, Polly.Param memory, Msg memory msg_) external view virtual returns (Polly.Param memory) {}
  function filter(string memory, uint, string memory, Msg memory msg_) external view virtual returns (string memory) {}
  function filter(string memory, uint, uint, Msg memory msg_) external view virtual returns (uint) {}
  function filter(string memory, uint, address, Msg memory msg_) external view virtual returns (address) {}
  function filter(string memory, uint, bool, Msg memory msg_) external view virtual returns (bool) {}

}



abstract contract PollyAuxParent {

  mapping(string => address) internal _aux_hooks;

  function registerAux(address aux_) public virtual;
  function _registerHooks(string[] memory hooks_, address aux_) internal {
    for (uint i = 0; i < hooks_.length; i++){
      _aux_hooks[hooks_[i]] = aux_;
    }
  }

  function getHookAddress(string memory hook_) public view returns (address) {
    return _aux_hooks[hook_];
  }

}

// File: @polly-tools/core/contracts/PollyConfigurator.sol




//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import './Polly.sol';
import './PollyModule.sol';

abstract contract PollyConfigurator {

  string internal constant ADMIN = 'admin';
  string internal constant MANAGER = 'manager';

  function fee(Polly, address, Polly.Param[] memory) public view virtual returns(uint){return 0;}
  function inputs() external view virtual returns (string[] memory){return new string[](0);}
  function outputs() external view virtual returns (string[] memory){return new string[](0);}
  function run(Polly, address, Polly.Param[] memory) external virtual payable returns(Polly.Param[] memory){return new Polly.Param[](0);}

  function _transfer(address module_, address to_) internal {
    _grantAll(to_, module_);
    _revokeAll(address(this), module_);
  }

  function _grantManager(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.grantRole(MANAGER, to_);
  }

  function _grantAdmin(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.grantRole(ADMIN, to_);
  }

  function _grantAll(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.grantRole(ADMIN, to_);
    m_.grantRole(MANAGER, to_);
  }

  function _revokeManager(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.revokeRole(MANAGER, to_);
  }

  function _revokeAdmin(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.revokeRole(ADMIN, to_);
  }

  function _revokeAll(address to_, address module_) internal {
    PMClone m_ = PMClone(module_);
    m_.revokeRole(MANAGER, to_);
    m_.revokeRole(ADMIN, to_);
  }

}

// File: @polly-tools/core/contracts/PollyFeeHandler.sol



// SPDX-License-Identifier: MIT

pragma solidity ^0.8.4;

contract PollyFeeHandler {

  /// @dev get the fee for a given address and amount
  function get(
    address,
    uint value_
  )
  public pure returns (uint){
    if(value_ == 0)
      return 0;
    return (value_/100)*5;
  }

}

// File: @polly-tools/core/contracts/PollyModule.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;

import "@openzeppelin/contracts/proxy/Clones.sol";
import "@openzeppelin/contracts/utils/Strings.sol";
import "./Polly.sol";

/// @dev full interface for a PollyModule
interface PollyModule {

  function PMTYPE() external view returns(Polly.ModuleType);
  function PMNAME() external view returns(string memory);
  function PMVERSION() external view returns(uint);

  // Clonable
  function init(address for_) external;
  function didInit() external view returns(bool);
  function configurator() external view returns(address);
  function isManager(address address_) external view returns(bool);

  // Keystore
  function lockKey(string memory key_) external;
  function isLockedKey(string memory key_) external view returns(bool);
  function set(Polly.ParamType type_, string memory key_, Polly.Param memory value_) external;
  function get(string memory key_) external view returns(Polly.Param memory value_);

}


abstract contract PMBase {

  address private _configurator;

  function PMTYPE() external view virtual returns(Polly.ModuleType);
  function PMNAME() external view virtual returns(string memory);
  function PMVERSION() external view virtual returns(uint);

  // Configuration
  function _setConfigurator(address configurator_) internal {
    _configurator = configurator_;
  }

  function configurator() public view returns(address){
    return _configurator;
  }

}


abstract contract PMReadOnly is PMBase {

  Polly.ModuleType public constant override PMTYPE = Polly.ModuleType.READONLY;

}


abstract contract PMClone is PMBase {

  Polly.ModuleType public constant override PMTYPE = Polly.ModuleType.CLONE;

  bool private _did_init = false;

  address private _owner;
  mapping(address => mapping(string => bool)) private _roles;

  modifier onlyRole(string memory role_){
    require(hasRole(role_, msg.sender), string(abi.encodePacked('MISSING_ROLE: ', role_, ' - ', Strings.toHexString(uint160(msg.sender), 20))));
    _;
  }


  // Initialization
  constructor(){
    init(msg.sender);
  }

  function init(address for_) public virtual {
    require(!_did_init, 'ALREADY_INITIALIZED');
    _did_init = true;
    _grantRole('admin', for_);
    _grantRole('manager', for_);
  }

  function didInit() public view returns(bool){
    return _did_init;
  }


  /// Access control

  function _requireRole(string memory role_, address address_) internal view {
    require(hasRole(role_, address_), string(abi.encodePacked('MISSING_ROLE: ', role_, ' - ', Strings.toHexString(uint160(address_), 20))));
  }

  function owner() public view returns(address){
    return _owner;
  }

  function _setOwner(address new_owner_) internal {
    _owner = new_owner_;
    _grantRole('admin', new_owner_);
  }

  function setOwner(address new_owner_) public {
    _requireRole('admin', msg.sender);
    _setOwner(new_owner_);
  }

  function hasRole(string memory role_, address check_) public view returns(bool){
    return _roles[check_][role_];
  }

  function _grantRole(string memory role_, address to_) internal {
    _roles[to_][role_] = true;
  }

  function grantRole(string memory role_, address to_) public {
    _requireRole('admin', msg.sender);
    _grantRole(role_, to_);
  }

  function revokeRole(string memory role_, address to_) public {
    _requireRole('admin', msg.sender);
    _roles[to_][role_] = false;
  }

  function renounceRole(string memory role_) public {
    _requireRole(role_, msg.sender);
    _roles[msg.sender][role_] = false;
  }


}

// File: @polly-tools/core/contracts/PollyToken.sol



//SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.4;
import '@openzeppelin/contracts/utils/introspection/ERC165.sol';
import './Polly.sol';
import './PollyAux.sol';
import './modules/Meta.sol';


/// @title IERC2981Royalties
/// @dev Interface for the ERC2981 - Token Royalty standard
interface IERC2981Royalties {
    /// @notice Called with the sale price to determine how much royalty
    //          is owed and to whom.
    /// @param id_ - the NFT asset queried for royalty information
    /// @param value_ - the sale price of the NFT asset specified by id_
    /// @return receiver_ - address of who should be sent the royalty payment
    /// @return amount_ - the royalty payment amount for value sale price
    function royaltyInfo(uint256 id_, uint256 value_)
        external
        view
        returns (address receiver_, uint256 amount_);
}



contract PollyToken is PMClone, PollyAuxParent, ERC165, IERC2981Royalties {

  /// DEFINITIONS

  struct MetaEntry {
    string _key;
    Polly.Param _value;
  }

  Meta internal _meta;

  uint[] internal _tokens;
  uint public highestId;

  event TokenCreated(uint id);


  /// @dev get the name of the module
  function PMNAME() external pure override virtual returns (string memory) {
    return 'PollyToken';
  }

  /// @dev get the version of the module
  function PMVERSION() external pure override virtual returns (uint) {
    return 1;
  }



  function _call(address target_, bytes memory data_) internal returns (bytes memory) {

      (bool success_, bytes memory result_) = target_.call(data_);

      if(!success_){
        if(result_.length < 68) revert();
        assembly {
          result_ := add(result_, 0x04)
        }
        revert(abi.decode(result_, (string)));
      }

      return result_;

  }

  function _staticcall(address target_, bytes memory data_) internal view returns (bytes memory) {

      (bool success_, bytes memory result_) = target_.staticcall(data_);

      if(!success_){
        if(result_.length < 68) revert();
        assembly {
          result_ := add(result_, 0x04)
        }
        revert(abi.decode(result_, (string)));
      }

      return result_;

  }


  /////////////////////////
  // AUX
  /////////////////////////

  /// @dev register aux
  /// @param aux_ the aux to register
  function registerAux(address aux_) public override virtual {
    _requireRole('admin', msg.sender);
    _registerHooks(PollyAux(aux_).hooks(), aux_);
  }


  /////////////////////////
  // META
  /////////////////////////


  /// @dev set meta handler
  /// @param handler_ the address of the meta handler
  function setMetaHandler(address handler_) public {
    _requireRole('admin', msg.sender);
    require(address(_meta) == address(0), 'META_HANDLER_SET');
    _meta = Meta(handler_);
  }


  /// @dev get meta handler attached to this contract
  function getMetaHandler() public view returns (Meta) {
    return _meta;
  }


  function getMeta(uint id_, string memory key_) public view returns (Polly.Param memory) {

    // Check for token specific filter
    string memory hook_ = string(abi.encodePacked('filter_Meta_', key_));
    address filter_ = getHookAddress(hook_);

    Polly.Param memory meta_ = _meta.get(id_, key_);

    if(filter_ != address(0)){
      bytes memory data_ = _staticcall(filter_, abi.encodeWithSignature(string(abi.encodePacked(hook_, '(uint256,(uint256,int256,bool,string,address))')), id_, _meta.get(id_, key_)));
      meta_ = abi.decode(data_, (Polly.Param));
    }

    return meta_;

  }




  /////////////////////////
  // TOKENS
  /////////////////////////


  /// @dev create a new token
  function _createToken(MetaEntry[] memory meta_) internal returns (uint) {

    uint id_ = highestId + 1;

    address hook_ = getHookAddress('action_BeforeCreateToken');
    if(hook_ != address(0))
      _call(hook_, abi.encodeWithSignature('action_BeforeCreateToken(uint256,(uint256,int256,bool,string,address)[])', id_, meta_));

    for(uint i = 0; i < meta_.length; i++) {
      _meta.set(id_, meta_[i]._key, meta_[i]._value);
    }

    _tokens.push(id_);
    _meta.setBool(id_, 'created', true);
    _meta.lockIdKey(id_, 'created');

    hook_ = getHookAddress('action_AfterCreateToken');
    if(hook_ != address(0))
      _call(hook_, abi.encodeWithSignature('action_AfterCreateToken(uint256)', id_, meta_));

    emit TokenCreated(id_);
    if(id_ > highestId) highestId = id_;
    return id_;

  }


  function getTokens(uint limit_, uint page_) public view returns (uint[] memory) {

    uint[] memory tokens_ = new uint[](limit_);
    uint count_ = 0;
    uint offset_ = page_ > 1 ? page_-1 * limit_ : 0;
    for(uint i = offset_; i < _tokens.length; i++){
      if(count_ == limit_) break;
      tokens_[count_] = _tokens[i];
      count_++;
    }

    return tokens_;

  }


  function _tokenUri(uint id_) internal view returns (string memory){
    return getMeta(id_, 'tokenUri')._string;
  }




  /////////////////////////
  // MISC
  /////////////////////////



  /// @dev get the contract metadata uri
  function contractURI() public view returns(string memory) {
    return getMeta(0, 'collectionUri')._string;
  }


  /// @dev get the royalty info
  /// @param id_ the id of the token
  /// @param value_ the value of the sale
  function royaltyInfo(uint id_, uint value_) public view override returns (address recipient_, uint amount_) {

     // Get royalty base and recipient for the token
    uint base_ = getMeta(id_, 'royaltyBase')._uint;
    recipient_ = getMeta(id_, 'royaltyRecipient')._address;

    // Use default royalty if no royalty is set for the token
    if(base_ == 0 && getMeta(0, 'royaltyBase')._uint > 0)
      base_ = getMeta(0, 'royaltyBase')._uint;

    // Use default recipient if no recipient is set for the token
    if(recipient_ == address(0) && getMeta(0, 'royaltyRecipient')._address != address(0))
      recipient_ = getMeta(0, 'royaltyRecipient')._address;

    // If either base or recipient is not set, return 0
    if(base_ == 0 || recipient_ == address(0) || value_ == 0)
      return (recipient_, 0);

    // Limit base to 10000 (100%)
    if(base_ > 10000)
      base_ = 10000;

    // Calculate and return royalty
    return (recipient_, (value_ * base_) / 10000);

  }


  // Withdraw all ETH from this contract
  function withdraw() public {
    _requireRole('admin', msg.sender);
    payable(msg.sender).transfer(address(this).balance);
  }


  function _postMintTransfer(uint id_, uint amount_) internal {

    // Send msg.value to the recipient address for token
    if(amount_ > 0){

      Meta meta_ = getMetaHandler();
      // Check if the token has a recipient address
      address recipient_ = meta_.getAddress(id_, 'collectionRecipient');
      // If not, check if contract has a recipient address
      if(recipient_ == address(0))
        recipient_ = meta_.getAddress(0, 'collectionRecipient');

      if(recipient_ != address(0))
        payable(recipient_).transfer(amount_);

    }

  }


  /// Override
  function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool){
      return interfaceId == type(IERC2981Royalties).interfaceId;
  }


}

// File: base64-sol/base64.sol



// SPDX-License-Identifier: MIT

pragma solidity >=0.6.0;

/// @title Base64
/// @author Brecht Devos - <brecht@loopring.org>
/// @notice Provides functions for encoding/decoding base64
library Base64 {
    string internal constant TABLE_ENCODE = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
    bytes  internal constant TABLE_DECODE = hex"0000000000000000000000000000000000000000000000000000000000000000"
                                            hex"00000000000000000000003e0000003f3435363738393a3b3c3d000000000000"
                                            hex"00000102030405060708090a0b0c0d0e0f101112131415161718190000000000"
                                            hex"001a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132330000000000";

    function encode(bytes memory data) internal pure returns (string memory) {
        if (data.length == 0) return '';

        // load the table into memory
        string memory table = TABLE_ENCODE;

        // multiply by 4/3 rounded up
        uint256 encodedLen = 4 * ((data.length + 2) / 3);

        // add some extra buffer at the end required for the writing
        string memory result = new string(encodedLen + 32);

        assembly {
            // set the actual output length
            mstore(result, encodedLen)

            // prepare the lookup table
            let tablePtr := add(table, 1)

            // input ptr
            let dataPtr := data
            let endPtr := add(dataPtr, mload(data))

            // result ptr, jump over length
            let resultPtr := add(result, 32)

            // run over the input, 3 bytes at a time
            for {} lt(dataPtr, endPtr) {}
            {
                // read 3 bytes
                dataPtr := add(dataPtr, 3)
                let input := mload(dataPtr)

                // write 4 characters
                mstore8(resultPtr, mload(add(tablePtr, and(shr(18, input), 0x3F))))
                resultPtr := add(resultPtr, 1)
                mstore8(resultPtr, mload(add(tablePtr, and(shr(12, input), 0x3F))))
                resultPtr := add(resultPtr, 1)
                mstore8(resultPtr, mload(add(tablePtr, and(shr( 6, input), 0x3F))))
                resultPtr := add(resultPtr, 1)
                mstore8(resultPtr, mload(add(tablePtr, and(        input,  0x3F))))
                resultPtr := add(resultPtr, 1)
            }

            // padding with '='
            switch mod(mload(data), 3)
            case 1 { mstore(sub(resultPtr, 2), shl(240, 0x3d3d)) }
            case 2 { mstore(sub(resultPtr, 1), shl(248, 0x3d)) }
        }

        return result;
    }

    function decode(string memory _data) internal pure returns (bytes memory) {
        bytes memory data = bytes(_data);

        if (data.length == 0) return new bytes(0);
        require(data.length % 4 == 0, "invalid base64 decoder input");

        // load the table into memory
        bytes memory table = TABLE_DECODE;

        // every 4 characters represent 3 bytes
        uint256 decodedLen = (data.length / 4) * 3;

        // add some extra buffer at the end required for the writing
        bytes memory result = new bytes(decodedLen + 32);

        assembly {
            // padding with '='
            let lastBytes := mload(add(data, mload(data)))
            if eq(and(lastBytes, 0xFF), 0x3d) {
                decodedLen := sub(decodedLen, 1)
                if eq(and(lastBytes, 0xFFFF), 0x3d3d) {
                    decodedLen := sub(decodedLen, 1)
                }
            }

            // set the actual output length
            mstore(result, decodedLen)

            // prepare the lookup table
            let tablePtr := add(table, 1)

            // input ptr
            let dataPtr := data
            let endPtr := add(dataPtr, mload(data))

            // result ptr, jump over length
            let resultPtr := add(result, 32)

            // run over the input, 4 characters at a time
            for {} lt(dataPtr, endPtr) {}
            {
               // read 4 characters
               dataPtr := add(dataPtr, 4)
               let input := mload(dataPtr)

               // write 3 bytes
               let output := add(
                   add(
                       shl(18, and(mload(add(tablePtr, and(shr(24, input), 0xFF))), 0xFF)),
                       shl(12, and(mload(add(tablePtr, and(shr(16, input), 0xFF))), 0xFF))),
                   add(
                       shl( 6, and(mload(add(tablePtr, and(shr( 8, input), 0xFF))), 0xFF)),
                               and(mload(add(tablePtr, and(        input , 0xFF))), 0xFF)
                    )
                )
                mstore(resultPtr, shl(232, output))
                resultPtr := add(resultPtr, 3)
            }
        }

        return result;
    }
}

// File: contracts/Wingbeats.sol



// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

import "@polly-tools/core/contracts/modules/Json.sol";
import "@polly-tools/core/contracts/modules/Meta.sol";
import "@polly-tools/core/contracts/modules/Token721.sol";
import "@polly-tools/core/contracts/PollyToken.sol";
import "@polly-tools/core/contracts/Polly.sol";
import "base64-sol/base64.sol";


contract Wingbeats is PollyAux, Ownable {

    // Polly
    Polly public immutable polly;
    Token721 public collection;
    Meta public meta;
    WingbeatsMetadata public metadata;

    bool private _initialised = false;

    uint public max_supply;
    uint public min_time;
    uint public price;
    
    
    constructor(address polly_) {
        polly = Polly(polly_);
        metadata = new WingbeatsMetadata();
    }


    /// UTILS

    function _stringIsEmpty(string memory string_) private pure returns (bool) {
        return keccak256(abi.encodePacked(string_)) == keccak256(abi.encodePacked(''));
    }

    function _stringEquals(string memory a_, string memory b_) private pure returns (bool) {
        return keccak256(abi.encodePacked(a_)) == keccak256(abi.encodePacked(b_));
    }




    /// ADMIN


    /// @notice Initialise the contract
    function initialise(
        uint max_supply_,
        uint min_time_,
        uint price_,
        string memory base_uri_
    ) public onlyOwner {

        // Check if already initialised
        require(!_initialised, 'ALREADY_INITIALISED');
        
        // Params for the Collection module
        Polly.Param[] memory params_ = new Polly.Param[](1);
        params_[0]._address = address(this); // Add this contract as a aux to the collection


        // Deploy the collection
        Polly.Param[] memory rparams_ = polly.configureModule(
            "Token721", // Module name
            1, // Module version
            params_, // Module params
            false, // Save module configuration in the Polly registry?
            '' // Module configuration name if saved
        );


        // Save the token and meta addresses for convenience
        collection = Token721(rparams_[0]._address);
        meta = Meta(rparams_[1]._address);

        // Set the royalty info on token
        collection.getMetaHandler().setUint(0, 'royaltyBase', 1000);
        collection.getMetaHandler().setAddress(0, 'royaltyRecipient', msg.sender);

        // Set collection details - min time, max supply and price
        min_time = min_time_;
        max_supply = max_supply_;
        price = price_;

        // Set the base uri
        meta.setString(0, 'baseUri', base_uri_);

        // Set the collection name and symbol
        meta.setString(0, 'externalLink', 'https://wingbeats.download');
        meta.setString(0, 'externalUrlBase', 'https://wingbeats.download/token');
        meta.setString(0, 'collectionName', 'Wingbeats');
        meta.lockIdKey(0, 'collectionName');
        meta.setString(0, 'collectionSymbol', 'WNGBTS');
        meta.lockIdKey(0, 'collectionSymbol');

        // Grant all privileges of the token and meta address to message sender
        collection.grantRole('admin', msg.sender);
        collection.grantRole('manager', msg.sender);
        meta.grantRole('admin', msg.sender);
        meta.grantRole('manager', msg.sender);

        // Mark as initialised
        _initialised = true;

    }


    /// @notice set the min time if not already open
    function setMinTime(uint min_time_) public onlyOwner {
        require(!open(), 'ALREADY_OPEN');
        min_time = min_time_;
    }

    /// @notice set the metadata contract
    function setMetadata(address metadata_) public onlyOwner {
        metadata = WingbeatsMetadata(metadata_);
    }



    /// HOOKS
    
    /// @notice Get the hooks this contract implements
    function hooks() public view virtual override returns (string[] memory) {
        string[] memory hooks_ = new string[](4);
        hooks_[0] = "filter_Meta_tokenUri";
        hooks_[1] = "filter_Meta_collectionUri";
        hooks_[2] = "action_BeforeMint721";
        hooks_[3] = "action_BeforeCreateToken";
        return hooks_;
    }

    /// @notice Runs before a token is created on the collection
    function action_BeforeCreateToken(uint, Polly.Param[] memory) public pure {
        revert('NO_MANUAL_CREATE');
    }

    /// @notice Runs before a token is minted on the collection
    function action_BeforeMint721(
        address, // to_
        uint id_,
        bool, // premint_
        PollyAux.Msg memory msg_
    ) public view {

        // Check if min time is met
        require(open(), 'MIN_TIME_NOT_REACHED');
        // Check if token has already been minted
        require(!collection.exists(id_), 'TOKEN_ID_ALREADY_MINTED');
        // Check if token id is within range 1 - 97
        require(id_ > 0 && id_ <= max_supply, 'TOKEN_ID_OUT_OF_RANGE');
        // Check if token price is correct
        require(price == msg_._value, 'INVALID_PRICE');

    }

    /// @notice Check if the min time has been reached
    function open() public view returns (bool) {
        return (block.timestamp >= min_time);
    }

    /// @notice Filters the token uri for a given token id in the collection
    function filter_Meta_tokenUri(uint id_, Polly.Param memory param_) public view returns (Polly.Param memory) {

        // Set the token uri on the param struct
        param_._string = metadata.tokenURI(id_);

        return param_;

    }

    /// @notice Filters the contract uri for the collection
    function filter_Meta_collectionUri(uint id_, Polly.Param memory param_) public view returns (Polly.Param memory) {

        if(id_ != 0) return param_; // Return if not the collection id = 0

        // Set the contract uri on the param struct
        param_._string = metadata.contractURI();

        return param_;

    }



}


contract WingbeatsMetadata {

    string public constant NAME = "Wingbeats";
    string public constant DESCRIPTION = "Wingbeats is a collection of 97 unique NFTs, each representing a fraction of a 40-minute experimental composition by the group Paris Peacock. Holding a Wingbeats NFT grants you access to the full music, liner notes and more on the Wingbeats website.";

    function tokenURI(uint id_) public view returns (string memory string_) {

        Wingbeats wingbeats_ = Wingbeats(msg.sender);
        Token721 collection = wingbeats_.collection();

        Json json_ = Json(wingbeats_.polly().getModule("Json", 1).implementation);

        string memory content_base_ = collection.getMeta(0, 'baseUri')._string;
        string memory image_uri_ = string(abi.encodePacked(content_base_, '/jpg/', Strings.toString(id_), '.jpg'));
        string memory audio_uri_ = string(abi.encodePacked(content_base_, '/mp3/', Strings.toString(id_), '.mp3'));
        string memory external_url_ = string(abi.encodePacked(collection.getMeta(0, 'externalUrlBase')._string, '/', Strings.toString(id_)));

        Json.Item[] memory items_ = new Json.Item[](6);

        items_[0]._key = "name";
        items_[0]._type = Json.Type.STRING;
        items_[0]._string = string(abi.encodePacked(NAME, " #", Strings.toString(id_)));

        items_[1]._key = "description";
        items_[1]._type = Json.Type.STRING;
        items_[1]._string = DESCRIPTION;

        items_[2]._key = "image";
        items_[2]._type = Json.Type.STRING;
        items_[2]._string = image_uri_;

        items_[3]._key = "license";
        items_[3]._type = Json.Type.STRING;
        items_[3]._string = "All rights reserved";

        items_[4]._key = "animation_url";
        items_[4]._type = Json.Type.STRING;
        items_[4]._string = audio_uri_;

        items_[5]._key = "external_url";
        items_[5]._type = Json.Type.STRING;
        items_[5]._string = external_url_;


        // Encode JSON and create data uri
        string_ = string(abi.encodePacked(
            'data:application/json;base64,',
            Base64.encode(bytes(json_.encode(items_, Json.Format.OBJECT)))
        ));

        return string_;

    }


    function contractURI() public view returns (string memory string_) {

        Wingbeats wingbeats_ = Wingbeats(msg.sender);
        Token721 collection = wingbeats_.collection();

        Json json_ = Json(wingbeats_.polly().getModule("Json", 1).implementation);


        string memory content_base_ = collection.getMeta(0, 'baseUri')._string;


        // {
        //     "name": "OpenSea Creatures",
        //     "description": "OpenSea Creatures are adorable aquatic beings primarily for demonstrating what can be done using the OpenSea platform. Adopt one today to try out all the OpenSea buying, selling, and bidding feature set.",
        //     "image": "external-link-url/image.png",
        //     "external_link": "external-link-url",
        //     "seller_fee_basis_points": 100, # Indicates a 1% seller fee.
        //     "fee_recipient": "0xA97F337c39cccE66adfeCB2BF99C1DdC54C2D721" # Where seller fees will be paid to.
        // }

        Json.Item[] memory items_ = new Json.Item[](4);

        items_[0]._key = "name";
        items_[0]._type = Json.Type.STRING;
        items_[0]._string = NAME;

        items_[1]._key = "description";
        items_[1]._type = Json.Type.STRING;
        items_[1]._string = DESCRIPTION;

        items_[2]._key = "image";
        items_[2]._type = Json.Type.STRING;
        items_[2]._string = string(abi.encodePacked(content_base_, '/collection.jpg'));

        items_[3]._key = "external_link";
        items_[3]._type = Json.Type.STRING;
        items_[3]._string = collection.getMeta(0, 'externalLink')._string;

        // Encode JSON and create data uri
        string_ = string(abi.encodePacked(
            'data:application/json;base64,',
            Base64.encode(bytes(json_.encode(items_, Json.Format.OBJECT)))
        ));

        return string_;

    }

}